1 //===---- CodePreparation.cpp - Code preparation for Scop Detection -------===//
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 // The Polly code preparation pass is executed before SCoP detection. Its only
11 // use is to translate all PHI nodes that can not be expressed by the code
12 // generator into explicit memory dependences. Depending of the code generation
13 // strategy different PHI nodes are translated:
14 //
15 // - indvars based code generation:
16 //
17 // The indvars based code generation requires explicit canonical induction
18 // variables. Such variables are generated before scop detection and
19 // also before the code preparation pass. All PHI nodes that are not canonical
20 // induction variables are not supported by the indvars based code generation
21 // and are consequently translated into explicit memory accesses.
22 //
23 // - scev based code generation:
24 //
25 // The scev based code generation can code generate all PHI nodes that do not
26 // reference parameters within the scop. As the code preparation pass is run
27 // before scop detection, we can not check this condition, because without
28 // a detected scop, we do not know SCEVUnknowns that appear in the SCEV of
29 // a PHI node may later be within or outside of the SCoP. Hence, we follow a
30 // heuristic and translate all PHI nodes that are either directly SCEVUnknown
31 // or SCEVCouldNotCompute. This will hopefully get most of the PHI nodes that
32 // are introduced due to conditional control flow, but not the ones that are
33 // referencing loop counters.
34 //
35 // XXX: In the future, we should remove the need for this pass entirely and
36 // instead add support for scalar dependences to ScopInfo and code generation.
37 //
38 //===----------------------------------------------------------------------===//
39 
40 #include "polly/LinkAllPasses.h"
41 #include "polly/CodeGen/BlockGenerators.h"
42 #include "polly/Support/ScopHelper.h"
43 #include "llvm/Analysis/DominanceFrontier.h"
44 #include "llvm/Analysis/LoopInfo.h"
45 #include "llvm/Analysis/RegionInfo.h"
46 #include "llvm/Analysis/ScalarEvolution.h"
47 #include "llvm/Transforms/Utils/Local.h"
48 
49 using namespace llvm;
50 using namespace polly;
51 
52 namespace {
53 
54 // Helper function which (for a given PHI node):
55 //
56 // 1) Remembers all incoming values and the associated basic blocks
57 // 2) Demotes the phi node to the stack
58 // 3) Remembers the correlation between the PHI node and the new alloca
59 //
60 // When we combine the information from 1) and 3) we know the values stored
61 // in this alloca at the end of the predecessor basic blocks of the PHI.
62 static void DemotePHI(
63     PHINode *PN, DenseMap<PHINode *, AllocaInst *> &PNallocMap,
64     DenseMap<std::pair<Value *, BasicBlock *>, PHINode *> &ValueLocToPhiMap) {
65 
66   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
67     auto *InVal = PN->getIncomingValue(i);
68     auto *InBB = PN->getIncomingBlock(i);
69     ValueLocToPhiMap[std::make_pair(InVal, InBB)] = PN;
70   }
71 
72   PNallocMap[PN] = DemotePHIToStack(PN);
73 }
74 
75 /// @brief Prepare the IR for the scop detection.
76 ///
77 class CodePreparation : public FunctionPass {
78   CodePreparation(const CodePreparation &) LLVM_DELETED_FUNCTION;
79   const CodePreparation &
80   operator=(const CodePreparation &) LLVM_DELETED_FUNCTION;
81 
82   LoopInfo *LI;
83   ScalarEvolution *SE;
84 
85   void clear();
86 
87   bool eliminatePHINodes(Function &F);
88 
89 public:
90   static char ID;
91 
92   explicit CodePreparation() : FunctionPass(ID) {}
93   ~CodePreparation();
94 
95   /// @name FunctionPass interface.
96   //@{
97   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
98   virtual void releaseMemory();
99   virtual bool runOnFunction(Function &F);
100   virtual void print(raw_ostream &OS, const Module *) const;
101   //@}
102 };
103 }
104 
105 void CodePreparation::clear() {}
106 
107 CodePreparation::~CodePreparation() { clear(); }
108 
109 bool CodePreparation::eliminatePHINodes(Function &F) {
110   // The PHINodes that will be demoted.
111   std::vector<PHINode *> PNtoDemote;
112   // The PHINodes that will be deleted (stack slot sharing).
113   std::vector<PHINode *> PNtoDelete;
114   // The PHINodes that will be preserved.
115   std::vector<PHINode *> PNtoPreserve;
116   // Map to remember values stored in PHINodes at the end of basic blocks.
117   DenseMap<std::pair<Value *, BasicBlock *>, PHINode *> ValueLocToPhiMap;
118   // Map from PHINodes to their alloca (after demotion) counterpart.
119   DenseMap<PHINode *, AllocaInst *> PNallocMap;
120 
121   // Scan the PHINodes in this function and categorize them to be either:
122   // o Preserved, if they are (canonical) induction variables or can be
123   //              synthesized during code generation ('SCEVable')
124   // o Deleted, if they are trivial PHI nodes (one incoming value) and the
125   //            incoming value is a PHI node we will demote
126   // o Demoted, if they do not fit any of the previous categories
127   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI)
128     for (BasicBlock::iterator II = BI->begin(), IE = BI->getFirstNonPHI();
129          II != IE; ++II) {
130       PHINode *PN = cast<PHINode>(II);
131       if (SCEVCodegen) {
132         if (SE->isSCEVable(PN->getType())) {
133           const SCEV *S = SE->getSCEV(PN);
134           if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) {
135             PNtoPreserve.push_back(PN);
136             continue;
137           }
138         }
139       } else {
140         if (Loop *L = LI->getLoopFor(BI)) {
141           // Induction variables will be preserved.
142           if (L->getCanonicalInductionVariable() == PN) {
143             PNtoPreserve.push_back(PN);
144             continue;
145           }
146         }
147       }
148 
149       // As DemotePHIToStack does not support invoke edges, we preserve
150       // PHINodes that have invoke edges.
151       if (hasInvokeEdge(PN)) {
152         PNtoPreserve.push_back(PN);
153       } else {
154         if (PN->getNumIncomingValues() == 1)
155           PNtoDelete.push_back(PN);
156         else
157           PNtoDemote.push_back(PN);
158       }
159     }
160 
161   if (PNtoDemote.empty() && PNtoDelete.empty())
162     return false;
163 
164   while (!PNtoDemote.empty()) {
165     PHINode *PN = PNtoDemote.back();
166     PNtoDemote.pop_back();
167     DemotePHI(PN, PNallocMap, ValueLocToPhiMap);
168   }
169 
170   // For each trivial PHI we encountered (and we want to delete) we try to find
171   // the value it will hold in a alloca we already created by PHI demotion. If
172   // we succeed (the incoming value is stored in an alloca at the predecessor
173   // block), we can replace the trivial PHI by the value stored in the alloca.
174   // If not, we will demote this trivial PHI as any other one.
175   for (auto PNIt = PNtoDelete.rbegin(), PNEnd = PNtoDelete.rend();
176        PNIt != PNEnd; ++PNIt) {
177     PHINode *TrivPN = *PNIt;
178     assert(TrivPN->getNumIncomingValues() == 1 && "Assumed trivial PHI");
179 
180     auto *InVal = TrivPN->getIncomingValue(0);
181     auto *InBB = TrivPN->getIncomingBlock(0);
182     const auto &ValLocIt = ValueLocToPhiMap.find(std::make_pair(InVal, InBB));
183     if (ValLocIt != ValueLocToPhiMap.end()) {
184       PHINode *InPHI = ValLocIt->second;
185       assert(PNallocMap.count(InPHI) &&
186              "Inconsitent state, PN was not demoted!");
187       auto *InPHIAlloca = PNallocMap[InPHI];
188       PNallocMap[TrivPN] = InPHIAlloca;
189       LoadInst *LI = new LoadInst(InPHIAlloca, "",
190                                   TrivPN->getParent()->getFirstInsertionPt());
191       TrivPN->replaceAllUsesWith(LI);
192       TrivPN->eraseFromParent();
193       continue;
194     }
195 
196     DemotePHI(TrivPN, PNallocMap, ValueLocToPhiMap);
197   }
198 
199   // Move preserved PHINodes to the beginning of the BasicBlock.
200   while (!PNtoPreserve.empty()) {
201     PHINode *PN = PNtoPreserve.back();
202     PNtoPreserve.pop_back();
203 
204     BasicBlock *BB = PN->getParent();
205     if (PN == BB->begin())
206       continue;
207 
208     PN->moveBefore(BB->begin());
209   }
210 
211   return true;
212 }
213 
214 void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
215   AU.addRequired<LoopInfo>();
216   AU.addRequired<ScalarEvolution>();
217 
218   AU.addPreserved<LoopInfo>();
219   AU.addPreserved<RegionInfoPass>();
220   AU.addPreserved<DominatorTreeWrapperPass>();
221   AU.addPreserved<DominanceFrontier>();
222 }
223 
224 bool CodePreparation::runOnFunction(Function &F) {
225   LI = &getAnalysis<LoopInfo>();
226   SE = &getAnalysis<ScalarEvolution>();
227 
228   splitEntryBlockForAlloca(&F.getEntryBlock(), this);
229 
230   eliminatePHINodes(F);
231 
232   return false;
233 }
234 
235 void CodePreparation::releaseMemory() { clear(); }
236 
237 void CodePreparation::print(raw_ostream &OS, const Module *) const {}
238 
239 char CodePreparation::ID = 0;
240 char &polly::CodePreparationID = CodePreparation::ID;
241 
242 Pass *polly::createCodePreparationPass() { return new CodePreparation(); }
243 
244 INITIALIZE_PASS_BEGIN(CodePreparation, "polly-prepare",
245                       "Polly - Prepare code for polly", false, false)
246 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
247 INITIALIZE_PASS_END(CodePreparation, "polly-prepare",
248                     "Polly - Prepare code for polly", false, false)
249