| //===- 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/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> | |
| using namespace llvm; | |
| using namespace polly; | |
| // Declared in LoopGenerators.cpp | |
| extern llvm::cl::opt<bool> PollyVectorizeMetadata; | |
| #define DEBUG_TYPE "polly-codegen" | |
| 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 { GNU, LLVM }; | |
| 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) { | |
| isl::ast_expr Cond = For.cond(); | |
| isl::ast_expr Iterator = For.iterator(); | |
| assert(isl_ast_expr_get_type(Cond.get()) == isl_ast_expr_op && | |
| "conditional expression is not an atomic upper bound"); | |
| isl_ast_op_type OpType = isl_ast_expr_get_op_type(Cond.get()); | |
| switch (OpType) { | |
| case isl_ast_op_le: | |
| Predicate = ICmpInst::ICMP_SLE; | |
| break; | |
| case isl_ast_op_lt: | |
| Predicate = ICmpInst::ICMP_SLT; | |
| break; | |
| default: | |
| llvm_unreachable("Unexpected comparison type in loop condition"); | |
| } | |
| isl::ast_expr Arg0 = Cond.get_op_arg(0); | |
| assert(isl_ast_expr_get_type(Arg0.get()) == isl_ast_expr_id && | |
| "conditional expression is not an atomic upper bound"); | |
| isl::id UBID = Arg0.get_id(); | |
| assert(isl_ast_expr_get_type(Iterator.get()) == isl_ast_expr_id && | |
| "Could not get the iterator"); | |
| isl::id IteratorID = Iterator.get_id(); | |
| assert(UBID.get() == IteratorID.get() && | |
| "conditional expression is not an atomic upper bound"); | |
| return Cond.get_op_arg(1); | |
| } | |
| int IslNodeBuilder::getNumberOfIterations(isl::ast_node_for For) { | |
| assert(isl_ast_node_get_type(For.get()) == isl_ast_node_for); | |
| isl::ast_node Body = For.body(); | |
| // First, check if we can actually handle this code. | |
| switch (isl_ast_node_get_type(Body.get())) { | |
| case isl_ast_node_user: | |
| break; | |
| case isl_ast_node_block: { | |
| isl::ast_node_block BodyBlock = Body.as<isl::ast_node_block>(); | |
| isl::ast_node_list List = BodyBlock.children(); | |
| for (isl::ast_node Node : List) { | |
| isl_ast_node_type NodeType = isl_ast_node_get_type(Node.get()); | |
| if (NodeType != isl_ast_node_user) | |
| return -1; | |
| } | |
| break; | |
| } | |
| default: | |
| return -1; | |
| } | |
| isl::ast_expr Init = For.init(); | |
| if (!Init.isa<isl::ast_expr_int>() || !Init.val().is_zero()) | |
| return -1; | |
| isl::ast_expr Inc = For.inc(); | |
| if (!Inc.isa<isl::ast_expr_int>() || !Inc.val().is_one()) | |
| return -1; | |
| CmpInst::Predicate Predicate; | |
| isl::ast_expr UB = getUpperBound(For, Predicate); | |
| if (!UB.isa<isl::ast_expr_int>()) | |
| return -1; | |
| isl::val UpVal = UB.get_val(); | |
| int NumberIterations = UpVal.get_num_si(); | |
| if (NumberIterations < 0) | |
| return -1; | |
| if (Predicate == CmpInst::ICMP_SLT) | |
| return NumberIterations; | |
| else | |
| return NumberIterations + 1; | |
| } | |
| static void findReferencesByUse(Value *SrcVal, ScopStmt *UserStmt, | |
| Loop *UserScope, const ValueMapT &GlobalMap, | |
| SetVector<Value *> &Values, | |
| SetVector<const SCEV *> &SCEVs) { | |
| VirtualUse VUse = VirtualUse::create(UserStmt, UserScope, SrcVal, true); | |
| switch (VUse.getKind()) { | |
| case VirtualUse::Constant: | |
| // When accelerator-offloading, GlobalValue is a host address whose content | |
| // must still be transferred to the GPU. | |
| if (isa<GlobalValue>(SrcVal)) | |
| Values.insert(SrcVal); | |
| break; | |
| case VirtualUse::Synthesizable: | |
| SCEVs.insert(VUse.getScevExpr()); | |
| return; | |
| case VirtualUse::Block: | |
| case VirtualUse::ReadOnly: | |
| case VirtualUse::Hoisted: | |
| case VirtualUse::Intra: | |
| case VirtualUse::Inter: | |
| break; | |
| } | |
| if (Value *NewVal = GlobalMap.lookup(SrcVal)) | |
| Values.insert(NewVal); | |
| } | |
| static void findReferencesInInst(Instruction *Inst, ScopStmt *UserStmt, | |
| Loop *UserScope, const ValueMapT &GlobalMap, | |
| SetVector<Value *> &Values, | |
| SetVector<const SCEV *> &SCEVs) { | |
| for (Use &U : Inst->operands()) | |
| findReferencesByUse(U.get(), UserStmt, UserScope, GlobalMap, Values, SCEVs); | |
| } | |
| static void findReferencesInStmt(ScopStmt *Stmt, SetVector<Value *> &Values, | |
| ValueMapT &GlobalMap, | |
| SetVector<const SCEV *> &SCEVs) { | |
| LoopInfo *LI = Stmt->getParent()->getLI(); | |
| BasicBlock *BB = Stmt->getBasicBlock(); | |
| // TODO: Should BB ever be null? | |
| Loop *Scope = BB ? LI->getLoopFor(BB) : nullptr; | |
| for (Instruction *Inst : Stmt->getInstructions()) | |
| findReferencesInInst(Inst, Stmt, Scope, GlobalMap, Values, SCEVs); | |
| if (Stmt->isRegionStmt()) { | |
| for (BasicBlock *BB : Stmt->getRegion()->blocks()) { | |
| Loop *Scope = LI->getLoopFor(BB); | |
| for (Instruction &Inst : *BB) | |
| findReferencesInInst(&Inst, Stmt, Scope, GlobalMap, Values, SCEVs); | |
| } | |
| } | |
| } | |
| void polly::addReferencesFromStmt(ScopStmt *Stmt, void *UserPtr, | |
| bool CreateScalarRefs) { | |
| auto &References = *static_cast<SubtreeReferences *>(UserPtr); | |
| findReferencesInStmt(Stmt, References.Values, References.GlobalMap, | |
| References.SCEVs); | |
| for (auto &Access : *Stmt) { | |
| if (References.ParamSpace) { | |
| isl::space ParamSpace = Access->getLatestAccessRelation().get_space(); | |
| (*References.ParamSpace) = | |
| References.ParamSpace->align_params(ParamSpace); | |
| } | |
| if (Access->isLatestArrayKind()) { | |
| auto *BasePtr = Access->getLatestScopArrayInfo()->getBasePtr(); | |
| if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr)) | |
| if (Stmt->getParent()->contains(OpInst)) | |
| continue; | |
| References.Values.insert(BasePtr); | |
| continue; | |
| } | |
| if (CreateScalarRefs) | |
| References.Values.insert(References.BlockGen.getOrCreateAlloca(*Access)); | |
| } | |
| } | |
| /// 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) { | |
| isl::id Id = Set.get_tuple_id(); | |
| auto *Stmt = static_cast<ScopStmt *>(Id.get_user()); | |
| addReferencesFromStmt(Stmt, 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) { | |
| for (isl::set Set : USet.get_set_list()) | |
| addReferencesFromStmtSet(Set, &References); | |
| } | |
| isl::union_map | |
| IslNodeBuilder::getScheduleForAstNode(const isl::ast_node &Node) { | |
| return IslAstInfo::getSchedule(Node); | |
| } | |
| void IslNodeBuilder::getReferencesInSubtree(const isl::ast_node &For, | |
| SetVector<Value *> &Values, | |
| SetVector<const Loop *> &Loops) { | |
| SetVector<const SCEV *> SCEVs; | |
| SubtreeReferences References = { | |
| LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator(), nullptr}; | |
| Values.insert_range(llvm::make_second_range(IDToValue)); | |
| // NOTE: this is populated in IslNodeBuilder::addParameters | |
| for (const auto &I : OutsideLoopIterations) | |
| Values.insert(cast<SCEVUnknown>(I.second)->getValue()); | |
| isl::union_set Schedule = getScheduleForAstNode(For).domain(); | |
| addReferencesFromStmtUnionSet(Schedule, References); | |
| for (const SCEV *Expr : SCEVs) { | |
| findValues(Expr, SE, Values); | |
| findLoops(Expr, Loops); | |
| } | |
| Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); }); | |
| /// Note: Code generation of induction variables of loops outside Scops | |
| /// | |
| /// Remove loops that contain the scop or that are part of the scop, as they | |
| /// are considered local. This leaves only loops that are before the scop, but | |
| /// do not contain the scop itself. | |
| /// We ignore loops perfectly contained in the Scop because these are already | |
| /// generated at `IslNodeBuilder::addParameters`. These `Loops` are loops | |
| /// whose induction variables are referred to by the Scop, but the Scop is not | |
| /// fully contained in these Loops. Since there can be many of these, | |
| /// we choose to codegen these on-demand. | |
| /// @see IslNodeBuilder::materializeNonScopLoopInductionVariable. | |
| Loops.remove_if([this](const Loop *L) { | |
| return S.contains(L) || L->contains(S.getEntry()); | |
| }); | |
| // Contains Values that may need to be replaced with other values | |
| // due to replacements from the ValueMap. We should make sure | |
| // that we return correctly remapped values. | |
| // NOTE: this code path is tested by: | |
| // 1. test/Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll | |
| // 2. test/Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll | |
| SetVector<Value *> ReplacedValues; | |
| for (Value *V : Values) { | |
| ReplacedValues.insert(getLatestValue(V)); | |
| } | |
| Values = ReplacedValues; | |
| } | |
| Value *IslNodeBuilder::getLatestValue(Value *Original) const { | |
| auto It = ValueMap.find(Original); | |
| if (It == ValueMap.end()) | |
| return Original; | |
| return It->second; | |
| } | |
| void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) { | |
| auto *Id = isl_ast_node_mark_get_id(Node); | |
| auto Child = isl_ast_node_mark_get_node(Node); | |
| isl_ast_node_free(Node); | |
| // If a child node of a 'SIMD mark' is a loop that has a single iteration, | |
| // it will be optimized away and we should skip it. | |
| if (strcmp(isl_id_get_name(Id), "SIMD") == 0 && | |
| isl_ast_node_get_type(Child) == isl_ast_node_for) { | |
| createForSequential(isl::manage(Child).as<isl::ast_node_for>(), true); | |
| isl_id_free(Id); | |
| return; | |
| } | |
| BandAttr *ChildLoopAttr = getLoopAttr(isl::manage_copy(Id)); | |
| BandAttr *AncestorLoopAttr; | |
| if (ChildLoopAttr) { | |
| // Save current LoopAttr environment to restore again when leaving this | |
| // subtree. This means there was no loop between the ancestor LoopAttr and | |
| // this mark, i.e. the ancestor LoopAttr did not directly mark a loop. This | |
| // can happen e.g. if the AST build peeled or unrolled the loop. | |
| AncestorLoopAttr = Annotator.getStagingAttrEnv(); | |
| Annotator.getStagingAttrEnv() = ChildLoopAttr; | |
| } | |
| create(Child); | |
| if (ChildLoopAttr) { | |
| assert(Annotator.getStagingAttrEnv() == ChildLoopAttr && | |
| "Nest must not overwrite loop attr environment"); | |
| Annotator.getStagingAttrEnv() = AncestorLoopAttr; | |
| } | |
| isl_id_free(Id); | |
| } | |
| /// 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) { | |
| assert(isl_ast_node_get_type(Node.get()) == isl_ast_node_for); | |
| isl::ast_node Body = Node.body(); | |
| if (isl_ast_node_get_type(Body.get()) != isl_ast_node_mark) | |
| return false; | |
| isl::ast_node_mark BodyMark = Body.as<isl::ast_node_mark>(); | |
| auto Id = BodyMark.id(); | |
| if (strcmp(Id.get_name().c_str(), "Loop Vectorizer Disabled") == 0) | |
| return true; | |
| return false; | |
| } | |
| /// Returns true if the loop has a dist=1 dependence involving FP operations | |
| /// (array-carried RAW/WAW or scalar FP reduction). In that case we omit the | |
| /// vectorize.enable annotation and let the Loop Vectorizer decide. | |
| static bool hasLoopCarriedDependence(isl::ast_node_for For, const Scop &S) { | |
| isl::pw_aff PwaDist = IslAstInfo::getMinimalDependenceDistance(For); | |
| if (PwaDist.is_null()) | |
| return false; | |
| isl::set Dist = isl::manage(isl_pw_aff_domain(PwaDist.copy())); | |
| isl::pw_aff PwaOne = isl::pw_aff(Dist, isl::val::one(S.getIslCtx())); | |
| if (isl_pw_aff_is_equal(PwaDist.get(), PwaOne.get()) != isl_bool_true) | |
| return false; | |
| // dist=1: suppress forced vectorization if the body has FP operations. | |
| for (isl::set StmtSet : | |
| IslAstInfo::getSchedule(For).domain().get_set_list()) { | |
| auto *Stmt = static_cast<ScopStmt *>(StmtSet.get_tuple_id().get_user()); | |
| for (Instruction *Inst : Stmt->getInstructions()) { | |
| if (Inst->getType()->isFloatingPointTy() || | |
| (Inst->getNumOperands() > 0 && | |
| Inst->getOperand(0)->getType()->isFloatingPointTy())) | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| /// Sign-extend or truncate V to Ty. | |
| /// | |
| /// Returns V unchanged if it already has type Ty, sign-extends it if | |
| /// Ty is wider, or truncates it if Ty is narrower. | |
| static Value *castToType(IRBuilderBase &Builder, Value *V, Type *Ty) { | |
| if (V->getType() == Ty) | |
| return V; | |
| return Builder.CreateSExtOrTrunc(V, Ty); | |
| } | |
| /// Returns true when V is known to fit in IntPtrTy without data loss. | |
| /// Accepts i64 constants such as 0 and 1 that ISL materialises as i64 even on | |
| /// 32-bit targets. | |
| static bool fitsInTy(Value *V, IntegerType *IntTy) { | |
| if (V->getType()->getIntegerBitWidth() <= IntTy->getBitWidth()) | |
| return true; | |
| if (auto *CI = dyn_cast<ConstantInt>(V)) | |
| return CI->getValue().isSignedIntN(IntTy->getBitWidth()); | |
| return false; | |
| } | |
| void IslNodeBuilder::createForSequential(isl::ast_node_for For, | |
| bool MarkParallel) { | |
| Value *ValueLB, *ValueUB, *ValueInc; | |
| Type *MaxType; | |
| BasicBlock *ExitBlock; | |
| Value *IV; | |
| CmpInst::Predicate Predicate; | |
| bool LoopVectorizerDisabled = IsLoopVectorizerDisabled(For); | |
| isl::ast_node Body = For.body(); | |
| // isl_ast_node_for_is_degenerate(For) | |
| // | |
| // TODO: For degenerated loops we could generate a plain assignment. | |
| // However, for now we just reuse the logic for normal loops, which will | |
| // create a loop with a single iteration. | |
| isl::ast_expr Init = For.init(); | |
| isl::ast_expr Inc = For.inc(); | |
| isl::ast_expr Iterator = For.iterator(); | |
| isl::id IteratorID = Iterator.get_id(); | |
| isl::ast_expr UB = getUpperBound(For, Predicate); | |
| ValueLB = ExprBuilder.create(Init.release()); | |
| ValueUB = ExprBuilder.create(UB.release()); | |
| ValueInc = ExprBuilder.create(Inc.release()); | |
| MaxType = ExprBuilder.getType(Iterator.get()); | |
| MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType()); | |
| MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType()); | |
| MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType()); | |
| // Narrow the IV type to pointer size when all three bounds are known to fit. | |
| // On 32-bit targets (e.g. Hexagon) this avoids i64 IVs and the truncations | |
| // they cause in loop bodies. This also allows Hexagon to represent loops as | |
| // Hardware loops. ISL materializes constants (e.g. LB=0, Inc=1) | |
| // as i64 even when they fit in i32, so we accept those via isSignedIntN. | |
| // Non-constant variables with a type wider than PtrBits are left unchanged | |
| // to avoid an unsafe truncation. | |
| IntegerType *IntPtrTy = Builder.getIntPtrTy(DL); | |
| if (MaxType->getIntegerBitWidth() > IntPtrTy->getBitWidth() && | |
| fitsInTy(ValueLB, IntPtrTy) && fitsInTy(ValueUB, IntPtrTy) && | |
| fitsInTy(ValueInc, IntPtrTy)) | |
| MaxType = IntPtrTy; | |
| // Coerce each bound to MaxType, using trunc when MaxType was narrowed. | |
| ValueLB = castToType(Builder, ValueLB, MaxType); | |
| ValueUB = castToType(Builder, ValueUB, MaxType); | |
| ValueInc = castToType(Builder, ValueInc, MaxType); | |
| // If we can show that LB <Predicate> UB holds at least once, we can | |
| // omit the GuardBB in front of the loop. | |
| bool UseGuardBB = !GenSE->isKnownPredicate(Predicate, GenSE->getSCEV(ValueLB), | |
| GenSE->getSCEV(ValueUB)); | |
| // FIXME: This is a workaround for | |
| // https://github.com/llvm/llvm-project/issues/198726. | |
| // llvm.loop.vectorize.enable=true has an additional property beyond | |
| // requesting vectorization — it implicitly allows FP operation reordering. | |
| // This is a limitation of the metadata format: there is no way to separate | |
| // the request for vectorization from the request for reassociating FP ops. | |
| // Once LoopVectorize is fixed to not reorder FP ops without explicit | |
| // permission, this workaround can be removed. | |
| // For now, skip vectorize.enable for dist=1 FP loops to avoid correctness | |
| // failures from FP reassociation. | |
| bool SkipVectorizeEnableMetadata = hasLoopCarriedDependence(For, S); | |
| IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, *GenLI, *GenDT, | |
| ExitBlock, Predicate, &Annotator, MarkParallel, UseGuardBB, | |
| LoopVectorizerDisabled, SkipVectorizeEnableMetadata); | |
| IDToValue[IteratorID.get()] = IV; | |
| create(Body.release()); | |
| Annotator.popLoop(MarkParallel); | |
| IDToValue.erase(IDToValue.find(IteratorID.get())); | |
| Builder.SetInsertPoint(ExitBlock->begin()); | |
| SequentialLoops++; | |
| } | |
| void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) { | |
| isl_ast_node *Body; | |
| isl_ast_expr *Init, *Inc, *Iterator, *UB; | |
| isl_id *IteratorID; | |
| Value *ValueLB, *ValueUB, *ValueInc; | |
| Type *MaxType; | |
| Value *IV; | |
| CmpInst::Predicate Predicate; | |
| // The preamble of parallel code interacts different than normal code with | |
| // e.g., scalar initialization. Therefore, we ensure the parallel code is | |
| // separated from the last basic block. | |
| BasicBlock *ParBB = | |
| SplitBlock(Builder.GetInsertBlock(), Builder.GetInsertPoint(), &DT, &LI); | |
| ParBB->setName("polly.parallel.for"); | |
| Builder.SetInsertPoint(ParBB->begin()); | |
| Body = isl_ast_node_for_get_body(For); | |
| Init = isl_ast_node_for_get_init(For); | |
| Inc = isl_ast_node_for_get_inc(For); | |
| Iterator = isl_ast_node_for_get_iterator(For); | |
| IteratorID = isl_ast_expr_get_id(Iterator); | |
| UB = getUpperBound(isl::manage_copy(For).as<isl::ast_node_for>(), Predicate) | |
| .release(); | |
| ValueLB = ExprBuilder.create(Init); | |
| ValueUB = ExprBuilder.create(UB); | |
| ValueInc = ExprBuilder.create(Inc); | |
| // OpenMP always uses SLE. In case the isl generated AST uses a SLT | |
| // expression, we need to adjust the loop bound by one. | |
| if (Predicate == CmpInst::ICMP_SLT) | |
| ValueUB = Builder.CreateAdd( | |
| ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType())); | |
| MaxType = ExprBuilder.getType(Iterator); | |
| MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType()); | |
| MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType()); | |
| MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType()); | |
| // Narrow the IV type to pointer size when all three bounds are known to fit. | |
| // On 32-bit targets (e.g. Hexagon) this avoids i64 IVs and the truncations | |
| // they cause in loop bodies. ISL materializes constants (e.g. LB=0, Inc=1) | |
| // as i64 even when they fit in i32, so we accept those via isSignedIntN. | |
| // Non-constant variables with a type wider than PtrBits are left unchanged | |
| // to avoid an unsafe truncation. | |
| IntegerType *IntPtrTy = Builder.getIntPtrTy(DL); | |
| if (MaxType->getIntegerBitWidth() > IntPtrTy->getBitWidth() && | |
| fitsInTy(ValueLB, IntPtrTy) && fitsInTy(ValueUB, IntPtrTy) && | |
| fitsInTy(ValueInc, IntPtrTy)) | |
| MaxType = IntPtrTy; | |
| // Coerce each bound to MaxType, using trunc when MaxType was narrowed. | |
| ValueLB = castToType(Builder, ValueLB, MaxType); | |
| ValueUB = castToType(Builder, ValueUB, MaxType); | |
| ValueInc = castToType(Builder, ValueInc, MaxType); | |
| BasicBlock::iterator LoopBody; | |
| SetVector<Value *> SubtreeValues; | |
| SetVector<const Loop *> Loops; | |
| getReferencesInSubtree(isl::manage_copy(For), SubtreeValues, Loops); | |
| // Create for all loops we depend on values that contain the current loop | |
| // iteration. These values are necessary to generate code for SCEVs that | |
| // depend on such loops. As a result we need to pass them to the subfunction. | |
| // See [Code generation of induction variables of loops outside Scops] | |
| for (const Loop *L : Loops) { | |
| Value *LoopInductionVar = materializeNonScopLoopInductionVariable(L); | |
| SubtreeValues.insert(LoopInductionVar); | |
| } | |
| ValueMapT NewValues; | |
| std::unique_ptr<ParallelLoopGenerator> ParallelLoopGenPtr; | |
| switch (PollyOmpBackend) { | |
| case OpenMPBackend::GNU: | |
| ParallelLoopGenPtr.reset(new ParallelLoopGeneratorGOMP(Builder, DL)); | |
| break; | |
| case OpenMPBackend::LLVM: | |
| ParallelLoopGenPtr.reset(new ParallelLoopGeneratorKMP(Builder, DL)); | |
| break; | |
| } | |
| IV = ParallelLoopGenPtr->createParallelLoop( | |
| ValueLB, ValueUB, ValueInc, SubtreeValues, NewValues, &LoopBody); | |
| BasicBlock::iterator AfterLoop = Builder.GetInsertPoint(); | |
| // Remember the parallel subfunction | |
| Function *SubFn = LoopBody->getFunction(); | |
| ParallelSubfunctions.push_back(SubFn); | |
| // We start working on the outlined function. Since DominatorTree/LoopInfo are | |
| // not an inter-procedural passes, we temporarily switch them out. Save the | |
| // old ones first. | |
| Function *CallerFn = Builder.GetInsertBlock()->getParent(); | |
| DominatorTree *CallerDT = GenDT; | |
| LoopInfo *CallerLI = GenLI; | |
| ScalarEvolution *CallerSE = GenSE; | |
| ValueMapT CallerGlobals = ValueMap; | |
| IslExprBuilder::IDToValueTy IDToValueCopy = IDToValue; | |
| MapVector<const Loop *, const SCEV *> OutsideLoopIterationsCopy = | |
| OutsideLoopIterations; | |
| // Get the analyses for the subfunction. ParallelLoopGenerator already create | |
| // DominatorTree and LoopInfo for us. | |
| DominatorTree *SubDT = ParallelLoopGenPtr->getCalleeDominatorTree(); | |
| LoopInfo *SubLI = ParallelLoopGenPtr->getCalleeLoopInfo(); | |
| // Create TargetLibraryInfo, AssumptionCachem and ScalarEvolution ourselves. | |
| // TODO: Ideally, we would use the pass manager's TargetLibraryInfoPass and | |
| // AssumptionAnalysis instead of our own. They contain more target-specific | |
| // information than we have available here: TargetLibraryInfoImpl can be a | |
| // derived class determined by TargetMachine, AssumptionCache can be | |
| // configured using a TargetTransformInfo object also derived from | |
| // TargetMachine. | |
| TargetLibraryInfoImpl BaselineInfoImpl(SubFn->getParent()->getTargetTriple()); | |
| TargetLibraryInfo CalleeTLI(BaselineInfoImpl, SubFn); | |
| AssumptionCache CalleeAC(*SubFn); | |
| std::unique_ptr<ScalarEvolution> SubSE = std::make_unique<ScalarEvolution>( | |
| *SubFn, CalleeTLI, CalleeAC, *SubDT, *SubLI); | |
| // Switch to the subfunction | |
| GenDT = SubDT; | |
| GenLI = SubLI; | |
| GenSE = SubSE.get(); | |
| BlockGen.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE); | |
| RegionGen.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE); | |
| ExprBuilder.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE); | |
| Builder.SetInsertPoint(LoopBody); | |
| // Update the ValueMap to use instructions in the subfunction. Note that | |
| // "GlobalMap" used in BlockGenerator/IslExprBuilder is a reference to this | |
| // ValueMap. | |
| ValueMap.remove_if([&](auto &P) { | |
| P.second = NewValues.lookup(P.second); | |
| // Clean up any value that getReferencesInSubtree thinks we do not need. | |
| return !P.second; | |
| }); | |
| // This is for NewVals that do not appear in ValueMap (such as SCoP-invariant | |
| // values whose original value can be reused as long as we are in the same | |
| // function). No need to map the others. | |
| for (auto &[NewVal, NewNewVal] : NewValues) { | |
| if (Instruction *NewValInst = dyn_cast<Instruction>((Value *)NewVal)) { | |
| if (S.contains(NewValInst)) | |
| continue; | |
| assert(NewValInst->getFunction() == &S.getFunction()); | |
| } | |
| assert(!ValueMap.contains(NewVal)); | |
| ValueMap[NewVal] = NewNewVal; | |
| } | |
| // Also update the IDToValue map to use instructions from the subfunction. | |
| for (auto &[OldVal, NewVal] : IDToValue) { | |
| NewVal = NewValues.lookup(NewVal); | |
| assert(NewVal); | |
| } | |
| IDToValue[IteratorID] = IV; | |
| // Also update OutsideLoopIterations to use values from the subfunction. | |
| // SCEVExpander may fold identity operations (e.g. x+0 -> x), returning the | |
| // original loop PHI instead of a new instruction. We need to remap these | |
| // values through NewValues so GenSE (now SubSE) doesn't operate on values | |
| // from the caller function. | |
| for (auto &[L, S] : OutsideLoopIterations) { | |
| if (auto *U = dyn_cast<SCEVUnknown>(S)) { | |
| Value *NewVal = NewValues.lookup(U->getValue()); | |
| assert(NewVal && "must have a new value"); | |
| OutsideLoopIterations[L] = GenSE->getUnknown(NewVal); | |
| } | |
| } | |
| #ifndef NDEBUG | |
| // Check whether the maps now exclusively refer to SubFn values. | |
| for (auto &[OldVal, SubVal] : ValueMap) { | |
| Instruction *SubInst = dyn_cast<Instruction>((Value *)SubVal); | |
| assert(SubInst->getFunction() == SubFn && | |
| "Instructions from outside the subfn cannot be accessed within the " | |
| "subfn"); | |
| } | |
| for (auto &[Id, SubVal] : IDToValue) { | |
| Instruction *SubInst = dyn_cast<Instruction>((Value *)SubVal); | |
| assert(SubInst->getFunction() == SubFn && | |
| "Instructions from outside the subfn cannot be accessed within the " | |
| "subfn"); | |
| } | |
| #endif | |
| ValueMapT NewValuesReverse; | |
| for (auto P : NewValues) | |
| NewValuesReverse[P.second] = P.first; | |
| Annotator.addAlternativeAliasBases(NewValuesReverse); | |
| create(Body); | |
| Annotator.resetAlternativeAliasBases(); | |
| // Resume working on the caller function. | |
| GenDT = CallerDT; | |
| GenLI = CallerLI; | |
| GenSE = CallerSE; | |
| IDToValue = std::move(IDToValueCopy); | |
| ValueMap = std::move(CallerGlobals); | |
| OutsideLoopIterations = std::move(OutsideLoopIterationsCopy); | |
| ExprBuilder.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE); | |
| RegionGen.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE); | |
| BlockGen.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE); | |
| Builder.SetInsertPoint(AfterLoop); | |
| isl_ast_node_free(For); | |
| isl_ast_expr_free(Iterator); | |
| isl_id_free(IteratorID); | |
| ParallelLoops++; | |
| } | |
| void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) { | |
| if (IslAstInfo::isExecutedInParallel(isl::manage_copy(For))) { | |
| createForParallel(For); | |
| return; | |
| } | |
| bool Parallel = (IslAstInfo::isParallel(isl::manage_copy(For)) && | |
| !IslAstInfo::isReductionParallel(isl::manage_copy(For))); | |
| createForSequential(isl::manage(For).as<isl::ast_node_for>(), Parallel); | |
| } | |
| void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) { | |
| isl_ast_expr *Cond = isl_ast_node_if_get_cond(If); | |
| Function *F = Builder.GetInsertBlock()->getParent(); | |
| LLVMContext &Context = F->getContext(); | |
| BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(), | |
| Builder.GetInsertPoint(), GenDT, GenLI); | |
| CondBB->setName("polly.cond"); | |
| BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), GenDT, GenLI); | |
| MergeBB->setName("polly.merge"); | |
| BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F); | |
| BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F); | |
| GenDT->addNewBlock(ThenBB, CondBB); | |
| GenDT->addNewBlock(ElseBB, CondBB); | |
| GenDT->changeImmediateDominator(MergeBB, CondBB); | |
| Loop *L = GenLI->getLoopFor(CondBB); | |
| if (L) { | |
| L->addBasicBlockToLoop(ThenBB, *GenLI); | |
| L->addBasicBlockToLoop(ElseBB, *GenLI); | |
| } | |
| CondBB->getTerminator()->eraseFromParent(); | |
| Builder.SetInsertPoint(CondBB); | |
| Value *Predicate = ExprBuilder.create(Cond); | |
| Builder.CreateCondBr(Predicate, ThenBB, ElseBB); | |
| Builder.SetInsertPoint(ThenBB); | |
| Builder.CreateBr(MergeBB); | |
| Builder.SetInsertPoint(ElseBB); | |
| Builder.CreateBr(MergeBB); | |
| Builder.SetInsertPoint(ThenBB->begin()); | |
| create(isl_ast_node_if_get_then(If)); | |
| Builder.SetInsertPoint(ElseBB->begin()); | |
| if (isl_ast_node_if_has_else(If)) | |
| create(isl_ast_node_if_get_else(If)); | |
| Builder.SetInsertPoint(MergeBB->begin()); | |
| isl_ast_node_free(If); | |
| IfConditions++; | |
| } | |
| __isl_give isl_id_to_ast_expr * | |
| IslNodeBuilder::createNewAccesses(ScopStmt *Stmt, | |
| __isl_keep isl_ast_node *Node) { | |
| isl::id_to_ast_expr NewAccesses = | |
| isl::id_to_ast_expr::alloc(Stmt->getParent()->getIslCtx(), 0); | |
| isl::ast_build Build = IslAstInfo::getBuild(isl::manage_copy(Node)); | |
| assert(!Build.is_null() && "Could not obtain isl_ast_build from user node"); | |
| Stmt->setAstBuild(Build); | |
| for (auto *MA : *Stmt) { | |
| if (!MA->hasNewAccessRelation()) { | |
| if (PollyGenerateExpressions) { | |
| if (!MA->isAffine()) | |
| continue; | |
| if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI()) | |
| continue; | |
| auto *BasePtr = | |
| dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr()); | |
| if (BasePtr && Stmt->getParent()->getRegion().contains(BasePtr)) | |
| continue; | |
| } else { | |
| continue; | |
| } | |
| } | |
| assert(MA->isAffine() && | |
| "Only affine memory accesses can be code generated"); | |
| isl::union_map Schedule = Build.get_schedule(); | |
| #ifndef NDEBUG | |
| if (MA->isRead()) { | |
| auto Dom = Stmt->getDomain().release(); | |
| auto SchedDom = isl_set_from_union_set(Schedule.domain().release()); | |
| auto AccDom = isl_map_domain(MA->getAccessRelation().release()); | |
| Dom = isl_set_intersect_params(Dom, | |
| Stmt->getParent()->getContext().release()); | |
| SchedDom = isl_set_intersect_params( | |
| SchedDom, Stmt->getParent()->getContext().release()); | |
| // Restrict to defined behavior context to match DeLICM's contract: | |
| // new read accesses are only required to cover the defined-behavior | |
| // subset of the domain. | |
| auto *DefinedBehavior = | |
| Stmt->getParent()->getBestKnownDefinedBehaviorContext().release(); | |
| SchedDom = | |
| isl_set_intersect_params(SchedDom, isl_set_copy(DefinedBehavior)); | |
| Dom = isl_set_intersect_params(Dom, DefinedBehavior); | |
| assert(isl_set_is_subset(SchedDom, AccDom) != isl_bool_false && | |
| "Access relation not defined on full schedule domain"); | |
| assert(isl_set_is_subset(Dom, AccDom) != isl_bool_false && | |
| "Access relation not defined on full domain"); | |
| isl_set_free(AccDom); | |
| isl_set_free(SchedDom); | |
| isl_set_free(Dom); | |
| } | |
| #endif | |
| isl::pw_multi_aff PWAccRel = MA->applyScheduleToAccessRelation(Schedule); | |
| // isl cannot generate an index expression for access-nothing accesses. | |
| isl::set AccDomain = PWAccRel.domain(); | |
| if (AccDomain.is_empty()) | |
| continue; | |
| isl::ast_expr AccessExpr = Build.access_from(PWAccRel); | |
| NewAccesses = NewAccesses.set(MA->getId(), AccessExpr); | |
| } | |
| return NewAccesses.release(); | |
| } | |
| void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr, | |
| ScopStmt *Stmt, LoopToScevMapT <S) { | |
| assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && | |
| "Expression of type 'op' expected"); | |
| assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_call && | |
| "Operation of type 'call' expected"); | |
| for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr) - 1; ++i) { | |
| isl_ast_expr *SubExpr; | |
| Value *V; | |
| SubExpr = isl_ast_expr_get_op_arg(Expr, i + 1); | |
| V = ExprBuilder.create(SubExpr); | |
| ScalarEvolution *SE = Stmt->getParent()->getSE(); | |
| LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V); | |
| } | |
| isl_ast_expr_free(Expr); | |
| } | |
| void IslNodeBuilder::createSubstitutionsVector( | |
| __isl_take isl_ast_expr *Expr, ScopStmt *Stmt, | |
| std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS, | |
| __isl_take isl_id *IteratorID) { | |
| int i = 0; | |
| Value *OldValue = IDToValue[IteratorID]; | |
| for (Value *IV : IVS) { | |
| IDToValue[IteratorID] = IV; | |
| createSubstitutions(isl_ast_expr_copy(Expr), Stmt, VLTS[i]); | |
| i++; | |
| } | |
| IDToValue[IteratorID] = OldValue; | |
| isl_id_free(IteratorID); | |
| isl_ast_expr_free(Expr); | |
| } | |
| void IslNodeBuilder::generateCopyStmt( | |
| ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) { | |
| assert(Stmt->size() == 2); | |
| auto ReadAccess = Stmt->begin(); | |
| auto WriteAccess = ReadAccess++; | |
| assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite()); | |
| assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() && | |
| "Accesses use the same data type"); | |
| assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind()); | |
| auto *AccessExpr = | |
| isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId().release()); | |
| auto *LoadValue = ExprBuilder.create(AccessExpr); | |
| AccessExpr = | |
| isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release()); | |
| auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr).first; | |
| Builder.CreateStore(LoadValue, StoreAddr); | |
| } | |
| Value *IslNodeBuilder::materializeNonScopLoopInductionVariable(const Loop *L) { | |
| assert(!OutsideLoopIterations.contains(L) && | |
| "trying to materialize loop induction variable twice"); | |
| const SCEV *OuterLIV = | |
| SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)), | |
| SE.getUnknown(Builder.getInt64(1)), L, SCEV::FlagNone); | |
| Value *V = generateSCEV(OuterLIV); | |
| OutsideLoopIterations[L] = SE.getUnknown(V); | |
| return V; | |
| } | |
| void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) { | |
| LoopToScevMapT LTS; | |
| isl_id *Id; | |
| ScopStmt *Stmt; | |
| isl_ast_expr *Expr = isl_ast_node_user_get_expr(User); | |
| isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0); | |
| Id = isl_ast_expr_get_id(StmtExpr); | |
| isl_ast_expr_free(StmtExpr); | |
| LTS.insert_range(OutsideLoopIterations); | |
| Stmt = (ScopStmt *)isl_id_get_user(Id); | |
| auto *NewAccesses = createNewAccesses(Stmt, User); | |
| if (Stmt->isCopyStmt()) { | |
| generateCopyStmt(Stmt, NewAccesses); | |
| isl_ast_expr_free(Expr); | |
| } else { | |
| createSubstitutions(Expr, Stmt, LTS); | |
| if (Stmt->isBlockStmt()) | |
| BlockGen.copyStmt(*Stmt, LTS, NewAccesses); | |
| else | |
| RegionGen.copyStmt(*Stmt, LTS, NewAccesses); | |
| } | |
| isl_id_to_ast_expr_free(NewAccesses); | |
| isl_ast_node_free(User); | |
| isl_id_free(Id); | |
| } | |
| void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) { | |
| isl_ast_node_list *List = isl_ast_node_block_get_children(Block); | |
| for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i) | |
| create(isl_ast_node_list_get_ast_node(List, i)); | |
| isl_ast_node_free(Block); | |
| isl_ast_node_list_free(List); | |
| } | |
| void IslNodeBuilder::generateBeginScopTrace() { | |
| if (!TraceStmts) | |
| return; | |
| // Sequence of strings to print. | |
| SmallVector<llvm::Value *, 8> Values; | |
| Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "Scop: ")); | |
| auto Params = S.getParamSpace(); | |
| for (int i : rangeIslSize(0, Params.dim(isl::dim::param))) { | |
| if (i != 0) | |
| Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " ")); | |
| isl::id PId = Params.get_dim_id(isl::dim::param, i); | |
| Values.push_back( | |
| RuntimeDebugBuilder::getPrintableString(Builder, PId.get_name())); | |
| Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "=")); | |
| Values.push_back(IDToValue.lookup(PId.get())); | |
| } | |
| Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n")); | |
| RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values)); | |
| } | |
| void IslNodeBuilder::create(__isl_take isl_ast_node *Node) { | |
| switch (isl_ast_node_get_type(Node)) { | |
| case isl_ast_node_error: | |
| llvm_unreachable("code generation error"); | |
| case isl_ast_node_mark: | |
| createMark(Node); | |
| return; | |
| case isl_ast_node_for: | |
| createFor(Node); | |
| return; | |
| case isl_ast_node_if: | |
| createIf(Node); | |
| return; | |
| case isl_ast_node_user: | |
| createUser(Node); | |
| return; | |
| case isl_ast_node_block: | |
| createBlock(Node); | |
| return; | |
| } | |
| llvm_unreachable("Unknown isl_ast_node type"); | |
| } | |
| bool IslNodeBuilder::materializeValue(__isl_take isl_id *Id) { | |
| // If the Id is already mapped, skip it. | |
| if (!IDToValue.count(Id)) { | |
| auto *ParamSCEV = (const SCEV *)isl_id_get_user(Id); | |
| Value *V = nullptr; | |
| // Parameters could refer to invariant loads that need to be | |
| // preloaded before we can generate code for the parameter. Thus, | |
| // check if any value referred to in ParamSCEV is an invariant load | |
| // and if so make sure its equivalence class is preloaded. | |
| SetVector<Value *> Values; | |
| findValues(ParamSCEV, SE, Values); | |
| for (auto *Val : Values) { | |
| // Check if the value is an instruction in a dead block within the SCoP | |
| // and if so do not code generate it. | |
| if (auto *Inst = dyn_cast<Instruction>(Val)) { | |
| if (S.contains(Inst)) { | |
| bool IsDead = true; | |
| // Check for "undef" loads first, then if there is a statement for | |
| // the parent of Inst and lastly if the parent of Inst has an empty | |
| // domain. In the first and last case the instruction is dead but if | |
| // there is a statement or the domain is not empty Inst is not dead. | |
| auto MemInst = MemAccInst::dyn_cast(Inst); | |
| auto Address = MemInst ? MemInst.getPointerOperand() : nullptr; | |
| if (Address && SE.getUnknown(UndefValue::get(Address->getType())) == | |
| SE.getPointerBase(SE.getSCEV(Address))) { | |
| } else if (S.getStmtFor(Inst)) { | |
| IsDead = false; | |
| } else { | |
| auto *Domain = S.getDomainConditions(Inst->getParent()).release(); | |
| IsDead = isl_set_is_empty(Domain); | |
| isl_set_free(Domain); | |
| } | |
| if (IsDead) { | |
| V = UndefValue::get(ParamSCEV->getType()); | |
| break; | |
| } | |
| } | |
| } | |
| if (auto *IAClass = S.lookupInvariantEquivClass(Val)) { | |
| // Check if this invariant access class is empty, hence if we never | |
| // actually added a loads instruction to it. In that case it has no | |
| // (meaningful) users and we should not try to code generate it. | |
| if (IAClass->InvariantAccesses.empty()) | |
| V = UndefValue::get(ParamSCEV->getType()); | |
| if (!preloadInvariantEquivClass(*IAClass)) { | |
| isl_id_free(Id); | |
| return false; | |
| } | |
| } | |
| } | |
| V = V ? V : generateSCEV(ParamSCEV); | |
| IDToValue[Id] = V; | |
| } | |
| isl_id_free(Id); | |
| return true; | |
| } | |
| bool IslNodeBuilder::materializeParameters(__isl_keep isl_set *Set) { | |
| for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) { | |
| if (!isl_set_involves_dims(Set, isl_dim_param, i, 1)) | |
| continue; | |
| isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i); | |
| if (!materializeValue(Id)) | |
| return false; | |
| } | |
| return true; | |
| } | |
| bool IslNodeBuilder::materializeParameters() { | |
| for (const SCEV *Param : S.parameters()) { | |
| isl_id *Id = S.getIdForParam(Param).release(); | |
| if (!materializeValue(Id)) | |
| return false; | |
| } | |
| return true; | |
| } | |
| Value *IslNodeBuilder::preloadUnconditionally(isl::set AccessRange, | |
| isl::ast_build Build, | |
| Instruction *AccInst) { | |
| isl::pw_multi_aff PWAccRel = isl::pw_multi_aff::from_set(AccessRange); | |
| PWAccRel = PWAccRel.gist_params(S.getContext()); | |
| isl::ast_expr Access = Build.access_from(PWAccRel); | |
| isl::ast_expr Address = Access.address_of(); | |
| Value *AddressValue = ExprBuilder.create(Address.release()); | |
| Value *PreloadVal; | |
| // Correct the type as the SAI might have a different type than the user | |
| // expects, especially if the base pointer is a struct. | |
| Type *Ty = AccInst->getType(); | |
| auto *Ptr = AddressValue; | |
| auto Name = Ptr->getName(); | |
| PreloadVal = Builder.CreateLoad(Ty, Ptr, Name + ".load"); | |
| if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal)) | |
| PreloadInst->setAlignment(cast<LoadInst>(AccInst)->getAlign()); | |
| return PreloadVal; | |
| } | |
| Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA, | |
| isl::set Domain) { | |
| isl::set AccessRange = MA.getAddressFunction().range(); | |
| if (!materializeParameters(AccessRange.get())) | |
| return nullptr; | |
| isl::ast_build Build = | |
| isl::ast_build::from_context(isl::set::universe(S.getParamSpace())); | |
| isl::set Universe = isl::set::universe(Domain.get_space()); | |
| bool AlwaysExecuted = Domain.is_equal(Universe); | |
| Instruction *AccInst = MA.getAccessInstruction(); | |
| Type *AccInstTy = AccInst->getType(); | |
| if (AlwaysExecuted) | |
| return preloadUnconditionally(AccessRange, Build, AccInst); | |
| if (!materializeParameters(Domain.get())) | |
| return nullptr; | |
| isl::ast_expr DomainCond = Build.expr_from(Domain); | |
| ExprBuilder.setTrackOverflow(true); | |
| Value *Cond = ExprBuilder.createBool(DomainCond.release()); | |
| Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(), | |
| "polly.preload.cond.overflown"); | |
| Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result"); | |
| ExprBuilder.setTrackOverflow(false); | |
| if (!Cond->getType()->isIntegerTy(1)) | |
| Cond = Builder.CreateIsNotNull(Cond); | |
| BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(), | |
| Builder.GetInsertPoint(), GenDT, GenLI); | |
| CondBB->setName("polly.preload.cond"); | |
| BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), GenDT, GenLI); | |
| MergeBB->setName("polly.preload.merge"); | |
| Function *F = Builder.GetInsertBlock()->getParent(); | |
| LLVMContext &Context = F->getContext(); | |
| BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F); | |
| GenDT->addNewBlock(ExecBB, CondBB); | |
| if (Loop *L = GenLI->getLoopFor(CondBB)) | |
| L->addBasicBlockToLoop(ExecBB, *GenLI); | |
| auto *CondBBTerminator = CondBB->getTerminator(); | |
| Builder.SetInsertPoint(CondBBTerminator->getIterator()); | |
| Builder.CreateCondBr(Cond, ExecBB, MergeBB); | |
| CondBBTerminator->eraseFromParent(); | |
| Builder.SetInsertPoint(ExecBB); | |
| Builder.CreateBr(MergeBB); | |
| Builder.SetInsertPoint(ExecBB->getTerminator()->getIterator()); | |
| Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst); | |
| Builder.SetInsertPoint(MergeBB->getTerminator()->getIterator()); | |
| auto *MergePHI = Builder.CreatePHI( | |
| AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge"); | |
| Value *PreloadVal = MergePHI; | |
| if (!PreAccInst) { | |
| PreloadVal = nullptr; | |
| PreAccInst = UndefValue::get(AccInstTy); | |
| } | |
| MergePHI->addIncoming(PreAccInst, ExecBB); | |
| MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB); | |
| return PreloadVal; | |
| } | |
| bool IslNodeBuilder::preloadInvariantEquivClass( | |
| InvariantEquivClassTy &IAClass) { | |
| // For an equivalence class of invariant loads we pre-load the representing | |
| // element with the unified execution context. However, we have to map all | |
| // elements of the class to the one preloaded load as they are referenced | |
| // during the code generation and therefore need to be mapped. | |
| const MemoryAccessList &MAs = IAClass.InvariantAccesses; | |
| if (MAs.empty()) | |
| return true; | |
| MemoryAccess *MA = MAs.front(); | |
| assert(MA->isArrayKind() && MA->isRead()); | |
| // If the access function was already mapped, the preload of this equivalence | |
| // class was triggered earlier already and doesn't need to be done again. | |
| if (ValueMap.count(MA->getAccessInstruction())) | |
| return true; | |
| // Check for recursion which can be caused by additional constraints, e.g., | |
| // non-finite loop constraints. In such a case we have to bail out and insert | |
| // a "false" runtime check that will cause the original code to be executed. | |
| auto PtrId = std::make_pair(IAClass.IdentifyingPointer, IAClass.AccessType); | |
| if (!PreloadedPtrs.insert(PtrId).second) | |
| return false; | |
| // The execution context of the IAClass. | |
| isl::set &ExecutionCtx = IAClass.ExecutionContext; | |
| // If the base pointer of this class is dependent on another one we have to | |
| // make sure it was preloaded already. | |
| auto *SAI = MA->getScopArrayInfo(); | |
| if (auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr())) { | |
| if (!preloadInvariantEquivClass(*BaseIAClass)) | |
| return false; | |
| // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and | |
| // we need to refine the ExecutionCtx. | |
| isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext; | |
| ExecutionCtx = ExecutionCtx.intersect(BaseExecutionCtx); | |
| } | |
| // If the size of a dimension is dependent on another class, make sure it is | |
| // preloaded. | |
| for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) { | |
| const SCEV *Dim = SAI->getDimensionSize(i); | |
| SetVector<Value *> Values; | |
| findValues(Dim, SE, Values); | |
| for (auto *Val : Values) { | |
| if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) { | |
| if (!preloadInvariantEquivClass(*BaseIAClass)) | |
| return false; | |
| // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx | |
| // and we need to refine the ExecutionCtx. | |
| isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext; | |
| ExecutionCtx = ExecutionCtx.intersect(BaseExecutionCtx); | |
| } | |
| } | |
| } | |
| Instruction *AccInst = MA->getAccessInstruction(); | |
| Type *AccInstTy = AccInst->getType(); | |
| Value *PreloadVal = preloadInvariantLoad(*MA, ExecutionCtx); | |
| if (!PreloadVal) | |
| return false; | |
| for (const MemoryAccess *MA : MAs) { | |
| Instruction *MAAccInst = MA->getAccessInstruction(); | |
| assert(PreloadVal->getType() == MAAccInst->getType()); | |
| ValueMap[MAAccInst] = PreloadVal; | |
| } | |
| if (SE.isSCEVable(AccInstTy)) { | |
| isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst)).release(); | |
| if (ParamId) | |
| IDToValue[ParamId] = PreloadVal; | |
| isl_id_free(ParamId); | |
| } | |
| BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock(); | |
| auto *Alloca = new AllocaInst(AccInstTy, DL.getAllocaAddrSpace(), | |
| AccInst->getName() + ".preload.s2a", | |
| EntryBB->getFirstInsertionPt()); | |
| Builder.CreateStore(PreloadVal, Alloca); | |
| ValueMapT PreloadedPointer; | |
| PreloadedPointer[PreloadVal] = AccInst; | |
| Annotator.addAlternativeAliasBases(PreloadedPointer); | |
| for (auto *DerivedSAI : SAI->getDerivedSAIs()) { | |
| Value *BasePtr = DerivedSAI->getBasePtr(); | |
| for (const MemoryAccess *MA : MAs) { | |
| // As the derived SAI information is quite coarse, any load from the | |
| // current SAI could be the base pointer of the derived SAI, however we | |
| // should only change the base pointer of the derived SAI if we actually | |
| // preloaded it. | |
| if (BasePtr == MA->getOriginalBaseAddr()) { | |
| assert(BasePtr->getType() == PreloadVal->getType()); | |
| DerivedSAI->setBasePtr(PreloadVal); | |
| } | |
| // For scalar derived SAIs we remap the alloca used for the derived value. | |
| if (BasePtr == MA->getAccessInstruction()) | |
| ScalarMap[DerivedSAI] = Alloca; | |
| } | |
| } | |
| for (const MemoryAccess *MA : MAs) { | |
| Instruction *MAAccInst = MA->getAccessInstruction(); | |
| // Use the escape system to get the correct value to users outside the SCoP. | |
| BlockGenerator::EscapeUserVectorTy EscapeUsers; | |
| for (auto *U : MAAccInst->users()) | |
| if (Instruction *UI = dyn_cast<Instruction>(U)) | |
| if (!S.contains(UI)) | |
| EscapeUsers.push_back(UI); | |
| if (EscapeUsers.empty()) | |
| continue; | |
| EscapeMap[MA->getAccessInstruction()] = | |
| std::make_pair(Alloca, std::move(EscapeUsers)); | |
| } | |
| return true; | |
| } | |
| void IslNodeBuilder::allocateNewArrays(BBPair StartExitBlocks) { | |
| for (auto &SAI : S.arrays()) { | |
| if (SAI->getBasePtr()) | |
| continue; | |
| assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) && | |
| "The size of the outermost dimension is used to declare newly " | |
| "created arrays that require memory allocation."); | |
| Type *NewArrayType = nullptr; | |
| // Get the size of the array = size(dim_1)*...*size(dim_n) | |
| uint64_t ArraySizeInt = 1; | |
| for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) { | |
| auto *DimSize = SAI->getDimensionSize(i); | |
| unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize) | |
| ->getAPInt() | |
| .getLimitedValue(); | |
| if (!NewArrayType) | |
| NewArrayType = SAI->getElementType(); | |
| NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize); | |
| ArraySizeInt *= UnsignedDimSize; | |
| } | |
| if (SAI->isOnHeap()) { | |
| LLVMContext &Ctx = NewArrayType->getContext(); | |
| // Get the IntPtrTy from the Datalayout | |
| auto IntPtrTy = DL.getIntPtrType(Ctx); | |
| // Get the size of the element type in bits | |
| unsigned Size = SAI->getElemSizeInBytes(); | |
| // Insert the malloc call at polly.start | |
| BasicBlock *StartBlock = std::get<0>(StartExitBlocks); | |
| Builder.SetInsertPoint(StartBlock->getTerminator()->getIterator()); | |
| auto *CreatedArray = Builder.CreateMalloc( | |
| IntPtrTy, ConstantInt::get(Type::getInt64Ty(Ctx), Size), | |
| ConstantInt::get(Type::getInt64Ty(Ctx), ArraySizeInt), nullptr, | |
| SAI->getName()); | |
| SAI->setBasePtr(CreatedArray); | |
| // Insert the free call at polly.exiting | |
| BasicBlock *ExitingBlock = std::get<1>(StartExitBlocks); | |
| Builder.SetInsertPoint(ExitingBlock->getTerminator()->getIterator()); | |
| Builder.CreateFree(CreatedArray); | |
| } else { | |
| auto InstIt = Builder.GetInsertBlock() | |
| ->getParent() | |
| ->getEntryBlock() | |
| .getTerminator() | |
| ->getIterator(); | |
| auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(), | |
| SAI->getName(), InstIt); | |
| if (PollyTargetFirstLevelCacheLineSize) | |
| CreatedArray->setAlignment(Align(PollyTargetFirstLevelCacheLineSize)); | |
| SAI->setBasePtr(CreatedArray); | |
| } | |
| } | |
| } | |
| bool IslNodeBuilder::preloadInvariantLoads() { | |
| auto &InvariantEquivClasses = S.getInvariantAccesses(); | |
| if (InvariantEquivClasses.empty()) | |
| return true; | |
| BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(), | |
| Builder.GetInsertPoint(), GenDT, GenLI); | |
| PreLoadBB->setName("polly.preload.begin"); | |
| Builder.SetInsertPoint(PreLoadBB->begin()); | |
| for (auto &IAClass : InvariantEquivClasses) | |
| if (!preloadInvariantEquivClass(IAClass)) | |
| return false; | |
| return true; | |
| } | |
| void IslNodeBuilder::addParameters(__isl_take isl_set *Context) { | |
| // Materialize values for the parameters of the SCoP. | |
| materializeParameters(); | |
| // Generate values for the current loop iteration for all surrounding loops. | |
| // | |
| // We may also reference loops outside of the scop which do not contain the | |
| // scop itself, but as the number of such scops may be arbitrarily large we do | |
| // not generate code for them here, but only at the point of code generation | |
| // where these values are needed. | |
| Loop *L = LI.getLoopFor(S.getEntry()); | |
| while (L != nullptr && S.contains(L)) | |
| L = L->getParentLoop(); | |
| while (L != nullptr) { | |
| materializeNonScopLoopInductionVariable(L); | |
| L = L->getParentLoop(); | |
| } | |
| isl_set_free(Context); | |
| } | |
| Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) { | |
| /// We pass the insert location of our Builder, as Polly ensures during IR | |
| /// generation that there is always a valid CFG into which instructions are | |
| /// inserted. As a result, the insertpoint is known to be always followed by a | |
| /// terminator instruction. This means the insert point may be specified by a | |
| /// terminator instruction, but it can never point to an ->end() iterator | |
| /// which does not have a corresponding instruction. Hence, dereferencing | |
| /// the insertpoint to obtain an instruction is known to be save. | |
| /// | |
| /// We also do not need to update the Builder here, as new instructions are | |
| /// always inserted _before_ the given InsertLocation. As a result, the | |
| /// insert location remains valid. | |
| assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() && | |
| "Insert location points after last valid instruction"); | |
| BasicBlock::iterator InsertLocation = Builder.GetInsertPoint(); | |
| return expandCodeFor(S, SE, Builder.GetInsertBlock()->getParent(), *GenSE, DL, | |
| "polly", Expr, Expr->getType(), InsertLocation, | |
| &ValueMap, /*LoopToScevMap*/ nullptr, | |
| StartBlock->getSinglePredecessor()); | |
| } | |
| /// 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) { | |
| auto ExprBuilder = getExprBuilder(); | |
| // In case the AST expression has integers larger than 64 bit, bail out. The | |
| // resulting LLVM-IR will contain operations on types that use more than 64 | |
| // bits. These are -- in case wrapping intrinsics are used -- translated to | |
| // runtime library calls that are not available on all systems (e.g., Android) | |
| // and consequently will result in linker errors. | |
| if (ExprBuilder.hasLargeInts(isl::manage_copy(Condition))) { | |
| isl_ast_expr_free(Condition); | |
| return Builder.getFalse(); | |
| } | |
| ExprBuilder.setTrackOverflow(true); | |
| Value *RTC = ExprBuilder.create(Condition); | |
| if (!RTC->getType()->isIntegerTy(1)) | |
| RTC = Builder.CreateIsNotNull(RTC); | |
| Value *OverflowHappened = | |
| Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown"); | |
| if (PollyGenerateRTCPrint) { | |
| auto *F = Builder.GetInsertBlock()->getParent(); | |
| RuntimeDebugBuilder::createCPUPrinter( | |
| Builder, | |
| "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() + | |
| "RTC: ", | |
| RTC, " Overflow: ", OverflowHappened, | |
| "\n" | |
| " (0 failed, -1 succeeded)\n" | |
| " (if one or both are 0 falling back to original code, if both are -1 " | |
| "executing Polly code)\n"); | |
| } | |
| RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result"); | |
| ExprBuilder.setTrackOverflow(false); | |
| if (!isa<ConstantInt>(RTC)) | |
| VersionedScops++; | |
| return RTC; | |
| } |