#define DEBUG_TYPE "branchfolding"
#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/CommandLine.h"
#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 <algorithm>
using namespace llvm;
STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
STATISTIC(NumBranchOpts, "Number of branches optimized");
STATISTIC(NumTailMerge , "Number of block tails merged");
STATISTIC(NumHoist , "Number of times common instructions are hoisted");
static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
cl::init(cl::BOU_UNSET), cl::Hidden);
static cl::opt<unsigned>
TailMergeThreshold("tail-merge-threshold",
cl::desc("Max number of predecessors to consider tail merging"),
cl::init(150), cl::Hidden);
static cl::opt<unsigned>
TailMergeSize("tail-merge-size",
cl::desc("Min number of instructions to consider tail merging"),
cl::init(3), cl::Hidden);
namespace {
class BranchFolderPass : public MachineFunctionPass {
public:
static char ID;
explicit BranchFolderPass(): MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<TargetPassConfig>();
MachineFunctionPass::getAnalysisUsage(AU);
}
};
}
char BranchFolderPass::ID = 0;
char &llvm::BranchFolderPassID = BranchFolderPass::ID;
INITIALIZE_PASS(BranchFolderPass, "branch-folder",
"Control Flow Optimizer", false, false)
bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
BranchFolder Folder(PassConfig->getEnableTailMerge(), true);
return Folder.OptimizeFunction(MF,
MF.getTarget().getInstrInfo(),
MF.getTarget().getRegisterInfo(),
getAnalysisIfAvailable<MachineModuleInfo>());
}
BranchFolder::BranchFolder(bool defaultEnableTailMerge, bool CommonHoist) {
switch (FlagEnableTailMerge) {
case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
case cl::BOU_TRUE: EnableTailMerge = true; break;
case cl::BOU_FALSE: EnableTailMerge = false; break;
}
EnableHoistCommonCode = CommonHoist;
}
void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
assert(MBB->pred_empty() && "MBB must be dead!");
DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
MachineFunction *MF = MBB->getParent();
while (!MBB->succ_empty())
MBB->removeSuccessor(MBB->succ_end()-1);
TriedMerging.erase(MBB);
MF->erase(MBB);
}
bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) {
SmallSet<unsigned, 4> ImpDefRegs;
MachineBasicBlock::iterator I = MBB->begin();
while (I != MBB->end()) {
if (!I->isImplicitDef())
break;
unsigned Reg = I->getOperand(0).getReg();
ImpDefRegs.insert(Reg);
for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
ImpDefRegs.insert(*SubRegs);
++I;
}
if (ImpDefRegs.empty())
return false;
MachineBasicBlock::iterator FirstTerm = I;
while (I != MBB->end()) {
if (!TII->isUnpredicatedTerminator(I))
return false;
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
MachineOperand &MO = I->getOperand(i);
if (!MO.isReg() || !MO.isUse())
continue;
unsigned Reg = MO.getReg();
if (ImpDefRegs.count(Reg))
return false;
}
++I;
}
I = MBB->begin();
while (I != FirstTerm) {
MachineInstr *ImpDefMI = &*I;
++I;
MBB->erase(ImpDefMI);
}
return true;
}
bool BranchFolder::OptimizeFunction(MachineFunction &MF,
const TargetInstrInfo *tii,
const TargetRegisterInfo *tri,
MachineModuleInfo *mmi) {
if (!tii) return false;
TriedMerging.clear();
TII = tii;
TRI = tri;
MMI = mmi;
RS = NULL;
MachineRegisterInfo &MRI = MF.getRegInfo();
if (MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF))
RS = new RegScavenger();
else
MRI.invalidateLiveness();
bool MadeChange = false;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true))
MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
MadeChange |= OptimizeImpDefsBlock(MBB);
}
bool MadeChangeThisIteration = true;
while (MadeChangeThisIteration) {
MadeChangeThisIteration = TailMergeBlocks(MF);
MadeChangeThisIteration |= OptimizeBranches(MF);
if (EnableHoistCommonCode)
MadeChangeThisIteration |= HoistCommonCode(MF);
MadeChange |= MadeChangeThisIteration;
}
MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
if (JTI == 0) {
delete RS;
return MadeChange;
}
BitVector JTIsLive(JTI->getJumpTables().size());
for (MachineFunction::iterator BB = MF.begin(), E = MF.end();
BB != E; ++BB) {
for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
I != E; ++I)
for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
MachineOperand &Op = I->getOperand(op);
if (!Op.isJTI()) continue;
JTIsLive.set(Op.getIndex());
}
}
for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
if (!JTIsLive.test(i)) {
JTI->RemoveJumpTable(i);
MadeChange = true;
}
delete RS;
return MadeChange;
}
static unsigned HashMachineInstr(const MachineInstr *MI) {
unsigned Hash = MI->getOpcode();
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &Op = MI->getOperand(i);
unsigned OperandHash = 0;
switch (Op.getType()) {
case MachineOperand::MO_Register: OperandHash = Op.getReg(); break;
case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break;
case MachineOperand::MO_MachineBasicBlock:
OperandHash = Op.getMBB()->getNumber();
break;
case MachineOperand::MO_FrameIndex:
case MachineOperand::MO_ConstantPoolIndex:
case MachineOperand::MO_JumpTableIndex:
OperandHash = Op.getIndex();
break;
case MachineOperand::MO_GlobalAddress:
case MachineOperand::MO_ExternalSymbol:
OperandHash = Op.getOffset();
break;
default: break;
}
Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
}
return Hash;
}
static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) {
MachineBasicBlock::const_iterator I = MBB->end();
if (I == MBB->begin())
return 0;
--I;
while (I->isDebugValue()) {
if (I==MBB->begin())
return 0; --I;
}
return HashMachineInstr(I);
}
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
MachineBasicBlock *MBB2,
MachineBasicBlock::iterator &I1,
MachineBasicBlock::iterator &I2) {
I1 = MBB1->end();
I2 = MBB2->end();
unsigned TailLen = 0;
while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
--I1; --I2;
while (I1->isDebugValue()) {
if (I1==MBB1->begin()) {
while (I2->isDebugValue()) {
if (I2==MBB2->begin())
return TailLen;
--I2;
}
++I2;
return TailLen;
}
--I1;
}
while (I2->isDebugValue()) {
if (I2==MBB2->begin()) {
++I1;
return TailLen;
}
--I2;
}
if (!I1->isIdenticalTo(I2) ||
I1->isInlineAsm()) {
++I1; ++I2;
break;
}
++TailLen;
}
if (I1 == MBB1->begin() && I2 != MBB2->begin()) {
--I2;
while (I2->isDebugValue()) {
if (I2 == MBB2->begin())
return TailLen;
--I2;
}
++I2;
}
if (I2 == MBB2->begin() && I1 != MBB1->begin()) {
--I1;
while (I1->isDebugValue()) {
if (I1 == MBB1->begin())
return TailLen;
--I1;
}
++I1;
}
return TailLen;
}
void BranchFolder::MaintainLiveIns(MachineBasicBlock *CurMBB,
MachineBasicBlock *NewMBB) {
if (RS) {
RS->enterBasicBlock(CurMBB);
if (!CurMBB->empty())
RS->forward(prior(CurMBB->end()));
BitVector RegsLiveAtExit(TRI->getNumRegs());
RS->getRegsUsed(RegsLiveAtExit, false);
for (unsigned int i = 0, e = TRI->getNumRegs(); i != e; i++)
if (RegsLiveAtExit[i])
NewMBB->addLiveIn(i);
}
}
void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
MachineBasicBlock *NewDest) {
MachineBasicBlock *CurMBB = OldInst->getParent();
TII->ReplaceTailWithBranchTo(OldInst, NewDest);
MaintainLiveIns(CurMBB, NewDest);
++NumTailMerge;
}
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
MachineBasicBlock::iterator BBI1) {
if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
return 0;
MachineFunction &MF = *CurMBB.getParent();
MachineFunction::iterator MBBI = &CurMBB;
MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock());
CurMBB.getParent()->insert(++MBBI, NewMBB);
NewMBB->transferSuccessors(&CurMBB);
CurMBB.addSuccessor(NewMBB);
NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
MaintainLiveIns(&CurMBB, NewMBB);
return NewMBB;
}
static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
MachineBasicBlock::iterator E) {
unsigned Time = 0;
for (; I != E; ++I) {
if (I->isDebugValue())
continue;
if (I->isCall())
Time += 10;
else if (I->mayLoad() || I->mayStore())
Time += 2;
else
++Time;
}
return Time;
}
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;
SmallVector<MachineOperand, 4> Cond;
DebugLoc dl; if (I != MF->end() &&
!TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
MachineBasicBlock *NextBB = I;
if (TBB == NextBB && !Cond.empty() && !FBB) {
if (!TII->ReverseBranchCondition(Cond)) {
TII->RemoveBranch(*CurMBB);
TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond, dl);
return;
}
}
}
TII->InsertBranch(*CurMBB, SuccBB, NULL,
SmallVector<MachineOperand, 0>(), dl);
}
bool
BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
if (getHash() < o.getHash())
return true;
if (getHash() > o.getHash())
return false;
if (getBlock()->getNumber() < o.getBlock()->getNumber())
return true;
if (getBlock()->getNumber() > o.getBlock()->getNumber())
return false;
#ifndef _GLIBCXX_DEBUG
llvm_unreachable("Predecessor appears twice");
#else
return false;
#endif
}
static unsigned CountTerminators(MachineBasicBlock *MBB,
MachineBasicBlock::iterator &I) {
I = MBB->end();
unsigned NumTerms = 0;
for (;;) {
if (I == MBB->begin()) {
I = MBB->end();
break;
}
--I;
if (!I->isTerminator()) break;
++NumTerms;
}
return NumTerms;
}
static bool ProfitableToMerge(MachineBasicBlock *MBB1,
MachineBasicBlock *MBB2,
unsigned minCommonTailLength,
unsigned &CommonTailLen,
MachineBasicBlock::iterator &I1,
MachineBasicBlock::iterator &I2,
MachineBasicBlock *SuccBB,
MachineBasicBlock *PredBB) {
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
<< '\n');
if (MBB1 == PredBB || MBB2 == PredBB) {
MachineBasicBlock::iterator I;
unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
if (CommonTailLen > NumTerms)
return true;
}
if (MBB1->isLayoutSuccessor(MBB2) && I2 == MBB2->begin())
return true;
if (MBB2->isLayoutSuccessor(MBB1) && I1 == MBB1->begin())
return true;
unsigned EffectiveTailLen = CommonTailLen;
if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
!MBB1->back().isBarrier() &&
!MBB2->back().isBarrier())
++EffectiveTailLen;
if (EffectiveTailLen >= minCommonTailLength)
return true;
MachineFunction *MF = MBB1->getParent();
if (EffectiveTailLen >= 2 &&
MF->getFunction()->getAttributes().
hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize) &&
(I1 == MBB1->begin() || I2 == MBB2->begin()))
return true;
return false;
}
unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
unsigned minCommonTailLength,
MachineBasicBlock *SuccBB,
MachineBasicBlock *PredBB) {
unsigned maxCommonTailLength = 0U;
SameTails.clear();
MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
MPIterator HighestMPIter = prior(MergePotentials.end());
for (MPIterator CurMPIter = prior(MergePotentials.end()),
B = MergePotentials.begin();
CurMPIter != B && CurMPIter->getHash() == CurHash;
--CurMPIter) {
for (MPIterator I = prior(CurMPIter); I->getHash() == CurHash ; --I) {
unsigned CommonTailLen;
if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
minCommonTailLength,
CommonTailLen, TrialBBI1, TrialBBI2,
SuccBB, PredBB)) {
if (CommonTailLen > maxCommonTailLength) {
SameTails.clear();
maxCommonTailLength = CommonTailLen;
HighestMPIter = CurMPIter;
SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
}
if (HighestMPIter == CurMPIter &&
CommonTailLen == maxCommonTailLength)
SameTails.push_back(SameTailElt(I, TrialBBI2));
}
if (I == B)
break;
}
}
return maxCommonTailLength;
}
void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
MachineBasicBlock *SuccBB,
MachineBasicBlock *PredBB) {
MPIterator CurMPIter, B;
for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin();
CurMPIter->getHash() == CurHash;
--CurMPIter) {
MachineBasicBlock *CurMBB = CurMPIter->getBlock();
if (SuccBB && CurMBB != PredBB)
FixTail(CurMBB, SuccBB, TII);
if (CurMPIter == B)
break;
}
if (CurMPIter->getHash() != CurHash)
CurMPIter++;
MergePotentials.erase(CurMPIter, MergePotentials.end());
}
bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
unsigned maxCommonTailLength,
unsigned &commonTailIndex) {
commonTailIndex = 0;
unsigned TimeEstimate = ~0U;
for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
if (SameTails[i].getBlock() == PredBB) {
commonTailIndex = i;
break;
}
unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
SameTails[i].getTailStartPos());
if (t <= TimeEstimate) {
TimeEstimate = t;
commonTailIndex = i;
}
}
MachineBasicBlock::iterator BBI =
SameTails[commonTailIndex].getTailStartPos();
MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size "
<< maxCommonTailLength);
MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
if (!newMBB) {
DEBUG(dbgs() << "... failed!");
return false;
}
SameTails[commonTailIndex].setBlock(newMBB);
SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
if (PredBB == MBB)
PredBB = newMBB;
return true;
}
bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
MachineBasicBlock *PredBB) {
bool MadeChange = false;
unsigned minCommonTailLength = TailMergeSize;
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';
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';
);
std::stable_sort(MergePotentials.begin(), MergePotentials.end());
while (MergePotentials.size() > 1) {
unsigned CurHash = MergePotentials.back().getHash();
unsigned maxCommonTailLength = ComputeSameTails(CurHash,
minCommonTailLength,
SuccBB, PredBB);
if (SameTails.empty()) {
RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
continue;
}
MachineBasicBlock *EntryBB = MergePotentials.begin()->getBlock()->
getParent()->begin();
unsigned commonTailIndex = SameTails.size();
if (SameTails.size() == 2 &&
SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
SameTails[1].tailIsWholeBlock())
commonTailIndex = 1;
else if (SameTails.size() == 2 &&
SameTails[1].getBlock()->isLayoutSuccessor(
SameTails[0].getBlock()) &&
SameTails[0].tailIsWholeBlock())
commonTailIndex = 0;
else {
for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
MachineBasicBlock *MBB = SameTails[i].getBlock();
if (MBB == EntryBB && SameTails[i].tailIsWholeBlock())
continue;
if (MBB == PredBB) {
commonTailIndex = i;
break;
}
if (SameTails[i].tailIsWholeBlock())
commonTailIndex = i;
}
}
if (commonTailIndex == SameTails.size() ||
(SameTails[commonTailIndex].getBlock() == PredBB &&
!SameTails[commonTailIndex].tailIsWholeBlock())) {
if (!CreateCommonTailOnlyBlock(PredBB,
maxCommonTailLength, commonTailIndex)) {
RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
continue;
}
}
MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber()
<< " 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 ? "" : ", "));
ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
MergePotentials.erase(SameTails[i].getMPIter());
}
DEBUG(dbgs() << "\n");
MadeChange = true;
}
return MadeChange;
}
bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
bool MadeChange = false;
if (!EnableTailMerge) return MadeChange;
MergePotentials.clear();
for (MachineFunction::iterator I = MF.begin(), E = MF.end();
I != E && MergePotentials.size() < TailMergeThreshold; ++I) {
if (TriedMerging.count(I))
continue;
if (I->succ_empty())
MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I), I));
}
if (MergePotentials.size() == TailMergeThreshold)
for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
TriedMerging.insert(MergePotentials[i].getBlock());
if (MergePotentials.size() >= 2)
MadeChange |= TryTailMergeBlocks(NULL, NULL);
for (MachineFunction::iterator I = llvm::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);
MergePotentials.clear();
for (MachineBasicBlock::pred_iterator P = I->pred_begin(),
E2 = I->pred_end();
P != E2 && MergePotentials.size() < TailMergeThreshold; ++P) {
MachineBasicBlock *PBB = *P;
if (TriedMerging.count(PBB))
continue;
if (PBB == IBB)
continue;
if (!UniquePreds.insert(PBB))
continue;
if (PBB->getLandingPadSuccessor())
continue;
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) {
SmallVector<MachineOperand, 4> NewCond(Cond);
if (!Cond.empty() && TBB == IBB) {
if (TII->ReverseBranchCondition(NewCond))
continue;
if (!FBB)
FBB = llvm::next(MachineFunction::iterator(PBB));
}
if (IBB->isLandingPad()) {
MachineFunction::iterator IP = PBB; IP++;
MachineBasicBlock *PredNextBB = NULL;
if (IP != MF.end())
PredNextBB = IP;
if (TBB == NULL) {
if (IBB != PredNextBB) continue;
} else if (FBB) {
if (TBB != IBB && FBB != IBB) continue;
} else if (Cond.empty()) {
if (TBB != IBB) continue;
} else {
if (TBB != IBB && IBB != PredNextBB) continue;
}
}
if (TBB && (Cond.empty() || FBB)) {
DebugLoc dl; TII->RemoveBranch(*PBB);
if (!Cond.empty())
TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond, dl);
}
MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB), *P));
}
}
if (MergePotentials.size() == TailMergeThreshold)
for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
TriedMerging.insert(MergePotentials[i].getBlock());
if (MergePotentials.size() >= 2)
MadeChange |= TryTailMergeBlocks(IBB, PredBB);
PredBB = prior(I); if (MergePotentials.size() == 1 &&
MergePotentials.begin()->getBlock() != PredBB)
FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
}
return MadeChange;
}
bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
bool MadeChange = false;
MF.RenumberBlocks();
for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
I != E; ) {
MachineBasicBlock *MBB = I++;
MadeChange |= OptimizeBlock(MBB);
if (MBB->pred_empty()) {
RemoveDeadBlock(MBB);
MadeChange = true;
++NumDeadBlocks;
}
}
return MadeChange;
}
static bool IsEmptyBlock(MachineBasicBlock *MBB) {
if (MBB->empty())
return true;
for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
MBBI!=MBBE; ++MBBI) {
if (!MBBI->isDebugValue())
return false;
}
return true;
}
static bool IsBranchOnlyBlock(MachineBasicBlock *MBB) {
MachineBasicBlock::iterator MBBI, MBBE;
for (MBBI = MBB->begin(), MBBE = MBB->end(); MBBI!=MBBE; ++MBBI) {
if (!MBBI->isDebugValue())
break;
}
return (MBBI->isBranch());
}
static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
MachineBasicBlock *MBB2) {
if (IsEmptyBlock(MBB1) || IsEmptyBlock(MBB2)) return false;
if (MBB1->isSuccessor(MBB2)) return true;
if (MBB2->isSuccessor(MBB1)) return false;
MachineBasicBlock::iterator MBB1I = --MBB1->end();
while (MBB1I->isDebugValue())
--MBB1I;
MachineBasicBlock::iterator MBB2I = --MBB2->end();
while (MBB2I->isDebugValue())
--MBB2I;
return MBB2I->isCall() && !MBB1I->isCall();
}
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) {
MachineBasicBlock::iterator I = MBB.end();
if (I == MBB.begin())
return DebugLoc();
--I;
while (I->isDebugValue() && I != MBB.begin())
--I;
if (I->isBranch())
return I->getDebugLoc();
return DebugLoc();
}
bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
bool MadeChange = false;
MachineFunction &MF = *MBB->getParent();
ReoptimizeBlock:
MachineFunction::iterator FallThrough = MBB;
++FallThrough;
if (IsEmptyBlock(MBB) && !MBB->isLandingPad() && !MBB->hasAddressTaken()) {
if (MBB->pred_empty()) return MadeChange;
if (FallThrough == MF.end()) {
} else {
while (!MBB->pred_empty()) {
MachineBasicBlock *Pred = *(MBB->pred_end()-1);
Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
}
if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
MJTI->ReplaceMBBInJumpTables(MBB, FallThrough);
MadeChange = true;
}
return MadeChange;
}
MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
SmallVector<MachineOperand, 4> PriorCond;
bool PriorUnAnalyzable =
TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
if (!PriorUnAnalyzable) {
MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
!PriorCond.empty());
if (PriorTBB && PriorTBB == PriorFBB) {
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
PriorCond.clear();
if (PriorTBB != MBB)
TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
}
if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
PrevBB.succ_size() == 1 &&
!MBB->hasAddressTaken() && !MBB->isLandingPad()) {
DEBUG(dbgs() << "\nMerging into block: " << PrevBB
<< "From MBB: " << *MBB);
if (PrevBB.begin() != PrevBB.end()) {
MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
--PrevBBIter;
MachineBasicBlock::iterator MBBIter = MBB->begin();
while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
&& PrevBBIter->isDebugValue() && MBBIter->isDebugValue()) {
if (!MBBIter->isIdenticalTo(PrevBBIter))
break;
MachineInstr *DuplicateDbg = MBBIter;
++MBBIter; -- PrevBBIter;
DuplicateDbg->eraseFromParent();
}
}
PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
PrevBB.removeSuccessor(PrevBB.succ_begin());
assert(PrevBB.succ_empty());
PrevBB.transferSuccessors(MBB);
MadeChange = true;
return MadeChange;
}
if (PriorTBB == MBB && PriorFBB == 0) {
TII->RemoveBranch(PrevBB);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
}
if (PriorFBB == MBB) {
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
}
if (PriorTBB == MBB) {
SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
if (!TII->ReverseBranchCondition(NewPriorCond)) {
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
}
}
if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 &&
MachineFunction::iterator(PriorTBB) == FallThrough &&
!MBB->canFallThrough()) {
bool DoTransform = true;
if (FallThrough == --MF.end() &&
!IsBetterFallthrough(PriorTBB, MBB))
DoTransform = false;
if (DoTransform) {
SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
if (!TII->ReverseBranchCondition(NewPriorCond)) {
DEBUG(dbgs() << "\nMoving MBB: " << *MBB
<< "To make fallthrough to: " << *PriorTBB << "\n");
DebugLoc dl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond, dl);
MBB->moveAfter(--MF.end());
MadeChange = true;
++NumBranchOpts;
return MadeChange;
}
}
}
}
MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
SmallVector<MachineOperand, 4> CurCond;
bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
if (!CurUnAnalyzable) {
MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());
if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
SmallVector<MachineOperand, 4> NewCond(CurCond);
if (!TII->ReverseBranchCondition(NewCond)) {
DebugLoc dl = getBranchDebugLoc(*MBB);
TII->RemoveBranch(*MBB);
TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
MadeChange = true;
++NumBranchOpts;
goto ReoptimizeBlock;
}
}
if (CurTBB && CurCond.empty() && CurFBB == 0 &&
IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
!MBB->hasAddressTaken()) {
DebugLoc dl = getBranchDebugLoc(*MBB);
TII->RemoveBranch(*MBB);
if (!MBB->empty()) {
bool NonDebugInfoFound = false;
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
if (!I->isDebugValue()) {
NonDebugInfoFound = true;
break;
}
}
if (!NonDebugInfoFound)
MBB->erase(MBB->begin(), MBB->end());
}
if (MBB->empty()) {
bool PredHasNoFallThrough = !PrevBB.canFallThrough();
if (PredHasNoFallThrough || !PriorUnAnalyzable ||
!PrevBB.isSuccessor(MBB)) {
if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
PriorTBB != MBB && PriorFBB != MBB) {
if (PriorTBB == 0) {
assert(PriorCond.empty() && PriorFBB == 0 &&
"Bad branch analysis");
PriorTBB = MBB;
} else {
assert(PriorFBB == 0 && "Machine CFG out of date!");
PriorFBB = MBB;
}
DebugLoc pdl = getBranchDebugLoc(PrevBB);
TII->RemoveBranch(PrevBB);
TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
}
size_t PI = 0;
bool DidChange = false;
bool HasBranchToSelf = false;
while(PI != MBB->pred_size()) {
MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
if (PMBB == MBB) {
++PI;
HasBranchToSelf = true;
} else {
DidChange = true;
PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0;
SmallVector<MachineOperand, 4> NewCurCond;
bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB,
NewCurFBB, NewCurCond, true);
if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
DebugLoc pdl = getBranchDebugLoc(*PMBB);
TII->RemoveBranch(*PMBB);
NewCurCond.clear();
TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond, pdl);
MadeChange = true;
++NumBranchOpts;
PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false);
}
}
}
if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
if (DidChange) {
++NumBranchOpts;
MadeChange = true;
if (!HasBranchToSelf) return MadeChange;
}
}
}
TII->InsertBranch(*MBB, CurTBB, 0, CurCond, dl);
}
}
if (!PrevBB.canFallThrough()) {
bool CurFallsThru = MBB->canFallThrough();
if (!MBB->isLandingPad()) {
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
E = MBB->pred_end(); PI != E; ++PI) {
MachineBasicBlock *PredBB = *PI;
MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
SmallVector<MachineOperand, 4> PredCond;
if (PredBB != MBB && !PredBB->canFallThrough() &&
!TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)
&& (!CurFallsThru || !CurTBB || !CurFBB)
&& (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
if (CurFallsThru) {
MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
CurCond.clear();
TII->InsertBranch(*MBB, NextBB, 0, CurCond, DebugLoc());
}
MBB->moveAfter(PredBB);
MadeChange = true;
goto ReoptimizeBlock;
}
}
}
if (!CurFallsThru) {
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
E = MBB->succ_end(); SI != E; ++SI) {
MachineBasicBlock *SuccBB = *SI;
MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
if (SuccBB != MBB && &*SuccPrev != MBB &&
!SuccPrev->canFallThrough() && !CurUnAnalyzable &&
!SuccBB->isLandingPad()) {
MBB->moveBefore(SuccBB);
MadeChange = true;
goto ReoptimizeBlock;
}
}
MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0;
SmallVector<MachineOperand, 4> PrevCond;
if (FallThrough != MF.end() &&
!TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
PrevBB.isSuccessor(FallThrough)) {
MBB->moveAfter(--MF.end());
MadeChange = true;
return MadeChange;
}
}
}
return MadeChange;
}
bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
bool MadeChange = false;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) {
MachineBasicBlock *MBB = I++;
MadeChange |= HoistCommonCodeInSuccs(MBB);
}
return MadeChange;
}
static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
MachineBasicBlock *TrueBB) {
for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
E = BB->succ_end(); SI != E; ++SI) {
MachineBasicBlock *SuccBB = *SI;
if (SuccBB != TrueBB)
return SuccBB;
}
return NULL;
}
static
MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
const TargetInstrInfo *TII,
const TargetRegisterInfo *TRI,
SmallSet<unsigned,4> &Uses,
SmallSet<unsigned,4> &Defs) {
MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
if (!TII->isUnpredicatedTerminator(Loc))
return MBB->end();
for (unsigned i = 0, e = Loc->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = Loc->getOperand(i);
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (MO.isUse()) {
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
Uses.insert(*AI);
} else if (!MO.isDead())
return MBB->end();
}
if (Uses.empty())
return Loc;
if (Loc == MBB->begin())
return MBB->end();
MachineBasicBlock::iterator PI = Loc;
--PI;
while (PI != MBB->begin() && Loc->isDebugValue())
--PI;
bool IsDef = false;
for (unsigned i = 0, e = PI->getNumOperands(); !IsDef && i != e; ++i) {
const MachineOperand &MO = PI->getOperand(i);
if (MO.isRegMask())
return Loc;
if (!MO.isReg() || MO.isUse())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (Uses.count(Reg))
IsDef = true;
}
if (!IsDef)
return Loc;
bool DontMoveAcrossStore = true;
if (!PI->isSafeToMove(TII, 0, DontMoveAcrossStore) ||
TII->isPredicated(PI))
return MBB->end();
for (unsigned i = 0, e = PI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = PI->getOperand(i);
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (MO.isUse()) {
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
Uses.insert(*AI);
} else {
if (Uses.erase(Reg)) {
for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
Uses.erase(*SubRegs); }
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
Defs.insert(*AI);
}
}
return PI;
}
bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
return false;
if (!FBB) FBB = findFalseBlock(MBB, TBB);
if (!FBB)
return false;
if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
return false;
SmallSet<unsigned, 4> Uses, Defs;
MachineBasicBlock::iterator Loc =
findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
if (Loc == MBB->end())
return false;
bool HasDups = false;
SmallVector<unsigned, 4> LocalDefs;
SmallSet<unsigned, 4> LocalDefsSet;
MachineBasicBlock::iterator TIB = TBB->begin();
MachineBasicBlock::iterator FIB = FBB->begin();
MachineBasicBlock::iterator TIE = TBB->end();
MachineBasicBlock::iterator FIE = FBB->end();
while (TIB != TIE && FIB != FIE) {
if (TIB->isDebugValue()) {
while (TIB != TIE && TIB->isDebugValue())
++TIB;
if (TIB == TIE)
break;
}
if (FIB->isDebugValue()) {
while (FIB != FIE && FIB->isDebugValue())
++FIB;
if (FIB == FIE)
break;
}
if (!TIB->isIdenticalTo(FIB, MachineInstr::CheckKillDead))
break;
if (TII->isPredicated(TIB))
break;
bool IsSafe = true;
for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) {
MachineOperand &MO = TIB->getOperand(i);
if (MO.isRegMask()) {
IsSafe = false;
break;
}
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (MO.isDef()) {
if (Uses.count(Reg)) {
IsSafe = false;
break;
}
if (Defs.count(Reg) && !MO.isDead()) {
IsSafe = false;
break;
}
} else if (!LocalDefsSet.count(Reg)) {
if (Defs.count(Reg)) {
IsSafe = false;
break;
}
if (MO.isKill() && Uses.count(Reg))
MO.setIsKill(false);
}
}
if (!IsSafe)
break;
bool DontMoveAcrossStore = true;
if (!TIB->isSafeToMove(TII, 0, DontMoveAcrossStore))
break;
for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) {
MachineOperand &MO = TIB->getOperand(i);
if (!MO.isReg() || !MO.isUse() || !MO.isKill())
continue;
unsigned Reg = MO.getReg();
if (!Reg || !LocalDefsSet.count(Reg))
continue;
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
LocalDefsSet.erase(*AI);
}
for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) {
MachineOperand &MO = TIB->getOperand(i);
if (!MO.isReg() || !MO.isDef() || MO.isDead())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
LocalDefs.push_back(Reg);
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
LocalDefsSet.insert(*AI);
}
HasDups = true;
++TIB;
++FIB;
}
if (!HasDups)
return false;
MBB->splice(Loc, TBB, TBB->begin(), TIB);
FBB->erase(FBB->begin(), FIB);
for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
unsigned Def = LocalDefs[i];
if (LocalDefsSet.count(Def)) {
TBB->addLiveIn(Def);
FBB->addLiveIn(Def);
}
}
++NumHoist;
return true;
}