1 //===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the BlockGenerator and VectorBlockGenerator classes,
11 // which generate sequential code and vectorized code for a polyhedral
12 // statement, respectively.
14 //===----------------------------------------------------------------------===//
16 #include "polly/CodeGen/BlockGenerators.h"
17 #include "polly/CodeGen/CodeGeneration.h"
18 #include "polly/CodeGen/IslExprBuilder.h"
19 #include "polly/CodeGen/RuntimeDebugBuilder.h"
20 #include "polly/Options.h"
21 #include "polly/ScopInfo.h"
22 #include "polly/Support/GICHelper.h"
23 #include "polly/Support/SCEVValidator.h"
24 #include "polly/Support/ScopHelper.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/RegionInfo.h"
27 #include "llvm/Analysis/ScalarEvolution.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
31 #include "llvm/Transforms/Utils/Local.h"
34 #include "isl/ast_build.h"
39 using namespace polly
;
41 static cl::opt
<bool> Aligned("enable-polly-aligned",
42 cl::desc("Assumed aligned memory accesses."),
43 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
44 cl::cat(PollyCategory
));
46 static cl::opt
<bool> DebugPrinting(
47 "polly-codegen-add-debug-printing",
48 cl::desc("Add printf calls that show the values loaded/stored."),
49 cl::Hidden
, cl::init(false), cl::ZeroOrMore
, cl::cat(PollyCategory
));
51 BlockGenerator::BlockGenerator(PollyIRBuilder
&B
, LoopInfo
&LI
,
52 ScalarEvolution
&SE
, DominatorTree
&DT
,
53 ScalarAllocaMapTy
&ScalarMap
,
54 ScalarAllocaMapTy
&PHIOpMap
,
55 EscapeUsersAllocaMapTy
&EscapeMap
,
57 IslExprBuilder
*ExprBuilder
)
58 : Builder(B
), LI(LI
), SE(SE
), ExprBuilder(ExprBuilder
), DT(DT
),
59 EntryBB(nullptr), PHIOpMap(PHIOpMap
), ScalarMap(ScalarMap
),
60 EscapeMap(EscapeMap
), GlobalMap(GlobalMap
) {}
62 Value
*BlockGenerator::trySynthesizeNewValue(ScopStmt
&Stmt
, Value
*Old
,
66 if (!SE
.isSCEVable(Old
->getType()))
69 const SCEV
*Scev
= SE
.getSCEVAtScope(Old
, L
);
73 if (isa
<SCEVCouldNotCompute
>(Scev
))
76 const SCEV
*NewScev
= SCEVLoopAddRecRewriter::rewrite(Scev
, LTS
, SE
);
78 VTV
.insert(BBMap
.begin(), BBMap
.end());
79 VTV
.insert(GlobalMap
.begin(), GlobalMap
.end());
81 Scop
&S
= *Stmt
.getParent();
82 const DataLayout
&DL
= S
.getFunction().getParent()->getDataLayout();
83 auto IP
= Builder
.GetInsertPoint();
85 assert(IP
!= Builder
.GetInsertBlock()->end() &&
86 "Only instructions can be insert points for SCEVExpander");
88 expandCodeFor(S
, SE
, DL
, "polly", NewScev
, Old
->getType(), &*IP
, &VTV
);
90 BBMap
[Old
] = Expanded
;
94 Value
*BlockGenerator::getNewValue(ScopStmt
&Stmt
, Value
*Old
, ValueMapT
&BBMap
,
95 LoopToScevMapT
<S
, Loop
*L
) const {
96 // Constants that do not reference any named value can always remain
97 // unchanged. Handle them early to avoid expensive map lookups. We do not take
98 // the fast-path for external constants which are referenced through globals
99 // as these may need to be rewritten when distributing code accross different
101 if (isa
<Constant
>(Old
) && !isa
<GlobalValue
>(Old
))
104 // Inline asm is like a constant to us.
105 if (isa
<InlineAsm
>(Old
))
108 if (Value
*New
= GlobalMap
.lookup(Old
)) {
109 if (Value
*NewRemapped
= GlobalMap
.lookup(New
))
111 if (Old
->getType()->getScalarSizeInBits() <
112 New
->getType()->getScalarSizeInBits())
113 New
= Builder
.CreateTruncOrBitCast(New
, Old
->getType());
118 if (Value
*New
= BBMap
.lookup(Old
))
121 if (Value
*New
= trySynthesizeNewValue(Stmt
, Old
, BBMap
, LTS
, L
))
124 // A scop-constant value defined by a global or a function parameter.
125 if (isa
<GlobalValue
>(Old
) || isa
<Argument
>(Old
))
128 // A scop-constant value defined by an instruction executed outside the scop.
129 if (const Instruction
*Inst
= dyn_cast
<Instruction
>(Old
))
130 if (!Stmt
.getParent()->contains(Inst
->getParent()))
133 // The scalar dependence is neither available nor SCEVCodegenable.
134 llvm_unreachable("Unexpected scalar dependence in region!");
138 void BlockGenerator::copyInstScalar(ScopStmt
&Stmt
, Instruction
*Inst
,
139 ValueMapT
&BBMap
, LoopToScevMapT
<S
) {
140 // We do not generate debug intrinsics as we did not investigate how to
141 // copy them correctly. At the current state, they just crash the code
142 // generation as the meta-data operands are not correctly copied.
143 if (isa
<DbgInfoIntrinsic
>(Inst
))
146 Instruction
*NewInst
= Inst
->clone();
148 // Replace old operands with the new ones.
149 for (Value
*OldOperand
: Inst
->operands()) {
151 getNewValue(Stmt
, OldOperand
, BBMap
, LTS
, getLoopForStmt(Stmt
));
154 assert(!isa
<StoreInst
>(NewInst
) &&
155 "Store instructions are always needed!");
160 NewInst
->replaceUsesOfWith(OldOperand
, NewOperand
);
163 Builder
.Insert(NewInst
);
164 BBMap
[Inst
] = NewInst
;
166 if (!NewInst
->getType()->isVoidTy())
167 NewInst
->setName("p_" + Inst
->getName());
171 BlockGenerator::generateLocationAccessed(ScopStmt
&Stmt
, MemAccInst Inst
,
172 ValueMapT
&BBMap
, LoopToScevMapT
<S
,
173 isl_id_to_ast_expr
*NewAccesses
) {
174 const MemoryAccess
&MA
= Stmt
.getArrayAccessFor(Inst
);
176 isl_ast_expr
*AccessExpr
= isl_id_to_ast_expr_get(NewAccesses
, MA
.getId());
179 AccessExpr
= isl_ast_expr_address_of(AccessExpr
);
180 auto Address
= ExprBuilder
->create(AccessExpr
);
182 // Cast the address of this memory access to a pointer type that has the
183 // same element type as the original access, but uses the address space of
184 // the newly generated pointer.
185 auto OldPtrTy
= MA
.getAccessValue()->getType()->getPointerTo();
186 auto NewPtrTy
= Address
->getType();
187 OldPtrTy
= PointerType::get(OldPtrTy
->getElementType(),
188 NewPtrTy
->getPointerAddressSpace());
190 if (OldPtrTy
!= NewPtrTy
)
191 Address
= Builder
.CreateBitOrPointerCast(Address
, OldPtrTy
);
195 return getNewValue(Stmt
, Inst
.getPointerOperand(), BBMap
, LTS
,
196 getLoopForStmt(Stmt
));
199 Loop
*BlockGenerator::getLoopForStmt(const ScopStmt
&Stmt
) const {
200 auto *StmtBB
= Stmt
.getEntryBlock();
201 return LI
.getLoopFor(StmtBB
);
204 Value
*BlockGenerator::generateScalarLoad(ScopStmt
&Stmt
, LoadInst
*Load
,
205 ValueMapT
&BBMap
, LoopToScevMapT
<S
,
206 isl_id_to_ast_expr
*NewAccesses
) {
207 if (Value
*PreloadLoad
= GlobalMap
.lookup(Load
))
211 generateLocationAccessed(Stmt
, Load
, BBMap
, LTS
, NewAccesses
);
212 Value
*ScalarLoad
= Builder
.CreateAlignedLoad(
213 NewPointer
, Load
->getAlignment(), Load
->getName() + "_p_scalar_");
216 RuntimeDebugBuilder::createCPUPrinter(Builder
, "Load from ", NewPointer
,
217 ": ", ScalarLoad
, "\n");
222 void BlockGenerator::generateScalarStore(ScopStmt
&Stmt
, StoreInst
*Store
,
223 ValueMapT
&BBMap
, LoopToScevMapT
<S
,
224 isl_id_to_ast_expr
*NewAccesses
) {
226 generateLocationAccessed(Stmt
, Store
, BBMap
, LTS
, NewAccesses
);
227 Value
*ValueOperand
= getNewValue(Stmt
, Store
->getValueOperand(), BBMap
, LTS
,
228 getLoopForStmt(Stmt
));
231 RuntimeDebugBuilder::createCPUPrinter(Builder
, "Store to ", NewPointer
,
232 ": ", ValueOperand
, "\n");
234 Builder
.CreateAlignedStore(ValueOperand
, NewPointer
, Store
->getAlignment());
237 bool BlockGenerator::canSyntheziseInStmt(ScopStmt
&Stmt
, Instruction
*Inst
) {
238 Loop
*L
= getLoopForStmt(Stmt
);
239 return (Stmt
.isBlockStmt() || !Stmt
.getRegion()->contains(L
)) &&
240 canSynthesize(Inst
, *Stmt
.getParent(), &LI
, &SE
, L
);
243 void BlockGenerator::copyInstruction(ScopStmt
&Stmt
, Instruction
*Inst
,
244 ValueMapT
&BBMap
, LoopToScevMapT
<S
,
245 isl_id_to_ast_expr
*NewAccesses
) {
246 // Terminator instructions control the control flow. They are explicitly
247 // expressed in the clast and do not need to be copied.
248 if (Inst
->isTerminator())
251 // Synthesizable statements will be generated on-demand.
252 if (canSyntheziseInStmt(Stmt
, Inst
))
255 if (auto *Load
= dyn_cast
<LoadInst
>(Inst
)) {
256 Value
*NewLoad
= generateScalarLoad(Stmt
, Load
, BBMap
, LTS
, NewAccesses
);
257 // Compute NewLoad before its insertion in BBMap to make the insertion
259 BBMap
[Load
] = NewLoad
;
263 if (auto *Store
= dyn_cast
<StoreInst
>(Inst
)) {
264 generateScalarStore(Stmt
, Store
, BBMap
, LTS
, NewAccesses
);
268 if (auto *PHI
= dyn_cast
<PHINode
>(Inst
)) {
269 copyPHIInstruction(Stmt
, PHI
, BBMap
, LTS
);
273 // Skip some special intrinsics for which we do not adjust the semantics to
274 // the new schedule. All others are handled like every other instruction.
275 if (isIgnoredIntrinsic(Inst
))
278 copyInstScalar(Stmt
, Inst
, BBMap
, LTS
);
281 void BlockGenerator::removeDeadInstructions(BasicBlock
*BB
, ValueMapT
&BBMap
) {
282 for (auto I
= BB
->rbegin(), E
= BB
->rend(); I
!= E
; I
++) {
283 Instruction
*Inst
= &*I
;
284 Value
*NewVal
= BBMap
[Inst
];
289 Instruction
*NewInst
= dyn_cast
<Instruction
>(NewVal
);
294 if (!isInstructionTriviallyDead(NewInst
))
298 NewInst
->eraseFromParent();
302 void BlockGenerator::copyStmt(ScopStmt
&Stmt
, LoopToScevMapT
<S
,
303 isl_id_to_ast_expr
*NewAccesses
) {
304 assert(Stmt
.isBlockStmt() &&
305 "Only block statements can be copied by the block generator");
309 BasicBlock
*BB
= Stmt
.getBasicBlock();
310 copyBB(Stmt
, BB
, BBMap
, LTS
, NewAccesses
);
311 removeDeadInstructions(BB
, BBMap
);
314 BasicBlock
*BlockGenerator::splitBB(BasicBlock
*BB
) {
315 BasicBlock
*CopyBB
= SplitBlock(Builder
.GetInsertBlock(),
316 &*Builder
.GetInsertPoint(), &DT
, &LI
);
317 CopyBB
->setName("polly.stmt." + BB
->getName());
321 BasicBlock
*BlockGenerator::copyBB(ScopStmt
&Stmt
, BasicBlock
*BB
,
322 ValueMapT
&BBMap
, LoopToScevMapT
<S
,
323 isl_id_to_ast_expr
*NewAccesses
) {
324 BasicBlock
*CopyBB
= splitBB(BB
);
325 Builder
.SetInsertPoint(&CopyBB
->front());
326 generateScalarLoads(Stmt
, BBMap
);
328 copyBB(Stmt
, BB
, CopyBB
, BBMap
, LTS
, NewAccesses
);
330 // After a basic block was copied store all scalars that escape this block in
332 generateScalarStores(Stmt
, LTS
, BBMap
);
336 void BlockGenerator::copyBB(ScopStmt
&Stmt
, BasicBlock
*BB
, BasicBlock
*CopyBB
,
337 ValueMapT
&BBMap
, LoopToScevMapT
<S
,
338 isl_id_to_ast_expr
*NewAccesses
) {
339 EntryBB
= &CopyBB
->getParent()->getEntryBlock();
341 for (Instruction
&Inst
: *BB
)
342 copyInstruction(Stmt
, &Inst
, BBMap
, LTS
, NewAccesses
);
345 Value
*BlockGenerator::getOrCreateAlloca(Value
*ScalarBase
,
346 ScalarAllocaMapTy
&Map
,
347 const char *NameExt
) {
348 // If no alloca was found create one and insert it in the entry block.
349 if (!Map
.count(ScalarBase
)) {
350 auto *Ty
= ScalarBase
->getType();
351 auto NewAddr
= new AllocaInst(Ty
, ScalarBase
->getName() + NameExt
);
352 EntryBB
= &Builder
.GetInsertBlock()->getParent()->getEntryBlock();
353 NewAddr
->insertBefore(&*EntryBB
->getFirstInsertionPt());
354 Map
[ScalarBase
] = NewAddr
;
357 auto Addr
= Map
[ScalarBase
];
359 if (auto NewAddr
= GlobalMap
.lookup(Addr
))
365 Value
*BlockGenerator::getOrCreateAlloca(const MemoryAccess
&Access
) {
366 if (Access
.isPHIKind())
367 return getOrCreatePHIAlloca(Access
.getBaseAddr());
369 return getOrCreateScalarAlloca(Access
.getBaseAddr());
372 Value
*BlockGenerator::getOrCreateAlloca(const ScopArrayInfo
*Array
) {
373 if (Array
->isPHIKind())
374 return getOrCreatePHIAlloca(Array
->getBasePtr());
376 return getOrCreateScalarAlloca(Array
->getBasePtr());
379 Value
*BlockGenerator::getOrCreateScalarAlloca(Value
*ScalarBase
) {
380 return getOrCreateAlloca(ScalarBase
, ScalarMap
, ".s2a");
383 Value
*BlockGenerator::getOrCreatePHIAlloca(Value
*ScalarBase
) {
384 return getOrCreateAlloca(ScalarBase
, PHIOpMap
, ".phiops");
387 void BlockGenerator::handleOutsideUsers(const Scop
&S
, Instruction
*Inst
) {
388 // If there are escape users we get the alloca for this instruction and put it
389 // in the EscapeMap for later finalization. Lastly, if the instruction was
390 // copied multiple times we already did this and can exit.
391 if (EscapeMap
.count(Inst
))
394 EscapeUserVectorTy EscapeUsers
;
395 for (User
*U
: Inst
->users()) {
397 // Non-instruction user will never escape.
398 Instruction
*UI
= dyn_cast
<Instruction
>(U
);
405 EscapeUsers
.push_back(UI
);
408 // Exit if no escape uses were found.
409 if (EscapeUsers
.empty())
412 // Get or create an escape alloca for this instruction.
413 auto *ScalarAddr
= getOrCreateScalarAlloca(Inst
);
415 // Remember that this instruction has escape uses and the escape alloca.
416 EscapeMap
[Inst
] = std::make_pair(ScalarAddr
, std::move(EscapeUsers
));
419 void BlockGenerator::generateScalarLoads(ScopStmt
&Stmt
, ValueMapT
&BBMap
) {
420 for (MemoryAccess
*MA
: Stmt
) {
421 if (MA
->isArrayKind() || MA
->isWrite())
424 auto *Address
= getOrCreateAlloca(*MA
);
425 assert((!isa
<Instruction
>(Address
) ||
426 DT
.dominates(cast
<Instruction
>(Address
)->getParent(),
427 Builder
.GetInsertBlock())) &&
428 "Domination violation");
429 BBMap
[MA
->getBaseAddr()] =
430 Builder
.CreateLoad(Address
, Address
->getName() + ".reload");
434 void BlockGenerator::generateScalarStores(ScopStmt
&Stmt
, LoopToScevMapT
<S
,
436 Loop
*L
= LI
.getLoopFor(Stmt
.getBasicBlock());
438 assert(Stmt
.isBlockStmt() && "Region statements need to use the "
439 "generateScalarStores() function in the "
442 for (MemoryAccess
*MA
: Stmt
) {
443 if (MA
->isArrayKind() || MA
->isRead())
446 Value
*Val
= MA
->getAccessValue();
447 if (MA
->isAnyPHIKind()) {
448 assert(MA
->getIncoming().size() >= 1 &&
449 "Block statements have exactly one exiting block, or multiple but "
450 "with same incoming block and value");
451 assert(std::all_of(MA
->getIncoming().begin(), MA
->getIncoming().end(),
452 [&](std::pair
<BasicBlock
*, Value
*> p
) -> bool {
453 return p
.first
== Stmt
.getBasicBlock();
455 "Incoming block must be statement's block");
456 Val
= MA
->getIncoming()[0].second
;
458 auto *Address
= getOrCreateAlloca(*MA
);
460 Val
= getNewValue(Stmt
, Val
, BBMap
, LTS
, L
);
461 assert((!isa
<Instruction
>(Val
) ||
462 DT
.dominates(cast
<Instruction
>(Val
)->getParent(),
463 Builder
.GetInsertBlock())) &&
464 "Domination violation");
465 assert((!isa
<Instruction
>(Address
) ||
466 DT
.dominates(cast
<Instruction
>(Address
)->getParent(),
467 Builder
.GetInsertBlock())) &&
468 "Domination violation");
469 Builder
.CreateStore(Val
, Address
);
473 void BlockGenerator::createScalarInitialization(Scop
&S
) {
474 BasicBlock
*ExitBB
= S
.getExit();
476 // The split block __just before__ the region and optimized region.
477 BasicBlock
*SplitBB
= S
.getEnteringBlock();
478 BranchInst
*SplitBBTerm
= cast
<BranchInst
>(SplitBB
->getTerminator());
479 assert(SplitBBTerm
->getNumSuccessors() == 2 && "Bad region entering block!");
481 // Get the start block of the __optimized__ region.
482 BasicBlock
*StartBB
= SplitBBTerm
->getSuccessor(0);
483 if (StartBB
== S
.getEntry())
484 StartBB
= SplitBBTerm
->getSuccessor(1);
486 Builder
.SetInsertPoint(StartBB
->getTerminator());
488 for (auto &Array
: S
.arrays()) {
489 if (Array
->getNumberOfDimensions() != 0)
491 if (Array
->isPHIKind()) {
492 // For PHI nodes, the only values we need to store are the ones that
493 // reach the PHI node from outside the region. In general there should
494 // only be one such incoming edge and this edge should enter through
496 auto PHI
= cast
<PHINode
>(Array
->getBasePtr());
498 for (auto BI
= PHI
->block_begin(), BE
= PHI
->block_end(); BI
!= BE
; BI
++)
499 if (!S
.contains(*BI
) && *BI
!= SplitBB
)
500 llvm_unreachable("Incoming edges from outside the scop should always "
501 "come from SplitBB");
503 int Idx
= PHI
->getBasicBlockIndex(SplitBB
);
507 Value
*ScalarValue
= PHI
->getIncomingValue(Idx
);
509 Builder
.CreateStore(ScalarValue
, getOrCreatePHIAlloca(PHI
));
513 auto *Inst
= dyn_cast
<Instruction
>(Array
->getBasePtr());
515 if (Inst
&& S
.contains(Inst
))
518 // PHI nodes that are not marked as such in their SAI object are either exit
519 // PHI nodes we model as common scalars but without initialization, or
520 // incoming phi nodes that need to be initialized. Check if the first is the
521 // case for Inst and do not create and initialize memory if so.
522 if (auto *PHI
= dyn_cast_or_null
<PHINode
>(Inst
))
523 if (!S
.hasSingleExitEdge() && PHI
->getBasicBlockIndex(ExitBB
) >= 0)
526 Builder
.CreateStore(Array
->getBasePtr(),
527 getOrCreateScalarAlloca(Array
->getBasePtr()));
531 void BlockGenerator::createScalarFinalization(Scop
&S
) {
532 // The exit block of the __unoptimized__ region.
533 BasicBlock
*ExitBB
= S
.getExitingBlock();
534 // The merge block __just after__ the region and the optimized region.
535 BasicBlock
*MergeBB
= S
.getExit();
537 // The exit block of the __optimized__ region.
538 BasicBlock
*OptExitBB
= *(pred_begin(MergeBB
));
539 if (OptExitBB
== ExitBB
)
540 OptExitBB
= *(++pred_begin(MergeBB
));
542 Builder
.SetInsertPoint(OptExitBB
->getTerminator());
543 for (const auto &EscapeMapping
: EscapeMap
) {
544 // Extract the escaping instruction and the escaping users as well as the
545 // alloca the instruction was demoted to.
546 Instruction
*EscapeInst
= EscapeMapping
.getFirst();
547 const auto &EscapeMappingValue
= EscapeMapping
.getSecond();
548 const EscapeUserVectorTy
&EscapeUsers
= EscapeMappingValue
.second
;
549 Value
*ScalarAddr
= EscapeMappingValue
.first
;
551 // Reload the demoted instruction in the optimized version of the SCoP.
552 Value
*EscapeInstReload
=
553 Builder
.CreateLoad(ScalarAddr
, EscapeInst
->getName() + ".final_reload");
555 Builder
.CreateBitOrPointerCast(EscapeInstReload
, EscapeInst
->getType());
557 // Create the merge PHI that merges the optimized and unoptimized version.
558 PHINode
*MergePHI
= PHINode::Create(EscapeInst
->getType(), 2,
559 EscapeInst
->getName() + ".merge");
560 MergePHI
->insertBefore(&*MergeBB
->getFirstInsertionPt());
562 // Add the respective values to the merge PHI.
563 MergePHI
->addIncoming(EscapeInstReload
, OptExitBB
);
564 MergePHI
->addIncoming(EscapeInst
, ExitBB
);
566 // The information of scalar evolution about the escaping instruction needs
567 // to be revoked so the new merged instruction will be used.
568 if (SE
.isSCEVable(EscapeInst
->getType()))
569 SE
.forgetValue(EscapeInst
);
571 // Replace all uses of the demoted instruction with the merge PHI.
572 for (Instruction
*EUser
: EscapeUsers
)
573 EUser
->replaceUsesOfWith(EscapeInst
, MergePHI
);
577 void BlockGenerator::findOutsideUsers(Scop
&S
) {
578 for (auto &Array
: S
.arrays()) {
580 if (Array
->getNumberOfDimensions() != 0)
583 if (Array
->isPHIKind())
586 auto *Inst
= dyn_cast
<Instruction
>(Array
->getBasePtr());
591 // Scop invariant hoisting moves some of the base pointers out of the scop.
592 // We can ignore these, as the invariant load hoisting already registers the
593 // relevant outside users.
594 if (!S
.contains(Inst
))
597 handleOutsideUsers(S
, Inst
);
601 void BlockGenerator::createExitPHINodeMerges(Scop
&S
) {
602 if (S
.hasSingleExitEdge())
605 auto *ExitBB
= S
.getExitingBlock();
606 auto *MergeBB
= S
.getExit();
607 auto *AfterMergeBB
= MergeBB
->getSingleSuccessor();
608 BasicBlock
*OptExitBB
= *(pred_begin(MergeBB
));
609 if (OptExitBB
== ExitBB
)
610 OptExitBB
= *(++pred_begin(MergeBB
));
612 Builder
.SetInsertPoint(OptExitBB
->getTerminator());
614 for (auto &SAI
: S
.arrays()) {
615 auto *Val
= SAI
->getBasePtr();
617 // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
618 // the original PHI's value or the reloaded incoming values from the
619 // generated code. An llvm::Value is merged between the original code's
620 // value or the generated one.
621 if (!SAI
->isValueKind() && !SAI
->isExitPHIKind())
624 PHINode
*PHI
= dyn_cast
<PHINode
>(Val
);
628 if (PHI
->getParent() != AfterMergeBB
)
631 std::string Name
= PHI
->getName();
632 Value
*ScalarAddr
= getOrCreateScalarAlloca(PHI
);
633 Value
*Reload
= Builder
.CreateLoad(ScalarAddr
, Name
+ ".ph.final_reload");
634 Reload
= Builder
.CreateBitOrPointerCast(Reload
, PHI
->getType());
635 Value
*OriginalValue
= PHI
->getIncomingValueForBlock(MergeBB
);
636 assert((!isa
<Instruction
>(OriginalValue
) ||
637 cast
<Instruction
>(OriginalValue
)->getParent() != MergeBB
) &&
638 "Original value must no be one we just generated.");
639 auto *MergePHI
= PHINode::Create(PHI
->getType(), 2, Name
+ ".ph.merge");
640 MergePHI
->insertBefore(&*MergeBB
->getFirstInsertionPt());
641 MergePHI
->addIncoming(Reload
, OptExitBB
);
642 MergePHI
->addIncoming(OriginalValue
, ExitBB
);
643 int Idx
= PHI
->getBasicBlockIndex(MergeBB
);
644 PHI
->setIncomingValue(Idx
, MergePHI
);
648 void BlockGenerator::finalizeSCoP(Scop
&S
) {
650 createScalarInitialization(S
);
651 createExitPHINodeMerges(S
);
652 createScalarFinalization(S
);
655 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator
&BlockGen
,
656 std::vector
<LoopToScevMapT
> &VLTS
,
658 : BlockGenerator(BlockGen
), VLTS(VLTS
), Schedule(Schedule
) {
659 assert(Schedule
&& "No statement domain provided");
662 Value
*VectorBlockGenerator::getVectorValue(ScopStmt
&Stmt
, Value
*Old
,
663 ValueMapT
&VectorMap
,
664 VectorValueMapT
&ScalarMaps
,
666 if (Value
*NewValue
= VectorMap
.lookup(Old
))
669 int Width
= getVectorWidth();
671 Value
*Vector
= UndefValue::get(VectorType::get(Old
->getType(), Width
));
673 for (int Lane
= 0; Lane
< Width
; Lane
++)
674 Vector
= Builder
.CreateInsertElement(
675 Vector
, getNewValue(Stmt
, Old
, ScalarMaps
[Lane
], VLTS
[Lane
], L
),
676 Builder
.getInt32(Lane
));
678 VectorMap
[Old
] = Vector
;
683 Type
*VectorBlockGenerator::getVectorPtrTy(const Value
*Val
, int Width
) {
684 PointerType
*PointerTy
= dyn_cast
<PointerType
>(Val
->getType());
685 assert(PointerTy
&& "PointerType expected");
687 Type
*ScalarType
= PointerTy
->getElementType();
688 VectorType
*VectorType
= VectorType::get(ScalarType
, Width
);
690 return PointerType::getUnqual(VectorType
);
693 Value
*VectorBlockGenerator::generateStrideOneLoad(
694 ScopStmt
&Stmt
, LoadInst
*Load
, VectorValueMapT
&ScalarMaps
,
695 __isl_keep isl_id_to_ast_expr
*NewAccesses
, bool NegativeStride
= false) {
696 unsigned VectorWidth
= getVectorWidth();
697 auto *Pointer
= Load
->getPointerOperand();
698 Type
*VectorPtrType
= getVectorPtrTy(Pointer
, VectorWidth
);
699 unsigned Offset
= NegativeStride
? VectorWidth
- 1 : 0;
701 Value
*NewPointer
= generateLocationAccessed(Stmt
, Load
, ScalarMaps
[Offset
],
702 VLTS
[Offset
], NewAccesses
);
704 Builder
.CreateBitCast(NewPointer
, VectorPtrType
, "vector_ptr");
706 Builder
.CreateLoad(VectorPtr
, Load
->getName() + "_p_vec_full");
708 VecLoad
->setAlignment(8);
710 if (NegativeStride
) {
711 SmallVector
<Constant
*, 16> Indices
;
712 for (int i
= VectorWidth
- 1; i
>= 0; i
--)
713 Indices
.push_back(ConstantInt::get(Builder
.getInt32Ty(), i
));
714 Constant
*SV
= llvm::ConstantVector::get(Indices
);
715 Value
*RevVecLoad
= Builder
.CreateShuffleVector(
716 VecLoad
, VecLoad
, SV
, Load
->getName() + "_reverse");
723 Value
*VectorBlockGenerator::generateStrideZeroLoad(
724 ScopStmt
&Stmt
, LoadInst
*Load
, ValueMapT
&BBMap
,
725 __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
726 auto *Pointer
= Load
->getPointerOperand();
727 Type
*VectorPtrType
= getVectorPtrTy(Pointer
, 1);
729 generateLocationAccessed(Stmt
, Load
, BBMap
, VLTS
[0], NewAccesses
);
730 Value
*VectorPtr
= Builder
.CreateBitCast(NewPointer
, VectorPtrType
,
731 Load
->getName() + "_p_vec_p");
732 LoadInst
*ScalarLoad
=
733 Builder
.CreateLoad(VectorPtr
, Load
->getName() + "_p_splat_one");
736 ScalarLoad
->setAlignment(8);
738 Constant
*SplatVector
= Constant::getNullValue(
739 VectorType::get(Builder
.getInt32Ty(), getVectorWidth()));
741 Value
*VectorLoad
= Builder
.CreateShuffleVector(
742 ScalarLoad
, ScalarLoad
, SplatVector
, Load
->getName() + "_p_splat");
746 Value
*VectorBlockGenerator::generateUnknownStrideLoad(
747 ScopStmt
&Stmt
, LoadInst
*Load
, VectorValueMapT
&ScalarMaps
,
748 __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
749 int VectorWidth
= getVectorWidth();
750 auto *Pointer
= Load
->getPointerOperand();
751 VectorType
*VectorType
= VectorType::get(
752 dyn_cast
<PointerType
>(Pointer
->getType())->getElementType(), VectorWidth
);
754 Value
*Vector
= UndefValue::get(VectorType
);
756 for (int i
= 0; i
< VectorWidth
; i
++) {
757 Value
*NewPointer
= generateLocationAccessed(Stmt
, Load
, ScalarMaps
[i
],
758 VLTS
[i
], NewAccesses
);
760 Builder
.CreateLoad(NewPointer
, Load
->getName() + "_p_scalar_");
761 Vector
= Builder
.CreateInsertElement(
762 Vector
, ScalarLoad
, Builder
.getInt32(i
), Load
->getName() + "_p_vec_");
768 void VectorBlockGenerator::generateLoad(
769 ScopStmt
&Stmt
, LoadInst
*Load
, ValueMapT
&VectorMap
,
770 VectorValueMapT
&ScalarMaps
, __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
771 if (Value
*PreloadLoad
= GlobalMap
.lookup(Load
)) {
772 VectorMap
[Load
] = Builder
.CreateVectorSplat(getVectorWidth(), PreloadLoad
,
773 Load
->getName() + "_p");
777 if (!VectorType::isValidElementType(Load
->getType())) {
778 for (int i
= 0; i
< getVectorWidth(); i
++)
779 ScalarMaps
[i
][Load
] =
780 generateScalarLoad(Stmt
, Load
, ScalarMaps
[i
], VLTS
[i
], NewAccesses
);
784 const MemoryAccess
&Access
= Stmt
.getArrayAccessFor(Load
);
786 // Make sure we have scalar values available to access the pointer to
787 // the data location.
788 extractScalarValues(Load
, VectorMap
, ScalarMaps
);
791 if (Access
.isStrideZero(isl_map_copy(Schedule
)))
792 NewLoad
= generateStrideZeroLoad(Stmt
, Load
, ScalarMaps
[0], NewAccesses
);
793 else if (Access
.isStrideOne(isl_map_copy(Schedule
)))
794 NewLoad
= generateStrideOneLoad(Stmt
, Load
, ScalarMaps
, NewAccesses
);
795 else if (Access
.isStrideX(isl_map_copy(Schedule
), -1))
796 NewLoad
= generateStrideOneLoad(Stmt
, Load
, ScalarMaps
, NewAccesses
, true);
798 NewLoad
= generateUnknownStrideLoad(Stmt
, Load
, ScalarMaps
, NewAccesses
);
800 VectorMap
[Load
] = NewLoad
;
803 void VectorBlockGenerator::copyUnaryInst(ScopStmt
&Stmt
, UnaryInstruction
*Inst
,
804 ValueMapT
&VectorMap
,
805 VectorValueMapT
&ScalarMaps
) {
806 int VectorWidth
= getVectorWidth();
807 Value
*NewOperand
= getVectorValue(Stmt
, Inst
->getOperand(0), VectorMap
,
808 ScalarMaps
, getLoopForStmt(Stmt
));
810 assert(isa
<CastInst
>(Inst
) && "Can not generate vector code for instruction");
812 const CastInst
*Cast
= dyn_cast
<CastInst
>(Inst
);
813 VectorType
*DestType
= VectorType::get(Inst
->getType(), VectorWidth
);
814 VectorMap
[Inst
] = Builder
.CreateCast(Cast
->getOpcode(), NewOperand
, DestType
);
817 void VectorBlockGenerator::copyBinaryInst(ScopStmt
&Stmt
, BinaryOperator
*Inst
,
818 ValueMapT
&VectorMap
,
819 VectorValueMapT
&ScalarMaps
) {
820 Loop
*L
= getLoopForStmt(Stmt
);
821 Value
*OpZero
= Inst
->getOperand(0);
822 Value
*OpOne
= Inst
->getOperand(1);
824 Value
*NewOpZero
, *NewOpOne
;
825 NewOpZero
= getVectorValue(Stmt
, OpZero
, VectorMap
, ScalarMaps
, L
);
826 NewOpOne
= getVectorValue(Stmt
, OpOne
, VectorMap
, ScalarMaps
, L
);
828 Value
*NewInst
= Builder
.CreateBinOp(Inst
->getOpcode(), NewOpZero
, NewOpOne
,
829 Inst
->getName() + "p_vec");
830 VectorMap
[Inst
] = NewInst
;
833 void VectorBlockGenerator::copyStore(
834 ScopStmt
&Stmt
, StoreInst
*Store
, ValueMapT
&VectorMap
,
835 VectorValueMapT
&ScalarMaps
, __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
836 const MemoryAccess
&Access
= Stmt
.getArrayAccessFor(Store
);
838 auto *Pointer
= Store
->getPointerOperand();
839 Value
*Vector
= getVectorValue(Stmt
, Store
->getValueOperand(), VectorMap
,
840 ScalarMaps
, getLoopForStmt(Stmt
));
842 // Make sure we have scalar values available to access the pointer to
843 // the data location.
844 extractScalarValues(Store
, VectorMap
, ScalarMaps
);
846 if (Access
.isStrideOne(isl_map_copy(Schedule
))) {
847 Type
*VectorPtrType
= getVectorPtrTy(Pointer
, getVectorWidth());
848 Value
*NewPointer
= generateLocationAccessed(Stmt
, Store
, ScalarMaps
[0],
849 VLTS
[0], NewAccesses
);
852 Builder
.CreateBitCast(NewPointer
, VectorPtrType
, "vector_ptr");
853 StoreInst
*Store
= Builder
.CreateStore(Vector
, VectorPtr
);
856 Store
->setAlignment(8);
858 for (unsigned i
= 0; i
< ScalarMaps
.size(); i
++) {
859 Value
*Scalar
= Builder
.CreateExtractElement(Vector
, Builder
.getInt32(i
));
860 Value
*NewPointer
= generateLocationAccessed(Stmt
, Store
, ScalarMaps
[i
],
861 VLTS
[i
], NewAccesses
);
862 Builder
.CreateStore(Scalar
, NewPointer
);
867 bool VectorBlockGenerator::hasVectorOperands(const Instruction
*Inst
,
868 ValueMapT
&VectorMap
) {
869 for (Value
*Operand
: Inst
->operands())
870 if (VectorMap
.count(Operand
))
875 bool VectorBlockGenerator::extractScalarValues(const Instruction
*Inst
,
876 ValueMapT
&VectorMap
,
877 VectorValueMapT
&ScalarMaps
) {
878 bool HasVectorOperand
= false;
879 int VectorWidth
= getVectorWidth();
881 for (Value
*Operand
: Inst
->operands()) {
882 ValueMapT::iterator VecOp
= VectorMap
.find(Operand
);
884 if (VecOp
== VectorMap
.end())
887 HasVectorOperand
= true;
888 Value
*NewVector
= VecOp
->second
;
890 for (int i
= 0; i
< VectorWidth
; ++i
) {
891 ValueMapT
&SM
= ScalarMaps
[i
];
893 // If there is one scalar extracted, all scalar elements should have
894 // already been extracted by the code here. So no need to check for the
895 // existence of all of them.
896 if (SM
.count(Operand
))
900 Builder
.CreateExtractElement(NewVector
, Builder
.getInt32(i
));
904 return HasVectorOperand
;
907 void VectorBlockGenerator::copyInstScalarized(
908 ScopStmt
&Stmt
, Instruction
*Inst
, ValueMapT
&VectorMap
,
909 VectorValueMapT
&ScalarMaps
, __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
910 bool HasVectorOperand
;
911 int VectorWidth
= getVectorWidth();
913 HasVectorOperand
= extractScalarValues(Inst
, VectorMap
, ScalarMaps
);
915 for (int VectorLane
= 0; VectorLane
< getVectorWidth(); VectorLane
++)
916 BlockGenerator::copyInstruction(Stmt
, Inst
, ScalarMaps
[VectorLane
],
917 VLTS
[VectorLane
], NewAccesses
);
919 if (!VectorType::isValidElementType(Inst
->getType()) || !HasVectorOperand
)
922 // Make the result available as vector value.
923 VectorType
*VectorType
= VectorType::get(Inst
->getType(), VectorWidth
);
924 Value
*Vector
= UndefValue::get(VectorType
);
926 for (int i
= 0; i
< VectorWidth
; i
++)
927 Vector
= Builder
.CreateInsertElement(Vector
, ScalarMaps
[i
][Inst
],
928 Builder
.getInt32(i
));
930 VectorMap
[Inst
] = Vector
;
933 int VectorBlockGenerator::getVectorWidth() { return VLTS
.size(); }
935 void VectorBlockGenerator::copyInstruction(
936 ScopStmt
&Stmt
, Instruction
*Inst
, ValueMapT
&VectorMap
,
937 VectorValueMapT
&ScalarMaps
, __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
938 // Terminator instructions control the control flow. They are explicitly
939 // expressed in the clast and do not need to be copied.
940 if (Inst
->isTerminator())
943 if (canSyntheziseInStmt(Stmt
, Inst
))
946 if (auto *Load
= dyn_cast
<LoadInst
>(Inst
)) {
947 generateLoad(Stmt
, Load
, VectorMap
, ScalarMaps
, NewAccesses
);
951 if (hasVectorOperands(Inst
, VectorMap
)) {
952 if (auto *Store
= dyn_cast
<StoreInst
>(Inst
)) {
953 copyStore(Stmt
, Store
, VectorMap
, ScalarMaps
, NewAccesses
);
957 if (auto *Unary
= dyn_cast
<UnaryInstruction
>(Inst
)) {
958 copyUnaryInst(Stmt
, Unary
, VectorMap
, ScalarMaps
);
962 if (auto *Binary
= dyn_cast
<BinaryOperator
>(Inst
)) {
963 copyBinaryInst(Stmt
, Binary
, VectorMap
, ScalarMaps
);
967 // Falltrough: We generate scalar instructions, if we don't know how to
968 // generate vector code.
971 copyInstScalarized(Stmt
, Inst
, VectorMap
, ScalarMaps
, NewAccesses
);
974 void VectorBlockGenerator::generateScalarVectorLoads(
975 ScopStmt
&Stmt
, ValueMapT
&VectorBlockMap
) {
976 for (MemoryAccess
*MA
: Stmt
) {
977 if (MA
->isArrayKind() || MA
->isWrite())
980 auto *Address
= getOrCreateAlloca(*MA
);
981 Type
*VectorPtrType
= getVectorPtrTy(Address
, 1);
982 Value
*VectorPtr
= Builder
.CreateBitCast(Address
, VectorPtrType
,
983 Address
->getName() + "_p_vec_p");
984 auto *Val
= Builder
.CreateLoad(VectorPtr
, Address
->getName() + ".reload");
985 Constant
*SplatVector
= Constant::getNullValue(
986 VectorType::get(Builder
.getInt32Ty(), getVectorWidth()));
988 Value
*VectorVal
= Builder
.CreateShuffleVector(
989 Val
, Val
, SplatVector
, Address
->getName() + "_p_splat");
990 VectorBlockMap
[MA
->getBaseAddr()] = VectorVal
;
994 void VectorBlockGenerator::verifyNoScalarStores(ScopStmt
&Stmt
) {
995 for (MemoryAccess
*MA
: Stmt
) {
996 if (MA
->isArrayKind() || MA
->isRead())
999 llvm_unreachable("Scalar stores not expected in vector loop");
1003 void VectorBlockGenerator::copyStmt(
1004 ScopStmt
&Stmt
, __isl_keep isl_id_to_ast_expr
*NewAccesses
) {
1005 assert(Stmt
.isBlockStmt() && "TODO: Only block statements can be copied by "
1006 "the vector block generator");
1008 BasicBlock
*BB
= Stmt
.getBasicBlock();
1009 BasicBlock
*CopyBB
= SplitBlock(Builder
.GetInsertBlock(),
1010 &*Builder
.GetInsertPoint(), &DT
, &LI
);
1011 CopyBB
->setName("polly.stmt." + BB
->getName());
1012 Builder
.SetInsertPoint(&CopyBB
->front());
1014 // Create two maps that store the mapping from the original instructions of
1015 // the old basic block to their copies in the new basic block. Those maps
1016 // are basic block local.
1018 // As vector code generation is supported there is one map for scalar values
1019 // and one for vector values.
1021 // In case we just do scalar code generation, the vectorMap is not used and
1022 // the scalarMap has just one dimension, which contains the mapping.
1024 // In case vector code generation is done, an instruction may either appear
1025 // in the vector map once (as it is calculating >vectorwidth< values at a
1026 // time. Or (if the values are calculated using scalar operations), it
1027 // appears once in every dimension of the scalarMap.
1028 VectorValueMapT
ScalarBlockMap(getVectorWidth());
1029 ValueMapT VectorBlockMap
;
1031 generateScalarVectorLoads(Stmt
, VectorBlockMap
);
1033 for (Instruction
&Inst
: *BB
)
1034 copyInstruction(Stmt
, &Inst
, VectorBlockMap
, ScalarBlockMap
, NewAccesses
);
1036 verifyNoScalarStores(Stmt
);
1039 BasicBlock
*RegionGenerator::repairDominance(BasicBlock
*BB
,
1040 BasicBlock
*BBCopy
) {
1042 BasicBlock
*BBIDom
= DT
.getNode(BB
)->getIDom()->getBlock();
1043 BasicBlock
*BBCopyIDom
= BlockMap
.lookup(BBIDom
);
1046 DT
.changeImmediateDominator(BBCopy
, BBCopyIDom
);
1051 // This is to determine whether an llvm::Value (defined in @p BB) is usable when
1052 // leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1053 // does not work in cases where the exit block has edges from outside the
1054 // region. In that case the llvm::Value would never be usable in in the exit
1055 // block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1056 // for the subregion's exiting edges only. We need to determine whether an
1057 // llvm::Value is usable in there. We do this by checking whether it dominates
1058 // all exiting blocks individually.
1059 static bool isDominatingSubregionExit(const DominatorTree
&DT
, Region
*R
,
1061 for (auto ExitingBB
: predecessors(R
->getExit())) {
1062 // Check for non-subregion incoming edges.
1063 if (!R
->contains(ExitingBB
))
1066 if (!DT
.dominates(BB
, ExitingBB
))
1073 // Find the direct dominator of the subregion's exit block if the subregion was
1075 static BasicBlock
*findExitDominator(DominatorTree
&DT
, Region
*R
) {
1076 BasicBlock
*Common
= nullptr;
1077 for (auto ExitingBB
: predecessors(R
->getExit())) {
1078 // Check for non-subregion incoming edges.
1079 if (!R
->contains(ExitingBB
))
1082 // First exiting edge.
1088 Common
= DT
.findNearestCommonDominator(Common
, ExitingBB
);
1091 assert(Common
&& R
->contains(Common
));
1095 void RegionGenerator::copyStmt(ScopStmt
&Stmt
, LoopToScevMapT
<S
,
1096 isl_id_to_ast_expr
*IdToAstExp
) {
1097 assert(Stmt
.isRegionStmt() &&
1098 "Only region statements can be copied by the region generator");
1100 // Forget all old mappings.
1103 IncompletePHINodeMap
.clear();
1105 // Collection of all values related to this subregion.
1108 // The region represented by the statement.
1109 Region
*R
= Stmt
.getRegion();
1111 // Create a dedicated entry for the region where we can reload all demoted
1113 BasicBlock
*EntryBB
= R
->getEntry();
1114 BasicBlock
*EntryBBCopy
= SplitBlock(Builder
.GetInsertBlock(),
1115 &*Builder
.GetInsertPoint(), &DT
, &LI
);
1116 EntryBBCopy
->setName("polly.stmt." + EntryBB
->getName() + ".entry");
1117 Builder
.SetInsertPoint(&EntryBBCopy
->front());
1119 ValueMapT
&EntryBBMap
= RegionMaps
[EntryBBCopy
];
1120 generateScalarLoads(Stmt
, EntryBBMap
);
1122 for (auto PI
= pred_begin(EntryBB
), PE
= pred_end(EntryBB
); PI
!= PE
; ++PI
)
1123 if (!R
->contains(*PI
))
1124 BlockMap
[*PI
] = EntryBBCopy
;
1126 // Iterate over all blocks in the region in a breadth-first search.
1127 std::deque
<BasicBlock
*> Blocks
;
1128 SmallPtrSet
<BasicBlock
*, 8> SeenBlocks
;
1129 Blocks
.push_back(EntryBB
);
1130 SeenBlocks
.insert(EntryBB
);
1132 while (!Blocks
.empty()) {
1133 BasicBlock
*BB
= Blocks
.front();
1136 // First split the block and update dominance information.
1137 BasicBlock
*BBCopy
= splitBB(BB
);
1138 BasicBlock
*BBCopyIDom
= repairDominance(BB
, BBCopy
);
1140 // Get the mapping for this block and initialize it with either the scalar
1141 // loads from the generated entering block (which dominates all blocks of
1142 // this subregion) or the maps of the immediate dominator, if part of the
1143 // subregion. The latter necessarily includes the former.
1144 ValueMapT
*InitBBMap
;
1146 assert(RegionMaps
.count(BBCopyIDom
));
1147 InitBBMap
= &RegionMaps
[BBCopyIDom
];
1149 InitBBMap
= &EntryBBMap
;
1150 auto Inserted
= RegionMaps
.insert(std::make_pair(BBCopy
, *InitBBMap
));
1151 ValueMapT
&RegionMap
= Inserted
.first
->second
;
1153 // Copy the block with the BlockGenerator.
1154 Builder
.SetInsertPoint(&BBCopy
->front());
1155 copyBB(Stmt
, BB
, BBCopy
, RegionMap
, LTS
, IdToAstExp
);
1157 // In order to remap PHI nodes we store also basic block mappings.
1158 BlockMap
[BB
] = BBCopy
;
1160 // Add values to incomplete PHI nodes waiting for this block to be copied.
1161 for (const PHINodePairTy
&PHINodePair
: IncompletePHINodeMap
[BB
])
1162 addOperandToPHI(Stmt
, PHINodePair
.first
, PHINodePair
.second
, BB
, LTS
);
1163 IncompletePHINodeMap
[BB
].clear();
1165 // And continue with new successors inside the region.
1166 for (auto SI
= succ_begin(BB
), SE
= succ_end(BB
); SI
!= SE
; SI
++)
1167 if (R
->contains(*SI
) && SeenBlocks
.insert(*SI
).second
)
1168 Blocks
.push_back(*SI
);
1170 // Remember value in case it is visible after this subregion.
1171 if (isDominatingSubregionExit(DT
, R
, BB
))
1172 ValueMap
.insert(RegionMap
.begin(), RegionMap
.end());
1175 // Now create a new dedicated region exit block and add it to the region map.
1176 BasicBlock
*ExitBBCopy
= SplitBlock(Builder
.GetInsertBlock(),
1177 &*Builder
.GetInsertPoint(), &DT
, &LI
);
1178 ExitBBCopy
->setName("polly.stmt." + R
->getExit()->getName() + ".exit");
1179 BlockMap
[R
->getExit()] = ExitBBCopy
;
1181 BasicBlock
*ExitDomBBCopy
= BlockMap
.lookup(findExitDominator(DT
, R
));
1182 assert(ExitDomBBCopy
&& "Common exit dominator must be within region; at "
1183 "least the entry node must match");
1184 DT
.changeImmediateDominator(ExitBBCopy
, ExitDomBBCopy
);
1186 // As the block generator doesn't handle control flow we need to add the
1187 // region control flow by hand after all blocks have been copied.
1188 for (BasicBlock
*BB
: SeenBlocks
) {
1190 BasicBlock
*BBCopy
= BlockMap
[BB
];
1191 TerminatorInst
*TI
= BB
->getTerminator();
1192 if (isa
<UnreachableInst
>(TI
)) {
1193 while (!BBCopy
->empty())
1194 BBCopy
->begin()->eraseFromParent();
1195 new UnreachableInst(BBCopy
->getContext(), BBCopy
);
1199 Instruction
*BICopy
= BBCopy
->getTerminator();
1201 ValueMapT
&RegionMap
= RegionMaps
[BBCopy
];
1202 RegionMap
.insert(BlockMap
.begin(), BlockMap
.end());
1204 Builder
.SetInsertPoint(BICopy
);
1205 copyInstScalar(Stmt
, TI
, RegionMap
, LTS
);
1206 BICopy
->eraseFromParent();
1209 // Add counting PHI nodes to all loops in the region that can be used as
1210 // replacement for SCEVs refering to the old loop.
1211 for (BasicBlock
*BB
: SeenBlocks
) {
1212 Loop
*L
= LI
.getLoopFor(BB
);
1213 if (L
== nullptr || L
->getHeader() != BB
|| !R
->contains(L
))
1216 BasicBlock
*BBCopy
= BlockMap
[BB
];
1217 Value
*NullVal
= Builder
.getInt32(0);
1219 PHINode::Create(Builder
.getInt32Ty(), 2, "polly.subregion.iv");
1220 Instruction
*LoopPHIInc
= BinaryOperator::CreateAdd(
1221 LoopPHI
, Builder
.getInt32(1), "polly.subregion.iv.inc");
1222 LoopPHI
->insertBefore(&BBCopy
->front());
1223 LoopPHIInc
->insertBefore(BBCopy
->getTerminator());
1225 for (auto *PredBB
: make_range(pred_begin(BB
), pred_end(BB
))) {
1226 if (!R
->contains(PredBB
))
1228 if (L
->contains(PredBB
))
1229 LoopPHI
->addIncoming(LoopPHIInc
, BlockMap
[PredBB
]);
1231 LoopPHI
->addIncoming(NullVal
, BlockMap
[PredBB
]);
1234 for (auto *PredBBCopy
: make_range(pred_begin(BBCopy
), pred_end(BBCopy
)))
1235 if (LoopPHI
->getBasicBlockIndex(PredBBCopy
) < 0)
1236 LoopPHI
->addIncoming(NullVal
, PredBBCopy
);
1238 LTS
[L
] = SE
.getUnknown(LoopPHI
);
1241 // Continue generating code in the exit block.
1242 Builder
.SetInsertPoint(&*ExitBBCopy
->getFirstInsertionPt());
1244 // Write values visible to other statements.
1245 generateScalarStores(Stmt
, LTS
, ValueMap
);
1248 IncompletePHINodeMap
.clear();
1251 PHINode
*RegionGenerator::buildExitPHI(MemoryAccess
*MA
, LoopToScevMapT
<S
,
1252 ValueMapT
&BBMap
, Loop
*L
) {
1253 ScopStmt
*Stmt
= MA
->getStatement();
1254 Region
*SubR
= Stmt
->getRegion();
1255 auto Incoming
= MA
->getIncoming();
1257 PollyIRBuilder::InsertPointGuard
IPGuard(Builder
);
1258 PHINode
*OrigPHI
= cast
<PHINode
>(MA
->getAccessInstruction());
1259 BasicBlock
*NewSubregionExit
= Builder
.GetInsertBlock();
1261 // This can happen if the subregion is simplified after the ScopStmts
1262 // have been created; simplification happens as part of CodeGeneration.
1263 if (OrigPHI
->getParent() != SubR
->getExit()) {
1264 BasicBlock
*FormerExit
= SubR
->getExitingBlock();
1266 NewSubregionExit
= BlockMap
.lookup(FormerExit
);
1269 PHINode
*NewPHI
= PHINode::Create(OrigPHI
->getType(), Incoming
.size(),
1270 "polly." + OrigPHI
->getName(),
1271 NewSubregionExit
->getFirstNonPHI());
1273 // Add the incoming values to the PHI.
1274 for (auto &Pair
: Incoming
) {
1275 BasicBlock
*OrigIncomingBlock
= Pair
.first
;
1276 BasicBlock
*NewIncomingBlock
= BlockMap
.lookup(OrigIncomingBlock
);
1277 Builder
.SetInsertPoint(NewIncomingBlock
->getTerminator());
1278 assert(RegionMaps
.count(NewIncomingBlock
));
1279 ValueMapT
*LocalBBMap
= &RegionMaps
[NewIncomingBlock
];
1281 Value
*OrigIncomingValue
= Pair
.second
;
1282 Value
*NewIncomingValue
=
1283 getNewValue(*Stmt
, OrigIncomingValue
, *LocalBBMap
, LTS
, L
);
1284 NewPHI
->addIncoming(NewIncomingValue
, NewIncomingBlock
);
1290 Value
*RegionGenerator::getExitScalar(MemoryAccess
*MA
, LoopToScevMapT
<S
,
1292 ScopStmt
*Stmt
= MA
->getStatement();
1294 // TODO: Add some test cases that ensure this is really the right choice.
1295 Loop
*L
= LI
.getLoopFor(Stmt
->getRegion()->getExit());
1297 if (MA
->isAnyPHIKind()) {
1298 auto Incoming
= MA
->getIncoming();
1299 assert(!Incoming
.empty() &&
1300 "PHI WRITEs must have originate from at least one incoming block");
1302 // If there is only one incoming value, we do not need to create a PHI.
1303 if (Incoming
.size() == 1) {
1304 Value
*OldVal
= Incoming
[0].second
;
1305 return getNewValue(*Stmt
, OldVal
, BBMap
, LTS
, L
);
1308 return buildExitPHI(MA
, LTS
, BBMap
, L
);
1311 // MK_Value accesses leaving the subregion must dominate the exit block; just
1312 // pass the copied value
1313 Value
*OldVal
= MA
->getAccessValue();
1314 return getNewValue(*Stmt
, OldVal
, BBMap
, LTS
, L
);
1317 void RegionGenerator::generateScalarStores(ScopStmt
&Stmt
, LoopToScevMapT
<S
,
1319 assert(Stmt
.getRegion() &&
1320 "Block statements need to use the generateScalarStores() "
1321 "function in the BlockGenerator");
1323 for (MemoryAccess
*MA
: Stmt
) {
1324 if (MA
->isArrayKind() || MA
->isRead())
1327 Value
*NewVal
= getExitScalar(MA
, LTS
, BBMap
);
1328 Value
*Address
= getOrCreateAlloca(*MA
);
1329 assert((!isa
<Instruction
>(NewVal
) ||
1330 DT
.dominates(cast
<Instruction
>(NewVal
)->getParent(),
1331 Builder
.GetInsertBlock())) &&
1332 "Domination violation");
1333 assert((!isa
<Instruction
>(Address
) ||
1334 DT
.dominates(cast
<Instruction
>(Address
)->getParent(),
1335 Builder
.GetInsertBlock())) &&
1336 "Domination violation");
1337 Builder
.CreateStore(NewVal
, Address
);
1341 void RegionGenerator::addOperandToPHI(ScopStmt
&Stmt
, const PHINode
*PHI
,
1342 PHINode
*PHICopy
, BasicBlock
*IncomingBB
,
1343 LoopToScevMapT
<S
) {
1344 Region
*StmtR
= Stmt
.getRegion();
1346 // If the incoming block was not yet copied mark this PHI as incomplete.
1347 // Once the block will be copied the incoming value will be added.
1348 BasicBlock
*BBCopy
= BlockMap
[IncomingBB
];
1350 assert(StmtR
->contains(IncomingBB
) &&
1351 "Bad incoming block for PHI in non-affine region");
1352 IncompletePHINodeMap
[IncomingBB
].push_back(std::make_pair(PHI
, PHICopy
));
1356 Value
*OpCopy
= nullptr;
1357 if (StmtR
->contains(IncomingBB
)) {
1358 assert(RegionMaps
.count(BBCopy
) &&
1359 "Incoming PHI block did not have a BBMap");
1360 ValueMapT
&BBCopyMap
= RegionMaps
[BBCopy
];
1362 Value
*Op
= PHI
->getIncomingValueForBlock(IncomingBB
);
1364 // If the current insert block is different from the PHIs incoming block
1365 // change it, otherwise do not.
1366 auto IP
= Builder
.GetInsertPoint();
1367 if (IP
->getParent() != BBCopy
)
1368 Builder
.SetInsertPoint(BBCopy
->getTerminator());
1369 OpCopy
= getNewValue(Stmt
, Op
, BBCopyMap
, LTS
, getLoopForStmt(Stmt
));
1370 if (IP
->getParent() != BBCopy
)
1371 Builder
.SetInsertPoint(&*IP
);
1374 if (PHICopy
->getBasicBlockIndex(BBCopy
) >= 0)
1377 Value
*PHIOpAddr
= getOrCreatePHIAlloca(const_cast<PHINode
*>(PHI
));
1378 OpCopy
= new LoadInst(PHIOpAddr
, PHIOpAddr
->getName() + ".reload",
1379 BlockMap
[IncomingBB
]->getTerminator());
1382 assert(OpCopy
&& "Incoming PHI value was not copied properly");
1383 assert(BBCopy
&& "Incoming PHI block was not copied properly");
1384 PHICopy
->addIncoming(OpCopy
, BBCopy
);
1387 void RegionGenerator::copyPHIInstruction(ScopStmt
&Stmt
, PHINode
*PHI
,
1389 LoopToScevMapT
<S
) {
1390 unsigned NumIncoming
= PHI
->getNumIncomingValues();
1392 Builder
.CreatePHI(PHI
->getType(), NumIncoming
, "polly." + PHI
->getName());
1393 PHICopy
->moveBefore(PHICopy
->getParent()->getFirstNonPHI());
1394 BBMap
[PHI
] = PHICopy
;
1396 for (unsigned u
= 0; u
< NumIncoming
; u
++)
1397 addOperandToPHI(Stmt
, PHI
, PHICopy
, PHI
->getIncomingBlock(u
), LTS
);