PHIElimination.cpp [plain text]
#define DEBUG_TYPE "phielim"
#include "llvm/CodeGen/Passes.h"
#include "PHIEliminationUtils.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include <algorithm>
using namespace llvm;
static cl::opt<bool>
DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
cl::Hidden, cl::desc("Disable critical edge splitting "
"during PHI elimination"));
namespace {
class PHIElimination : public MachineFunctionPass {
MachineRegisterInfo *MRI;
public:
static char ID; PHIElimination() : MachineFunctionPass(ID) {
initializePHIEliminationPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnMachineFunction(MachineFunction &Fn);
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
private:
bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
void LowerAtomicPHINode(MachineBasicBlock &MBB,
MachineBasicBlock::iterator AfterPHIsIt);
void analyzePHINodes(const MachineFunction& Fn);
bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
LiveVariables &LV, MachineLoopInfo *MLI);
typedef std::pair<unsigned, unsigned> BBVRegPair;
typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse;
VRegPHIUse VRegPHIUseCount;
SmallPtrSet<MachineInstr*, 4> ImpDefs;
typedef DenseMap<MachineInstr*, unsigned,
MachineInstrExpressionTrait> LoweredPHIMap;
LoweredPHIMap LoweredPHIs;
};
}
STATISTIC(NumAtomic, "Number of atomic phis lowered");
STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
STATISTIC(NumReused, "Number of reused lowered phis");
char PHIElimination::ID = 0;
char& llvm::PHIEliminationID = PHIElimination::ID;
INITIALIZE_PASS_BEGIN(PHIElimination, "phi-node-elimination",
"Eliminate PHI nodes for register allocation",
false, false)
INITIALIZE_PASS_DEPENDENCY(LiveVariables)
INITIALIZE_PASS_END(PHIElimination, "phi-node-elimination",
"Eliminate PHI nodes for register allocation", false, false)
void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<LiveVariables>();
AU.addPreserved<MachineDominatorTree>();
AU.addPreserved<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
MRI = &MF.getRegInfo();
bool Changed = false;
MRI->leaveSSA();
if (!DisableEdgeSplitting) {
if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>()) {
MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
Changed |= SplitPHIEdges(MF, *I, *LV, MLI);
}
}
analyzePHINodes(MF);
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
Changed |= EliminatePHINodes(MF, *I);
for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(),
E = ImpDefs.end(); I != E; ++I) {
MachineInstr *DefMI = *I;
unsigned DefReg = DefMI->getOperand(0).getReg();
if (MRI->use_nodbg_empty(DefReg))
DefMI->eraseFromParent();
}
for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end();
I != E; ++I)
MF.DeleteMachineInstr(I->first);
LoweredPHIs.clear();
ImpDefs.clear();
VRegPHIUseCount.clear();
return Changed;
}
bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
MachineBasicBlock &MBB) {
if (MBB.empty() || !MBB.front().isPHI())
return false;
MachineBasicBlock::iterator AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin());
while (MBB.front().isPHI())
LowerAtomicPHINode(MBB, AfterPHIsIt);
return true;
}
static bool isImplicitlyDefined(unsigned VirtReg,
const MachineRegisterInfo *MRI) {
for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(VirtReg),
DE = MRI->def_end(); DI != DE; ++DI)
if (!DI->isImplicitDef())
return false;
return true;
}
static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi,
const MachineRegisterInfo *MRI) {
for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
if (!isImplicitlyDefined(MPhi->getOperand(i).getReg(), MRI))
return false;
return true;
}
void PHIElimination::LowerAtomicPHINode(
MachineBasicBlock &MBB,
MachineBasicBlock::iterator AfterPHIsIt) {
++NumAtomic;
MachineInstr *MPhi = MBB.remove(MBB.begin());
unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
unsigned DestReg = MPhi->getOperand(0).getReg();
assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
bool isDead = MPhi->getOperand(0).isDead();
MachineFunction &MF = *MBB.getParent();
unsigned IncomingReg = 0;
bool reusedIncoming = false;
const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
if (isSourceDefinedByImplicitDef(MPhi, MRI))
BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
else {
unsigned &entry = LoweredPHIs[MPhi];
if (entry) {
IncomingReg = entry;
reusedIncoming = true;
++NumReused;
DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi);
} else {
const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
}
BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
TII->get(TargetOpcode::COPY), DestReg)
.addReg(IncomingReg);
}
LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
if (LV) {
MachineInstr *PHICopy = prior(AfterPHIsIt);
if (IncomingReg) {
LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
LV->setPHIJoin(IncomingReg);
if (reusedIncoming)
if (MachineInstr *OldKill = VI.findKill(&MBB)) {
DEBUG(dbgs() << "Remove old kill from " << *OldKill);
LV->removeVirtualRegisterKilled(IncomingReg, OldKill);
DEBUG(MBB.dump());
}
LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
}
LV->removeVirtualRegistersKilled(MPhi);
if (isDead) {
LV->addVirtualRegisterDead(DestReg, PHICopy);
LV->removeVirtualRegisterDead(DestReg, MPhi);
}
}
for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
--VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
MPhi->getOperand(i).getReg())];
SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
for (int i = NumSrcs - 1; i >= 0; --i) {
unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
isImplicitlyDefined(SrcReg, MRI);
assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
"Machine PHI Operands must all be virtual registers!");
MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
if (!MBBsInsertedInto.insert(&opBlock))
continue;
MachineBasicBlock::iterator InsertPos =
findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
if (!reusedIncoming && IncomingReg) {
if (SrcUndef) {
BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg);
if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
if (DefMI->isImplicitDef())
ImpDefs.insert(DefMI);
} else {
BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
TII->get(TargetOpcode::COPY), IncomingReg)
.addReg(SrcReg, 0, SrcSubReg);
}
}
if (SrcUndef || !LV) continue;
bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)];
if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) {
MachineBasicBlock::iterator KillInst = opBlock.end();
MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
for (MachineBasicBlock::iterator Term = FirstTerm;
Term != opBlock.end(); ++Term) {
if (Term->readsRegister(SrcReg))
KillInst = Term;
}
if (KillInst == opBlock.end()) {
if (reusedIncoming || !IncomingReg) {
KillInst = FirstTerm;
while (KillInst != opBlock.begin()) {
--KillInst;
if (KillInst->isDebugValue())
continue;
if (KillInst->readsRegister(SrcReg))
break;
}
} else {
KillInst = prior(InsertPos);
}
}
assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
LV->addVirtualRegisterKilled(SrcReg, KillInst);
unsigned opBlockNum = opBlock.getNumber();
LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
}
}
if (reusedIncoming || !IncomingReg)
MF.DeleteMachineInstr(MPhi);
}
void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
I != E; ++I)
for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
BBI != BBE && BBI->isPHI(); ++BBI)
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(),
BBI->getOperand(i).getReg())];
}
bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
MachineBasicBlock &MBB,
LiveVariables &LV,
MachineLoopInfo *MLI) {
if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad())
return false;
const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : 0;
bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
bool Changed = false;
for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
BBI != BBE && BBI->isPHI(); ++BBI) {
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
unsigned Reg = BBI->getOperand(i).getReg();
MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
if (PreMBB->succ_size() == 1)
continue;
if (PreMBB == &MBB)
continue;
const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0;
if (IsLoopHeader && PreLoop == CurLoop)
continue;
if (!LV.isLiveOut(Reg, *PreMBB))
continue;
DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#"
<< PreMBB->getNumber() << " -> BB#" << MBB.getNumber()
<< ": " << *BBI);
bool ShouldSplit = !LV.isLiveIn(Reg, MBB);
if (!ShouldSplit && CurLoop != PreLoop) {
DEBUG({
dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
if (PreLoop) dbgs() << "PreLoop: " << *PreLoop;
if (CurLoop) dbgs() << "CurLoop: " << *CurLoop;
});
ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
}
if (!ShouldSplit)
continue;
if (!PreMBB->SplitCriticalEdge(&MBB, this)) {
DEBUG(dbgs() << "Failed to split ciritcal edge.\n");
continue;
}
Changed = true;
++NumCriticalEdgesSplit;
}
}
return Changed;
}