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 
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/Analysis/RegionInfo.h"
18 #include "llvm/Analysis/ScalarEvolution.h"
19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
20 #include "llvm/Support/CFG.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 
23 #define DEBUG_TYPE "polly-scop-helper"
24 #include "llvm/Support/Debug.h"
25 
26 using namespace llvm;
27 
28 
29 namespace {
30 // Checks if a SCEV is invariant in a region. This is if all Values are
31 // referenced in this SCEV are defined outside the region.
32 class InvariantChecker: SCEVVisitor<InvariantChecker, bool> {
33   Region &R;
34 
35 public:
36   bool visitConstant(const SCEVConstant *S) {
37     return true;
38   }
39 
40   bool visitUnknown(const SCEVUnknown* S) {
41     Value *V = S->getValue();
42 
43     // An Instruction defined outside the region is invariant.
44     if (Instruction *I = dyn_cast<Instruction>(V))
45       return !R.contains(I);
46 
47     // A constant is invariant.
48     return true;
49   }
50 
51   bool visitNAryExpr(const SCEVNAryExpr *S) {
52     for (SCEVNAryExpr::op_iterator OI = S->op_begin(), OE = S->op_end();
53          OI != OE; ++OI)
54       if (!visit(*OI))
55         return false;
56 
57     return true;
58   }
59 
60   bool visitMulExpr(const SCEVMulExpr* S) {
61     return visitNAryExpr(S);
62   }
63 
64   bool visitCastExpr(const SCEVCastExpr *S) {
65     return visit(S->getOperand());
66   }
67 
68   bool visitTruncateExpr(const SCEVTruncateExpr *S) {
69     return visit(S->getOperand());
70   }
71 
72   bool visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
73     return visit(S->getOperand());
74   }
75 
76   bool visitSignExtendExpr(const SCEVSignExtendExpr *S) {
77     return visit(S->getOperand());
78   }
79 
80   bool visitAddExpr(const SCEVAddExpr *S) {
81     return visitNAryExpr(S);
82   }
83 
84   bool visitAddRecExpr(const SCEVAddRecExpr *S) {
85     // Check if the addrec is contained in the region.
86     if (R.contains(S->getLoop()))
87       return false;
88 
89     return visitNAryExpr(S);
90   }
91 
92   bool visitUDivExpr(const SCEVUDivExpr *S) {
93     return visit(S->getLHS()) && visit(S->getRHS());
94   }
95 
96   bool visitSMaxExpr(const SCEVSMaxExpr *S) {
97     return visitNAryExpr(S);
98   }
99 
100   bool visitUMaxExpr(const SCEVUMaxExpr *S) {
101     return visitNAryExpr(S);
102   }
103 
104   bool visitCouldNotCompute(const SCEVCouldNotCompute *S) {
105     llvm_unreachable("SCEV cannot be checked");
106   }
107 
108   InvariantChecker(Region &RefRegion)
109     : R(RefRegion) {}
110 
111   static bool isInvariantInRegion(const SCEV *S, Region &R) {
112     InvariantChecker Checker(R);
113     return Checker.visit(S);
114   }
115 };
116 }
117 
118 // Helper function for Scop
119 // TODO: Add assertion to not allow parameter to be null
120 //===----------------------------------------------------------------------===//
121 // Temporary Hack for extended region tree.
122 // Cast the region to loop if there is a loop have the same header and exit.
123 Loop *polly::castToLoop(const Region &R, LoopInfo &LI) {
124   BasicBlock *entry = R.getEntry();
125 
126   if (!LI.isLoopHeader(entry))
127     return 0;
128 
129   Loop *L = LI.getLoopFor(entry);
130 
131   BasicBlock *exit = L->getExitBlock();
132 
133   // Is the loop with multiple exits?
134   if (!exit) return 0;
135 
136   if (exit != R.getExit()) {
137     // SubRegion/ParentRegion with the same entry.
138     assert((R.getNode(R.getEntry())->isSubRegion()
139             || R.getParent()->getEntry() == entry)
140            && "Expect the loop is the smaller or bigger region");
141     return 0;
142   }
143 
144   return L;
145 }
146 
147 Value *polly::getPointerOperand(Instruction &Inst) {
148   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
149     return load->getPointerOperand();
150   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
151     return store->getPointerOperand();
152   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
153     return gep->getPointerOperand();
154 
155   return 0;
156 }
157 
158 //===----------------------------------------------------------------------===//
159 // Helper functions
160 
161 bool polly::isInvariant(const SCEV *S, Region &R) {
162   return InvariantChecker::isInvariantInRegion(S, R);
163 }
164 
165 // Helper function to check parameter
166 bool polly::isParameter(const SCEV *Var, Region &RefRegion,
167                         LoopInfo &LI, ScalarEvolution &SE) {
168   assert(Var && "Var can not be null!");
169 
170   if (!isInvariant(Var, RefRegion))
171     return false;
172 
173   if (isa<SCEVAddRecExpr>(Var))
174     return true;
175 
176   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Var)) {
177     if (isa<PHINode>(U->getValue()))
178       return false;
179 
180     if(isa<UndefValue>(U->getValue()))
181       return false;
182 
183     return true;
184   }
185 
186   if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(Var))
187     return isParameter(Cast->getOperand(), RefRegion, LI, SE);
188 
189   return false;
190 }
191 
192 bool polly::isIndVar(const SCEV *Var, Region &RefRegion,
193                      LoopInfo &LI, ScalarEvolution &SE) {
194   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Var);
195 
196   // AddRecExprs are no induction variables.
197   if (!AddRec) return false;
198 
199   Loop *L = const_cast<Loop*>(AddRec->getLoop());
200 
201   // Is the addrec an induction variable of a loop contained in the current
202   // region.
203   if (!RefRegion.contains(L))
204     return false;
205 
206   DEBUG(dbgs() << "Find AddRec: " << *AddRec
207         << " at region: " << RefRegion.getNameStr() << " as indvar\n");
208   return true;
209 }
210 
211 bool polly::isIndVar(const Instruction *I, const LoopInfo *LI) {
212   Loop *L = LI->getLoopFor(I->getParent());
213 
214   return L && I == L->getCanonicalInductionVariable();
215 }
216 
217 bool polly::hasInvokeEdge(const PHINode *PN) {
218   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
219     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
220       if (II->getParent() == PN->getIncomingBlock(i))
221         return true;
222 
223   return false;
224 }
225 
226 BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
227   BasicBlock *BB = R->getExit();
228 
229   SmallVector<BasicBlock*, 4> Preds;
230   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
231     if (R->contains(*PI))
232       Preds.push_back(*PI);
233 
234   return SplitBlockPredecessors(BB, Preds.data(), Preds.size(), ".region", P);
235 }
236 
237 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
238   // Find first non-alloca instruction. Every basic block has a non-alloc
239   // instruction, as every well formed basic block has a terminator.
240   BasicBlock::iterator I = EntryBlock->begin();
241   while (isa<AllocaInst>(I)) ++I;
242 
243   // SplitBlock updates DT, DF and LI.
244   BasicBlock *NewEntry = SplitBlock(EntryBlock, I, P);
245   if (RegionInfo *RI = P->getAnalysisIfAvailable<RegionInfo>())
246     RI->splitBlock(NewEntry, EntryBlock);
247 }
248