Polly 19.0.0git
CodeGeneration.cpp
Go to the documentation of this file.
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
26#include "polly/CodeGen/Utils.h"
28#include "polly/LinkAllPasses.h"
29#include "polly/Options.h"
30#include "polly/ScopInfo.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
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
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(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, &errs()))
88 return;
89
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))
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.
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>(&*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, &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
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
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, *LI, *DT, *SE, *RI);
334 }
335
336 /// Register all analyses and transformation required.
337 void getAnalysisUsage(AnalysisUsage &AU) const override {
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
359 SPMUpdater &U) {
360 auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
361 if (generateCode(S, AI, AR.LI, AR.DT, AR.SE, 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);
376INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
377INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
379INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
381INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
382 "Polly - Create LLVM-IR from SCoPs", false, false)
static bool generateCode(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT, ScalarEvolution &SE, RegionInfo &RI)
STATISTIC(ScopsProcessed, "Number of SCoP processed")
static cl::opt< bool, true > XPerfMonitoring("polly-codegen-perf-monitoring", cl::desc("Add run-time performance monitoring"), cl::Hidden, cl::location(polly::PerfMonitoring), cl::cat(PollyCategory))
static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI)
static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI)
static cl::opt< bool > Verify("polly-codegen-verify", cl::desc("Verify the function generated by Polly"), cl::Hidden, cl::cat(PollyCategory))
static void removeLifetimeMarkers(Region *R)
Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from @R.
INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false)
INITIALIZE_PASS_END(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false) namespace
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
polly dump Polly Dump Function
llvm::cl::OptionCategory PollyCategory
#define POLLY_DEBUG(X)
Definition: PollyDebug.h:23
__isl_give isl_ast_expr * release()
bool is_null() const
__isl_give isl_ast_node * release()
Add Polly specifics when running IRBuilder.
Definition: IRBuilder.h:120
isl::ast_expr getRunCondition()
Get the run condition.
Definition: IslAst.cpp:563
void print(raw_ostream &O)
Definition: IslAst.cpp:719
IslAst & getIslAst()
Return the isl AST computed by this IslAstInfo.
Definition: IslAst.h:112
const std::shared_ptr< isl_ctx > getSharedIslCtx() const
Definition: IslAst.h:45
isl::ast_node getAst()
Definition: IslAst.cpp:559
void addParameters(__isl_take isl_set *Context)
void create(__isl_take isl_ast_node *Node)
virtual void finalize()
Finalize code generation.
bool preloadInvariantLoads()
Preload all memory loads that are invariant.
const ArrayRef< Function * > getParallelSubfunctions() const
Return the parallel subfunctions that have been created.
void allocateNewArrays(BBPair StartExitBlocks)
Allocate memory for all new arrays created by Polly.
Value * createRTC(isl_ast_expr *Condition)
Generate code that evaluates Condition at run-time.
void initialize()
Initialize the performance monitor.
void insertRegionEnd(llvm::Instruction *InsertBefore)
Mark the end of a timing region.
void insertRegionStart(llvm::Instruction *InsertBefore)
Mark the beginning of a timing region.
void invalidateScop(Scop &S)
Definition: ScopPass.h:202
Helper class to annotate newly generated SCoPs with metadata.
Definition: IRBuilder.h:44
void buildAliasScopes(Scop &S)
Build all alias scopes for the given SCoP.
Definition: IRBuilder.cpp:59
The legacy pass manager's analysis pass to compute scop information for a region.
Definition: ScopInfo.h:2677
ScopPass - This class adapts the RegionPass interface to allow convenient creation of passes that ope...
Definition: ScopPass.h:161
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: ScopPass.cpp:44
virtual bool runOnScop(Scop &S)=0
runOnScop - This method must be overloaded to perform the desired Polyhedral transformation or analys...
Static Control Part.
Definition: ScopInfo.h:1628
#define assert(exp)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::pair< llvm::BasicBlock *, llvm::BasicBlock * > BBPair
Type to hold region delimiters (entry & exit block).
Definition: Utils.h:31
bool PerfMonitoring
void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder)
Mark a basic block unreachable.
@ Value
MemoryKind::Value: Models an llvm::Value.
llvm::Pass * createCodeGenerationPass()
std::pair< BBPair, llvm::BranchInst * > executeScopConditionally(Scop &S, llvm::Value *RTC, llvm::DominatorTree &DT, llvm::RegionInfo &RI, llvm::LoopInfo &LI)
Execute a Scop conditionally wrt RTC.
llvm::IRBuilder< llvm::ConstantFolder, IRInserter > PollyIRBuilder
Definition: IRBuilder.h:141
AnalysisManager< Scop, ScopStandardAnalysisResults & > ScopAnalysisManager
Definition: ScopPass.h:46
void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT, llvm::LoopInfo *LI, llvm::RegionInfo *RI)
Simplify the region to have a single unconditional entry edge and a single exit edge.
PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM, ScopStandardAnalysisResults &AR, SPMUpdater &U)