1 //===- ScopHelper.cpp - Some Helper Functions for Scop. ------------------===//
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Small functions that help with Scop and LLVM-IR.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "polly/Support/ScopHelper.h"
14 #include "polly/Options.h"
15 #include "polly/ScopInfo.h"
16 #include "polly/Support/SCEVValidator.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/RegionInfo.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 #include "llvm/Transforms/Utils/LoopUtils.h"
23 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
24
25 using namespace llvm;
26 using namespace polly;
27
28 #define DEBUG_TYPE "polly-scop-helper"
29
30 static cl::opt<bool> PollyAllowErrorBlocks(
31 "polly-allow-error-blocks",
32 cl::desc("Allow to speculate on the execution of 'error blocks'."),
33 cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
34
35 static cl::list<std::string> DebugFunctions(
36 "polly-debug-func",
37 cl::desc("Allow calls to the specified functions in SCoPs even if their "
38 "side-effects are unknown. This can be used to do debug output in "
39 "Polly-transformed code."),
40 cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
41
42 // Ensures that there is just one predecessor to the entry node from outside the
43 // region.
44 // The identity of the region entry node is preserved.
simplifyRegionEntry(Region * R,DominatorTree * DT,LoopInfo * LI,RegionInfo * RI)45 static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
46 RegionInfo *RI) {
47 BasicBlock *EnteringBB = R->getEnteringBlock();
48 BasicBlock *Entry = R->getEntry();
49
50 // Before (one of):
51 //
52 // \ / //
53 // EnteringBB //
54 // | \------> //
55 // \ / | //
56 // Entry <--\ Entry <--\ //
57 // / \ / / \ / //
58 // .... .... //
59
60 // Create single entry edge if the region has multiple entry edges.
61 if (!EnteringBB) {
62 SmallVector<BasicBlock *, 4> Preds;
63 for (BasicBlock *P : predecessors(Entry))
64 if (!R->contains(P))
65 Preds.push_back(P);
66
67 BasicBlock *NewEntering =
68 SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
69
70 if (RI) {
71 // The exit block of predecessing regions must be changed to NewEntering
72 for (BasicBlock *ExitPred : predecessors(NewEntering)) {
73 Region *RegionOfPred = RI->getRegionFor(ExitPred);
74 if (RegionOfPred->getExit() != Entry)
75 continue;
76
77 while (!RegionOfPred->isTopLevelRegion() &&
78 RegionOfPred->getExit() == Entry) {
79 RegionOfPred->replaceExit(NewEntering);
80 RegionOfPred = RegionOfPred->getParent();
81 }
82 }
83
84 // Make all ancestors use EnteringBB as entry; there might be edges to it
85 Region *AncestorR = R->getParent();
86 RI->setRegionFor(NewEntering, AncestorR);
87 while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) {
88 AncestorR->replaceEntry(NewEntering);
89 AncestorR = AncestorR->getParent();
90 }
91 }
92
93 EnteringBB = NewEntering;
94 }
95 assert(R->getEnteringBlock() == EnteringBB);
96
97 // After:
98 //
99 // \ / //
100 // EnteringBB //
101 // | //
102 // | //
103 // Entry <--\ //
104 // / \ / //
105 // .... //
106 }
107
108 // Ensure that the region has a single block that branches to the exit node.
simplifyRegionExit(Region * R,DominatorTree * DT,LoopInfo * LI,RegionInfo * RI)109 static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
110 RegionInfo *RI) {
111 BasicBlock *ExitBB = R->getExit();
112 BasicBlock *ExitingBB = R->getExitingBlock();
113
114 // Before:
115 //
116 // (Region) ______/ //
117 // \ | / //
118 // ExitBB //
119 // / \ //
120
121 if (!ExitingBB) {
122 SmallVector<BasicBlock *, 4> Preds;
123 for (BasicBlock *P : predecessors(ExitBB))
124 if (R->contains(P))
125 Preds.push_back(P);
126
127 // Preds[0] Preds[1] otherBB //
128 // \ | ________/ //
129 // \ | / //
130 // BB //
131 ExitingBB =
132 SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
133 // Preds[0] Preds[1] otherBB //
134 // \ / / //
135 // BB.region_exiting / //
136 // \ / //
137 // BB //
138
139 if (RI)
140 RI->setRegionFor(ExitingBB, R);
141
142 // Change the exit of nested regions, but not the region itself,
143 R->replaceExitRecursive(ExitingBB);
144 R->replaceExit(ExitBB);
145 }
146 assert(ExitingBB == R->getExitingBlock());
147
148 // After:
149 //
150 // \ / //
151 // ExitingBB _____/ //
152 // \ / //
153 // ExitBB //
154 // / \ //
155 }
156
simplifyRegion(Region * R,DominatorTree * DT,LoopInfo * LI,RegionInfo * RI)157 void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
158 RegionInfo *RI) {
159 assert(R && !R->isTopLevelRegion());
160 assert(!RI || RI == R->getRegionInfo());
161 assert((!RI || DT) &&
162 "RegionInfo requires DominatorTree to be updated as well");
163
164 simplifyRegionEntry(R, DT, LI, RI);
165 simplifyRegionExit(R, DT, LI, RI);
166 assert(R->isSimple());
167 }
168
169 // Split the block into two successive blocks.
170 //
171 // Like llvm::SplitBlock, but also preserves RegionInfo
splitBlock(BasicBlock * Old,Instruction * SplitPt,DominatorTree * DT,llvm::LoopInfo * LI,RegionInfo * RI)172 static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
173 DominatorTree *DT, llvm::LoopInfo *LI,
174 RegionInfo *RI) {
175 assert(Old && SplitPt);
176
177 // Before:
178 //
179 // \ / //
180 // Old //
181 // / \ //
182
183 BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
184
185 if (RI) {
186 Region *R = RI->getRegionFor(Old);
187 RI->setRegionFor(NewBlock, R);
188 }
189
190 // After:
191 //
192 // \ / //
193 // Old //
194 // | //
195 // NewBlock //
196 // / \ //
197
198 return NewBlock;
199 }
200
splitEntryBlockForAlloca(BasicBlock * EntryBlock,DominatorTree * DT,LoopInfo * LI,RegionInfo * RI)201 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT,
202 LoopInfo *LI, RegionInfo *RI) {
203 // Find first non-alloca instruction. Every basic block has a non-alloca
204 // instruction, as every well formed basic block has a terminator.
205 BasicBlock::iterator I = EntryBlock->begin();
206 while (isa<AllocaInst>(I))
207 ++I;
208
209 // splitBlock updates DT, LI and RI.
210 splitBlock(EntryBlock, &*I, DT, LI, RI);
211 }
212
splitEntryBlockForAlloca(BasicBlock * EntryBlock,Pass * P)213 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
214 auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
215 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
216 auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
217 auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
218 RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
219 RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
220
221 // splitBlock updates DT, LI and RI.
222 polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI);
223 }
224
recordAssumption(polly::RecordedAssumptionsTy * RecordedAssumptions,polly::AssumptionKind Kind,isl::set Set,DebugLoc Loc,polly::AssumptionSign Sign,BasicBlock * BB,bool RTC)225 void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions,
226 polly::AssumptionKind Kind, isl::set Set,
227 DebugLoc Loc, polly::AssumptionSign Sign,
228 BasicBlock *BB, bool RTC) {
229 assert((Set.is_params() || BB) &&
230 "Assumptions without a basic block must be parameter sets");
231 if (RecordedAssumptions)
232 RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB, RTC});
233 }
234
235 /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
236 /// instruction but just use it, if it is referenced as a SCEVUnknown. We want
237 /// however to generate new code if the instruction is in the analyzed region
238 /// and we generate code outside/in front of that region. Hence, we generate the
239 /// code for the SDiv/SRem operands in front of the analyzed region and then
240 /// create a new SDiv/SRem operation there too.
241 struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
242 friend struct SCEVVisitor<ScopExpander, const SCEV *>;
243
ScopExpanderScopExpander244 explicit ScopExpander(const Region &R, ScalarEvolution &SE,
245 const DataLayout &DL, const char *Name, ValueMapT *VMap,
246 BasicBlock *RTCBB)
247 : Expander(SE, DL, Name, /*PreserveLCSSA=*/false), SE(SE), Name(Name),
248 R(R), VMap(VMap), RTCBB(RTCBB) {}
249
expandCodeForScopExpander250 Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
251 // If we generate code in the region we will immediately fall back to the
252 // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
253 // needed replace them by copies computed in the entering block.
254 if (!R.contains(I))
255 E = visit(E);
256 return Expander.expandCodeFor(E, Ty, I);
257 }
258
visitScopExpander259 const SCEV *visit(const SCEV *E) {
260 // Cache the expansion results for intermediate SCEV expressions. A SCEV
261 // expression can refer to an operand multiple times (e.g. "x*x), so
262 // a naive visitor takes exponential time.
263 if (SCEVCache.count(E))
264 return SCEVCache[E];
265 const SCEV *Result = SCEVVisitor::visit(E);
266 SCEVCache[E] = Result;
267 return Result;
268 }
269
270 private:
271 SCEVExpander Expander;
272 ScalarEvolution &SE;
273 const char *Name;
274 const Region &R;
275 ValueMapT *VMap;
276 BasicBlock *RTCBB;
277 DenseMap<const SCEV *, const SCEV *> SCEVCache;
278
visitGenericInstScopExpander279 const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
280 Instruction *IP) {
281 if (!Inst || !R.contains(Inst))
282 return E;
283
284 assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
285 !isa<PHINode>(Inst));
286
287 auto *InstClone = Inst->clone();
288 for (auto &Op : Inst->operands()) {
289 assert(SE.isSCEVable(Op->getType()));
290 auto *OpSCEV = SE.getSCEV(Op);
291 auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);
292 InstClone->replaceUsesOfWith(Op, OpClone);
293 }
294
295 InstClone->setName(Name + Inst->getName());
296 InstClone->insertBefore(IP);
297 return SE.getSCEV(InstClone);
298 }
299
visitUnknownScopExpander300 const SCEV *visitUnknown(const SCEVUnknown *E) {
301
302 // If a value mapping was given try if the underlying value is remapped.
303 Value *NewVal = VMap ? VMap->lookup(E->getValue()) : nullptr;
304 if (NewVal) {
305 auto *NewE = SE.getSCEV(NewVal);
306
307 // While the mapped value might be different the SCEV representation might
308 // not be. To this end we will check before we go into recursion here.
309 if (E != NewE)
310 return visit(NewE);
311 }
312
313 Instruction *Inst = dyn_cast<Instruction>(E->getValue());
314 Instruction *IP;
315 if (Inst && !R.contains(Inst))
316 IP = Inst;
317 else if (Inst && RTCBB->getParent() == Inst->getFunction())
318 IP = RTCBB->getTerminator();
319 else
320 IP = RTCBB->getParent()->getEntryBlock().getTerminator();
321
322 if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
323 Inst->getOpcode() != Instruction::SDiv))
324 return visitGenericInst(E, Inst, IP);
325
326 const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
327 const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
328
329 if (!SE.isKnownNonZero(RHSScev))
330 RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
331
332 Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);
333 Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);
334
335 Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
336 LHS, RHS, Inst->getName() + Name, IP);
337 return SE.getSCEV(Inst);
338 }
339
340 /// The following functions will just traverse the SCEV and rebuild it with
341 /// the new operands returned by the traversal.
342 ///
343 ///{
visitConstantScopExpander344 const SCEV *visitConstant(const SCEVConstant *E) { return E; }
visitPtrToIntExprScopExpander345 const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *E) {
346 return SE.getPtrToIntExpr(visit(E->getOperand()), E->getType());
347 }
visitTruncateExprScopExpander348 const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
349 return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
350 }
visitZeroExtendExprScopExpander351 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
352 return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
353 }
visitSignExtendExprScopExpander354 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
355 return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
356 }
visitUDivExprScopExpander357 const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
358 auto *RHSScev = visit(E->getRHS());
359 if (!SE.isKnownNonZero(RHSScev))
360 RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
361 return SE.getUDivExpr(visit(E->getLHS()), RHSScev);
362 }
visitAddExprScopExpander363 const SCEV *visitAddExpr(const SCEVAddExpr *E) {
364 SmallVector<const SCEV *, 4> NewOps;
365 for (const SCEV *Op : E->operands())
366 NewOps.push_back(visit(Op));
367 return SE.getAddExpr(NewOps);
368 }
visitMulExprScopExpander369 const SCEV *visitMulExpr(const SCEVMulExpr *E) {
370 SmallVector<const SCEV *, 4> NewOps;
371 for (const SCEV *Op : E->operands())
372 NewOps.push_back(visit(Op));
373 return SE.getMulExpr(NewOps);
374 }
visitUMaxExprScopExpander375 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
376 SmallVector<const SCEV *, 4> NewOps;
377 for (const SCEV *Op : E->operands())
378 NewOps.push_back(visit(Op));
379 return SE.getUMaxExpr(NewOps);
380 }
visitSMaxExprScopExpander381 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
382 SmallVector<const SCEV *, 4> NewOps;
383 for (const SCEV *Op : E->operands())
384 NewOps.push_back(visit(Op));
385 return SE.getSMaxExpr(NewOps);
386 }
visitUMinExprScopExpander387 const SCEV *visitUMinExpr(const SCEVUMinExpr *E) {
388 SmallVector<const SCEV *, 4> NewOps;
389 for (const SCEV *Op : E->operands())
390 NewOps.push_back(visit(Op));
391 return SE.getUMinExpr(NewOps);
392 }
visitSMinExprScopExpander393 const SCEV *visitSMinExpr(const SCEVSMinExpr *E) {
394 SmallVector<const SCEV *, 4> NewOps;
395 for (const SCEV *Op : E->operands())
396 NewOps.push_back(visit(Op));
397 return SE.getSMinExpr(NewOps);
398 }
visitAddRecExprScopExpander399 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
400 SmallVector<const SCEV *, 4> NewOps;
401 for (const SCEV *Op : E->operands())
402 NewOps.push_back(visit(Op));
403 return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
404 }
405 ///}
406 };
407
expandCodeFor(Scop & S,ScalarEvolution & SE,const DataLayout & DL,const char * Name,const SCEV * E,Type * Ty,Instruction * IP,ValueMapT * VMap,BasicBlock * RTCBB)408 Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
409 const char *Name, const SCEV *E, Type *Ty,
410 Instruction *IP, ValueMapT *VMap,
411 BasicBlock *RTCBB) {
412 ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
413 return Expander.expandCodeFor(E, Ty, IP);
414 }
415
isErrorBlock(BasicBlock & BB,const Region & R,LoopInfo & LI,const DominatorTree & DT)416 bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
417 const DominatorTree &DT) {
418 if (!PollyAllowErrorBlocks)
419 return false;
420
421 if (isa<UnreachableInst>(BB.getTerminator()))
422 return true;
423
424 if (LI.isLoopHeader(&BB))
425 return false;
426
427 // Basic blocks that are always executed are not considered error blocks,
428 // as their execution can not be a rare event.
429 bool DominatesAllPredecessors = true;
430 if (R.isTopLevelRegion()) {
431 for (BasicBlock &I : *R.getEntry()->getParent())
432 if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I))
433 DominatesAllPredecessors = false;
434 } else {
435 for (auto Pred : predecessors(R.getExit()))
436 if (R.contains(Pred) && !DT.dominates(&BB, Pred))
437 DominatesAllPredecessors = false;
438 }
439
440 if (DominatesAllPredecessors)
441 return false;
442
443 for (Instruction &Inst : BB)
444 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
445 if (isDebugCall(CI))
446 continue;
447
448 if (isIgnoredIntrinsic(CI))
449 continue;
450
451 // memset, memcpy and memmove are modeled intrinsics.
452 if (isa<MemSetInst>(CI) || isa<MemTransferInst>(CI))
453 continue;
454
455 if (!CI->doesNotAccessMemory())
456 return true;
457 if (CI->doesNotReturn())
458 return true;
459 }
460
461 return false;
462 }
463
getConditionFromTerminator(Instruction * TI)464 Value *polly::getConditionFromTerminator(Instruction *TI) {
465 if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
466 if (BR->isUnconditional())
467 return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
468
469 return BR->getCondition();
470 }
471
472 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
473 return SI->getCondition();
474
475 return nullptr;
476 }
477
getLoopSurroundingScop(Scop & S,LoopInfo & LI)478 Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
479 // Start with the smallest loop containing the entry and expand that
480 // loop until it contains all blocks in the region. If there is a loop
481 // containing all blocks in the region check if it is itself contained
482 // and if so take the parent loop as it will be the smallest containing
483 // the region but not contained by it.
484 Loop *L = LI.getLoopFor(S.getEntry());
485 while (L) {
486 bool AllContained = true;
487 for (auto *BB : S.blocks())
488 AllContained &= L->contains(BB);
489 if (AllContained)
490 break;
491 L = L->getParentLoop();
492 }
493
494 return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
495 }
496
getNumBlocksInLoop(Loop * L)497 unsigned polly::getNumBlocksInLoop(Loop *L) {
498 unsigned NumBlocks = L->getNumBlocks();
499 SmallVector<BasicBlock *, 4> ExitBlocks;
500 L->getExitBlocks(ExitBlocks);
501
502 for (auto ExitBlock : ExitBlocks) {
503 if (isa<UnreachableInst>(ExitBlock->getTerminator()))
504 NumBlocks++;
505 }
506 return NumBlocks;
507 }
508
getNumBlocksInRegionNode(RegionNode * RN)509 unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) {
510 if (!RN->isSubRegion())
511 return 1;
512
513 Region *R = RN->getNodeAs<Region>();
514 return std::distance(R->block_begin(), R->block_end());
515 }
516
getRegionNodeLoop(RegionNode * RN,LoopInfo & LI)517 Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
518 if (!RN->isSubRegion()) {
519 BasicBlock *BB = RN->getNodeAs<BasicBlock>();
520 Loop *L = LI.getLoopFor(BB);
521
522 // Unreachable statements are not considered to belong to a LLVM loop, as
523 // they are not part of an actual loop in the control flow graph.
524 // Nevertheless, we handle certain unreachable statements that are common
525 // when modeling run-time bounds checks as being part of the loop to be
526 // able to model them and to later eliminate the run-time bounds checks.
527 //
528 // Specifically, for basic blocks that terminate in an unreachable and
529 // where the immediate predecessor is part of a loop, we assume these
530 // basic blocks belong to the loop the predecessor belongs to. This
531 // allows us to model the following code.
532 //
533 // for (i = 0; i < N; i++) {
534 // if (i > 1024)
535 // abort(); <- this abort might be translated to an
536 // unreachable
537 //
538 // A[i] = ...
539 // }
540 if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())
541 L = LI.getLoopFor(BB->getPrevNode());
542 return L;
543 }
544
545 Region *NonAffineSubRegion = RN->getNodeAs<Region>();
546 Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
547 while (L && NonAffineSubRegion->contains(L))
548 L = L->getParentLoop();
549 return L;
550 }
551
hasVariantIndex(GetElementPtrInst * Gep,Loop * L,Region & R,ScalarEvolution & SE)552 static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,
553 ScalarEvolution &SE) {
554 for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {
555 const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L);
556 Loop *OuterLoop = R.outermostLoopInRegion(L);
557 if (!SE.isLoopInvariant(PtrSCEV, OuterLoop))
558 return true;
559 }
560 return false;
561 }
562
isHoistableLoad(LoadInst * LInst,Region & R,LoopInfo & LI,ScalarEvolution & SE,const DominatorTree & DT,const InvariantLoadsSetTy & KnownInvariantLoads)563 bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
564 ScalarEvolution &SE, const DominatorTree &DT,
565 const InvariantLoadsSetTy &KnownInvariantLoads) {
566 Loop *L = LI.getLoopFor(LInst->getParent());
567 auto *Ptr = LInst->getPointerOperand();
568
569 // A LoadInst is hoistable if the address it is loading from is also
570 // invariant; in this case: another invariant load (whether that address
571 // is also not written to has to be checked separately)
572 // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst
573 // pattern generated by the Chapel frontend, but generally this applies
574 // for any chain of instruction that does not also depend on any
575 // induction variable
576 if (auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) {
577 if (!hasVariantIndex(GepInst, L, R, SE)) {
578 if (auto *DecidingLoad =
579 dyn_cast<LoadInst>(GepInst->getPointerOperand())) {
580 if (KnownInvariantLoads.count(DecidingLoad))
581 return true;
582 }
583 }
584 }
585
586 const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
587 while (L && R.contains(L)) {
588 if (!SE.isLoopInvariant(PtrSCEV, L))
589 return false;
590 L = L->getParentLoop();
591 }
592
593 for (auto *User : Ptr->users()) {
594 auto *UserI = dyn_cast<Instruction>(User);
595 if (!UserI || !R.contains(UserI))
596 continue;
597 if (!UserI->mayWriteToMemory())
598 continue;
599
600 auto &BB = *UserI->getParent();
601 if (DT.dominates(&BB, LInst->getParent()))
602 return false;
603
604 bool DominatesAllPredecessors = true;
605 if (R.isTopLevelRegion()) {
606 for (BasicBlock &I : *R.getEntry()->getParent())
607 if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I))
608 DominatesAllPredecessors = false;
609 } else {
610 for (auto Pred : predecessors(R.getExit()))
611 if (R.contains(Pred) && !DT.dominates(&BB, Pred))
612 DominatesAllPredecessors = false;
613 }
614
615 if (!DominatesAllPredecessors)
616 continue;
617
618 return false;
619 }
620
621 return true;
622 }
623
isIgnoredIntrinsic(const Value * V)624 bool polly::isIgnoredIntrinsic(const Value *V) {
625 if (auto *IT = dyn_cast<IntrinsicInst>(V)) {
626 switch (IT->getIntrinsicID()) {
627 // Lifetime markers are supported/ignored.
628 case llvm::Intrinsic::lifetime_start:
629 case llvm::Intrinsic::lifetime_end:
630 // Invariant markers are supported/ignored.
631 case llvm::Intrinsic::invariant_start:
632 case llvm::Intrinsic::invariant_end:
633 // Some misc annotations are supported/ignored.
634 case llvm::Intrinsic::var_annotation:
635 case llvm::Intrinsic::ptr_annotation:
636 case llvm::Intrinsic::annotation:
637 case llvm::Intrinsic::donothing:
638 case llvm::Intrinsic::assume:
639 // Some debug info intrinsics are supported/ignored.
640 case llvm::Intrinsic::dbg_value:
641 case llvm::Intrinsic::dbg_declare:
642 return true;
643 default:
644 break;
645 }
646 }
647 return false;
648 }
649
canSynthesize(const Value * V,const Scop & S,ScalarEvolution * SE,Loop * Scope)650 bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
651 Loop *Scope) {
652 if (!V || !SE->isSCEVable(V->getType()))
653 return false;
654
655 const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();
656 if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
657 if (!isa<SCEVCouldNotCompute>(Scev))
658 if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS))
659 return true;
660
661 return false;
662 }
663
getUseBlock(const llvm::Use & U)664 llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) {
665 Instruction *UI = dyn_cast<Instruction>(U.getUser());
666 if (!UI)
667 return nullptr;
668
669 if (PHINode *PHI = dyn_cast<PHINode>(UI))
670 return PHI->getIncomingBlock(U);
671
672 return UI->getParent();
673 }
674
getFirstNonBoxedLoopFor(llvm::Loop * L,llvm::LoopInfo & LI,const BoxedLoopsSetTy & BoxedLoops)675 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
676 const BoxedLoopsSetTy &BoxedLoops) {
677 while (BoxedLoops.count(L))
678 L = L->getParentLoop();
679 return L;
680 }
681
getFirstNonBoxedLoopFor(llvm::BasicBlock * BB,llvm::LoopInfo & LI,const BoxedLoopsSetTy & BoxedLoops)682 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
683 llvm::LoopInfo &LI,
684 const BoxedLoopsSetTy &BoxedLoops) {
685 Loop *L = LI.getLoopFor(BB);
686 return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
687 }
688
isDebugCall(Instruction * Inst)689 bool polly::isDebugCall(Instruction *Inst) {
690 auto *CI = dyn_cast<CallInst>(Inst);
691 if (!CI)
692 return false;
693
694 Function *CF = CI->getCalledFunction();
695 if (!CF)
696 return false;
697
698 return std::find(DebugFunctions.begin(), DebugFunctions.end(),
699 CF->getName()) != DebugFunctions.end();
700 }
701
hasDebugCall(BasicBlock * BB)702 static bool hasDebugCall(BasicBlock *BB) {
703 for (Instruction &Inst : *BB) {
704 if (isDebugCall(&Inst))
705 return true;
706 }
707 return false;
708 }
709
hasDebugCall(ScopStmt * Stmt)710 bool polly::hasDebugCall(ScopStmt *Stmt) {
711 // Quick skip if no debug functions have been defined.
712 if (DebugFunctions.empty())
713 return false;
714
715 if (!Stmt)
716 return false;
717
718 for (Instruction *Inst : Stmt->getInstructions())
719 if (isDebugCall(Inst))
720 return true;
721
722 if (Stmt->isRegionStmt()) {
723 for (BasicBlock *RBB : Stmt->getRegion()->blocks())
724 if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB))
725 return true;
726 }
727
728 return false;
729 }
730
731 /// Find a property in a LoopID.
findNamedMetadataNode(MDNode * LoopMD,StringRef Name)732 static MDNode *findNamedMetadataNode(MDNode *LoopMD, StringRef Name) {
733 if (!LoopMD)
734 return nullptr;
735 for (const MDOperand &X : drop_begin(LoopMD->operands(), 1)) {
736 auto *OpNode = dyn_cast<MDNode>(X.get());
737 if (!OpNode)
738 continue;
739
740 auto *OpName = dyn_cast<MDString>(OpNode->getOperand(0));
741 if (!OpName)
742 continue;
743 if (OpName->getString() == Name)
744 return OpNode;
745 }
746 return nullptr;
747 }
748
findNamedMetadataArg(MDNode * LoopID,StringRef Name)749 static Optional<const MDOperand *> findNamedMetadataArg(MDNode *LoopID,
750 StringRef Name) {
751 MDNode *MD = findNamedMetadataNode(LoopID, Name);
752 if (!MD)
753 return None;
754 switch (MD->getNumOperands()) {
755 case 1:
756 return nullptr;
757 case 2:
758 return &MD->getOperand(1);
759 default:
760 llvm_unreachable("loop metadata has 0 or 1 operand");
761 }
762 }
763
findMetadataOperand(MDNode * LoopMD,StringRef Name)764 Optional<Metadata *> polly::findMetadataOperand(MDNode *LoopMD,
765 StringRef Name) {
766 MDNode *MD = findNamedMetadataNode(LoopMD, Name);
767 if (!MD)
768 return None;
769 switch (MD->getNumOperands()) {
770 case 1:
771 return nullptr;
772 case 2:
773 return MD->getOperand(1).get();
774 default:
775 llvm_unreachable("loop metadata must have 0 or 1 operands");
776 }
777 }
778
getOptionalBoolLoopAttribute(MDNode * LoopID,StringRef Name)779 static Optional<bool> getOptionalBoolLoopAttribute(MDNode *LoopID,
780 StringRef Name) {
781 MDNode *MD = findNamedMetadataNode(LoopID, Name);
782 if (!MD)
783 return None;
784 switch (MD->getNumOperands()) {
785 case 1:
786 return true;
787 case 2:
788 if (ConstantInt *IntMD =
789 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
790 return IntMD->getZExtValue();
791 return true;
792 }
793 llvm_unreachable("unexpected number of options");
794 }
795
getBooleanLoopAttribute(MDNode * LoopID,StringRef Name)796 bool polly::getBooleanLoopAttribute(MDNode *LoopID, StringRef Name) {
797 return getOptionalBoolLoopAttribute(LoopID, Name).getValueOr(false);
798 }
799
getOptionalIntLoopAttribute(MDNode * LoopID,StringRef Name)800 llvm::Optional<int> polly::getOptionalIntLoopAttribute(MDNode *LoopID,
801 StringRef Name) {
802 const MDOperand *AttrMD =
803 findNamedMetadataArg(LoopID, Name).getValueOr(nullptr);
804 if (!AttrMD)
805 return None;
806
807 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
808 if (!IntMD)
809 return None;
810
811 return IntMD->getSExtValue();
812 }
813
hasDisableAllTransformsHint(Loop * L)814 bool polly::hasDisableAllTransformsHint(Loop *L) {
815 return llvm::hasDisableAllTransformsHint(L);
816 }
817
hasDisableAllTransformsHint(llvm::MDNode * LoopID)818 bool polly::hasDisableAllTransformsHint(llvm::MDNode *LoopID) {
819 return getBooleanLoopAttribute(LoopID, "llvm.loop.disable_nonforced");
820 }
821
getIslLoopAttr(isl::ctx Ctx,BandAttr * Attr)822 isl::id polly::getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr) {
823 assert(Attr && "Must be a valid BandAttr");
824
825 // The name "Loop" signals that this id contains a pointer to a BandAttr.
826 // The ScheduleOptimizer also uses the string "Inter iteration alias-free" in
827 // markers, but it's user pointer is an llvm::Value.
828 isl::id Result = isl::id::alloc(Ctx, "Loop with Metadata", Attr);
829 Result = isl::manage(isl_id_set_free_user(Result.release(), [](void *Ptr) {
830 BandAttr *Attr = reinterpret_cast<BandAttr *>(Ptr);
831 delete Attr;
832 }));
833 return Result;
834 }
835
createIslLoopAttr(isl::ctx Ctx,Loop * L)836 isl::id polly::createIslLoopAttr(isl::ctx Ctx, Loop *L) {
837 if (!L)
838 return {};
839
840 // A loop without metadata does not need to be annotated.
841 MDNode *LoopID = L->getLoopID();
842 if (!LoopID)
843 return {};
844
845 BandAttr *Attr = new BandAttr();
846 Attr->OriginalLoop = L;
847 Attr->Metadata = L->getLoopID();
848
849 return getIslLoopAttr(Ctx, Attr);
850 }
851
isLoopAttr(const isl::id & Id)852 bool polly::isLoopAttr(const isl::id &Id) {
853 if (Id.is_null())
854 return false;
855
856 return Id.get_name() == "Loop with Metadata";
857 }
858
getLoopAttr(const isl::id & Id)859 BandAttr *polly::getLoopAttr(const isl::id &Id) {
860 if (!isLoopAttr(Id))
861 return nullptr;
862
863 return reinterpret_cast<BandAttr *>(Id.get_user());
864 }
865