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

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