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 Type *polly::getAccessInstType(Instruction *AccInst) {
71   if (StoreInst *Store = dyn_cast<StoreInst>(AccInst))
72     return Store->getValueOperand()->getType();
73   if (BranchInst *Branch = dyn_cast<BranchInst>(AccInst))
74     return Branch->getCondition()->getType();
75   return AccInst->getType();
76 }
77 
78 bool polly::hasInvokeEdge(const PHINode *PN) {
79   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
80     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
81       if (II->getParent() == PN->getIncomingBlock(i))
82         return true;
83 
84   return false;
85 }
86 
87 BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
88   BasicBlock *BB = R->getExit();
89 
90   SmallVector<BasicBlock *, 4> Preds;
91   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
92     if (R->contains(*PI))
93       Preds.push_back(*PI);
94 
95   auto *AA = P->getAnalysisIfAvailable<AliasAnalysis>();
96   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
97   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
98   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
99   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
100 
101   return SplitBlockPredecessors(BB, Preds, ".region", AA, DT, LI);
102 }
103 
104 static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
105                                       BasicBlock *NewEntry) {
106   if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry))
107     Stmt->setBasicBlock(NewEntry);
108 
109   S->getRegion().replaceEntryRecursive(NewEntry);
110 }
111 
112 BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
113   Region *R = &S->getRegion();
114 
115   // The entering block for the region.
116   BasicBlock *EnteringBB = R->getEnteringBlock();
117   BasicBlock *OldEntry = R->getEntry();
118   BasicBlock *NewEntry = nullptr;
119 
120   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
121   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
122   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
123   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
124 
125   // Create single entry edge if the region has multiple entry edges.
126   if (!EnteringBB) {
127     NewEntry = SplitBlock(OldEntry, OldEntry->begin(), DT, LI);
128     EnteringBB = OldEntry;
129   }
130 
131   // Create an unconditional entry edge.
132   if (EnteringBB->getTerminator()->getNumSuccessors() != 1) {
133     BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry;
134     BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, DT, LI);
135 
136     // Once the edge between EnteringBB and EntryBB is split, two cases arise.
137     // The first is simple. The new block is inserted between EnteringBB and
138     // EntryBB. In this case no further action is needed. However it might
139     // happen (if the splitted edge is not critical) that the new block is
140     // inserted __after__ EntryBB causing the following situation:
141     //
142     // EnteringBB
143     //    _|_
144     //    | |
145     //    |  \-> some_other_BB_not_in_R
146     //    V
147     // EntryBB
148     //    |
149     //    V
150     // SplitEdgeBB
151     //
152     // In this case we need to swap the role of EntryBB and SplitEdgeBB.
153 
154     // Check which case SplitEdge produced:
155     if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) {
156       // First (simple) case.
157       EnteringBB = SplitEdgeBB;
158     } else {
159       // Second (complicated) case.
160       NewEntry = SplitEdgeBB;
161       EnteringBB = EntryBB;
162     }
163 
164     EnteringBB->setName("polly.entering.block");
165   }
166 
167   if (NewEntry)
168     replaceScopAndRegionEntry(S, OldEntry, NewEntry);
169 
170   // Create single exit edge if the region has multiple exit edges.
171   if (!R->getExitingBlock()) {
172     BasicBlock *NewExiting = createSingleExitEdge(R, P);
173     (void)NewExiting;
174     assert(NewExiting == R->getExitingBlock() &&
175            "Did not create a single exiting block");
176   }
177 
178   return EnteringBB;
179 }
180 
181 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
182   // Find first non-alloca instruction. Every basic block has a non-alloc
183   // instruction, as every well formed basic block has a terminator.
184   BasicBlock::iterator I = EntryBlock->begin();
185   while (isa<AllocaInst>(I))
186     ++I;
187 
188   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
189   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
190   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
191   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
192 
193   // SplitBlock updates DT, DF and LI.
194   BasicBlock *NewEntry = SplitBlock(EntryBlock, I, DT, LI);
195   if (RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>())
196     RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock);
197 }
198