aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/BranchRelaxation.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/BranchRelaxation.cpp')
-rw-r--r--lib/CodeGen/BranchRelaxation.cpp184
1 files changed, 119 insertions, 65 deletions
diff --git a/lib/CodeGen/BranchRelaxation.cpp b/lib/CodeGen/BranchRelaxation.cpp
index 0d87f142c7cc..c092da2b6602 100644
--- a/lib/CodeGen/BranchRelaxation.cpp
+++ b/lib/CodeGen/BranchRelaxation.cpp
@@ -18,6 +18,7 @@
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/Config/llvm-config.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
@@ -95,7 +96,7 @@ class BranchRelaxation : public MachineFunctionPass {
MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
MachineBasicBlock *DestBB);
- void adjustBlockOffsets(MachineBasicBlock &MBB);
+ void adjustBlockOffsets(MachineBasicBlock &Start);
bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
bool fixupConditionalBranch(MachineInstr &MI);
@@ -287,10 +288,11 @@ bool BranchRelaxation::isBlockInRange(
if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
return true;
- DEBUG(dbgs() << "Out of range branch to destination "
- << printMBBReference(DestBB) << " from "
- << printMBBReference(*MI.getParent()) << " to " << DestOffset
- << " offset " << DestOffset - BrOffset << '\t' << MI);
+ LLVM_DEBUG(dbgs() << "Out of range branch to destination "
+ << printMBBReference(DestBB) << " from "
+ << printMBBReference(*MI.getParent()) << " to "
+ << DestOffset << " offset " << DestOffset - BrOffset << '\t'
+ << MI);
return false;
}
@@ -302,8 +304,41 @@ bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
DebugLoc DL = MI.getDebugLoc();
MachineBasicBlock *MBB = MI.getParent();
MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+ MachineBasicBlock *NewBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
+ auto insertUncondBranch = [&](MachineBasicBlock *MBB,
+ MachineBasicBlock *DestBB) {
+ unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
+ int NewBrSize = 0;
+ TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
+ BBSize += NewBrSize;
+ };
+ auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
+ MachineBasicBlock *FBB,
+ SmallVectorImpl<MachineOperand>& Cond) {
+ unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
+ int NewBrSize = 0;
+ TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
+ BBSize += NewBrSize;
+ };
+ auto removeBranch = [&](MachineBasicBlock *MBB) {
+ unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
+ int RemovedSize = 0;
+ TII->removeBranch(*MBB, &RemovedSize);
+ BBSize -= RemovedSize;
+ };
+
+ auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
+ MachineBasicBlock *NewBB) {
+ // Keep the block offsets up to date.
+ adjustBlockOffsets(*MBB);
+
+ // Need to fix live-in lists if we track liveness.
+ if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
+ computeAndAddLiveIns(LiveRegs, *NewBB);
+ };
+
bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
assert(!Fail && "branches to be relaxed must be analyzable");
(void)Fail;
@@ -316,71 +351,90 @@ bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
// b L1
// L2:
- if (FBB && isBlockInRange(MI, *FBB)) {
- // Last MI in the BB is an unconditional branch. We can simply invert the
- // condition and swap destinations:
- // beq L1
- // b L2
- // =>
- // bne L2
- // b L1
- DEBUG(dbgs() << " Invert condition and swap "
- "its destination with " << MBB->back());
-
- TII->reverseBranchCondition(Cond);
- int OldSize = 0, NewSize = 0;
- TII->removeBranch(*MBB, &OldSize);
- TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize);
-
- BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize);
- return true;
- } else if (FBB) {
- // We need to split the basic block here to obtain two long-range
- // unconditional branches.
- auto &NewBB = *MF->CreateMachineBasicBlock(MBB->getBasicBlock());
- MF->insert(++MBB->getIterator(), &NewBB);
-
- // Insert an entry into BlockInfo to align it properly with the block
- // numbers.
- BlockInfo.insert(BlockInfo.begin() + NewBB.getNumber(), BasicBlockInfo());
-
- unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size;
- int NewBrSize;
- TII->insertUnconditionalBranch(NewBB, FBB, DL, &NewBrSize);
- NewBBSize += NewBrSize;
-
- // Update the successor lists according to the transformation to follow.
- // Do it here since if there's no split, no update is needed.
- MBB->replaceSuccessor(FBB, &NewBB);
- NewBB.addSuccessor(FBB);
+ bool ReversedCond = !TII->reverseBranchCondition(Cond);
+ if (ReversedCond) {
+ if (FBB && isBlockInRange(MI, *FBB)) {
+ // Last MI in the BB is an unconditional branch. We can simply invert the
+ // condition and swap destinations:
+ // beq L1
+ // b L2
+ // =>
+ // bne L2
+ // b L1
+ LLVM_DEBUG(dbgs() << " Invert condition and swap "
+ "its destination with "
+ << MBB->back());
+
+ removeBranch(MBB);
+ insertBranch(MBB, FBB, TBB, Cond);
+ finalizeBlockChanges(MBB, nullptr);
+ return true;
+ }
+ if (FBB) {
+ // We need to split the basic block here to obtain two long-range
+ // unconditional branches.
+ NewBB = createNewBlockAfter(*MBB);
+
+ insertUncondBranch(NewBB, FBB);
+ // Update the succesor lists according to the transformation to follow.
+ // Do it here since if there's no split, no update is needed.
+ MBB->replaceSuccessor(FBB, NewBB);
+ NewBB->addSuccessor(FBB);
+ }
- // Need to fix live-in lists if we track liveness.
- if (TRI->trackLivenessAfterRegAlloc(*MF))
- computeAndAddLiveIns(LiveRegs, NewBB);
+ // We now have an appropriate fall-through block in place (either naturally or
+ // just created), so we can use the inverted the condition.
+ MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
+
+ LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
+ << ", invert condition and change dest. to "
+ << printMBBReference(NextBB) << '\n');
+
+ removeBranch(MBB);
+ // Insert a new conditional branch and a new unconditional branch.
+ insertBranch(MBB, &NextBB, TBB, Cond);
+
+ finalizeBlockChanges(MBB, NewBB);
+ return true;
}
+ // Branch cond can't be inverted.
+ // In this case we always add a block after the MBB.
+ LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
+ << " Insert a new BB after " << MBB->back());
- // We now have an appropriate fall-through block in place (either naturally or
- // just created), so we can invert the condition.
- MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
+ if (!FBB)
+ FBB = &(*std::next(MachineFunction::iterator(MBB)));
- DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
- << ", invert condition and change dest. to "
- << printMBBReference(NextBB) << '\n');
+ // This is the block with cond. branch and the distance to TBB is too long.
+ // beq L1
+ // L2:
- unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size;
+ // We do the following transformation:
+ // beq NewBB
+ // b L2
+ // NewBB:
+ // b L1
+ // L2:
- // Insert a new conditional branch and a new unconditional branch.
- int RemovedSize = 0;
- TII->reverseBranchCondition(Cond);
- TII->removeBranch(*MBB, &RemovedSize);
- MBBSize -= RemovedSize;
+ NewBB = createNewBlockAfter(*MBB);
+ insertUncondBranch(NewBB, TBB);
- int AddedSize = 0;
- TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize);
- MBBSize += AddedSize;
+ LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
+ << printMBBReference(*NewBB)
+ << " Keep the exiting condition.\n"
+ << " Insert B to " << printMBBReference(*FBB) << ".\n"
+ << " In the new BB: Insert B to "
+ << printMBBReference(*TBB) << ".\n");
- // Finally, keep the block offsets up to date.
- adjustBlockOffsets(*MBB);
+ // Update the successor lists according to the transformation to follow.
+ MBB->replaceSuccessor(TBB, NewBB);
+ NewBB->addSuccessor(TBB);
+
+ // Replace branch in the current (MBB) block.
+ removeBranch(MBB);
+ insertBranch(MBB, NewBB, FBB, Cond);
+
+ finalizeBlockChanges(MBB, NewBB);
return true;
}
@@ -490,7 +544,7 @@ bool BranchRelaxation::relaxBranchInstructions() {
bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
MF = &mf;
- DEBUG(dbgs() << "***** BranchRelaxation *****\n");
+ LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
const TargetSubtargetInfo &ST = MF->getSubtarget();
TII = ST.getInstrInfo();
@@ -507,7 +561,7 @@ bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
// sizes of each block.
scanFunction();
- DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
+ LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
bool MadeChange = false;
while (relaxBranchInstructions())
@@ -516,7 +570,7 @@ bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
// After a while, this might be made debug-only, but it is not expensive.
verify();
- DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
+ LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
BlockInfo.clear();
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-24 23:27:37 +0000