Deleted Added
sdiff udiff text old ( 200581 ) new ( 201360 )
full compact
BranchFolding.cpp (200581) BranchFolding.cpp (201360)
1//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 84 unchanged lines hidden (view full) ---

93 case cl::BOU_FALSE: EnableTailMerge = false; break;
94 }
95}
96
97/// RemoveDeadBlock - Remove the specified dead machine basic block from the
98/// function, updating the CFG.
99void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
100 assert(MBB->pred_empty() && "MBB must be dead!");
1//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 84 unchanged lines hidden (view full) ---

93 case cl::BOU_FALSE: EnableTailMerge = false; break;
94 }
95}
96
97/// RemoveDeadBlock - Remove the specified dead machine basic block from the
98/// function, updating the CFG.
99void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
100 assert(MBB->pred_empty() && "MBB must be dead!");
101 DEBUG(errs() << "\nRemoving MBB: " << *MBB);
101 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
102
103 MachineFunction *MF = MBB->getParent();
104 // drop all successors.
105 while (!MBB->succ_empty())
106 MBB->removeSuccessor(MBB->succ_end()-1);
107
108 // If there are any labels in the basic block, unregister them from
109 // MachineModuleInfo.

--- 521 unchanged lines hidden (view full) ---

631 commonTailIndex = i;
632 }
633 }
634
635 MachineBasicBlock::iterator BBI =
636 SameTails[commonTailIndex].getTailStartPos();
637 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
638
102
103 MachineFunction *MF = MBB->getParent();
104 // drop all successors.
105 while (!MBB->succ_empty())
106 MBB->removeSuccessor(MBB->succ_end()-1);
107
108 // If there are any labels in the basic block, unregister them from
109 // MachineModuleInfo.

--- 521 unchanged lines hidden (view full) ---

631 commonTailIndex = i;
632 }
633 }
634
635 MachineBasicBlock::iterator BBI =
636 SameTails[commonTailIndex].getTailStartPos();
637 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
638
639 DEBUG(errs() << "\nSplitting BB#" << MBB->getNumber() << ", size "
639 DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size "
640 << maxCommonTailLength);
641
642 MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
643 SameTails[commonTailIndex].setBlock(newMBB);
644 SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
645
646 // If we split PredBB, newMBB is the new predecessor.
647 if (PredBB == MBB)

--- 13 unchanged lines hidden (view full) ---

661bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
662 MachineBasicBlock *PredBB) {
663 bool MadeChange = false;
664
665 // Except for the special cases below, tail-merge if there are at least
666 // this many instructions in common.
667 unsigned minCommonTailLength = TailMergeSize;
668
640 << maxCommonTailLength);
641
642 MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
643 SameTails[commonTailIndex].setBlock(newMBB);
644 SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
645
646 // If we split PredBB, newMBB is the new predecessor.
647 if (PredBB == MBB)

--- 13 unchanged lines hidden (view full) ---

661bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
662 MachineBasicBlock *PredBB) {
663 bool MadeChange = false;
664
665 // Except for the special cases below, tail-merge if there are at least
666 // this many instructions in common.
667 unsigned minCommonTailLength = TailMergeSize;
668
669 DEBUG(errs() << "\nTryTailMergeBlocks: ";
669 DEBUG(dbgs() << "\nTryTailMergeBlocks: ";
670 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
670 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
671 errs() << "BB#" << MergePotentials[i].getBlock()->getNumber()
671 dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber()
672 << (i == e-1 ? "" : ", ");
672 << (i == e-1 ? "" : ", ");
673 errs() << "\n";
673 dbgs() << "\n";
674 if (SuccBB) {
674 if (SuccBB) {
675 errs() << " with successor BB#" << SuccBB->getNumber() << '\n';
675 dbgs() << " with successor BB#" << SuccBB->getNumber() << '\n';
676 if (PredBB)
676 if (PredBB)
677 errs() << " which has fall-through from BB#"
677 dbgs() << " which has fall-through from BB#"
678 << PredBB->getNumber() << "\n";
679 }
678 << PredBB->getNumber() << "\n";
679 }
680 errs() << "Looking for common tails of at least "
680 dbgs() << "Looking for common tails of at least "
681 << minCommonTailLength << " instruction"
682 << (minCommonTailLength == 1 ? "" : "s") << '\n';
683 );
684
685 // Sort by hash value so that blocks with identical end sequences sort
686 // together.
687 std::stable_sort(MergePotentials.begin(), MergePotentials.end());
688

--- 54 unchanged lines hidden (view full) ---

743 // None of the blocks consist entirely of the common tail.
744 // Split a block so that one does.
745 commonTailIndex = CreateCommonTailOnlyBlock(PredBB, maxCommonTailLength);
746 }
747
748 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
749 // MBB is common tail. Adjust all other BB's to jump to this one.
750 // Traversal must be forwards so erases work.
681 << minCommonTailLength << " instruction"
682 << (minCommonTailLength == 1 ? "" : "s") << '\n';
683 );
684
685 // Sort by hash value so that blocks with identical end sequences sort
686 // together.
687 std::stable_sort(MergePotentials.begin(), MergePotentials.end());
688

