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