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