#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
static cl::opt<unsigned>
TailMergeThreshold("tail-merge-threshold",
cl::desc("Max number of predecessors to consider tail merging"),
- cl::init(100), cl::Hidden);
+ cl::init(150), cl::Hidden);
namespace {
struct VISIBILITY_HIDDEN BranchFolder : public MachineFunctionPass {
static char ID;
explicit BranchFolder(bool defaultEnableTailMerge) :
- MachineFunctionPass((intptr_t)&ID) {
- switch (FlagEnableTailMerge) {
- case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
- case cl::BOU_TRUE: EnableTailMerge = true; break;
- case cl::BOU_FALSE: EnableTailMerge = false; break;
- }
+ MachineFunctionPass(&ID) {
+ switch (FlagEnableTailMerge) {
+ case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
+ case cl::BOU_TRUE: EnableTailMerge = true; break;
+ case cl::BOU_FALSE: EnableTailMerge = false; break;
+ }
}
virtual bool runOnMachineFunction(MachineFunction &MF);
bool CanFallThrough(MachineBasicBlock *CurBB);
bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
MachineBasicBlock *TBB, MachineBasicBlock *FBB,
- const std::vector<MachineOperand> &Cond);
+ const SmallVectorImpl<MachineOperand> &Cond);
};
char BranchFolder::ID = 0;
}
while (!MBB->succ_empty())
MBB->removeSuccessor(MBB->succ_end()-1);
- // If there is DWARF info to active, check to see if there are any DBG_LABEL
- // records in the basic block. If so, unregister them from MachineModuleInfo.
+ // If there are any labels in the basic block, unregister them from
+ // MachineModuleInfo.
if (MMI && !MBB->empty()) {
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
- if ((unsigned)I->getOpcode() == TargetInstrInfo::DBG_LABEL) {
+ if (I->isLabel())
// The label ID # is always operand #0, an immediate.
MMI->InvalidateLabel(I->getOperand(0).getImm());
- }
}
}
// Remove the block.
- MF->getBasicBlockList().erase(MBB);
+ MF->erase(MBB);
}
/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
bool EverMadeChange = false;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
- std::vector<MachineOperand> Cond;
- if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
+ SmallVector<MachineOperand, 4> Cond;
+ if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true))
EverMadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
EverMadeChange |= OptimizeImpDefsBlock(MBB);
}
RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL;
- MMI = getAnalysisToUpdate<MachineModuleInfo>();
+ MMI = getAnalysisIfAvailable<MachineModuleInfo>();
bool MadeChangeThisIteration = true;
while (MadeChangeThisIteration) {
I != E; ++I)
for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
MachineOperand &Op = I->getOperand(op);
- if (!Op.isJumpTableIndex()) continue;
+ if (!Op.isJTI()) continue;
unsigned NewIdx = JTMapping[Op.getIndex()];
Op.setIndex(NewIdx);
// If OldBB isn't immediately before OldBB, insert a branch to it.
if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
- TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>());
+ TII->InsertBranch(*OldBB, NewDest, 0, SmallVector<MachineOperand, 0>());
OldBB->addSuccessor(NewDest);
++NumTailMerge;
}
/// iterator. This returns the new MBB.
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
MachineBasicBlock::iterator BBI1) {
+ MachineFunction &MF = *CurMBB.getParent();
+
// Create the fall-through block.
MachineFunction::iterator MBBI = &CurMBB;
- MachineBasicBlock *NewMBB = new MachineBasicBlock(CurMBB.getBasicBlock());
- CurMBB.getParent()->getBasicBlockList().insert(++MBBI, NewMBB);
+ MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock());
+ CurMBB.getParent()->insert(++MBBI, NewMBB);
// Move all the successors of this block to the specified block.
NewMBB->transferSuccessors(&CurMBB);
const TargetInstrDesc &TID = I->getDesc();
if (TID.isCall())
Time += 10;
- else if (TID.isSimpleLoad() || TID.mayStore())
+ else if (TID.mayLoad() || TID.mayStore())
Time += 2;
else
++Time;
MachineFunction *MF = CurMBB->getParent();
MachineFunction::iterator I = next(MachineFunction::iterator(CurMBB));
MachineBasicBlock *TBB = 0, *FBB = 0;
- std::vector<MachineOperand> Cond;
+ SmallVector<MachineOperand, 4> Cond;
if (I != MF->end() &&
- !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond)) {
+ !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
MachineBasicBlock *NextBB = I;
if (TBB == NextBB && !Cond.empty() && !FBB) {
if (!TII->ReverseBranchCondition(Cond)) {
}
}
}
- TII->InsertBranch(*CurMBB, SuccBB, NULL, std::vector<MachineOperand>());
+ TII->InsertBranch(*CurMBB, SuccBB, NULL, SmallVector<MachineOperand, 0>());
}
static bool MergeCompare(const std::pair<unsigned,MachineBasicBlock*> &p,
// _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
// an object with itself.
#ifndef _GLIBCXX_DEBUG
- assert(0 && "Predecessor appears twice");
+ llvm_unreachable("Predecessor appears twice");
#endif
- return(false);
+ return false;
}
}
unsigned minCommonTailLength = (SuccBB ? 1 : 2) + 1;
MadeChange = false;
- DOUT << "\nTryMergeBlocks " << MergePotentials.size();
+ DOUT << "\nTryMergeBlocks " << MergePotentials.size() << '\n';
// Sort by hash value so that blocks with identical end sequences sort
// together.
if (PBB==IBB)
continue;
MachineBasicBlock *TBB = 0, *FBB = 0;
- std::vector<MachineOperand> Cond;
- if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond)) {
+ 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 branch.
- std::vector<MachineOperand> NewCond(Cond);
+ SmallVector<MachineOperand, 4> NewCond(Cond);
if (!Cond.empty() && TBB==IBB) {
if (TII->ReverseBranchCondition(NewCond))
continue;
bool BranchUnAnalyzable,
MachineBasicBlock *TBB,
MachineBasicBlock *FBB,
- const std::vector<MachineOperand> &Cond) {
+ const SmallVectorImpl<MachineOperand> &Cond) {
MachineFunction::iterator Fallthrough = CurBB;
++Fallthrough;
// If FallthroughBlock is off the end of the function, it can't fall through.
///
bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) {
MachineBasicBlock *TBB = 0, *FBB = 0;
- std::vector<MachineOperand> Cond;
- bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond);
+ SmallVector<MachineOperand, 4> Cond;
+ bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond, true);
return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond);
}
+/// RemoveDuplicateSuccessor - make sure block Pred has at most one
+/// successor edge leading to Succ. This is only called in one place,
+/// but Chris prefers that it be a separate function.
+static void RemoveDuplicateSuccessor(MachineBasicBlock *Pred,
+ MachineBasicBlock *Succ) {
+ MachineBasicBlock::succ_iterator SI = Pred->succ_begin();
+ bool found = false;
+ while (SI != Pred->succ_end()) {
+ if (*SI == Succ) {
+ if (!found) {
+ found = true;
+ ++SI;
+ } else {
+ SI = Pred->removeSuccessor(SI);
+ }
+ } else {
+ ++SI;
+ }
+ }
+}
+
/// IsBetterFallthrough - Return true if it would be clearly better to
/// fall-through to MBB1 than to fall through into MBB2. This has to return
/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
while (!MBB->pred_empty()) {
MachineBasicBlock *Pred = *(MBB->pred_end()-1);
Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
+ // If this resulted in a predecessor with true and false edges
+ // both going to the fallthrough block, clean up;
+ // BranchFolding doesn't like this.
+ RemoveDuplicateSuccessor(Pred, FallThrough);
}
-
// If MBB was the target of a jump table, update jump tables to go to the
// fallthrough instead.
MBB->getParent()->getJumpTableInfo()->
MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
- std::vector<MachineOperand> PriorCond;
+ SmallVector<MachineOperand, 4> PriorCond;
bool PriorUnAnalyzable =
- TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
+ TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
if (!PriorUnAnalyzable) {
// If the CFG for the prior block has extra edges, remove them.
MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
// if the branch condition is reversible, reverse the branch to create a
// fall-through.
if (PriorTBB == MBB) {
- std::vector<MachineOperand> NewPriorCond(PriorCond);
+ SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
if (!TII->ReverseBranchCondition(NewPriorCond)) {
TII->RemoveBranch(PrevBB);
TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond);
if (DoTransform) {
// Reverse the branch so we will fall through on the previous true cond.
- std::vector<MachineOperand> NewPriorCond(PriorCond);
+ SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
if (!TII->ReverseBranchCondition(NewPriorCond)) {
DOUT << "\nMoving MBB: " << *MBB;
DOUT << "To make fallthrough to: " << *PriorTBB << "\n";
// Analyze the branch in the current block.
MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
- std::vector<MachineOperand> CurCond;
- bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond);
+ SmallVector<MachineOperand, 4> CurCond;
+ bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
if (!CurUnAnalyzable) {
// If the CFG for the prior block has extra edges, remove them.
MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());
// we want:
// Loop: xxx; jncc Loop; jmp Out
if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
- std::vector<MachineOperand> NewCond(CurCond);
+ SmallVector<MachineOperand, 4> NewCond(CurCond);
if (!TII->ReverseBranchCondition(NewCond)) {
TII->RemoveBranch(*MBB);
TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond);
} else {
DidChange = true;
PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
+ // 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;
+ SmallVector<MachineOperand, 4> NewCurCond;
+ bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB,
+ NewCurFBB, NewCurCond, true);
+ if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
+ TII->RemoveBranch(*PMBB);
+ NewCurCond.clear();
+ TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond);
+ MadeChange = true;
+ ++NumBranchOpts;
+ PMBB->CorrectExtraCFGEdges(NewCurTBB, NewCurFBB, false);
+ }
}
}