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