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
47using namespace llvm;
48using namespace polly;
49
50#include "polly/Support/PollyDebug.h"
51#define DEBUG_TYPE "polly-codegen"
52
53static cl::opt<bool> Verify("polly-codegen-verify",
54 cl::desc("Verify the function generated by Polly"),
55 cl::Hidden, cl::cat(PollyCategory));
56
57bool polly::PerfMonitoring;
58
59static cl::opt<bool, true>
60 XPerfMonitoring("polly-codegen-perf-monitoring",
61 cl::desc("Add run-time performance monitoring"), cl::Hidden,
62 cl::location(L&: polly::PerfMonitoring),
63 cl::cat(PollyCategory));
64
65STATISTIC(ScopsProcessed, "Number of SCoP processed");
66STATISTIC(CodegenedScops, "Number of successfully generated SCoPs");
67STATISTIC(CodegenedAffineLoops,
68 "Number of original affine loops in SCoPs that have been generated");
69STATISTIC(CodegenedBoxedLoops,
70 "Number of original boxed loops in SCoPs that have been generated");
71
72namespace polly {
73
74/// Mark a basic block unreachable.
75///
76/// Marks the basic block @p Block unreachable by equipping it with an
77/// UnreachableInst.
78void 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
86static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
87 if (!Verify || !verifyFunction(F, OS: &errs()))
88 return;
89
90 POLLY_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.
107static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
108 for (BasicBlock &BB : F) {
109 if (RI.getRegionFor(BB: &BB))
110 continue;
111
112 RI.setRegionFor(BB: &BB, R: &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.
144static 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>(Val: &*InstIt)) {
154 switch (IT->getIntrinsicID()) {
155 case Intrinsic::lifetime_start:
156 case Intrinsic::lifetime_end:
157 IT->eraseFromParent();
158 break;
159 default:
160 break;
161 }
162 }
163
164 InstIt = NextIt;
165 }
166 }
167}
168
169static 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 POLLY_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: &DT, LI: &LI, RI: &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>(in: executeScopConditionally(S, RTC: Builder.getTrue(), DT, RI, LI));
223 BasicBlock *StartBlock = std::get<0>(in&: StartExitBlocks);
224 BasicBlock *ExitBlock = std::get<1>(in&: 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(InsertBefore: SplitBlock->getTerminator());
240
241 BasicBlock *MergeBlock = ExitBlock->getUniqueSuccessor();
242 P.insertRegionEnd(InsertBefore: 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(i: 0, Val: 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(Block&: *StartBlock, Builder);
265 markBlockUnreachable(Block&: *ExitingBlock, Builder);
266 auto *ExitingBB = S.getExitingBlock();
267 assert(ExitingBB);
268 DT.changeImmediateDominator(BB: MergeBlock, NewBB: ExitingBB);
269 DT.eraseNode(BB: ExitingBlock);
270 } else {
271 NodeBuilder.addParameters(Context: S.getContext().release());
272 Value *RTC = NodeBuilder.createRTC(Condition: AI.getRunCondition().release());
273
274 Builder.GetInsertBlock()->getTerminator()->setOperand(i: 0, Val: 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(Node: AstRoot.release());
285 NodeBuilder.finalize();
286 fixRegionInfo(F&: *EnteringBB->getParent(), ParentRegion&: *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&: *F, AI);
295 for (auto *SubF : NodeBuilder.getParallelSubfunctions())
296 verifyGeneratedFunction(S, F&: *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(Kind: "polly-optimized");
301 return true;
302}
303
304namespace {
305
306class CodeGeneration final : public ScopPass {
307public:
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
323 CodeGeneration() : ScopPass(ID) {}
324
325 /// Generate LLVM-IR for the SCoP @p S.
326 bool runOnScop(Scop &S) override {
327 AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
328 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
329 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
330 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
331 DL = &S.getFunction().getParent()->getDataLayout();
332 RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
333 return generateCode(S, AI&: *AI, LI&: *LI, DT&: *DT, SE&: *SE, RI&: *RI);
334 }
335
336 /// Register all analyses and transformation required.
337 void getAnalysisUsage(AnalysisUsage &AU) const override {
338 ScopPass::getAnalysisUsage(AU);
339
340 AU.addRequired<DominatorTreeWrapperPass>();
341 AU.addRequired<IslAstInfoWrapperPass>();
342 AU.addRequired<RegionInfoPass>();
343 AU.addRequired<ScalarEvolutionWrapperPass>();
344 AU.addRequired<ScopDetectionWrapperPass>();
345 AU.addRequired<ScopInfoRegionPass>();
346 AU.addRequired<LoopInfoWrapperPass>();
347
348 AU.addPreserved<DependenceInfo>();
349 AU.addPreserved<IslAstInfoWrapperPass>();
350
351 // FIXME: We do not yet add regions for the newly generated code to the
352 // region tree.
353 }
354};
355} // namespace
356
357PreservedAnalyses CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
358 ScopStandardAnalysisResults &AR,
359 SPMUpdater &U) {
360 auto &AI = SAM.getResult<IslAstAnalysis>(IR&: S, ExtraArgs&: AR);
361 if (generateCode(S, AI, LI&: AR.LI, DT&: AR.DT, SE&: AR.SE, RI&: AR.RI)) {
362 U.invalidateScop(S);
363 return PreservedAnalyses::none();
364 }
365
366 return PreservedAnalyses::all();
367}
368
369char CodeGeneration::ID = 1;
370
371Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
372
373INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
374 "Polly - Create LLVM-IR from SCoPs", false, false);
375INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
376INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
377INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
378INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
379INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
380INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
381INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
382 "Polly - Create LLVM-IR from SCoPs", false, false)
383

source code of polly/lib/CodeGen/CodeGeneration.cpp