aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm/lib/CodeGen/BranchFolding.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/CodeGen/BranchFolding.cpp')
-rw-r--r--contrib/llvm/lib/CodeGen/BranchFolding.cpp138
1 files changed, 77 insertions, 61 deletions
diff --git a/contrib/llvm/lib/CodeGen/BranchFolding.cpp b/contrib/llvm/lib/CodeGen/BranchFolding.cpp
index 9cd4208d6461..7503e5751994 100644
--- a/contrib/llvm/lib/CodeGen/BranchFolding.cpp
+++ b/contrib/llvm/lib/CodeGen/BranchFolding.cpp
@@ -16,7 +16,6 @@
//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "branchfolding"
#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
@@ -38,6 +37,8 @@
#include <algorithm>
using namespace llvm;
+#define DEBUG_TYPE "branchfolding"
+
STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
STATISTIC(NumBranchOpts, "Number of branches optimized");
STATISTIC(NumTailMerge , "Number of block tails merged");
@@ -66,9 +67,9 @@ namespace {
static char ID;
explicit BranchFolderPass(): MachineFunctionPass(ID) {}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<TargetPassConfig>();
MachineFunctionPass::getAnalysisUsage(AU);
}
@@ -82,8 +83,15 @@ INITIALIZE_PASS(BranchFolderPass, "branch-folder",
"Control Flow Optimizer", false, false)
bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
+ if (skipOptnoneFunction(*MF.getFunction()))
+ return false;
+
TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
- BranchFolder Folder(PassConfig->getEnableTailMerge(), /*CommonHoist=*/true);
+ // TailMerge can create jump into if branches that make CFG irreducible for
+ // HW that requires structurized CFG.
+ bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
+ PassConfig->getEnableTailMerge();
+ BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true);
return Folder.OptimizeFunction(MF,
MF.getTarget().getInstrInfo(),
MF.getTarget().getRegisterInfo(),
@@ -182,7 +190,7 @@ bool BranchFolder::OptimizeFunction(MachineFunction &MF,
TII = tii;
TRI = tri;
MMI = mmi;
- RS = NULL;
+ RS = nullptr;
// Use a RegScavenger to help update liveness when required.
MachineRegisterInfo &MRI = MF.getRegInfo();
@@ -194,7 +202,7 @@ bool BranchFolder::OptimizeFunction(MachineFunction &MF,
// Fix CFG. The later algorithms expect it to be right.
bool MadeChange = false;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
- MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
+ MachineBasicBlock *MBB = I, *TBB = nullptr, *FBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true))
MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
@@ -213,7 +221,7 @@ bool BranchFolder::OptimizeFunction(MachineFunction &MF,
// See if any jump tables have become dead as the code generator
// did its thing.
MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
- if (JTI == 0) {
+ if (!JTI) {
delete RS;
return MadeChange;
}
@@ -379,7 +387,7 @@ void BranchFolder::MaintainLiveIns(MachineBasicBlock *CurMBB,
if (RS) {
RS->enterBasicBlock(CurMBB);
if (!CurMBB->empty())
- RS->forward(prior(CurMBB->end()));
+ RS->forward(std::prev(CurMBB->end()));
BitVector RegsLiveAtExit(TRI->getNumRegs());
RS->getRegsUsed(RegsLiveAtExit, false);
for (unsigned int i = 0, e = TRI->getNumRegs(); i != e; i++)
@@ -409,7 +417,7 @@ MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
MachineBasicBlock::iterator BBI1,
const BasicBlock *BB) {
if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
- return 0;
+ return nullptr;
MachineFunction &MF = *CurMBB.getParent();
@@ -458,8 +466,8 @@ static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
const TargetInstrInfo *TII) {
MachineFunction *MF = CurMBB->getParent();
- MachineFunction::iterator I = llvm::next(MachineFunction::iterator(CurMBB));
- MachineBasicBlock *TBB = 0, *FBB = 0;
+ MachineFunction::iterator I = std::next(MachineFunction::iterator(CurMBB));
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
DebugLoc dl; // FIXME: this is nowhere
if (I != MF->end() &&
@@ -468,12 +476,12 @@ static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
if (TBB == NextBB && !Cond.empty() && !FBB) {
if (!TII->ReverseBranchCondition(Cond)) {
TII->RemoveBranch(*CurMBB);
- TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond, dl);
+ TII->InsertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);
return;
}
}
}
- TII->InsertBranch(*CurMBB, SuccBB, NULL,
+ TII->InsertBranch(*CurMBB, SuccBB, nullptr,
SmallVector<MachineOperand, 0>(), dl);
}
@@ -596,12 +604,11 @@ unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
unsigned maxCommonTailLength = 0U;
SameTails.clear();
MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
- MPIterator HighestMPIter = prior(MergePotentials.end());
- for (MPIterator CurMPIter = prior(MergePotentials.end()),
+ MPIterator HighestMPIter = std::prev(MergePotentials.end());
+ for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
B = MergePotentials.begin();
- CurMPIter != B && CurMPIter->getHash() == CurHash;
- --CurMPIter) {
- for (MPIterator I = prior(CurMPIter); I->getHash() == CurHash ; --I) {
+ CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
+ for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
unsigned CommonTailLen;
if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
minCommonTailLength,
@@ -630,9 +637,9 @@ void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
MachineBasicBlock *SuccBB,
MachineBasicBlock *PredBB) {
MPIterator CurMPIter, B;
- for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin();
- CurMPIter->getHash() == CurHash;
- --CurMPIter) {
+ for (CurMPIter = std::prev(MergePotentials.end()),
+ B = MergePotentials.begin();
+ CurMPIter->getHash() == CurHash; --CurMPIter) {
// Put the unconditional branch back, if we need one.
MachineBasicBlock *CurMBB = CurMPIter->getBlock();
if (SuccBB && CurMBB != PredBB)
@@ -843,7 +850,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
// See if we can do any tail merging on those.
if (MergePotentials.size() >= 2)
- MadeChange |= TryTailMergeBlocks(NULL, NULL);
+ MadeChange |= TryTailMergeBlocks(nullptr, nullptr);
// Look at blocks (IBB) with multiple predecessors (PBB).
// We change each predecessor to a canonical form, by
@@ -864,12 +871,12 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
// a compile-time infinite loop repeatedly doing and undoing the same
// transformations.)
- for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
+ for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
I != E; ++I) {
if (I->pred_size() < 2) continue;
SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
MachineBasicBlock *IBB = I;
- MachineBasicBlock *PredBB = prior(I);
+ MachineBasicBlock *PredBB = std::prev(I);
MergePotentials.clear();
for (MachineBasicBlock::pred_iterator P = I->pred_begin(),
E2 = I->pred_end();
@@ -890,7 +897,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
if (PBB->getLandingPadSuccessor())
continue;
- MachineBasicBlock *TBB = 0, *FBB = 0;
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) {
// Failing case: IBB is the target of a cbr, and we cannot reverse the
@@ -901,7 +908,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
continue;
// This is the QBB case described above
if (!FBB)
- FBB = llvm::next(MachineFunction::iterator(PBB));
+ FBB = std::next(MachineFunction::iterator(PBB));
}
// Failing case: the only way IBB can be reached from PBB is via
@@ -909,10 +916,10 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
// a bit in the edge so we didn't have to do all this.
if (IBB->isLandingPad()) {
MachineFunction::iterator IP = PBB; IP++;
- MachineBasicBlock *PredNextBB = NULL;
+ MachineBasicBlock *PredNextBB = nullptr;
if (IP != MF.end())
PredNextBB = IP;
- if (TBB == NULL) {
+ if (!TBB) {
if (IBB != PredNextBB) // fallthrough
continue;
} else if (FBB) {
@@ -933,7 +940,8 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
TII->RemoveBranch(*PBB);
if (!Cond.empty())
// reinsert conditional branch only, for now
- TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond, dl);
+ TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
+ NewCond, dl);
}
MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB), *P));
@@ -951,7 +959,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
// Reinsert an unconditional branch if needed. The 1 below can occur as a
// result of removing blocks in TryTailMergeBlocks.
- PredBB = prior(I); // this may have been changed in TryTailMergeBlocks
+ PredBB = std::prev(I); // this may have been changed in TryTailMergeBlocks
if (MergePotentials.size() == 1 &&
MergePotentials.begin()->getBlock() != PredBB)
FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
@@ -970,7 +978,7 @@ bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
// Make sure blocks are numbered in order
MF.RenumberBlocks();
- for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
+ for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
I != E; ) {
MachineBasicBlock *MBB = I++;
MadeChange |= OptimizeBlock(MBB);
@@ -1091,9 +1099,9 @@ ReoptimizeBlock:
// Check to see if we can simplify the terminator of the block before this
// one.
- MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
+ MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
- MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
+ MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
SmallVector<MachineOperand, 4> PriorCond;
bool PriorUnAnalyzable =
TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
@@ -1110,7 +1118,7 @@ ReoptimizeBlock:
TII->RemoveBranch(PrevBB);
PriorCond.clear();
if (PriorTBB != MBB)
- TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl);
+ TII->InsertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
@@ -1154,7 +1162,7 @@ ReoptimizeBlock:
// If the previous branch *only* branches to *this* block (conditional or
// not) remove the branch.
- if (PriorTBB == MBB && PriorFBB == 0) {
+ if (PriorTBB == MBB && !PriorFBB) {
TII->RemoveBranch(PrevBB);
MadeChange = true;
++NumBranchOpts;
@@ -1166,7 +1174,7 @@ ReoptimizeBlock:
if (PriorFBB == MBB) {
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
- TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl);
+ TII->InsertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
@@ -1180,7 +1188,7 @@ ReoptimizeBlock:
if (!TII->ReverseBranchCondition(NewPriorCond)) {
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
- TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond, dl);
+ TII->InsertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
@@ -1195,7 +1203,7 @@ ReoptimizeBlock:
// We consider it more likely that execution will stay in the function (e.g.
// due to loops) than it is to exit it. This asserts in loops etc, moving
// the assert condition out of the loop body.
- if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 &&
+ if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
MachineFunction::iterator(PriorTBB) == FallThrough &&
!MBB->canFallThrough()) {
bool DoTransform = true;
@@ -1218,7 +1226,7 @@ ReoptimizeBlock:
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
- TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond, dl);
+ TII->InsertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
// Move this block to the end of the function.
MBB->moveAfter(--MF.end());
@@ -1231,7 +1239,7 @@ ReoptimizeBlock:
}
// Analyze the branch in the current block.
- MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
+ MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
SmallVector<MachineOperand, 4> CurCond;
bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
if (!CurUnAnalyzable) {
@@ -1257,7 +1265,7 @@ ReoptimizeBlock:
// If this branch is the only thing in its block, see if we can forward
// other blocks across it.
- if (CurTBB && CurCond.empty() && CurFBB == 0 &&
+ if (CurTBB && CurCond.empty() && !CurFBB &&
IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
!MBB->hasAddressTaken()) {
DebugLoc dl = getBranchDebugLoc(*MBB);
@@ -1295,12 +1303,12 @@ ReoptimizeBlock:
// explicit branch to us to make updates simpler.
if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
PriorTBB != MBB && PriorFBB != MBB) {
- if (PriorTBB == 0) {
- assert(PriorCond.empty() && PriorFBB == 0 &&
+ if (!PriorTBB) {
+ assert(PriorCond.empty() && !PriorFBB &&
"Bad branch analysis");
PriorTBB = MBB;
} else {
- assert(PriorFBB == 0 && "Machine CFG out of date!");
+ assert(!PriorFBB && "Machine CFG out of date!");
PriorFBB = MBB;
}
DebugLoc pdl = getBranchDebugLoc(PrevBB);
@@ -1324,7 +1332,7 @@ ReoptimizeBlock:
// If this change resulted in PMBB ending in a conditional
// branch where both conditions go to the same destination,
// change this to an unconditional branch (and fix the CFG).
- MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0;
+ MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
SmallVector<MachineOperand, 4> NewCurCond;
bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB,
NewCurFBB, NewCurCond, true);
@@ -1332,10 +1340,10 @@ ReoptimizeBlock:
DebugLoc pdl = getBranchDebugLoc(*PMBB);
TII->RemoveBranch(*PMBB);
NewCurCond.clear();
- TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond, pdl);
+ TII->InsertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
MadeChange = true;
++NumBranchOpts;
- PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false);
+ PMBB->CorrectExtraCFGEdges(NewCurTBB, nullptr, false);
}
}
}
@@ -1352,7 +1360,7 @@ ReoptimizeBlock:
}
// Add the branch back if the block is more than just an uncond branch.
- TII->InsertBranch(*MBB, CurTBB, 0, CurCond, dl);
+ TII->InsertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
}
}
@@ -1373,7 +1381,7 @@ ReoptimizeBlock:
// Analyze the branch at the end of the pred.
MachineBasicBlock *PredBB = *PI;
MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
- MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
+ MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
SmallVector<MachineOperand, 4> PredCond;
if (PredBB != MBB && !PredBB->canFallThrough() &&
!TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)
@@ -1390,9 +1398,10 @@ ReoptimizeBlock:
// B elsewhere
// next:
if (CurFallsThru) {
- MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
+ MachineBasicBlock *NextBB =
+ std::next(MachineFunction::iterator(MBB));
CurCond.clear();
- TII->InsertBranch(*MBB, NextBB, 0, CurCond, DebugLoc());
+ TII->InsertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
}
MBB->moveAfter(PredBB);
MadeChange = true;
@@ -1425,7 +1434,7 @@ ReoptimizeBlock:
// Okay, there is no really great place to put this block. If, however,
// the block before this one would be a fall-through if this block were
// removed, move this block to the end of the function.
- MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0;
+ MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
SmallVector<MachineOperand, 4> PrevCond;
if (FallThrough != MF.end() &&
!TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
@@ -1466,7 +1475,7 @@ static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
if (SuccBB != TrueBB)
return SuccBB;
}
- return NULL;
+ return nullptr;
}
/// findHoistingInsertPosAndDeps - Find the location to move common instructions
@@ -1496,10 +1505,17 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
if (MO.isUse()) {
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
Uses.insert(*AI);
- } else if (!MO.isDead())
- // Don't try to hoist code in the rare case the terminator defines a
- // register that is later used.
- return MBB->end();
+ } else {
+ if (!MO.isDead())
+ // Don't try to hoist code in the rare case the terminator defines a
+ // register that is later used.
+ return MBB->end();
+
+ // If the terminator defines a register, make sure we don't hoist
+ // the instruction whose def might be clobbered by the terminator.
+ for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
+ Defs.insert(*AI);
+ }
}
if (Uses.empty())
@@ -1511,7 +1527,7 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
// branch from condition setting instruction.
MachineBasicBlock::iterator PI = Loc;
--PI;
- while (PI != MBB->begin() && Loc->isDebugValue())
+ while (PI != MBB->begin() && PI->isDebugValue())
--PI;
bool IsDef = false;
@@ -1540,7 +1556,7 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
// Also avoid moving code above predicated instruction since it's hard to
// reason about register liveness with predicated instruction.
bool DontMoveAcrossStore = true;
- if (!PI->isSafeToMove(TII, 0, DontMoveAcrossStore) ||
+ if (!PI->isSafeToMove(TII, nullptr, DontMoveAcrossStore) ||
TII->isPredicated(PI))
return MBB->end();
@@ -1574,7 +1590,7 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
/// sequence at the start of the function, move the instructions before MBB
/// terminator if it's legal.
bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
- MachineBasicBlock *TBB = 0, *FBB = 0;
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
return false;
@@ -1679,7 +1695,7 @@ bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
break;
bool DontMoveAcrossStore = true;
- if (!TIB->isSafeToMove(TII, 0, DontMoveAcrossStore))
+ if (!TIB->isSafeToMove(TII, nullptr, DontMoveAcrossStore))
break;
// Remove kills from LocalDefsSet, these registers had short live ranges.