IslNodeBuilder.cpp | Explore in Territory

//===- IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains the IslNodeBuilder, a class to translate an isl AST into
// a LLVM-IR AST.
//
//===----------------------------------------------------------------------===//

#include "polly/CodeGen/IslNodeBuilder.h"
#include "polly/CodeGen/BlockGenerators.h"
#include "polly/CodeGen/CodeGeneration.h"
#include "polly/CodeGen/IslAst.h"
#include "polly/CodeGen/IslExprBuilder.h"
#include "polly/CodeGen/LoopGeneratorsGOMP.h"
#include "polly/CodeGen/LoopGeneratorsKMP.h"
#include "polly/CodeGen/RuntimeDebugBuilder.h"
#include "polly/Options.h"
#include "polly/ScopInfo.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/SCEVValidator.h"
#include "polly/Support/ScopHelper.h"
#include "polly/Support/VirtualInstruction.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/TargetParser/Triple.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "isl/aff.h"
#include "isl/aff_type.h"
#include "isl/ast.h"
#include "isl/ast_build.h"
#include "isl/isl-noexceptions.h"
#include "isl/map.h"
#include "isl/set.h"
#include "isl/union_map.h"
#include "isl/union_set.h"
#include "isl/val.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <string>
#include <utility>
#include <vector>

usingnamespacellvm;
usingnamespacepolly;

#define DEBUG_TYPE …

STATISTIC(VersionedScops, "Number of SCoPs that required versioning.");

STATISTIC(SequentialLoops, "Number of generated sequential for-loops");
STATISTIC(ParallelLoops, "Number of generated parallel for-loops");
STATISTIC(IfConditions, "Number of generated if-conditions");

/// OpenMP backend options
enum class OpenMPBackend { … };

static cl::opt<bool> PollyGenerateRTCPrint(
    "polly-codegen-emit-rtc-print",
    cl::desc("Emit code that prints the runtime check result dynamically."),
    cl::Hidden, cl::cat(PollyCategory));

// If this option is set we always use the isl AST generator to regenerate
// memory accesses. Without this option set we regenerate expressions using the
// original SCEV expressions and only generate new expressions in case the
// access relation has been changed and consequently must be regenerated.
static cl::opt<bool> PollyGenerateExpressions(
    "polly-codegen-generate-expressions",
    cl::desc("Generate AST expressions for unmodified and modified accesses"),
    cl::Hidden, cl::cat(PollyCategory));

static cl::opt<int> PollyTargetFirstLevelCacheLineSize(
    "polly-target-first-level-cache-line-size",
    cl::desc("The size of the first level cache line size specified in bytes."),
    cl::Hidden, cl::init(64), cl::cat(PollyCategory));

static cl::opt<OpenMPBackend> PollyOmpBackend(
    "polly-omp-backend", cl::desc("Choose the OpenMP library to use:"),
    cl::values(clEnumValN(OpenMPBackend::GNU, "GNU", "GNU OpenMP"),
               clEnumValN(OpenMPBackend::LLVM, "LLVM", "LLVM OpenMP")),
    cl::Hidden, cl::init(OpenMPBackend::GNU), cl::cat(PollyCategory));

isl::ast_expr IslNodeBuilder::getUpperBound(isl::ast_node_for For,
                                            ICmpInst::Predicate &Predicate) { … }

int IslNodeBuilder::getNumberOfIterations(isl::ast_node_for For) { … }

static void findReferencesByUse(Value *SrcVal, ScopStmt *UserStmt,
                                Loop *UserScope, const ValueMapT &GlobalMap,
                                SetVector<Value *> &Values,
                                SetVector<const SCEV *> &SCEVs) { … }

static void findReferencesInInst(Instruction *Inst, ScopStmt *UserStmt,
                                 Loop *UserScope, const ValueMapT &GlobalMap,
                                 SetVector<Value *> &Values,
                                 SetVector<const SCEV *> &SCEVs) { … }

static void findReferencesInStmt(ScopStmt *Stmt, SetVector<Value *> &Values,
                                 ValueMapT &GlobalMap,
                                 SetVector<const SCEV *> &SCEVs) { … }

