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/LoopInfo.h"
17 #include "llvm/Analysis/RegionInfo.h"
18 #include "llvm/Analysis/ScalarEvolution.h"
19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "polly-scop-helper"
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)
45     return 0;
46 
47   if (exit != R.getExit()) {
48     // SubRegion/ParentRegion with the same entry.
49     assert((R.getNode(R.getEntry())->isSubRegion() ||
50             R.getParent()->getEntry() == entry) &&
51            "Expect the loop is the smaller or bigger region");
52     return 0;
53   }
54 
55   return L;
56 }
57 
58 Value *polly::getPointerOperand(Instruction &Inst) {
59   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
60     return load->getPointerOperand();
61   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
62     return store->getPointerOperand();
63   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
64     return gep->getPointerOperand();
65 
66   return 0;
67 }
68 
69 bool polly::hasInvokeEdge(const PHINode *PN) {
70   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
71     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
72       if (II->getParent() == PN->getIncomingBlock(i))
73         return true;
74 
75   return false;
76 }
77 
78 BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
79   BasicBlock *BB = R->getExit();
80 
81   SmallVector<BasicBlock *, 4> Preds;
82   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
83     if (R->contains(*PI))
84       Preds.push_back(*PI);
85 
86   return SplitBlockPredecessors(BB, Preds, ".region", P);
87 }
88 
89 static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
90                                       BasicBlock *NewEntry) {
91   for (polly::ScopStmt *Stmt : *S)
92     if (Stmt->getBasicBlock() == OldEntry) {
93       Stmt->setBasicBlock(NewEntry);
94       break;
95     }
96 
97   S->getRegion().replaceEntryRecursive(NewEntry);
98 }
99 
100 BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
101   Region *R = &S->getRegion();
102 
103   // The entering block for the region.
104   BasicBlock *EnteringBB = R->getEnteringBlock();
105   BasicBlock *OldEntry = R->getEntry();
106   BasicBlock *NewEntry = nullptr;
107 
108   // Create single entry edge if the region has multiple entry edges.
109   if (!EnteringBB) {
110     NewEntry = SplitBlock(OldEntry, OldEntry->begin(), P);
111     EnteringBB = OldEntry;
112   }
113 
114   // Create an unconditional entry edge.
115   if (EnteringBB->getTerminator()->getNumSuccessors() != 1) {
116     BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry;
117     BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, P);
118 
119     // Once the edge between EnteringBB and EntryBB is split, two cases arise.
120     // The first is simple. The new block is inserted between EnteringBB and
121     // EntryBB. In this case no further action is needed. However it might
122     // happen (if the splitted edge is not critical) that the new block is
123     // inserted __after__ EntryBB causing the following situation:
124     //
125     // EnteringBB
126     //    _|_
127     //    | |
128     //    |  \-> some_other_BB_not_in_R
129     //    V
130     // EntryBB
131     //    |
132     //    V
133     // SplitEdgeBB
134     //
135     // In this case we need to swap the role of EntryBB and SplitEdgeBB.
136 
137     // Check which case SplitEdge produced:
138     if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) {
139       // First (simple) case.
140       EnteringBB = SplitEdgeBB;
141     } else {
142       // Second (complicated) case.
143       NewEntry = SplitEdgeBB;
144       EnteringBB = EntryBB;
145     }
146 
147     EnteringBB->setName("polly.entering.block");
148   }
149 
150   if (NewEntry)
151     replaceScopAndRegionEntry(S, OldEntry, NewEntry);
152 
153   // Create single exit edge if the region has multiple exit edges.
154   if (!R->getExitingBlock()) {
155     BasicBlock *NewExit = createSingleExitEdge(R, P);
156 
157     for (auto &&SubRegion : *R)
158       SubRegion->replaceExitRecursive(NewExit);
159   }
160 
161   return EnteringBB;
162 }
163 
164 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
165   // Find first non-alloca instruction. Every basic block has a non-alloc
166   // instruction, as every well formed basic block has a terminator.
167   BasicBlock::iterator I = EntryBlock->begin();
168   while (isa<AllocaInst>(I))
169     ++I;
170 
171   // SplitBlock updates DT, DF and LI.
172   BasicBlock *NewEntry = SplitBlock(EntryBlock, I, P);
173   if (RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>())
174     RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock);
175 }
176