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, BasicBlock::iterator SplitPt,
169 DominatorTree *DT, llvm::LoopInfo *LI,
170 RegionInfo *RI) {
171 assert(Old);
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/// ScopExpander generates IR the the value of a SCEV that represents a value
232/// from a SCoP.
233///
234/// IMPORTANT: There are two ScalarEvolutions at play here. First, the SE that
235/// was used to analyze the original SCoP (not actually referenced anywhere
236/// here, but passed as argument to make the distinction clear). Second, GenSE
237/// which is the SE for the function that the code is emitted into. SE and GenSE
238/// may be different when the generated code is to be emitted into an outlined
239/// function, e.g. for a parallel loop. That is, each SCEV is to be used only by
240/// the SE that "owns" it and ScopExpander handles the translation between them.
241/// The SCEVVisitor methods are only to be called on SCEVs of the original SE.
242/// Their job is to create a new SCEV for GenSE. The nested SCEVExpander is to
243/// be used only with SCEVs belonging to GenSE. Currently SCEVs do not store a
244/// reference to the ScalarEvolution they belong to, so a mixup does not
245/// immediately cause a crash but certainly is a violation of its interface.
246///
247/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
248/// instruction but just use it, if it is referenced as a SCEVUnknown. We want
249/// however to generate new code if the instruction is in the analyzed region
250/// and we generate code outside/in front of that region. Hence, we generate the
251/// code for the SDiv/SRem operands in front of the analyzed region and then
252/// create a new SDiv/SRem operation there too.
253struct ScopExpander final : SCEVVisitor<ScopExpander, const SCEV *> {
254 friend struct SCEVVisitor<ScopExpander, const SCEV *>;
255
256 explicit ScopExpander(const Region &R, ScalarEvolution &SE, Function *GenFn,
257 ScalarEvolution &GenSE, const DataLayout &DL,
258 const char *Name, ValueMapT *VMap,
259 LoopToScevMapT *LoopMap, BasicBlock *RTCBB)
260 : Expander(GenSE, DL, Name, /*PreserveLCSSA=*/false), Name(Name), R(R),
261 VMap(VMap), LoopMap(LoopMap), RTCBB(RTCBB), GenSE(GenSE), GenFn(GenFn) {
262 }
263
264 Value *expandCodeFor(const SCEV *E, Type *Ty, BasicBlock::iterator IP) {
265 assert(isInGenRegion(&*IP) &&
266 "ScopExpander assumes to be applied to generated code region");
267 const SCEV *GenE = visit(E);
268 return Expander.expandCodeFor(SH: GenE, Ty, I: IP);
269 }
270
271 const SCEV *visit(const SCEV *E) {
272 // Cache the expansion results for intermediate SCEV expressions. A SCEV
273 // expression can refer to an operand multiple times (e.g. "x*x), so
274 // a naive visitor takes exponential time.
275 if (SCEVCache.count(Val: E))
276 return SCEVCache[E];
277 const SCEV *Result = SCEVVisitor::visit(S: E);
278 SCEVCache[E] = Result;
279 return Result;
280 }
281
282private:
283 SCEVExpander Expander;
284 const char *Name;
285 const Region &R;
286 ValueMapT *VMap;
287 LoopToScevMapT *LoopMap;
288 BasicBlock *RTCBB;
289 DenseMap<const SCEV *, const SCEV *> SCEVCache;
290
291 ScalarEvolution &GenSE;
292 Function *GenFn;
293
294 /// Is the instruction part of the original SCoP (in contrast to be located in
295 /// the code-generated region)?
296 bool isInOrigRegion(Instruction *Inst) {
297 Function *Fn = R.getEntry()->getParent();
298 bool isInOrigRegion = Inst->getFunction() == Fn && R.contains(Inst);
299 assert((isInOrigRegion || GenFn == Inst->getFunction()) &&
300 "Instruction expected to be either in the SCoP or the translated "
301 "region");
302 return isInOrigRegion;
303 }
304
305 bool isInGenRegion(Instruction *Inst) { return !isInOrigRegion(Inst); }
306
307 const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
308 BasicBlock::iterator IP) {
309 if (!Inst || isInGenRegion(Inst))
310 return E;
311
312 assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
313 !isa<PHINode>(Inst));
314
315 auto *InstClone = Inst->clone();
316 for (auto &Op : Inst->operands()) {
317 assert(GenSE.isSCEVable(Op->getType()));
318 const SCEV *OpSCEV = GenSE.getSCEV(V: Op);
319 auto *OpClone = expandCodeFor(E: OpSCEV, Ty: Op->getType(), IP);
320 InstClone->replaceUsesOfWith(From: Op, To: OpClone);
321 }
322
323 InstClone->setName(Name + Inst->getName());
324 InstClone->insertBefore(InsertPos: IP);
325 return GenSE.getSCEV(V: InstClone);
326 }
327
328 const SCEV *visitUnknown(const SCEVUnknown *E) {
329
330 // If a value mapping was given try if the underlying value is remapped.
331 Value *NewVal = VMap ? VMap->lookup(Val: E->getValue()) : nullptr;
332 if (NewVal) {
333 const SCEV *NewE = GenSE.getSCEV(V: NewVal);
334
335 // While the mapped value might be different the SCEV representation might
336 // not be. To this end we will check before we go into recursion here.
337 // FIXME: SCEVVisitor must only visit SCEVs that belong to the original
338 // SE. This calls it on SCEVs that belong GenSE.
339 if (E != NewE)
340 return visit(E: NewE);
341 }
342
343 Instruction *Inst = dyn_cast<Instruction>(Val: E->getValue());
344 BasicBlock::iterator IP;
345 if (Inst && isInGenRegion(Inst))
346 IP = Inst->getIterator();
347 else if (R.getEntry()->getParent() != GenFn) {
348 // RTCBB is in the original function, but we are generating for a
349 // subfunction so we cannot emit to RTCBB. Usually, we land here only
350 // because E->getValue() is not an instruction but a global or constant
351 // which do not need to emit anything.
352 IP = GenFn->getEntryBlock().getTerminator()->getIterator();
353 } else if (Inst && RTCBB->getParent() == Inst->getFunction())
354 IP = RTCBB->getTerminator()->getIterator();
355 else
356 IP = RTCBB->getParent()->getEntryBlock().getTerminator()->getIterator();
357
358 if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
359 Inst->getOpcode() != Instruction::SDiv))
360 return visitGenericInst(E, Inst, IP);
361
362 const SCEV *LHSScev = GenSE.getSCEV(V: Inst->getOperand(i: 0));
363 const SCEV *RHSScev = GenSE.getSCEV(V: Inst->getOperand(i: 1));
364
365 if (!GenSE.isKnownNonZero(S: RHSScev))
366 RHSScev = GenSE.getUMaxExpr(LHS: RHSScev, RHS: GenSE.getConstant(Ty: E->getType(), V: 1));
367
368 Value *LHS = expandCodeFor(E: LHSScev, Ty: E->getType(), IP);
369 Value *RHS = expandCodeFor(E: RHSScev, Ty: E->getType(), IP);
370
371 Inst = BinaryOperator::Create(Op: (Instruction::BinaryOps)Inst->getOpcode(),
372 S1: LHS, S2: RHS, Name: Inst->getName() + Name, InsertBefore: IP);
373 return GenSE.getSCEV(V: Inst);
374 }
375
376 /// The following functions will just traverse the SCEV and rebuild it using
377 /// GenSE and the new operands returned by the traversal.
378 ///
379 ///{
380 const SCEV *visitConstant(const SCEVConstant *E) { return E; }
381 const SCEV *visitVScale(const SCEVVScale *E) { return E; }
382 const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *E) {
383 return GenSE.getPtrToIntExpr(Op: visit(E: E->getOperand()), Ty: E->getType());
384 }
385 const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
386 return GenSE.getTruncateExpr(Op: visit(E: E->getOperand()), Ty: E->getType());
387 }
388 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
389 return GenSE.getZeroExtendExpr(Op: visit(E: E->getOperand()), Ty: E->getType());
390 }
391 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
392 return GenSE.getSignExtendExpr(Op: visit(E: E->getOperand()), Ty: E->getType());
393 }
394 const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
395 auto *RHSScev = visit(E: E->getRHS());
396 if (!GenSE.isKnownNonZero(S: RHSScev))
397 RHSScev = GenSE.getUMaxExpr(LHS: RHSScev, RHS: GenSE.getConstant(Ty: E->getType(), V: 1));
398 return GenSE.getUDivExpr(LHS: visit(E: E->getLHS()), RHS: RHSScev);
399 }
400 const SCEV *visitAddExpr(const SCEVAddExpr *E) {
401 SmallVector<const SCEV *, 4> NewOps;
402 for (const SCEV *Op : E->operands())
403 NewOps.push_back(Elt: visit(E: Op));
404 return GenSE.getAddExpr(Ops&: NewOps);
405 }
406 const SCEV *visitMulExpr(const SCEVMulExpr *E) {
407 SmallVector<const SCEV *, 4> NewOps;
408 for (const SCEV *Op : E->operands())
409 NewOps.push_back(Elt: visit(E: Op));
410 return GenSE.getMulExpr(Ops&: NewOps);
411 }
412 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
413 SmallVector<const SCEV *, 4> NewOps;
414 for (const SCEV *Op : E->operands())
415 NewOps.push_back(Elt: visit(E: Op));
416 return GenSE.getUMaxExpr(Operands&: NewOps);
417 }
418 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
419 SmallVector<const SCEV *, 4> NewOps;
420 for (const SCEV *Op : E->operands())
421 NewOps.push_back(Elt: visit(E: Op));
422 return GenSE.getSMaxExpr(Operands&: NewOps);
423 }
424 const SCEV *visitUMinExpr(const SCEVUMinExpr *E) {
425 SmallVector<const SCEV *, 4> NewOps;
426 for (const SCEV *Op : E->operands())
427 NewOps.push_back(Elt: visit(E: Op));
428 return GenSE.getUMinExpr(Operands&: NewOps);
429 }
430 const SCEV *visitSMinExpr(const SCEVSMinExpr *E) {
431 SmallVector<const SCEV *, 4> NewOps;
432 for (const SCEV *Op : E->operands())
433 NewOps.push_back(Elt: visit(E: Op));
434 return GenSE.getSMinExpr(Operands&: NewOps);
435 }
436 const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E) {
437 SmallVector<const SCEV *, 4> NewOps;
438 for (const SCEV *Op : E->operands())
439 NewOps.push_back(Elt: visit(E: Op));
440 return GenSE.getUMinExpr(Operands&: NewOps, /*Sequential=*/true);
441 }
442 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
443 SmallVector<const SCEV *, 4> NewOps;
444 for (const SCEV *Op : E->operands())
445 NewOps.push_back(Elt: visit(E: Op));
446
447 const Loop *L = E->getLoop();
448 const SCEV *GenLRepl = LoopMap ? LoopMap->lookup(Val: L) : nullptr;
449 if (!GenLRepl)
450 return GenSE.getAddRecExpr(Operands&: NewOps, L, Flags: E->getNoWrapFlags());
451
452 // evaluateAtIteration replaces the SCEVAddrExpr with a direct calculation.
453 const SCEV *Evaluated =
454 SCEVAddRecExpr::evaluateAtIteration(Operands: NewOps, It: GenLRepl, SE&: GenSE);
455
456 // FIXME: This emits a SCEV for GenSE (since GenLRepl will refer to the
457 // induction variable of a generated loop), so we should not use SCEVVisitor
458 // with it. However, it still contains references to the SCoP region.
459 return visit(E: Evaluated);
460 }
461 ///}
462};
463
464Value *polly::expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
465 llvm::Function *GenFn, ScalarEvolution &GenSE,
466 const DataLayout &DL, const char *Name,
467 const SCEV *E, Type *Ty, BasicBlock::iterator IP,
468 ValueMapT *VMap, LoopToScevMapT *LoopMap,
469 BasicBlock *RTCBB) {
470 ScopExpander Expander(S.getRegion(), SE, GenFn, GenSE, DL, Name, VMap,
471 LoopMap, RTCBB);
472 return Expander.expandCodeFor(E, Ty, IP);
473}
474
475Value *polly::getConditionFromTerminator(Instruction *TI) {
476 if (BranchInst *BR = dyn_cast<BranchInst>(Val: TI)) {
477 if (BR->isUnconditional())
478 return ConstantInt::getTrue(Ty: Type::getInt1Ty(C&: TI->getContext()));
479
480 return BR->getCondition();
481 }
482
483 if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: TI))
484 return SI->getCondition();
485
486 return nullptr;
487}
488
489Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
490 // Start with the smallest loop containing the entry and expand that
491 // loop until it contains all blocks in the region. If there is a loop
492 // containing all blocks in the region check if it is itself contained
493 // and if so take the parent loop as it will be the smallest containing
494 // the region but not contained by it.
495 Loop *L = LI.getLoopFor(BB: S.getEntry());
496 while (L) {
497 bool AllContained = true;
498 for (auto *BB : S.blocks())
499 AllContained &= L->contains(BB);
500 if (AllContained)
501 break;
502 L = L->getParentLoop();
503 }
504
505 return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
506}
507
508unsigned polly::getNumBlocksInLoop(Loop *L) {
509 unsigned NumBlocks = L->getNumBlocks();
510 SmallVector<BasicBlock *, 4> ExitBlocks;
511 L->getExitBlocks(ExitBlocks);
512
513 for (auto ExitBlock : ExitBlocks) {
514 if (isa<UnreachableInst>(Val: ExitBlock->getTerminator()))
515 NumBlocks++;
516 }
517 return NumBlocks;
518}
519
520unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) {
521 if (!RN->isSubRegion())
522 return 1;
523
524 Region *R = RN->getNodeAs<Region>();
525 return std::distance(first: R->block_begin(), last: R->block_end());
526}
527
528Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
529 if (!RN->isSubRegion()) {
530 BasicBlock *BB = RN->getNodeAs<BasicBlock>();
531 Loop *L = LI.getLoopFor(BB);
532
533 // Unreachable statements are not considered to belong to a LLVM loop, as
534 // they are not part of an actual loop in the control flow graph.
535 // Nevertheless, we handle certain unreachable statements that are common
536 // when modeling run-time bounds checks as being part of the loop to be
537 // able to model them and to later eliminate the run-time bounds checks.
538 //
539 // Specifically, for basic blocks that terminate in an unreachable and
540 // where the immediate predecessor is part of a loop, we assume these
541 // basic blocks belong to the loop the predecessor belongs to. This
542 // allows us to model the following code.
543 //
544 // for (i = 0; i < N; i++) {
545 // if (i > 1024)
546 // abort(); <- this abort might be translated to an
547 // unreachable
548 //
549 // A[i] = ...
550 // }
551 if (!L && isa<UnreachableInst>(Val: BB->getTerminator()) && BB->getPrevNode())
552 L = LI.getLoopFor(BB: BB->getPrevNode());
553 return L;
554 }
555
556 Region *NonAffineSubRegion = RN->getNodeAs<Region>();
557 Loop *L = LI.getLoopFor(BB: NonAffineSubRegion->getEntry());
558 while (L && NonAffineSubRegion->contains(L))
559 L = L->getParentLoop();
560 return L;
561}
562
563static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,
564 ScalarEvolution &SE) {
565 for (const Use &Val : llvm::drop_begin(RangeOrContainer: Gep->operands(), N: 1)) {
566 const SCEV *PtrSCEV = SE.getSCEVAtScope(V: Val, L);
567 Loop *OuterLoop = R.outermostLoopInRegion(L);
568 if (!SE.isLoopInvariant(S: PtrSCEV, L: OuterLoop))
569 return true;
570 }
571 return false;
572}
573
574bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
575 ScalarEvolution &SE, const DominatorTree &DT,
576 const InvariantLoadsSetTy &KnownInvariantLoads) {
577 Loop *L = LI.getLoopFor(BB: LInst->getParent());
578 auto *Ptr = LInst->getPointerOperand();
579
580 // A LoadInst is hoistable if the address it is loading from is also
581 // invariant; in this case: another invariant load (whether that address
582 // is also not written to has to be checked separately)
583 // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst
584 // pattern generated by the Chapel frontend, but generally this applies
585 // for any chain of instruction that does not also depend on any
586 // induction variable
587 if (auto *GepInst = dyn_cast<GetElementPtrInst>(Val: Ptr)) {
588 if (!hasVariantIndex(Gep: GepInst, L, R, SE)) {
589 if (auto *DecidingLoad =
590 dyn_cast<LoadInst>(Val: GepInst->getPointerOperand())) {
591 if (KnownInvariantLoads.count(key: DecidingLoad))
592 return true;
593 }
594 }
595 }
596
597 const SCEV *PtrSCEV = SE.getSCEVAtScope(V: Ptr, L);
598 while (L && R.contains(L)) {
599 if (!SE.isLoopInvariant(S: PtrSCEV, L))
600 return false;
601 L = L->getParentLoop();
602 }
603
604 if (!Ptr->hasUseList())
605 return true;
606
607 for (auto *User : Ptr->users()) {
608 auto *UserI = dyn_cast<Instruction>(Val: User);
609 if (!UserI || UserI->getFunction() != LInst->getFunction() ||
610 !R.contains(Inst: UserI))
611 continue;
612 if (!UserI->mayWriteToMemory())
613 continue;
614
615 auto &BB = *UserI->getParent();
616 if (DT.dominates(A: &BB, B: LInst->getParent()))
617 return false;
618
619 bool DominatesAllPredecessors = true;
620 if (R.isTopLevelRegion()) {
621 for (BasicBlock &I : *R.getEntry()->getParent())
622 if (isa<ReturnInst>(Val: I.getTerminator()) && !DT.dominates(A: &BB, B: &I))
623 DominatesAllPredecessors = false;
624 } else {
625 for (auto Pred : predecessors(BB: R.getExit()))
626 if (R.contains(BB: Pred) && !DT.dominates(A: &BB, B: Pred))
627 DominatesAllPredecessors = false;
628 }
629
630 if (!DominatesAllPredecessors)
631 continue;
632
633 return false;
634 }
635
636 return true;
637}
638
639bool polly::isIgnoredIntrinsic(const Value *V) {
640 if (auto *IT = dyn_cast<IntrinsicInst>(Val: V)) {
641 switch (IT->getIntrinsicID()) {
642 // Lifetime markers are supported/ignored.
643 case llvm::Intrinsic::lifetime_start:
644 case llvm::Intrinsic::lifetime_end:
645 // Invariant markers are supported/ignored.
646 case llvm::Intrinsic::invariant_start:
647 case llvm::Intrinsic::invariant_end:
648 // Some misc annotations are supported/ignored.
649 case llvm::Intrinsic::var_annotation:
650 case llvm::Intrinsic::ptr_annotation:
651 case llvm::Intrinsic::annotation:
652 case llvm::Intrinsic::donothing:
653 case llvm::Intrinsic::assume:
654 // Some debug info intrinsics are supported/ignored.
655 case llvm::Intrinsic::dbg_value:
656 case llvm::Intrinsic::dbg_declare:
657 return true;
658 default:
659 break;
660 }
661 }
662 return false;
663}
664
665bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
666 Loop *Scope) {
667 if (!V || !SE->isSCEVable(Ty: V->getType()))
668 return false;
669
670 const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();
671 if (const SCEV *Scev = SE->getSCEVAtScope(V: const_cast<Value *>(V), L: Scope))
672 if (!isa<SCEVCouldNotCompute>(Val: Scev))
673 if (!hasScalarDepsInsideRegion(Expr: Scev, R: &S.getRegion(), Scope, AllowLoops: false, ILS))
674 return true;
675
676 return false;
677}
678
679llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) {
680 Instruction *UI = dyn_cast<Instruction>(Val: U.getUser());
681 if (!UI)
682 return nullptr;
683
684 if (PHINode *PHI = dyn_cast<PHINode>(Val: UI))
685 return PHI->getIncomingBlock(U);
686
687 return UI->getParent();
688}
689
690llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
691 const BoxedLoopsSetTy &BoxedLoops) {
692 while (BoxedLoops.count(key: L))
693 L = L->getParentLoop();
694 return L;
695}
696
697llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
698 llvm::LoopInfo &LI,
699 const BoxedLoopsSetTy &BoxedLoops) {
700 Loop *L = LI.getLoopFor(BB);
701 return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
702}
703
704bool polly::isDebugCall(Instruction *Inst) {
705 auto *CI = dyn_cast<CallInst>(Val: Inst);
706 if (!CI)
707 return false;
708
709 Function *CF = CI->getCalledFunction();
710 if (!CF)
711 return false;
712
713 return std::find(first: DebugFunctions.begin(), last: DebugFunctions.end(),
714 val: CF->getName()) != DebugFunctions.end();
715}
716
717static bool hasDebugCall(BasicBlock *BB) {
718 for (Instruction &Inst : *BB) {
719 if (isDebugCall(Inst: &Inst))
720 return true;
721 }
722 return false;
723}
724
725bool polly::hasDebugCall(ScopStmt *Stmt) {
726 // Quick skip if no debug functions have been defined.
727 if (DebugFunctions.empty())
728 return false;
729
730 if (!Stmt)
731 return false;
732
733 for (Instruction *Inst : Stmt->getInstructions())
734 if (isDebugCall(Inst))
735 return true;
736
737 if (Stmt->isRegionStmt()) {
738 for (BasicBlock *RBB : Stmt->getRegion()->blocks())
739 if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(BB: RBB))
740 return true;
741 }
742
743 return false;
744}
745
746/// Find a property in a LoopID.
747static MDNode *findNamedMetadataNode(MDNode *LoopMD, StringRef Name) {
748 if (!LoopMD)
749 return nullptr;
750 for (const MDOperand &X : drop_begin(RangeOrContainer: LoopMD->operands(), N: 1)) {
751 auto *OpNode = dyn_cast<MDNode>(Val: X.get());
752 if (!OpNode)
753 continue;
754
755 auto *OpName = dyn_cast<MDString>(Val: OpNode->getOperand(I: 0));
756 if (!OpName)
757 continue;
758 if (OpName->getString() == Name)
759 return OpNode;
760 }
761 return nullptr;
762}
763
764static std::optional<const MDOperand *> findNamedMetadataArg(MDNode *LoopID,
765 StringRef Name) {
766 MDNode *MD = findNamedMetadataNode(LoopMD: LoopID, Name);
767 if (!MD)
768 return std::nullopt;
769 switch (MD->getNumOperands()) {
770 case 1:
771 return nullptr;
772 case 2:
773 return &MD->getOperand(I: 1);
774 default:
775 llvm_unreachable("loop metadata has 0 or 1 operand");
776 }
777}
778
779std::optional<Metadata *> polly::findMetadataOperand(MDNode *LoopMD,
780 StringRef Name) {
781 MDNode *MD = findNamedMetadataNode(LoopMD, Name);
782 if (!MD)
783 return std::nullopt;
784 switch (MD->getNumOperands()) {
785 case 1:
786 return nullptr;
787 case 2:
788 return MD->getOperand(I: 1).get();
789 default:
790 llvm_unreachable("loop metadata must have 0 or 1 operands");
791 }
792}
793
794static std::optional<bool> getOptionalBoolLoopAttribute(MDNode *LoopID,
795 StringRef Name) {
796 MDNode *MD = findNamedMetadataNode(LoopMD: LoopID, Name);
797 if (!MD)
798 return std::nullopt;
799 switch (MD->getNumOperands()) {
800 case 1:
801 return true;
802 case 2:
803 if (ConstantInt *IntMD =
804 mdconst::extract_or_null<ConstantInt>(MD: MD->getOperand(I: 1).get()))
805 return IntMD->getZExtValue();
806 return true;
807 }
808 llvm_unreachable("unexpected number of options");
809}
810
811bool polly::getBooleanLoopAttribute(MDNode *LoopID, StringRef Name) {
812 return getOptionalBoolLoopAttribute(LoopID, Name).value_or(u: false);
813}
814
815std::optional<int> polly::getOptionalIntLoopAttribute(MDNode *LoopID,
816 StringRef Name) {
817 const MDOperand *AttrMD =
818 findNamedMetadataArg(LoopID, Name).value_or(u: nullptr);
819 if (!AttrMD)
820 return std::nullopt;
821
822 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(MD: AttrMD->get());
823 if (!IntMD)
824 return std::nullopt;
825
826 return IntMD->getSExtValue();
827}
828
829bool polly::hasDisableAllTransformsHint(Loop *L) {
830 return llvm::hasDisableAllTransformsHint(L);
831}
832
833bool polly::hasDisableAllTransformsHint(llvm::MDNode *LoopID) {
834 return getBooleanLoopAttribute(LoopID, Name: "llvm.loop.disable_nonforced");
835}
836
837isl::id polly::getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr) {
838 assert(Attr && "Must be a valid BandAttr");
839
840 // The name "Loop" signals that this id contains a pointer to a BandAttr.
841 // The ScheduleOptimizer also uses the string "Inter iteration alias-free" in
842 // markers, but it's user pointer is an llvm::Value.
843 isl::id Result = isl::id::alloc(ctx: Ctx, name: "Loop with Metadata", user: Attr);
844 Result = isl::manage(ptr: isl_id_set_free_user(id: Result.release(), free_user: [](void *Ptr) {
845 BandAttr *Attr = reinterpret_cast<BandAttr *>(Ptr);
846 delete Attr;
847 }));
848 return Result;
849}
850
851isl::id polly::createIslLoopAttr(isl::ctx Ctx, Loop *L) {
852 if (!L)
853 return {};
854
855 // A loop without metadata does not need to be annotated.
856 MDNode *LoopID = L->getLoopID();
857 if (!LoopID)
858 return {};
859
860 BandAttr *Attr = new BandAttr();
861 Attr->OriginalLoop = L;
862 Attr->Metadata = L->getLoopID();
863
864 return getIslLoopAttr(Ctx, Attr);
865}
866
867bool polly::isLoopAttr(const isl::id &Id) {
868 if (Id.is_null())
869 return false;
870
871 return Id.get_name() == "Loop with Metadata";
872}
873
874BandAttr *polly::getLoopAttr(const isl::id &Id) {
875 if (!isLoopAttr(Id))
876 return nullptr;
877
878 return reinterpret_cast<BandAttr *>(Id.get_user());
879}
880

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