CodePlacementOpt.cpp [plain text]
#define DEBUG_TYPE "code-placement"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumLoopsAligned, "Number of loops aligned");
STATISTIC(NumIntraElim, "Number of intra loop branches eliminated");
STATISTIC(NumIntraMoved, "Number of intra loop branches moved");
namespace {
class CodePlacementOpt : public MachineFunctionPass {
const MachineLoopInfo *MLI;
const TargetInstrInfo *TII;
const TargetLowering *TLI;
public:
static char ID;
CodePlacementOpt() : MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<MachineLoopInfo>();
AU.addPreservedID(MachineDominatorsID);
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
bool HasFallthrough(MachineBasicBlock *MBB);
bool HasAnalyzableTerminator(MachineBasicBlock *MBB);
void Splice(MachineFunction &MF,
MachineFunction::iterator InsertPt,
MachineFunction::iterator Begin,
MachineFunction::iterator End);
bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
MachineLoop *L);
bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
MachineLoop *L);
bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
bool OptimizeIntraLoopEdges(MachineFunction &MF);
bool AlignLoops(MachineFunction &MF);
bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
};
char CodePlacementOpt::ID = 0;
}
char &llvm::CodePlacementOptID = CodePlacementOpt::ID;
INITIALIZE_PASS(CodePlacementOpt, "code-placement",
"Code Placement Optimizer", false, false)
bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) {
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
return false;
if (FBB)
return false;
if (Cond.empty() && TBB)
return false;
return true;
}
bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) {
if (MBB->isLandingPad()) return false;
if (MBB->succ_empty()) return true;
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
return false;
if (1u + !Cond.empty() != MBB->succ_size())
return false;
if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
return false;
return true;
}
void CodePlacementOpt::Splice(MachineFunction &MF,
MachineFunction::iterator InsertPt,
MachineFunction::iterator Begin,
MachineFunction::iterator End) {
assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
"Splice can't change the entry block!");
MachineFunction::iterator OldBeginPrior = prior(Begin);
MachineFunction::iterator OldEndPrior = prior(End);
MF.splice(InsertPt, Begin, End);
prior(Begin)->updateTerminator();
OldBeginPrior->updateTerminator();
OldEndPrior->updateTerminator();
}
bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
MachineLoop *L) {
bool Changed = false;
MachineBasicBlock *TopMBB = L->getTopBlock();
bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
if (TopMBB == MF.begin() ||
HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
new_top:
for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
PE = TopMBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock *Pred = *PI;
if (Pred == TopMBB) continue;
if (HasFallthrough(Pred)) continue;
if (!L->contains(Pred)) continue;
if (Pred == MF.begin())
continue;
if (!HasAnalyzableTerminator(Pred))
continue;
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
continue;
DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber()
<< " to top of loop.\n");
Changed = true;
MachineFunction::iterator Begin = Pred;
MachineFunction::iterator End = llvm::next(Begin);
while (Begin != MF.begin()) {
MachineFunction::iterator Prior = prior(Begin);
if (Prior == MF.begin())
break;
if (!HasFallthrough(Prior))
break;
if (Prior->isSuccessor(End))
break;
if (Prior == MachineFunction::iterator(TopMBB)) {
if (!Prior->isSuccessor(End))
goto next_pred;
break;
}
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
break;
Begin = Prior;
++NumIntraMoved;
}
Splice(MF, TopMBB, Begin, End);
TopMBB = L->getTopBlock();
goto new_top;
next_pred:;
}
}
if (Changed &&
!BotHasFallthrough &&
HasFallthrough(L->getBottomBlock())) {
++NumIntraElim;
}
return Changed;
}
bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
MachineLoop *L) {
bool Changed = false;
MachineBasicBlock *TopMBB = L->getTopBlock();
MachineBasicBlock *BotMBB = L->getBottomBlock();
MachineFunction::iterator InsertPt =
llvm::next(MachineFunction::iterator(BotMBB));
bool InsertAtTop = false;
if (TopMBB != MF.begin() &&
!HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
HasFallthrough(BotMBB)) {
InsertPt = TopMBB;
InsertAtTop = true;
}
SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
for (MachineFunction::iterator I = TopMBB,
E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)
ContiguousBlocks.insert(I);
if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
BI != BE; ++BI) {
MachineBasicBlock *BB = *BI;
if (!HasAnalyzableTerminator(BB))
continue;
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
continue;
if (BB != MF.begin() &&
L->contains(prior(MachineFunction::iterator(BB))))
continue;
if (!ContiguousBlocks.insert(BB))
continue;
DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber()
<< " to be contiguous with loop.\n");
Changed = true;
MachineFunction::iterator Begin = BB;
MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));
for (; End != MF.end(); ++End) {
if (!L->contains(End)) break;
if (!HasAnalyzableTerminator(End)) break;
ContiguousBlocks.insert(End);
++NumIntraMoved;
}
if (!InsertAtTop)
for (; End != MF.end(); ++End) {
if (L->contains(End)) break;
if (!HasAnalyzableTerminator(End)) break;
if (!HasFallthrough(prior(End))) break;
}
Splice(MF, InsertPt, Begin, End);
}
return Changed;
}
bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
MachineLoop *L) {
bool Changed = false;
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
Changed |= EliminateUnconditionalJumpsToTop(MF, L);
Changed |= MoveDiscontiguousLoopBlocks(MF, L);
return Changed;
}
bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
bool Changed = false;
if (!TLI->shouldOptimizeCodePlacement())
return Changed;
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
I != E; ++I)
if (!(*I)->getParentLoop())
Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
return Changed;
}
bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
const Function *F = MF.getFunction();
if (F->hasFnAttr(Attribute::OptimizeForSize))
return false;
unsigned Align = TLI->getPrefLoopAlignment();
if (!Align)
return false;
bool Changed = false;
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
I != E; ++I)
Changed |= AlignLoop(MF, *I, Align);
return Changed;
}
bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
unsigned Align) {
bool Changed = false;
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= AlignLoop(MF, *I, Align);
L->getTopBlock()->setAlignment(Align);
Changed = true;
++NumLoopsAligned;
return Changed;
}
bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
MLI = &getAnalysis<MachineLoopInfo>();
if (MLI->empty())
return false;
TLI = MF.getTarget().getTargetLowering();
TII = MF.getTarget().getInstrInfo();
bool Changed = OptimizeIntraLoopEdges(MF);
Changed |= AlignLoops(MF);
return Changed;
}