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/ScalarEvolutionExpressions.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "polly-scop-helper"
28 
29 // Helper function for Scop
30 // TODO: Add assertion to not allow parameter to be null
31 //===----------------------------------------------------------------------===//
32 // Temporary Hack for extended region tree.
33 // Cast the region to loop if there is a loop have the same header and exit.
34 Loop *polly::castToLoop(const Region &R, LoopInfo &LI) {
35   BasicBlock *entry = R.getEntry();
36 
37   if (!LI.isLoopHeader(entry))
38     return 0;
39 
40   Loop *L = LI.getLoopFor(entry);
41 
42   BasicBlock *exit = L->getExitBlock();
43 
44   // Is the loop with multiple exits?
45   if (!exit)
46     return 0;
47 
48   if (exit != R.getExit()) {
49     // SubRegion/ParentRegion with the same entry.
50     assert((R.getNode(R.getEntry())->isSubRegion() ||
51             R.getParent()->getEntry() == entry) &&
52            "Expect the loop is the smaller or bigger region");
53     return 0;
54   }
55 
56   return L;
57 }
58 
59 Value *polly::getPointerOperand(Instruction &Inst) {
60   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
61     return load->getPointerOperand();
62   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
63     return store->getPointerOperand();
64   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
65     return gep->getPointerOperand();
66 
67   return 0;
68 }
69 
70 bool polly::hasInvokeEdge(const PHINode *PN) {
71   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
72     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
73       if (II->getParent() == PN->getIncomingBlock(i))
74         return true;
75 
76   return false;
77 }
78 
79 // Ensures that there is just one predecessor to the entry node from outside the
80 // region.
81 // The identity of the region entry node is preserved.
82 static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
83                                 RegionInfo *RI) {
84   BasicBlock *EnteringBB = R->getEnteringBlock();
85   BasicBlock *Entry = R->getEntry();
86 
87   // Before (one of):
88   //
89   //                       \    /            //
90   //                      EnteringBB         //
91   //                        |    \------>    //
92   //   \   /                |                //
93   //   Entry <--\         Entry <--\         //
94   //   /   \    /         /   \    /         //
95   //        ....               ....          //
96 
97   // Create single entry edge if the region has multiple entry edges.
98   if (!EnteringBB) {
99     SmallVector<BasicBlock *, 4> Preds;
100     for (BasicBlock *P : predecessors(Entry))
101       if (!R->contains(P))
102         Preds.push_back(P);
103 
104     BasicBlock *NewEntering =
105         SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
106 
107     if (RI) {
108       // The exit block of predecessing regions must be changed to NewEntering
109       for (BasicBlock *ExitPred : predecessors(NewEntering)) {
110         Region *RegionOfPred = RI->getRegionFor(ExitPred);
111         if (RegionOfPred->getExit() != Entry)
112           continue;
113 
114         while (!RegionOfPred->isTopLevelRegion() &&
115                RegionOfPred->getExit() == Entry) {
116           RegionOfPred->replaceExit(NewEntering);
117           RegionOfPred = RegionOfPred->getParent();
118         }
119       }
120 
121       // Make all ancestors use EnteringBB as entry; there might be edges to it
122       Region *AncestorR = R->getParent();
123       RI->setRegionFor(NewEntering, AncestorR);
124       while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) {
125         AncestorR->replaceEntry(NewEntering);
126         AncestorR = AncestorR->getParent();
127       }
128     }
129 
130     EnteringBB = NewEntering;
131   }
132   assert(R->getEnteringBlock() == EnteringBB);
133 
134   // After:
135   //
136   //    \    /       //
137   //  EnteringBB     //
138   //      |          //
139   //      |          //
140   //    Entry <--\   //
141   //    /   \    /   //
142   //         ....    //
143 }
144 
145 // Ensure that the region has a single block that branches to the exit node.
146 static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
147                                RegionInfo *RI) {
148   BasicBlock *ExitBB = R->getExit();
149   BasicBlock *ExitingBB = R->getExitingBlock();
150 
151   // Before:
152   //
153   //   (Region)   ______/  //
154   //      \  |   /         //
155   //       ExitBB          //
156   //       /    \          //
157 
158   if (!ExitingBB) {
159     SmallVector<BasicBlock *, 4> Preds;
160     for (BasicBlock *P : predecessors(ExitBB))
161       if (R->contains(P))
162         Preds.push_back(P);
163 
164     //  Preds[0] Preds[1]      otherBB //
165     //         \  |  ________/         //
166     //          \ | /                  //
167     //           BB                    //
168     ExitingBB =
169         SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
170     // Preds[0] Preds[1]      otherBB  //
171     //        \  /           /         //
172     // BB.region_exiting    /          //
173     //                  \  /           //
174     //                   BB            //
175 
176     if (RI)
177       RI->setRegionFor(ExitingBB, R);
178 
179     // Change the exit of nested regions, but not the region itself,
180     R->replaceExitRecursive(ExitingBB);
181     R->replaceExit(ExitBB);
182   }
183   assert(ExitingBB == R->getExitingBlock());
184 
185   // After:
186   //
187   //     \   /                //
188   //    ExitingBB     _____/  //
189   //          \      /        //
190   //           ExitBB         //
191   //           /    \         //
192 }
193 
194 void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
195                            RegionInfo *RI) {
196   assert(R && !R->isTopLevelRegion());
197   assert(!RI || RI == R->getRegionInfo());
198   assert((!RI || DT) &&
199          "RegionInfo requires DominatorTree to be updated as well");
200 
201   simplifyRegionEntry(R, DT, LI, RI);
202   simplifyRegionExit(R, DT, LI, RI);
203   assert(R->isSimple());
204 }
205 
206 // Split the block into two successive blocks.
207 //
208 // Like llvm::SplitBlock, but also preserves RegionInfo
209 static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
210                               DominatorTree *DT, llvm::LoopInfo *LI,
211                               RegionInfo *RI) {
212   assert(Old && SplitPt);
213 
214   // Before:
215   //
216   //  \   /  //
217   //   Old   //
218   //  /   \  //
219 
220   BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
221 
222   if (RI) {
223     Region *R = RI->getRegionFor(Old);
224     RI->setRegionFor(NewBlock, R);
225   }
226 
227   // After:
228   //
229   //   \   /    //
230   //    Old     //
231   //     |      //
232   //  NewBlock  //
233   //   /   \    //
234 
235   return NewBlock;
236 }
237 
238 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
239   // Find first non-alloca instruction. Every basic block has a non-alloc
240   // instruction, as every well formed basic block has a terminator.
241   BasicBlock::iterator I = EntryBlock->begin();
242   while (isa<AllocaInst>(I))
243     ++I;
244 
245   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
246   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
247   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
248   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
249   RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
250   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
251 
252   // splitBlock updates DT, LI and RI.
253   splitBlock(EntryBlock, I, DT, LI, RI);
254 }
255