summaryrefslogtreecommitdiff
path: root/lib/CodeGen/BranchFolding.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/BranchFolding.cpp')
-rw-r--r--lib/CodeGen/BranchFolding.cpp205
1 files changed, 126 insertions, 79 deletions
diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp
index 3c439e66944b..7f358a679366 100644
--- a/lib/CodeGen/BranchFolding.cpp
+++ b/lib/CodeGen/BranchFolding.cpp
@@ -19,27 +19,35 @@
#include "BranchFolding.h"
#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
#include "llvm/CodeGen/Analysis.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/CodeGen/TargetRegisterInfo.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
+#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
@@ -48,10 +56,7 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Target/TargetSubtargetInfo.h"
#include <cassert>
#include <cstddef>
#include <iterator>
@@ -81,8 +86,8 @@ TailMergeThreshold("tail-merge-threshold",
// TODO: This should be replaced with a target query.
static cl::opt<unsigned>
TailMergeSize("tail-merge-size",
- cl::desc("Min number of instructions to consider tail merging"),
- cl::init(3), cl::Hidden);
+ cl::desc("Min number of instructions to consider tail merging"),
+ cl::init(3), cl::Hidden);
namespace {
@@ -106,13 +111,14 @@ namespace {
} // end anonymous namespace
char BranchFolderPass::ID = 0;
+
char &llvm::BranchFolderPassID = BranchFolderPass::ID;
INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE,
"Control Flow Optimizer", false, false)
bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
- if (skipFunction(*MF.getFunction()))
+ if (skipFunction(MF.getFunction()))
return false;
TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
@@ -365,15 +371,37 @@ static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
return TailLen;
}
-void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
- MachineBasicBlock *NewDest) {
- TII->ReplaceTailWithBranchTo(OldInst, NewDest);
-
+void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
+ MachineBasicBlock &NewDest) {
if (UpdateLiveIns) {
- NewDest->clearLiveIns();
- computeLiveIns(LiveRegs, *MRI, *NewDest);
+ // OldInst should always point to an instruction.
+ MachineBasicBlock &OldMBB = *OldInst->getParent();
+ LiveRegs.clear();
+ LiveRegs.addLiveOuts(OldMBB);
+ // Move backward to the place where will insert the jump.
+ MachineBasicBlock::iterator I = OldMBB.end();
+ do {
+ --I;
+ LiveRegs.stepBackward(*I);
+ } while (I != OldInst);
+
+ // Merging the tails may have switched some undef operand to non-undef ones.
+ // Add IMPLICIT_DEFS into OldMBB as necessary to have a definition of the
+ // register.
+ for (MachineBasicBlock::RegisterMaskPair P : NewDest.liveins()) {
+ // We computed the liveins with computeLiveIn earlier and should only see
+ // full registers:
+ assert(P.LaneMask == LaneBitmask::getAll() &&
+ "Can only handle full register.");
+ MCPhysReg Reg = P.PhysReg;
+ if (!LiveRegs.available(*MRI, Reg))
+ continue;
+ DebugLoc DL;
+ BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
+ }
}
+ TII->ReplaceTailWithBranchTo(OldInst, &NewDest);
++NumTailMerge;
}
@@ -408,7 +436,7 @@ MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
if (UpdateLiveIns)
- computeLiveIns(LiveRegs, *MRI, *NewMBB);
+ computeAndAddLiveIns(LiveRegs, *NewMBB);
// Add the new block to the funclet.
const auto &FuncletI = FuncletMembership.find(&CurMBB);
@@ -585,8 +613,8 @@ ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
if (CommonTailLen == 0)
return false;
- DEBUG(dbgs() << "Common tail length of BB#" << MBB1->getNumber()
- << " and BB#" << MBB2->getNumber() << " is " << CommonTailLen
+ DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)
+ << " and " << printMBBReference(*MBB2) << " is " << CommonTailLen
<< '\n');
// It's almost always profitable to merge any number of non-terminator
@@ -657,7 +685,7 @@ ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
// branch instruction, which is likely to be smaller than the 2
// instructions that would be deleted in the merge.
MachineFunction *MF = MBB1->getParent();
- return EffectiveTailLen >= 2 && MF->getFunction()->optForSize() &&
+ return EffectiveTailLen >= 2 && MF->getFunction().optForSize() &&
(I1 == MBB1->begin() || I2 == MBB2->begin());
}
@@ -742,7 +770,7 @@ bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
SameTails[commonTailIndex].getTailStartPos();
MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
- DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size "
+ DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "
<< maxCommonTailLength);
// If the split block unconditionally falls-thru to SuccBB, it will be
@@ -766,43 +794,6 @@ bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
return true;
}
-void BranchFolder::MergeCommonTailDebugLocs(unsigned commonTailIndex) {
- MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
-
- std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
- for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
- if (i != commonTailIndex)
- NextCommonInsts[i] = SameTails[i].getTailStartPos();
- else {
- assert(SameTails[i].getTailStartPos() == MBB->begin() &&
- "MBB is not a common tail only block");
- }
- }
-
- for (auto &MI : *MBB) {
- if (MI.isDebugValue())
- continue;
- DebugLoc DL = MI.getDebugLoc();
- for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
- if (i == commonTailIndex)
- continue;
-
- auto &Pos = NextCommonInsts[i];
- assert(Pos != SameTails[i].getBlock()->end() &&
- "Reached BB end within common tail");
- while (Pos->isDebugValue()) {
- ++Pos;
- assert(Pos != SameTails[i].getBlock()->end() &&
- "Reached BB end within common tail");
- }
- assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
- DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
- NextCommonInsts[i] = ++Pos;
- }
- MI.setDebugLoc(DL);
- }
-}
-
static void
mergeOperations(MachineBasicBlock::iterator MBBIStartPos,
MachineBasicBlock &MBBCommon) {
@@ -853,6 +844,67 @@ mergeOperations(MachineBasicBlock::iterator MBBIStartPos,
}
}
+void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
+ MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
+
+ std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
+ for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
+ if (i != commonTailIndex) {
+ NextCommonInsts[i] = SameTails[i].getTailStartPos();
+ mergeOperations(SameTails[i].getTailStartPos(), *MBB);
+ } else {
+ assert(SameTails[i].getTailStartPos() == MBB->begin() &&
+ "MBB is not a common tail only block");
+ }
+ }
+
+ for (auto &MI : *MBB) {
+ if (MI.isDebugValue())
+ continue;
+ DebugLoc DL = MI.getDebugLoc();
+ for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
+ if (i == commonTailIndex)
+ continue;
+
+ auto &Pos = NextCommonInsts[i];
+ assert(Pos != SameTails[i].getBlock()->end() &&
+ "Reached BB end within common tail");
+ while (Pos->isDebugValue()) {
+ ++Pos;
+ assert(Pos != SameTails[i].getBlock()->end() &&
+ "Reached BB end within common tail");
+ }
+ assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
+ DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
+ NextCommonInsts[i] = ++Pos;
+ }
+ MI.setDebugLoc(DL);
+ }
+
+ if (UpdateLiveIns) {
+ LivePhysRegs NewLiveIns(*TRI);
+ computeLiveIns(NewLiveIns, *MBB);
+
+ // The flag merging may lead to some register uses no longer using the
+ // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
+ for (MachineBasicBlock *Pred : MBB->predecessors()) {
+ LiveRegs.init(*TRI);
+ LiveRegs.addLiveOuts(*Pred);
+ MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
+ for (unsigned Reg : NewLiveIns) {
+ if (!LiveRegs.available(*MRI, Reg))
+ continue;
+ DebugLoc DL;
+ BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
+ Reg);
+ }
+ }
+
+ MBB->clearLiveIns();
+ addLiveIns(*MBB, NewLiveIns);
+ }
+}
+
// See if any of the blocks in MergePotentials (which all have SuccBB as a
// successor, or all have no successor if it is null) can be tail-merged.
// If there is a successor, any blocks in MergePotentials that are not
@@ -868,20 +920,17 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
bool MadeChange = false;
DEBUG(dbgs() << "\nTryTailMergeBlocks: ";
- for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
- dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber()
- << (i == e-1 ? "" : ", ");
- dbgs() << "\n";
- if (SuccBB) {
- dbgs() << " with successor BB#" << SuccBB->getNumber() << '\n';
+ for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
+ << printMBBReference(*MergePotentials[i].getBlock())
+ << (i == e - 1 ? "" : ", ");
+ dbgs() << "\n"; if (SuccBB) {
+ dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
if (PredBB)
- dbgs() << " which has fall-through from BB#"
- << PredBB->getNumber() << "\n";
- }
- dbgs() << "Looking for common tails of at least "
- << MinCommonTailLength << " instruction"
- << (MinCommonTailLength == 1 ? "" : "s") << '\n';
- );
+ dbgs() << " which has fall-through from "
+ << printMBBReference(*PredBB) << "\n";
+ } dbgs() << "Looking for common tails of at least "
+ << MinCommonTailLength << " instruction"
+ << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
// Sort by hash value so that blocks with identical end sequences sort
// together.
@@ -955,22 +1004,21 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
// Recompute common tail MBB's edge weights and block frequency.
setCommonTailEdgeWeights(*MBB);
- // Merge debug locations across identical instructions for common tail.
- MergeCommonTailDebugLocs(commonTailIndex);
+ // Merge debug locations, MMOs and undef flags across identical instructions
+ // for common tail.
+ mergeCommonTails(commonTailIndex);
// MBB is common tail. Adjust all other BB's to jump to this one.
// Traversal must be forwards so erases work.
- DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber()
+ DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
<< " for ");
for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
if (commonTailIndex == i)
continue;
- DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber()
- << (i == e-1 ? "" : ", "));
- // Merge operations (MMOs, undef flags)
- mergeOperations(SameTails[i].getTailStartPos(), *MBB);
+ DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
+ << (i == e - 1 ? "" : ", "));
// Hack the end off BB i, making it jump to BB commonTailIndex instead.
- ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
+ replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
// BB i is no longer a predecessor of SuccBB; remove it from the worklist.
MergePotentials.erase(SameTails[i].getMPIter());
}
@@ -1463,7 +1511,7 @@ ReoptimizeBlock:
}
if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 &&
- MF.getFunction()->optForSize()) {
+ MF.getFunction().optForSize()) {
// Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch
// direction, thereby defeating careful block placement and regressing
// performance. Therefore, only consider this for optsize functions.
@@ -1819,7 +1867,6 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
return MBB->end();
-
// Find out what registers are live. Note this routine is ignoring other live
// registers which are only used by instructions in successor blocks.
for (const MachineOperand &MO : PI->operands()) {
@@ -1921,7 +1968,7 @@ bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
//
// BB2:
// r1 = op2, ...
- // = op3, r1<kill>
+ // = op3, killed r1
IsSafe = false;
break;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 11:19:02 +0000