31 #define DEBUG_TYPE "ppc-branch-coalescing"
33 STATISTIC(NumBlocksCoalesced,
"Number of blocks coalesced");
34 STATISTIC(NumPHINotMoved,
"Number of PHI Nodes that cannot be merged");
35 STATISTIC(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;
174 StringRef getPassName()
const override {
return "Branch Coalescing"; }
176 bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
177 CoalescingCandidateInfo &TargetRegion);
182 bool canMerge(CoalescingCandidateInfo &SourceRegion,
183 CoalescingCandidateInfo &TargetRegion)
const;
194 return new PPCBranchCoalescing();
198 "Branch Coalescing",
false,
false)
204 PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
205 : BranchBlock(
nullptr), BranchTargetBlock(
nullptr),
206 FallThroughBlock(
nullptr), MustMoveDown(
false), MustMoveUp(
false) {}
209 BranchBlock =
nullptr;
210 BranchTargetBlock =
nullptr;
211 FallThroughBlock =
nullptr;
213 MustMoveDown =
false;
218 MDT = &getAnalysis<MachineDominatorTree>();
219 MPDT = &getAnalysis<MachinePostDominatorTree>();
234 bool 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)
303 ? *Cand.BranchBlock->succ_rbegin()
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;
332 bool PPCBranchCoalescing::identicalOperands(
335 if (OpList1.
size() != OpList2.
size()) {
340 for (
unsigned i = 0;
i < OpList1.
size(); ++
i) {
345 <<
"Op2: " << Op2 <<
"\n");
354 LLVM_DEBUG(
dbgs() <<
"The operands are not provably identical.\n");
369 if (
TII->produceSameValue(*Op1Def, *Op2Def,
MRI)) {
371 <<
" produce the same value!\n");
377 LLVM_DEBUG(
dbgs() <<
"The operands are not provably identical.\n");
401 LLVM_DEBUG(
dbgs() <<
"SourceMBB contains no PHI instructions.\n");
410 if (MO.
getMBB() == SourceMBB)
427 bool PPCBranchCoalescing::canMoveToBeginning(
const MachineInstr &
MI,
434 for (
auto &
Def :
MI.defs()) {
436 if (
Use.isPHI() &&
Use.getParent() == &TargetMBB) {
465 for (
auto &
Use :
MI.uses()) {
473 dbgs() <<
" *** def is in another block -- safe to move!\n");
491 bool PPCBranchCoalescing::validateCandidates(
492 CoalescingCandidateInfo &SourceRegion,
493 CoalescingCandidateInfo &TargetRegion)
const {
495 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
496 llvm_unreachable(
"Expecting SourceRegion to immediately follow TargetRegion");
497 else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
499 else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
501 else if (!TargetRegion.FallThroughBlock->empty() ||
502 !SourceRegion.FallThroughBlock->empty())
534 bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
535 CoalescingCandidateInfo &TargetRegion)
const {
536 if (!validateCandidates(SourceRegion, TargetRegion))
542 I = SourceRegion.BranchBlock->instr_begin(),
543 E = SourceRegion.BranchBlock->getFirstNonPHI();
545 for (
auto &
Def :
I->defs())
547 if (
Use.isPHI() &&
Use.getParent() == SourceRegion.BranchTargetBlock) {
550 <<
" defines register used in another "
551 "PHI within branch target block -- can't merge\n");
555 if (
Use.getParent() == SourceRegion.BranchBlock) {
557 <<
" defines register used in this "
558 "block -- all must move down\n");
559 SourceRegion.MustMoveDown =
true;
567 I = SourceRegion.BranchBlock->getFirstNonPHI(),
568 E = SourceRegion.BranchBlock->end();
570 if (!canMoveToBeginning(*
I, *SourceRegion.BranchTargetBlock)) {
572 <<
" cannot move down - must move up!\n");
573 SourceRegion.MustMoveUp =
true;
575 if (!canMoveToEnd(*
I, *TargetRegion.BranchBlock)) {
577 <<
" cannot move up - must move down!\n");
578 SourceRegion.MustMoveDown =
true;
582 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ?
false :
true;
641 bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
642 CoalescingCandidateInfo &TargetRegion) {
644 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
649 if (!validateCandidates(SourceRegion, TargetRegion))
654 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
659 SourceRegion.BranchBlock->getFirstNonPHI();
661 SourceRegion.BranchBlock->getFirstTerminator();
664 ? SourceRegion.BranchTargetBlock
665 : TargetRegion.BranchBlock;
668 SourceRegion.MustMoveDown
669 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
670 : TargetRegion.BranchBlock->getFirstTerminator();
672 Source->splice(
Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
679 SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
680 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
681 SourceRegion.BranchBlock);
685 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
686 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
689 SourceRegion.BranchBlock->terminators().begin();
690 while (
I != SourceRegion.BranchBlock->terminators().end()) {
699 assert(TargetRegion.FallThroughBlock->empty() &&
700 "FallThroughBlocks should be empty!");
704 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
705 SourceRegion.FallThroughBlock);
706 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
709 assert(SourceRegion.BranchBlock->empty() &&
710 "Expecting branch block to be empty!");
711 SourceRegion.BranchBlock->eraseFromParent();
713 assert(SourceRegion.FallThroughBlock->empty() &&
714 "Expecting fall-through block to be empty!\n");
715 SourceRegion.FallThroughBlock->eraseFromParent();
717 NumBlocksCoalesced++;
726 bool didSomething =
false;
733 CoalescingCandidateInfo Cand1, Cand2;
738 bool MergedCandidates =
false;
740 MergedCandidates =
false;
744 Cand1.BranchBlock = &
MBB;
747 if (!canCoalesceBranch(Cand1))
750 Cand2.BranchBlock = Cand1.BranchTargetBlock;
751 if (!canCoalesceBranch(Cand2))
756 assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
757 "Branch-taken block should post-dominate first candidate");
759 if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
761 <<
" and " << Cand2.BranchBlock->getNumber()
762 <<
" have different branches\n");
765 if (!canMerge(Cand2, Cand1)) {
767 << Cand1.BranchBlock->getNumber() <<
" and "
768 << Cand2.BranchBlock->getNumber() <<
"\n");
769 NumBlocksNotCoalesced++;
772 LLVM_DEBUG(
dbgs() <<
"Merging blocks " << Cand1.BranchBlock->getNumber()
773 <<
" and " << Cand1.BranchTargetBlock->getNumber()
775 MergedCandidates = mergeCandidates(Cand2, Cand1);
776 if (MergedCandidates)
781 }
while (MergedCandidates);
787 MF.verify(
nullptr,
"Error in code produced by branch coalescing");