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