--- 54 unchanged lines hidden (view full) ---

743 // None of the blocks consist entirely of the common tail.
744 // Split a block so that one does.
745 commonTailIndex = CreateCommonTailOnlyBlock(PredBB, maxCommonTailLength);
746 }
747
748 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
749 // MBB is common tail. Adjust all other BB's to jump to this one.
750 // Traversal must be forwards so erases work.
751 DEBUG(errs() << "\nUsing common tail in BB#" << MBB->getNumber()
751 DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber()
752 << " for ");
753 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
754 if (commonTailIndex == i)
755 continue;
752 << " for ");
753 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
754 if (commonTailIndex == i)
755 continue;
756 DEBUG(errs() << "BB#" << SameTails[i].getBlock()->getNumber()
756 DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber()
757 << (i == e-1 ? "" : ", "));
758 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
759 ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
760 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
761 MergePotentials.erase(SameTails[i].getMPIter());
762 }
757 << (i == e-1 ? "" : ", "));
758 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
759 ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
760 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
761 MergePotentials.erase(SameTails[i].getMPIter());
762 }
763 DEBUG(errs() << "\n");
763 DEBUG(dbgs() << "\n");
764 // We leave commonTailIndex in the worklist in case there are other blocks
765 // that match it with a smaller number of instructions.
766 MadeChange = true;
767 }
768 return MadeChange;
769}
770
771bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {

--- 222 unchanged lines hidden (view full) ---

994 // into the prior block. This doesn't usually happen when SimplifyCFG
995 // has been used, but it can happen if tail merging splits a fall-through
996 // predecessor of a block.
997 // This has to check PrevBB->succ_size() because EH edges are ignored by
998 // AnalyzeBranch.
999 if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1000 PrevBB.succ_size() == 1 &&
1001 !MBB->hasAddressTaken()) {
764 // We leave commonTailIndex in the worklist in case there are other blocks
765 // that match it with a smaller number of instructions.
766 MadeChange = true;
767 }
768 return MadeChange;
769}
770
771bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {

--- 222 unchanged lines hidden (view full) ---

994 // into the prior block. This doesn't usually happen when SimplifyCFG
995 // has been used, but it can happen if tail merging splits a fall-through
996 // predecessor of a block.
997 // This has to check PrevBB->succ_size() because EH edges are ignored by
998 // AnalyzeBranch.
999 if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1000 PrevBB.succ_size() == 1 &&
1001 !MBB->hasAddressTaken()) {
1002 DEBUG(errs() << "\nMerging into block: " << PrevBB
1002 DEBUG(dbgs() << "\nMerging into block: " << PrevBB
1003 << "From MBB: " << *MBB);
1004 PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1005 PrevBB.removeSuccessor(PrevBB.succ_begin());;
1006 assert(PrevBB.succ_empty());
1007 PrevBB.transferSuccessors(MBB);
1008 MadeChange = true;
1009 return MadeChange;
1010 }

--- 68 unchanged lines hidden (view full) ---

1079 (!PriorTBB->canFallThrough() || PriorTBB->empty()))
1080 DoTransform = false;
1081
1082
1083 if (DoTransform) {
1084 // Reverse the branch so we will fall through on the previous true cond.
1085 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1086 if (!TII->ReverseBranchCondition(NewPriorCond)) {
1003 << "From MBB: " << *MBB);
1004 PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1005 PrevBB.removeSuccessor(PrevBB.succ_begin());;
1006 assert(PrevBB.succ_empty());
1007 PrevBB.transferSuccessors(MBB);
1008 MadeChange = true;
1009 return MadeChange;
1010 }

