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