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/LiveIntervalAnalysis.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"));
static cl::opt<bool>
SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
cl::Hidden, cl::desc("Split all critical edges during "
"PHI elimination"));
namespace {
class PHIElimination : public MachineFunctionPass {
MachineRegisterInfo *MRI; LiveVariables *LV;
LiveIntervals *LIS;
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 LowerPHINode(MachineBasicBlock &MBB,
MachineBasicBlock::iterator LastPHIIt);
void analyzePHINodes(const MachineFunction& Fn);
bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
MachineLoopInfo *MLI);
bool isLiveIn(unsigned Reg, MachineBasicBlock *MBB);
bool isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB);
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(NumLowered, "Number of 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<SlotIndexes>();
AU.addPreserved<LiveIntervals>();
AU.addPreserved<MachineDominatorTree>();
AU.addPreserved<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
MRI = &MF.getRegInfo();
LV = getAnalysisIfAvailable<LiveVariables>();
LIS = getAnalysisIfAvailable<LiveIntervals>();
bool Changed = false;
MRI->leaveSSA();
if (!DisableEdgeSplitting && (LV || LIS)) {
MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
Changed |= SplitPHIEdges(MF, *I, 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)) {
if (LIS)
LIS->RemoveMachineInstrFromMaps(DefMI);
DefMI->eraseFromParent();
}
}
for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end();
I != E; ++I) {
if (LIS)
LIS->RemoveMachineInstrFromMaps(I->first);
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 LastPHIIt =
prior(MBB.SkipPHIsAndLabels(MBB.begin()));
while (MBB.front().isPHI())
LowerPHINode(MBB, LastPHIIt);
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::LowerPHINode(MachineBasicBlock &MBB,
MachineBasicBlock::iterator LastPHIIt) {
++NumLowered;
MachineBasicBlock::iterator AfterPHIsIt = llvm::next(LastPHIIt);
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);
}
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);
}
}
if (LIS) {
MachineInstr *NewInstr = prior(AfterPHIsIt);
SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr);
SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
if (IncomingReg) {
LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
if (!IncomingVNI)
IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
LIS->getVNInfoAllocator());
IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
DestCopyIndex.getRegSlot(),
IncomingVNI));
}
LiveInterval &DestLI = LIS->getInterval(DestReg);
assert(DestLI.begin() != DestLI.end() &&
"PHIs should have nonempty LiveIntervals.");
if (DestLI.endIndex().isDead()) {
VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
assert(OrigDestVNI && "PHI destination should be live at block entry.");
DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
LIS->getVNInfoAllocator());
DestLI.removeValNo(OrigDestVNI);
} else {
DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
assert(DestVNI && "PHI destination should be live at its definition.");
DestVNI->def = DestCopyIndex.getRegSlot();
}
}
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);
MachineInstr *NewSrcInstr = 0;
if (!reusedIncoming && IncomingReg) {
if (SrcUndef) {
NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
TII->get(TargetOpcode::IMPLICIT_DEF),
IncomingReg);
if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
if (DefMI->isImplicitDef())
ImpDefs.insert(DefMI);
} else {
NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
TII->get(TargetOpcode::COPY), IncomingReg)
.addReg(SrcReg, 0, SrcSubReg);
}
}
if (LV && !SrcUndef &&
!VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
!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 (LIS) {
if (NewSrcInstr) {
LIS->InsertMachineInstrInMaps(NewSrcInstr);
LIS->addSegmentToEndOfBlock(IncomingReg, NewSrcInstr);
}
if (!SrcUndef &&
!VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
LiveInterval &SrcLI = LIS->getInterval(SrcReg);
bool isLiveOut = false;
for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
SE = opBlock.succ_end(); SI != SE; ++SI) {
SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
if (VNI && VNI->def != startIdx) {
isLiveOut = true;
break;
}
}
if (!isLiveOut) {
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");
SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst);
SrcLI.removeSegment(LastUseIndex.getRegSlot(),
LIS->getMBBEndIdx(&opBlock));
}
}
}
}
if (reusedIncoming || !IncomingReg) {
if (LIS)
LIS->RemoveMachineInstrFromMaps(MPhi);
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,
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 && !SplitAllCriticalEdges)
continue;
const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0;
if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
continue;
if (!isLiveOutPastPHIs(Reg, PreMBB) && !SplitAllCriticalEdges)
continue;
DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#"
<< PreMBB->getNumber() << " -> BB#" << MBB.getNumber()
<< ": " << *BBI);
bool ShouldSplit = !isLiveIn(Reg, &MBB) || SplitAllCriticalEdges;
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 critical edge.\n");
continue;
}
Changed = true;
++NumCriticalEdgesSplit;
}
}
return Changed;
}
bool PHIElimination::isLiveIn(unsigned Reg, MachineBasicBlock *MBB) {
assert((LV || LIS) &&
"isLiveIn() requires either LiveVariables or LiveIntervals");
if (LIS)
return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
else
return LV->isLiveIn(Reg, *MBB);
}
bool PHIElimination::isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB) {
assert((LV || LIS) &&
"isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
if (LIS) {
const LiveInterval &LI = LIS->getInterval(Reg);
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI) {
if (LI.liveAt(LIS->getMBBStartIdx(*SI)))
return true;
}
return false;
} else {
return LV->isLiveOut(Reg, *MBB);
}
}