30#define DEBUG_TYPE "ppc-branch-coalescing"
32STATISTIC(NumBlocksCoalesced,
"Number of blocks coalesced");
33STATISTIC(NumPHINotMoved,
"Number of PHI Nodes that cannot be merged");
34STATISTIC(NumBlocksNotCoalesced,
"Number of blocks not coalesced");
136 struct CoalescingCandidateInfo {
144 CoalescingCandidateInfo();
154 bool canCoalesceBranch(CoalescingCandidateInfo &Cand);
157 bool validateCandidates(CoalescingCandidateInfo &SourceRegion,
158 CoalescingCandidateInfo &TargetRegion)
const;
175 bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
176 CoalescingCandidateInfo &TargetRegion);
181 bool canMerge(CoalescingCandidateInfo &SourceRegion,
182 CoalescingCandidateInfo &TargetRegion)
const;
189char PPCBranchCoalescing::ID = 0;
193 return new PPCBranchCoalescing();
197 "Branch Coalescing",
false,
false)
203PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
204 : BranchBlock(
nullptr), BranchTargetBlock(
nullptr),
205 FallThroughBlock(
nullptr), MustMoveDown(
false), MustMoveUp(
false) {}
207void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {
208 BranchBlock =
nullptr;
209 BranchTargetBlock =
nullptr;
210 FallThroughBlock =
nullptr;
212 MustMoveDown =
false;
217 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
218 MPDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
233bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
235 << Cand.BranchBlock->getNumber() <<
" can be coalesced:");
244 for (
auto &
I : Cand.BranchBlock->terminators()) {
262 if (
I.getNumOperands() !=
I.getNumExplicitOperands()) {
263 LLVM_DEBUG(
dbgs() <<
"Terminator contains implicit operands - skip : "
269 if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
274 if (Cand.BranchBlock->mayHaveInlineAsmBr()) {
281 if (!Cand.BranchTargetBlock || FalseMBB ||
282 !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {
288 if (Cand.BranchBlock->succ_size() != 2) {
294 assert(Cand.BranchBlock->canFallThrough() &&
295 "Expecting the block to fall through!");
301 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
303 : *Cand.BranchBlock->succ_begin();
305 assert(Succ &&
"Expecting a valid fall-through block\n");
307 if (!Succ->
empty()) {
308 LLVM_DEBUG(
dbgs() <<
"Fall-through block contains code -- skip\n");
315 <<
"Successor of fall through block is not branch taken block\n");
319 Cand.FallThroughBlock = Succ;
331bool PPCBranchCoalescing::identicalOperands(
334 if (OpList1.
size() != OpList2.
size()) {
339 for (
unsigned i = 0; i < OpList1.
size(); ++i) {
344 <<
"Op2: " << Op2 <<
"\n");
352 LLVM_DEBUG(
dbgs() <<
"The operands are not provably identical.\n");
366 if (
TII->produceSameValue(*Op1Def, *Op2Def,
MRI)) {
368 <<
" produce the same value!\n");
374 LLVM_DEBUG(
dbgs() <<
"The operands are not provably identical.\n");
398 LLVM_DEBUG(
dbgs() <<
"SourceMBB contains no PHI instructions.\n");
405 for (
unsigned i = 2, e = PHIInst.
getNumOperands() + 1; i != e; i += 2) {
407 if (MO.
getMBB() == SourceMBB)
424bool PPCBranchCoalescing::canMoveToBeginning(
const MachineInstr &
MI,
431 for (
auto &Def :
MI.defs()) {
432 for (
auto &
Use :
MRI->use_instructions(
Def.getReg())) {
433 if (
Use.isPHI() &&
Use.getParent() == &TargetMBB) {
462 for (
auto &
Use :
MI.uses()) {
463 if (
Use.isReg() &&
Use.getReg().isVirtual()) {
470 dbgs() <<
" *** def is in another block -- safe to move!\n");
488bool PPCBranchCoalescing::validateCandidates(
489 CoalescingCandidateInfo &SourceRegion,
490 CoalescingCandidateInfo &TargetRegion)
const {
492 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
493 llvm_unreachable(
"Expecting SourceRegion to immediately follow TargetRegion");
494 else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
496 else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
498 else if (!TargetRegion.FallThroughBlock->empty() ||
499 !SourceRegion.FallThroughBlock->empty())
531bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
532 CoalescingCandidateInfo &TargetRegion)
const {
533 if (!validateCandidates(SourceRegion, TargetRegion))
539 I = SourceRegion.BranchBlock->instr_begin(),
540 E = SourceRegion.BranchBlock->getFirstNonPHI();
542 for (
auto &Def :
I->defs())
543 for (
auto &
Use :
MRI->use_instructions(
Def.getReg())) {
544 if (
Use.isPHI() &&
Use.getParent() == SourceRegion.BranchTargetBlock) {
547 <<
" defines register used in another "
548 "PHI within branch target block -- can't merge\n");
552 if (
Use.getParent() == SourceRegion.BranchBlock) {
554 <<
" defines register used in this "
555 "block -- all must move down\n");
556 SourceRegion.MustMoveDown =
true;
564 I = SourceRegion.BranchBlock->getFirstNonPHI(),
565 E = SourceRegion.BranchBlock->end();
567 if (!canMoveToBeginning(*
I, *SourceRegion.BranchTargetBlock)) {
569 <<
" cannot move down - must move up!\n");
570 SourceRegion.MustMoveUp =
true;
572 if (!canMoveToEnd(*
I, *TargetRegion.BranchBlock)) {
574 <<
" cannot move up - must move down!\n");
575 SourceRegion.MustMoveDown =
true;
579 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ?
false :
true;
638bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
639 CoalescingCandidateInfo &TargetRegion) {
641 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
646 if (!validateCandidates(SourceRegion, TargetRegion))
651 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
656 SourceRegion.BranchBlock->getFirstNonPHI();
658 SourceRegion.BranchBlock->getFirstTerminator();
661 ? SourceRegion.BranchTargetBlock
662 : TargetRegion.BranchBlock;
665 SourceRegion.MustMoveDown
666 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
667 : TargetRegion.BranchBlock->getFirstTerminator();
669 Source->splice(
Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
676 SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
677 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
678 SourceRegion.BranchBlock);
682 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
683 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
686 SourceRegion.BranchBlock->terminators().begin();
687 while (
I != SourceRegion.BranchBlock->terminators().end()) {
696 assert(TargetRegion.FallThroughBlock->empty() &&
697 "FallThroughBlocks should be empty!");
701 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
702 SourceRegion.FallThroughBlock);
703 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
704 TargetRegion.FallThroughBlock->normalizeSuccProbs();
707 assert(SourceRegion.BranchBlock->empty() &&
708 "Expecting branch block to be empty!");
709 SourceRegion.BranchBlock->eraseFromParent();
711 assert(SourceRegion.FallThroughBlock->empty() &&
712 "Expecting fall-through block to be empty!\n");
713 SourceRegion.FallThroughBlock->eraseFromParent();
715 NumBlocksCoalesced++;
724 bool didSomething =
false;
731 CoalescingCandidateInfo Cand1, Cand2;
736 bool MergedCandidates =
false;
738 MergedCandidates =
false;
742 Cand1.BranchBlock = &
MBB;
745 if (!canCoalesceBranch(Cand1))
748 Cand2.BranchBlock = Cand1.BranchTargetBlock;
749 if (!canCoalesceBranch(Cand2))
754 assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
755 "Branch-taken block should post-dominate first candidate");
757 if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
759 <<
" and " << Cand2.BranchBlock->getNumber()
760 <<
" have different branches\n");
763 if (!canMerge(Cand2, Cand1)) {
765 << Cand1.BranchBlock->getNumber() <<
" and "
766 << Cand2.BranchBlock->getNumber() <<
"\n");
767 NumBlocksNotCoalesced++;
770 LLVM_DEBUG(
dbgs() <<
"Merging blocks " << Cand1.BranchBlock->getNumber()
771 <<
" and " << Cand1.BranchTargetBlock->getNumber()
773 MergedCandidates = mergeCandidates(Cand2, Cand1);
774 if (MergedCandidates)
779 }
while (MergedCandidates);
785 MF.verify(
nullptr,
"Error in code produced by branch coalescing");
unsigned const MachineRegisterInfo * MRI
static void clear(coro::Shape &Shape)
const HexagonInstrInfo * TII
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
FunctionPass class - This class is used to implement most global optimizations.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
succ_reverse_iterator succ_rbegin()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setMBB(MachineBasicBlock *MBB)
Register getReg() const
getReg - Returns the register number.
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
virtual const TargetInstrInfo * getInstrInfo() const
Target - Wrapper for Target specific information.
A Use represents the edge between a Value definition and its users.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
NodeAddr< DefNode * > Def
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.
FunctionPass * createPPCBranchCoalescingPass()
createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing Pass
void initializePPCBranchCoalescingPass(PassRegistry &)