28#define DEBUG_TYPE "loop-vectorize"
34class PlainCFGBuilder {
68 bool isExternalDef(
Value *Val);
75 : TheLoop(Lp), LI(LI), Plan(
P) {}
87 Loop *LoopForBB = LI->getLoopFor(BB);
88 if (!SinglePred || LI->getLoopFor(SinglePred) == LoopForBB)
92 assert(SinglePred == LI->getLoopFor(SinglePred)->getLoopLatch() &&
93 "SinglePred must be the only loop latch");
96 if (
auto *LatchBB = GetLatchOfExit(BB)) {
97 auto *PredRegion = getOrCreateVPBB(LatchBB)->getParent();
98 assert(VPBB == cast<VPBasicBlock>(PredRegion->getSingleSuccessor()) &&
99 "successor must already be set for PredRegion; it must have VPBB "
100 "as single successor");
107 VPBBPreds.
push_back(getOrCreateVPBB(Pred));
112 return L && BB == L->getHeader();
118 Loop *LoopOfBB = LI->getLoopFor(BB);
123void PlainCFGBuilder::fixPhiNodes() {
124 for (
auto *Phi : PhisToFix) {
125 assert(IRDef2VPValue.count(Phi) &&
"Missing VPInstruction for PHINode.");
127 assert(isa<VPWidenPHIRecipe>(VPVal) &&
128 "Expected WidenPHIRecipe for phi node.");
129 auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
130 assert(VPPhi->getNumOperands() == 0 &&
131 "Expected VPInstruction with no operands.");
133 Loop *
L = LI->getLoopFor(
Phi->getParent());
140 getOrCreateVPOperand(
Phi->getIncomingValueForBlock(LoopPred)),
144 getOrCreateVPOperand(
Phi->getIncomingValueForBlock(LoopLatch)),
149 for (
unsigned I = 0;
I !=
Phi->getNumOperands(); ++
I)
150 VPPhi->addIncoming(getOrCreateVPOperand(
Phi->getIncomingValue(
I)),
151 BB2VPBB[
Phi->getIncomingBlock(
I)]);
164 if (
auto *VPBB = BB2VPBB.lookup(BB)) {
175 Loop *LoopOfBB = LI->getLoopFor(BB);
181 "region must exist or BB must be a loop header");
191 RegionOfVPBB->setParent(Loop2Region[LoopOfBB->
getParentLoop()]);
192 RegionOfVPBB->setEntry(VPBB);
193 Loop2Region[LoopOfBB] = RegionOfVPBB;
205bool PlainCFGBuilder::isExternalDef(
Value *Val) {
213 assert(InstParent &&
"Expected instruction parent.");
217 assert(PH &&
"Expected loop pre-header.");
219 if (InstParent == PH)
224 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
225 assert(Exit &&
"Expected loop with single exit.");
226 if (InstParent == Exit) {
232 return !TheLoop->contains(Inst);
240VPValue *PlainCFGBuilder::getOrCreateVPOperand(
Value *IRVal) {
241 auto VPValIt = IRDef2VPValue.find(IRVal);
242 if (VPValIt != IRDef2VPValue.end())
245 return VPValIt->second;
254 assert(isExternalDef(IRVal) &&
"Expected external definition as operand.");
258 VPValue *NewVPVal = Plan.getVPValueOrAddLiveIn(IRVal);
259 IRDef2VPValue[IRVal] = NewVPVal;
266void PlainCFGBuilder::createVPInstructionsForVPBB(
VPBasicBlock *VPBB,
268 VPIRBuilder.setInsertPoint(VPBB);
274 assert(!IRDef2VPValue.count(Inst) &&
275 "Instruction shouldn't have been visited.");
277 if (
auto *Br = dyn_cast<BranchInst>(Inst)) {
280 if (Br->isConditional()) {
281 VPValue *
Cond = getOrCreateVPOperand(Br->getCondition());
291 if (
auto *Phi = dyn_cast<PHINode>(Inst)) {
297 PhisToFix.push_back(Phi);
307 NewVPV = cast<VPInstruction>(
308 VPIRBuilder.createNaryOp(Inst->
getOpcode(), VPOperands, Inst));
311 IRDef2VPValue[Inst] = NewVPV;
316void PlainCFGBuilder::buildPlainCFG() {
326 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
328 "Unexpected loop preheader");
333 BB2VPBB[ThePreheaderBB] = ThePreheaderVPBB;
334 ThePreheaderVPBB->
setName(
"vector.ph");
335 for (
auto &
I : *ThePreheaderBB) {
336 if (
I.getType()->isVoidTy())
338 IRDef2VPValue[&
I] = Plan.getVPValueOrAddLiveIn(&
I);
342 VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
343 HeaderVPBB->
setName(
"vector.body");
354 createVPInstructionsForVPBB(VPBB, BB);
355 Loop *LoopForBB = LI->getLoopFor(BB);
358 setVPBBPredsFromBB(VPBB, BB);
362 setRegionPredsFromBB(
Region, BB);
368 auto *BI = cast<BranchInst>(BB->getTerminator());
371 auto *
Successor = getOrCreateVPBB(BB->getSingleSuccessor());
377 assert(BI->isConditional() && NumSuccs == 2 && BI->isConditional() &&
378 "block must have conditional branch with 2 successors");
381 assert(IRDef2VPValue.contains(BI->getCondition()) &&
382 "Missing condition bit in IRDef2VPValue!");
383 VPBasicBlock *Successor0 = getOrCreateVPBB(BI->getSuccessor(0));
384 VPBasicBlock *Successor1 = getOrCreateVPBB(BI->getSuccessor(1));
398 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
399 assert(LoopExitBB &&
"Loops with multiple exits are not supported.");
403 setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
411void VPlanHCFGBuilder::buildPlainCFG() {
412 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
413 PCFGBuilder.buildPlainCFG();
427 LLVM_DEBUG(
dbgs() <<
"Dominator Tree after building the plain CFG.\n";
This file provides a LoopVectorizationPlanner class.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isHeaderBB(BasicBlock *BB, Loop *L)
static bool isHeaderVPBB(VPBasicBlock *VPBB)
This file defines the VPlanHCFGBuilder class which contains the public interface (buildHierarchicalCF...
LLVM Basic Block Representation.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This class represents an Operation in the Expression.
void print(raw_ostream &O) const
print - Convert to human readable form
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const BasicBlock * getParent() const
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Represents a single loop in the control flow graph.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::string str() const
str - Get the contents as an std::string.
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
VPRegionBlock * getParent()
void setName(const Twine &newName)
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
void setParent(VPRegionBlock *P)
VPlan-based builder utility analogous to IRBuilder.
This is a concrete Recipe that models a single VPlan-level instruction.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
const VPBlockBase * getEntry() const
A recipe for handling header phis that are widened in the vector loop.
void buildHierarchicalCFG()
Build H-CFG for TheLoop and update Plan accordingly.
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
void setName(const Twine &newName)
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
LLVM Value Representation.
StringRef getName() const
Return a constant reference to the value's name.
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
auto predecessors(const MachineBasicBlock *BB)
unsigned succ_size(const MachineBasicBlock *BB)
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.