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
11 // currently only splits the entry block of the SCoP to make room for alloc
12 // instructions as they are generated during code generation.
13 //
14 // XXX: In the future, we should remove the need for this pass entirely and
15 // instead add this spitting to the code generation pass.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "polly/CodePreparation.h"
20 #include "polly/LinkAllPasses.h"
21 #include "polly/ScopDetection.h"
22 #include "polly/Support/ScopHelper.h"
23 #include "llvm/Analysis/DominanceFrontier.h"
24 #include "llvm/Analysis/LoopInfo.h"
25 #include "llvm/Analysis/RegionInfo.h"
26 #include "llvm/Analysis/ScalarEvolution.h"
27 #include "llvm/Transforms/Utils/Local.h"
28 
29 using namespace llvm;
30 using namespace polly;
31 
32 namespace {
33 
34 /// Prepare the IR for the scop detection.
35 ///
36 class CodePreparation : public FunctionPass {
37   CodePreparation(const CodePreparation &) = delete;
38   const CodePreparation &operator=(const CodePreparation &) = delete;
39 
40   LoopInfo *LI;
41   ScalarEvolution *SE;
42 
43   void clear();
44 
45 public:
46   static char ID;
47 
48   explicit CodePreparation() : FunctionPass(ID) {}
49   ~CodePreparation();
50 
51   /// @name FunctionPass interface.
52   //@{
53   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
54   virtual void releaseMemory();
55   virtual bool runOnFunction(Function &F);
56   virtual void print(raw_ostream &OS, const Module *) const;
57   //@}
58 };
59 } // namespace
60 
61 PreservedAnalyses CodePreparationPass::run(Function &F,
62                                            FunctionAnalysisManager &FAM) {
63 
64   // Find first non-alloca instruction. Every basic block has a non-alloca
65   // instruction, as every well formed basic block has a terminator.
66   auto &EntryBlock = F.getEntryBlock();
67   BasicBlock::iterator I = EntryBlock.begin();
68   while (isa<AllocaInst>(I))
69     ++I;
70 
71   auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
72   auto &LI = FAM.getResult<LoopAnalysis>(F);
73 
74   // splitBlock updates DT, LI and RI.
75   splitEntryBlockForAlloca(&EntryBlock, &DT, &LI, nullptr);
76 
77   PreservedAnalyses PA;
78   PA.preserve<DominatorTreeAnalysis>();
79   PA.preserve<LoopAnalysis>();
80   return PA;
81 }
82 
83 void CodePreparation::clear() {}
84 
85 CodePreparation::~CodePreparation() { clear(); }
86 
87 void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
88   AU.addRequired<LoopInfoWrapperPass>();
89   AU.addRequired<ScalarEvolutionWrapperPass>();
90 
91   AU.addPreserved<LoopInfoWrapperPass>();
92   AU.addPreserved<RegionInfoPass>();
93   AU.addPreserved<DominatorTreeWrapperPass>();
94   AU.addPreserved<DominanceFrontierWrapperPass>();
95 }
96 
97 bool CodePreparation::runOnFunction(Function &F) {
98   if (skipFunction(F))
99     return false;
100 
101   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
102   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
103 
104   splitEntryBlockForAlloca(&F.getEntryBlock(), this);
105 
106   return true;
107 }
108 
109 void CodePreparation::releaseMemory() { clear(); }
110 
111 void CodePreparation::print(raw_ostream &OS, const Module *) const {}
112 
113 char CodePreparation::ID = 0;
114 char &polly::CodePreparationID = CodePreparation::ID;
115 
116 Pass *polly::createCodePreparationPass() { return new CodePreparation(); }
117 
118 INITIALIZE_PASS_BEGIN(CodePreparation, "polly-prepare",
119                       "Polly - Prepare code for polly", false, false)
120 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
121 INITIALIZE_PASS_END(CodePreparation, "polly-prepare",
122                     "Polly - Prepare code for polly", false, false)
123