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/ScopHelper.h"
21 #include "polly/Support/VirtualInstruction.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/Analysis/RegionInfo.h"
24 #include "llvm/Analysis/ScalarEvolution.h"
25 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
26 #include "llvm/Transforms/Utils/Local.h"
27 #include "isl/ast.h"
28 #include <deque>
29
30 using namespace llvm;
31 using namespace polly;
32
33 static cl::opt<bool> Aligned("enable-polly-aligned",
34 cl::desc("Assumed aligned memory accesses."),
35 cl::Hidden, cl::init(false), cl::ZeroOrMore,
36 cl::cat(PollyCategory));
37
38 bool PollyDebugPrinting;
39 static cl::opt<bool, true> DebugPrintingX(
40 "polly-codegen-add-debug-printing",
41 cl::desc("Add printf calls that show the values loaded/stored."),
42 cl::location(PollyDebugPrinting), cl::Hidden, cl::init(false),
43 cl::ZeroOrMore, 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::init(false), cl::ZeroOrMore, 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::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
55
BlockGenerator(PollyIRBuilder & B,LoopInfo & LI,ScalarEvolution & SE,DominatorTree & DT,AllocaMapTy & ScalarMap,EscapeUsersAllocaMapTy & EscapeMap,ValueMapT & GlobalMap,IslExprBuilder * ExprBuilder,BasicBlock * StartBlock)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),
61 EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap),
62 GlobalMap(GlobalMap), StartBlock(StartBlock) {}
63
trySynthesizeNewValue(ScopStmt & Stmt,Value * Old,ValueMapT & BBMap,LoopToScevMapT & LTS,Loop * L) const64 Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
65 ValueMapT &BBMap,
66 LoopToScevMapT <S,
67 Loop *L) const {
68 if (!SE.isSCEVable(Old->getType()))
69 return nullptr;
70
71 const SCEV *Scev = SE.getSCEVAtScope(Old, L);
72 if (!Scev)
73 return nullptr;
74
75 if (isa<SCEVCouldNotCompute>(Scev))
76 return nullptr;
77
78 const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE);
79 ValueMapT VTV;
80 VTV.insert(BBMap.begin(), BBMap.end());
81 VTV.insert(GlobalMap.begin(), GlobalMap.end());
82
83 Scop &S = *Stmt.getParent();
84 const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
85 auto IP = Builder.GetInsertPoint();
86
87 assert(IP != Builder.GetInsertBlock()->end() &&
88 "Only instructions can be insert points for SCEVExpander");
89 Value *Expanded =
90 expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV,
91 StartBlock->getSinglePredecessor());
92
93 BBMap[Old] = Expanded;
94 return Expanded;
95 }
96
getNewValue(ScopStmt & Stmt,Value * Old,ValueMapT & BBMap,LoopToScevMapT & LTS,Loop * L) const97 Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
98 LoopToScevMapT <S, Loop *L) const {
99
100 auto lookupGlobally = [this](Value *Old) -> Value * {
101 Value *New = GlobalMap.lookup(Old);
102 if (!New)
103 return nullptr;
104
105 // Required by:
106 // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll
107 // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll
108 // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll
109 // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll
110 // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
111 // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll
112 // GlobalMap should be a mapping from (value in original SCoP) to (copied
113 // value in generated SCoP), without intermediate mappings, which might
114 // easily require transitiveness as well.
115 if (Value *NewRemapped = GlobalMap.lookup(New))
116 New = NewRemapped;
117
118 // No test case for this code.
119 if (Old->getType()->getScalarSizeInBits() <
120 New->getType()->getScalarSizeInBits())
121 New = Builder.CreateTruncOrBitCast(New, Old->getType());
122
123 return New;
124 };
125
126 Value *New = nullptr;
127 auto VUse = VirtualUse::create(&Stmt, L, Old, true);
128 switch (VUse.getKind()) {
129 case VirtualUse::Block:
130 // BasicBlock are constants, but the BlockGenerator copies them.
131 New = BBMap.lookup(Old);
132 break;
133
134 case VirtualUse::Constant:
135 // Used by:
136 // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll
137 // Constants should not be redefined. In this case, the GlobalMap just
138 // contains a mapping to the same constant, which is unnecessary, but
139 // harmless.
140 if ((New = lookupGlobally(Old)))
141 break;
142
143 assert(!BBMap.count(Old));
144 New = Old;
145 break;
146
147 case VirtualUse::ReadOnly:
148 assert(!GlobalMap.count(Old));
149
150 // Required for:
151 // * Isl/CodeGen/MemAccess/create_arrays.ll
152 // * Isl/CodeGen/read-only-scalars.ll
153 // * ScheduleOptimizer/pattern-matching-based-opts_10.ll
154 // For some reason these reload a read-only value. The reloaded value ends
155 // up in BBMap, buts its value should be identical.
156 //
157 // Required for:
158 // * Isl/CodeGen/OpenMP/single_loop_with_param.ll
159 // The parallel subfunctions need to reference the read-only value from the
160 // parent function, this is done by reloading them locally.
161 if ((New = BBMap.lookup(Old)))
162 break;
163
164 New = Old;
165 break;
166
167 case VirtualUse::Synthesizable:
168 // Used by:
169 // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
170 // * Isl/CodeGen/OpenMP/recomputed-srem.ll
171 // * Isl/CodeGen/OpenMP/reference-other-bb.ll
172 // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
173 // For some reason synthesizable values end up in GlobalMap. Their values
174 // are the same as trySynthesizeNewValue would return. The legacy
175 // implementation prioritized GlobalMap, so this is what we do here as well.
176 // Ideally, synthesizable values should not end up in GlobalMap.
177 if ((New = lookupGlobally(Old)))
178 break;
179
180 // Required for:
181 // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll
182 // * Isl/CodeGen/getNumberOfIterations.ll
183 // * Isl/CodeGen/non_affine_float_compare.ll
184 // * ScheduleOptimizer/pattern-matching-based-opts_10.ll
185 // Ideally, synthesizable values are synthesized by trySynthesizeNewValue,
186 // not precomputed (SCEVExpander has its own caching mechanism).
187 // These tests fail without this, but I think trySynthesizeNewValue would
188 // just re-synthesize the same instructions.
189 if ((New = BBMap.lookup(Old)))
190 break;
191
192 New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L);
193 break;
194
195 case VirtualUse::Hoisted:
196 // TODO: Hoisted invariant loads should be found in GlobalMap only, but not
197 // redefined locally (which will be ignored anyway). That is, the following
198 // assertion should apply: assert(!BBMap.count(Old))
199
200 New = lookupGlobally(Old);
201 break;
202
203 case VirtualUse::Intra:
204 case VirtualUse::Inter:
205 assert(!GlobalMap.count(Old) &&
206 "Intra and inter-stmt values are never global");
207 New = BBMap.lookup(Old);
208 break;
209 }
210 assert(New && "Unexpected scalar dependence in region!");
211 return New;
212 }
213
copyInstScalar(ScopStmt & Stmt,Instruction * Inst,ValueMapT & BBMap,LoopToScevMapT & LTS)214 void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
215 ValueMapT &BBMap, LoopToScevMapT <S) {
216 // We do not generate debug intrinsics as we did not investigate how to
217 // copy them correctly. At the current state, they just crash the code
218 // generation as the meta-data operands are not correctly copied.
219 if (isa<DbgInfoIntrinsic>(Inst))
220 return;
221
222 Instruction *NewInst = Inst->clone();
223
224 // Replace old operands with the new ones.
225 for (Value *OldOperand : Inst->operands()) {
226 Value *NewOperand =
227 getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
228
229 if (!NewOperand) {
230 assert(!isa<StoreInst>(NewInst) &&
231 "Store instructions are always needed!");
232 NewInst->deleteValue();
233 return;
234 }
235
236 NewInst->replaceUsesOfWith(OldOperand, NewOperand);
237 }
238
239 Builder.Insert(NewInst);
240 BBMap[Inst] = NewInst;
241
242 // When copying the instruction onto the Module meant for the GPU,
243 // debug metadata attached to an instruction causes all related
244 // metadata to be pulled into the Module. This includes the DICompileUnit,
245 // which will not be listed in llvm.dbg.cu of the Module since the Module
246 // doesn't contain one. This fails the verification of the Module and the
247 // subsequent generation of the ASM string.
248 if (NewInst->getModule() != Inst->getModule())
249 NewInst->setDebugLoc(llvm::DebugLoc());
250
251 if (!NewInst->getType()->isVoidTy())
252 NewInst->setName("p_" + Inst->getName());
253 }
254
255 Value *
generateLocationAccessed(ScopStmt & Stmt,MemAccInst Inst,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)256 BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
257 ValueMapT &BBMap, LoopToScevMapT <S,
258 isl_id_to_ast_expr *NewAccesses) {
259 const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
260 return generateLocationAccessed(
261 Stmt, getLoopForStmt(Stmt),
262 Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS,
263 NewAccesses, MA.getId().release(), MA.getAccessValue()->getType());
264 }
265
generateLocationAccessed(ScopStmt & Stmt,Loop * L,Value * Pointer,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses,__isl_take isl_id * Id,Type * ExpectedType)266 Value *BlockGenerator::generateLocationAccessed(
267 ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
268 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,
269 Type *ExpectedType) {
270 isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);
271
272 if (AccessExpr) {
273 AccessExpr = isl_ast_expr_address_of(AccessExpr);
274 auto Address = ExprBuilder->create(AccessExpr);
275
276 // Cast the address of this memory access to a pointer type that has the
277 // same element type as the original access, but uses the address space of
278 // the newly generated pointer.
279 auto OldPtrTy = ExpectedType->getPointerTo();
280 auto NewPtrTy = Address->getType();
281 OldPtrTy = PointerType::getWithSamePointeeType(
282 OldPtrTy, NewPtrTy->getPointerAddressSpace());
283
284 if (OldPtrTy != NewPtrTy)
285 Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
286 return Address;
287 }
288 assert(
289 Pointer &&
290 "If expression was not generated, must use the original pointer value");
291 return getNewValue(Stmt, Pointer, BBMap, LTS, L);
292 }
293
294 Value *
getImplicitAddress(MemoryAccess & Access,Loop * L,LoopToScevMapT & LTS,ValueMapT & BBMap,__isl_keep isl_id_to_ast_expr * NewAccesses)295 BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
296 LoopToScevMapT <S, ValueMapT &BBMap,
297 __isl_keep isl_id_to_ast_expr *NewAccesses) {
298 if (Access.isLatestArrayKind())
299 return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap,
300 LTS, NewAccesses, Access.getId().release(),
301 Access.getAccessValue()->getType());
302
303 return getOrCreateAlloca(Access);
304 }
305
getLoopForStmt(const ScopStmt & Stmt) const306 Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
307 auto *StmtBB = Stmt.getEntryBlock();
308 return LI.getLoopFor(StmtBB);
309 }
310
generateArrayLoad(ScopStmt & Stmt,LoadInst * Load,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)311 Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,
312 ValueMapT &BBMap, LoopToScevMapT <S,
313 isl_id_to_ast_expr *NewAccesses) {
314 if (Value *PreloadLoad = GlobalMap.lookup(Load))
315 return PreloadLoad;
316
317 Value *NewPointer =
318 generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
319 Value *ScalarLoad =
320 Builder.CreateAlignedLoad(Load->getType(), NewPointer, Load->getAlign(),
321 Load->getName() + "_p_scalar_");
322
323 if (PollyDebugPrinting)
324 RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
325 ": ", ScalarLoad, "\n");
326
327 return ScalarLoad;
328 }
329
generateArrayStore(ScopStmt & Stmt,StoreInst * Store,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)330 void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,
331 ValueMapT &BBMap, LoopToScevMapT <S,
332 isl_id_to_ast_expr *NewAccesses) {
333 MemoryAccess &MA = Stmt.getArrayAccessFor(Store);
334 isl::set AccDom = MA.getAccessRelation().domain();
335 std::string Subject = MA.getId().get_name();
336
337 generateConditionalExecution(Stmt, AccDom, Subject.c_str(), [&, this]() {
338 Value *NewPointer =
339 generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
340 Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap,
341 LTS, getLoopForStmt(Stmt));
342
343 if (PollyDebugPrinting)
344 RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer,
345 ": ", ValueOperand, "\n");
346
347 Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlign());
348 });
349 }
350
canSyntheziseInStmt(ScopStmt & Stmt,Instruction * Inst)351 bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
352 Loop *L = getLoopForStmt(Stmt);
353 return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
354 canSynthesize(Inst, *Stmt.getParent(), &SE, L);
355 }
356
copyInstruction(ScopStmt & Stmt,Instruction * Inst,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)357 void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
358 ValueMapT &BBMap, LoopToScevMapT <S,
359 isl_id_to_ast_expr *NewAccesses) {
360 // Terminator instructions control the control flow. They are explicitly
361 // expressed in the clast and do not need to be copied.
362 if (Inst->isTerminator())
363 return;
364
365 // Synthesizable statements will be generated on-demand.
366 if (canSyntheziseInStmt(Stmt, Inst))
367 return;
368
369 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
370 Value *NewLoad = generateArrayLoad(Stmt, Load, BBMap, LTS, NewAccesses);
371 // Compute NewLoad before its insertion in BBMap to make the insertion
372 // deterministic.
373 BBMap[Load] = NewLoad;
374 return;
375 }
376
377 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
378 // Identified as redundant by -polly-simplify.
379 if (!Stmt.getArrayAccessOrNULLFor(Store))
380 return;
381
382 generateArrayStore(Stmt, Store, BBMap, LTS, NewAccesses);
383 return;
384 }
385
386 if (auto *PHI = dyn_cast<PHINode>(Inst)) {
387 copyPHIInstruction(Stmt, PHI, BBMap, LTS);
388 return;
389 }
390
391 // Skip some special intrinsics for which we do not adjust the semantics to
392 // the new schedule. All others are handled like every other instruction.
393 if (isIgnoredIntrinsic(Inst))
394 return;
395
396 copyInstScalar(Stmt, Inst, BBMap, LTS);
397 }
398
removeDeadInstructions(BasicBlock * BB,ValueMapT & BBMap)399 void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) {
400 auto NewBB = Builder.GetInsertBlock();
401 for (auto I = NewBB->rbegin(); I != NewBB->rend(); I++) {
402 Instruction *NewInst = &*I;
403
404 if (!isInstructionTriviallyDead(NewInst))
405 continue;
406
407 for (auto Pair : BBMap)
408 if (Pair.second == NewInst) {
409 BBMap.erase(Pair.first);
410 }
411
412 NewInst->eraseFromParent();
413 I = NewBB->rbegin();
414 }
415 }
416
copyStmt(ScopStmt & Stmt,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)417 void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S,
418 isl_id_to_ast_expr *NewAccesses) {
419 assert(Stmt.isBlockStmt() &&
420 "Only block statements can be copied by the block generator");
421
422 ValueMapT BBMap;
423
424 BasicBlock *BB = Stmt.getBasicBlock();
425 copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
426 removeDeadInstructions(BB, BBMap);
427 }
428
splitBB(BasicBlock * BB)429 BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
430 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
431 &*Builder.GetInsertPoint(), &DT, &LI);
432 CopyBB->setName("polly.stmt." + BB->getName());
433 return CopyBB;
434 }
435
copyBB(ScopStmt & Stmt,BasicBlock * BB,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)436 BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
437 ValueMapT &BBMap, LoopToScevMapT <S,
438 isl_id_to_ast_expr *NewAccesses) {
439 BasicBlock *CopyBB = splitBB(BB);
440 Builder.SetInsertPoint(&CopyBB->front());
441 generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);
442 generateBeginStmtTrace(Stmt, LTS, BBMap);
443
444 copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
445
446 // After a basic block was copied store all scalars that escape this block in
447 // their alloca.
448 generateScalarStores(Stmt, LTS, BBMap, NewAccesses);
449 return CopyBB;
450 }
451
copyBB(ScopStmt & Stmt,BasicBlock * BB,BasicBlock * CopyBB,ValueMapT & BBMap,LoopToScevMapT & LTS,isl_id_to_ast_expr * NewAccesses)452 void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
453 ValueMapT &BBMap, LoopToScevMapT <S,
454 isl_id_to_ast_expr *NewAccesses) {
455 EntryBB = &CopyBB->getParent()->getEntryBlock();
456
457 // Block statements and the entry blocks of region statement are code
458 // generated from instruction lists. This allow us to optimize the
459 // instructions that belong to a certain scop statement. As the code
460 // structure of region statements might be arbitrary complex, optimizing the
461 // instruction list is not yet supported.
462 if (Stmt.isBlockStmt() || (Stmt.isRegionStmt() && Stmt.getEntryBlock() == BB))
463 for (Instruction *Inst : Stmt.getInstructions())
464 copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses);
465 else
466 for (Instruction &Inst : *BB)
467 copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
468 }
469
getOrCreateAlloca(const MemoryAccess & Access)470 Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
471 assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind");
472
473 return getOrCreateAlloca(Access.getLatestScopArrayInfo());
474 }
475
getOrCreateAlloca(const ScopArrayInfo * Array)476 Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
477 assert(!Array->isArrayKind() && "Trying to get alloca for array kind");
478
479 auto &Addr = ScalarMap[Array];
480
481 if (Addr) {
482 // Allow allocas to be (temporarily) redirected once by adding a new
483 // old-alloca-addr to new-addr mapping to GlobalMap. This functionality
484 // is used for example by the OpenMP code generation where a first use
485 // of a scalar while still in the host code allocates a normal alloca with
486 // getOrCreateAlloca. When the values of this scalar are accessed during
487 // the generation of the parallel subfunction, these values are copied over
488 // to the parallel subfunction and each request for a scalar alloca slot
489 // must be forwarded to the temporary in-subfunction slot. This mapping is
490 // removed when the subfunction has been generated and again normal host
491 // code is generated. Due to the following reasons it is not possible to
492 // perform the GlobalMap lookup right after creating the alloca below, but
493 // instead we need to check GlobalMap at each call to getOrCreateAlloca:
494 //
495 // 1) GlobalMap may be changed multiple times (for each parallel loop),
496 // 2) The temporary mapping is commonly only known after the initial
497 // alloca has already been generated, and
498 // 3) The original alloca value must be restored after leaving the
499 // sub-function.
500 if (Value *NewAddr = GlobalMap.lookup(&*Addr))
501 return NewAddr;
502 return Addr;
503 }
504
505 Type *Ty = Array->getElementType();
506 Value *ScalarBase = Array->getBasePtr();
507 std::string NameExt;
508 if (Array->isPHIKind())
509 NameExt = ".phiops";
510 else
511 NameExt = ".s2a";
512
513 const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout();
514
515 Addr =
516 new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr,
517 DL.getPrefTypeAlign(Ty), ScalarBase->getName() + NameExt);
518 EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
519 Addr->insertBefore(&*EntryBB->getFirstInsertionPt());
520
521 return Addr;
522 }
523
handleOutsideUsers(const Scop & S,ScopArrayInfo * Array)524 void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) {
525 Instruction *Inst = cast<Instruction>(Array->getBasePtr());
526
527 // If there are escape users we get the alloca for this instruction and put it
528 // in the EscapeMap for later finalization. Lastly, if the instruction was
529 // copied multiple times we already did this and can exit.
530 if (EscapeMap.count(Inst))
531 return;
532
533 EscapeUserVectorTy EscapeUsers;
534 for (User *U : Inst->users()) {
535
536 // Non-instruction user will never escape.
537 Instruction *UI = dyn_cast<Instruction>(U);
538 if (!UI)
539 continue;
540
541 if (S.contains(UI))
542 continue;
543
544 EscapeUsers.push_back(UI);
545 }
546
547 // Exit if no escape uses were found.
548 if (EscapeUsers.empty())
549 return;
550
551 // Get or create an escape alloca for this instruction.
552 auto *ScalarAddr = getOrCreateAlloca(Array);
553
554 // Remember that this instruction has escape uses and the escape alloca.
555 EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
556 }
557
generateScalarLoads(ScopStmt & Stmt,LoopToScevMapT & LTS,ValueMapT & BBMap,__isl_keep isl_id_to_ast_expr * NewAccesses)558 void BlockGenerator::generateScalarLoads(
559 ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap,
560 __isl_keep isl_id_to_ast_expr *NewAccesses) {
561 for (MemoryAccess *MA : Stmt) {
562 if (MA->isOriginalArrayKind() || MA->isWrite())
563 continue;
564
565 #ifndef NDEBUG
566 auto StmtDom =
567 Stmt.getDomain().intersect_params(Stmt.getParent()->getContext());
568 auto AccDom = MA->getAccessRelation().domain();
569 assert(!StmtDom.is_subset(AccDom).is_false() &&
570 "Scalar must be loaded in all statement instances");
571 #endif
572
573 auto *Address =
574 getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
575 assert((!isa<Instruction>(Address) ||
576 DT.dominates(cast<Instruction>(Address)->getParent(),
577 Builder.GetInsertBlock())) &&
578 "Domination violation");
579 BBMap[MA->getAccessValue()] = Builder.CreateLoad(
580 MA->getElementType(), Address, Address->getName() + ".reload");
581 }
582 }
583
buildContainsCondition(ScopStmt & Stmt,const isl::set & Subdomain)584 Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt,
585 const isl::set &Subdomain) {
586 isl::ast_build AstBuild = Stmt.getAstBuild();
587 isl::set Domain = Stmt.getDomain();
588
589 isl::union_map USchedule = AstBuild.get_schedule();
590 USchedule = USchedule.intersect_domain(Domain);
591
592 assert(!USchedule.is_empty());
593 isl::map Schedule = isl::map::from_union_map(USchedule);
594
595 isl::set ScheduledDomain = Schedule.range();
596 isl::set ScheduledSet = Subdomain.apply(Schedule);
597
598 isl::ast_build RestrictedBuild = AstBuild.restrict(ScheduledDomain);
599
600 isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduledSet);
601 Value *IsInSetExpr = ExprBuilder->create(IsInSet.copy());
602 IsInSetExpr = Builder.CreateICmpNE(
603 IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0));
604
605 return IsInSetExpr;
606 }
607
generateConditionalExecution(ScopStmt & Stmt,const isl::set & Subdomain,StringRef Subject,const std::function<void ()> & GenThenFunc)608 void BlockGenerator::generateConditionalExecution(
609 ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject,
610 const std::function<void()> &GenThenFunc) {
611 isl::set StmtDom = Stmt.getDomain();
612
613 // If the condition is a tautology, don't generate a condition around the
614 // code.
615 bool IsPartialWrite =
616 !StmtDom.intersect_params(Stmt.getParent()->getContext())
617 .is_subset(Subdomain);
618 if (!IsPartialWrite) {
619 GenThenFunc();
620 return;
621 }
622
623 // Generate the condition.
624 Value *Cond = buildContainsCondition(Stmt, Subdomain);
625
626 // Don't call GenThenFunc if it is never executed. An ast index expression
627 // might not be defined in this case.
628 if (auto *Const = dyn_cast<ConstantInt>(Cond))
629 if (Const->isZero())
630 return;
631
632 BasicBlock *HeadBlock = Builder.GetInsertBlock();
633 StringRef BlockName = HeadBlock->getName();
634
635 // Generate the conditional block.
636 SplitBlockAndInsertIfThen(Cond, &*Builder.GetInsertPoint(), false, nullptr,
637 &DT, &LI);
638 BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());
639 BasicBlock *ThenBlock = Branch->getSuccessor(0);
640 BasicBlock *TailBlock = Branch->getSuccessor(1);
641
642 // Assign descriptive names.
643 if (auto *CondInst = dyn_cast<Instruction>(Cond))
644 CondInst->setName("polly." + Subject + ".cond");
645 ThenBlock->setName(BlockName + "." + Subject + ".partial");
646 TailBlock->setName(BlockName + ".cont");
647
648 // Put the client code into the conditional block and continue in the merge
649 // block afterwards.
650 Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());
651 GenThenFunc();
652 Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());
653 }
654
getInstName(Value * Val)655 static std::string getInstName(Value *Val) {
656 std::string Result;
657 raw_string_ostream OS(Result);
658 Val->printAsOperand(OS, false);
659 return OS.str();
660 }
661
generateBeginStmtTrace(ScopStmt & Stmt,LoopToScevMapT & LTS,ValueMapT & BBMap)662 void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S,
663 ValueMapT &BBMap) {
664 if (!TraceStmts)
665 return;
666
667 Scop *S = Stmt.getParent();
668 const char *BaseName = Stmt.getBaseName();
669
670 isl::ast_build AstBuild = Stmt.getAstBuild();
671 isl::set Domain = Stmt.getDomain();
672
673 isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(Domain);
674 isl::map Schedule = isl::map::from_union_map(USchedule);
675 assert(Schedule.is_empty().is_false() &&
676 "The stmt must have a valid instance");
677
678 isl::multi_pw_aff ScheduleMultiPwAff =
679 isl::pw_multi_aff::from_map(Schedule.reverse());
680 isl::ast_build RestrictedBuild = AstBuild.restrict(Schedule.range());
681
682 // Sequence of strings to print.
683 SmallVector<llvm::Value *, 8> Values;
684
685 // Print the name of the statement.
686 // TODO: Indent by the depth of the statement instance in the schedule tree.
687 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, BaseName));
688 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "("));
689
690 // Add the coordinate of the statement instance.
691 int DomDims = ScheduleMultiPwAff.dim(isl::dim::out).release();
692 for (int i = 0; i < DomDims; i += 1) {
693 if (i > 0)
694 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ","));
695
696 isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduleMultiPwAff.at(i));
697 Values.push_back(ExprBuilder->create(IsInSet.copy()));
698 }
699
700 if (TraceScalars) {
701 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")"));
702 DenseSet<Instruction *> Encountered;
703
704 // Add the value of each scalar (and the result of PHIs) used in the
705 // statement.
706 // TODO: Values used in region-statements.
707 for (Instruction *Inst : Stmt.insts()) {
708 if (!RuntimeDebugBuilder::isPrintable(Inst->getType()))
709 continue;
710
711 if (isa<PHINode>(Inst)) {
712 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " "));
713 Values.push_back(RuntimeDebugBuilder::getPrintableString(
714 Builder, getInstName(Inst)));
715 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "="));
716 Values.push_back(getNewValue(Stmt, Inst, BBMap, LTS,
717 LI.getLoopFor(Inst->getParent())));
718 } else {
719 for (Value *Op : Inst->operand_values()) {
720 // Do not print values that cannot change during the execution of the
721 // SCoP.
722 auto *OpInst = dyn_cast<Instruction>(Op);
723 if (!OpInst)
724 continue;
725 if (!S->contains(OpInst))
726 continue;
727
728 // Print each scalar at most once, and exclude values defined in the
729 // statement itself.
730 if (Encountered.count(OpInst))
731 continue;
732
733 Values.push_back(
734 RuntimeDebugBuilder::getPrintableString(Builder, " "));
735 Values.push_back(RuntimeDebugBuilder::getPrintableString(
736 Builder, getInstName(OpInst)));
737 Values.push_back(
738 RuntimeDebugBuilder::getPrintableString(Builder, "="));
739 Values.push_back(getNewValue(Stmt, OpInst, BBMap, LTS,
740 LI.getLoopFor(Inst->getParent())));
741 Encountered.insert(OpInst);
742 }
743 }
744
745 Encountered.insert(Inst);
746 }
747
748 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n"));
749 } else {
750 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")\n"));
751 }
752
753 RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values));
754 }
755
generateScalarStores(ScopStmt & Stmt,LoopToScevMapT & LTS,ValueMapT & BBMap,__isl_keep isl_id_to_ast_expr * NewAccesses)756 void BlockGenerator::generateScalarStores(
757 ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap,
758 __isl_keep isl_id_to_ast_expr *NewAccesses) {
759 Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
760
761 assert(Stmt.isBlockStmt() &&
762 "Region statements need to use the generateScalarStores() function in "
763 "the RegionGenerator");
764
765 for (MemoryAccess *MA : Stmt) {
766 if (MA->isOriginalArrayKind() || MA->isRead())
767 continue;
768
769 isl::set AccDom = MA->getAccessRelation().domain();
770 std::string Subject = MA->getId().get_name();
771
772 generateConditionalExecution(
773 Stmt, AccDom, Subject.c_str(), [&, this, MA]() {
774 Value *Val = MA->getAccessValue();
775 if (MA->isAnyPHIKind()) {
776 assert(MA->getIncoming().size() >= 1 &&
777 "Block statements have exactly one exiting block, or "
778 "multiple but "
779 "with same incoming block and value");
780 assert(std::all_of(MA->getIncoming().begin(),
781 MA->getIncoming().end(),
782 [&](std::pair<BasicBlock *, Value *> p) -> bool {
783 return p.first == Stmt.getBasicBlock();
784 }) &&
785 "Incoming block must be statement's block");
786 Val = MA->getIncoming()[0].second;
787 }
788 auto Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
789 BBMap, NewAccesses);
790
791 Val = getNewValue(Stmt, Val, BBMap, LTS, L);
792 assert((!isa<Instruction>(Val) ||
793 DT.dominates(cast<Instruction>(Val)->getParent(),
794 Builder.GetInsertBlock())) &&
795 "Domination violation");
796 assert((!isa<Instruction>(Address) ||
797 DT.dominates(cast<Instruction>(Address)->getParent(),
798 Builder.GetInsertBlock())) &&
799 "Domination violation");
800
801 // The new Val might have a different type than the old Val due to
802 // ScalarEvolution looking through bitcasts.
803 Address = Builder.CreateBitOrPointerCast(
804 Address, Val->getType()->getPointerTo(
805 Address->getType()->getPointerAddressSpace()));
806
807 Builder.CreateStore(Val, Address);
808 });
809 }
810 }
811
createScalarInitialization(Scop & S)812 void BlockGenerator::createScalarInitialization(Scop &S) {
813 BasicBlock *ExitBB = S.getExit();
814 BasicBlock *PreEntryBB = S.getEnteringBlock();
815
816 Builder.SetInsertPoint(&*StartBlock->begin());
817
818 for (auto &Array : S.arrays()) {
819 if (Array->getNumberOfDimensions() != 0)
820 continue;
821 if (Array->isPHIKind()) {
822 // For PHI nodes, the only values we need to store are the ones that
823 // reach the PHI node from outside the region. In general there should
824 // only be one such incoming edge and this edge should enter through
825 // 'PreEntryBB'.
826 auto PHI = cast<PHINode>(Array->getBasePtr());
827
828 for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
829 if (!S.contains(*BI) && *BI != PreEntryBB)
830 llvm_unreachable("Incoming edges from outside the scop should always "
831 "come from PreEntryBB");
832
833 int Idx = PHI->getBasicBlockIndex(PreEntryBB);
834 if (Idx < 0)
835 continue;
836
837 Value *ScalarValue = PHI->getIncomingValue(Idx);
838
839 Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array));
840 continue;
841 }
842
843 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
844
845 if (Inst && S.contains(Inst))
846 continue;
847
848 // PHI nodes that are not marked as such in their SAI object are either exit
849 // PHI nodes we model as common scalars but without initialization, or
850 // incoming phi nodes that need to be initialized. Check if the first is the
851 // case for Inst and do not create and initialize memory if so.
852 if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
853 if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
854 continue;
855
856 Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array));
857 }
858 }
859
createScalarFinalization(Scop & S)860 void BlockGenerator::createScalarFinalization(Scop &S) {
861 // The exit block of the __unoptimized__ region.
862 BasicBlock *ExitBB = S.getExitingBlock();
863 // The merge block __just after__ the region and the optimized region.
864 BasicBlock *MergeBB = S.getExit();
865
866 // The exit block of the __optimized__ region.
867 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
868 if (OptExitBB == ExitBB)
869 OptExitBB = *(++pred_begin(MergeBB));
870
871 Builder.SetInsertPoint(OptExitBB->getTerminator());
872 for (const auto &EscapeMapping : EscapeMap) {
873 // Extract the escaping instruction and the escaping users as well as the
874 // alloca the instruction was demoted to.
875 Instruction *EscapeInst = EscapeMapping.first;
876 const auto &EscapeMappingValue = EscapeMapping.second;
877 const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
878 auto *ScalarAddr = cast<AllocaInst>(&*EscapeMappingValue.first);
879
880 // Reload the demoted instruction in the optimized version of the SCoP.
881 Value *EscapeInstReload =
882 Builder.CreateLoad(ScalarAddr->getAllocatedType(), ScalarAddr,
883 EscapeInst->getName() + ".final_reload");
884 EscapeInstReload =
885 Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
886
887 // Create the merge PHI that merges the optimized and unoptimized version.
888 PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
889 EscapeInst->getName() + ".merge");
890 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
891
892 // Add the respective values to the merge PHI.
893 MergePHI->addIncoming(EscapeInstReload, OptExitBB);
894 MergePHI->addIncoming(EscapeInst, ExitBB);
895
896 // The information of scalar evolution about the escaping instruction needs
897 // to be revoked so the new merged instruction will be used.
898 if (SE.isSCEVable(EscapeInst->getType()))
899 SE.forgetValue(EscapeInst);
900
901 // Replace all uses of the demoted instruction with the merge PHI.
902 for (Instruction *EUser : EscapeUsers)
903 EUser->replaceUsesOfWith(EscapeInst, MergePHI);
904 }
905 }
906
findOutsideUsers(Scop & S)907 void BlockGenerator::findOutsideUsers(Scop &S) {
908 for (auto &Array : S.arrays()) {
909
910 if (Array->getNumberOfDimensions() != 0)
911 continue;
912
913 if (Array->isPHIKind())
914 continue;
915
916 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
917
918 if (!Inst)
919 continue;
920
921 // Scop invariant hoisting moves some of the base pointers out of the scop.
922 // We can ignore these, as the invariant load hoisting already registers the
923 // relevant outside users.
924 if (!S.contains(Inst))
925 continue;
926
927 handleOutsideUsers(S, Array);
928 }
929 }
930
createExitPHINodeMerges(Scop & S)931 void BlockGenerator::createExitPHINodeMerges(Scop &S) {
932 if (S.hasSingleExitEdge())
933 return;
934
935 auto *ExitBB = S.getExitingBlock();
936 auto *MergeBB = S.getExit();
937 auto *AfterMergeBB = MergeBB->getSingleSuccessor();
938 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
939 if (OptExitBB == ExitBB)
940 OptExitBB = *(++pred_begin(MergeBB));
941
942 Builder.SetInsertPoint(OptExitBB->getTerminator());
943
944 for (auto &SAI : S.arrays()) {
945 auto *Val = SAI->getBasePtr();
946
947 // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
948 // the original PHI's value or the reloaded incoming values from the
949 // generated code. An llvm::Value is merged between the original code's
950 // value or the generated one.
951 if (!SAI->isExitPHIKind())
952 continue;
953
954 PHINode *PHI = dyn_cast<PHINode>(Val);
955 if (!PHI)
956 continue;
957
958 if (PHI->getParent() != AfterMergeBB)
959 continue;
960
961 std::string Name = PHI->getName().str();
962 Value *ScalarAddr = getOrCreateAlloca(SAI);
963 Value *Reload = Builder.CreateLoad(SAI->getElementType(), ScalarAddr,
964 Name + ".ph.final_reload");
965 Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
966 Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
967 assert((!isa<Instruction>(OriginalValue) ||
968 cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&
969 "Original value must no be one we just generated.");
970 auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
971 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
972 MergePHI->addIncoming(Reload, OptExitBB);
973 MergePHI->addIncoming(OriginalValue, ExitBB);
974 int Idx = PHI->getBasicBlockIndex(MergeBB);
975 PHI->setIncomingValue(Idx, MergePHI);
976 }
977 }
978
invalidateScalarEvolution(Scop & S)979 void BlockGenerator::invalidateScalarEvolution(Scop &S) {
980 for (auto &Stmt : S)
981 if (Stmt.isCopyStmt())
982 continue;
983 else if (Stmt.isBlockStmt())
984 for (auto &Inst : *Stmt.getBasicBlock())
985 SE.forgetValue(&Inst);
986 else if (Stmt.isRegionStmt())
987 for (auto *BB : Stmt.getRegion()->blocks())
988 for (auto &Inst : *BB)
989 SE.forgetValue(&Inst);
990 else
991 llvm_unreachable("Unexpected statement type found");
992
993 // Invalidate SCEV of loops surrounding the EscapeUsers.
994 for (const auto &EscapeMapping : EscapeMap) {
995 const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second;
996 for (Instruction *EUser : EscapeUsers) {
997 if (Loop *L = LI.getLoopFor(EUser->getParent()))
998 while (L) {
999 SE.forgetLoop(L);
1000 L = L->getParentLoop();
1001 }
1002 }
1003 }
1004 }
1005
finalizeSCoP(Scop & S)1006 void BlockGenerator::finalizeSCoP(Scop &S) {
1007 findOutsideUsers(S);
1008 createScalarInitialization(S);
1009 createExitPHINodeMerges(S);
1010 createScalarFinalization(S);
1011 invalidateScalarEvolution(S);
1012 }
1013
VectorBlockGenerator(BlockGenerator & BlockGen,std::vector<LoopToScevMapT> & VLTS,isl_map * Schedule)1014 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
1015 std::vector<LoopToScevMapT> &VLTS,
1016 isl_map *Schedule)
1017 : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
1018 assert(Schedule && "No statement domain provided");
1019 }
1020
getVectorValue(ScopStmt & Stmt,Value * Old,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps,Loop * L)1021 Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
1022 ValueMapT &VectorMap,
1023 VectorValueMapT &ScalarMaps,
1024 Loop *L) {
1025 if (Value *NewValue = VectorMap.lookup(Old))
1026 return NewValue;
1027
1028 int Width = getVectorWidth();
1029
1030 Value *Vector = UndefValue::get(FixedVectorType::get(Old->getType(), Width));
1031
1032 for (int Lane = 0; Lane < Width; Lane++)
1033 Vector = Builder.CreateInsertElement(
1034 Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
1035 Builder.getInt32(Lane));
1036
1037 VectorMap[Old] = Vector;
1038
1039 return Vector;
1040 }
1041
generateStrideOneLoad(ScopStmt & Stmt,LoadInst * Load,VectorValueMapT & ScalarMaps,__isl_keep isl_id_to_ast_expr * NewAccesses,bool NegativeStride=false)1042 Value *VectorBlockGenerator::generateStrideOneLoad(
1043 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
1044 __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
1045 unsigned VectorWidth = getVectorWidth();
1046 Type *VectorType = FixedVectorType::get(Load->getType(), VectorWidth);
1047 Type *VectorPtrType =
1048 PointerType::get(VectorType, Load->getPointerAddressSpace());
1049 unsigned Offset = NegativeStride ? VectorWidth - 1 : 0;
1050
1051 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
1052 VLTS[Offset], NewAccesses);
1053 Value *VectorPtr =
1054 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
1055 LoadInst *VecLoad = Builder.CreateLoad(VectorType, VectorPtr,
1056 Load->getName() + "_p_vec_full");
1057 if (!Aligned)
1058 VecLoad->setAlignment(Align(8));
1059
1060 if (NegativeStride) {
1061 SmallVector<Constant *, 16> Indices;
1062 for (int i = VectorWidth - 1; i >= 0; i--)
1063 Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i));
1064 Constant *SV = llvm::ConstantVector::get(Indices);
1065 Value *RevVecLoad = Builder.CreateShuffleVector(
1066 VecLoad, VecLoad, SV, Load->getName() + "_reverse");
1067 return RevVecLoad;
1068 }
1069
1070 return VecLoad;
1071 }
1072
generateStrideZeroLoad(ScopStmt & Stmt,LoadInst * Load,ValueMapT & BBMap,__isl_keep isl_id_to_ast_expr * NewAccesses)1073 Value *VectorBlockGenerator::generateStrideZeroLoad(
1074 ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
1075 __isl_keep isl_id_to_ast_expr *NewAccesses) {
1076 Type *VectorType = FixedVectorType::get(Load->getType(), 1);
1077 Type *VectorPtrType =
1078 PointerType::get(VectorType, Load->getPointerAddressSpace());
1079 Value *NewPointer =
1080 generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
1081 Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
1082 Load->getName() + "_p_vec_p");
1083 LoadInst *ScalarLoad = Builder.CreateLoad(VectorType, VectorPtr,
1084 Load->getName() + "_p_splat_one");
1085
1086 if (!Aligned)
1087 ScalarLoad->setAlignment(Align(8));
1088
1089 Constant *SplatVector = Constant::getNullValue(
1090 FixedVectorType::get(Builder.getInt32Ty(), getVectorWidth()));
1091
1092 Value *VectorLoad = Builder.CreateShuffleVector(
1093 ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
1094 return VectorLoad;
1095 }
1096
generateUnknownStrideLoad(ScopStmt & Stmt,LoadInst * Load,VectorValueMapT & ScalarMaps,__isl_keep isl_id_to_ast_expr * NewAccesses)1097 Value *VectorBlockGenerator::generateUnknownStrideLoad(
1098 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
1099 __isl_keep isl_id_to_ast_expr *NewAccesses) {
1100 int VectorWidth = getVectorWidth();
1101 Type *ElemTy = Load->getType();
1102 auto *FVTy = FixedVectorType::get(ElemTy, VectorWidth);
1103
1104 Value *Vector = UndefValue::get(FVTy);
1105
1106 for (int i = 0; i < VectorWidth; i++) {
1107 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
1108 VLTS[i], NewAccesses);
1109 Value *ScalarLoad =
1110 Builder.CreateLoad(ElemTy, NewPointer, Load->getName() + "_p_scalar_");
1111 Vector = Builder.CreateInsertElement(
1112 Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
1113 }
1114
1115 return Vector;
1116 }
1117
generateLoad(ScopStmt & Stmt,LoadInst * Load,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps,__isl_keep isl_id_to_ast_expr * NewAccesses)1118 void VectorBlockGenerator::generateLoad(
1119 ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
1120 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1121 if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
1122 VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
1123 Load->getName() + "_p");
1124 return;
1125 }
1126
1127 if (!VectorType::isValidElementType(Load->getType())) {
1128 for (int i = 0; i < getVectorWidth(); i++)
1129 ScalarMaps[i][Load] =
1130 generateArrayLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
1131 return;
1132 }
1133
1134 const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);
1135
1136 // Make sure we have scalar values available to access the pointer to
1137 // the data location.
1138 extractScalarValues(Load, VectorMap, ScalarMaps);
1139
1140 Value *NewLoad;
1141 if (Access.isStrideZero(isl::manage_copy(Schedule)))
1142 NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
1143 else if (Access.isStrideOne(isl::manage_copy(Schedule)))
1144 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
1145 else if (Access.isStrideX(isl::manage_copy(Schedule), -1))
1146 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
1147 else
1148 NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);
1149
1150 VectorMap[Load] = NewLoad;
1151 }
1152
copyUnaryInst(ScopStmt & Stmt,UnaryInstruction * Inst,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps)1153 void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
1154 ValueMapT &VectorMap,
1155 VectorValueMapT &ScalarMaps) {
1156 int VectorWidth = getVectorWidth();
1157 Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
1158 ScalarMaps, getLoopForStmt(Stmt));
1159
1160 assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction");
1161
1162 const CastInst *Cast = dyn_cast<CastInst>(Inst);
1163 auto *DestType = FixedVectorType::get(Inst->getType(), VectorWidth);
1164 VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
1165 }
1166
copyBinaryInst(ScopStmt & Stmt,BinaryOperator * Inst,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps)1167 void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
1168 ValueMapT &VectorMap,
1169 VectorValueMapT &ScalarMaps) {
1170 Loop *L = getLoopForStmt(Stmt);
1171 Value *OpZero = Inst->getOperand(0);
1172 Value *OpOne = Inst->getOperand(1);
1173
1174 Value *NewOpZero, *NewOpOne;
1175 NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
1176 NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
1177
1178 Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
1179 Inst->getName() + "p_vec");
1180 VectorMap[Inst] = NewInst;
1181 }
1182
copyStore(ScopStmt & Stmt,StoreInst * Store,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps,__isl_keep isl_id_to_ast_expr * NewAccesses)1183 void VectorBlockGenerator::copyStore(
1184 ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
1185 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1186 const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);
1187
1188 Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
1189 ScalarMaps, getLoopForStmt(Stmt));
1190
1191 // Make sure we have scalar values available to access the pointer to
1192 // the data location.
1193 extractScalarValues(Store, VectorMap, ScalarMaps);
1194
1195 if (Access.isStrideOne(isl::manage_copy(Schedule))) {
1196 Type *VectorType = FixedVectorType::get(Store->getValueOperand()->getType(),
1197 getVectorWidth());
1198 Type *VectorPtrType =
1199 PointerType::get(VectorType, Store->getPointerAddressSpace());
1200 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
1201 VLTS[0], NewAccesses);
1202
1203 Value *VectorPtr =
1204 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
1205 StoreInst *Store = Builder.CreateStore(Vector, VectorPtr);
1206
1207 if (!Aligned)
1208 Store->setAlignment(Align(8));
1209 } else {
1210 for (unsigned i = 0; i < ScalarMaps.size(); i++) {
1211 Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
1212 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
1213 VLTS[i], NewAccesses);
1214 Builder.CreateStore(Scalar, NewPointer);
1215 }
1216 }
1217 }
1218
hasVectorOperands(const Instruction * Inst,ValueMapT & VectorMap)1219 bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
1220 ValueMapT &VectorMap) {
1221 for (Value *Operand : Inst->operands())
1222 if (VectorMap.count(Operand))
1223 return true;
1224 return false;
1225 }
1226
extractScalarValues(const Instruction * Inst,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps)1227 bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst,
1228 ValueMapT &VectorMap,
1229 VectorValueMapT &ScalarMaps) {
1230 bool HasVectorOperand = false;
1231 int VectorWidth = getVectorWidth();
1232
1233 for (Value *Operand : Inst->operands()) {
1234 ValueMapT::iterator VecOp = VectorMap.find(Operand);
1235
1236 if (VecOp == VectorMap.end())
1237 continue;
1238
1239 HasVectorOperand = true;
1240 Value *NewVector = VecOp->second;
1241
1242 for (int i = 0; i < VectorWidth; ++i) {
1243 ValueMapT &SM = ScalarMaps[i];
1244
1245 // If there is one scalar extracted, all scalar elements should have
1246 // already been extracted by the code here. So no need to check for the
1247 // existence of all of them.
1248 if (SM.count(Operand))
1249 break;
1250
1251 SM[Operand] =
1252 Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
1253 }
1254 }
1255
1256 return HasVectorOperand;
1257 }
1258
copyInstScalarized(ScopStmt & Stmt,Instruction * Inst,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps,__isl_keep isl_id_to_ast_expr * NewAccesses)1259 void VectorBlockGenerator::copyInstScalarized(
1260 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
1261 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1262 bool HasVectorOperand;
1263 int VectorWidth = getVectorWidth();
1264
1265 HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);
1266
1267 for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++)
1268 BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
1269 VLTS[VectorLane], NewAccesses);
1270
1271 if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand)
1272 return;
1273
1274 // Make the result available as vector value.
1275 auto *FVTy = FixedVectorType::get(Inst->getType(), VectorWidth);
1276 Value *Vector = UndefValue::get(FVTy);
1277
1278 for (int i = 0; i < VectorWidth; i++)
1279 Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst],
1280 Builder.getInt32(i));
1281
1282 VectorMap[Inst] = Vector;
1283 }
1284
getVectorWidth()1285 int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }
1286
copyInstruction(ScopStmt & Stmt,Instruction * Inst,ValueMapT & VectorMap,VectorValueMapT & ScalarMaps,__isl_keep isl_id_to_ast_expr * NewAccesses)1287 void VectorBlockGenerator::copyInstruction(
1288 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
1289 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1290 // Terminator instructions control the control flow. They are explicitly
1291 // expressed in the clast and do not need to be copied.
1292 if (Inst->isTerminator())
1293 return;
1294
1295 if (canSyntheziseInStmt(Stmt, Inst))
1296 return;
1297
1298 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
1299 generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
1300 return;
1301 }
1302
1303 if (hasVectorOperands(Inst, VectorMap)) {
1304 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
1305 // Identified as redundant by -polly-simplify.
1306 if (!Stmt.getArrayAccessOrNULLFor(Store))
1307 return;
1308
1309 copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
1310 return;
1311 }
1312
1313 if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
1314 copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
1315 return;
1316 }
1317
1318 if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
1319 copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
1320 return;
1321 }
1322
1323 // Fallthrough: We generate scalar instructions, if we don't know how to
1324 // generate vector code.
1325 }
1326
1327 copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
1328 }
1329
generateScalarVectorLoads(ScopStmt & Stmt,ValueMapT & VectorBlockMap)1330 void VectorBlockGenerator::generateScalarVectorLoads(
1331 ScopStmt &Stmt, ValueMapT &VectorBlockMap) {
1332 for (MemoryAccess *MA : Stmt) {
1333 if (MA->isArrayKind() || MA->isWrite())
1334 continue;
1335
1336 auto *Address = getOrCreateAlloca(*MA);
1337 Type *VectorType = FixedVectorType::get(MA->getElementType(), 1);
1338 Type *VectorPtrType = PointerType::get(
1339 VectorType, Address->getType()->getPointerAddressSpace());
1340 Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType,
1341 Address->getName() + "_p_vec_p");
1342 auto *Val = Builder.CreateLoad(VectorType, VectorPtr,
1343 Address->getName() + ".reload");
1344 Constant *SplatVector = Constant::getNullValue(
1345 FixedVectorType::get(Builder.getInt32Ty(), getVectorWidth()));
1346
1347 Value *VectorVal = Builder.CreateShuffleVector(
1348 Val, Val, SplatVector, Address->getName() + "_p_splat");
1349 VectorBlockMap[MA->getAccessValue()] = VectorVal;
1350 }
1351 }
1352
verifyNoScalarStores(ScopStmt & Stmt)1353 void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) {
1354 for (MemoryAccess *MA : Stmt) {
1355 if (MA->isArrayKind() || MA->isRead())
1356 continue;
1357
1358 llvm_unreachable("Scalar stores not expected in vector loop");
1359 }
1360 }
1361
copyStmt(ScopStmt & Stmt,__isl_keep isl_id_to_ast_expr * NewAccesses)1362 void VectorBlockGenerator::copyStmt(
1363 ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1364 assert(Stmt.isBlockStmt() &&
1365 "TODO: Only block statements can be copied by the vector block "
1366 "generator");
1367
1368 BasicBlock *BB = Stmt.getBasicBlock();
1369 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
1370 &*Builder.GetInsertPoint(), &DT, &LI);
1371 CopyBB->setName("polly.stmt." + BB->getName());
1372 Builder.SetInsertPoint(&CopyBB->front());
1373
1374 // Create two maps that store the mapping from the original instructions of
1375 // the old basic block to their copies in the new basic block. Those maps
1376 // are basic block local.
1377 //
1378 // As vector code generation is supported there is one map for scalar values
1379 // and one for vector values.
1380 //
1381 // In case we just do scalar code generation, the vectorMap is not used and
1382 // the scalarMap has just one dimension, which contains the mapping.
1383 //
1384 // In case vector code generation is done, an instruction may either appear
1385 // in the vector map once (as it is calculating >vectorwidth< values at a
1386 // time. Or (if the values are calculated using scalar operations), it
1387 // appears once in every dimension of the scalarMap.
1388 VectorValueMapT ScalarBlockMap(getVectorWidth());
1389 ValueMapT VectorBlockMap;
1390
1391 generateScalarVectorLoads(Stmt, VectorBlockMap);
1392
1393 for (Instruction *Inst : Stmt.getInstructions())
1394 copyInstruction(Stmt, Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
1395
1396 verifyNoScalarStores(Stmt);
1397 }
1398
repairDominance(BasicBlock * BB,BasicBlock * BBCopy)1399 BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
1400 BasicBlock *BBCopy) {
1401
1402 BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();
1403 BasicBlock *BBCopyIDom = EndBlockMap.lookup(BBIDom);
1404
1405 if (BBCopyIDom)
1406 DT.changeImmediateDominator(BBCopy, BBCopyIDom);
1407
1408 return StartBlockMap.lookup(BBIDom);
1409 }
1410
1411 // This is to determine whether an llvm::Value (defined in @p BB) is usable when
1412 // leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1413 // does not work in cases where the exit block has edges from outside the
1414 // region. In that case the llvm::Value would never be usable in in the exit
1415 // block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1416 // for the subregion's exiting edges only. We need to determine whether an
1417 // llvm::Value is usable in there. We do this by checking whether it dominates
1418 // all exiting blocks individually.
isDominatingSubregionExit(const DominatorTree & DT,Region * R,BasicBlock * BB)1419 static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
1420 BasicBlock *BB) {
1421 for (auto ExitingBB : predecessors(R->getExit())) {
1422 // Check for non-subregion incoming edges.
1423 if (!R->contains(ExitingBB))
1424 continue;
1425
1426 if (!DT.dominates(BB, ExitingBB))
1427 return false;
1428 }
1429
1430 return true;
1431 }
1432
1433 // Find the direct dominator of the subregion's exit block if the subregion was
1434 // simplified.
findExitDominator(DominatorTree & DT,Region * R)1435 static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
1436 BasicBlock *Common = nullptr;
1437 for (auto ExitingBB : predecessors(R->getExit())) {
1438 // Check for non-subregion incoming edges.
1439 if (!R->contains(ExitingBB))
1440 continue;
1441
1442 // First exiting edge.
1443 if (!Common) {
1444 Common = ExitingBB;
1445 continue;
1446 }
1447
1448 Common = DT.findNearestCommonDominator(Common, ExitingBB);
1449 }
1450
1451 assert(Common && R->contains(Common));
1452 return Common;
1453 }
1454
copyStmt(ScopStmt & Stmt,LoopToScevMapT & LTS,isl_id_to_ast_expr * IdToAstExp)1455 void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S,
1456 isl_id_to_ast_expr *IdToAstExp) {
1457 assert(Stmt.isRegionStmt() &&
1458 "Only region statements can be copied by the region generator");
1459
1460 // Forget all old mappings.
1461 StartBlockMap.clear();
1462 EndBlockMap.clear();
1463 RegionMaps.clear();
1464 IncompletePHINodeMap.clear();
1465
1466 // Collection of all values related to this subregion.
1467 ValueMapT ValueMap;
1468
1469 // The region represented by the statement.
1470 Region *R = Stmt.getRegion();
1471
1472 // Create a dedicated entry for the region where we can reload all demoted
1473 // inputs.
1474 BasicBlock *EntryBB = R->getEntry();
1475 BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
1476 &*Builder.GetInsertPoint(), &DT, &LI);
1477 EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
1478 Builder.SetInsertPoint(&EntryBBCopy->front());
1479
1480 ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
1481 generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
1482 generateBeginStmtTrace(Stmt, LTS, EntryBBMap);
1483
1484 for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
1485 if (!R->contains(*PI)) {
1486 StartBlockMap[*PI] = EntryBBCopy;
1487 EndBlockMap[*PI] = EntryBBCopy;
1488 }
1489
1490 // Iterate over all blocks in the region in a breadth-first search.
1491 std::deque<BasicBlock *> Blocks;
1492 SmallSetVector<BasicBlock *, 8> SeenBlocks;
1493 Blocks.push_back(EntryBB);
1494 SeenBlocks.insert(EntryBB);
1495
1496 while (!Blocks.empty()) {
1497 BasicBlock *BB = Blocks.front();
1498 Blocks.pop_front();
1499
1500 // First split the block and update dominance information.
1501 BasicBlock *BBCopy = splitBB(BB);
1502 BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);
1503
1504 // Get the mapping for this block and initialize it with either the scalar
1505 // loads from the generated entering block (which dominates all blocks of
1506 // this subregion) or the maps of the immediate dominator, if part of the
1507 // subregion. The latter necessarily includes the former.
1508 ValueMapT *InitBBMap;
1509 if (BBCopyIDom) {
1510 assert(RegionMaps.count(BBCopyIDom));
1511 InitBBMap = &RegionMaps[BBCopyIDom];
1512 } else
1513 InitBBMap = &EntryBBMap;
1514 auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
1515 ValueMapT &RegionMap = Inserted.first->second;
1516
1517 // Copy the block with the BlockGenerator.
1518 Builder.SetInsertPoint(&BBCopy->front());
1519 copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
1520
1521 // In order to remap PHI nodes we store also basic block mappings.
1522 StartBlockMap[BB] = BBCopy;
1523 EndBlockMap[BB] = Builder.GetInsertBlock();
1524
1525 // Add values to incomplete PHI nodes waiting for this block to be copied.
1526 for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
1527 addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
1528 IncompletePHINodeMap[BB].clear();
1529
1530 // And continue with new successors inside the region.
1531 for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
1532 if (R->contains(*SI) && SeenBlocks.insert(*SI))
1533 Blocks.push_back(*SI);
1534
1535 // Remember value in case it is visible after this subregion.
1536 if (isDominatingSubregionExit(DT, R, BB))
1537 ValueMap.insert(RegionMap.begin(), RegionMap.end());
1538 }
1539
1540 // Now create a new dedicated region exit block and add it to the region map.
1541 BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
1542 &*Builder.GetInsertPoint(), &DT, &LI);
1543 ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
1544 StartBlockMap[R->getExit()] = ExitBBCopy;
1545 EndBlockMap[R->getExit()] = ExitBBCopy;
1546
1547 BasicBlock *ExitDomBBCopy = EndBlockMap.lookup(findExitDominator(DT, R));
1548 assert(ExitDomBBCopy &&
1549 "Common exit dominator must be within region; at least the entry node "
1550 "must match");
1551 DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
1552
1553 // As the block generator doesn't handle control flow we need to add the
1554 // region control flow by hand after all blocks have been copied.
1555 for (BasicBlock *BB : SeenBlocks) {
1556
1557 BasicBlock *BBCopyStart = StartBlockMap[BB];
1558 BasicBlock *BBCopyEnd = EndBlockMap[BB];
1559 Instruction *TI = BB->getTerminator();
1560 if (isa<UnreachableInst>(TI)) {
1561 while (!BBCopyEnd->empty())
1562 BBCopyEnd->begin()->eraseFromParent();
1563 new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd);
1564 continue;
1565 }
1566
1567 Instruction *BICopy = BBCopyEnd->getTerminator();
1568
1569 ValueMapT &RegionMap = RegionMaps[BBCopyStart];
1570 RegionMap.insert(StartBlockMap.begin(), StartBlockMap.end());
1571
1572 Builder.SetInsertPoint(BICopy);
1573 copyInstScalar(Stmt, TI, RegionMap, LTS);
1574 BICopy->eraseFromParent();
1575 }
1576
1577 // Add counting PHI nodes to all loops in the region that can be used as
1578 // replacement for SCEVs referring to the old loop.
1579 for (BasicBlock *BB : SeenBlocks) {
1580 Loop *L = LI.getLoopFor(BB);
1581 if (L == nullptr || L->getHeader() != BB || !R->contains(L))
1582 continue;
1583
1584 BasicBlock *BBCopy = StartBlockMap[BB];
1585 Value *NullVal = Builder.getInt32(0);
1586 PHINode *LoopPHI =
1587 PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");
1588 Instruction *LoopPHIInc = BinaryOperator::CreateAdd(
1589 LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");
1590 LoopPHI->insertBefore(&BBCopy->front());
1591 LoopPHIInc->insertBefore(BBCopy->getTerminator());
1592
1593 for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) {
1594 if (!R->contains(PredBB))
1595 continue;
1596 if (L->contains(PredBB))
1597 LoopPHI->addIncoming(LoopPHIInc, EndBlockMap[PredBB]);
1598 else
1599 LoopPHI->addIncoming(NullVal, EndBlockMap[PredBB]);
1600 }
1601
1602 for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
1603 if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
1604 LoopPHI->addIncoming(NullVal, PredBBCopy);
1605
1606 LTS[L] = SE.getUnknown(LoopPHI);
1607 }
1608
1609 // Continue generating code in the exit block.
1610 Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
1611
1612 // Write values visible to other statements.
1613 generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp);
1614 StartBlockMap.clear();
1615 EndBlockMap.clear();
1616 RegionMaps.clear();
1617 IncompletePHINodeMap.clear();
1618 }
1619
buildExitPHI(MemoryAccess * MA,LoopToScevMapT & LTS,ValueMapT & BBMap,Loop * L)1620 PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S,
1621 ValueMapT &BBMap, Loop *L) {
1622 ScopStmt *Stmt = MA->getStatement();
1623 Region *SubR = Stmt->getRegion();
1624 auto Incoming = MA->getIncoming();
1625
1626 PollyIRBuilder::InsertPointGuard IPGuard(Builder);
1627 PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
1628 BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
1629
1630 // This can happen if the subregion is simplified after the ScopStmts
1631 // have been created; simplification happens as part of CodeGeneration.
1632 if (OrigPHI->getParent() != SubR->getExit()) {
1633 BasicBlock *FormerExit = SubR->getExitingBlock();
1634 if (FormerExit)
1635 NewSubregionExit = StartBlockMap.lookup(FormerExit);
1636 }
1637
1638 PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
1639 "polly." + OrigPHI->getName(),
1640 NewSubregionExit->getFirstNonPHI());
1641
1642 // Add the incoming values to the PHI.
1643 for (auto &Pair : Incoming) {
1644 BasicBlock *OrigIncomingBlock = Pair.first;
1645 BasicBlock *NewIncomingBlockStart = StartBlockMap.lookup(OrigIncomingBlock);
1646 BasicBlock *NewIncomingBlockEnd = EndBlockMap.lookup(OrigIncomingBlock);
1647 Builder.SetInsertPoint(NewIncomingBlockEnd->getTerminator());
1648 assert(RegionMaps.count(NewIncomingBlockStart));
1649 assert(RegionMaps.count(NewIncomingBlockEnd));
1650 ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlockStart];
1651
1652 Value *OrigIncomingValue = Pair.second;
1653 Value *NewIncomingValue =
1654 getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
1655 NewPHI->addIncoming(NewIncomingValue, NewIncomingBlockEnd);
1656 }
1657
1658 return NewPHI;
1659 }
1660
getExitScalar(MemoryAccess * MA,LoopToScevMapT & LTS,ValueMapT & BBMap)1661 Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT <S,
1662 ValueMapT &BBMap) {
1663 ScopStmt *Stmt = MA->getStatement();
1664
1665 // TODO: Add some test cases that ensure this is really the right choice.
1666 Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());
1667
1668 if (MA->isAnyPHIKind()) {
1669 auto Incoming = MA->getIncoming();
1670 assert(!Incoming.empty() &&
1671 "PHI WRITEs must have originate from at least one incoming block");
1672
1673 // If there is only one incoming value, we do not need to create a PHI.
1674 if (Incoming.size() == 1) {
1675 Value *OldVal = Incoming[0].second;
1676 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1677 }
1678
1679 return buildExitPHI(MA, LTS, BBMap, L);
1680 }
1681
1682 // MemoryKind::Value accesses leaving the subregion must dominate the exit
1683 // block; just pass the copied value.
1684 Value *OldVal = MA->getAccessValue();
1685 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1686 }
1687
generateScalarStores(ScopStmt & Stmt,LoopToScevMapT & LTS,ValueMapT & BBMap,__isl_keep isl_id_to_ast_expr * NewAccesses)1688 void RegionGenerator::generateScalarStores(
1689 ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap,
1690 __isl_keep isl_id_to_ast_expr *NewAccesses) {
1691 assert(Stmt.getRegion() &&
1692 "Block statements need to use the generateScalarStores() "
1693 "function in the BlockGenerator");
1694
1695 // Get the exit scalar values before generating the writes.
1696 // This is necessary because RegionGenerator::getExitScalar may insert
1697 // PHINodes that depend on the region's exiting blocks. But
1698 // BlockGenerator::generateConditionalExecution may insert a new basic block
1699 // such that the current basic block is not a direct successor of the exiting
1700 // blocks anymore. Hence, build the PHINodes while the current block is still
1701 // the direct successor.
1702 SmallDenseMap<MemoryAccess *, Value *> NewExitScalars;
1703 for (MemoryAccess *MA : Stmt) {
1704 if (MA->isOriginalArrayKind() || MA->isRead())
1705 continue;
1706
1707 Value *NewVal = getExitScalar(MA, LTS, BBMap);
1708 NewExitScalars[MA] = NewVal;
1709 }
1710
1711 for (MemoryAccess *MA : Stmt) {
1712 if (MA->isOriginalArrayKind() || MA->isRead())
1713 continue;
1714
1715 isl::set AccDom = MA->getAccessRelation().domain();
1716 std::string Subject = MA->getId().get_name();
1717 generateConditionalExecution(
1718 Stmt, AccDom, Subject.c_str(), [&, this, MA]() {
1719 Value *NewVal = NewExitScalars.lookup(MA);
1720 assert(NewVal && "The exit scalar must be determined before");
1721 Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
1722 BBMap, NewAccesses);
1723 assert((!isa<Instruction>(NewVal) ||
1724 DT.dominates(cast<Instruction>(NewVal)->getParent(),
1725 Builder.GetInsertBlock())) &&
1726 "Domination violation");
1727 assert((!isa<Instruction>(Address) ||
1728 DT.dominates(cast<Instruction>(Address)->getParent(),
1729 Builder.GetInsertBlock())) &&
1730 "Domination violation");
1731 Builder.CreateStore(NewVal, Address);
1732 });
1733 }
1734 }
1735
addOperandToPHI(ScopStmt & Stmt,PHINode * PHI,PHINode * PHICopy,BasicBlock * IncomingBB,LoopToScevMapT & LTS)1736 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
1737 PHINode *PHICopy, BasicBlock *IncomingBB,
1738 LoopToScevMapT <S) {
1739 // If the incoming block was not yet copied mark this PHI as incomplete.
1740 // Once the block will be copied the incoming value will be added.
1741 BasicBlock *BBCopyStart = StartBlockMap[IncomingBB];
1742 BasicBlock *BBCopyEnd = EndBlockMap[IncomingBB];
1743 if (!BBCopyStart) {
1744 assert(!BBCopyEnd);
1745 assert(Stmt.represents(IncomingBB) &&
1746 "Bad incoming block for PHI in non-affine region");
1747 IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
1748 return;
1749 }
1750
1751 assert(RegionMaps.count(BBCopyStart) &&
1752 "Incoming PHI block did not have a BBMap");
1753 ValueMapT &BBCopyMap = RegionMaps[BBCopyStart];
1754
1755 Value *OpCopy = nullptr;
1756
1757 if (Stmt.represents(IncomingBB)) {
1758 Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
1759
1760 // If the current insert block is different from the PHIs incoming block
1761 // change it, otherwise do not.
1762 auto IP = Builder.GetInsertPoint();
1763 if (IP->getParent() != BBCopyEnd)
1764 Builder.SetInsertPoint(BBCopyEnd->getTerminator());
1765 OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
1766 if (IP->getParent() != BBCopyEnd)
1767 Builder.SetInsertPoint(&*IP);
1768 } else {
1769 // All edges from outside the non-affine region become a single edge
1770 // in the new copy of the non-affine region. Make sure to only add the
1771 // corresponding edge the first time we encounter a basic block from
1772 // outside the non-affine region.
1773 if (PHICopy->getBasicBlockIndex(BBCopyEnd) >= 0)
1774 return;
1775
1776 // Get the reloaded value.
1777 OpCopy = getNewValue(Stmt, PHI, BBCopyMap, LTS, getLoopForStmt(Stmt));
1778 }
1779
1780 assert(OpCopy && "Incoming PHI value was not copied properly");
1781 PHICopy->addIncoming(OpCopy, BBCopyEnd);
1782 }
1783
copyPHIInstruction(ScopStmt & Stmt,PHINode * PHI,ValueMapT & BBMap,LoopToScevMapT & LTS)1784 void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1785 ValueMapT &BBMap,
1786 LoopToScevMapT <S) {
1787 unsigned NumIncoming = PHI->getNumIncomingValues();
1788 PHINode *PHICopy =
1789 Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());
1790 PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
1791 BBMap[PHI] = PHICopy;
1792
1793 for (BasicBlock *IncomingBB : PHI->blocks())
1794 addOperandToPHI(Stmt, PHI, PHICopy, IncomingBB, LTS);
1795 }
1796