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 
34 using namespace polly;
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "polly-codegen"
38 
39 namespace {
40 class CodeGeneration : public ScopPass {
41 public:
42   static char ID;
43 
44   CodeGeneration() : ScopPass(ID) {}
45 
46   /// @brief The datalayout used
47   const DataLayout *DL;
48 
49   /// @name The analysis passes we need to generate code.
50   ///
51   ///{
52   LoopInfo *LI;
53   IslAstInfo *AI;
54   DominatorTree *DT;
55   ScalarEvolution *SE;
56   RegionInfo *RI;
57   ///}
58 
59   /// @brief The loop annotator to generate llvm.loop metadata.
60   ScopAnnotator Annotator;
61 
62   /// @brief Build the runtime condition.
63   ///
64   /// Build the condition that evaluates at run-time to true iff all
65   /// assumptions taken for the SCoP hold, and to false otherwise.
66   ///
67   /// @return A value evaluating to true/false if execution is save/unsafe.
68   Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
69     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
70     Value *RTC = ExprBuilder.create(AI->getRunCondition());
71     if (!RTC->getType()->isIntegerTy(1))
72       RTC = Builder.CreateIsNotNull(RTC);
73     return RTC;
74   }
75 
76   bool verifyGeneratedFunction(Scop &S, Function &F) {
77     if (!verifyFunction(F))
78       return false;
79 
80     DEBUG({
81       errs() << "== ISL Codegen created an invalid function ==\n\n== The "
82                 "SCoP ==\n";
83       S.print(errs());
84       errs() << "\n== The isl AST ==\n";
85       AI->printScop(errs(), S);
86       errs() << "\n== The invalid function ==\n";
87       F.print(errs());
88       errs() << "\n== The errors ==\n";
89       verifyFunction(F, &errs());
90     });
91 
92     return true;
93   }
94 
95   bool runOnScop(Scop &S) override {
96     AI = &getAnalysis<IslAstInfo>();
97 
98     // Check if we created an isl_ast root node, otherwise exit.
99     isl_ast_node *AstRoot = AI->getAst();
100     if (!AstRoot)
101       return false;
102 
103     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
104     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
105     SE = &getAnalysis<ScalarEvolution>();
106     DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
107     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
108     Region *R = &S.getRegion();
109     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
110 
111     Annotator.buildAliasScopes(S);
112 
113     simplifyRegion(R, DT, LI, RI);
114     assert(R->isSimple());
115     BasicBlock *EnteringBB = S.getRegion().getEnteringBlock();
116     assert(EnteringBB);
117     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
118 
119     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
120 
121     // Only build the run-time condition and parameters _after_ having
122     // introduced the conditional branch. This is important as the conditional
123     // branch will guard the original scop from new induction variables that
124     // the SCEVExpander may introduce while code generating the parameters and
125     // which may introduce scalar dependences that prevent us from correctly
126     // code generating this scop.
127     BasicBlock *StartBlock =
128         executeScopConditionally(S, this, Builder.getTrue());
129     auto SplitBlock = StartBlock->getSinglePredecessor();
130     Builder.SetInsertPoint(SplitBlock->getTerminator());
131     NodeBuilder.addParameters(S.getContext());
132     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
133     SplitBlock->getTerminator()->setOperand(0, RTC);
134     Builder.SetInsertPoint(StartBlock->begin());
135 
136     NodeBuilder.create(AstRoot);
137 
138     NodeBuilder.finalizeSCoP(S);
139 
140     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
141            "Verification of generated function failed");
142     return true;
143   }
144 
145   void printScop(raw_ostream &, Scop &) const override {}
146 
147   void getAnalysisUsage(AnalysisUsage &AU) const override {
148     AU.addRequired<DominatorTreeWrapperPass>();
149     AU.addRequired<IslAstInfo>();
150     AU.addRequired<RegionInfoPass>();
151     AU.addRequired<ScalarEvolution>();
152     AU.addRequired<ScopDetection>();
153     AU.addRequired<ScopInfo>();
154     AU.addRequired<LoopInfoWrapperPass>();
155 
156     AU.addPreserved<DependenceInfo>();
157 
158     AU.addPreserved<LoopInfoWrapperPass>();
159     AU.addPreserved<DominatorTreeWrapperPass>();
160     AU.addPreserved<IslAstInfo>();
161     AU.addPreserved<ScopDetection>();
162     AU.addPreserved<ScalarEvolution>();
163 
164     // FIXME: We do not yet add regions for the newly generated code to the
165     //        region tree.
166     AU.addPreserved<RegionInfoPass>();
167     AU.addPreserved<TempScopInfo>();
168     AU.addPreserved<ScopInfo>();
169     AU.addPreservedID(IndependentBlocksID);
170   }
171 };
172 }
173 
174 char CodeGeneration::ID = 1;
175 
176 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
177 
178 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
179                       "Polly - Create LLVM-IR from SCoPs", false, false);
180 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
181 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
182 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
183 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
184 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
185 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
186 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
187                     "Polly - Create LLVM-IR from SCoPs", false, false)
188