--- 68 unchanged lines hidden (view full) ---

1079 (!PriorTBB->canFallThrough() || PriorTBB->empty()))
1080 DoTransform = false;
1081
1082
1083 if (DoTransform) {
1084 // Reverse the branch so we will fall through on the previous true cond.
1085 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1086 if (!TII->ReverseBranchCondition(NewPriorCond)) {
1087 DEBUG(errs() << "\nMoving MBB: " << *MBB
1087 DEBUG(dbgs() << "\nMoving MBB: " << *MBB
1088 << "To make fallthrough to: " << *PriorTBB << "\n");
1089
1090 TII->RemoveBranch(PrevBB);
1091 TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond);
1092
1093 // Move this block to the end of the function.
1094 MBB->moveAfter(--MF.end());
1095 MadeChange = true;

--- 121 unchanged lines hidden (view full) ---

1217 if (!MBB->isLandingPad()) {
1218 // Check all the predecessors of this block. If one of them has no fall
1219 // throughs, move this block right after it.
1220 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
1221 E = MBB->pred_end(); PI != E; ++PI) {
1222 // Analyze the branch at the end of the pred.
1223 MachineBasicBlock *PredBB = *PI;
1224 MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
1088 << "To make fallthrough to: " << *PriorTBB << "\n");
1089
1090 TII->RemoveBranch(PrevBB);
1091 TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond);
1092
1093 // Move this block to the end of the function.
1094 MBB->moveAfter(--MF.end());
1095 MadeChange = true;

--- 121 unchanged lines hidden (view full) ---

1217 if (!MBB->isLandingPad()) {
1218 // Check all the predecessors of this block. If one of them has no fall
1219 // throughs, move this block right after it.
1220 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
1221 E = MBB->pred_end(); PI != E; ++PI) {
1222 // Analyze the branch at the end of the pred.
1223 MachineBasicBlock *PredBB = *PI;
1224 MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
1225 MachineBasicBlock *PredTBB, *PredFBB;
1225 MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
1226 SmallVector<MachineOperand, 4> PredCond;
1227 if (PredBB != MBB && !PredBB->canFallThrough() &&
1228 !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)
1229 && (!CurFallsThru || !CurTBB || !CurFBB)
1230 && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1231 // If the current block doesn't fall through, just move it.
1232 // If the current block can fall through and does not end with a
1233 // conditional branch, we need to append an unconditional jump to

--- 35 unchanged lines hidden (view full) ---

1269 MadeChange = true;
1270 goto ReoptimizeBlock;
1271 }
1272 }
1273
1274 // Okay, there is no really great place to put this block. If, however,
1275 // the block before this one would be a fall-through if this block were
1276 // removed, move this block to the end of the function.
1226 SmallVector<MachineOperand, 4> PredCond;
1227 if (PredBB != MBB && !PredBB->canFallThrough() &&
1228 !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)
1229 && (!CurFallsThru || !CurTBB || !CurFBB)
1230 && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1231 // If the current block doesn't fall through, just move it.
1232 // If the current block can fall through and does not end with a
1233 // conditional branch, we need to append an unconditional jump to

--- 35 unchanged lines hidden (view full) ---

1269 MadeChange = true;
1270 goto ReoptimizeBlock;
1271 }
1272 }
1273
1274 // Okay, there is no really great place to put this block. If, however,
1275 // the block before this one would be a fall-through if this block were
1276 // removed, move this block to the end of the function.
1277 MachineBasicBlock *PrevTBB, *PrevFBB;
1277 MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0;
1278 SmallVector<MachineOperand, 4> PrevCond;
1279 if (FallThrough != MF.end() &&
1280 !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1281 PrevBB.isSuccessor(FallThrough)) {
1282 MBB->moveAfter(--MF.end());
1283 MadeChange = true;
1284 return MadeChange;
1285 }
1286 }
1287 }
1288
1289 return MadeChange;
1290}
1278 SmallVector<MachineOperand, 4> PrevCond;
1279 if (FallThrough != MF.end() &&
1280 !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1281 PrevBB.isSuccessor(FallThrough)) {
1282 MBB->moveAfter(--MF.end());
1283 MadeChange = true;
1284 return MadeChange;
1285 }
1286 }
1287 }
1288
1289 return MadeChange;
1290}