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
32using namespace llvm;
33using namespace polly;
34
35static cl::opt<bool> Aligned("enable-polly-aligned",
36 cl::desc("Assumed aligned memory accesses."),
37 cl::Hidden, cl::cat(PollyCategory));
38
39bool PollyDebugPrinting;
40static 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
45static 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
50static 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
56BlockGenerator::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
64Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
65 ValueMapT &BBMap,
66 LoopToScevMapT &LTS,
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: &LTS, RTCBB: StartBlock->getSinglePredecessor());
91
92 BBMap[Old] = Expanded;
93 return Expanded;
94}
95
96Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
97 LoopToScevMapT &LTS, 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
213void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
214 ValueMapT &BBMap, LoopToScevMapT &LTS) {
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
250Value *
251BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
252 ValueMapT &BBMap, LoopToScevMapT &LTS,
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
261Value *BlockGenerator::generateLocationAccessed(
262 ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
263 LoopToScevMapT &LTS, 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
277Value *
278BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
279 LoopToScevMapT &LTS, 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
289Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
290 auto *StmtBB = Stmt.getEntryBlock();
291 return LI.getLoopFor(BB: StmtBB);
292}
293
294Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,
295 ValueMapT &BBMap, LoopToScevMapT &LTS,
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
313void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,
314 ValueMapT &BBMap, LoopToScevMapT &LTS,
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
334bool 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
340void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
341 ValueMapT &BBMap, LoopToScevMapT &LTS,
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
382void 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
400void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
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
412BasicBlock *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
419BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
420 ValueMapT &BBMap, LoopToScevMapT &LTS,
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
435void 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
446void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
447 ValueMapT &BBMap, LoopToScevMapT &LTS,
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
462Value *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
468Value *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
516void 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
550void BlockGenerator::generateScalarLoads(
551 ScopStmt &Stmt, LoopToScevMapT &LTS, 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
572Value *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
596void 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
644static 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
651void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT &LTS,
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
744void BlockGenerator::generateScalarStores(
745 ScopStmt &Stmt, LoopToScevMapT &LTS, 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
794void 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
842void 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
889void 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
913void 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
961void 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
988void BlockGenerator::finalizeSCoP(Scop &S) {
989 findOutsideUsers(S);
990 createScalarInitialization(S);
991 createExitPHINodeMerges(S);
992 createScalarFinalization(S);
993 invalidateScalarEvolution(S);
994}
995
996BasicBlock *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.
1016static 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.
1032static 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
1052void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
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
1217PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
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
1259Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
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
1286void RegionGenerator::generateScalarStores(
1287 ScopStmt &Stmt, LoopToScevMapT &LTS, 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
1334void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
1335 PHINode *PHICopy, BasicBlock *IncomingBB,
1336 LoopToScevMapT &LTS) {
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
1383void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1384 ValueMapT &BBMap,
1385 LoopToScevMapT &LTS) {
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

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