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

source code of polly/lib/Support/ScopHelper.cpp