1457 lines · cpp
1//===- IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST -------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains the IslNodeBuilder, a class to translate an isl AST into10// a LLVM-IR AST.11//12//===----------------------------------------------------------------------===//13 14#include "polly/CodeGen/IslNodeBuilder.h"15#include "polly/CodeGen/BlockGenerators.h"16#include "polly/CodeGen/CodeGeneration.h"17#include "polly/CodeGen/IslAst.h"18#include "polly/CodeGen/IslExprBuilder.h"19#include "polly/CodeGen/LoopGeneratorsGOMP.h"20#include "polly/CodeGen/LoopGeneratorsKMP.h"21#include "polly/CodeGen/RuntimeDebugBuilder.h"22#include "polly/Options.h"23#include "polly/ScopInfo.h"24#include "polly/Support/ISLTools.h"25#include "polly/Support/SCEVValidator.h"26#include "polly/Support/ScopHelper.h"27#include "polly/Support/VirtualInstruction.h"28#include "llvm/ADT/APInt.h"29#include "llvm/ADT/PostOrderIterator.h"30#include "llvm/ADT/SetVector.h"31#include "llvm/ADT/SmallPtrSet.h"32#include "llvm/ADT/Statistic.h"33#include "llvm/Analysis/AssumptionCache.h"34#include "llvm/Analysis/LoopInfo.h"35#include "llvm/Analysis/RegionInfo.h"36#include "llvm/Analysis/ScalarEvolution.h"37#include "llvm/Analysis/ScalarEvolutionExpressions.h"38#include "llvm/Analysis/TargetLibraryInfo.h"39#include "llvm/IR/BasicBlock.h"40#include "llvm/IR/Constant.h"41#include "llvm/IR/Constants.h"42#include "llvm/IR/DataLayout.h"43#include "llvm/IR/DerivedTypes.h"44#include "llvm/IR/Dominators.h"45#include "llvm/IR/Function.h"46#include "llvm/IR/InstrTypes.h"47#include "llvm/IR/Instruction.h"48#include "llvm/IR/Instructions.h"49#include "llvm/IR/Module.h"50#include "llvm/IR/Type.h"51#include "llvm/IR/Value.h"52#include "llvm/Support/Casting.h"53#include "llvm/Support/CommandLine.h"54#include "llvm/Support/ErrorHandling.h"55#include "llvm/TargetParser/Triple.h"56#include "llvm/Transforms/Utils/BasicBlockUtils.h"57#include "isl/aff.h"58#include "isl/aff_type.h"59#include "isl/ast.h"60#include "isl/ast_build.h"61#include "isl/isl-noexceptions.h"62#include "isl/map.h"63#include "isl/set.h"64#include "isl/union_map.h"65#include "isl/union_set.h"66#include "isl/val.h"67#include <algorithm>68#include <cassert>69#include <cstdint>70#include <cstring>71#include <string>72#include <utility>73#include <vector>74 75using namespace llvm;76using namespace polly;77 78#define DEBUG_TYPE "polly-codegen"79 80STATISTIC(VersionedScops, "Number of SCoPs that required versioning.");81 82STATISTIC(SequentialLoops, "Number of generated sequential for-loops");83STATISTIC(ParallelLoops, "Number of generated parallel for-loops");84STATISTIC(IfConditions, "Number of generated if-conditions");85 86/// OpenMP backend options87enum class OpenMPBackend { GNU, LLVM };88 89static cl::opt<bool> PollyGenerateRTCPrint(90 "polly-codegen-emit-rtc-print",91 cl::desc("Emit code that prints the runtime check result dynamically."),92 cl::Hidden, cl::cat(PollyCategory));93 94// If this option is set we always use the isl AST generator to regenerate95// memory accesses. Without this option set we regenerate expressions using the96// original SCEV expressions and only generate new expressions in case the97// access relation has been changed and consequently must be regenerated.98static cl::opt<bool> PollyGenerateExpressions(99 "polly-codegen-generate-expressions",100 cl::desc("Generate AST expressions for unmodified and modified accesses"),101 cl::Hidden, cl::cat(PollyCategory));102 103static cl::opt<int> PollyTargetFirstLevelCacheLineSize(104 "polly-target-first-level-cache-line-size",105 cl::desc("The size of the first level cache line size specified in bytes."),106 cl::Hidden, cl::init(64), cl::cat(PollyCategory));107 108static cl::opt<OpenMPBackend> PollyOmpBackend(109 "polly-omp-backend", cl::desc("Choose the OpenMP library to use:"),110 cl::values(clEnumValN(OpenMPBackend::GNU, "GNU", "GNU OpenMP"),111 clEnumValN(OpenMPBackend::LLVM, "LLVM", "LLVM OpenMP")),112 cl::Hidden, cl::init(OpenMPBackend::GNU), cl::cat(PollyCategory));113 114isl::ast_expr IslNodeBuilder::getUpperBound(isl::ast_node_for For,115 ICmpInst::Predicate &Predicate) {116 isl::ast_expr Cond = For.cond();117 isl::ast_expr Iterator = For.iterator();118 assert(isl_ast_expr_get_type(Cond.get()) == isl_ast_expr_op &&119 "conditional expression is not an atomic upper bound");120 121 isl_ast_op_type OpType = isl_ast_expr_get_op_type(Cond.get());122 123 switch (OpType) {124 case isl_ast_op_le:125 Predicate = ICmpInst::ICMP_SLE;126 break;127 case isl_ast_op_lt:128 Predicate = ICmpInst::ICMP_SLT;129 break;130 default:131 llvm_unreachable("Unexpected comparison type in loop condition");132 }133 134 isl::ast_expr Arg0 = Cond.get_op_arg(0);135 136 assert(isl_ast_expr_get_type(Arg0.get()) == isl_ast_expr_id &&137 "conditional expression is not an atomic upper bound");138 139 isl::id UBID = Arg0.get_id();140 141 assert(isl_ast_expr_get_type(Iterator.get()) == isl_ast_expr_id &&142 "Could not get the iterator");143 144 isl::id IteratorID = Iterator.get_id();145 146 assert(UBID.get() == IteratorID.get() &&147 "conditional expression is not an atomic upper bound");148 149 return Cond.get_op_arg(1);150}151 152int IslNodeBuilder::getNumberOfIterations(isl::ast_node_for For) {153 assert(isl_ast_node_get_type(For.get()) == isl_ast_node_for);154 isl::ast_node Body = For.body();155 156 // First, check if we can actually handle this code.157 switch (isl_ast_node_get_type(Body.get())) {158 case isl_ast_node_user:159 break;160 case isl_ast_node_block: {161 isl::ast_node_block BodyBlock = Body.as<isl::ast_node_block>();162 isl::ast_node_list List = BodyBlock.children();163 for (isl::ast_node Node : List) {164 isl_ast_node_type NodeType = isl_ast_node_get_type(Node.get());165 if (NodeType != isl_ast_node_user)166 return -1;167 }168 break;169 }170 default:171 return -1;172 }173 174 isl::ast_expr Init = For.init();175 if (!Init.isa<isl::ast_expr_int>() || !Init.val().is_zero())176 return -1;177 isl::ast_expr Inc = For.inc();178 if (!Inc.isa<isl::ast_expr_int>() || !Inc.val().is_one())179 return -1;180 CmpInst::Predicate Predicate;181 isl::ast_expr UB = getUpperBound(For, Predicate);182 if (!UB.isa<isl::ast_expr_int>())183 return -1;184 isl::val UpVal = UB.get_val();185 int NumberIterations = UpVal.get_num_si();186 if (NumberIterations < 0)187 return -1;188 if (Predicate == CmpInst::ICMP_SLT)189 return NumberIterations;190 else191 return NumberIterations + 1;192}193 194static void findReferencesByUse(Value *SrcVal, ScopStmt *UserStmt,195 Loop *UserScope, const ValueMapT &GlobalMap,196 SetVector<Value *> &Values,197 SetVector<const SCEV *> &SCEVs) {198 VirtualUse VUse = VirtualUse::create(UserStmt, UserScope, SrcVal, true);199 switch (VUse.getKind()) {200 case VirtualUse::Constant:201 // When accelerator-offloading, GlobalValue is a host address whose content202 // must still be transferred to the GPU.203 if (isa<GlobalValue>(SrcVal))204 Values.insert(SrcVal);205 break;206 207 case VirtualUse::Synthesizable:208 SCEVs.insert(VUse.getScevExpr());209 return;210 211 case VirtualUse::Block:212 case VirtualUse::ReadOnly:213 case VirtualUse::Hoisted:214 case VirtualUse::Intra:215 case VirtualUse::Inter:216 break;217 }218 219 if (Value *NewVal = GlobalMap.lookup(SrcVal))220 Values.insert(NewVal);221}222 223static void findReferencesInInst(Instruction *Inst, ScopStmt *UserStmt,224 Loop *UserScope, const ValueMapT &GlobalMap,225 SetVector<Value *> &Values,226 SetVector<const SCEV *> &SCEVs) {227 for (Use &U : Inst->operands())228 findReferencesByUse(U.get(), UserStmt, UserScope, GlobalMap, Values, SCEVs);229}230 231static void findReferencesInStmt(ScopStmt *Stmt, SetVector<Value *> &Values,232 ValueMapT &GlobalMap,233 SetVector<const SCEV *> &SCEVs) {234 LoopInfo *LI = Stmt->getParent()->getLI();235 236 BasicBlock *BB = Stmt->getBasicBlock();237 Loop *Scope = LI->getLoopFor(BB);238 for (Instruction *Inst : Stmt->getInstructions())239 findReferencesInInst(Inst, Stmt, Scope, GlobalMap, Values, SCEVs);240 241 if (Stmt->isRegionStmt()) {242 for (BasicBlock *BB : Stmt->getRegion()->blocks()) {243 Loop *Scope = LI->getLoopFor(BB);244 for (Instruction &Inst : *BB)245 findReferencesInInst(&Inst, Stmt, Scope, GlobalMap, Values, SCEVs);246 }247 }248}249 250void polly::addReferencesFromStmt(ScopStmt *Stmt, void *UserPtr,251 bool CreateScalarRefs) {252 auto &References = *static_cast<SubtreeReferences *>(UserPtr);253 254 findReferencesInStmt(Stmt, References.Values, References.GlobalMap,255 References.SCEVs);256 257 for (auto &Access : *Stmt) {258 if (References.ParamSpace) {259 isl::space ParamSpace = Access->getLatestAccessRelation().get_space();260 (*References.ParamSpace) =261 References.ParamSpace->align_params(ParamSpace);262 }263 264 if (Access->isLatestArrayKind()) {265 auto *BasePtr = Access->getLatestScopArrayInfo()->getBasePtr();266 if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr))267 if (Stmt->getParent()->contains(OpInst))268 continue;269 270 References.Values.insert(BasePtr);271 continue;272 }273 274 if (CreateScalarRefs)275 References.Values.insert(References.BlockGen.getOrCreateAlloca(*Access));276 }277}278 279/// Extract the out-of-scop values and SCEVs referenced from a set describing280/// a ScopStmt.281///282/// This includes the SCEVUnknowns referenced by the SCEVs used in the283/// statement and the base pointers of the memory accesses. For scalar284/// statements we force the generation of alloca memory locations and list285/// these locations in the set of out-of-scop values as well.286///287/// @param Set A set which references the ScopStmt we are interested in.288/// @param UserPtr A void pointer that can be casted to a SubtreeReferences289/// structure.290static void addReferencesFromStmtSet(isl::set Set, SubtreeReferences *UserPtr) {291 isl::id Id = Set.get_tuple_id();292 auto *Stmt = static_cast<ScopStmt *>(Id.get_user());293 addReferencesFromStmt(Stmt, UserPtr);294}295 296/// Extract the out-of-scop values and SCEVs referenced from a union set297/// referencing multiple ScopStmts.298///299/// This includes the SCEVUnknowns referenced by the SCEVs used in the300/// statement and the base pointers of the memory accesses. For scalar301/// statements we force the generation of alloca memory locations and list302/// these locations in the set of out-of-scop values as well.303///304/// @param USet A union set referencing the ScopStmts we are interested305/// in.306/// @param References The SubtreeReferences data structure through which307/// results are returned and further information is308/// provided.309static void addReferencesFromStmtUnionSet(isl::union_set USet,310 SubtreeReferences &References) {311 312 for (isl::set Set : USet.get_set_list())313 addReferencesFromStmtSet(Set, &References);314}315 316isl::union_map317IslNodeBuilder::getScheduleForAstNode(const isl::ast_node &Node) {318 return IslAstInfo::getSchedule(Node);319}320 321void IslNodeBuilder::getReferencesInSubtree(const isl::ast_node &For,322 SetVector<Value *> &Values,323 SetVector<const Loop *> &Loops) {324 SetVector<const SCEV *> SCEVs;325 SubtreeReferences References = {326 LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator(), nullptr};327 328 Values.insert_range(llvm::make_second_range(IDToValue));329 330 // NOTE: this is populated in IslNodeBuilder::addParameters331 for (const auto &I : OutsideLoopIterations)332 Values.insert(cast<SCEVUnknown>(I.second)->getValue());333 334 isl::union_set Schedule = getScheduleForAstNode(For).domain();335 addReferencesFromStmtUnionSet(Schedule, References);336 337 for (const SCEV *Expr : SCEVs) {338 findValues(Expr, SE, Values);339 findLoops(Expr, Loops);340 }341 342 Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); });343 344 /// Note: Code generation of induction variables of loops outside Scops345 ///346 /// Remove loops that contain the scop or that are part of the scop, as they347 /// are considered local. This leaves only loops that are before the scop, but348 /// do not contain the scop itself.349 /// We ignore loops perfectly contained in the Scop because these are already350 /// generated at `IslNodeBuilder::addParameters`. These `Loops` are loops351 /// whose induction variables are referred to by the Scop, but the Scop is not352 /// fully contained in these Loops. Since there can be many of these,353 /// we choose to codegen these on-demand.354 /// @see IslNodeBuilder::materializeNonScopLoopInductionVariable.355 Loops.remove_if([this](const Loop *L) {356 return S.contains(L) || L->contains(S.getEntry());357 });358 359 // Contains Values that may need to be replaced with other values360 // due to replacements from the ValueMap. We should make sure361 // that we return correctly remapped values.362 // NOTE: this code path is tested by:363 // 1. test/Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll364 // 2. test/Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll365 SetVector<Value *> ReplacedValues;366 for (Value *V : Values) {367 ReplacedValues.insert(getLatestValue(V));368 }369 Values = ReplacedValues;370}371 372Value *IslNodeBuilder::getLatestValue(Value *Original) const {373 auto It = ValueMap.find(Original);374 if (It == ValueMap.end())375 return Original;376 return It->second;377}378 379void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) {380 auto *Id = isl_ast_node_mark_get_id(Node);381 auto Child = isl_ast_node_mark_get_node(Node);382 isl_ast_node_free(Node);383 // If a child node of a 'SIMD mark' is a loop that has a single iteration,384 // it will be optimized away and we should skip it.385 if (strcmp(isl_id_get_name(Id), "SIMD") == 0 &&386 isl_ast_node_get_type(Child) == isl_ast_node_for) {387 createForSequential(isl::manage(Child).as<isl::ast_node_for>(), true);388 isl_id_free(Id);389 return;390 }391 392 BandAttr *ChildLoopAttr = getLoopAttr(isl::manage_copy(Id));393 BandAttr *AncestorLoopAttr;394 if (ChildLoopAttr) {395 // Save current LoopAttr environment to restore again when leaving this396 // subtree. This means there was no loop between the ancestor LoopAttr and397 // this mark, i.e. the ancestor LoopAttr did not directly mark a loop. This398 // can happen e.g. if the AST build peeled or unrolled the loop.399 AncestorLoopAttr = Annotator.getStagingAttrEnv();400 401 Annotator.getStagingAttrEnv() = ChildLoopAttr;402 }403 404 create(Child);405 406 if (ChildLoopAttr) {407 assert(Annotator.getStagingAttrEnv() == ChildLoopAttr &&408 "Nest must not overwrite loop attr environment");409 Annotator.getStagingAttrEnv() = AncestorLoopAttr;410 }411 412 isl_id_free(Id);413}414 415/// Restore the initial ordering of dimensions of the band node416///417/// In case the band node represents all the dimensions of the iteration418/// domain, recreate the band node to restore the initial ordering of the419/// dimensions.420///421/// @param Node The band node to be modified.422/// @return The modified schedule node.423static bool IsLoopVectorizerDisabled(isl::ast_node_for Node) {424 assert(isl_ast_node_get_type(Node.get()) == isl_ast_node_for);425 isl::ast_node Body = Node.body();426 if (isl_ast_node_get_type(Body.get()) != isl_ast_node_mark)427 return false;428 429 isl::ast_node_mark BodyMark = Body.as<isl::ast_node_mark>();430 auto Id = BodyMark.id();431 if (strcmp(Id.get_name().c_str(), "Loop Vectorizer Disabled") == 0)432 return true;433 return false;434}435 436void IslNodeBuilder::createForSequential(isl::ast_node_for For,437 bool MarkParallel) {438 Value *ValueLB, *ValueUB, *ValueInc;439 Type *MaxType;440 BasicBlock *ExitBlock;441 Value *IV;442 CmpInst::Predicate Predicate;443 444 bool LoopVectorizerDisabled = IsLoopVectorizerDisabled(For);445 446 isl::ast_node Body = For.body();447 448 // isl_ast_node_for_is_degenerate(For)449 //450 // TODO: For degenerated loops we could generate a plain assignment.451 // However, for now we just reuse the logic for normal loops, which will452 // create a loop with a single iteration.453 454 isl::ast_expr Init = For.init();455 isl::ast_expr Inc = For.inc();456 isl::ast_expr Iterator = For.iterator();457 isl::id IteratorID = Iterator.get_id();458 isl::ast_expr UB = getUpperBound(For, Predicate);459 460 ValueLB = ExprBuilder.create(Init.release());461 ValueUB = ExprBuilder.create(UB.release());462 ValueInc = ExprBuilder.create(Inc.release());463 464 MaxType = ExprBuilder.getType(Iterator.get());465 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());466 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());467 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());468 469 if (MaxType != ValueLB->getType())470 ValueLB = Builder.CreateSExt(ValueLB, MaxType);471 if (MaxType != ValueUB->getType())472 ValueUB = Builder.CreateSExt(ValueUB, MaxType);473 if (MaxType != ValueInc->getType())474 ValueInc = Builder.CreateSExt(ValueInc, MaxType);475 476 // If we can show that LB <Predicate> UB holds at least once, we can477 // omit the GuardBB in front of the loop.478 bool UseGuardBB = !GenSE->isKnownPredicate(Predicate, GenSE->getSCEV(ValueLB),479 GenSE->getSCEV(ValueUB));480 IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, *GenLI, *GenDT,481 ExitBlock, Predicate, &Annotator, MarkParallel, UseGuardBB,482 LoopVectorizerDisabled);483 IDToValue[IteratorID.get()] = IV;484 485 create(Body.release());486 487 Annotator.popLoop(MarkParallel);488 489 IDToValue.erase(IDToValue.find(IteratorID.get()));490 491 Builder.SetInsertPoint(ExitBlock, ExitBlock->begin());492 493 SequentialLoops++;494}495 496void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {497 isl_ast_node *Body;498 isl_ast_expr *Init, *Inc, *Iterator, *UB;499 isl_id *IteratorID;500 Value *ValueLB, *ValueUB, *ValueInc;501 Type *MaxType;502 Value *IV;503 CmpInst::Predicate Predicate;504 505 // The preamble of parallel code interacts different than normal code with506 // e.g., scalar initialization. Therefore, we ensure the parallel code is507 // separated from the last basic block.508 BasicBlock *ParBB =509 SplitBlock(Builder.GetInsertBlock(), Builder.GetInsertPoint(), &DT, &LI);510 ParBB->setName("polly.parallel.for");511 Builder.SetInsertPoint(ParBB, ParBB->begin());512 513 Body = isl_ast_node_for_get_body(For);514 Init = isl_ast_node_for_get_init(For);515 Inc = isl_ast_node_for_get_inc(For);516 Iterator = isl_ast_node_for_get_iterator(For);517 IteratorID = isl_ast_expr_get_id(Iterator);518 UB = getUpperBound(isl::manage_copy(For).as<isl::ast_node_for>(), Predicate)519 .release();520 521 ValueLB = ExprBuilder.create(Init);522 ValueUB = ExprBuilder.create(UB);523 ValueInc = ExprBuilder.create(Inc);524 525 // OpenMP always uses SLE. In case the isl generated AST uses a SLT526 // expression, we need to adjust the loop bound by one.527 if (Predicate == CmpInst::ICMP_SLT)528 ValueUB = Builder.CreateAdd(529 ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));530 531 MaxType = ExprBuilder.getType(Iterator);532 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());533 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());534 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());535 536 if (MaxType != ValueLB->getType())537 ValueLB = Builder.CreateSExt(ValueLB, MaxType);538 if (MaxType != ValueUB->getType())539 ValueUB = Builder.CreateSExt(ValueUB, MaxType);540 if (MaxType != ValueInc->getType())541 ValueInc = Builder.CreateSExt(ValueInc, MaxType);542 543 BasicBlock::iterator LoopBody;544 545 SetVector<Value *> SubtreeValues;546 SetVector<const Loop *> Loops;547 548 getReferencesInSubtree(isl::manage_copy(For), SubtreeValues, Loops);549 550 // Create for all loops we depend on values that contain the current loop551 // iteration. These values are necessary to generate code for SCEVs that552 // depend on such loops. As a result we need to pass them to the subfunction.553 // See [Code generation of induction variables of loops outside Scops]554 for (const Loop *L : Loops) {555 Value *LoopInductionVar = materializeNonScopLoopInductionVariable(L);556 SubtreeValues.insert(LoopInductionVar);557 }558 559 ValueMapT NewValues;560 561 std::unique_ptr<ParallelLoopGenerator> ParallelLoopGenPtr;562 563 switch (PollyOmpBackend) {564 case OpenMPBackend::GNU:565 ParallelLoopGenPtr.reset(new ParallelLoopGeneratorGOMP(Builder, DL));566 break;567 case OpenMPBackend::LLVM:568 ParallelLoopGenPtr.reset(new ParallelLoopGeneratorKMP(Builder, DL));569 break;570 }571 572 IV = ParallelLoopGenPtr->createParallelLoop(573 ValueLB, ValueUB, ValueInc, SubtreeValues, NewValues, &LoopBody);574 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();575 576 // Remember the parallel subfunction577 Function *SubFn = LoopBody->getFunction();578 ParallelSubfunctions.push_back(SubFn);579 580 // We start working on the outlined function. Since DominatorTree/LoopInfo are581 // not an inter-procedural passes, we temporarily switch them out. Save the582 // old ones first.583 Function *CallerFn = Builder.GetInsertBlock()->getParent();584 DominatorTree *CallerDT = GenDT;585 LoopInfo *CallerLI = GenLI;586 ScalarEvolution *CallerSE = GenSE;587 ValueMapT CallerGlobals = ValueMap;588 IslExprBuilder::IDToValueTy IDToValueCopy = IDToValue;589 590 // Get the analyses for the subfunction. ParallelLoopGenerator already create591 // DominatorTree and LoopInfo for us.592 DominatorTree *SubDT = ParallelLoopGenPtr->getCalleeDominatorTree();593 LoopInfo *SubLI = ParallelLoopGenPtr->getCalleeLoopInfo();594 595 // Create TargetLibraryInfo, AssumptionCachem and ScalarEvolution ourselves.596 // TODO: Ideally, we would use the pass manager's TargetLibraryInfoPass and597 // AssumptionAnalysis instead of our own. They contain more target-specific598 // information than we have available here: TargetLibraryInfoImpl can be a599 // derived class determined by TargetMachine, AssumptionCache can be600 // configured using a TargetTransformInfo object also derived from601 // TargetMachine.602 TargetLibraryInfoImpl BaselineInfoImpl(SubFn->getParent()->getTargetTriple());603 TargetLibraryInfo CalleeTLI(BaselineInfoImpl, SubFn);604 AssumptionCache CalleeAC(*SubFn);605 std::unique_ptr<ScalarEvolution> SubSE = std::make_unique<ScalarEvolution>(606 *SubFn, CalleeTLI, CalleeAC, *SubDT, *SubLI);607 608 // Switch to the subfunction609 GenDT = SubDT;610 GenLI = SubLI;611 GenSE = SubSE.get();612 BlockGen.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE);613 RegionGen.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE);614 ExprBuilder.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE);615 Builder.SetInsertPoint(LoopBody);616 617 // Update the ValueMap to use instructions in the subfunction. Note that618 // "GlobalMap" used in BlockGenerator/IslExprBuilder is a reference to this619 // ValueMap.620 for (auto &[OldVal, NewVal] : ValueMap) {621 NewVal = NewValues.lookup(NewVal);622 623 // Clean-up any value that getReferencesInSubtree thinks we do not need.624 // DenseMap::erase only writes a tombstone (and destroys OldVal/NewVal), so625 // does not invalidate our iterator.626 if (!NewVal)627 ValueMap.erase(OldVal);628 }629 630 // This is for NewVals that do not appear in ValueMap (such as SCoP-invariant631 // values whose original value can be reused as long as we are in the same632 // function). No need to map the others.633 for (auto &[NewVal, NewNewVal] : NewValues) {634 if (Instruction *NewValInst = dyn_cast<Instruction>((Value *)NewVal)) {635 if (S.contains(NewValInst))636 continue;637 assert(NewValInst->getFunction() == &S.getFunction());638 }639 assert(!ValueMap.contains(NewVal));640 ValueMap[NewVal] = NewNewVal;641 }642 643 // Also update the IDToValue map to use instructions from the subfunction.644 for (auto &[OldVal, NewVal] : IDToValue) {645 NewVal = NewValues.lookup(NewVal);646 assert(NewVal);647 }648 IDToValue[IteratorID] = IV;649 650#ifndef NDEBUG651 // Check whether the maps now exclusively refer to SubFn values.652 for (auto &[OldVal, SubVal] : ValueMap) {653 Instruction *SubInst = dyn_cast<Instruction>((Value *)SubVal);654 assert(SubInst->getFunction() == SubFn &&655 "Instructions from outside the subfn cannot be accessed within the "656 "subfn");657 }658 for (auto &[Id, SubVal] : IDToValue) {659 Instruction *SubInst = dyn_cast<Instruction>((Value *)SubVal);660 assert(SubInst->getFunction() == SubFn &&661 "Instructions from outside the subfn cannot be accessed within the "662 "subfn");663 }664#endif665 666 ValueMapT NewValuesReverse;667 for (auto P : NewValues)668 NewValuesReverse[P.second] = P.first;669 670 Annotator.addAlternativeAliasBases(NewValuesReverse);671 672 create(Body);673 674 Annotator.resetAlternativeAliasBases();675 676 // Resume working on the caller function.677 GenDT = CallerDT;678 GenLI = CallerLI;679 GenSE = CallerSE;680 IDToValue = std::move(IDToValueCopy);681 ValueMap = std::move(CallerGlobals);682 ExprBuilder.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE);683 RegionGen.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE);684 BlockGen.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE);685 Builder.SetInsertPoint(AfterLoop);686 687 for (const Loop *L : Loops)688 OutsideLoopIterations.erase(L);689 690 isl_ast_node_free(For);691 isl_ast_expr_free(Iterator);692 isl_id_free(IteratorID);693 694 ParallelLoops++;695}696 697void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {698 if (IslAstInfo::isExecutedInParallel(isl::manage_copy(For))) {699 createForParallel(For);700 return;701 }702 bool Parallel = (IslAstInfo::isParallel(isl::manage_copy(For)) &&703 !IslAstInfo::isReductionParallel(isl::manage_copy(For)));704 createForSequential(isl::manage(For).as<isl::ast_node_for>(), Parallel);705}706 707void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) {708 isl_ast_expr *Cond = isl_ast_node_if_get_cond(If);709 710 Function *F = Builder.GetInsertBlock()->getParent();711 LLVMContext &Context = F->getContext();712 713 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),714 Builder.GetInsertPoint(), GenDT, GenLI);715 CondBB->setName("polly.cond");716 BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), GenDT, GenLI);717 MergeBB->setName("polly.merge");718 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);719 BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F);720 721 GenDT->addNewBlock(ThenBB, CondBB);722 GenDT->addNewBlock(ElseBB, CondBB);723 GenDT->changeImmediateDominator(MergeBB, CondBB);724 725 Loop *L = GenLI->getLoopFor(CondBB);726 if (L) {727 L->addBasicBlockToLoop(ThenBB, *GenLI);728 L->addBasicBlockToLoop(ElseBB, *GenLI);729 }730 731 CondBB->getTerminator()->eraseFromParent();732 733 Builder.SetInsertPoint(CondBB);734 Value *Predicate = ExprBuilder.create(Cond);735 Builder.CreateCondBr(Predicate, ThenBB, ElseBB);736 Builder.SetInsertPoint(ThenBB);737 Builder.CreateBr(MergeBB);738 Builder.SetInsertPoint(ElseBB);739 Builder.CreateBr(MergeBB);740 Builder.SetInsertPoint(ThenBB, ThenBB->begin());741 742 create(isl_ast_node_if_get_then(If));743 744 Builder.SetInsertPoint(ElseBB, ElseBB->begin());745 746 if (isl_ast_node_if_has_else(If))747 create(isl_ast_node_if_get_else(If));748 749 Builder.SetInsertPoint(MergeBB, MergeBB->begin());750 751 isl_ast_node_free(If);752 753 IfConditions++;754}755 756__isl_give isl_id_to_ast_expr *757IslNodeBuilder::createNewAccesses(ScopStmt *Stmt,758 __isl_keep isl_ast_node *Node) {759 isl::id_to_ast_expr NewAccesses =760 isl::id_to_ast_expr::alloc(Stmt->getParent()->getIslCtx(), 0);761 762 isl::ast_build Build = IslAstInfo::getBuild(isl::manage_copy(Node));763 assert(!Build.is_null() && "Could not obtain isl_ast_build from user node");764 Stmt->setAstBuild(Build);765 766 for (auto *MA : *Stmt) {767 if (!MA->hasNewAccessRelation()) {768 if (PollyGenerateExpressions) {769 if (!MA->isAffine())770 continue;771 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())772 continue;773 774 auto *BasePtr =775 dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());776 if (BasePtr && Stmt->getParent()->getRegion().contains(BasePtr))777 continue;778 } else {779 continue;780 }781 }782 assert(MA->isAffine() &&783 "Only affine memory accesses can be code generated");784 785 isl::union_map Schedule = Build.get_schedule();786 787#ifndef NDEBUG788 if (MA->isRead()) {789 auto Dom = Stmt->getDomain().release();790 auto SchedDom = isl_set_from_union_set(Schedule.domain().release());791 auto AccDom = isl_map_domain(MA->getAccessRelation().release());792 Dom = isl_set_intersect_params(Dom,793 Stmt->getParent()->getContext().release());794 SchedDom = isl_set_intersect_params(795 SchedDom, Stmt->getParent()->getContext().release());796 assert(isl_set_is_subset(SchedDom, AccDom) &&797 "Access relation not defined on full schedule domain");798 assert(isl_set_is_subset(Dom, AccDom) &&799 "Access relation not defined on full domain");800 isl_set_free(AccDom);801 isl_set_free(SchedDom);802 isl_set_free(Dom);803 }804#endif805 806 isl::pw_multi_aff PWAccRel = MA->applyScheduleToAccessRelation(Schedule);807 808 // isl cannot generate an index expression for access-nothing accesses.809 isl::set AccDomain = PWAccRel.domain();810 isl::set Context = S.getContext();811 AccDomain = AccDomain.intersect_params(Context);812 if (AccDomain.is_empty())813 continue;814 815 isl::ast_expr AccessExpr = Build.access_from(PWAccRel);816 NewAccesses = NewAccesses.set(MA->getId(), AccessExpr);817 }818 819 return NewAccesses.release();820}821 822void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,823 ScopStmt *Stmt, LoopToScevMapT <S) {824 assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&825 "Expression of type 'op' expected");826 assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_call &&827 "Operation of type 'call' expected");828 for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr) - 1; ++i) {829 isl_ast_expr *SubExpr;830 Value *V;831 832 SubExpr = isl_ast_expr_get_op_arg(Expr, i + 1);833 V = ExprBuilder.create(SubExpr);834 ScalarEvolution *SE = Stmt->getParent()->getSE();835 LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V);836 }837 838 isl_ast_expr_free(Expr);839}840 841void IslNodeBuilder::createSubstitutionsVector(842 __isl_take isl_ast_expr *Expr, ScopStmt *Stmt,843 std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,844 __isl_take isl_id *IteratorID) {845 int i = 0;846 847 Value *OldValue = IDToValue[IteratorID];848 for (Value *IV : IVS) {849 IDToValue[IteratorID] = IV;850 createSubstitutions(isl_ast_expr_copy(Expr), Stmt, VLTS[i]);851 i++;852 }853 854 IDToValue[IteratorID] = OldValue;855 isl_id_free(IteratorID);856 isl_ast_expr_free(Expr);857}858 859void IslNodeBuilder::generateCopyStmt(860 ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {861 assert(Stmt->size() == 2);862 auto ReadAccess = Stmt->begin();863 auto WriteAccess = ReadAccess++;864 assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite());865 assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&866 "Accesses use the same data type");867 assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind());868 auto *AccessExpr =869 isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId().release());870 auto *LoadValue = ExprBuilder.create(AccessExpr);871 AccessExpr =872 isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release());873 auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr).first;874 Builder.CreateStore(LoadValue, StoreAddr);875}876 877Value *IslNodeBuilder::materializeNonScopLoopInductionVariable(const Loop *L) {878 assert(!OutsideLoopIterations.contains(L) &&879 "trying to materialize loop induction variable twice");880 const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),881 SE.getUnknown(Builder.getInt64(1)), L,882 SCEV::FlagAnyWrap);883 Value *V = generateSCEV(OuterLIV);884 OutsideLoopIterations[L] = SE.getUnknown(V);885 return V;886}887 888void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {889 LoopToScevMapT LTS;890 isl_id *Id;891 ScopStmt *Stmt;892 893 isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);894 isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);895 Id = isl_ast_expr_get_id(StmtExpr);896 isl_ast_expr_free(StmtExpr);897 898 LTS.insert_range(OutsideLoopIterations);899 900 Stmt = (ScopStmt *)isl_id_get_user(Id);901 auto *NewAccesses = createNewAccesses(Stmt, User);902 if (Stmt->isCopyStmt()) {903 generateCopyStmt(Stmt, NewAccesses);904 isl_ast_expr_free(Expr);905 } else {906 createSubstitutions(Expr, Stmt, LTS);907 908 if (Stmt->isBlockStmt())909 BlockGen.copyStmt(*Stmt, LTS, NewAccesses);910 else911 RegionGen.copyStmt(*Stmt, LTS, NewAccesses);912 }913 914 isl_id_to_ast_expr_free(NewAccesses);915 isl_ast_node_free(User);916 isl_id_free(Id);917}918 919void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) {920 isl_ast_node_list *List = isl_ast_node_block_get_children(Block);921 922 for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)923 create(isl_ast_node_list_get_ast_node(List, i));924 925 isl_ast_node_free(Block);926 isl_ast_node_list_free(List);927}928 929void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {930 switch (isl_ast_node_get_type(Node)) {931 case isl_ast_node_error:932 llvm_unreachable("code generation error");933 case isl_ast_node_mark:934 createMark(Node);935 return;936 case isl_ast_node_for:937 createFor(Node);938 return;939 case isl_ast_node_if:940 createIf(Node);941 return;942 case isl_ast_node_user:943 createUser(Node);944 return;945 case isl_ast_node_block:946 createBlock(Node);947 return;948 }949 950 llvm_unreachable("Unknown isl_ast_node type");951}952 953bool IslNodeBuilder::materializeValue(__isl_take isl_id *Id) {954 // If the Id is already mapped, skip it.955 if (!IDToValue.count(Id)) {956 auto *ParamSCEV = (const SCEV *)isl_id_get_user(Id);957 Value *V = nullptr;958 959 // Parameters could refer to invariant loads that need to be960 // preloaded before we can generate code for the parameter. Thus,961 // check if any value referred to in ParamSCEV is an invariant load962 // and if so make sure its equivalence class is preloaded.963 SetVector<Value *> Values;964 findValues(ParamSCEV, SE, Values);965 for (auto *Val : Values) {966 // Check if the value is an instruction in a dead block within the SCoP967 // and if so do not code generate it.968 if (auto *Inst = dyn_cast<Instruction>(Val)) {969 if (S.contains(Inst)) {970 bool IsDead = true;971 972 // Check for "undef" loads first, then if there is a statement for973 // the parent of Inst and lastly if the parent of Inst has an empty974 // domain. In the first and last case the instruction is dead but if975 // there is a statement or the domain is not empty Inst is not dead.976 auto MemInst = MemAccInst::dyn_cast(Inst);977 auto Address = MemInst ? MemInst.getPointerOperand() : nullptr;978 if (Address && SE.getUnknown(UndefValue::get(Address->getType())) ==979 SE.getPointerBase(SE.getSCEV(Address))) {980 } else if (S.getStmtFor(Inst)) {981 IsDead = false;982 } else {983 auto *Domain = S.getDomainConditions(Inst->getParent()).release();984 IsDead = isl_set_is_empty(Domain);985 isl_set_free(Domain);986 }987 988 if (IsDead) {989 V = UndefValue::get(ParamSCEV->getType());990 break;991 }992 }993 }994 995 if (auto *IAClass = S.lookupInvariantEquivClass(Val)) {996 // Check if this invariant access class is empty, hence if we never997 // actually added a loads instruction to it. In that case it has no998 // (meaningful) users and we should not try to code generate it.999 if (IAClass->InvariantAccesses.empty())1000 V = UndefValue::get(ParamSCEV->getType());1001 1002 if (!preloadInvariantEquivClass(*IAClass)) {1003 isl_id_free(Id);1004 return false;1005 }1006 }1007 }1008 1009 V = V ? V : generateSCEV(ParamSCEV);1010 IDToValue[Id] = V;1011 }1012 1013 isl_id_free(Id);1014 return true;1015}1016 1017bool IslNodeBuilder::materializeParameters(__isl_take isl_set *Set) {1018 for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) {1019 if (!isl_set_involves_dims(Set, isl_dim_param, i, 1))1020 continue;1021 isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i);1022 if (!materializeValue(Id))1023 return false;1024 }1025 return true;1026}1027 1028bool IslNodeBuilder::materializeParameters() {1029 for (const SCEV *Param : S.parameters()) {1030 isl_id *Id = S.getIdForParam(Param).release();1031 if (!materializeValue(Id))1032 return false;1033 }1034 return true;1035}1036 1037Value *IslNodeBuilder::preloadUnconditionally(__isl_take isl_set *AccessRange,1038 isl_ast_build *Build,1039 Instruction *AccInst) {1040 isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);1041 isl_ast_expr *Access =1042 isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);1043 auto *Address = isl_ast_expr_address_of(Access);1044 auto *AddressValue = ExprBuilder.create(Address);1045 Value *PreloadVal;1046 1047 // Correct the type as the SAI might have a different type than the user1048 // expects, especially if the base pointer is a struct.1049 Type *Ty = AccInst->getType();1050 1051 auto *Ptr = AddressValue;1052 auto Name = Ptr->getName();1053 PreloadVal = Builder.CreateLoad(Ty, Ptr, Name + ".load");1054 if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal))1055 PreloadInst->setAlignment(cast<LoadInst>(AccInst)->getAlign());1056 1057 // TODO: This is only a hot fix for SCoP sequences that use the same load1058 // instruction contained and hoisted by one of the SCoPs.1059 if (SE.isSCEVable(Ty))1060 SE.forgetValue(AccInst);1061 1062 return PreloadVal;1063}1064 1065Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,1066 __isl_take isl_set *Domain) {1067 isl_set *AccessRange = isl_map_range(MA.getAddressFunction().release());1068 AccessRange = isl_set_gist_params(AccessRange, S.getContext().release());1069 1070 if (!materializeParameters(AccessRange)) {1071 isl_set_free(AccessRange);1072 isl_set_free(Domain);1073 return nullptr;1074 }1075 1076 auto *Build =1077 isl_ast_build_from_context(isl_set_universe(S.getParamSpace().release()));1078 isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));1079 bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);1080 isl_set_free(Universe);1081 1082 Instruction *AccInst = MA.getAccessInstruction();1083 Type *AccInstTy = AccInst->getType();1084 1085 Value *PreloadVal = nullptr;1086 if (AlwaysExecuted) {1087 PreloadVal = preloadUnconditionally(AccessRange, Build, AccInst);1088 isl_ast_build_free(Build);1089 isl_set_free(Domain);1090 return PreloadVal;1091 }1092 1093 if (!materializeParameters(Domain)) {1094 isl_ast_build_free(Build);1095 isl_set_free(AccessRange);1096 isl_set_free(Domain);1097 return nullptr;1098 }1099 1100 isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);1101 Domain = nullptr;1102 1103 ExprBuilder.setTrackOverflow(true);1104 Value *Cond = ExprBuilder.createBool(DomainCond);1105 Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(),1106 "polly.preload.cond.overflown");1107 Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result");1108 ExprBuilder.setTrackOverflow(false);1109 1110 if (!Cond->getType()->isIntegerTy(1))1111 Cond = Builder.CreateIsNotNull(Cond);1112 1113 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),1114 Builder.GetInsertPoint(), GenDT, GenLI);1115 CondBB->setName("polly.preload.cond");1116 1117 BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), GenDT, GenLI);1118 MergeBB->setName("polly.preload.merge");1119 1120 Function *F = Builder.GetInsertBlock()->getParent();1121 LLVMContext &Context = F->getContext();1122 BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);1123 1124 GenDT->addNewBlock(ExecBB, CondBB);1125 if (Loop *L = GenLI->getLoopFor(CondBB))1126 L->addBasicBlockToLoop(ExecBB, *GenLI);1127 1128 auto *CondBBTerminator = CondBB->getTerminator();1129 Builder.SetInsertPoint(CondBB, CondBBTerminator->getIterator());1130 Builder.CreateCondBr(Cond, ExecBB, MergeBB);1131 CondBBTerminator->eraseFromParent();1132 1133 Builder.SetInsertPoint(ExecBB);1134 Builder.CreateBr(MergeBB);1135 1136 Builder.SetInsertPoint(ExecBB, ExecBB->getTerminator()->getIterator());1137 Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);1138 Builder.SetInsertPoint(MergeBB, MergeBB->getTerminator()->getIterator());1139 auto *MergePHI = Builder.CreatePHI(1140 AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");1141 PreloadVal = MergePHI;1142 1143 if (!PreAccInst) {1144 PreloadVal = nullptr;1145 PreAccInst = UndefValue::get(AccInstTy);1146 }1147 1148 MergePHI->addIncoming(PreAccInst, ExecBB);1149 MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);1150 1151 isl_ast_build_free(Build);1152 return PreloadVal;1153}1154 1155bool IslNodeBuilder::preloadInvariantEquivClass(1156 InvariantEquivClassTy &IAClass) {1157 // For an equivalence class of invariant loads we pre-load the representing1158 // element with the unified execution context. However, we have to map all1159 // elements of the class to the one preloaded load as they are referenced1160 // during the code generation and therefore need to be mapped.1161 const MemoryAccessList &MAs = IAClass.InvariantAccesses;1162 if (MAs.empty())1163 return true;1164 1165 MemoryAccess *MA = MAs.front();1166 assert(MA->isArrayKind() && MA->isRead());1167 1168 // If the access function was already mapped, the preload of this equivalence1169 // class was triggered earlier already and doesn't need to be done again.1170 if (ValueMap.count(MA->getAccessInstruction()))1171 return true;1172 1173 // Check for recursion which can be caused by additional constraints, e.g.,1174 // non-finite loop constraints. In such a case we have to bail out and insert1175 // a "false" runtime check that will cause the original code to be executed.1176 auto PtrId = std::make_pair(IAClass.IdentifyingPointer, IAClass.AccessType);1177 if (!PreloadedPtrs.insert(PtrId).second)1178 return false;1179 1180 // The execution context of the IAClass.1181 isl::set &ExecutionCtx = IAClass.ExecutionContext;1182 1183 // If the base pointer of this class is dependent on another one we have to1184 // make sure it was preloaded already.1185 auto *SAI = MA->getScopArrayInfo();1186 if (auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr())) {1187 if (!preloadInvariantEquivClass(*BaseIAClass))1188 return false;1189 1190 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and1191 // we need to refine the ExecutionCtx.1192 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;1193 ExecutionCtx = ExecutionCtx.intersect(BaseExecutionCtx);1194 }1195 1196 // If the size of a dimension is dependent on another class, make sure it is1197 // preloaded.1198 for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {1199 const SCEV *Dim = SAI->getDimensionSize(i);1200 SetVector<Value *> Values;1201 findValues(Dim, SE, Values);1202 for (auto *Val : Values) {1203 if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {1204 if (!preloadInvariantEquivClass(*BaseIAClass))1205 return false;1206 1207 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx1208 // and we need to refine the ExecutionCtx.1209 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;1210 ExecutionCtx = ExecutionCtx.intersect(BaseExecutionCtx);1211 }1212 }1213 }1214 1215 Instruction *AccInst = MA->getAccessInstruction();1216 Type *AccInstTy = AccInst->getType();1217 1218 Value *PreloadVal = preloadInvariantLoad(*MA, ExecutionCtx.copy());1219 if (!PreloadVal)1220 return false;1221 1222 for (const MemoryAccess *MA : MAs) {1223 Instruction *MAAccInst = MA->getAccessInstruction();1224 assert(PreloadVal->getType() == MAAccInst->getType());1225 ValueMap[MAAccInst] = PreloadVal;1226 }1227 1228 if (SE.isSCEVable(AccInstTy)) {1229 isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst)).release();1230 if (ParamId)1231 IDToValue[ParamId] = PreloadVal;1232 isl_id_free(ParamId);1233 }1234 1235 BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();1236 auto *Alloca = new AllocaInst(AccInstTy, DL.getAllocaAddrSpace(),1237 AccInst->getName() + ".preload.s2a",1238 EntryBB->getFirstInsertionPt());1239 Builder.CreateStore(PreloadVal, Alloca);1240 ValueMapT PreloadedPointer;1241 PreloadedPointer[PreloadVal] = AccInst;1242 Annotator.addAlternativeAliasBases(PreloadedPointer);1243 1244 for (auto *DerivedSAI : SAI->getDerivedSAIs()) {1245 Value *BasePtr = DerivedSAI->getBasePtr();1246 1247 for (const MemoryAccess *MA : MAs) {1248 // As the derived SAI information is quite coarse, any load from the1249 // current SAI could be the base pointer of the derived SAI, however we1250 // should only change the base pointer of the derived SAI if we actually1251 // preloaded it.1252 if (BasePtr == MA->getOriginalBaseAddr()) {1253 assert(BasePtr->getType() == PreloadVal->getType());1254 DerivedSAI->setBasePtr(PreloadVal);1255 }1256 1257 // For scalar derived SAIs we remap the alloca used for the derived value.1258 if (BasePtr == MA->getAccessInstruction())1259 ScalarMap[DerivedSAI] = Alloca;1260 }1261 }1262 1263 for (const MemoryAccess *MA : MAs) {1264 Instruction *MAAccInst = MA->getAccessInstruction();1265 // Use the escape system to get the correct value to users outside the SCoP.1266 BlockGenerator::EscapeUserVectorTy EscapeUsers;1267 for (auto *U : MAAccInst->users())1268 if (Instruction *UI = dyn_cast<Instruction>(U))1269 if (!S.contains(UI))1270 EscapeUsers.push_back(UI);1271 1272 if (EscapeUsers.empty())1273 continue;1274 1275 EscapeMap[MA->getAccessInstruction()] =1276 std::make_pair(Alloca, std::move(EscapeUsers));1277 }1278 1279 return true;1280}1281 1282void IslNodeBuilder::allocateNewArrays(BBPair StartExitBlocks) {1283 for (auto &SAI : S.arrays()) {1284 if (SAI->getBasePtr())1285 continue;1286 1287 assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&1288 "The size of the outermost dimension is used to declare newly "1289 "created arrays that require memory allocation.");1290 1291 Type *NewArrayType = nullptr;1292 1293 // Get the size of the array = size(dim_1)*...*size(dim_n)1294 uint64_t ArraySizeInt = 1;1295 for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {1296 auto *DimSize = SAI->getDimensionSize(i);1297 unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize)1298 ->getAPInt()1299 .getLimitedValue();1300 1301 if (!NewArrayType)1302 NewArrayType = SAI->getElementType();1303 1304 NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);1305 ArraySizeInt *= UnsignedDimSize;1306 }1307 1308 if (SAI->isOnHeap()) {1309 LLVMContext &Ctx = NewArrayType->getContext();1310 1311 // Get the IntPtrTy from the Datalayout1312 auto IntPtrTy = DL.getIntPtrType(Ctx);1313 1314 // Get the size of the element type in bits1315 unsigned Size = SAI->getElemSizeInBytes();1316 1317 // Insert the malloc call at polly.start1318 BasicBlock *StartBlock = std::get<0>(StartExitBlocks);1319 Builder.SetInsertPoint(StartBlock,1320 StartBlock->getTerminator()->getIterator());1321 auto *CreatedArray = Builder.CreateMalloc(1322 IntPtrTy, SAI->getElementType(),1323 ConstantInt::get(Type::getInt64Ty(Ctx), Size),1324 ConstantInt::get(Type::getInt64Ty(Ctx), ArraySizeInt), nullptr,1325 SAI->getName());1326 1327 SAI->setBasePtr(CreatedArray);1328 1329 // Insert the free call at polly.exiting1330 BasicBlock *ExitingBlock = std::get<1>(StartExitBlocks);1331 Builder.SetInsertPoint(ExitingBlock,1332 ExitingBlock->getTerminator()->getIterator());1333 Builder.CreateFree(CreatedArray);1334 } else {1335 auto InstIt = Builder.GetInsertBlock()1336 ->getParent()1337 ->getEntryBlock()1338 .getTerminator()1339 ->getIterator();1340 1341 auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(),1342 SAI->getName(), InstIt);1343 if (PollyTargetFirstLevelCacheLineSize)1344 CreatedArray->setAlignment(Align(PollyTargetFirstLevelCacheLineSize));1345 SAI->setBasePtr(CreatedArray);1346 }1347 }1348}1349 1350bool IslNodeBuilder::preloadInvariantLoads() {1351 auto &InvariantEquivClasses = S.getInvariantAccesses();1352 if (InvariantEquivClasses.empty())1353 return true;1354 1355 BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),1356 Builder.GetInsertPoint(), GenDT, GenLI);1357 PreLoadBB->setName("polly.preload.begin");1358 Builder.SetInsertPoint(PreLoadBB, PreLoadBB->begin());1359 1360 for (auto &IAClass : InvariantEquivClasses)1361 if (!preloadInvariantEquivClass(IAClass))1362 return false;1363 1364 return true;1365}1366 1367void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {1368 // Materialize values for the parameters of the SCoP.1369 materializeParameters();1370 1371 // Generate values for the current loop iteration for all surrounding loops.1372 //1373 // We may also reference loops outside of the scop which do not contain the1374 // scop itself, but as the number of such scops may be arbitrarily large we do1375 // not generate code for them here, but only at the point of code generation1376 // where these values are needed.1377 Loop *L = LI.getLoopFor(S.getEntry());1378 1379 while (L != nullptr && S.contains(L))1380 L = L->getParentLoop();1381 1382 while (L != nullptr) {1383 materializeNonScopLoopInductionVariable(L);1384 L = L->getParentLoop();1385 }1386 1387 isl_set_free(Context);1388}1389 1390Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {1391 /// We pass the insert location of our Builder, as Polly ensures during IR1392 /// generation that there is always a valid CFG into which instructions are1393 /// inserted. As a result, the insertpoint is known to be always followed by a1394 /// terminator instruction. This means the insert point may be specified by a1395 /// terminator instruction, but it can never point to an ->end() iterator1396 /// which does not have a corresponding instruction. Hence, dereferencing1397 /// the insertpoint to obtain an instruction is known to be save.1398 ///1399 /// We also do not need to update the Builder here, as new instructions are1400 /// always inserted _before_ the given InsertLocation. As a result, the1401 /// insert location remains valid.1402 assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() &&1403 "Insert location points after last valid instruction");1404 BasicBlock::iterator InsertLocation = Builder.GetInsertPoint();1405 1406 return expandCodeFor(S, SE, Builder.GetInsertBlock()->getParent(), *GenSE, DL,1407 "polly", Expr, Expr->getType(), InsertLocation,1408 &ValueMap, /*LoopToScevMap*/ nullptr,1409 StartBlock->getSinglePredecessor());1410}1411 1412/// The AST expression we generate to perform the run-time check assumes1413/// computations on integer types of infinite size. As we only use 64-bit1414/// arithmetic we check for overflows, in case of which we set the result1415/// of this run-time check to false to be conservatively correct,1416Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {1417 auto ExprBuilder = getExprBuilder();1418 1419 // In case the AST expression has integers larger than 64 bit, bail out. The1420 // resulting LLVM-IR will contain operations on types that use more than 641421 // bits. These are -- in case wrapping intrinsics are used -- translated to1422 // runtime library calls that are not available on all systems (e.g., Android)1423 // and consequently will result in linker errors.1424 if (ExprBuilder.hasLargeInts(isl::manage_copy(Condition))) {1425 isl_ast_expr_free(Condition);1426 return Builder.getFalse();1427 }1428 1429 ExprBuilder.setTrackOverflow(true);1430 Value *RTC = ExprBuilder.create(Condition);1431 if (!RTC->getType()->isIntegerTy(1))1432 RTC = Builder.CreateIsNotNull(RTC);1433 Value *OverflowHappened =1434 Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");1435 1436 if (PollyGenerateRTCPrint) {1437 auto *F = Builder.GetInsertBlock()->getParent();1438 RuntimeDebugBuilder::createCPUPrinter(1439 Builder,1440 "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +1441 "RTC: ",1442 RTC, " Overflow: ", OverflowHappened,1443 "\n"1444 " (0 failed, -1 succeeded)\n"1445 " (if one or both are 0 falling back to original code, if both are -1 "1446 "executing Polly code)\n");1447 }1448 1449 RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");1450 ExprBuilder.setTrackOverflow(false);1451 1452 if (!isa<ConstantInt>(RTC))1453 VersionedScops++;1454 1455 return RTC;1456}1457