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