//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "branchfolding"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/MachineDebugInfo.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;
-static Statistic<> NumDeadBlocks("branchfold", "Number of dead blocks removed");
-static Statistic<> NumBranchOpts("branchfold", "Number of branches optimized");
-static Statistic<> NumTailMerge ("branchfold", "Number of block tails merged");
+STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
+STATISTIC(NumBranchOpts, "Number of branches optimized");
+STATISTIC(NumTailMerge , "Number of block tails merged");
static cl::opt<bool> EnableTailMerge("enable-tail-merge", cl::Hidden);
namespace {
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual const char *getPassName() const { return "Control Flow Optimizer"; }
const TargetInstrInfo *TII;
- MachineDebugInfo *MDI;
+ MachineModuleInfo *MMI;
bool MadeChange;
private:
// Tail Merging.
MachineBasicBlock *NewDest);
MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
MachineBasicBlock::iterator BBI1);
-
+
+ const MRegisterInfo *RegInfo;
+ RegScavenger *RS;
// Branch optzn.
bool OptimizeBranches(MachineFunction &MF);
void OptimizeBlock(MachineBasicBlock *MBB);
/// function, updating the CFG.
void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
assert(MBB->pred_empty() && "MBB must be dead!");
+ DOUT << "\nRemoving MBB: " << *MBB;
MachineFunction *MF = MBB->getParent();
// drop all successors.
while (!MBB->succ_empty())
MBB->removeSuccessor(MBB->succ_end()-1);
- // If there is DWARF info to active, check to see if there are any DWARF_LABEL
- // records in the basic block. If so, unregister them from MachineDebugInfo.
- if (MDI && !MBB->empty()) {
- unsigned DWARF_LABELOpc = TII->getDWARF_LABELOpcode();
- assert(DWARF_LABELOpc &&
- "Target supports dwarf but didn't implement getDWARF_LABELOpcode!");
-
+ // If there is DWARF info to active, check to see if there are any LABEL
+ // records in the basic block. If so, unregister them from MachineModuleInfo.
+ if (MMI && !MBB->empty()) {
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
- if ((unsigned)I->getOpcode() == DWARF_LABELOpc) {
+ if ((unsigned)I->getOpcode() == TargetInstrInfo::LABEL) {
// The label ID # is always operand #0, an immediate.
- MDI->InvalidateLabel(I->getOperand(0).getImm());
+ MMI->InvalidateLabel(I->getOperand(0).getImm());
}
}
}
TII = MF.getTarget().getInstrInfo();
if (!TII) return false;
- MDI = getAnalysisToUpdate<MachineDebugInfo>();
+ RegInfo = MF.getTarget().getRegisterInfo();
+ RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL;
+
+ MMI = getAnalysisToUpdate<MachineModuleInfo>();
bool EverMadeChange = false;
bool MadeChangeThisIteration = true;
}
}
+ delete RS;
return EverMadeChange;
}
// Splice the code over.
NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
+
+ // For targets that use the register scavenger, we must maintain LiveIns.
+ if (RS) {
+ RS->enterBasicBlock(&CurMBB);
+ if (!CurMBB.empty())
+ RS->forward(prior(CurMBB.end()));
+ BitVector RegsLiveAtExit(RegInfo->getNumRegs());
+ RS->getRegsUsed(RegsLiveAtExit, false);
+ for (unsigned int i=0, e=RegInfo->getNumRegs(); i!=e; i++)
+ if (RegsLiveAtExit[i])
+ NewMBB->addLiveIn(i);
+ }
+
return NewMBB;
}
bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
MadeChange = false;
+ // Make sure blocks are numbered in order
+ MF.RenumberBlocks();
+
for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
MachineBasicBlock *MBB = I++;
OptimizeBlock(MBB);
} else if (*SI == DestB) {
DestB = 0;
++SI;
+ } else if ((*SI)->isLandingPad()) {
+ ++SI;
} else {
// Otherwise, this is a superfluous edge, remove it.
MBB.removeSuccessor(SI);
return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond);
}
+/// 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
+/// result in infinite loops.
+static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
+ MachineBasicBlock *MBB2,
+ const TargetInstrInfo &TII) {
+ // Right now, we use a simple heuristic. If MBB2 ends with a call, and
+ // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
+ // optimize branches that branch to either a return block or an assert block
+ // into a fallthrough to the return.
+ if (MBB1->empty() || MBB2->empty()) return false;
+
+ MachineInstr *MBB1I = --MBB1->end();
+ MachineInstr *MBB2I = --MBB2->end();
+ return TII.isCall(MBB2I->getOpcode()) && !TII.isCall(MBB1I->getOpcode());
+}
+
/// OptimizeBlock - Analyze and optimize control flow related to the specified
/// block. This is never called on the entry block.
void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
return OptimizeBlock(MBB);
}
}
+
+ // If this block doesn't fall through (e.g. it ends with an uncond branch or
+ // has no successors) and if the pred falls through into this block, and if
+ // it would otherwise fall through into the block after this, move this
+ // block to the end of the function.
+ //
+ // 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 (!PriorCond.empty() && PriorFBB == 0 &&
+ MachineFunction::iterator(PriorTBB) == FallThrough &&
+ !CanFallThrough(MBB)) {
+ bool DoTransform = true;
+
+ // We have to be careful that the succs of PredBB aren't both no-successor
+ // blocks. If neither have successors and if PredBB is the second from
+ // last block in the function, we'd just keep swapping the two blocks for
+ // last. Only do the swap if one is clearly better to fall through than
+ // the other.
+ if (FallThrough == --MBB->getParent()->end() &&
+ !IsBetterFallthrough(PriorTBB, MBB, *TII))
+ DoTransform = false;
+
+ // We don't want to do this transformation if we have control flow like:
+ // br cond BB2
+ // BB1:
+ // ..
+ // jmp BBX
+ // BB2:
+ // ..
+ // ret
+ //
+ // In this case, we could actually be moving the return block *into* a
+ // loop!
+ if (DoTransform && !MBB->succ_empty() &&
+ (!CanFallThrough(PriorTBB) || PriorTBB->empty()))
+ DoTransform = false;
+
+
+ if (DoTransform) {
+ // Reverse the branch so we will fall through on the previous true cond.
+ std::vector<MachineOperand> NewPriorCond(PriorCond);
+ if (!TII->ReverseBranchCondition(NewPriorCond)) {
+ DOUT << "\nMoving MBB: " << *MBB;
+ DOUT << "To make fallthrough to: " << *PriorTBB << "\n";
+
+ TII->RemoveBranch(PrevBB);
+ TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond);
+
+ // Move this block to the end of the function.
+ MBB->moveAfter(--MBB->getParent()->end());
+ MadeChange = true;
+ ++NumBranchOpts;
+ return;
+ }
+ }
+ }
}
// Analyze the branch in the current block.
PriorTBB, PriorFBB, PriorCond)) {
// Now we know that there was no fall-through into this block, check to
// see if it has a fall-through into its successor.
- if (!CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, CurCond)) {
+ bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB,
+ CurCond);
+
+ if (!MBB->isLandingPad()) {
// Check all the predecessors of this block. If one of them has no fall
// throughs, move this block right after it.
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
// Analyze the branch at the end of the pred.
MachineBasicBlock *PredBB = *PI;
MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
- std::vector<MachineOperand> PredCond;
- if (PredBB != MBB && !CanFallThrough(PredBB)) {
+ if (PredBB != MBB && !CanFallThrough(PredBB)
+ && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
+ // If the current block doesn't fall through, just move it.
+ // If the current block can fall through and does not end with a
+ // conditional branch, we need to append an unconditional jump to
+ // the (current) next block. To avoid a possible compile-time
+ // infinite loop, move blocks only backward in this case.
+ if (CurFallsThru) {
+ MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB));
+ CurCond.clear();
+ TII->InsertBranch(*MBB, NextBB, 0, CurCond);
+ }
MBB->moveAfter(PredBB);
MadeChange = true;
return OptimizeBlock(MBB);
}
}
+ }
+ if (!CurFallsThru) {
// Check all successors to see if we can move this block before it.
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
E = MBB->succ_end(); SI != E; ++SI) {
projects / oota-llvm.git / blobdiff