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