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