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