BranchRelaxation: Support expanding unconditional branches
AMDGPU needs to expand unconditional branches in a new
block with an indirect branch.
llvm-svn: 283464
diff --git a/llvm/lib/CodeGen/BranchRelaxation.cpp b/llvm/lib/CodeGen/BranchRelaxation.cpp
index 4f0dfaf..1d76831 100644
--- a/llvm/lib/CodeGen/BranchRelaxation.cpp
+++ b/llvm/lib/CodeGen/BranchRelaxation.cpp
@@ -11,6 +11,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include "llvm/Support/Debug.h"
@@ -23,6 +24,7 @@
STATISTIC(NumSplit, "Number of basic blocks split");
STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
+STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
#define BRANCH_RELAX_NAME "Branch relaxation pass"
@@ -66,17 +68,22 @@
};
SmallVector<BasicBlockInfo, 16> BlockInfo;
+ std::unique_ptr<RegScavenger> RS;
MachineFunction *MF;
const TargetInstrInfo *TII;
bool relaxBranchInstructions();
void scanFunction();
+
+ MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
+
MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI);
void adjustBlockOffsets(MachineBasicBlock &MBB);
bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
bool fixupConditionalBranch(MachineInstr &MI);
+ bool fixupUnconditionalBranch(MachineInstr &MI);
uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
unsigned getInstrOffset(const MachineInstr &MI) const;
void dumpBBs();
@@ -182,6 +189,19 @@
}
}
+ /// Insert a new empty basic block and insert it after \BB
+MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
+ // Create a new MBB for the code after the OrigBB.
+ MachineBasicBlock *NewBB =
+ MF->CreateMachineBasicBlock(BB.getBasicBlock());
+ MF->insert(++BB.getIterator(), NewBB);
+
+ // Insert an entry into BlockInfo to align it properly with the block numbers.
+ BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
+
+ return NewBB;
+}
+
/// Split the basic block containing MI into two blocks, which are joined by
/// an unconditional branch. Update data structures and renumber blocks to
/// account for this change and returns the newly created block.
@@ -333,16 +353,55 @@
return true;
}
+bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
+ MachineBasicBlock *MBB = MI.getParent();
+
+ unsigned OldBrSize = TII->getInstSizeInBytes(MI);
+ MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
+
+ int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
+ int64_t SrcOffset = getInstrOffset(MI);
+
+ assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
+
+ BlockInfo[MBB->getNumber()].Size -= OldBrSize;
+
+ MachineBasicBlock *BranchBB = MBB;
+
+ // If this was an expanded conditional branch, there is already a single
+ // unconditional branch in a block.
+ if (!MBB->empty()) {
+ BranchBB = createNewBlockAfter(*MBB);
+
+ // Add live outs.
+ for (const MachineBasicBlock *Succ : MBB->successors()) {
+ for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
+ BranchBB->addLiveIn(LiveIn);
+ }
+
+ BranchBB->addSuccessor(DestBB);
+ MBB->replaceSuccessor(DestBB, BranchBB);
+ }
+
+ DebugLoc DL = MI.getDebugLoc();
+ MI.eraseFromParent();
+
+ // insertUnconditonalBranch may have inserted a new block.
+ BlockInfo[MBB->getNumber()].Size += TII->insertIndirectBranch(
+ *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
+
+ computeBlockSize(*BranchBB);
+ adjustBlockOffsets(*MBB);
+ return true;
+}
+
bool BranchRelaxation::relaxBranchInstructions() {
bool Changed = false;
+
// Relaxing branches involves creating new basic blocks, so re-eval
// end() for termination.
for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
MachineBasicBlock &MBB = *I;
- MachineBasicBlock::iterator J = MBB.getFirstTerminator();
- if (J == MBB.end())
- continue;
-
MachineBasicBlock::iterator Next;
for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
@@ -377,6 +436,21 @@
Next = MBB.getFirstTerminator();
}
}
+
+ if (MI.isUnconditionalBranch()) {
+ // Unconditional branch destination might be unanalyzable, assume these
+ // are OK.
+ if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI)) {
+ if (!isBlockInRange(MI, *DestBB)) {
+ fixupUnconditionalBranch(MI);
+ ++NumUnconditionalRelaxed;
+ Changed = true;
+ }
+ }
+
+ // Unconditional branch is the last terminator.
+ break;
+ }
}
}
@@ -388,7 +462,12 @@
DEBUG(dbgs() << "***** BranchRelaxation *****\n");
- TII = MF->getSubtarget().getInstrInfo();
+ const TargetSubtargetInfo &ST = MF->getSubtarget();
+ TII = ST.getInstrInfo();
+
+ const TargetRegisterInfo *TRI = ST.getRegisterInfo();
+ if (TRI->trackLivenessAfterRegAlloc(*MF))
+ RS.reset(new RegScavenger());
// Renumber all of the machine basic blocks in the function, guaranteeing that
// the numbers agree with the position of the block in the function.