Lines Matching +full:polly +full:- +full:build
1 //===- IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST -------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 // a LLVM-IR AST.
12 //===----------------------------------------------------------------------===//
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"
61 #include "isl/isl-noexceptions.h"
76 using namespace polly;
78 #define DEBUG_TYPE "polly-codegen"
82 STATISTIC(SequentialLoops, "Number of generated sequential for-loops");
83 STATISTIC(ParallelLoops, "Number of generated parallel for-loops");
84 STATISTIC(IfConditions, "Number of generated if-conditions");
90 "polly-codegen-emit-rtc-print",
99 "polly-codegen-generate-expressions",
104 "polly-target-first-level-cache-line-size",
109 "polly-omp-backend", cl::desc("Choose the OpenMP library to use:"),
166 return -1;
171 return -1;
176 return -1;
179 return -1;
183 return -1;
187 return -1;
201 // When accelerator-offloading, GlobalValue is a host address whose content
227 for (Use &U : Inst->operands())
234 LoopInfo *LI = Stmt->getParent()->getLI();
236 BasicBlock *BB = Stmt->getBasicBlock();
237 Loop *Scope = LI->getLoopFor(BB);
238 for (Instruction *Inst : Stmt->getInstructions())
241 if (Stmt->isRegionStmt()) {
242 for (BasicBlock *BB : Stmt->getRegion()->blocks()) {
243 Loop *Scope = LI->getLoopFor(BB);
250 void polly::addReferencesFromStmt(ScopStmt *Stmt, void *UserPtr,
259 isl::space ParamSpace = Access->getLatestAccessRelation().get_space();
261 References.ParamSpace->align_params(ParamSpace);
264 if (Access->isLatestArrayKind()) {
265 auto *BasePtr = Access->getLatestScopArrayInfo()->getBasePtr();
267 if (Stmt->getParent()->contains(OpInst))
279 /// Extract the out-of-scop values and SCEVs referenced from a set describing
285 /// these locations in the set of out-of-scop values as well.
296 /// Extract the out-of-scop values and SCEVs referenced from a union set
302 /// these locations in the set of out-of-scop values as well.
333 Values.insert(cast<SCEVUnknown>(I.second)->getValue());
354 /// we choose to codegen these on-demand.
357 return S.contains(L) || L->contains(S.getEntry());
365 // 2. test/Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
377 return It->second;
399 // can happen e.g. if the AST build peeled or unrolled the loop.
466 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
467 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
468 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
470 if (MaxType != ValueLB->getType())
472 if (MaxType != ValueUB->getType())
474 if (MaxType != ValueInc->getType())
479 bool UseGuardBB = !GenSE->isKnownPredicate(Predicate, GenSE->getSCEV(ValueLB),
480 GenSE->getSCEV(ValueUB));
492 Builder.SetInsertPoint(&ExitBlock->front());
511 ParBB->setName("polly.parallel.for");
512 Builder.SetInsertPoint(&ParBB->front());
530 ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));
533 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
534 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
535 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
537 if (MaxType != ValueLB->getType())
539 if (MaxType != ValueUB->getType())
541 if (MaxType != ValueInc->getType())
573 IV = ParallelLoopGenPtr->createParallelLoop(
578 Function *SubFn = LoopBody->getFunction();
582 // not an inter-procedural passes, we temporarily switch them out. Save the
584 Function *CallerFn = Builder.GetInsertBlock()->getParent();
593 DominatorTree *SubDT = ParallelLoopGenPtr->getCalleeDominatorTree();
594 LoopInfo *SubLI = ParallelLoopGenPtr->getCalleeLoopInfo();
598 // AssumptionAnalysis instead of our own. They contain more target-specific
604 Triple(SubFn->getParent()->getTargetTriple()));
625 // Clean-up any value that getReferencesInSubtree thinks we do not need.
632 // This is for NewVals that do not appear in ValueMap (such as SCoP-invariant
639 assert(NewValInst->getFunction() == &S.getFunction());
656 assert(SubInst->getFunction() == SubFn &&
662 assert(SubInst->getFunction() == SubFn &&
712 Function *F = Builder.GetInsertBlock()->getParent();
713 LLVMContext &Context = F->getContext();
717 CondBB->setName("polly.cond");
718 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), GenDT, GenLI);
719 MergeBB->setName("polly.merge");
720 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
721 BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F);
723 GenDT->addNewBlock(ThenBB, CondBB);
724 GenDT->addNewBlock(ElseBB, CondBB);
725 GenDT->changeImmediateDominator(MergeBB, CondBB);
727 Loop *L = GenLI->getLoopFor(CondBB);
729 L->addBasicBlockToLoop(ThenBB, *GenLI);
730 L->addBasicBlockToLoop(ElseBB, *GenLI);
733 CondBB->getTerminator()->eraseFromParent();
742 Builder.SetInsertPoint(&ThenBB->front());
746 Builder.SetInsertPoint(&ElseBB->front());
751 Builder.SetInsertPoint(&MergeBB->front());
762 isl::id_to_ast_expr::alloc(Stmt->getParent()->getIslCtx(), 0);
764 isl::ast_build Build = IslAstInfo::getBuild(isl::manage_copy(Node));
765 assert(!Build.is_null() && "Could not obtain isl_ast_build from user node");
766 Stmt->setAstBuild(Build);
769 if (!MA->hasNewAccessRelation()) {
771 if (!MA->isAffine())
773 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())
777 dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());
778 if (BasePtr && Stmt->getParent()->getRegion().contains(BasePtr))
784 assert(MA->isAffine() &&
787 isl::union_map Schedule = Build.get_schedule();
790 if (MA->isRead()) {
791 auto Dom = Stmt->getDomain().release();
793 auto AccDom = isl_map_domain(MA->getAccessRelation().release());
795 Stmt->getParent()->getContext().release());
797 SchedDom, Stmt->getParent()->getContext().release());
808 isl::pw_multi_aff PWAccRel = MA->applyScheduleToAccessRelation(Schedule);
810 // isl cannot generate an index expression for access-nothing accesses.
817 isl::ast_expr AccessExpr = Build.access_from(PWAccRel);
818 NewAccesses = NewAccesses.set(MA->getId(), AccessExpr);
830 for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr) - 1; ++i) {
836 ScalarEvolution *SE = Stmt->getParent()->getSE();
837 LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V);
863 assert(Stmt->size() == 2);
864 auto ReadAccess = Stmt->begin();
866 assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite());
867 assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&
869 assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind());
871 isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId().release());
874 isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release());
904 if (Stmt->isCopyStmt()) {
910 if (Stmt->isBlockStmt())
980 if (Address && SE.getUnknown(UndefValue::get(Address->getType())) ==
985 auto *Domain = S.getDomainConditions(Inst->getParent()).release();
991 V = UndefValue::get(ParamSCEV->getType());
1001 if (IAClass->InvariantAccesses.empty())
1002 V = UndefValue::get(ParamSCEV->getType());
1040 isl_ast_build *Build,
1044 isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
1051 Type *Ty = AccInst->getType();
1054 auto Name = Ptr->getName();
1057 PreloadInst->setAlignment(cast<LoadInst>(AccInst)->getAlign());
1078 auto *Build =
1085 Type *AccInstTy = AccInst->getType();
1089 PreloadVal = preloadUnconditionally(AccessRange, Build, AccInst);
1090 isl_ast_build_free(Build);
1096 isl_ast_build_free(Build);
1102 isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
1108 "polly.preload.cond.overflown");
1109 Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result");
1112 if (!Cond->getType()->isIntegerTy(1))
1117 CondBB->setName("polly.preload.cond");
1119 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), GenDT, GenLI);
1120 MergeBB->setName("polly.preload.merge");
1122 Function *F = Builder.GetInsertBlock()->getParent();
1123 LLVMContext &Context = F->getContext();
1124 BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);
1126 GenDT->addNewBlock(ExecBB, CondBB);
1127 if (Loop *L = GenLI->getLoopFor(CondBB))
1128 L->addBasicBlockToLoop(ExecBB, *GenLI);
1130 auto *CondBBTerminator = CondBB->getTerminator();
1133 CondBBTerminator->eraseFromParent();
1138 Builder.SetInsertPoint(ExecBB->getTerminator());
1139 Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);
1140 Builder.SetInsertPoint(MergeBB->getTerminator());
1142 AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
1150 MergePHI->addIncoming(PreAccInst, ExecBB);
1151 MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
1153 isl_ast_build_free(Build);
1159 // For an equivalence class of invariant loads we pre-load the representing
1168 assert(MA->isArrayKind() && MA->isRead());
1172 if (ValueMap.count(MA->getAccessInstruction()))
1176 // non-finite loop constraints. In such a case we have to bail out and insert
1187 auto *SAI = MA->getScopArrayInfo();
1188 if (auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr())) {
1194 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1200 for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
1201 const SCEV *Dim = SAI->getDimensionSize(i);
1211 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1217 Instruction *AccInst = MA->getAccessInstruction();
1218 Type *AccInstTy = AccInst->getType();
1225 Instruction *MAAccInst = MA->getAccessInstruction();
1226 assert(PreloadVal->getType() == MAAccInst->getType());
1237 BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
1239 AccInst->getName() + ".preload.s2a",
1240 EntryBB->getFirstInsertionPt());
1246 for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
1247 Value *BasePtr = DerivedSAI->getBasePtr();
1254 if (BasePtr == MA->getOriginalBaseAddr()) {
1255 assert(BasePtr->getType() == PreloadVal->getType());
1256 DerivedSAI->setBasePtr(PreloadVal);
1260 if (BasePtr == MA->getAccessInstruction())
1266 Instruction *MAAccInst = MA->getAccessInstruction();
1269 for (auto *U : MAAccInst->users())
1277 EscapeMap[MA->getAccessInstruction()] =
1286 if (SAI->getBasePtr())
1289 assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&
1297 for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {
1298 auto *DimSize = SAI->getDimensionSize(i);
1300 ->getAPInt()
1304 NewArrayType = SAI->getElementType();
1310 if (SAI->isOnHeap()) {
1311 LLVMContext &Ctx = NewArrayType->getContext();
1317 unsigned Size = SAI->getElemSizeInBytes();
1319 // Insert the malloc call at polly.start
1320 Builder.SetInsertPoint(std::get<0>(StartExitBlocks)->getTerminator());
1322 IntPtrTy, SAI->getElementType(),
1325 SAI->getName());
1327 SAI->setBasePtr(CreatedArray);
1329 // Insert the free call at polly.exiting
1330 Builder.SetInsertPoint(std::get<1>(StartExitBlocks)->getTerminator());
1334 ->getParent()
1335 ->getEntryBlock()
1337 ->getIterator();
1340 SAI->getName(), InstIt);
1342 CreatedArray->setAlignment(Align(PollyTargetFirstLevelCacheLineSize));
1343 SAI->setBasePtr(CreatedArray);
1355 PreLoadBB->setName("polly.preload.begin");
1356 Builder.SetInsertPoint(&PreLoadBB->front());
1378 L = L->getParentLoop();
1382 L = L->getParentLoop();
1389 /// We pass the insert location of our Builder, as Polly ensures during IR
1393 /// terminator instruction, but it can never point to an ->end() iterator
1400 assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() &&
1404 return expandCodeFor(S, SE, Builder.GetInsertBlock()->getParent(), *GenSE, DL,
1405 "polly", Expr, Expr->getType(), InsertLocation,
1407 StartBlock->getSinglePredecessor());
1410 /// The AST expression we generate to perform the run-time check assumes
1411 /// computations on integer types of infinite size. As we only use 64-bit
1413 /// of this run-time check to false to be conservatively correct,
1418 // resulting LLVM-IR will contain operations on types that use more than 64
1419 // bits. These are -- in case wrapping intrinsics are used -- translated to
1429 if (!RTC->getType()->isIntegerTy(1))
1432 Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
1435 auto *F = Builder.GetInsertBlock()->getParent();
1438 "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
1442 " (0 failed, -1 succeeded)\n"
1443 " (if one or both are 0 falling back to original code, if both are -1 "
1444 "executing Polly code)\n");
1447 RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");