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/ScopInfo.h"
16 #include "llvm/Analysis/AliasAnalysis.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/IR/CFG.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
25 
26 using namespace llvm;
27 using namespace polly;
28 
29 #define DEBUG_TYPE "polly-scop-helper"
30 
31 Value *polly::getPointerOperand(Instruction &Inst) {
32   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
33     return load->getPointerOperand();
34   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
35     return store->getPointerOperand();
36   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
37     return gep->getPointerOperand();
38 
39   return 0;
40 }
41 
42 bool polly::hasInvokeEdge(const PHINode *PN) {
43   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
44     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
45       if (II->getParent() == PN->getIncomingBlock(i))
46         return true;
47 
48   return false;
49 }
50 
51 // Ensures that there is just one predecessor to the entry node from outside the
52 // region.
53 // The identity of the region entry node is preserved.
54 static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
55                                 RegionInfo *RI) {
56   BasicBlock *EnteringBB = R->getEnteringBlock();
57   BasicBlock *Entry = R->getEntry();
58 
59   // Before (one of):
60   //
61   //                       \    /            //
62   //                      EnteringBB         //
63   //                        |    \------>    //
64   //   \   /                |                //
65   //   Entry <--\         Entry <--\         //
66   //   /   \    /         /   \    /         //
67   //        ....               ....          //
68 
69   // Create single entry edge if the region has multiple entry edges.
70   if (!EnteringBB) {
71     SmallVector<BasicBlock *, 4> Preds;
72     for (BasicBlock *P : predecessors(Entry))
73       if (!R->contains(P))
74         Preds.push_back(P);
75 
76     BasicBlock *NewEntering =
77         SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
78 
79     if (RI) {
80       // The exit block of predecessing regions must be changed to NewEntering
81       for (BasicBlock *ExitPred : predecessors(NewEntering)) {
82         Region *RegionOfPred = RI->getRegionFor(ExitPred);
83         if (RegionOfPred->getExit() != Entry)
84           continue;
85 
86         while (!RegionOfPred->isTopLevelRegion() &&
87                RegionOfPred->getExit() == Entry) {
88           RegionOfPred->replaceExit(NewEntering);
89           RegionOfPred = RegionOfPred->getParent();
90         }
91       }
92 
93       // Make all ancestors use EnteringBB as entry; there might be edges to it
94       Region *AncestorR = R->getParent();
95       RI->setRegionFor(NewEntering, AncestorR);
96       while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) {
97         AncestorR->replaceEntry(NewEntering);
98         AncestorR = AncestorR->getParent();
99       }
100     }
101 
102     EnteringBB = NewEntering;
103   }
104   assert(R->getEnteringBlock() == EnteringBB);
105 
106   // After:
107   //
108   //    \    /       //
109   //  EnteringBB     //
110   //      |          //
111   //      |          //
112   //    Entry <--\   //
113   //    /   \    /   //
114   //         ....    //
115 }
116 
117 // Ensure that the region has a single block that branches to the exit node.
118 static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
119                                RegionInfo *RI) {
120   BasicBlock *ExitBB = R->getExit();
121   BasicBlock *ExitingBB = R->getExitingBlock();
122 
123   // Before:
124   //
125   //   (Region)   ______/  //
126   //      \  |   /         //
127   //       ExitBB          //
128   //       /    \          //
129 
130   if (!ExitingBB) {
131     SmallVector<BasicBlock *, 4> Preds;
132     for (BasicBlock *P : predecessors(ExitBB))
133       if (R->contains(P))
134         Preds.push_back(P);
135 
136     //  Preds[0] Preds[1]      otherBB //
137     //         \  |  ________/         //
138     //          \ | /                  //
139     //           BB                    //
140     ExitingBB =
141         SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
142     // Preds[0] Preds[1]      otherBB  //
143     //        \  /           /         //
144     // BB.region_exiting    /          //
145     //                  \  /           //
146     //                   BB            //
147 
148     if (RI)
149       RI->setRegionFor(ExitingBB, R);
150 
151     // Change the exit of nested regions, but not the region itself,
152     R->replaceExitRecursive(ExitingBB);
153     R->replaceExit(ExitBB);
154   }
155   assert(ExitingBB == R->getExitingBlock());
156 
157   // After:
158   //
159   //     \   /                //
160   //    ExitingBB     _____/  //
161   //          \      /        //
162   //           ExitBB         //
163   //           /    \         //
164 }
165 
166 void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
167                            RegionInfo *RI) {
168   assert(R && !R->isTopLevelRegion());
169   assert(!RI || RI == R->getRegionInfo());
170   assert((!RI || DT) &&
171          "RegionInfo requires DominatorTree to be updated as well");
172 
173   simplifyRegionEntry(R, DT, LI, RI);
174   simplifyRegionExit(R, DT, LI, RI);
175   assert(R->isSimple());
176 }
177 
178 // Split the block into two successive blocks.
179 //
180 // Like llvm::SplitBlock, but also preserves RegionInfo
181 static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
182                               DominatorTree *DT, llvm::LoopInfo *LI,
183                               RegionInfo *RI) {
184   assert(Old && SplitPt);
185 
186   // Before:
187   //
188   //  \   /  //
189   //   Old   //
190   //  /   \  //
191 
192   BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
193 
194   if (RI) {
195     Region *R = RI->getRegionFor(Old);
196     RI->setRegionFor(NewBlock, R);
197   }
198 
199   // After:
200   //
201   //   \   /    //
202   //    Old     //
203   //     |      //
204   //  NewBlock  //
205   //   /   \    //
206 
207   return NewBlock;
208 }
209 
210 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
211   // Find first non-alloca instruction. Every basic block has a non-alloc
212   // instruction, as every well formed basic block has a terminator.
213   BasicBlock::iterator I = EntryBlock->begin();
214   while (isa<AllocaInst>(I))
215     ++I;
216 
217   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
218   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
219   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
220   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
221   RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
222   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
223 
224   // splitBlock updates DT, LI and RI.
225   splitBlock(EntryBlock, I, DT, LI, RI);
226 }
227 
228 /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
229 /// instruction but just use it, if it is referenced as a SCEVUnknown. We want
230 /// however to generate new code if the instruction is in the analyzed region
231 /// and we generate code outside/in front of that region. Hence, we generate the
232 /// code for the SDiv/SRem operands in front of the analyzed region and then
233 /// create a new SDiv/SRem operation there too.
234 struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
235   friend struct SCEVVisitor<ScopExpander, const SCEV *>;
236 
237   explicit ScopExpander(const Region &R, ScalarEvolution &SE,
238                         const DataLayout &DL, const char *Name, ValueMapT *VMap)
239       : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
240         VMap(VMap) {}
241 
242   Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
243     // If we generate code in the region we will immediately fall back to the
244     // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
245     // needed replace them by copies computed in the entering block.
246     if (!R.contains(I))
247       E = visit(E);
248     return Expander.expandCodeFor(E, Ty, I);
249   }
250 
251 private:
252   SCEVExpander Expander;
253   ScalarEvolution &SE;
254   const char *Name;
255   const Region &R;
256   ValueMapT *VMap;
257 
258   const SCEV *visitUnknown(const SCEVUnknown *E) {
259 
260     // If a value mapping was given try if the underlying value is remapped.
261     if (VMap)
262       if (Value *NewVal = VMap->lookup(E->getValue()))
263         if (NewVal != E->getValue())
264           return visit(SE.getSCEV(NewVal));
265 
266     Instruction *Inst = dyn_cast<Instruction>(E->getValue());
267     if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
268                   Inst->getOpcode() != Instruction::SDiv))
269       return E;
270 
271     if (!R.contains(Inst))
272       return E;
273 
274     Instruction *StartIP = R.getEnteringBlock()->getTerminator();
275 
276     const SCEV *LHSScev = visit(SE.getSCEV(Inst->getOperand(0)));
277     const SCEV *RHSScev = visit(SE.getSCEV(Inst->getOperand(1)));
278 
279     Value *LHS = Expander.expandCodeFor(LHSScev, E->getType(), StartIP);
280     Value *RHS = Expander.expandCodeFor(RHSScev, E->getType(), StartIP);
281 
282     Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
283                                   LHS, RHS, Inst->getName() + Name, StartIP);
284     return SE.getSCEV(Inst);
285   }
286 
287   /// The following functions will just traverse the SCEV and rebuild it with
288   /// the new operands returned by the traversal.
289   ///
290   ///{
291   const SCEV *visitConstant(const SCEVConstant *E) { return E; }
292   const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
293     return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
294   }
295   const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
296     return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
297   }
298   const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
299     return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
300   }
301   const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
302     return SE.getUDivExpr(visit(E->getLHS()), visit(E->getRHS()));
303   }
304   const SCEV *visitAddExpr(const SCEVAddExpr *E) {
305     SmallVector<const SCEV *, 4> NewOps;
306     for (const SCEV *Op : E->operands())
307       NewOps.push_back(visit(Op));
308     return SE.getAddExpr(NewOps);
309   }
310   const SCEV *visitMulExpr(const SCEVMulExpr *E) {
311     SmallVector<const SCEV *, 4> NewOps;
312     for (const SCEV *Op : E->operands())
313       NewOps.push_back(visit(Op));
314     return SE.getMulExpr(NewOps);
315   }
316   const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
317     SmallVector<const SCEV *, 4> NewOps;
318     for (const SCEV *Op : E->operands())
319       NewOps.push_back(visit(Op));
320     return SE.getUMaxExpr(NewOps);
321   }
322   const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
323     SmallVector<const SCEV *, 4> NewOps;
324     for (const SCEV *Op : E->operands())
325       NewOps.push_back(visit(Op));
326     return SE.getSMaxExpr(NewOps);
327   }
328   const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
329     SmallVector<const SCEV *, 4> NewOps;
330     for (const SCEV *Op : E->operands())
331       NewOps.push_back(visit(Op));
332     return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
333   }
334   ///}
335 };
336 
337 Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
338                             const char *Name, const SCEV *E, Type *Ty,
339                             Instruction *IP, ValueMapT *VMap) {
340   ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap);
341   return Expander.expandCodeFor(E, Ty, IP);
342 }
343 
344 bool polly::isErrorBlock(BasicBlock &BB) {
345 
346   for (Instruction &Inst : BB)
347     if (CallInst *CI = dyn_cast<CallInst>(&Inst))
348       if (Function *F = CI->getCalledFunction())
349         if (F->getName().equals("__ubsan_handle_out_of_bounds"))
350           return true;
351 
352   if (isa<UnreachableInst>(BB.getTerminator()))
353     return true;
354 
355   return false;
356 }
357 
358 Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
359   if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
360     if (BR->isUnconditional())
361       return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
362 
363     return BR->getCondition();
364   }
365 
366   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
367     return SI->getCondition();
368 
369   return nullptr;
370 }
371