StrongPHIElimination.cpp [plain text]
#define DEBUG_TYPE "strongphielim"
#include "PHIEliminationUtils.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
using namespace llvm;
namespace {
class StrongPHIElimination : public MachineFunctionPass {
public:
static char ID; StrongPHIElimination() : MachineFunctionPass(ID) {
initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
}
virtual void getAnalysisUsage(AnalysisUsage&) const;
bool runOnMachineFunction(MachineFunction&);
private:
struct Node {
enum Flags {
kRegisterIsolatedFlag = 1,
kPHIIsolatedFlag = 2
};
Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); }
Node *getLeader();
PointerIntPair<Node*, 2> parent;
unsigned value;
unsigned rank;
};
void addReg(unsigned);
void unionRegs(unsigned, unsigned);
unsigned getRegColor(unsigned);
void isolateReg(unsigned);
unsigned getPHIColor(MachineInstr*);
void isolatePHI(MachineInstr*);
void SplitInterferencesForBasicBlock(
MachineBasicBlock&,
DenseMap<unsigned, unsigned> &CurrentDominatingParent,
DenseMap<unsigned, unsigned> &ImmediateDominatingParent);
void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);
void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
MachineRegisterInfo *MRI;
const TargetInstrInfo *TII;
MachineDominatorTree *DT;
LiveIntervals *LI;
BumpPtrAllocator Allocator;
DenseMap<unsigned, Node*> RegNodeMap;
DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > PHISrcDefs;
DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > SrcCopySet;
SrcCopySet InsertedSrcCopySet;
typedef DenseMap<std::pair<MachineBasicBlock*, unsigned>, MachineInstr*>
SrcCopyMap;
SrcCopyMap InsertedSrcCopyMap;
typedef DenseMap<unsigned, MachineInstr*> DestCopyMap;
DestCopyMap InsertedDestCopies;
};
struct MIIndexCompare {
MIIndexCompare(LiveIntervals *LiveIntervals) : LI(LiveIntervals) { }
bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS);
}
LiveIntervals *LI;
};
}
STATISTIC(NumPHIsLowered, "Number of PHIs lowered");
STATISTIC(NumDestCopiesInserted, "Number of destination copies inserted");
STATISTIC(NumSrcCopiesInserted, "Number of source copies inserted");
char StrongPHIElimination::ID = 0;
INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
"Eliminate PHI nodes for register allocation, intelligently", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
"Eliminate PHI nodes for register allocation, intelligently", false, false)
char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
void StrongPHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<MachineDominatorTree>();
AU.addRequired<SlotIndexes>();
AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
MachineFunctionPass::getAnalysisUsage(AU);
}
static MachineOperand *findLastUse(MachineBasicBlock *MBB, unsigned Reg) {
for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
assert (RI != MBB->rend());
MachineInstr *MI = &*RI;
for (MachineInstr::mop_iterator OI = MI->operands_begin(),
OE = MI->operands_end(); OI != OE; ++OI) {
MachineOperand &MO = *OI;
if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
return &MO;
}
}
}
bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
MRI = &MF.getRegInfo();
TII = MF.getTarget().getInstrInfo();
DT = &getAnalysis<MachineDominatorTree>();
LI = &getAnalysis<LiveIntervals>();
for (MachineFunction::iterator I = MF.begin(), E = MF.end();
I != E; ++I) {
for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
BBI != BBE && BBI->isPHI(); ++BBI) {
unsigned DestReg = BBI->getOperand(0).getReg();
addReg(DestReg);
PHISrcDefs[I].push_back(BBI);
for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
MachineOperand &SrcMO = BBI->getOperand(i);
unsigned SrcReg = SrcMO.getReg();
addReg(SrcReg);
unionRegs(DestReg, SrcReg);
MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
if (DefMI)
PHISrcDefs[DefMI->getParent()].push_back(DefMI);
}
}
}
DenseMap<unsigned, unsigned> CurrentDominatingParent;
DenseMap<unsigned, unsigned> ImmediateDominatingParent;
for (df_iterator<MachineDomTreeNode*> DI = df_begin(DT->getRootNode()),
DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
SplitInterferencesForBasicBlock(*DI->getBlock(),
CurrentDominatingParent,
ImmediateDominatingParent);
}
for (MachineFunction::iterator I = MF.begin(), E = MF.end();
I != E; ++I) {
for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
BBI != BBE && BBI->isPHI(); ++BBI) {
InsertCopiesForPHI(BBI, I);
}
}
RegNodeMap.clear();
for (MachineFunction::iterator I = MF.begin(), E = MF.end();
I != E; ++I) {
for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
BBI != BBE && BBI->isPHI(); ++BBI) {
unsigned DestReg = BBI->getOperand(0).getReg();
addReg(DestReg);
for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
unsigned SrcReg = BBI->getOperand(i).getReg();
addReg(SrcReg);
unionRegs(DestReg, SrcReg);
}
}
}
DenseMap<unsigned, unsigned> RegRenamingMap;
bool Changed = false;
for (MachineFunction::iterator I = MF.begin(), E = MF.end();
I != E; ++I) {
MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
while (BBI != BBE && BBI->isPHI()) {
MachineInstr *PHI = BBI;
assert(PHI->getNumOperands() > 0);
unsigned SrcReg = PHI->getOperand(1).getReg();
unsigned SrcColor = getRegColor(SrcReg);
unsigned NewReg = RegRenamingMap[SrcColor];
if (!NewReg) {
NewReg = SrcReg;
RegRenamingMap[SrcColor] = SrcReg;
}
MergeLIsAndRename(SrcReg, NewReg);
unsigned DestReg = PHI->getOperand(0).getReg();
if (!InsertedDestCopies.count(DestReg))
MergeLIsAndRename(DestReg, NewReg);
for (unsigned i = 3; i < PHI->getNumOperands(); i += 2) {
unsigned SrcReg = PHI->getOperand(i).getReg();
MergeLIsAndRename(SrcReg, NewReg);
}
++BBI;
LI->RemoveMachineInstrFromMaps(PHI);
PHI->eraseFromParent();
Changed = true;
}
}
for (DestCopyMap::iterator I = InsertedDestCopies.begin(),
E = InsertedDestCopies.end(); I != E; ++I) {
unsigned DestReg = I->first;
unsigned DestColor = getRegColor(DestReg);
unsigned NewReg = RegRenamingMap[DestColor];
LiveInterval &DestLI = LI->getInterval(DestReg);
LiveInterval &NewLI = LI->getInterval(NewReg);
assert(DestLI.ranges.size() == 1
&& "PHI destination copy's live interval should be a single live "
"range from the beginning of the BB to the copy instruction.");
LiveRange *DestLR = DestLI.begin();
VNInfo *NewVNI = NewLI.getVNInfoAt(DestLR->start);
if (!NewVNI) {
NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
MachineInstr *CopyInstr = I->second;
CopyInstr->getOperand(1).setIsKill(true);
}
LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
NewLI.addRange(NewLR);
LI->removeInterval(DestReg);
MRI->replaceRegWith(DestReg, NewReg);
}
for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
E = InsertedSrcCopySet.end(); I != E; ++I) {
MachineBasicBlock *MBB = I->first;
unsigned SrcReg = I->second;
if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
SrcReg = RenamedRegister;
LiveInterval &SrcLI = LI->getInterval(SrcReg);
bool isLiveOut = false;
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI) {
if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
isLiveOut = true;
break;
}
}
if (isLiveOut)
continue;
MachineOperand *LastUse = findLastUse(MBB, SrcReg);
assert(LastUse);
SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
SrcLI.removeRange(LastUseIndex.getRegSlot(), LI->getMBBEndIdx(MBB));
LastUse->setIsKill(true);
}
Allocator.Reset();
RegNodeMap.clear();
PHISrcDefs.clear();
InsertedSrcCopySet.clear();
InsertedSrcCopyMap.clear();
InsertedDestCopies.clear();
return Changed;
}
void StrongPHIElimination::addReg(unsigned Reg) {
if (RegNodeMap.count(Reg))
return;
RegNodeMap[Reg] = new (Allocator) Node(Reg);
}
StrongPHIElimination::Node*
StrongPHIElimination::Node::getLeader() {
Node *N = this;
Node *Parent = parent.getPointer();
Node *Grandparent = Parent->parent.getPointer();
while (Parent != Grandparent) {
N->parent.setPointer(Grandparent);
N = Grandparent;
Parent = Parent->parent.getPointer();
Grandparent = Parent->parent.getPointer();
}
return Parent;
}
unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
if (RI == RegNodeMap.end())
return 0;
Node *Node = RI->second;
if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
return 0;
return Node->getLeader()->value;
}
void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
Node *Node1 = RegNodeMap[Reg1]->getLeader();
Node *Node2 = RegNodeMap[Reg2]->getLeader();
if (Node1->rank > Node2->rank) {
Node2->parent.setPointer(Node1->getLeader());
} else if (Node1->rank < Node2->rank) {
Node1->parent.setPointer(Node2->getLeader());
} else if (Node1 != Node2) {
Node2->parent.setPointer(Node1->getLeader());
Node1->rank++;
}
}
void StrongPHIElimination::isolateReg(unsigned Reg) {
Node *Node = RegNodeMap[Reg];
Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
}
unsigned StrongPHIElimination::getPHIColor(MachineInstr *PHI) {
assert(PHI->isPHI());
unsigned DestReg = PHI->getOperand(0).getReg();
Node *DestNode = RegNodeMap[DestReg];
if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
return 0;
for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
unsigned SrcColor = getRegColor(PHI->getOperand(i).getReg());
if (SrcColor)
return SrcColor;
}
return 0;
}
void StrongPHIElimination::isolatePHI(MachineInstr *PHI) {
assert(PHI->isPHI());
Node *Node = RegNodeMap[PHI->getOperand(0).getReg()];
Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
}
void
StrongPHIElimination::SplitInterferencesForBasicBlock(
MachineBasicBlock &MBB,
DenseMap<unsigned, unsigned> &CurrentDominatingParent,
DenseMap<unsigned, unsigned> &ImmediateDominatingParent) {
std::vector<MachineInstr*> &DefInstrs = PHISrcDefs[&MBB];
std::sort(DefInstrs.begin(), DefInstrs.end(), MIIndexCompare(LI));
for (std::vector<MachineInstr*>::const_iterator BBI = DefInstrs.begin(),
BBE = DefInstrs.end(); BBI != BBE; ++BBI) {
for (MachineInstr::const_mop_iterator I = (*BBI)->operands_begin(),
E = (*BBI)->operands_end(); I != E; ++I) {
const MachineOperand &MO = *I;
if (!MO.isReg() || !MO.isDef())
continue;
unsigned DestReg = MO.getReg();
if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg))
continue;
unsigned DestColor = getRegColor(DestReg);
if (!DestColor)
continue;
unsigned &CurrentParent = CurrentDominatingParent[DestColor];
unsigned NewParent = CurrentParent;
if (NewParent == DestReg)
continue;
while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), *BBI)
|| !getRegColor(NewParent)))
NewParent = ImmediateDominatingParent[NewParent];
if (NewParent
&& LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(*BBI))) {
isolateReg(DestReg);
CurrentParent = NewParent;
} else {
ImmediateDominatingParent[DestReg] = NewParent;
CurrentParent = DestReg;
}
}
}
CurrentPHIForColor.clear();
for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(),
SE = MBB.succ_end(); SI != SE; ++SI) {
for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
BBI != BBE && BBI->isPHI(); ++BBI) {
MachineInstr *PHI = BBI;
unsigned Color = getPHIColor(PHI);
if (!Color)
continue;
unsigned PredIndex;
for (PredIndex = 1; PredIndex < PHI->getNumOperands(); PredIndex += 2) {
if (PHI->getOperand(PredIndex + 1).getMBB() == &MBB)
break;
}
assert(PredIndex < PHI->getNumOperands());
unsigned PredOperandReg = PHI->getOperand(PredIndex).getReg();
unsigned &CurrentParent = CurrentDominatingParent[Color];
unsigned NewParent = CurrentParent;
while (NewParent
&& (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
|| !getRegColor(NewParent)))
NewParent = ImmediateDominatingParent[NewParent];
CurrentParent = NewParent;
if (NewParent && LI->isLiveOutOfMBB(LI->getInterval(NewParent), &MBB)
&& NewParent != PredOperandReg)
isolateReg(NewParent);
std::pair<MachineInstr*, unsigned>
&CurrentPHI = CurrentPHIForColor[Color];
if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
isolatePHI(PHI);
else
CurrentPHI = std::make_pair(PHI, PredOperandReg);
}
}
}
void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
MachineBasicBlock *MBB) {
assert(PHI->isPHI());
++NumPHIsLowered;
unsigned PHIColor = getPHIColor(PHI);
for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
MachineOperand &SrcMO = PHI->getOperand(i);
if (SrcMO.isUndef())
continue;
unsigned SrcReg = SrcMO.getReg();
assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
"Machine PHI Operands must all be virtual registers!");
MachineBasicBlock *PredBB = PHI->getOperand(i + 1).getMBB();
unsigned SrcColor = getRegColor(SrcReg);
if (PHIColor && SrcColor == PHIColor) {
LiveInterval &SrcInterval = LI->getInterval(SrcReg);
SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
VNInfo *SrcVNI = SrcInterval.getVNInfoBefore(PredIndex);
assert(SrcVNI);
SrcVNI->setHasPHIKill(true);
continue;
}
unsigned CopyReg = 0;
if (PHIColor) {
SrcCopyMap::const_iterator I
= InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor));
CopyReg
= I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0;
}
if (!CopyReg) {
const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
CopyReg = MRI->createVirtualRegister(RC);
MachineBasicBlock::iterator
CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
unsigned SrcSubReg = SrcMO.getSubReg();
MachineInstr *CopyInstr = BuildMI(*PredBB,
CopyInsertPoint,
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
CopyReg).addReg(SrcReg, 0, SrcSubReg);
LI->InsertMachineInstrInMaps(CopyInstr);
++NumSrcCopiesInserted;
LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));
addReg(CopyReg);
if (PHIColor) {
unionRegs(PHIColor, CopyReg);
assert(getRegColor(CopyReg) != CopyReg);
} else {
PHIColor = CopyReg;
assert(getRegColor(CopyReg) == CopyReg);
}
if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr;
}
SrcMO.setReg(CopyReg);
LiveInterval &SrcLI = LI->getInterval(SrcReg);
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
}
unsigned DestReg = PHI->getOperand(0).getReg();
unsigned DestColor = getRegColor(DestReg);
if (PHIColor && DestColor == PHIColor) {
LiveInterval &DestLI = LI->getInterval(DestReg);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getRegSlot());
assert(DestVNI);
DestVNI->setIsPHIDef(true);
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
DestVNI->def = MBBStartIndex;
DestLI.addRange(LiveRange(MBBStartIndex,
PHIIndex.getRegSlot(),
DestVNI));
return;
}
const TargetRegisterClass *RC = MRI->getRegClass(DestReg);
unsigned CopyReg = MRI->createVirtualRegister(RC);
MachineInstr *CopyInstr = BuildMI(*MBB,
MBB->SkipPHIsAndLabels(MBB->begin()),
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
DestReg).addReg(CopyReg);
LI->InsertMachineInstrInMaps(CopyInstr);
PHI->getOperand(0).setReg(CopyReg);
++NumDestCopiesInserted;
LiveInterval &CopyLI = LI->getOrCreateInterval(CopyReg);
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex,
LI->getVNInfoAllocator());
CopyVNI->setIsPHIDef(true);
CopyLI.addRange(LiveRange(MBBStartIndex,
DestCopyIndex.getRegSlot(),
CopyVNI));
LiveInterval &DestLI = LI->getOrCreateInterval(DestReg);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
DestLI.removeRange(PHIIndex.getRegSlot(), DestCopyIndex.getRegSlot());
VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
assert(DestVNI);
DestVNI->def = DestCopyIndex.getRegSlot();
InsertedDestCopies[CopyReg] = CopyInstr;
}
void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
if (Reg == NewReg)
return;
LiveInterval &OldLI = LI->getInterval(Reg);
LiveInterval &NewLI = LI->getInterval(NewReg);
DenseMap<VNInfo*, VNInfo*> VNMap;
for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
LRI != LRE; ++LRI) {
LiveRange OldLR = *LRI;
VNInfo *OldVN = OldLR.valno;
VNInfo *&NewVN = VNMap[OldVN];
if (!NewVN) {
NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
VNMap[OldVN] = NewVN;
}
LiveRange LR(OldLR.start, OldLR.end, NewVN);
NewLI.addRange(LR);
}
LI->removeInterval(Reg);
MRI->replaceRegWith(Reg, NewReg);
}