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 // Helper function for Scop
29 // TODO: Add assertion to not allow parameter to be null
30 //===----------------------------------------------------------------------===//
31 // Temporary Hack for extended region tree.
32 // Cast the region to loop if there is a loop have the same header and exit.
33 Loop *polly::castToLoop(const Region &R, LoopInfo &LI) {
34   BasicBlock *entry = R.getEntry();
35 
36   if (!LI.isLoopHeader(entry))
37     return 0;
38 
39   Loop *L = LI.getLoopFor(entry);
40 
41   BasicBlock *exit = L->getExitBlock();
42 
43   // Is the loop with multiple exits?
44   if (!exit) return 0;
45 
46   if (exit != R.getExit()) {
47     // SubRegion/ParentRegion with the same entry.
48     assert((R.getNode(R.getEntry())->isSubRegion()
49             || R.getParent()->getEntry() == entry)
50            && "Expect the loop is the smaller or bigger region");
51     return 0;
52   }
53 
54   return L;
55 }
56 
57 Value *polly::getPointerOperand(Instruction &Inst) {
58   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
59     return load->getPointerOperand();
60   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
61     return store->getPointerOperand();
62   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
63     return gep->getPointerOperand();
64 
65   return 0;
66 }
67 
68 //===----------------------------------------------------------------------===//
69 // Helper functions
70 bool polly::isIndVar(const SCEV *Var, Region &RefRegion,
71                      LoopInfo &LI, ScalarEvolution &SE) {
72   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Var);
73 
74   // AddRecExprs are no induction variables.
75   if (!AddRec) return false;
76 
77   Loop *L = const_cast<Loop*>(AddRec->getLoop());
78 
79   // Is the addrec an induction variable of a loop contained in the current
80   // region.
81   if (!RefRegion.contains(L))
82     return false;
83 
84   DEBUG(dbgs() << "Find AddRec: " << *AddRec
85         << " at region: " << RefRegion.getNameStr() << " as indvar\n");
86   return true;
87 }
88 
89 bool polly::isIndVar(const Instruction *I, const LoopInfo *LI) {
90   Loop *L = LI->getLoopFor(I->getParent());
91 
92   return L && I == L->getCanonicalInductionVariable();
93 }
94 
95 bool polly::hasInvokeEdge(const PHINode *PN) {
96   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
97     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
98       if (II->getParent() == PN->getIncomingBlock(i))
99         return true;
100 
101   return false;
102 }
103 
104 BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
105   BasicBlock *BB = R->getExit();
106 
107   SmallVector<BasicBlock*, 4> Preds;
108   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
109     if (R->contains(*PI))
110       Preds.push_back(*PI);
111 
112   return SplitBlockPredecessors(BB, Preds, ".region", P);
113 }
114 
115 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
116   // Find first non-alloca instruction. Every basic block has a non-alloc
117   // instruction, as every well formed basic block has a terminator.
118   BasicBlock::iterator I = EntryBlock->begin();
119   while (isa<AllocaInst>(I)) ++I;
120 
121   // SplitBlock updates DT, DF and LI.
122   BasicBlock *NewEntry = SplitBlock(EntryBlock, I, P);
123   if (RegionInfo *RI = P->getAnalysisIfAvailable<RegionInfo>())
124     RI->splitBlock(NewEntry, EntryBlock);
125 }
126