1 | //===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===// |
---|---|
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 | // This file implements the BlockGenerator and VectorBlockGenerator classes, |
10 | // which generate sequential code and vectorized code for a polyhedral |
11 | // statement, respectively. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "polly/CodeGen/BlockGenerators.h" |
16 | #include "polly/CodeGen/IslExprBuilder.h" |
17 | #include "polly/CodeGen/RuntimeDebugBuilder.h" |
18 | #include "polly/Options.h" |
19 | #include "polly/ScopInfo.h" |
20 | #include "polly/Support/ISLTools.h" |
21 | #include "polly/Support/ScopHelper.h" |
22 | #include "polly/Support/VirtualInstruction.h" |
23 | #include "llvm/Analysis/DomTreeUpdater.h" |
24 | #include "llvm/Analysis/LoopInfo.h" |
25 | #include "llvm/Analysis/RegionInfo.h" |
26 | #include "llvm/Analysis/ScalarEvolution.h" |
27 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
28 | #include "llvm/Transforms/Utils/Local.h" |
29 | #include "isl/ast.h" |
30 | #include <deque> |
31 | |
32 | using namespace llvm; |
33 | using namespace polly; |
34 | |
35 | static cl::opt<bool> Aligned("enable-polly-aligned", |
36 | cl::desc("Assumed aligned memory accesses."), |
37 | cl::Hidden, cl::cat(PollyCategory)); |
38 | |
39 | bool PollyDebugPrinting; |
40 | static cl::opt<bool, true> DebugPrintingX( |
41 | "polly-codegen-add-debug-printing", |
42 | cl::desc("Add printf calls that show the values loaded/stored."), |
43 | cl::location(L&: PollyDebugPrinting), cl::Hidden, cl::cat(PollyCategory)); |
44 | |
45 | static cl::opt<bool> TraceStmts( |
46 | "polly-codegen-trace-stmts", |
47 | cl::desc("Add printf calls that print the statement being executed"), |
48 | cl::Hidden, cl::cat(PollyCategory)); |
49 | |
50 | static cl::opt<bool> TraceScalars( |
51 | "polly-codegen-trace-scalars", |
52 | cl::desc("Add printf calls that print the values of all scalar values " |
53 | "used in a statement. Requires -polly-codegen-trace-stmts."), |
54 | cl::Hidden, cl::cat(PollyCategory)); |
55 | |
56 | BlockGenerator::BlockGenerator( |
57 | PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, |
58 | AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap, |
59 | ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock) |
60 | : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT), GenDT(&DT), |
61 | GenLI(&LI), GenSE(&SE), ScalarMap(ScalarMap), EscapeMap(EscapeMap), |
62 | GlobalMap(GlobalMap), StartBlock(StartBlock) {} |
63 | |
64 | Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, |
65 | ValueMapT &BBMap, |
66 | LoopToScevMapT <S, |
67 | Loop *L) const { |
68 | if (!SE.isSCEVable(Ty: Old->getType())) |
69 | return nullptr; |
70 | |
71 | const SCEV *Scev = SE.getSCEVAtScope(V: Old, L); |
72 | if (!Scev) |
73 | return nullptr; |
74 | |
75 | if (isa<SCEVCouldNotCompute>(Val: Scev)) |
76 | return nullptr; |
77 | |
78 | ValueMapT VTV; |
79 | VTV.insert_range(R&: BBMap); |
80 | VTV.insert_range(R&: GlobalMap); |
81 | |
82 | Scop &S = *Stmt.getParent(); |
83 | const DataLayout &DL = S.getFunction().getDataLayout(); |
84 | auto IP = Builder.GetInsertPoint(); |
85 | |
86 | assert(IP != Builder.GetInsertBlock()->end() && |
87 | "Only instructions can be insert points for SCEVExpander"); |
88 | Value *Expanded = expandCodeFor( |
89 | S, SE, GenFn: Builder.GetInsertBlock()->getParent(), GenSE&: *GenSE, DL, Name: "polly", E: Scev, |
90 | Ty: Old->getType(), IP, VMap: &VTV, LoopMap: <S, RTCBB: StartBlock->getSinglePredecessor()); |
91 | |
92 | BBMap[Old] = Expanded; |
93 | return Expanded; |
94 | } |
95 | |
96 | Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, |
97 | LoopToScevMapT <S, Loop *L) const { |
98 | |
99 | auto lookupGlobally = [this](Value *Old) -> Value * { |
100 | Value *New = GlobalMap.lookup(Val: Old); |
101 | if (!New) |
102 | return nullptr; |
103 | |
104 | // Required by: |
105 | // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll |
106 | // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll |
107 | // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll |
108 | // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll |
109 | // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll |
110 | // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll |
111 | // GlobalMap should be a mapping from (value in original SCoP) to (copied |
112 | // value in generated SCoP), without intermediate mappings, which might |
113 | // easily require transitiveness as well. |
114 | if (Value *NewRemapped = GlobalMap.lookup(Val: New)) |
115 | New = NewRemapped; |
116 | |
117 | // No test case for this code. |
118 | if (Old->getType()->getScalarSizeInBits() < |
119 | New->getType()->getScalarSizeInBits()) |
120 | New = Builder.CreateTruncOrBitCast(V: New, DestTy: Old->getType()); |
121 | |
122 | return New; |
123 | }; |
124 | |
125 | Value *New = nullptr; |
126 | auto VUse = VirtualUse::create(UserStmt: &Stmt, UserScope: L, Val: Old, Virtual: true); |
127 | switch (VUse.getKind()) { |
128 | case VirtualUse::Block: |
129 | // BasicBlock are constants, but the BlockGenerator copies them. |
130 | New = BBMap.lookup(Val: Old); |
131 | break; |
132 | |
133 | case VirtualUse::Constant: |
134 | // Used by: |
135 | // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll |
136 | // Constants should not be redefined. In this case, the GlobalMap just |
137 | // contains a mapping to the same constant, which is unnecessary, but |
138 | // harmless. |
139 | if ((New = lookupGlobally(Old))) |
140 | break; |
141 | |
142 | assert(!BBMap.count(Old)); |
143 | New = Old; |
144 | break; |
145 | |
146 | case VirtualUse::ReadOnly: |
147 | assert(!GlobalMap.count(Old)); |
148 | |
149 | // Required for: |
150 | // * Isl/CodeGen/MemAccess/create_arrays.ll |
151 | // * Isl/CodeGen/read-only-scalars.ll |
152 | // * ScheduleOptimizer/pattern-matching-based-opts_10.ll |
153 | // For some reason these reload a read-only value. The reloaded value ends |
154 | // up in BBMap, buts its value should be identical. |
155 | // |
156 | // Required for: |
157 | // * Isl/CodeGen/OpenMP/single_loop_with_param.ll |
158 | // The parallel subfunctions need to reference the read-only value from the |
159 | // parent function, this is done by reloading them locally. |
160 | if ((New = BBMap.lookup(Val: Old))) |
161 | break; |
162 | |
163 | New = Old; |
164 | break; |
165 | |
166 | case VirtualUse::Synthesizable: |
167 | // Used by: |
168 | // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll |
169 | // * Isl/CodeGen/OpenMP/recomputed-srem.ll |
170 | // * Isl/CodeGen/OpenMP/reference-other-bb.ll |
171 | // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll |
172 | // For some reason synthesizable values end up in GlobalMap. Their values |
173 | // are the same as trySynthesizeNewValue would return. The legacy |
174 | // implementation prioritized GlobalMap, so this is what we do here as well. |
175 | // Ideally, synthesizable values should not end up in GlobalMap. |
176 | if ((New = lookupGlobally(Old))) |
177 | break; |
178 | |
179 | // Required for: |
180 | // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll |
181 | // * Isl/CodeGen/getNumberOfIterations.ll |
182 | // * Isl/CodeGen/non_affine_float_compare.ll |
183 | // * ScheduleOptimizer/pattern-matching-based-opts_10.ll |
184 | // Ideally, synthesizable values are synthesized by trySynthesizeNewValue, |
185 | // not precomputed (SCEVExpander has its own caching mechanism). |
186 | // These tests fail without this, but I think trySynthesizeNewValue would |
187 | // just re-synthesize the same instructions. |
188 | if ((New = BBMap.lookup(Val: Old))) |
189 | break; |
190 | |
191 | New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L); |
192 | break; |
193 | |
194 | case VirtualUse::Hoisted: |
195 | // TODO: Hoisted invariant loads should be found in GlobalMap only, but not |
196 | // redefined locally (which will be ignored anyway). That is, the following |
197 | // assertion should apply: assert(!BBMap.count(Old)) |
198 | |
199 | New = lookupGlobally(Old); |
200 | break; |
201 | |
202 | case VirtualUse::Intra: |
203 | case VirtualUse::Inter: |
204 | assert(!GlobalMap.count(Old) && |
205 | "Intra and inter-stmt values are never global"); |
206 | New = BBMap.lookup(Val: Old); |
207 | break; |
208 | } |
209 | assert(New && "Unexpected scalar dependence in region!"); |
210 | return New; |
211 | } |
212 | |
213 | void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst, |
214 | ValueMapT &BBMap, LoopToScevMapT <S) { |
215 | // We do not generate debug intrinsics as we did not investigate how to |
216 | // copy them correctly. At the current state, they just crash the code |
217 | // generation as the meta-data operands are not correctly copied. |
218 | if (isa<DbgInfoIntrinsic>(Val: Inst)) |
219 | return; |
220 | |
221 | Instruction *NewInst = Inst->clone(); |
222 | |
223 | // Replace old operands with the new ones. |
224 | for (Value *OldOperand : Inst->operands()) { |
225 | Value *NewOperand = |
226 | getNewValue(Stmt, Old: OldOperand, BBMap, LTS, L: getLoopForStmt(Stmt)); |
227 | |
228 | if (!NewOperand) { |
229 | assert(!isa<StoreInst>(NewInst) && |
230 | "Store instructions are always needed!"); |
231 | NewInst->deleteValue(); |
232 | return; |
233 | } |
234 | |
235 | // FIXME: We will encounter "NewOperand" again if used twice. getNewValue() |
236 | // is meant to be called on old values only. |
237 | NewInst->replaceUsesOfWith(From: OldOperand, To: NewOperand); |
238 | } |
239 | |
240 | Builder.Insert(I: NewInst); |
241 | BBMap[Inst] = NewInst; |
242 | |
243 | assert(NewInst->getModule() == Inst->getModule() && |
244 | "Expecting instructions to be in the same module"); |
245 | |
246 | if (!NewInst->getType()->isVoidTy()) |
247 | NewInst->setName("p_"+ Inst->getName()); |
248 | } |
249 | |
250 | Value * |
251 | BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, |
252 | ValueMapT &BBMap, LoopToScevMapT <S, |
253 | isl_id_to_ast_expr *NewAccesses) { |
254 | const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst); |
255 | return generateLocationAccessed( |
256 | Stmt, L: getLoopForStmt(Stmt), |
257 | Pointer: Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS, |
258 | NewAccesses, Id: MA.getId().release(), ExpectedType: MA.getAccessValue()->getType()); |
259 | } |
260 | |
261 | Value *BlockGenerator::generateLocationAccessed( |
262 | ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap, |
263 | LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id, |
264 | Type *ExpectedType) { |
265 | isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(hmap: NewAccesses, key: Id); |
266 | |
267 | if (AccessExpr) { |
268 | AccessExpr = isl_ast_expr_address_of(expr: AccessExpr); |
269 | return ExprBuilder->create(Expr: AccessExpr); |
270 | } |
271 | assert( |
272 | Pointer && |
273 | "If expression was not generated, must use the original pointer value"); |
274 | return getNewValue(Stmt, Old: Pointer, BBMap, LTS, L); |
275 | } |
276 | |
277 | Value * |
278 | BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L, |
279 | LoopToScevMapT <S, ValueMapT &BBMap, |
280 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
281 | if (Access.isLatestArrayKind()) |
282 | return generateLocationAccessed(Stmt&: *Access.getStatement(), L, Pointer: nullptr, BBMap, |
283 | LTS, NewAccesses, Id: Access.getId().release(), |
284 | ExpectedType: Access.getAccessValue()->getType()); |
285 | |
286 | return getOrCreateAlloca(Access); |
287 | } |
288 | |
289 | Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const { |
290 | auto *StmtBB = Stmt.getEntryBlock(); |
291 | return LI.getLoopFor(BB: StmtBB); |
292 | } |
293 | |
294 | Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load, |
295 | ValueMapT &BBMap, LoopToScevMapT <S, |
296 | isl_id_to_ast_expr *NewAccesses) { |
297 | if (Value *PreloadLoad = GlobalMap.lookup(Val: Load)) |
298 | return PreloadLoad; |
299 | |
300 | Value *NewPointer = |
301 | generateLocationAccessed(Stmt, Inst: Load, BBMap, LTS, NewAccesses); |
302 | Value *ScalarLoad = |
303 | Builder.CreateAlignedLoad(Ty: Load->getType(), Ptr: NewPointer, Align: Load->getAlign(), |
304 | Name: Load->getName() + "_p_scalar_"); |
305 | |
306 | if (PollyDebugPrinting) |
307 | RuntimeDebugBuilder::createCPUPrinter(Builder, args: "Load from ", args: NewPointer, |
308 | args: ": ", args: ScalarLoad, args: "\n"); |
309 | |
310 | return ScalarLoad; |
311 | } |
312 | |
313 | void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store, |
314 | ValueMapT &BBMap, LoopToScevMapT <S, |
315 | isl_id_to_ast_expr *NewAccesses) { |
316 | MemoryAccess &MA = Stmt.getArrayAccessFor(Inst: Store); |
317 | isl::set AccDom = MA.getAccessRelation().domain(); |
318 | std::string Subject = MA.getId().get_name(); |
319 | |
320 | generateConditionalExecution(Stmt, Subdomain: AccDom, Subject: Subject.c_str(), GenThenFunc: [&, this]() { |
321 | Value *NewPointer = |
322 | generateLocationAccessed(Stmt, Inst: Store, BBMap, LTS, NewAccesses); |
323 | Value *ValueOperand = getNewValue(Stmt, Old: Store->getValueOperand(), BBMap, |
324 | LTS, L: getLoopForStmt(Stmt)); |
325 | |
326 | if (PollyDebugPrinting) |
327 | RuntimeDebugBuilder::createCPUPrinter(Builder, args: "Store to ", args: NewPointer, |
328 | args: ": ", args: ValueOperand, args: "\n"); |
329 | |
330 | Builder.CreateAlignedStore(Val: ValueOperand, Ptr: NewPointer, Align: Store->getAlign()); |
331 | }); |
332 | } |
333 | |
334 | bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) { |
335 | Loop *L = getLoopForStmt(Stmt); |
336 | return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) && |
337 | canSynthesize(V: Inst, S: *Stmt.getParent(), SE: &SE, Scope: L); |
338 | } |
339 | |
340 | void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst, |
341 | ValueMapT &BBMap, LoopToScevMapT <S, |
342 | isl_id_to_ast_expr *NewAccesses) { |
343 | // Terminator instructions control the control flow. They are explicitly |
344 | // expressed in the clast and do not need to be copied. |
345 | if (Inst->isTerminator()) |
346 | return; |
347 | |
348 | // Synthesizable statements will be generated on-demand. |
349 | if (canSyntheziseInStmt(Stmt, Inst)) |
350 | return; |
351 | |
352 | if (auto *Load = dyn_cast<LoadInst>(Val: Inst)) { |
353 | Value *NewLoad = generateArrayLoad(Stmt, Load, BBMap, LTS, NewAccesses); |
354 | // Compute NewLoad before its insertion in BBMap to make the insertion |
355 | // deterministic. |
356 | BBMap[Load] = NewLoad; |
357 | return; |
358 | } |
359 | |
360 | if (auto *Store = dyn_cast<StoreInst>(Val: Inst)) { |
361 | // Identified as redundant by -polly-simplify. |
362 | if (!Stmt.getArrayAccessOrNULLFor(Inst: Store)) |
363 | return; |
364 | |
365 | generateArrayStore(Stmt, Store, BBMap, LTS, NewAccesses); |
366 | return; |
367 | } |
368 | |
369 | if (auto *PHI = dyn_cast<PHINode>(Val: Inst)) { |
370 | copyPHIInstruction(Stmt, PHI, BBMap, LTS); |
371 | return; |
372 | } |
373 | |
374 | // Skip some special intrinsics for which we do not adjust the semantics to |
375 | // the new schedule. All others are handled like every other instruction. |
376 | if (isIgnoredIntrinsic(V: Inst)) |
377 | return; |
378 | |
379 | copyInstScalar(Stmt, Inst, BBMap, LTS); |
380 | } |
381 | |
382 | void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) { |
383 | auto NewBB = Builder.GetInsertBlock(); |
384 | for (auto I = NewBB->rbegin(); I != NewBB->rend(); I++) { |
385 | Instruction *NewInst = &*I; |
386 | |
387 | if (!isInstructionTriviallyDead(I: NewInst)) |
388 | continue; |
389 | |
390 | for (auto Pair : BBMap) |
391 | if (Pair.second == NewInst) { |
392 | BBMap.erase(Val: Pair.first); |
393 | } |
394 | |
395 | NewInst->eraseFromParent(); |
396 | I = NewBB->rbegin(); |
397 | } |
398 | } |
399 | |
400 | void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, |
401 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
402 | assert(Stmt.isBlockStmt() && |
403 | "Only block statements can be copied by the block generator"); |
404 | |
405 | ValueMapT BBMap; |
406 | |
407 | BasicBlock *BB = Stmt.getBasicBlock(); |
408 | copyBB(Stmt, BB, BBMap, LTS, NewAccesses); |
409 | removeDeadInstructions(BB, BBMap); |
410 | } |
411 | |
412 | BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) { |
413 | BasicBlock *CopyBB = SplitBlock(Old: Builder.GetInsertBlock(), |
414 | SplitPt: Builder.GetInsertPoint(), DT: GenDT, LI: GenLI); |
415 | CopyBB->setName("polly.stmt."+ BB->getName()); |
416 | return CopyBB; |
417 | } |
418 | |
419 | BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, |
420 | ValueMapT &BBMap, LoopToScevMapT <S, |
421 | isl_id_to_ast_expr *NewAccesses) { |
422 | BasicBlock *CopyBB = splitBB(BB); |
423 | Builder.SetInsertPoint(TheBB: CopyBB, IP: CopyBB->begin()); |
424 | generateScalarLoads(Stmt, LTS, BBMap, NewAccesses); |
425 | generateBeginStmtTrace(Stmt, LTS, BBMap); |
426 | |
427 | copyBB(Stmt, BB, BBCopy: CopyBB, BBMap, LTS, NewAccesses); |
428 | |
429 | // After a basic block was copied store all scalars that escape this block in |
430 | // their alloca. |
431 | generateScalarStores(Stmt, LTS, BBMap, NewAccesses); |
432 | return CopyBB; |
433 | } |
434 | |
435 | void BlockGenerator::switchGeneratedFunc(Function *GenFn, DominatorTree *GenDT, |
436 | LoopInfo *GenLI, |
437 | ScalarEvolution *GenSE) { |
438 | assert(GenFn == GenDT->getRoot()->getParent()); |
439 | assert(GenLI->getTopLevelLoops().empty() || |
440 | GenFn == GenLI->getTopLevelLoops().front()->getHeader()->getParent()); |
441 | this->GenDT = GenDT; |
442 | this->GenLI = GenLI; |
443 | this->GenSE = GenSE; |
444 | } |
445 | |
446 | void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB, |
447 | ValueMapT &BBMap, LoopToScevMapT <S, |
448 | isl_id_to_ast_expr *NewAccesses) { |
449 | // Block statements and the entry blocks of region statement are code |
450 | // generated from instruction lists. This allow us to optimize the |
451 | // instructions that belong to a certain scop statement. As the code |
452 | // structure of region statements might be arbitrary complex, optimizing the |
453 | // instruction list is not yet supported. |
454 | if (Stmt.isBlockStmt() || (Stmt.isRegionStmt() && Stmt.getEntryBlock() == BB)) |
455 | for (Instruction *Inst : Stmt.getInstructions()) |
456 | copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses); |
457 | else |
458 | for (Instruction &Inst : *BB) |
459 | copyInstruction(Stmt, Inst: &Inst, BBMap, LTS, NewAccesses); |
460 | } |
461 | |
462 | Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) { |
463 | assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind"); |
464 | |
465 | return getOrCreateAlloca(Array: Access.getLatestScopArrayInfo()); |
466 | } |
467 | |
468 | Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) { |
469 | assert(!Array->isArrayKind() && "Trying to get alloca for array kind"); |
470 | |
471 | auto &Addr = ScalarMap[Array]; |
472 | |
473 | if (Addr) { |
474 | // Allow allocas to be (temporarily) redirected once by adding a new |
475 | // old-alloca-addr to new-addr mapping to GlobalMap. This functionality |
476 | // is used for example by the OpenMP code generation where a first use |
477 | // of a scalar while still in the host code allocates a normal alloca with |
478 | // getOrCreateAlloca. When the values of this scalar are accessed during |
479 | // the generation of the parallel subfunction, these values are copied over |
480 | // to the parallel subfunction and each request for a scalar alloca slot |
481 | // must be forwarded to the temporary in-subfunction slot. This mapping is |
482 | // removed when the subfunction has been generated and again normal host |
483 | // code is generated. Due to the following reasons it is not possible to |
484 | // perform the GlobalMap lookup right after creating the alloca below, but |
485 | // instead we need to check GlobalMap at each call to getOrCreateAlloca: |
486 | // |
487 | // 1) GlobalMap may be changed multiple times (for each parallel loop), |
488 | // 2) The temporary mapping is commonly only known after the initial |
489 | // alloca has already been generated, and |
490 | // 3) The original alloca value must be restored after leaving the |
491 | // sub-function. |
492 | if (Value *NewAddr = GlobalMap.lookup(Val: &*Addr)) |
493 | return NewAddr; |
494 | return Addr; |
495 | } |
496 | |
497 | Type *Ty = Array->getElementType(); |
498 | Value *ScalarBase = Array->getBasePtr(); |
499 | std::string NameExt; |
500 | if (Array->isPHIKind()) |
501 | NameExt = ".phiops"; |
502 | else |
503 | NameExt = ".s2a"; |
504 | |
505 | const DataLayout &DL = Builder.GetInsertBlock()->getDataLayout(); |
506 | |
507 | Addr = |
508 | new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr, |
509 | DL.getPrefTypeAlign(Ty), ScalarBase->getName() + NameExt); |
510 | BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock(); |
511 | Addr->insertBefore(InsertPos: EntryBB->getFirstInsertionPt()); |
512 | |
513 | return Addr; |
514 | } |
515 | |
516 | void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) { |
517 | Instruction *Inst = cast<Instruction>(Val: Array->getBasePtr()); |
518 | |
519 | // If there are escape users we get the alloca for this instruction and put it |
520 | // in the EscapeMap for later finalization. Lastly, if the instruction was |
521 | // copied multiple times we already did this and can exit. |
522 | if (EscapeMap.count(Key: Inst)) |
523 | return; |
524 | |
525 | EscapeUserVectorTy EscapeUsers; |
526 | for (User *U : Inst->users()) { |
527 | |
528 | // Non-instruction user will never escape. |
529 | Instruction *UI = dyn_cast<Instruction>(Val: U); |
530 | if (!UI) |
531 | continue; |
532 | |
533 | if (S.contains(I: UI)) |
534 | continue; |
535 | |
536 | EscapeUsers.push_back(Elt: UI); |
537 | } |
538 | |
539 | // Exit if no escape uses were found. |
540 | if (EscapeUsers.empty()) |
541 | return; |
542 | |
543 | // Get or create an escape alloca for this instruction. |
544 | auto *ScalarAddr = getOrCreateAlloca(Array); |
545 | |
546 | // Remember that this instruction has escape uses and the escape alloca. |
547 | EscapeMap[Inst] = std::make_pair(x&: ScalarAddr, y: std::move(EscapeUsers)); |
548 | } |
549 | |
550 | void BlockGenerator::generateScalarLoads( |
551 | ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, |
552 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
553 | for (MemoryAccess *MA : Stmt) { |
554 | if (MA->isOriginalArrayKind() || MA->isWrite()) |
555 | continue; |
556 | |
557 | #ifndef NDEBUG |
558 | auto StmtDom = |
559 | Stmt.getDomain().intersect_params(params: Stmt.getParent()->getContext()); |
560 | auto AccDom = MA->getAccessRelation().domain(); |
561 | assert(!StmtDom.is_subset(AccDom).is_false() && |
562 | "Scalar must be loaded in all statement instances"); |
563 | #endif |
564 | |
565 | auto *Address = |
566 | getImplicitAddress(Access&: *MA, L: getLoopForStmt(Stmt), LTS, BBMap, NewAccesses); |
567 | BBMap[MA->getAccessValue()] = Builder.CreateLoad( |
568 | Ty: MA->getElementType(), Ptr: Address, Name: Address->getName() + ".reload"); |
569 | } |
570 | } |
571 | |
572 | Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt, |
573 | const isl::set &Subdomain) { |
574 | isl::ast_build AstBuild = Stmt.getAstBuild(); |
575 | isl::set Domain = Stmt.getDomain(); |
576 | |
577 | isl::union_map USchedule = AstBuild.get_schedule(); |
578 | USchedule = USchedule.intersect_domain(uset: Domain); |
579 | |
580 | assert(!USchedule.is_empty()); |
581 | isl::map Schedule = isl::map::from_union_map(umap: USchedule); |
582 | |
583 | isl::set ScheduledDomain = Schedule.range(); |
584 | isl::set ScheduledSet = Subdomain.apply(map: Schedule); |
585 | |
586 | isl::ast_build RestrictedBuild = AstBuild.restrict(set: ScheduledDomain); |
587 | |
588 | isl::ast_expr IsInSet = RestrictedBuild.expr_from(set: ScheduledSet); |
589 | Value *IsInSetExpr = ExprBuilder->create(Expr: IsInSet.copy()); |
590 | IsInSetExpr = Builder.CreateICmpNE( |
591 | LHS: IsInSetExpr, RHS: ConstantInt::get(Ty: IsInSetExpr->getType(), V: 0)); |
592 | |
593 | return IsInSetExpr; |
594 | } |
595 | |
596 | void BlockGenerator::generateConditionalExecution( |
597 | ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject, |
598 | const std::function<void()> &GenThenFunc) { |
599 | isl::set StmtDom = Stmt.getDomain(); |
600 | |
601 | // If the condition is a tautology, don't generate a condition around the |
602 | // code. |
603 | bool IsPartialWrite = |
604 | !StmtDom.intersect_params(params: Stmt.getParent()->getContext()) |
605 | .is_subset(set2: Subdomain); |
606 | if (!IsPartialWrite) { |
607 | GenThenFunc(); |
608 | return; |
609 | } |
610 | |
611 | // Generate the condition. |
612 | Value *Cond = buildContainsCondition(Stmt, Subdomain); |
613 | |
614 | // Don't call GenThenFunc if it is never executed. An ast index expression |
615 | // might not be defined in this case. |
616 | if (auto *Const = dyn_cast<ConstantInt>(Val: Cond)) |
617 | if (Const->isZero()) |
618 | return; |
619 | |
620 | BasicBlock *HeadBlock = Builder.GetInsertBlock(); |
621 | StringRef BlockName = HeadBlock->getName(); |
622 | |
623 | // Generate the conditional block. |
624 | DomTreeUpdater DTU(GenDT, DomTreeUpdater::UpdateStrategy::Eager); |
625 | SplitBlockAndInsertIfThen(Cond, SplitBefore: Builder.GetInsertPoint(), Unreachable: false, BranchWeights: nullptr, |
626 | DTU: &DTU, LI: GenLI); |
627 | BranchInst *Branch = cast<BranchInst>(Val: HeadBlock->getTerminator()); |
628 | BasicBlock *ThenBlock = Branch->getSuccessor(i: 0); |
629 | BasicBlock *TailBlock = Branch->getSuccessor(i: 1); |
630 | |
631 | // Assign descriptive names. |
632 | if (auto *CondInst = dyn_cast<Instruction>(Val: Cond)) |
633 | CondInst->setName("polly."+ Subject + ".cond"); |
634 | ThenBlock->setName(BlockName + "."+ Subject + ".partial"); |
635 | TailBlock->setName(BlockName + ".cont"); |
636 | |
637 | // Put the client code into the conditional block and continue in the merge |
638 | // block afterwards. |
639 | Builder.SetInsertPoint(TheBB: ThenBlock, IP: ThenBlock->getFirstInsertionPt()); |
640 | GenThenFunc(); |
641 | Builder.SetInsertPoint(TheBB: TailBlock, IP: TailBlock->getFirstInsertionPt()); |
642 | } |
643 | |
644 | static std::string getInstName(Value *Val) { |
645 | std::string Result; |
646 | raw_string_ostream OS(Result); |
647 | Val->printAsOperand(O&: OS, PrintType: false); |
648 | return Result; |
649 | } |
650 | |
651 | void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S, |
652 | ValueMapT &BBMap) { |
653 | if (!TraceStmts) |
654 | return; |
655 | |
656 | Scop *S = Stmt.getParent(); |
657 | const char *BaseName = Stmt.getBaseName(); |
658 | |
659 | isl::ast_build AstBuild = Stmt.getAstBuild(); |
660 | isl::set Domain = Stmt.getDomain(); |
661 | |
662 | isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(uset: Domain); |
663 | isl::map Schedule = isl::map::from_union_map(umap: USchedule); |
664 | assert(Schedule.is_empty().is_false() && |
665 | "The stmt must have a valid instance"); |
666 | |
667 | isl::multi_pw_aff ScheduleMultiPwAff = |
668 | isl::pw_multi_aff::from_map(map: Schedule.reverse()); |
669 | isl::ast_build RestrictedBuild = AstBuild.restrict(set: Schedule.range()); |
670 | |
671 | // Sequence of strings to print. |
672 | SmallVector<llvm::Value *, 8> Values; |
673 | |
674 | // Print the name of the statement. |
675 | // TODO: Indent by the depth of the statement instance in the schedule tree. |
676 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: BaseName)); |
677 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: "(")); |
678 | |
679 | // Add the coordinate of the statement instance. |
680 | for (unsigned i : rangeIslSize(Begin: 0, End: ScheduleMultiPwAff.dim(type: isl::dim::out))) { |
681 | if (i > 0) |
682 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: ",")); |
683 | |
684 | isl::ast_expr IsInSet = RestrictedBuild.expr_from(pa: ScheduleMultiPwAff.at(pos: i)); |
685 | Values.push_back(Elt: ExprBuilder->create(Expr: IsInSet.copy())); |
686 | } |
687 | |
688 | if (TraceScalars) { |
689 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: ")")); |
690 | DenseSet<Instruction *> Encountered; |
691 | |
692 | // Add the value of each scalar (and the result of PHIs) used in the |
693 | // statement. |
694 | // TODO: Values used in region-statements. |
695 | for (Instruction *Inst : Stmt.insts()) { |
696 | if (!RuntimeDebugBuilder::isPrintable(Ty: Inst->getType())) |
697 | continue; |
698 | |
699 | if (isa<PHINode>(Val: Inst)) { |
700 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: " ")); |
701 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString( |
702 | Builder, Str: getInstName(Val: Inst))); |
703 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: "=")); |
704 | Values.push_back(Elt: getNewValue(Stmt, Old: Inst, BBMap, LTS, |
705 | L: LI.getLoopFor(BB: Inst->getParent()))); |
706 | } else { |
707 | for (Value *Op : Inst->operand_values()) { |
708 | // Do not print values that cannot change during the execution of the |
709 | // SCoP. |
710 | auto *OpInst = dyn_cast<Instruction>(Val: Op); |
711 | if (!OpInst) |
712 | continue; |
713 | if (!S->contains(I: OpInst)) |
714 | continue; |
715 | |
716 | // Print each scalar at most once, and exclude values defined in the |
717 | // statement itself. |
718 | if (Encountered.count(V: OpInst)) |
719 | continue; |
720 | |
721 | Values.push_back( |
722 | Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: " ")); |
723 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString( |
724 | Builder, Str: getInstName(Val: OpInst))); |
725 | Values.push_back( |
726 | Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: "=")); |
727 | Values.push_back(Elt: getNewValue(Stmt, Old: OpInst, BBMap, LTS, |
728 | L: LI.getLoopFor(BB: Inst->getParent()))); |
729 | Encountered.insert(V: OpInst); |
730 | } |
731 | } |
732 | |
733 | Encountered.insert(V: Inst); |
734 | } |
735 | |
736 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: "\n")); |
737 | } else { |
738 | Values.push_back(Elt: RuntimeDebugBuilder::getPrintableString(Builder, Str: ")\n")); |
739 | } |
740 | |
741 | RuntimeDebugBuilder::createCPUPrinter(Builder, args: ArrayRef<Value *>(Values)); |
742 | } |
743 | |
744 | void BlockGenerator::generateScalarStores( |
745 | ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, |
746 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
747 | Loop *L = LI.getLoopFor(BB: Stmt.getBasicBlock()); |
748 | |
749 | assert(Stmt.isBlockStmt() && |
750 | "Region statements need to use the generateScalarStores() function in " |
751 | "the RegionGenerator"); |
752 | |
753 | for (MemoryAccess *MA : Stmt) { |
754 | if (MA->isOriginalArrayKind() || MA->isRead()) |
755 | continue; |
756 | |
757 | isl::set AccDom = MA->getAccessRelation().domain(); |
758 | std::string Subject = MA->getId().get_name(); |
759 | |
760 | generateConditionalExecution( |
761 | Stmt, Subdomain: AccDom, Subject: Subject.c_str(), GenThenFunc: [&, this, MA]() { |
762 | Value *Val = MA->getAccessValue(); |
763 | if (MA->isAnyPHIKind()) { |
764 | assert(MA->getIncoming().size() >= 1 && |
765 | "Block statements have exactly one exiting block, or " |
766 | "multiple but " |
767 | "with same incoming block and value"); |
768 | assert(std::all_of(MA->getIncoming().begin(), |
769 | MA->getIncoming().end(), |
770 | [&](std::pair<BasicBlock *, Value *> p) -> bool { |
771 | return p.first == Stmt.getBasicBlock(); |
772 | }) && |
773 | "Incoming block must be statement's block"); |
774 | Val = MA->getIncoming()[0].second; |
775 | } |
776 | auto Address = getImplicitAddress(Access&: *MA, L: getLoopForStmt(Stmt), LTS, |
777 | BBMap, NewAccesses); |
778 | |
779 | Val = getNewValue(Stmt, Old: Val, BBMap, LTS, L); |
780 | assert((!isa<Instruction>(Val) || |
781 | DT.dominates(cast<Instruction>(Val)->getParent(), |
782 | Builder.GetInsertBlock())) && |
783 | "Domination violation"); |
784 | assert((!isa<Instruction>(Address) || |
785 | DT.dominates(cast<Instruction>(Address)->getParent(), |
786 | Builder.GetInsertBlock())) && |
787 | "Domination violation"); |
788 | |
789 | Builder.CreateStore(Val, Ptr: Address); |
790 | }); |
791 | } |
792 | } |
793 | |
794 | void BlockGenerator::createScalarInitialization(Scop &S) { |
795 | BasicBlock *ExitBB = S.getExit(); |
796 | BasicBlock *PreEntryBB = S.getEnteringBlock(); |
797 | |
798 | Builder.SetInsertPoint(TheBB: StartBlock, IP: StartBlock->begin()); |
799 | |
800 | for (auto &Array : S.arrays()) { |
801 | if (Array->getNumberOfDimensions() != 0) |
802 | continue; |
803 | if (Array->isPHIKind()) { |
804 | // For PHI nodes, the only values we need to store are the ones that |
805 | // reach the PHI node from outside the region. In general there should |
806 | // only be one such incoming edge and this edge should enter through |
807 | // 'PreEntryBB'. |
808 | auto PHI = cast<PHINode>(Val: Array->getBasePtr()); |
809 | |
810 | for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++) |
811 | if (!S.contains(BB: *BI) && *BI != PreEntryBB) |
812 | llvm_unreachable("Incoming edges from outside the scop should always " |
813 | "come from PreEntryBB"); |
814 | |
815 | int Idx = PHI->getBasicBlockIndex(BB: PreEntryBB); |
816 | if (Idx < 0) |
817 | continue; |
818 | |
819 | Value *ScalarValue = PHI->getIncomingValue(i: Idx); |
820 | |
821 | Builder.CreateStore(Val: ScalarValue, Ptr: getOrCreateAlloca(Array)); |
822 | continue; |
823 | } |
824 | |
825 | auto *Inst = dyn_cast<Instruction>(Val: Array->getBasePtr()); |
826 | |
827 | if (Inst && S.contains(I: Inst)) |
828 | continue; |
829 | |
830 | // PHI nodes that are not marked as such in their SAI object are either exit |
831 | // PHI nodes we model as common scalars but without initialization, or |
832 | // incoming phi nodes that need to be initialized. Check if the first is the |
833 | // case for Inst and do not create and initialize memory if so. |
834 | if (auto *PHI = dyn_cast_or_null<PHINode>(Val: Inst)) |
835 | if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(BB: ExitBB) >= 0) |
836 | continue; |
837 | |
838 | Builder.CreateStore(Val: Array->getBasePtr(), Ptr: getOrCreateAlloca(Array)); |
839 | } |
840 | } |
841 | |
842 | void BlockGenerator::createScalarFinalization(Scop &S) { |
843 | // The exit block of the __unoptimized__ region. |
844 | BasicBlock *ExitBB = S.getExitingBlock(); |
845 | // The merge block __just after__ the region and the optimized region. |
846 | BasicBlock *MergeBB = S.getExit(); |
847 | |
848 | // The exit block of the __optimized__ region. |
849 | BasicBlock *OptExitBB = *(pred_begin(BB: MergeBB)); |
850 | if (OptExitBB == ExitBB) |
851 | OptExitBB = *(++pred_begin(BB: MergeBB)); |
852 | |
853 | Builder.SetInsertPoint(TheBB: OptExitBB, IP: OptExitBB->getTerminator()->getIterator()); |
854 | for (const auto &EscapeMapping : EscapeMap) { |
855 | // Extract the escaping instruction and the escaping users as well as the |
856 | // alloca the instruction was demoted to. |
857 | Instruction *EscapeInst = EscapeMapping.first; |
858 | const auto &EscapeMappingValue = EscapeMapping.second; |
859 | const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second; |
860 | auto *ScalarAddr = cast<AllocaInst>(Val: &*EscapeMappingValue.first); |
861 | |
862 | // Reload the demoted instruction in the optimized version of the SCoP. |
863 | Value *EscapeInstReload = |
864 | Builder.CreateLoad(Ty: ScalarAddr->getAllocatedType(), Ptr: ScalarAddr, |
865 | Name: EscapeInst->getName() + ".final_reload"); |
866 | EscapeInstReload = |
867 | Builder.CreateBitOrPointerCast(V: EscapeInstReload, DestTy: EscapeInst->getType()); |
868 | |
869 | // Create the merge PHI that merges the optimized and unoptimized version. |
870 | PHINode *MergePHI = PHINode::Create(Ty: EscapeInst->getType(), NumReservedValues: 2, |
871 | NameStr: EscapeInst->getName() + ".merge"); |
872 | MergePHI->insertBefore(InsertPos: MergeBB->getFirstInsertionPt()); |
873 | |
874 | // Add the respective values to the merge PHI. |
875 | MergePHI->addIncoming(V: EscapeInstReload, BB: OptExitBB); |
876 | MergePHI->addIncoming(V: EscapeInst, BB: ExitBB); |
877 | |
878 | // The information of scalar evolution about the escaping instruction needs |
879 | // to be revoked so the new merged instruction will be used. |
880 | if (SE.isSCEVable(Ty: EscapeInst->getType())) |
881 | SE.forgetValue(V: EscapeInst); |
882 | |
883 | // Replace all uses of the demoted instruction with the merge PHI. |
884 | for (Instruction *EUser : EscapeUsers) |
885 | EUser->replaceUsesOfWith(From: EscapeInst, To: MergePHI); |
886 | } |
887 | } |
888 | |
889 | void BlockGenerator::findOutsideUsers(Scop &S) { |
890 | for (auto &Array : S.arrays()) { |
891 | |
892 | if (Array->getNumberOfDimensions() != 0) |
893 | continue; |
894 | |
895 | if (Array->isPHIKind()) |
896 | continue; |
897 | |
898 | auto *Inst = dyn_cast<Instruction>(Val: Array->getBasePtr()); |
899 | |
900 | if (!Inst) |
901 | continue; |
902 | |
903 | // Scop invariant hoisting moves some of the base pointers out of the scop. |
904 | // We can ignore these, as the invariant load hoisting already registers the |
905 | // relevant outside users. |
906 | if (!S.contains(I: Inst)) |
907 | continue; |
908 | |
909 | handleOutsideUsers(S, Array); |
910 | } |
911 | } |
912 | |
913 | void BlockGenerator::createExitPHINodeMerges(Scop &S) { |
914 | if (S.hasSingleExitEdge()) |
915 | return; |
916 | |
917 | auto *ExitBB = S.getExitingBlock(); |
918 | auto *MergeBB = S.getExit(); |
919 | auto *AfterMergeBB = MergeBB->getSingleSuccessor(); |
920 | BasicBlock *OptExitBB = *(pred_begin(BB: MergeBB)); |
921 | if (OptExitBB == ExitBB) |
922 | OptExitBB = *(++pred_begin(BB: MergeBB)); |
923 | |
924 | Builder.SetInsertPoint(TheBB: OptExitBB, IP: OptExitBB->getTerminator()->getIterator()); |
925 | |
926 | for (auto &SAI : S.arrays()) { |
927 | auto *Val = SAI->getBasePtr(); |
928 | |
929 | // Only Value-like scalars need a merge PHI. Exit block PHIs receive either |
930 | // the original PHI's value or the reloaded incoming values from the |
931 | // generated code. An llvm::Value is merged between the original code's |
932 | // value or the generated one. |
933 | if (!SAI->isExitPHIKind()) |
934 | continue; |
935 | |
936 | PHINode *PHI = dyn_cast<PHINode>(Val); |
937 | if (!PHI) |
938 | continue; |
939 | |
940 | if (PHI->getParent() != AfterMergeBB) |
941 | continue; |
942 | |
943 | std::string Name = PHI->getName().str(); |
944 | Value *ScalarAddr = getOrCreateAlloca(Array: SAI); |
945 | Value *Reload = Builder.CreateLoad(Ty: SAI->getElementType(), Ptr: ScalarAddr, |
946 | Name: Name + ".ph.final_reload"); |
947 | Reload = Builder.CreateBitOrPointerCast(V: Reload, DestTy: PHI->getType()); |
948 | Value *OriginalValue = PHI->getIncomingValueForBlock(BB: MergeBB); |
949 | assert((!isa<Instruction>(OriginalValue) || |
950 | cast<Instruction>(OriginalValue)->getParent() != MergeBB) && |
951 | "Original value must no be one we just generated."); |
952 | auto *MergePHI = PHINode::Create(Ty: PHI->getType(), NumReservedValues: 2, NameStr: Name + ".ph.merge"); |
953 | MergePHI->insertBefore(InsertPos: MergeBB->getFirstInsertionPt()); |
954 | MergePHI->addIncoming(V: Reload, BB: OptExitBB); |
955 | MergePHI->addIncoming(V: OriginalValue, BB: ExitBB); |
956 | int Idx = PHI->getBasicBlockIndex(BB: MergeBB); |
957 | PHI->setIncomingValue(i: Idx, V: MergePHI); |
958 | } |
959 | } |
960 | |
961 | void BlockGenerator::invalidateScalarEvolution(Scop &S) { |
962 | for (auto &Stmt : S) |
963 | if (Stmt.isCopyStmt()) |
964 | continue; |
965 | else if (Stmt.isBlockStmt()) |
966 | for (auto &Inst : *Stmt.getBasicBlock()) |
967 | SE.forgetValue(V: &Inst); |
968 | else if (Stmt.isRegionStmt()) |
969 | for (auto *BB : Stmt.getRegion()->blocks()) |
970 | for (auto &Inst : *BB) |
971 | SE.forgetValue(V: &Inst); |
972 | else |
973 | llvm_unreachable("Unexpected statement type found"); |
974 | |
975 | // Invalidate SCEV of loops surrounding the EscapeUsers. |
976 | for (const auto &EscapeMapping : EscapeMap) { |
977 | const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second; |
978 | for (Instruction *EUser : EscapeUsers) { |
979 | if (Loop *L = LI.getLoopFor(BB: EUser->getParent())) |
980 | while (L) { |
981 | SE.forgetLoop(L); |
982 | L = L->getParentLoop(); |
983 | } |
984 | } |
985 | } |
986 | } |
987 | |
988 | void BlockGenerator::finalizeSCoP(Scop &S) { |
989 | findOutsideUsers(S); |
990 | createScalarInitialization(S); |
991 | createExitPHINodeMerges(S); |
992 | createScalarFinalization(S); |
993 | invalidateScalarEvolution(S); |
994 | } |
995 | |
996 | BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB, |
997 | BasicBlock *BBCopy) { |
998 | |
999 | BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock(); |
1000 | BasicBlock *BBCopyIDom = EndBlockMap.lookup(Val: BBIDom); |
1001 | |
1002 | if (BBCopyIDom) |
1003 | GenDT->changeImmediateDominator(BB: BBCopy, NewBB: BBCopyIDom); |
1004 | |
1005 | return StartBlockMap.lookup(Val: BBIDom); |
1006 | } |
1007 | |
1008 | // This is to determine whether an llvm::Value (defined in @p BB) is usable when |
1009 | // leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock()) |
1010 | // does not work in cases where the exit block has edges from outside the |
1011 | // region. In that case the llvm::Value would never be usable in in the exit |
1012 | // block. The RegionGenerator however creates an new exit block ('ExitBBCopy') |
1013 | // for the subregion's exiting edges only. We need to determine whether an |
1014 | // llvm::Value is usable in there. We do this by checking whether it dominates |
1015 | // all exiting blocks individually. |
1016 | static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R, |
1017 | BasicBlock *BB) { |
1018 | for (auto ExitingBB : predecessors(BB: R->getExit())) { |
1019 | // Check for non-subregion incoming edges. |
1020 | if (!R->contains(BB: ExitingBB)) |
1021 | continue; |
1022 | |
1023 | if (!DT.dominates(A: BB, B: ExitingBB)) |
1024 | return false; |
1025 | } |
1026 | |
1027 | return true; |
1028 | } |
1029 | |
1030 | // Find the direct dominator of the subregion's exit block if the subregion was |
1031 | // simplified. |
1032 | static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) { |
1033 | BasicBlock *Common = nullptr; |
1034 | for (auto ExitingBB : predecessors(BB: R->getExit())) { |
1035 | // Check for non-subregion incoming edges. |
1036 | if (!R->contains(BB: ExitingBB)) |
1037 | continue; |
1038 | |
1039 | // First exiting edge. |
1040 | if (!Common) { |
1041 | Common = ExitingBB; |
1042 | continue; |
1043 | } |
1044 | |
1045 | Common = DT.findNearestCommonDominator(A: Common, B: ExitingBB); |
1046 | } |
1047 | |
1048 | assert(Common && R->contains(Common)); |
1049 | return Common; |
1050 | } |
1051 | |
1052 | void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, |
1053 | __isl_keep isl_id_to_ast_expr *IdToAstExp) { |
1054 | assert(Stmt.isRegionStmt() && |
1055 | "Only region statements can be copied by the region generator"); |
1056 | |
1057 | // Forget all old mappings. |
1058 | StartBlockMap.clear(); |
1059 | EndBlockMap.clear(); |
1060 | RegionMaps.clear(); |
1061 | IncompletePHINodeMap.clear(); |
1062 | |
1063 | // Collection of all values related to this subregion. |
1064 | ValueMapT ValueMap; |
1065 | |
1066 | // The region represented by the statement. |
1067 | Region *R = Stmt.getRegion(); |
1068 | |
1069 | // Create a dedicated entry for the region where we can reload all demoted |
1070 | // inputs. |
1071 | BasicBlock *EntryBB = R->getEntry(); |
1072 | BasicBlock *EntryBBCopy = SplitBlock(Old: Builder.GetInsertBlock(), |
1073 | SplitPt: Builder.GetInsertPoint(), DT: GenDT, LI: GenLI); |
1074 | EntryBBCopy->setName("polly.stmt."+ EntryBB->getName() + ".entry"); |
1075 | Builder.SetInsertPoint(TheBB: EntryBBCopy, IP: EntryBBCopy->begin()); |
1076 | |
1077 | ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy]; |
1078 | generateScalarLoads(Stmt, LTS, BBMap&: EntryBBMap, NewAccesses: IdToAstExp); |
1079 | generateBeginStmtTrace(Stmt, LTS, BBMap&: EntryBBMap); |
1080 | |
1081 | for (auto PI = pred_begin(BB: EntryBB), PE = pred_end(BB: EntryBB); PI != PE; ++PI) |
1082 | if (!R->contains(BB: *PI)) { |
1083 | StartBlockMap[*PI] = EntryBBCopy; |
1084 | EndBlockMap[*PI] = EntryBBCopy; |
1085 | } |
1086 | |
1087 | // Iterate over all blocks in the region in a breadth-first search. |
1088 | std::deque<BasicBlock *> Blocks; |
1089 | SmallSetVector<BasicBlock *, 8> SeenBlocks; |
1090 | Blocks.push_back(x: EntryBB); |
1091 | SeenBlocks.insert(X: EntryBB); |
1092 | |
1093 | while (!Blocks.empty()) { |
1094 | BasicBlock *BB = Blocks.front(); |
1095 | Blocks.pop_front(); |
1096 | |
1097 | // First split the block and update dominance information. |
1098 | BasicBlock *BBCopy = splitBB(BB); |
1099 | BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy); |
1100 | |
1101 | // Get the mapping for this block and initialize it with either the scalar |
1102 | // loads from the generated entering block (which dominates all blocks of |
1103 | // this subregion) or the maps of the immediate dominator, if part of the |
1104 | // subregion. The latter necessarily includes the former. |
1105 | ValueMapT *InitBBMap; |
1106 | if (BBCopyIDom) { |
1107 | assert(RegionMaps.count(BBCopyIDom)); |
1108 | InitBBMap = &RegionMaps[BBCopyIDom]; |
1109 | } else |
1110 | InitBBMap = &EntryBBMap; |
1111 | auto Inserted = RegionMaps.insert(KV: std::make_pair(x&: BBCopy, y&: *InitBBMap)); |
1112 | ValueMapT &RegionMap = Inserted.first->second; |
1113 | |
1114 | // Copy the block with the BlockGenerator. |
1115 | Builder.SetInsertPoint(TheBB: BBCopy, IP: BBCopy->begin()); |
1116 | copyBB(Stmt, BB, CopyBB: BBCopy, BBMap&: RegionMap, LTS, NewAccesses: IdToAstExp); |
1117 | |
1118 | // In order to remap PHI nodes we store also basic block mappings. |
1119 | StartBlockMap[BB] = BBCopy; |
1120 | EndBlockMap[BB] = Builder.GetInsertBlock(); |
1121 | |
1122 | // Add values to incomplete PHI nodes waiting for this block to be copied. |
1123 | for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB]) |
1124 | addOperandToPHI(Stmt, PHI: PHINodePair.first, PHICopy: PHINodePair.second, IncomingBB: BB, LTS); |
1125 | IncompletePHINodeMap[BB].clear(); |
1126 | |
1127 | // And continue with new successors inside the region. |
1128 | for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++) |
1129 | if (R->contains(BB: *SI) && SeenBlocks.insert(X: *SI)) |
1130 | Blocks.push_back(x: *SI); |
1131 | |
1132 | // Remember value in case it is visible after this subregion. |
1133 | if (isDominatingSubregionExit(DT, R, BB)) |
1134 | ValueMap.insert_range(R&: RegionMap); |
1135 | } |
1136 | |
1137 | // Now create a new dedicated region exit block and add it to the region map. |
1138 | BasicBlock *ExitBBCopy = SplitBlock(Old: Builder.GetInsertBlock(), |
1139 | SplitPt: Builder.GetInsertPoint(), DT: GenDT, LI: GenLI); |
1140 | ExitBBCopy->setName("polly.stmt."+ R->getExit()->getName() + ".exit"); |
1141 | StartBlockMap[R->getExit()] = ExitBBCopy; |
1142 | EndBlockMap[R->getExit()] = ExitBBCopy; |
1143 | |
1144 | BasicBlock *ExitDomBBCopy = EndBlockMap.lookup(Val: findExitDominator(DT, R)); |
1145 | assert(ExitDomBBCopy && |
1146 | "Common exit dominator must be within region; at least the entry node " |
1147 | "must match"); |
1148 | GenDT->changeImmediateDominator(BB: ExitBBCopy, NewBB: ExitDomBBCopy); |
1149 | |
1150 | // As the block generator doesn't handle control flow we need to add the |
1151 | // region control flow by hand after all blocks have been copied. |
1152 | for (BasicBlock *BB : SeenBlocks) { |
1153 | |
1154 | BasicBlock *BBCopyStart = StartBlockMap[BB]; |
1155 | BasicBlock *BBCopyEnd = EndBlockMap[BB]; |
1156 | Instruction *TI = BB->getTerminator(); |
1157 | if (isa<UnreachableInst>(Val: TI)) { |
1158 | while (!BBCopyEnd->empty()) |
1159 | BBCopyEnd->begin()->eraseFromParent(); |
1160 | new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd); |
1161 | continue; |
1162 | } |
1163 | |
1164 | Instruction *BICopy = BBCopyEnd->getTerminator(); |
1165 | |
1166 | ValueMapT &RegionMap = RegionMaps[BBCopyStart]; |
1167 | RegionMap.insert_range(R&: StartBlockMap); |
1168 | |
1169 | Builder.SetInsertPoint(TheBB: BBCopyEnd, IP: BICopy->getIterator()); |
1170 | copyInstScalar(Stmt, Inst: TI, BBMap&: RegionMap, LTS); |
1171 | BICopy->eraseFromParent(); |
1172 | } |
1173 | |
1174 | // Add counting PHI nodes to all loops in the region that can be used as |
1175 | // replacement for SCEVs referring to the old loop. |
1176 | for (BasicBlock *BB : SeenBlocks) { |
1177 | Loop *L = LI.getLoopFor(BB); |
1178 | if (L == nullptr || L->getHeader() != BB || !R->contains(L)) |
1179 | continue; |
1180 | |
1181 | BasicBlock *BBCopy = StartBlockMap[BB]; |
1182 | Value *NullVal = Builder.getInt32(C: 0); |
1183 | PHINode *LoopPHI = |
1184 | PHINode::Create(Ty: Builder.getInt32Ty(), NumReservedValues: 2, NameStr: "polly.subregion.iv"); |
1185 | Instruction *LoopPHIInc = BinaryOperator::CreateAdd( |
1186 | V1: LoopPHI, V2: Builder.getInt32(C: 1), Name: "polly.subregion.iv.inc"); |
1187 | LoopPHI->insertBefore(InsertPos: BBCopy->begin()); |
1188 | LoopPHIInc->insertBefore(InsertPos: BBCopy->getTerminator()->getIterator()); |
1189 | |
1190 | for (auto *PredBB : predecessors(BB)) { |
1191 | if (!R->contains(BB: PredBB)) |
1192 | continue; |
1193 | if (L->contains(BB: PredBB)) |
1194 | LoopPHI->addIncoming(V: LoopPHIInc, BB: EndBlockMap[PredBB]); |
1195 | else |
1196 | LoopPHI->addIncoming(V: NullVal, BB: EndBlockMap[PredBB]); |
1197 | } |
1198 | |
1199 | for (auto *PredBBCopy : predecessors(BB: BBCopy)) |
1200 | if (LoopPHI->getBasicBlockIndex(BB: PredBBCopy) < 0) |
1201 | LoopPHI->addIncoming(V: NullVal, BB: PredBBCopy); |
1202 | |
1203 | LTS[L] = SE.getUnknown(V: LoopPHI); |
1204 | } |
1205 | |
1206 | // Continue generating code in the exit block. |
1207 | Builder.SetInsertPoint(TheBB: ExitBBCopy, IP: ExitBBCopy->getFirstInsertionPt()); |
1208 | |
1209 | // Write values visible to other statements. |
1210 | generateScalarStores(Stmt, LTS, BBMAp&: ValueMap, NewAccesses: IdToAstExp); |
1211 | StartBlockMap.clear(); |
1212 | EndBlockMap.clear(); |
1213 | RegionMaps.clear(); |
1214 | IncompletePHINodeMap.clear(); |
1215 | } |
1216 | |
1217 | PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, |
1218 | ValueMapT &BBMap, Loop *L) { |
1219 | ScopStmt *Stmt = MA->getStatement(); |
1220 | Region *SubR = Stmt->getRegion(); |
1221 | auto Incoming = MA->getIncoming(); |
1222 | |
1223 | PollyIRBuilder::InsertPointGuard IPGuard(Builder); |
1224 | PHINode *OrigPHI = cast<PHINode>(Val: MA->getAccessInstruction()); |
1225 | BasicBlock *NewSubregionExit = Builder.GetInsertBlock(); |
1226 | |
1227 | // This can happen if the subregion is simplified after the ScopStmts |
1228 | // have been created; simplification happens as part of CodeGeneration. |
1229 | if (OrigPHI->getParent() != SubR->getExit()) { |
1230 | BasicBlock *FormerExit = SubR->getExitingBlock(); |
1231 | if (FormerExit) |
1232 | NewSubregionExit = StartBlockMap.lookup(Val: FormerExit); |
1233 | } |
1234 | |
1235 | PHINode *NewPHI = PHINode::Create(Ty: OrigPHI->getType(), NumReservedValues: Incoming.size(), |
1236 | NameStr: "polly."+ OrigPHI->getName(), |
1237 | InsertBefore: NewSubregionExit->getFirstNonPHIIt()); |
1238 | |
1239 | // Add the incoming values to the PHI. |
1240 | for (auto &Pair : Incoming) { |
1241 | BasicBlock *OrigIncomingBlock = Pair.first; |
1242 | BasicBlock *NewIncomingBlockStart = StartBlockMap.lookup(Val: OrigIncomingBlock); |
1243 | BasicBlock *NewIncomingBlockEnd = EndBlockMap.lookup(Val: OrigIncomingBlock); |
1244 | Builder.SetInsertPoint(TheBB: NewIncomingBlockEnd, |
1245 | IP: NewIncomingBlockEnd->getTerminator()->getIterator()); |
1246 | assert(RegionMaps.count(NewIncomingBlockStart)); |
1247 | assert(RegionMaps.count(NewIncomingBlockEnd)); |
1248 | ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlockStart]; |
1249 | |
1250 | Value *OrigIncomingValue = Pair.second; |
1251 | Value *NewIncomingValue = |
1252 | getNewValue(Stmt&: *Stmt, Old: OrigIncomingValue, BBMap&: *LocalBBMap, LTS, L); |
1253 | NewPHI->addIncoming(V: NewIncomingValue, BB: NewIncomingBlockEnd); |
1254 | } |
1255 | |
1256 | return NewPHI; |
1257 | } |
1258 | |
1259 | Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, |
1260 | ValueMapT &BBMap) { |
1261 | ScopStmt *Stmt = MA->getStatement(); |
1262 | |
1263 | // TODO: Add some test cases that ensure this is really the right choice. |
1264 | Loop *L = LI.getLoopFor(BB: Stmt->getRegion()->getExit()); |
1265 | |
1266 | if (MA->isAnyPHIKind()) { |
1267 | auto Incoming = MA->getIncoming(); |
1268 | assert(!Incoming.empty() && |
1269 | "PHI WRITEs must have originate from at least one incoming block"); |
1270 | |
1271 | // If there is only one incoming value, we do not need to create a PHI. |
1272 | if (Incoming.size() == 1) { |
1273 | Value *OldVal = Incoming[0].second; |
1274 | return getNewValue(Stmt&: *Stmt, Old: OldVal, BBMap, LTS, L); |
1275 | } |
1276 | |
1277 | return buildExitPHI(MA, LTS, BBMap, L); |
1278 | } |
1279 | |
1280 | // MemoryKind::Value accesses leaving the subregion must dominate the exit |
1281 | // block; just pass the copied value. |
1282 | Value *OldVal = MA->getAccessValue(); |
1283 | return getNewValue(Stmt&: *Stmt, Old: OldVal, BBMap, LTS, L); |
1284 | } |
1285 | |
1286 | void RegionGenerator::generateScalarStores( |
1287 | ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, |
1288 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
1289 | assert(Stmt.getRegion() && |
1290 | "Block statements need to use the generateScalarStores() " |
1291 | "function in the BlockGenerator"); |
1292 | |
1293 | // Get the exit scalar values before generating the writes. |
1294 | // This is necessary because RegionGenerator::getExitScalar may insert |
1295 | // PHINodes that depend on the region's exiting blocks. But |
1296 | // BlockGenerator::generateConditionalExecution may insert a new basic block |
1297 | // such that the current basic block is not a direct successor of the exiting |
1298 | // blocks anymore. Hence, build the PHINodes while the current block is still |
1299 | // the direct successor. |
1300 | SmallDenseMap<MemoryAccess *, Value *> NewExitScalars; |
1301 | for (MemoryAccess *MA : Stmt) { |
1302 | if (MA->isOriginalArrayKind() || MA->isRead()) |
1303 | continue; |
1304 | |
1305 | Value *NewVal = getExitScalar(MA, LTS, BBMap); |
1306 | NewExitScalars[MA] = NewVal; |
1307 | } |
1308 | |
1309 | for (MemoryAccess *MA : Stmt) { |
1310 | if (MA->isOriginalArrayKind() || MA->isRead()) |
1311 | continue; |
1312 | |
1313 | isl::set AccDom = MA->getAccessRelation().domain(); |
1314 | std::string Subject = MA->getId().get_name(); |
1315 | generateConditionalExecution( |
1316 | Stmt, Subdomain: AccDom, Subject: Subject.c_str(), GenThenFunc: [&, this, MA]() { |
1317 | Value *NewVal = NewExitScalars.lookup(Val: MA); |
1318 | assert(NewVal && "The exit scalar must be determined before"); |
1319 | Value *Address = getImplicitAddress(Access&: *MA, L: getLoopForStmt(Stmt), LTS, |
1320 | BBMap, NewAccesses); |
1321 | assert((!isa<Instruction>(NewVal) || |
1322 | DT.dominates(cast<Instruction>(NewVal)->getParent(), |
1323 | Builder.GetInsertBlock())) && |
1324 | "Domination violation"); |
1325 | assert((!isa<Instruction>(Address) || |
1326 | DT.dominates(cast<Instruction>(Address)->getParent(), |
1327 | Builder.GetInsertBlock())) && |
1328 | "Domination violation"); |
1329 | Builder.CreateStore(Val: NewVal, Ptr: Address); |
1330 | }); |
1331 | } |
1332 | } |
1333 | |
1334 | void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, |
1335 | PHINode *PHICopy, BasicBlock *IncomingBB, |
1336 | LoopToScevMapT <S) { |
1337 | // If the incoming block was not yet copied mark this PHI as incomplete. |
1338 | // Once the block will be copied the incoming value will be added. |
1339 | BasicBlock *BBCopyStart = StartBlockMap[IncomingBB]; |
1340 | BasicBlock *BBCopyEnd = EndBlockMap[IncomingBB]; |
1341 | if (!BBCopyStart) { |
1342 | assert(!BBCopyEnd); |
1343 | assert(Stmt.represents(IncomingBB) && |
1344 | "Bad incoming block for PHI in non-affine region"); |
1345 | IncompletePHINodeMap[IncomingBB].push_back(Elt: std::make_pair(x&: PHI, y&: PHICopy)); |
1346 | return; |
1347 | } |
1348 | |
1349 | assert(RegionMaps.count(BBCopyStart) && |
1350 | "Incoming PHI block did not have a BBMap"); |
1351 | ValueMapT &BBCopyMap = RegionMaps[BBCopyStart]; |
1352 | |
1353 | Value *OpCopy = nullptr; |
1354 | |
1355 | if (Stmt.represents(BB: IncomingBB)) { |
1356 | Value *Op = PHI->getIncomingValueForBlock(BB: IncomingBB); |
1357 | |
1358 | // If the current insert block is different from the PHIs incoming block |
1359 | // change it, otherwise do not. |
1360 | auto IP = Builder.GetInsertPoint(); |
1361 | if (IP->getParent() != BBCopyEnd) |
1362 | Builder.SetInsertPoint(TheBB: BBCopyEnd, |
1363 | IP: BBCopyEnd->getTerminator()->getIterator()); |
1364 | OpCopy = getNewValue(Stmt, Old: Op, BBMap&: BBCopyMap, LTS, L: getLoopForStmt(Stmt)); |
1365 | if (IP->getParent() != BBCopyEnd) |
1366 | Builder.SetInsertPoint(IP); |
1367 | } else { |
1368 | // All edges from outside the non-affine region become a single edge |
1369 | // in the new copy of the non-affine region. Make sure to only add the |
1370 | // corresponding edge the first time we encounter a basic block from |
1371 | // outside the non-affine region. |
1372 | if (PHICopy->getBasicBlockIndex(BB: BBCopyEnd) >= 0) |
1373 | return; |
1374 | |
1375 | // Get the reloaded value. |
1376 | OpCopy = getNewValue(Stmt, Old: PHI, BBMap&: BBCopyMap, LTS, L: getLoopForStmt(Stmt)); |
1377 | } |
1378 | |
1379 | assert(OpCopy && "Incoming PHI value was not copied properly"); |
1380 | PHICopy->addIncoming(V: OpCopy, BB: BBCopyEnd); |
1381 | } |
1382 | |
1383 | void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI, |
1384 | ValueMapT &BBMap, |
1385 | LoopToScevMapT <S) { |
1386 | unsigned NumIncoming = PHI->getNumIncomingValues(); |
1387 | PHINode *PHICopy = |
1388 | Builder.CreatePHI(Ty: PHI->getType(), NumReservedValues: NumIncoming, Name: "polly."+ PHI->getName()); |
1389 | PHICopy->moveBefore(InsertPos: PHICopy->getParent()->getFirstNonPHIIt()); |
1390 | BBMap[PHI] = PHICopy; |
1391 | |
1392 | for (BasicBlock *IncomingBB : PHI->blocks()) |
1393 | addOperandToPHI(Stmt, PHI, PHICopy, IncomingBB, LTS); |
1394 | } |
1395 |
Definitions
- Aligned
- PollyDebugPrinting
- DebugPrintingX
- TraceStmts
- TraceScalars
- BlockGenerator
- trySynthesizeNewValue
- getNewValue
- copyInstScalar
- generateLocationAccessed
- generateLocationAccessed
- getImplicitAddress
- getLoopForStmt
- generateArrayLoad
- generateArrayStore
- canSyntheziseInStmt
- copyInstruction
- removeDeadInstructions
- copyStmt
- splitBB
- copyBB
- switchGeneratedFunc
- copyBB
- getOrCreateAlloca
- getOrCreateAlloca
- handleOutsideUsers
- generateScalarLoads
- buildContainsCondition
- generateConditionalExecution
- getInstName
- generateBeginStmtTrace
- generateScalarStores
- createScalarInitialization
- createScalarFinalization
- findOutsideUsers
- createExitPHINodeMerges
- invalidateScalarEvolution
- finalizeSCoP
- repairDominance
- isDominatingSubregionExit
- findExitDominator
- copyStmt
- buildExitPHI
- getExitScalar
- generateScalarStores
- addOperandToPHI
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more