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