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 /// @brief Prepare the IR for the scop detection.
53 ///
54 class CodePreparation : public FunctionPass {
55   CodePreparation(const CodePreparation &) LLVM_DELETED_FUNCTION;
56   const CodePreparation &
57   operator=(const CodePreparation &) LLVM_DELETED_FUNCTION;
58 
59   LoopInfo *LI;
60   ScalarEvolution *SE;
61 
62   void clear();
63 
64   bool eliminatePHINodes(Function &F);
65 
66 public:
67   static char ID;
68 
69   explicit CodePreparation() : FunctionPass(ID) {}
70   ~CodePreparation();
71 
72   /// @name FunctionPass interface.
73   //@{
74   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
75   virtual void releaseMemory();
76   virtual bool runOnFunction(Function &F);
77   virtual void print(raw_ostream &OS, const Module *) const;
78   //@}
79 };
80 }
81 
82 void CodePreparation::clear() {}
83 
84 CodePreparation::~CodePreparation() { clear(); }
85 
86 bool CodePreparation::eliminatePHINodes(Function &F) {
87   // The PHINodes that will be deleted.
88   std::vector<PHINode *> PNtoDelete;
89   // The PHINodes that will be preserved.
90   std::vector<PHINode *> PreservedPNs;
91 
92   // Scan the PHINodes in this function.
93   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI)
94     for (BasicBlock::iterator II = BI->begin(), IE = BI->getFirstNonPHI();
95          II != IE; ++II) {
96       PHINode *PN = cast<PHINode>(II);
97       if (SCEVCodegen) {
98         if (SE->isSCEVable(PN->getType())) {
99           const SCEV *S = SE->getSCEV(PN);
100           if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) {
101             PreservedPNs.push_back(PN);
102             continue;
103           }
104         }
105       } else {
106         if (Loop *L = LI->getLoopFor(BI)) {
107           // Induction variables will be preserved.
108           if (L->getCanonicalInductionVariable() == PN) {
109             PreservedPNs.push_back(PN);
110             continue;
111           }
112         }
113       }
114 
115       // As DemotePHIToStack does not support invoke edges, we preserve
116       // PHINodes that have invoke edges.
117       if (hasInvokeEdge(PN))
118         PreservedPNs.push_back(PN);
119       else
120         PNtoDelete.push_back(PN);
121     }
122 
123   if (PNtoDelete.empty())
124     return false;
125 
126   while (!PNtoDelete.empty()) {
127     PHINode *PN = PNtoDelete.back();
128     PNtoDelete.pop_back();
129 
130     DemotePHIToStack(PN);
131   }
132 
133   // Move preserved PHINodes to the beginning of the BasicBlock.
134   while (!PreservedPNs.empty()) {
135     PHINode *PN = PreservedPNs.back();
136     PreservedPNs.pop_back();
137 
138     BasicBlock *BB = PN->getParent();
139     if (PN == BB->begin())
140       continue;
141 
142     PN->moveBefore(BB->begin());
143   }
144 
145   return true;
146 }
147 
148 void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
149   AU.addRequired<LoopInfo>();
150   AU.addRequired<ScalarEvolution>();
151 
152   AU.addPreserved<LoopInfo>();
153   AU.addPreserved<RegionInfo>();
154   AU.addPreserved<DominatorTreeWrapperPass>();
155   AU.addPreserved<DominanceFrontier>();
156 }
157 
158 bool CodePreparation::runOnFunction(Function &F) {
159   LI = &getAnalysis<LoopInfo>();
160   SE = &getAnalysis<ScalarEvolution>();
161 
162   splitEntryBlockForAlloca(&F.getEntryBlock(), this);
163 
164   eliminatePHINodes(F);
165 
166   return false;
167 }
168 
169 void CodePreparation::releaseMemory() { clear(); }
170 
171 void CodePreparation::print(raw_ostream &OS, const Module *) const {}
172 
173 char CodePreparation::ID = 0;
174 char &polly::CodePreparationID = CodePreparation::ID;
175 
176 Pass *polly::createCodePreparationPass() { return new CodePreparation(); }
177 
178 INITIALIZE_PASS_BEGIN(CodePreparation, "polly-prepare",
179                       "Polly - Prepare code for polly", false, false)
180 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
181 INITIALIZE_PASS_END(CodePreparation, "polly-prepare",
182                     "Polly - Prepare code for polly", false, false)
183