1 //===------ CodeGeneration.cpp - Code generate the Scops using ISL. ----======//
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 CodeGeneration pass takes a Scop created by ScopInfo and translates it
11 // back to LLVM-IR using the ISL code generator.
12 //
13 // The Scop describes the high level memory behaviour of a control flow region.
14 // Transformation passes can update the schedule (execution order) of statements
15 // in the Scop. ISL is used to generate an abstract syntax tree that reflects
16 // the updated execution order. This clast is used to create new LLVM-IR that is
17 // computationally equivalent to the original control flow region, but executes
18 // its code in the new execution order defined by the changed schedule.
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #include "polly/CodeGen/IslNodeBuilder.h"
23 #include "polly/CodeGen/IslAst.h"
24 #include "polly/CodeGen/Utils.h"
25 #include "polly/DependenceInfo.h"
26 #include "polly/LinkAllPasses.h"
27 #include "polly/ScopInfo.h"
28 #include "polly/Support/ScopHelper.h"
29 #include "polly/TempScopInfo.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/Verifier.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Analysis/AliasAnalysis.h"
34 #include "llvm/Analysis/BasicAliasAnalysis.h"
35 #include "llvm/Analysis/GlobalsModRef.h"
36 #include "llvm/Analysis/PostDominators.h"
37 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
38 
39 using namespace polly;
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "polly-codegen"
43 
44 namespace {
45 class CodeGeneration : public ScopPass {
46 public:
47   static char ID;
48 
49   CodeGeneration() : ScopPass(ID) {}
50 
51   /// @brief The datalayout used
52   const DataLayout *DL;
53 
54   /// @name The analysis passes we need to generate code.
55   ///
56   ///{
57   LoopInfo *LI;
58   IslAstInfo *AI;
59   DominatorTree *DT;
60   ScalarEvolution *SE;
61   RegionInfo *RI;
62   ///}
63 
64   /// @brief The loop annotator to generate llvm.loop metadata.
65   ScopAnnotator Annotator;
66 
67   /// @brief Build the runtime condition.
68   ///
69   /// Build the condition that evaluates at run-time to true iff all
70   /// assumptions taken for the SCoP hold, and to false otherwise.
71   ///
72   /// @return A value evaluating to true/false if execution is save/unsafe.
73   Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
74     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
75     Value *RTC = ExprBuilder.create(AI->getRunCondition());
76     if (!RTC->getType()->isIntegerTy(1))
77       RTC = Builder.CreateIsNotNull(RTC);
78     return RTC;
79   }
80 
81   bool verifyGeneratedFunction(Scop &S, Function &F) {
82     if (!verifyFunction(F))
83       return false;
84 
85     DEBUG({
86       errs() << "== ISL Codegen created an invalid function ==\n\n== The "
87                 "SCoP ==\n";
88       S.print(errs());
89       errs() << "\n== The isl AST ==\n";
90       AI->printScop(errs(), S);
91       errs() << "\n== The invalid function ==\n";
92       F.print(errs());
93       errs() << "\n== The errors ==\n";
94       verifyFunction(F, &errs());
95     });
96 
97     return true;
98   }
99 
100   // CodeGeneration adds a lot of BBs without updating the RegionInfo
101   // We make all created BBs belong to the scop's parent region without any
102   // nested structure to keep the RegionInfo verifier happy.
103   void fixRegionInfo(Function *F, Region *ParentRegion) {
104     for (BasicBlock &BB : *F) {
105       if (RI->getRegionFor(&BB))
106         continue;
107 
108       RI->setRegionFor(&BB, ParentRegion);
109     }
110   }
111 
112   bool runOnScop(Scop &S) override {
113     AI = &getAnalysis<IslAstInfo>();
114 
115     // Check if we created an isl_ast root node, otherwise exit.
116     isl_ast_node *AstRoot = AI->getAst();
117     if (!AstRoot)
118       return false;
119 
120     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
121     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
122     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
123     DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
124     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
125     Region *R = &S.getRegion();
126     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
127 
128     Annotator.buildAliasScopes(S);
129 
130     simplifyRegion(R, DT, LI, RI);
131     assert(R->isSimple());
132     BasicBlock *EnteringBB = S.getRegion().getEnteringBlock();
133     assert(EnteringBB);
134     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
135 
136     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
137 
138     // Only build the run-time condition and parameters _after_ having
139     // introduced the conditional branch. This is important as the conditional
140     // branch will guard the original scop from new induction variables that
141     // the SCEVExpander may introduce while code generating the parameters and
142     // which may introduce scalar dependences that prevent us from correctly
143     // code generating this scop.
144     BasicBlock *StartBlock =
145         executeScopConditionally(S, this, Builder.getTrue());
146     auto SplitBlock = StartBlock->getSinglePredecessor();
147     Builder.SetInsertPoint(SplitBlock->getTerminator());
148     NodeBuilder.addParameters(S.getContext());
149     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
150     SplitBlock->getTerminator()->setOperand(0, RTC);
151     Builder.SetInsertPoint(StartBlock->begin());
152 
153     NodeBuilder.create(AstRoot);
154 
155     NodeBuilder.finalizeSCoP(S);
156     fixRegionInfo(EnteringBB->getParent(), R->getParent());
157 
158     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
159            "Verification of generated function failed");
160     return true;
161   }
162 
163   void printScop(raw_ostream &, Scop &) const override {}
164 
165   void getAnalysisUsage(AnalysisUsage &AU) const override {
166     AU.addRequired<DominatorTreeWrapperPass>();
167     AU.addRequired<IslAstInfo>();
168     AU.addRequired<RegionInfoPass>();
169     AU.addRequired<ScalarEvolutionWrapperPass>();
170     AU.addRequired<ScopDetection>();
171     AU.addRequired<ScopInfo>();
172     AU.addRequired<LoopInfoWrapperPass>();
173 
174     AU.addPreserved<DependenceInfo>();
175 
176     AU.addPreserved<AAResultsWrapperPass>();
177     AU.addPreserved<BasicAAWrapperPass>();
178     AU.addPreserved<LoopInfoWrapperPass>();
179     AU.addPreserved<DominatorTreeWrapperPass>();
180     AU.addPreserved<GlobalsAAWrapperPass>();
181     AU.addPreserved<PostDominatorTree>();
182     AU.addPreserved<IslAstInfo>();
183     AU.addPreserved<ScopDetection>();
184     AU.addPreserved<ScalarEvolutionWrapperPass>();
185     AU.addPreserved<SCEVAAWrapperPass>();
186 
187     // FIXME: We do not yet add regions for the newly generated code to the
188     //        region tree.
189     AU.addPreserved<RegionInfoPass>();
190     AU.addPreserved<TempScopInfo>();
191     AU.addPreserved<ScopInfo>();
192     AU.addPreservedID(IndependentBlocksID);
193   }
194 };
195 }
196 
197 char CodeGeneration::ID = 1;
198 
199 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
200 
201 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
202                       "Polly - Create LLVM-IR from SCoPs", false, false);
203 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
204 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
205 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
206 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
207 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
208 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
209 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
210                     "Polly - Create LLVM-IR from SCoPs", false, false)
211