28#define DEBUG_TYPE "loop-vectorize"
34class PlainCFGBuilder {
67 bool isExternalDef(
Value *Val);
74 : TheLoop(Lp), LI(LI), Plan(
P) {}
88 VPBBPreds.
push_back(getOrCreateVPBB(Pred));
94void PlainCFGBuilder::fixPhiNodes() {
95 for (
auto *Phi : PhisToFix) {
96 assert(IRDef2VPValue.count(Phi) &&
"Missing VPInstruction for PHINode.");
97 VPValue *VPVal = IRDef2VPValue[Phi];
98 assert(isa<VPWidenPHIRecipe>(VPVal) &&
99 "Expected WidenPHIRecipe for phi node.");
100 auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
101 assert(VPPhi->getNumOperands() == 0 &&
102 "Expected VPInstruction with no operands.");
104 for (
unsigned I = 0;
I != Phi->getNumOperands(); ++
I)
105 VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(
I)),
106 BB2VPBB[Phi->getIncomingBlock(
I)]);
115 auto BlockIt = BB2VPBB.find(BB);
116 if (BlockIt != BB2VPBB.end())
118 return BlockIt->second;
121 Loop *CurrentLoop = LI->getLoopFor(BB);
124 auto Iter = Loop2Region.insert({CurrentLoop,
nullptr});
128 ParentR = Iter.first->second;
146bool PlainCFGBuilder::isExternalDef(
Value *Val) {
154 assert(InstParent &&
"Expected instruction parent.");
158 assert(PH &&
"Expected loop pre-header.");
160 if (InstParent == PH)
165 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
166 assert(Exit &&
"Expected loop with single exit.");
167 if (InstParent == Exit) {
173 return !TheLoop->contains(Inst);
181VPValue *PlainCFGBuilder::getOrCreateVPOperand(
Value *IRVal) {
182 auto VPValIt = IRDef2VPValue.find(IRVal);
183 if (VPValIt != IRDef2VPValue.end())
186 return VPValIt->second;
195 assert(isExternalDef(IRVal) &&
"Expected external definition as operand.");
199 VPValue *NewVPVal = Plan.getOrAddExternalDef(IRVal);
200 IRDef2VPValue[IRVal] = NewVPVal;
207void PlainCFGBuilder::createVPInstructionsForVPBB(
VPBasicBlock *VPBB,
209 VPIRBuilder.setInsertPoint(VPBB);
215 assert(!IRDef2VPValue.count(Inst) &&
216 "Instruction shouldn't have been visited.");
218 if (
auto *Br = dyn_cast<BranchInst>(Inst)) {
221 if (Br->isConditional()) {
222 VPValue *
Cond = getOrCreateVPOperand(Br->getCondition());
232 if (
auto *Phi = dyn_cast<PHINode>(Inst)) {
238 PhisToFix.push_back(Phi);
244 VPOperands.
push_back(getOrCreateVPOperand(Op));
248 NewVPV = cast<VPInstruction>(
249 VPIRBuilder.createNaryOp(Inst->
getOpcode(), VPOperands, Inst));
252 IRDef2VPValue[Inst] = NewVPV;
267 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
269 "Unexpected loop preheader");
270 VPBasicBlock *ThePreheaderVPBB = getOrCreateVPBB(ThePreheaderBB);
271 ThePreheaderVPBB->
setName(
"vector.ph");
272 for (
auto &
I : *ThePreheaderBB) {
273 if (
I.getType()->isVoidTy())
275 IRDef2VPValue[&
I] = Plan.getOrAddExternalDef(&
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());
375 return ThePreheaderVPBB;
379 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
380 return PCFGBuilder.buildPlainCFG();
395 LLVM_DEBUG(
dbgs() <<
"Dominator Tree after building the plain CFG.\n";
SmallVector< MachineOperand, 4 > Cond
This file provides a LoopVectorizationPlanner class.
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...
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.
VPBlockBase * setEntry(VPBlockBase *Block)
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.
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.