1 //===- ScopHelper.cpp - Some Helper Functions for Scop.  ------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Small functions that help with Scop and LLVM-IR.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "polly/Support/ScopHelper.h"
15 #include "polly/Options.h"
16 #include "polly/ScopInfo.h"
17 #include "polly/Support/SCEVValidator.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/RegionInfo.h"
20 #include "llvm/Analysis/ScalarEvolution.h"
21 #include "llvm/Analysis/ScalarEvolutionExpander.h"
22 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
27 
28 using namespace llvm;
29 using namespace polly;
30 
31 #define DEBUG_TYPE "polly-scop-helper"
32 
33 bool polly::hasInvokeEdge(const PHINode *PN) {
34   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
35     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
36       if (II->getParent() == PN->getIncomingBlock(i))
37         return true;
38 
39   return false;
40 }
41 
42 // Ensures that there is just one predecessor to the entry node from outside the
43 // region.
44 // The identity of the region entry node is preserved.
45 static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
46                                 RegionInfo *RI) {
47   BasicBlock *EnteringBB = R->getEnteringBlock();
48   BasicBlock *Entry = R->getEntry();
49 
50   // Before (one of):
51   //
52   //                       \    /            //
53   //                      EnteringBB         //
54   //                        |    \------>    //
55   //   \   /                |                //
56   //   Entry <--\         Entry <--\         //
57   //   /   \    /         /   \    /         //
58   //        ....               ....          //
59 
60   // Create single entry edge if the region has multiple entry edges.
61   if (!EnteringBB) {
62     SmallVector<BasicBlock *, 4> Preds;
63     for (BasicBlock *P : predecessors(Entry))
64       if (!R->contains(P))
65         Preds.push_back(P);
66 
67     BasicBlock *NewEntering =
68         SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
69 
70     if (RI) {
71       // The exit block of predecessing regions must be changed to NewEntering
72       for (BasicBlock *ExitPred : predecessors(NewEntering)) {
73         Region *RegionOfPred = RI->getRegionFor(ExitPred);
74         if (RegionOfPred->getExit() != Entry)
75           continue;
76 
77         while (!RegionOfPred->isTopLevelRegion() &&
78                RegionOfPred->getExit() == Entry) {
79           RegionOfPred->replaceExit(NewEntering);
80           RegionOfPred = RegionOfPred->getParent();
81         }
82       }
83 
84       // Make all ancestors use EnteringBB as entry; there might be edges to it
85       Region *AncestorR = R->getParent();
86       RI->setRegionFor(NewEntering, AncestorR);
87       while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) {
88         AncestorR->replaceEntry(NewEntering);
89         AncestorR = AncestorR->getParent();
90       }
91     }
92 
93     EnteringBB = NewEntering;
94   }
95   assert(R->getEnteringBlock() == EnteringBB);
96 
97   // After:
98   //
99   //    \    /       //
100   //  EnteringBB     //
101   //      |          //
102   //      |          //
103   //    Entry <--\   //
104   //    /   \    /   //
105   //         ....    //
106 }
107 
108 // Ensure that the region has a single block that branches to the exit node.
109 static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
110                                RegionInfo *RI) {
111   BasicBlock *ExitBB = R->getExit();
112   BasicBlock *ExitingBB = R->getExitingBlock();
113 
114   // Before:
115   //
116   //   (Region)   ______/  //
117   //      \  |   /         //
118   //       ExitBB          //
119   //       /    \          //
120 
121   if (!ExitingBB) {
122     SmallVector<BasicBlock *, 4> Preds;
123     for (BasicBlock *P : predecessors(ExitBB))
124       if (R->contains(P))
125         Preds.push_back(P);
126 
127     //  Preds[0] Preds[1]      otherBB //
128     //         \  |  ________/         //
129     //          \ | /                  //
130     //           BB                    //
131     ExitingBB =
132         SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
133     // Preds[0] Preds[1]      otherBB  //
134     //        \  /           /         //
135     // BB.region_exiting    /          //
136     //                  \  /           //
137     //                   BB            //
138 
139     if (RI)
140       RI->setRegionFor(ExitingBB, R);
141 
142     // Change the exit of nested regions, but not the region itself,
143     R->replaceExitRecursive(ExitingBB);
144     R->replaceExit(ExitBB);
145   }
146   assert(ExitingBB == R->getExitingBlock());
147 
148   // After:
149   //
150   //     \   /                //
151   //    ExitingBB     _____/  //
152   //          \      /        //
153   //           ExitBB         //
154   //           /    \         //
155 }
156 
157 void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
158                            RegionInfo *RI) {
159   assert(R && !R->isTopLevelRegion());
160   assert(!RI || RI == R->getRegionInfo());
161   assert((!RI || DT) &&
162          "RegionInfo requires DominatorTree to be updated as well");
163 
164   simplifyRegionEntry(R, DT, LI, RI);
165   simplifyRegionExit(R, DT, LI, RI);
166   assert(R->isSimple());
167 }
168 
169 // Split the block into two successive blocks.
170 //
171 // Like llvm::SplitBlock, but also preserves RegionInfo
172 static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
173                               DominatorTree *DT, llvm::LoopInfo *LI,
174                               RegionInfo *RI) {
175   assert(Old && SplitPt);
176 
177   // Before:
178   //
179   //  \   /  //
180   //   Old   //
181   //  /   \  //
182 
183   BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
184 
185   if (RI) {
186     Region *R = RI->getRegionFor(Old);
187     RI->setRegionFor(NewBlock, R);
188   }
189 
190   // After:
191   //
192   //   \   /    //
193   //    Old     //
194   //     |      //
195   //  NewBlock  //
196   //   /   \    //
197 
198   return NewBlock;
199 }
200 
201 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
202   // Find first non-alloca instruction. Every basic block has a non-alloc
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   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
209   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
210   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
211   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
212   RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
213   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
214 
215   // splitBlock updates DT, LI and RI.
216   splitBlock(EntryBlock, &*I, DT, LI, RI);
217 }
218 
219 /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
220 /// instruction but just use it, if it is referenced as a SCEVUnknown. We want
221 /// however to generate new code if the instruction is in the analyzed region
222 /// and we generate code outside/in front of that region. Hence, we generate the
223 /// code for the SDiv/SRem operands in front of the analyzed region and then
224 /// create a new SDiv/SRem operation there too.
225 struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
226   friend struct SCEVVisitor<ScopExpander, const SCEV *>;
227 
228   explicit ScopExpander(const Region &R, ScalarEvolution &SE,
229                         const DataLayout &DL, const char *Name, ValueMapT *VMap,
230                         BasicBlock *RTCBB)
231       : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
232         VMap(VMap), RTCBB(RTCBB) {}
233 
234   Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
235     // If we generate code in the region we will immediately fall back to the
236     // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
237     // needed replace them by copies computed in the entering block.
238     if (!R.contains(I))
239       E = visit(E);
240     return Expander.expandCodeFor(E, Ty, I);
241   }
242 
243 private:
244   SCEVExpander Expander;
245   ScalarEvolution &SE;
246   const char *Name;
247   const Region &R;
248   ValueMapT *VMap;
249   BasicBlock *RTCBB;
250 
251   const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
252                                Instruction *IP) {
253     if (!Inst || !R.contains(Inst))
254       return E;
255 
256     assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
257            !isa<PHINode>(Inst));
258 
259     auto *InstClone = Inst->clone();
260     for (auto &Op : Inst->operands()) {
261       assert(SE.isSCEVable(Op->getType()));
262       auto *OpSCEV = SE.getSCEV(Op);
263       auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);
264       InstClone->replaceUsesOfWith(Op, OpClone);
265     }
266 
267     InstClone->setName(Name + Inst->getName());
268     InstClone->insertBefore(IP);
269     return SE.getSCEV(InstClone);
270   }
271 
272   const SCEV *visitUnknown(const SCEVUnknown *E) {
273 
274     // If a value mapping was given try if the underlying value is remapped.
275     Value *NewVal = VMap ? VMap->lookup(E->getValue()) : nullptr;
276     if (NewVal) {
277       auto *NewE = SE.getSCEV(NewVal);
278 
279       // While the mapped value might be different the SCEV representation might
280       // not be. To this end we will check before we go into recursion here.
281       if (E != NewE)
282         return visit(NewE);
283     }
284 
285     Instruction *Inst = dyn_cast<Instruction>(E->getValue());
286     Instruction *IP;
287     if (Inst && !R.contains(Inst))
288       IP = Inst;
289     else if (Inst && RTCBB->getParent() == Inst->getFunction())
290       IP = RTCBB->getTerminator();
291     else
292       IP = RTCBB->getParent()->getEntryBlock().getTerminator();
293 
294     if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
295                   Inst->getOpcode() != Instruction::SDiv))
296       return visitGenericInst(E, Inst, IP);
297 
298     const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
299     const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
300 
301     if (!SE.isKnownNonZero(RHSScev))
302       RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
303 
304     Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);
305     Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);
306 
307     Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
308                                   LHS, RHS, Inst->getName() + Name, IP);
309     return SE.getSCEV(Inst);
310   }
311 
312   /// The following functions will just traverse the SCEV and rebuild it with
313   /// the new operands returned by the traversal.
314   ///
315   ///{
316   const SCEV *visitConstant(const SCEVConstant *E) { return E; }
317   const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
318     return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
319   }
320   const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
321     return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
322   }
323   const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
324     return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
325   }
326   const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
327     auto *RHSScev = visit(E->getRHS());
328     if (!SE.isKnownNonZero(RHSScev))
329       RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
330     return SE.getUDivExpr(visit(E->getLHS()), RHSScev);
331   }
332   const SCEV *visitAddExpr(const SCEVAddExpr *E) {
333     SmallVector<const SCEV *, 4> NewOps;
334     for (const SCEV *Op : E->operands())
335       NewOps.push_back(visit(Op));
336     return SE.getAddExpr(NewOps);
337   }
338   const SCEV *visitMulExpr(const SCEVMulExpr *E) {
339     SmallVector<const SCEV *, 4> NewOps;
340     for (const SCEV *Op : E->operands())
341       NewOps.push_back(visit(Op));
342     return SE.getMulExpr(NewOps);
343   }
344   const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
345     SmallVector<const SCEV *, 4> NewOps;
346     for (const SCEV *Op : E->operands())
347       NewOps.push_back(visit(Op));
348     return SE.getUMaxExpr(NewOps);
349   }
350   const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
351     SmallVector<const SCEV *, 4> NewOps;
352     for (const SCEV *Op : E->operands())
353       NewOps.push_back(visit(Op));
354     return SE.getSMaxExpr(NewOps);
355   }
356   const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
357     SmallVector<const SCEV *, 4> NewOps;
358     for (const SCEV *Op : E->operands())
359       NewOps.push_back(visit(Op));
360     return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
361   }
362   ///}
363 };
364 
365 Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
366                             const char *Name, const SCEV *E, Type *Ty,
367                             Instruction *IP, ValueMapT *VMap,
368                             BasicBlock *RTCBB) {
369   ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
370   return Expander.expandCodeFor(E, Ty, IP);
371 }
372 
373 bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
374                          const DominatorTree &DT) {
375 
376   if (isa<UnreachableInst>(BB.getTerminator()))
377     return true;
378 
379   if (LI.isLoopHeader(&BB))
380     return false;
381 
382   // Basic blocks that are always executed are not considered error blocks,
383   // as their execution can not be a rare event.
384   bool DominatesAllPredecessors = true;
385   for (auto Pred : predecessors(R.getExit()))
386     if (R.contains(Pred) && !DT.dominates(&BB, Pred))
387       DominatesAllPredecessors = false;
388 
389   if (DominatesAllPredecessors)
390     return false;
391 
392   // FIXME: This is a simple heuristic to determine if the load is executed
393   //        in a conditional. However, we actually would need the control
394   //        condition, i.e., the post dominance frontier. Alternatively we
395   //        could walk up the dominance tree until we find a block that is
396   //        not post dominated by the load and check if it is a conditional
397   //        or a loop header.
398   auto *DTNode = DT.getNode(&BB);
399   auto *IDomBB = DTNode->getIDom()->getBlock();
400   if (LI.isLoopHeader(IDomBB))
401     return false;
402 
403   for (Instruction &Inst : BB)
404     if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
405       if (isIgnoredIntrinsic(CI))
406         return false;
407 
408       if (!CI->doesNotAccessMemory())
409         return true;
410       if (CI->doesNotReturn())
411         return true;
412     }
413 
414   return false;
415 }
416 
417 Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
418   if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
419     if (BR->isUnconditional())
420       return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
421 
422     return BR->getCondition();
423   }
424 
425   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
426     return SI->getCondition();
427 
428   return nullptr;
429 }
430 
431 bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
432                             ScalarEvolution &SE) {
433   Loop *L = LI.getLoopFor(LInst->getParent());
434   const SCEV *PtrSCEV = SE.getSCEVAtScope(LInst->getPointerOperand(), L);
435   while (L && R.contains(L)) {
436     if (!SE.isLoopInvariant(PtrSCEV, L))
437       return false;
438     L = L->getParentLoop();
439   }
440 
441   return true;
442 }
443 
444 bool polly::isIgnoredIntrinsic(const Value *V) {
445   if (auto *IT = dyn_cast<IntrinsicInst>(V)) {
446     switch (IT->getIntrinsicID()) {
447     // Lifetime markers are supported/ignored.
448     case llvm::Intrinsic::lifetime_start:
449     case llvm::Intrinsic::lifetime_end:
450     // Invariant markers are supported/ignored.
451     case llvm::Intrinsic::invariant_start:
452     case llvm::Intrinsic::invariant_end:
453     // Some misc annotations are supported/ignored.
454     case llvm::Intrinsic::var_annotation:
455     case llvm::Intrinsic::ptr_annotation:
456     case llvm::Intrinsic::annotation:
457     case llvm::Intrinsic::donothing:
458     case llvm::Intrinsic::assume:
459     case llvm::Intrinsic::expect:
460     // Some debug info intrisics are supported/ignored.
461     case llvm::Intrinsic::dbg_value:
462     case llvm::Intrinsic::dbg_declare:
463       return true;
464     default:
465       break;
466     }
467   }
468   return false;
469 }
470 
471 bool polly::canSynthesize(const Value *V, const Scop &S,
472                           const llvm::LoopInfo *LI, ScalarEvolution *SE,
473                           Loop *Scope) {
474   if (!V || !SE->isSCEVable(V->getType()))
475     return false;
476 
477   if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
478     if (!isa<SCEVCouldNotCompute>(Scev))
479       if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false))
480         return true;
481 
482   return false;
483 }
484 
485 llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
486   Instruction *UI = dyn_cast<Instruction>(U.getUser());
487   if (!UI)
488     return nullptr;
489 
490   if (PHINode *PHI = dyn_cast<PHINode>(UI))
491     return PHI->getIncomingBlock(U);
492 
493   return UI->getParent();
494 }
495 
496 std::tuple<std::vector<const SCEV *>, std::vector<int>>
497 polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
498   std::vector<const SCEV *> Subscripts;
499   std::vector<int> Sizes;
500 
501   Type *Ty = GEP->getPointerOperandType();
502 
503   bool DroppedFirstDim = false;
504 
505   for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
506 
507     const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
508 
509     if (i == 1) {
510       if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
511         Ty = PtrTy->getElementType();
512       } else if (auto *ArrayTy = dyn_cast<ArrayType>(Ty)) {
513         Ty = ArrayTy->getElementType();
514       } else {
515         Subscripts.clear();
516         Sizes.clear();
517         break;
518       }
519       if (auto *Const = dyn_cast<SCEVConstant>(Expr))
520         if (Const->getValue()->isZero()) {
521           DroppedFirstDim = true;
522           continue;
523         }
524       Subscripts.push_back(Expr);
525       continue;
526     }
527 
528     auto *ArrayTy = dyn_cast<ArrayType>(Ty);
529     if (!ArrayTy) {
530       Subscripts.clear();
531       Sizes.clear();
532       break;
533     }
534 
535     Subscripts.push_back(Expr);
536     if (!(DroppedFirstDim && i == 2))
537       Sizes.push_back(ArrayTy->getNumElements());
538 
539     Ty = ArrayTy->getElementType();
540   }
541 
542   return std::make_tuple(Subscripts, Sizes);
543 }
544