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 behavior 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/CodeGeneration.h"
23 #include "polly/CodeGen/IslAst.h"
24 #include "polly/CodeGen/IslNodeBuilder.h"
25 #include "polly/CodeGen/PerfMonitor.h"
26 #include "polly/CodeGen/Utils.h"
27 #include "polly/DependenceInfo.h"
28 #include "polly/LinkAllPasses.h"
29 #include "polly/Options.h"
30 #include "polly/ScopInfo.h"
31 #include "polly/Support/ScopHelper.h"
32 #include "llvm/Analysis/AliasAnalysis.h"
33 #include "llvm/Analysis/BasicAliasAnalysis.h"
34 #include "llvm/Analysis/GlobalsModRef.h"
35 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/PassManager.h"
39 #include "llvm/IR/Verifier.h"
40 #include "llvm/Support/Debug.h"
41 
42 using namespace polly;
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "polly-codegen"
46 
47 static cl::opt<bool> Verify("polly-codegen-verify",
48                             cl::desc("Verify the function generated by Polly"),
49                             cl::Hidden, cl::init(false), cl::ZeroOrMore,
50                             cl::cat(PollyCategory));
51 
52 static cl::opt<bool>
53     PerfMonitoring("polly-codegen-perf-monitoring",
54                    cl::desc("Add run-time performance monitoring"), cl::Hidden,
55                    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
56 
57 namespace {
58 
59 static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
60   if (!Verify || !verifyFunction(F, &errs()))
61     return;
62 
63   DEBUG({
64     errs() << "== ISL Codegen created an invalid function ==\n\n== The "
65               "SCoP ==\n";
66     S.print(errs());
67     errs() << "\n== The isl AST ==\n";
68     AI.print(errs());
69     errs() << "\n== The invalid function ==\n";
70     F.print(errs());
71   });
72 
73   llvm_unreachable("Polly generated function could not be verified. Add "
74                    "-polly-codegen-verify=false to disable this assertion.");
75 }
76 
77 // CodeGeneration adds a lot of BBs without updating the RegionInfo
78 // We make all created BBs belong to the scop's parent region without any
79 // nested structure to keep the RegionInfo verifier happy.
80 static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
81   for (BasicBlock &BB : F) {
82     if (RI.getRegionFor(&BB))
83       continue;
84 
85     RI.setRegionFor(&BB, &ParentRegion);
86   }
87 }
88 
89 /// Mark a basic block unreachable.
90 ///
91 /// Marks the basic block @p Block unreachable by equipping it with an
92 /// UnreachableInst.
93 static void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
94   auto *OrigTerminator = Block.getTerminator();
95   Builder.SetInsertPoint(OrigTerminator);
96   Builder.CreateUnreachable();
97   OrigTerminator->eraseFromParent();
98 }
99 
100 /// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from
101 /// @R.
102 ///
103 /// CodeGeneration does not copy lifetime markers into the optimized SCoP,
104 /// which would leave the them only in the original path. This can transform
105 /// code such as
106 ///
107 ///     llvm.lifetime.start(%p)
108 ///     llvm.lifetime.end(%p)
109 ///
110 /// into
111 ///
112 ///     if (RTC) {
113 ///       // generated code
114 ///     } else {
115 ///       // original code
116 ///       llvm.lifetime.start(%p)
117 ///     }
118 ///     llvm.lifetime.end(%p)
119 ///
120 /// The current StackColoring algorithm cannot handle if some, but not all,
121 /// paths from the end marker to the entry block cross the start marker. Same
122 /// for start markers that do not always cross the end markers. We avoid any
123 /// issues by removing all lifetime markers, even from the original code.
124 ///
125 /// A better solution could be to hoist all llvm.lifetime.start to the split
126 /// node and all llvm.lifetime.end to the merge node, which should be
127 /// conservatively correct.
128 static void removeLifetimeMarkers(Region *R) {
129   for (auto *BB : R->blocks()) {
130     auto InstIt = BB->begin();
131     auto InstEnd = BB->end();
132 
133     while (InstIt != InstEnd) {
134       auto NextIt = InstIt;
135       ++NextIt;
136 
137       if (auto *IT = dyn_cast<IntrinsicInst>(&*InstIt)) {
138         switch (IT->getIntrinsicID()) {
139         case llvm::Intrinsic::lifetime_start:
140         case llvm::Intrinsic::lifetime_end:
141           BB->getInstList().erase(InstIt);
142           break;
143         default:
144           break;
145         }
146       }
147 
148       InstIt = NextIt;
149     }
150   }
151 }
152 
153 static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
154                     ScalarEvolution &SE, RegionInfo &RI) {
155   // Check if we created an isl_ast root node, otherwise exit.
156   isl_ast_node *AstRoot = AI.getAst();
157   if (!AstRoot)
158     return false;
159 
160   auto &DL = S.getFunction().getParent()->getDataLayout();
161   Region *R = &S.getRegion();
162   assert(!R->isTopLevelRegion() && "Top level regions are not supported");
163 
164   ScopAnnotator Annotator;
165 
166   simplifyRegion(R, &DT, &LI, &RI);
167   assert(R->isSimple());
168   BasicBlock *EnteringBB = S.getEnteringBlock();
169   assert(EnteringBB);
170   PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
171 
172   // Only build the run-time condition and parameters _after_ having
173   // introduced the conditional branch. This is important as the conditional
174   // branch will guard the original scop from new induction variables that
175   // the SCEVExpander may introduce while code generating the parameters and
176   // which may introduce scalar dependences that prevent us from correctly
177   // code generating this scop.
178   BBPair StartExitBlocks =
179       executeScopConditionally(S, Builder.getTrue(), DT, RI, LI);
180   BasicBlock *StartBlock = std::get<0>(StartExitBlocks);
181 
182   removeLifetimeMarkers(R);
183   auto *SplitBlock = StartBlock->getSinglePredecessor();
184 
185   IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
186 
187   // All arrays must have their base pointers known before
188   // ScopAnnotator::buildAliasScopes.
189   NodeBuilder.allocateNewArrays();
190   Annotator.buildAliasScopes(S);
191 
192   if (PerfMonitoring) {
193     PerfMonitor P(S, EnteringBB->getParent()->getParent());
194     P.initialize();
195     P.insertRegionStart(SplitBlock->getTerminator());
196 
197     BasicBlock *MergeBlock = SplitBlock->getTerminator()
198                                  ->getSuccessor(0)
199                                  ->getUniqueSuccessor()
200                                  ->getUniqueSuccessor();
201     P.insertRegionEnd(MergeBlock->getTerminator());
202   }
203 
204   // First generate code for the hoisted invariant loads and transitively the
205   // parameters they reference. Afterwards, for the remaining parameters that
206   // might reference the hoisted loads. Finally, build the runtime check
207   // that might reference both hoisted loads as well as parameters.
208   // If the hoisting fails we have to bail and execute the original code.
209   Builder.SetInsertPoint(SplitBlock->getTerminator());
210   if (!NodeBuilder.preloadInvariantLoads()) {
211 
212     // Patch the introduced branch condition to ensure that we always execute
213     // the original SCoP.
214     auto *FalseI1 = Builder.getFalse();
215     auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
216     SplitBBTerm->setOperand(0, FalseI1);
217 
218     // Since the other branch is hence ignored we mark it as unreachable and
219     // adjust the dominator tree accordingly.
220     auto *ExitingBlock = StartBlock->getUniqueSuccessor();
221     assert(ExitingBlock);
222     auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
223     assert(MergeBlock);
224     markBlockUnreachable(*StartBlock, Builder);
225     markBlockUnreachable(*ExitingBlock, Builder);
226     auto *ExitingBB = S.getExitingBlock();
227     assert(ExitingBB);
228     DT.changeImmediateDominator(MergeBlock, ExitingBB);
229     DT.eraseNode(ExitingBlock);
230 
231     isl_ast_node_free(AstRoot);
232   } else {
233     NodeBuilder.addParameters(S.getContext());
234     Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
235 
236     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
237     Builder.SetInsertPoint(&StartBlock->front());
238 
239     NodeBuilder.create(AstRoot);
240     NodeBuilder.finalize();
241     fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
242   }
243 
244   Function *F = EnteringBB->getParent();
245   verifyGeneratedFunction(S, *F, AI);
246   for (auto *SubF : NodeBuilder.getParallelSubfunctions())
247     verifyGeneratedFunction(S, *SubF, AI);
248 
249   // Mark the function such that we run additional cleanup passes on this
250   // function (e.g. mem2reg to rediscover phi nodes).
251   F->addFnAttr("polly-optimized");
252   return true;
253 }
254 
255 class CodeGeneration : public ScopPass {
256 public:
257   static char ID;
258 
259   CodeGeneration() : ScopPass(ID) {}
260 
261   /// The data layout used.
262   const DataLayout *DL;
263 
264   /// @name The analysis passes we need to generate code.
265   ///
266   ///{
267   LoopInfo *LI;
268   IslAstInfo *AI;
269   DominatorTree *DT;
270   ScalarEvolution *SE;
271   RegionInfo *RI;
272   ///}
273 
274   /// Generate LLVM-IR for the SCoP @p S.
275   bool runOnScop(Scop &S) override {
276     AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
277     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
278     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
279     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
280     DL = &S.getFunction().getParent()->getDataLayout();
281     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
282     return CodeGen(S, *AI, *LI, *DT, *SE, *RI);
283   }
284 
285   /// Register all analyses and transformation required.
286   void getAnalysisUsage(AnalysisUsage &AU) const override {
287     AU.addRequired<DominatorTreeWrapperPass>();
288     AU.addRequired<IslAstInfoWrapperPass>();
289     AU.addRequired<RegionInfoPass>();
290     AU.addRequired<ScalarEvolutionWrapperPass>();
291     AU.addRequired<ScopDetectionWrapperPass>();
292     AU.addRequired<ScopInfoRegionPass>();
293     AU.addRequired<LoopInfoWrapperPass>();
294 
295     AU.addPreserved<DependenceInfo>();
296 
297     AU.addPreserved<AAResultsWrapperPass>();
298     AU.addPreserved<BasicAAWrapperPass>();
299     AU.addPreserved<LoopInfoWrapperPass>();
300     AU.addPreserved<DominatorTreeWrapperPass>();
301     AU.addPreserved<GlobalsAAWrapperPass>();
302     AU.addPreserved<IslAstInfoWrapperPass>();
303     AU.addPreserved<ScopDetectionWrapperPass>();
304     AU.addPreserved<ScalarEvolutionWrapperPass>();
305     AU.addPreserved<SCEVAAWrapperPass>();
306 
307     // FIXME: We do not yet add regions for the newly generated code to the
308     //        region tree.
309     AU.addPreserved<RegionInfoPass>();
310     AU.addPreserved<ScopInfoRegionPass>();
311   }
312 };
313 } // namespace
314 
315 PreservedAnalyses
316 polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
317                                ScopStandardAnalysisResults &AR, SPMUpdater &U) {
318   auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
319   if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI))
320     return PreservedAnalyses::none();
321 
322   return PreservedAnalyses::all();
323 }
324 
325 char CodeGeneration::ID = 1;
326 
327 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
328 
329 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
330                       "Polly - Create LLVM-IR from SCoPs", false, false);
331 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
332 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
333 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
334 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
335 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
336 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
337 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
338                     "Polly - Create LLVM-IR from SCoPs", false, false)
339