28#define DEBUG_TYPE "loop-vectorize"
34class PlainCFGBuilder {
67 bool isExternalDef(
Value *Val);
74 : TheLoop(Lp), LI(LI), Plan(
P) {}
87 VPBBPreds.
push_back(getOrCreateVPBB(Pred));
93void PlainCFGBuilder::fixPhiNodes() {
94 for (
auto *Phi : PhisToFix) {
95 assert(IRDef2VPValue.count(Phi) &&
"Missing VPInstruction for PHINode.");
97 assert(isa<VPWidenPHIRecipe>(VPVal) &&
98 "Expected WidenPHIRecipe for phi node.");
99 auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
100 assert(VPPhi->getNumOperands() == 0 &&
101 "Expected VPInstruction with no operands.");
103 for (
unsigned I = 0;
I !=
Phi->getNumOperands(); ++
I)
104 VPPhi->addIncoming(getOrCreateVPOperand(
Phi->getIncomingValue(
I)),
105 BB2VPBB[
Phi->getIncomingBlock(
I)]);
114 auto BlockIt = BB2VPBB.find(BB);
115 if (BlockIt != BB2VPBB.end())
117 return BlockIt->second;
120 Loop *CurrentLoop = LI->getLoopFor(BB);
123 auto Iter = Loop2Region.insert({CurrentLoop,
nullptr});
127 ParentR = Iter.first->second;
145bool PlainCFGBuilder::isExternalDef(
Value *Val) {
153 assert(InstParent &&
"Expected instruction parent.");
157 assert(PH &&
"Expected loop pre-header.");
159 if (InstParent == PH)
164 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
165 assert(Exit &&
"Expected loop with single exit.");
166 if (InstParent == Exit) {
172 return !TheLoop->contains(Inst);
180VPValue *PlainCFGBuilder::getOrCreateVPOperand(
Value *IRVal) {
181 auto VPValIt = IRDef2VPValue.find(IRVal);
182 if (VPValIt != IRDef2VPValue.end())
185 return VPValIt->second;
194 assert(isExternalDef(IRVal) &&
"Expected external definition as operand.");
198 VPValue *NewVPVal = Plan.getVPValueOrAddLiveIn(IRVal);
199 IRDef2VPValue[IRVal] = NewVPVal;
206void PlainCFGBuilder::createVPInstructionsForVPBB(
VPBasicBlock *VPBB,
208 VPIRBuilder.setInsertPoint(VPBB);
214 assert(!IRDef2VPValue.count(Inst) &&
215 "Instruction shouldn't have been visited.");
217 if (
auto *Br = dyn_cast<BranchInst>(Inst)) {
220 if (Br->isConditional()) {
221 VPValue *
Cond = getOrCreateVPOperand(Br->getCondition());
231 if (
auto *Phi = dyn_cast<PHINode>(Inst)) {
237 PhisToFix.push_back(Phi);
247 NewVPV = cast<VPInstruction>(
248 VPIRBuilder.createNaryOp(Inst->
getOpcode(), VPOperands, Inst));
251 IRDef2VPValue[Inst] = NewVPV;
256void PlainCFGBuilder::buildPlainCFG() {
266 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
268 "Unexpected loop preheader");
270 BB2VPBB[ThePreheaderBB] = ThePreheaderVPBB;
271 ThePreheaderVPBB->
setName(
"vector.ph");
272 for (
auto &
I : *ThePreheaderBB) {
273 if (
I.getType()->isVoidTy())
275 IRDef2VPValue[&
I] = Plan.getVPValueOrAddLiveIn(&
I);
278 VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
279 HeaderVPBB->
setName(
"vector.body");
289 createVPInstructionsForVPBB(VPBB, BB);
295 assert(TI &&
"Terminator expected.");
300 assert(SuccVPBB &&
"VPBB Successor not found.");
302 }
else if (NumSuccs == 2) {
304 assert(SuccVPBB0 &&
"Successor 0 not found.");
306 assert(SuccVPBB1 &&
"Successor 1 not found.");
309 assert(isa<BranchInst>(TI) &&
"Unsupported terminator!");
312 assert(IRDef2VPValue.count(cast<BranchInst>(TI)->getCondition()) &&
313 "Missing condition bit in IRDef2VPValue!");
321 setVPBBPredsFromBB(VPBB, BB);
327 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
328 assert(LoopExitBB &&
"Loops with multiple exits are not supported.");
332 setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
341 while (!LoopWorkList.
empty()) {
345 assert(Exiting ==
L->getExitingBlock() &&
346 "Latch must be the only exiting block");
352 VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(
L->getLoopPreheader());
357 Region->setEntry(HeaderVPBB);
364 Region->setExiting(ExitingVPBB);
368 LoopWorkList.
append(
L->begin(),
L->end());
376void VPlanHCFGBuilder::buildPlainCFG() {
377 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
378 PCFGBuilder.buildPlainCFG();
392 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())
This file defines the VPlanHCFGBuilder class which contains the public interface (buildHierarchicalCF...
LLVM Basic Block Representation.
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
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
BlockT * getHeader() const
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 append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
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)
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
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...
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.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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)
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.