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/IslAst.h"
23 #include "polly/CodeGen/IslNodeBuilder.h"
24 #include "polly/CodeGen/Utils.h"
25 #include "polly/DependenceInfo.h"
26 #include "polly/LinkAllPasses.h"
27 #include "polly/Options.h"
28 #include "polly/ScopInfo.h"
29 #include "polly/Support/ScopHelper.h"
30 #include "llvm/Analysis/AliasAnalysis.h"
31 #include "llvm/Analysis/BasicAliasAnalysis.h"
32 #include "llvm/Analysis/GlobalsModRef.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 static cl::opt<bool> Verify("polly-codegen-verify",
44                             cl::desc("Verify the function generated by Polly"),
45                             cl::Hidden, cl::init(true), cl::ZeroOrMore,
46                             cl::cat(PollyCategory));
47 
48 namespace {
49 class CodeGeneration : public ScopPass {
50 public:
51   static char ID;
52 
53   CodeGeneration() : ScopPass(ID) {}
54 
55   /// The datalayout used
56   const DataLayout *DL;
57 
58   /// @name The analysis passes we need to generate code.
59   ///
60   ///{
61   LoopInfo *LI;
62   IslAstInfo *AI;
63   DominatorTree *DT;
64   ScalarEvolution *SE;
65   RegionInfo *RI;
66   ///}
67 
68   void verifyGeneratedFunction(Scop &S, Function &F) {
69     if (!verifyFunction(F, &errs()) || !Verify)
70       return;
71 
72     DEBUG({
73       errs() << "== ISL Codegen created an invalid function ==\n\n== The "
74                 "SCoP ==\n";
75       S.print(errs());
76       errs() << "\n== The isl AST ==\n";
77       AI->printScop(errs(), S);
78       errs() << "\n== The invalid function ==\n";
79       F.print(errs());
80     });
81 
82     llvm_unreachable("Polly generated function could not be verified. Add "
83                      "-polly-codegen-verify=false to disable this assertion.");
84   }
85 
86   // CodeGeneration adds a lot of BBs without updating the RegionInfo
87   // We make all created BBs belong to the scop's parent region without any
88   // nested structure to keep the RegionInfo verifier happy.
89   void fixRegionInfo(Function *F, Region *ParentRegion) {
90     for (BasicBlock &BB : *F) {
91       if (RI->getRegionFor(&BB))
92         continue;
93 
94       RI->setRegionFor(&BB, ParentRegion);
95     }
96   }
97 
98   /// Mark a basic block unreachable.
99   ///
100   /// Marks the basic block @p Block unreachable by equipping it with an
101   /// UnreachableInst.
102   void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
103     auto *OrigTerminator = Block.getTerminator();
104     Builder.SetInsertPoint(OrigTerminator);
105     Builder.CreateUnreachable();
106     OrigTerminator->eraseFromParent();
107   }
108 
109   /// Generate LLVM-IR for the SCoP @p S.
110   bool runOnScop(Scop &S) override {
111     AI = &getAnalysis<IslAstInfo>();
112 
113     // Check if we created an isl_ast root node, otherwise exit.
114     isl_ast_node *AstRoot = AI->getAst();
115     if (!AstRoot)
116       return false;
117 
118     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
119     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
120     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
121     DL = &S.getFunction().getParent()->getDataLayout();
122     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
123     Region *R = &S.getRegion();
124     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
125 
126     ScopAnnotator Annotator;
127     Annotator.buildAliasScopes(S);
128 
129     simplifyRegion(R, DT, LI, RI);
130     assert(R->isSimple());
131     BasicBlock *EnteringBB = S.getEnteringBlock();
132     assert(EnteringBB);
133     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
134 
135     // Only build the run-time condition and parameters _after_ having
136     // introduced the conditional branch. This is important as the conditional
137     // branch will guard the original scop from new induction variables that
138     // the SCEVExpander may introduce while code generating the parameters and
139     // which may introduce scalar dependences that prevent us from correctly
140     // code generating this scop.
141     BasicBlock *StartBlock =
142         executeScopConditionally(S, this, Builder.getTrue());
143     auto *SplitBlock = StartBlock->getSinglePredecessor();
144 
145     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S,
146                                StartBlock);
147 
148     // First generate code for the hoisted invariant loads and transitively the
149     // parameters they reference. Afterwards, for the remaining parameters that
150     // might reference the hoisted loads. Finally, build the runtime check
151     // that might reference both hoisted loads as well as parameters.
152     // If the hoisting fails we have to bail and execute the original code.
153     Builder.SetInsertPoint(SplitBlock->getTerminator());
154     if (!NodeBuilder.preloadInvariantLoads()) {
155 
156       // Patch the introduced branch condition to ensure that we always execute
157       // the original SCoP.
158       auto *FalseI1 = Builder.getFalse();
159       auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
160       SplitBBTerm->setOperand(0, FalseI1);
161 
162       // Since the other branch is hence ignored we mark it as unreachable and
163       // adjust the dominator tree accordingly.
164       auto *ExitingBlock = StartBlock->getUniqueSuccessor();
165       assert(ExitingBlock);
166       auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
167       assert(MergeBlock);
168       markBlockUnreachable(*StartBlock, Builder);
169       markBlockUnreachable(*ExitingBlock, Builder);
170       auto *ExitingBB = S.getExitingBlock();
171       assert(ExitingBB);
172       DT->changeImmediateDominator(MergeBlock, ExitingBB);
173       DT->eraseNode(ExitingBlock);
174 
175       isl_ast_node_free(AstRoot);
176     } else {
177       NodeBuilder.allocateNewArrays();
178       NodeBuilder.addParameters(S.getContext());
179       Value *RTC = NodeBuilder.createRTC(AI->getRunCondition());
180 
181       Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
182       Builder.SetInsertPoint(&StartBlock->front());
183 
184       NodeBuilder.create(AstRoot);
185       NodeBuilder.finalize();
186       fixRegionInfo(EnteringBB->getParent(), R->getParent());
187     }
188 
189     Function *F = EnteringBB->getParent();
190     verifyGeneratedFunction(S, *F);
191     for (auto *SubF : NodeBuilder.getParallelSubfunctions())
192       verifyGeneratedFunction(S, *SubF);
193 
194     // Mark the function such that we run additional cleanup passes on this
195     // function (e.g. mem2reg to rediscover phi nodes).
196     F->addFnAttr("polly-optimized");
197 
198     return true;
199   }
200 
201   /// Register all analyses and transformation required.
202   void getAnalysisUsage(AnalysisUsage &AU) const override {
203     AU.addRequired<DominatorTreeWrapperPass>();
204     AU.addRequired<IslAstInfo>();
205     AU.addRequired<RegionInfoPass>();
206     AU.addRequired<ScalarEvolutionWrapperPass>();
207     AU.addRequired<ScopDetection>();
208     AU.addRequired<ScopInfoRegionPass>();
209     AU.addRequired<LoopInfoWrapperPass>();
210 
211     AU.addPreserved<DependenceInfo>();
212 
213     AU.addPreserved<AAResultsWrapperPass>();
214     AU.addPreserved<BasicAAWrapperPass>();
215     AU.addPreserved<LoopInfoWrapperPass>();
216     AU.addPreserved<DominatorTreeWrapperPass>();
217     AU.addPreserved<GlobalsAAWrapperPass>();
218     AU.addPreserved<IslAstInfo>();
219     AU.addPreserved<ScopDetection>();
220     AU.addPreserved<ScalarEvolutionWrapperPass>();
221     AU.addPreserved<SCEVAAWrapperPass>();
222 
223     // FIXME: We do not yet add regions for the newly generated code to the
224     //        region tree.
225     AU.addPreserved<RegionInfoPass>();
226     AU.addPreserved<ScopInfoRegionPass>();
227   }
228 };
229 } // namespace
230 
231 char CodeGeneration::ID = 1;
232 
233 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
234 
235 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
236                       "Polly - Create LLVM-IR from SCoPs", false, false);
237 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
238 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
239 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
240 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
241 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
242 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
243 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
244                     "Polly - Create LLVM-IR from SCoPs", false, false)
245