void polly::addReferencesFromStmt(ScopStmt *Stmt, void *UserPtr,
                                  bool CreateScalarRefs) { … }

/// Extract the out-of-scop values and SCEVs referenced from a set describing
/// a ScopStmt.
///
/// This includes the SCEVUnknowns referenced by the SCEVs used in the
/// statement and the base pointers of the memory accesses. For scalar
/// statements we force the generation of alloca memory locations and list
/// these locations in the set of out-of-scop values as well.
///
/// @param Set     A set which references the ScopStmt we are interested in.
/// @param UserPtr A void pointer that can be casted to a SubtreeReferences
///                structure.
static void addReferencesFromStmtSet(isl::set Set, SubtreeReferences *UserPtr) { … }

/// Extract the out-of-scop values and SCEVs referenced from a union set
/// referencing multiple ScopStmts.
///
/// This includes the SCEVUnknowns referenced by the SCEVs used in the
/// statement and the base pointers of the memory accesses. For scalar
/// statements we force the generation of alloca memory locations and list
/// these locations in the set of out-of-scop values as well.
///
/// @param USet       A union set referencing the ScopStmts we are interested
///                   in.
/// @param References The SubtreeReferences data structure through which
///                   results are returned and further information is
///                   provided.
static void addReferencesFromStmtUnionSet(isl::union_set USet,
                                          SubtreeReferences &References) { … }

isl::union_map
IslNodeBuilder::getScheduleForAstNode(const isl::ast_node &Node) { … }

void IslNodeBuilder::getReferencesInSubtree(const isl::ast_node &For,
                                            SetVector<Value *> &Values,
                                            SetVector<const Loop *> &Loops) { … }

Value *IslNodeBuilder::getLatestValue(Value *Original) const { … }

void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) { … }

/// Restore the initial ordering of dimensions of the band node
///
/// In case the band node represents all the dimensions of the iteration
/// domain, recreate the band node to restore the initial ordering of the
/// dimensions.
///
/// @param Node The band node to be modified.
/// @return The modified schedule node.
static bool IsLoopVectorizerDisabled(isl::ast_node_for Node) { … }

void IslNodeBuilder::createForSequential(isl::ast_node_for For,
                                         bool MarkParallel) { … }

void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) { … }

void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) { … }

void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) { … }

__isl_give isl_id_to_ast_expr *
IslNodeBuilder::createNewAccesses(ScopStmt *Stmt,
                                  __isl_keep isl_ast_node *Node) { … }

void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,
                                         ScopStmt *Stmt, LoopToScevMapT &LTS) { … }

void IslNodeBuilder::createSubstitutionsVector(
    __isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
    std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,
    __isl_take isl_id *IteratorID) { … }

void IslNodeBuilder::generateCopyStmt(
    ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) { … }

Value *IslNodeBuilder::materializeNonScopLoopInductionVariable(const Loop *L) { … }

void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) { … }

void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) { … }

void IslNodeBuilder::create(__isl_take isl_ast_node *Node) { … }

bool IslNodeBuilder::materializeValue(__isl_take isl_id *Id) { … }

bool IslNodeBuilder::materializeParameters(__isl_take isl_set *Set) { … }

bool IslNodeBuilder::materializeParameters() { … }

Value *IslNodeBuilder::preloadUnconditionally(__isl_take isl_set *AccessRange,
                                              isl_ast_build *Build,
                                              Instruction *AccInst) { … }

Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
                                            __isl_take isl_set *Domain) { … }

bool IslNodeBuilder::preloadInvariantEquivClass(
    InvariantEquivClassTy &IAClass) { … }

void IslNodeBuilder::allocateNewArrays(BBPair StartExitBlocks) { … }

bool IslNodeBuilder::preloadInvariantLoads() { … }

void IslNodeBuilder::addParameters(__isl_take isl_set *Context) { … }

Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) { … }

/// The AST expression we generate to perform the run-time check assumes
/// computations on integer types of infinite size. As we only use 64-bit
/// arithmetic we check for overflows, in case of which we set the result
/// of this run-time check to false to be conservatively correct,
Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) { … }
llvm/polly/lib/CodeGen/IslNodeBuilder.cpp
