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 "llvm/Analysis/AliasAnalysis.h"
30 #include "llvm/Analysis/BasicAliasAnalysis.h"
31 #include "llvm/Analysis/GlobalsModRef.h"
32 #include "llvm/Analysis/PostDominators.h"
33 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/Verifier.h"
36 #include "llvm/Support/Debug.h"
37 
38 using namespace polly;
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "polly-codegen"
42 
43 namespace {
44 class CodeGeneration : public ScopPass {
45 public:
46   static char ID;
47 
48   CodeGeneration() : ScopPass(ID) {}
49 
50   /// @brief The datalayout used
51   const DataLayout *DL;
52 
53   /// @name The analysis passes we need to generate code.
54   ///
55   ///{
56   LoopInfo *LI;
57   IslAstInfo *AI;
58   DominatorTree *DT;
59   ScalarEvolution *SE;
60   RegionInfo *RI;
61   ///}
62 
63   /// @brief Build the runtime condition.
64   ///
65   /// Build the condition that evaluates at run-time to true iff all
66   /// assumptions taken for the SCoP hold, and to false otherwise.
67   ///
68   /// @return A value evaluating to true/false if execution is save/unsafe.
69   Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
70     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
71     Value *RTC = ExprBuilder.create(AI->getRunCondition());
72     if (!RTC->getType()->isIntegerTy(1))
73       RTC = Builder.CreateIsNotNull(RTC);
74     return RTC;
75   }
76 
77   bool verifyGeneratedFunction(Scop &S, Function &F) {
78     if (!verifyFunction(F))
79       return false;
80 
81     DEBUG({
82       errs() << "== ISL Codegen created an invalid function ==\n\n== The "
83                 "SCoP ==\n";
84       S.print(errs());
85       errs() << "\n== The isl AST ==\n";
86       AI->printScop(errs(), S);
87       errs() << "\n== The invalid function ==\n";
88       F.print(errs());
89       errs() << "\n== The errors ==\n";
90       verifyFunction(F, &errs());
91     });
92 
93     return true;
94   }
95 
96   // CodeGeneration adds a lot of BBs without updating the RegionInfo
97   // We make all created BBs belong to the scop's parent region without any
98   // nested structure to keep the RegionInfo verifier happy.
99   void fixRegionInfo(Function *F, Region *ParentRegion) {
100     for (BasicBlock &BB : *F) {
101       if (RI->getRegionFor(&BB))
102         continue;
103 
104       RI->setRegionFor(&BB, ParentRegion);
105     }
106   }
107 
108   /// @brief Generate LLVM-IR for the SCoP @p S.
109   bool runOnScop(Scop &S) override {
110     AI = &getAnalysis<IslAstInfo>();
111 
112     // Check if we created an isl_ast root node, otherwise exit.
113     isl_ast_node *AstRoot = AI->getAst();
114     if (!AstRoot)
115       return false;
116 
117     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
118     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
119     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
120     DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
121     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
122     Region *R = &S.getRegion();
123     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
124 
125     ScopAnnotator Annotator;
126     Annotator.buildAliasScopes(S);
127 
128     simplifyRegion(R, DT, LI, RI);
129     assert(R->isSimple());
130     BasicBlock *EnteringBB = S.getRegion().getEnteringBlock();
131     assert(EnteringBB);
132     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
133 
134     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
135 
136     // Only build the run-time condition and parameters _after_ having
137     // introduced the conditional branch. This is important as the conditional
138     // branch will guard the original scop from new induction variables that
139     // the SCEVExpander may introduce while code generating the parameters and
140     // which may introduce scalar dependences that prevent us from correctly
141     // code generating this scop.
142     BasicBlock *StartBlock =
143         executeScopConditionally(S, this, Builder.getTrue());
144     auto SplitBlock = StartBlock->getSinglePredecessor();
145 
146     // First generate code for the hoisted invariant loads and transitively the
147     // parameters they reference. Afterwards, for the remaining parameters that
148     // might reference the hoisted loads. Finally, build the runtime check
149     // that might reference both hoisted loads as well as parameters.
150     // If the hoisting fails we have to bail and execute the original code.
151     Builder.SetInsertPoint(SplitBlock->getTerminator());
152     if (!NodeBuilder.preloadInvariantLoads()) {
153 
154       auto *FalseI1 = Builder.getFalse();
155       auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
156       SplitBBTerm->setOperand(0, FalseI1);
157       auto *StartBBTerm = StartBlock->getTerminator();
158       Builder.SetInsertPoint(StartBBTerm);
159       Builder.CreateUnreachable();
160       StartBBTerm->eraseFromParent();
161       isl_ast_node_free(AstRoot);
162 
163     } else {
164 
165       NodeBuilder.addParameters(S.getContext());
166 
167       Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
168       Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
169       Builder.SetInsertPoint(&StartBlock->front());
170 
171       NodeBuilder.create(AstRoot);
172 
173       NodeBuilder.finalizeSCoP(S);
174       fixRegionInfo(EnteringBB->getParent(), R->getParent());
175     }
176 
177     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
178            "Verification of generated function failed");
179 
180     // Mark the function such that we run additional cleanup passes on this
181     // function (e.g. mem2reg to rediscover phi nodes).
182     Function *F = EnteringBB->getParent();
183     F->addFnAttr("polly-optimized");
184 
185     return true;
186   }
187 
188   /// @brief Register all analyses and transformation required.
189   void getAnalysisUsage(AnalysisUsage &AU) const override {
190     AU.addRequired<DominatorTreeWrapperPass>();
191     AU.addRequired<IslAstInfo>();
192     AU.addRequired<RegionInfoPass>();
193     AU.addRequired<ScalarEvolutionWrapperPass>();
194     AU.addRequired<ScopDetection>();
195     AU.addRequired<ScopInfo>();
196     AU.addRequired<LoopInfoWrapperPass>();
197 
198     AU.addPreserved<DependenceInfo>();
199 
200     AU.addPreserved<AAResultsWrapperPass>();
201     AU.addPreserved<BasicAAWrapperPass>();
202     AU.addPreserved<LoopInfoWrapperPass>();
203     AU.addPreserved<DominatorTreeWrapperPass>();
204     AU.addPreserved<GlobalsAAWrapperPass>();
205     AU.addPreserved<PostDominatorTree>();
206     AU.addPreserved<IslAstInfo>();
207     AU.addPreserved<ScopDetection>();
208     AU.addPreserved<ScalarEvolutionWrapperPass>();
209     AU.addPreserved<SCEVAAWrapperPass>();
210 
211     // FIXME: We do not yet add regions for the newly generated code to the
212     //        region tree.
213     AU.addPreserved<RegionInfoPass>();
214     AU.addPreserved<ScopInfo>();
215   }
216 };
217 }
218 
219 char CodeGeneration::ID = 1;
220 
221 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
222 
223 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
224                       "Polly - Create LLVM-IR from SCoPs", false, false);
225 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
226 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
227 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
228 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
229 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
230 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
231 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
232                     "Polly - Create LLVM-IR from SCoPs", false, false)
233