31#define DEBUG_TYPE "ppc-branch-coalescing"
33STATISTIC(NumBlocksCoalesced,
"Number of blocks coalesced");
34STATISTIC(NumPHINotMoved,
"Number of PHI Nodes that cannot be merged");
35STATISTIC(NumBlocksNotCoalesced,
"Number of blocks not coalesced");
137 struct CoalescingCandidateInfo {
145 CoalescingCandidateInfo();
155 bool canCoalesceBranch(CoalescingCandidateInfo &Cand);
158 bool validateCandidates(CoalescingCandidateInfo &SourceRegion,
159 CoalescingCandidateInfo &TargetRegion)
const;
176 bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
177 CoalescingCandidateInfo &TargetRegion);
182 bool canMerge(CoalescingCandidateInfo &SourceRegion,
183 CoalescingCandidateInfo &TargetRegion)
const;
190char PPCBranchCoalescing::ID = 0;
194 return new PPCBranchCoalescing();
198 "Branch Coalescing",
false,
false)
204PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
205 : BranchBlock(
nullptr), BranchTargetBlock(
nullptr),
206 FallThroughBlock(
nullptr), MustMoveDown(
false), MustMoveUp(
false) {}
208void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {
209 BranchBlock =
nullptr;
210 BranchTargetBlock =
nullptr;
211 FallThroughBlock =
nullptr;
213 MustMoveDown =
false;
218 MDT = &getAnalysis<MachineDominatorTree>();
219 MPDT = &getAnalysis<MachinePostDominatorTree>();
234bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
236 << Cand.BranchBlock->getNumber() <<
" can be coalesced:");
245 for (
auto &
I : Cand.BranchBlock->terminators()) {
263 if (
I.getNumOperands() !=
I.getNumExplicitOperands()) {
264 LLVM_DEBUG(
dbgs() <<
"Terminator contains implicit operands - skip : "
270 if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
275 if (Cand.BranchBlock->mayHaveInlineAsmBr()) {
282 if (!Cand.BranchTargetBlock || FalseMBB ||
283 !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {
289 if (Cand.BranchBlock->succ_size() != 2) {
295 assert(Cand.BranchBlock->canFallThrough() &&
296 "Expecting the block to fall through!");
302 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
304 : *Cand.BranchBlock->succ_begin();
306 assert(Succ &&
"Expecting a valid fall-through block\n");
308 if (!Succ->
empty()) {
309 LLVM_DEBUG(
dbgs() <<
"Fall-through block contains code -- skip\n");
316 <<
"Successor of fall through block is not branch taken block\n");
320 Cand.FallThroughBlock = Succ;
332bool PPCBranchCoalescing::identicalOperands(
335 if (OpList1.
size() != OpList2.
size()) {
340 for (
unsigned i = 0; i < OpList1.
size(); ++i) {
345 <<
"Op2: " << Op2 <<
"\n");
353 LLVM_DEBUG(
dbgs() <<
"The operands are not provably identical.\n");
367 if (
TII->produceSameValue(*Op1Def, *Op2Def,
MRI)) {
369 <<
" produce the same value!\n");
375 LLVM_DEBUG(
dbgs() <<
"The operands are not provably identical.\n");
399 LLVM_DEBUG(
dbgs() <<
"SourceMBB contains no PHI instructions.\n");
406 for (
unsigned i = 2, e = PHIInst.
getNumOperands() + 1; i != e; i += 2) {
408 if (MO.
getMBB() == SourceMBB)
425bool PPCBranchCoalescing::canMoveToBeginning(
const MachineInstr &
MI,
432 for (
auto &Def :
MI.defs()) {
433 for (
auto &
Use :
MRI->use_instructions(
Def.getReg())) {
434 if (
Use.isPHI() &&
Use.getParent() == &TargetMBB) {
463 for (
auto &
Use :
MI.uses()) {
464 if (
Use.isReg() &&
Use.getReg().isVirtual()) {
471 dbgs() <<
" *** def is in another block -- safe to move!\n");
489bool PPCBranchCoalescing::validateCandidates(
490 CoalescingCandidateInfo &SourceRegion,
491 CoalescingCandidateInfo &TargetRegion)
const {
493 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
494 llvm_unreachable(
"Expecting SourceRegion to immediately follow TargetRegion");
495 else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
497 else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
499 else if (!TargetRegion.FallThroughBlock->empty() ||
500 !SourceRegion.FallThroughBlock->empty())
532bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
533 CoalescingCandidateInfo &TargetRegion)
const {
534 if (!validateCandidates(SourceRegion, TargetRegion))
540 I = SourceRegion.BranchBlock->instr_begin(),
541 E = SourceRegion.BranchBlock->getFirstNonPHI();
543 for (
auto &Def :
I->defs())
544 for (
auto &
Use :
MRI->use_instructions(
Def.getReg())) {
545 if (
Use.isPHI() &&
Use.getParent() == SourceRegion.BranchTargetBlock) {
548 <<
" defines register used in another "
549 "PHI within branch target block -- can't merge\n");
553 if (
Use.getParent() == SourceRegion.BranchBlock) {
555 <<
" defines register used in this "
556 "block -- all must move down\n");
557 SourceRegion.MustMoveDown =
true;
565 I = SourceRegion.BranchBlock->getFirstNonPHI(),
566 E = SourceRegion.BranchBlock->end();
568 if (!canMoveToBeginning(*
I, *SourceRegion.BranchTargetBlock)) {
570 <<
" cannot move down - must move up!\n");
571 SourceRegion.MustMoveUp =
true;
573 if (!canMoveToEnd(*
I, *TargetRegion.BranchBlock)) {
575 <<
" cannot move up - must move down!\n");
576 SourceRegion.MustMoveDown =
true;
580 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ?
false :
true;
639bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
640 CoalescingCandidateInfo &TargetRegion) {
642 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
647 if (!validateCandidates(SourceRegion, TargetRegion))
652 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
657 SourceRegion.BranchBlock->getFirstNonPHI();
659 SourceRegion.BranchBlock->getFirstTerminator();
662 ? SourceRegion.BranchTargetBlock
663 : TargetRegion.BranchBlock;
666 SourceRegion.MustMoveDown
667 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
668 : TargetRegion.BranchBlock->getFirstTerminator();
670 Source->splice(
Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
677 SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
678 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
679 SourceRegion.BranchBlock);
683 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
684 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
687 SourceRegion.BranchBlock->terminators().begin();
688 while (
I != SourceRegion.BranchBlock->terminators().end()) {
697 assert(TargetRegion.FallThroughBlock->empty() &&
698 "FallThroughBlocks should be empty!");
702 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
703 SourceRegion.FallThroughBlock);
704 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
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
SmallVector< MachineOperand, 4 > Cond
This file implements the BitVector class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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)
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 '...
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 &)