1 //===- CodeGeneration.cpp - Code generate the Scops using ISL. ---------======//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // The CodeGeneration pass takes a Scop created by ScopInfo and translates it
10 // back to LLVM-IR using the ISL code generator.
11 //
12 // The Scop describes the high level memory behavior of a control flow region.
13 // Transformation passes can update the schedule (execution order) of statements
14 // in the Scop. ISL is used to generate an abstract syntax tree that reflects
15 // the updated execution order. This clast is used to create new LLVM-IR that is
16 // computationally equivalent to the original control flow region, but executes
17 // its code in the new execution order defined by the changed schedule.
18 //
19 //===----------------------------------------------------------------------===//
20
21 #include "polly/CodeGen/CodeGeneration.h"
22 #include "polly/CodeGen/IRBuilder.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/ADT/Statistic.h"
33 #include "llvm/Analysis/LoopInfo.h"
34 #include "llvm/Analysis/RegionInfo.h"
35 #include "llvm/IR/BasicBlock.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/PassManager.h"
39 #include "llvm/IR/Verifier.h"
40 #include "llvm/InitializePasses.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/ErrorHandling.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include "isl/ast.h"
45 #include <cassert>
46
47 using namespace llvm;
48 using namespace polly;
49
50 #define DEBUG_TYPE "polly-codegen"
51
52 static cl::opt<bool> Verify("polly-codegen-verify",
53 cl::desc("Verify the function generated by Polly"),
54 cl::Hidden, cl::init(false), cl::ZeroOrMore,
55 cl::cat(PollyCategory));
56
57 bool polly::PerfMonitoring;
58
59 static cl::opt<bool, true>
60 XPerfMonitoring("polly-codegen-perf-monitoring",
61 cl::desc("Add run-time performance monitoring"), cl::Hidden,
62 cl::location(polly::PerfMonitoring), cl::init(false),
63 cl::ZeroOrMore, cl::cat(PollyCategory));
64
65 STATISTIC(ScopsProcessed, "Number of SCoP processed");
66 STATISTIC(CodegenedScops, "Number of successfully generated SCoPs");
67 STATISTIC(CodegenedAffineLoops,
68 "Number of original affine loops in SCoPs that have been generated");
69 STATISTIC(CodegenedBoxedLoops,
70 "Number of original boxed loops in SCoPs that have been generated");
71
72 namespace polly {
73
74 /// Mark a basic block unreachable.
75 ///
76 /// Marks the basic block @p Block unreachable by equipping it with an
77 /// UnreachableInst.
markBlockUnreachable(BasicBlock & Block,PollyIRBuilder & Builder)78 void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
79 auto *OrigTerminator = Block.getTerminator();
80 Builder.SetInsertPoint(OrigTerminator);
81 Builder.CreateUnreachable();
82 OrigTerminator->eraseFromParent();
83 }
84 } // namespace polly
85
verifyGeneratedFunction(Scop & S,Function & F,IslAstInfo & AI)86 static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
87 if (!Verify || !verifyFunction(F, &errs()))
88 return;
89
90 LLVM_DEBUG({
91 errs() << "== ISL Codegen created an invalid function ==\n\n== The "
92 "SCoP ==\n";
93 errs() << S;
94 errs() << "\n== The isl AST ==\n";
95 AI.print(errs());
96 errs() << "\n== The invalid function ==\n";
97 F.print(errs());
98 });
99
100 llvm_unreachable("Polly generated function could not be verified. Add "
101 "-polly-codegen-verify=false to disable this assertion.");
102 }
103
104 // CodeGeneration adds a lot of BBs without updating the RegionInfo
105 // We make all created BBs belong to the scop's parent region without any
106 // nested structure to keep the RegionInfo verifier happy.
fixRegionInfo(Function & F,Region & ParentRegion,RegionInfo & RI)107 static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
108 for (BasicBlock &BB : F) {
109 if (RI.getRegionFor(&BB))
110 continue;
111
112 RI.setRegionFor(&BB, &ParentRegion);
113 }
114 }
115
116 /// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from
117 /// @R.
118 ///
119 /// CodeGeneration does not copy lifetime markers into the optimized SCoP,
120 /// which would leave the them only in the original path. This can transform
121 /// code such as
122 ///
123 /// llvm.lifetime.start(%p)
124 /// llvm.lifetime.end(%p)
125 ///
126 /// into
127 ///
128 /// if (RTC) {
129 /// // generated code
130 /// } else {
131 /// // original code
132 /// llvm.lifetime.start(%p)
133 /// }
134 /// llvm.lifetime.end(%p)
135 ///
136 /// The current StackColoring algorithm cannot handle if some, but not all,
137 /// paths from the end marker to the entry block cross the start marker. Same
138 /// for start markers that do not always cross the end markers. We avoid any
139 /// issues by removing all lifetime markers, even from the original code.
140 ///
141 /// A better solution could be to hoist all llvm.lifetime.start to the split
142 /// node and all llvm.lifetime.end to the merge node, which should be
143 /// conservatively correct.
removeLifetimeMarkers(Region * R)144 static void removeLifetimeMarkers(Region *R) {
145 for (auto *BB : R->blocks()) {
146 auto InstIt = BB->begin();
147 auto InstEnd = BB->end();
148
149 while (InstIt != InstEnd) {
150 auto NextIt = InstIt;
151 ++NextIt;
152
153 if (auto *IT = dyn_cast<IntrinsicInst>(&*InstIt)) {
154 switch (IT->getIntrinsicID()) {
155 case Intrinsic::lifetime_start:
156 case Intrinsic::lifetime_end:
157 BB->getInstList().erase(InstIt);
158 break;
159 default:
160 break;
161 }
162 }
163
164 InstIt = NextIt;
165 }
166 }
167 }
168
generateCode(Scop & S,IslAstInfo & AI,LoopInfo & LI,DominatorTree & DT,ScalarEvolution & SE,RegionInfo & RI)169 static bool generateCode(Scop &S, IslAstInfo &AI, LoopInfo &LI,
170 DominatorTree &DT, ScalarEvolution &SE,
171 RegionInfo &RI) {
172 // Check whether IslAstInfo uses the same isl_ctx. Since -polly-codegen
173 // reports itself to preserve DependenceInfo and IslAstInfo, we might get
174 // those analysis that were computed by a different ScopInfo for a different
175 // Scop structure. When the ScopInfo/Scop object is freed, there is a high
176 // probability that the new ScopInfo/Scop object will be created at the same
177 // heap position with the same address. Comparing whether the Scop or ScopInfo
178 // address is the expected therefore is unreliable.
179 // Instead, we compare the address of the isl_ctx object. Both, DependenceInfo
180 // and IslAstInfo must hold a reference to the isl_ctx object to ensure it is
181 // not freed before the destruction of those analyses which might happen after
182 // the destruction of the Scop/ScopInfo they refer to. Hence, the isl_ctx
183 // will not be freed and its space not reused as long there is a
184 // DependenceInfo or IslAstInfo around.
185 IslAst &Ast = AI.getIslAst();
186 if (Ast.getSharedIslCtx() != S.getSharedIslCtx()) {
187 LLVM_DEBUG(dbgs() << "Got an IstAst for a different Scop/isl_ctx\n");
188 return false;
189 }
190
191 // Check if we created an isl_ast root node, otherwise exit.
192 isl::ast_node AstRoot = Ast.getAst();
193 if (AstRoot.is_null())
194 return false;
195
196 // Collect statistics. Do it before we modify the IR to avoid having it any
197 // influence on the result.
198 auto ScopStats = S.getStatistics();
199 ScopsProcessed++;
200
201 auto &DL = S.getFunction().getParent()->getDataLayout();
202 Region *R = &S.getRegion();
203 assert(!R->isTopLevelRegion() && "Top level regions are not supported");
204
205 ScopAnnotator Annotator;
206
207 simplifyRegion(R, &DT, &LI, &RI);
208 assert(R->isSimple());
209 BasicBlock *EnteringBB = S.getEnteringBlock();
210 assert(EnteringBB);
211 PollyIRBuilder Builder(EnteringBB->getContext(), ConstantFolder(),
212 IRInserter(Annotator));
213 Builder.SetInsertPoint(EnteringBB->getTerminator());
214
215 // Only build the run-time condition and parameters _after_ having
216 // introduced the conditional branch. This is important as the conditional
217 // branch will guard the original scop from new induction variables that
218 // the SCEVExpander may introduce while code generating the parameters and
219 // which may introduce scalar dependences that prevent us from correctly
220 // code generating this scop.
221 BBPair StartExitBlocks =
222 std::get<0>(executeScopConditionally(S, Builder.getTrue(), DT, RI, LI));
223 BasicBlock *StartBlock = std::get<0>(StartExitBlocks);
224 BasicBlock *ExitBlock = std::get<1>(StartExitBlocks);
225
226 removeLifetimeMarkers(R);
227 auto *SplitBlock = StartBlock->getSinglePredecessor();
228
229 IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
230
231 // All arrays must have their base pointers known before
232 // ScopAnnotator::buildAliasScopes.
233 NodeBuilder.allocateNewArrays(StartExitBlocks);
234 Annotator.buildAliasScopes(S);
235
236 if (PerfMonitoring) {
237 PerfMonitor P(S, EnteringBB->getParent()->getParent());
238 P.initialize();
239 P.insertRegionStart(SplitBlock->getTerminator());
240
241 BasicBlock *MergeBlock = ExitBlock->getUniqueSuccessor();
242 P.insertRegionEnd(MergeBlock->getTerminator());
243 }
244
245 // First generate code for the hoisted invariant loads and transitively the
246 // parameters they reference. Afterwards, for the remaining parameters that
247 // might reference the hoisted loads. Finally, build the runtime check
248 // that might reference both hoisted loads as well as parameters.
249 // If the hoisting fails we have to bail and execute the original code.
250 Builder.SetInsertPoint(SplitBlock->getTerminator());
251 if (!NodeBuilder.preloadInvariantLoads()) {
252 // Patch the introduced branch condition to ensure that we always execute
253 // the original SCoP.
254 auto *FalseI1 = Builder.getFalse();
255 auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
256 SplitBBTerm->setOperand(0, FalseI1);
257
258 // Since the other branch is hence ignored we mark it as unreachable and
259 // adjust the dominator tree accordingly.
260 auto *ExitingBlock = StartBlock->getUniqueSuccessor();
261 assert(ExitingBlock);
262 auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
263 assert(MergeBlock);
264 markBlockUnreachable(*StartBlock, Builder);
265 markBlockUnreachable(*ExitingBlock, Builder);
266 auto *ExitingBB = S.getExitingBlock();
267 assert(ExitingBB);
268 DT.changeImmediateDominator(MergeBlock, ExitingBB);
269 DT.eraseNode(ExitingBlock);
270 } else {
271 NodeBuilder.addParameters(S.getContext().release());
272 Value *RTC = NodeBuilder.createRTC(AI.getRunCondition().release());
273
274 Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
275
276 // Explicitly set the insert point to the end of the block to avoid that a
277 // split at the builder's current
278 // insert position would move the malloc calls to the wrong BasicBlock.
279 // Ideally we would just split the block during allocation of the new
280 // arrays, but this would break the assumption that there are no blocks
281 // between polly.start and polly.exiting (at this point).
282 Builder.SetInsertPoint(StartBlock->getTerminator());
283
284 NodeBuilder.create(AstRoot.release());
285 NodeBuilder.finalize();
286 fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
287
288 CodegenedScops++;
289 CodegenedAffineLoops += ScopStats.NumAffineLoops;
290 CodegenedBoxedLoops += ScopStats.NumBoxedLoops;
291 }
292
293 Function *F = EnteringBB->getParent();
294 verifyGeneratedFunction(S, *F, AI);
295 for (auto *SubF : NodeBuilder.getParallelSubfunctions())
296 verifyGeneratedFunction(S, *SubF, AI);
297
298 // Mark the function such that we run additional cleanup passes on this
299 // function (e.g. mem2reg to rediscover phi nodes).
300 F->addFnAttr("polly-optimized");
301 return true;
302 }
303
304 namespace {
305
306 class CodeGeneration : public ScopPass {
307 public:
308 static char ID;
309
310 /// The data layout used.
311 const DataLayout *DL;
312
313 /// @name The analysis passes we need to generate code.
314 ///
315 ///{
316 LoopInfo *LI;
317 IslAstInfo *AI;
318 DominatorTree *DT;
319 ScalarEvolution *SE;
320 RegionInfo *RI;
321 ///}
322
CodeGeneration()323 CodeGeneration() : ScopPass(ID) {}
324
325 /// Generate LLVM-IR for the SCoP @p S.
runOnScop(Scop & S)326 bool runOnScop(Scop &S) override {
327 // Skip SCoPs in case they're already code-generated by PPCGCodeGeneration.
328 if (S.isToBeSkipped())
329 return false;
330
331 AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
332 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
333 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
334 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
335 DL = &S.getFunction().getParent()->getDataLayout();
336 RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
337 return generateCode(S, *AI, *LI, *DT, *SE, *RI);
338 }
339
340 /// Register all analyses and transformation required.
getAnalysisUsage(AnalysisUsage & AU) const341 void getAnalysisUsage(AnalysisUsage &AU) const override {
342 ScopPass::getAnalysisUsage(AU);
343
344 AU.addRequired<DominatorTreeWrapperPass>();
345 AU.addRequired<IslAstInfoWrapperPass>();
346 AU.addRequired<RegionInfoPass>();
347 AU.addRequired<ScalarEvolutionWrapperPass>();
348 AU.addRequired<ScopDetectionWrapperPass>();
349 AU.addRequired<ScopInfoRegionPass>();
350 AU.addRequired<LoopInfoWrapperPass>();
351
352 AU.addPreserved<DependenceInfo>();
353 AU.addPreserved<IslAstInfoWrapperPass>();
354
355 // FIXME: We do not yet add regions for the newly generated code to the
356 // region tree.
357 }
358 };
359 } // namespace
360
run(Scop & S,ScopAnalysisManager & SAM,ScopStandardAnalysisResults & AR,SPMUpdater & U)361 PreservedAnalyses CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
362 ScopStandardAnalysisResults &AR,
363 SPMUpdater &U) {
364 auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
365 if (generateCode(S, AI, AR.LI, AR.DT, AR.SE, AR.RI)) {
366 U.invalidateScop(S);
367 return PreservedAnalyses::none();
368 }
369
370 return PreservedAnalyses::all();
371 }
372
373 char CodeGeneration::ID = 1;
374
createCodeGenerationPass()375 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
376
377 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
378 "Polly - Create LLVM-IR from SCoPs", false, false);
379 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
380 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
381 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
382 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
383 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
384 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
385 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
386 "Polly - Create LLVM-IR from SCoPs", false, false)
387