Bug Summary

File:polly/lib/Support/ScopHelper.cpp
Warning:line 88, column 5
Value stored to 'EnteringBB' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

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