#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;
};
Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); }
- Node* getLeader();
+ Node *getLeader();
PointerIntPair<Node*, 2> parent;
unsigned value;
/// Add a register in a new congruence class containing only itself.
void addReg(unsigned);
- /// Join the congruence classes of two registers.
+ /// Join the congruence classes of two registers. This function is biased
+ /// towards the left argument, i.e. after
+ ///
+ /// addReg(r2);
+ /// unionRegs(r1, r2);
+ ///
+ /// the leader of the unioned congruence class is the same as the leader of
+ /// r1's congruence class prior to the union. This is actually relied upon
+ /// in the copy insertion code.
void unionRegs(unsigned, unsigned);
/// Get the color of a register. The color is 0 if the register has been
/// of the dominator tree.
void SplitInterferencesForBasicBlock(
MachineBasicBlock&,
- DenseMap<unsigned, unsigned>& CurrentDominatingParent,
- DenseMap<unsigned, unsigned>& ImmediateDominatingParent);
+ DenseMap<unsigned, unsigned> &CurrentDominatingParent,
+ DenseMap<unsigned, unsigned> &ImmediateDominatingParent);
// Lowers a PHI instruction, inserting copies of the source and destination
// registers as necessary.
// overlapping lifetimes.
void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
- MachineRegisterInfo* MRI;
- const TargetInstrInfo* TII;
- MachineDominatorTree* DT;
- LiveIntervals* LI;
+ MachineRegisterInfo *MRI;
+ const TargetInstrInfo *TII;
+ MachineDominatorTree *DT;
+ LiveIntervals *LI;
BumpPtrAllocator Allocator;
// sources.
DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > PHISrcDefs;
+ // Maps a color to a pair of a MachineInstr* and a virtual register, which
+ // is the operand of that PHI corresponding to the current basic block.
+ DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
+
// FIXME: Can these two data structures be combined? Would a std::multimap
// be any better?
};
struct MIIndexCompare {
- MIIndexCompare(LiveIntervals* LiveIntervals) : LI(LiveIntervals) { }
+ MIIndexCompare(LiveIntervals *LiveIntervals) : LI(LiveIntervals) { }
- bool operator()(const MachineInstr* LHS, const MachineInstr* RHS) const {
+ bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS);
}
- LiveIntervals* LI;
+ LiveIntervals *LI;
};
} // namespace
+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)
char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
-void StrongPHIElimination::getAnalysisUsage(AnalysisUsage& AU) const {
+void StrongPHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<MachineDominatorTree>();
AU.addRequired<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
-static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
+static MachineOperand *findLastUse(MachineBasicBlock *MBB, unsigned Reg) {
// FIXME: This only needs to check from the first terminator, as only the
// first terminator can use a virtual register.
for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
assert (RI != MBB->rend());
- MachineInstr* MI = &*RI;
+ MachineInstr *MI = &*RI;
for (MachineInstr::mop_iterator OI = MI->operands_begin(),
OE = MI->operands_end(); OI != OE; ++OI) {
- MachineOperand& MO = *OI;
+ MachineOperand &MO = *OI;
if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
return &MO;
}
}
- return NULL;
}
-bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
+bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
MRI = &MF.getRegInfo();
TII = MF.getTarget().getInstrInfo();
DT = &getAnalysis<MachineDominatorTree>();
PHISrcDefs[I].push_back(BBI);
for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
- MachineOperand& SrcMO = BBI->getOperand(i);
+ MachineOperand &SrcMO = BBI->getOperand(i);
unsigned SrcReg = SrcMO.getReg();
addReg(SrcReg);
unionRegs(DestReg, SrcReg);
- for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(SrcReg),
- DE = MRI->def_end(); DI != DE; ++DI) {
- PHISrcDefs[DI->getParent()].push_back(&*DI);
- }
+ MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
+ if (DefMI)
+ PHISrcDefs[DefMI->getParent()].push_back(DefMI);
}
}
}
I != E; ++I) {
MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
while (BBI != BBE && BBI->isPHI()) {
- MachineInstr* PHI = BBI;
+ MachineInstr *PHI = BBI;
assert(PHI->getNumOperands() > 0);
unsigned DestColor = getRegColor(DestReg);
unsigned NewReg = RegRenamingMap[DestColor];
- LiveInterval& DestLI = LI->getInterval(DestReg);
- LiveInterval& NewLI = LI->getInterval(NewReg);
+ 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);
+ LiveRange *DestLR = DestLI.begin();
+ VNInfo *NewVNI = NewLI.getVNInfoAt(DestLR->start);
if (!NewVNI) {
NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
- MachineInstr* CopyInstr = I->second;
+ MachineInstr *CopyInstr = I->second;
CopyInstr->getOperand(1).setIsKill(true);
}
// register.
for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
E = InsertedSrcCopySet.end(); I != E; ++I) {
- MachineBasicBlock* MBB = I->first;
+ MachineBasicBlock *MBB = I->first;
unsigned SrcReg = I->second;
if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
SrcReg = RenamedRegister;
- LiveInterval& SrcLI = LI->getInterval(SrcReg);
+ LiveInterval &SrcLI = LI->getInterval(SrcReg);
bool isLiveOut = false;
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
if (isLiveOut)
continue;
- MachineOperand* LastUse = findLastUse(MBB, SrcReg);
+ MachineOperand *LastUse = findLastUse(MBB, SrcReg);
assert(LastUse);
SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
- SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
+ SrcLI.removeRange(LastUseIndex.getRegSlot(), LI->getMBBEndIdx(MBB));
LastUse->setIsKill(true);
}
- LI->renumber();
-
Allocator.Reset();
RegNodeMap.clear();
PHISrcDefs.clear();
StrongPHIElimination::Node*
StrongPHIElimination::Node::getLeader() {
- Node* parentPointer = parent.getPointer();
- if (parentPointer == this)
- return this;
- Node* newParent = parentPointer->getLeader();
- parent.setPointer(newParent);
- return newParent;
+ 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;
+ 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();
+ Node *Node1 = RegNodeMap[Reg1]->getLeader();
+ Node *Node2 = RegNodeMap[Reg2]->getLeader();
if (Node1->rank > Node2->rank) {
Node2->parent.setPointer(Node1->getLeader());
}
void StrongPHIElimination::isolateReg(unsigned Reg) {
- Node* Node = RegNodeMap[Reg];
+ Node *Node = RegNodeMap[Reg];
Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
}
-unsigned StrongPHIElimination::getPHIColor(MachineInstr* PHI) {
+unsigned StrongPHIElimination::getPHIColor(MachineInstr *PHI) {
assert(PHI->isPHI());
unsigned DestReg = PHI->getOperand(0).getReg();
- Node* DestNode = RegNodeMap[DestReg];
+ Node *DestNode = RegNodeMap[DestReg];
if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
return 0;
return 0;
}
-void StrongPHIElimination::isolatePHI(MachineInstr* PHI) {
+void StrongPHIElimination::isolatePHI(MachineInstr *PHI) {
assert(PHI->isPHI());
- Node* Node = RegNodeMap[PHI->getOperand(0).getReg()];
+ Node *Node = RegNodeMap[PHI->getOperand(0).getReg()];
Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
}
/// interference in multiple distinct sets at once.
void
StrongPHIElimination::SplitInterferencesForBasicBlock(
- MachineBasicBlock& MBB,
- DenseMap<unsigned, unsigned>& CurrentDominatingParent,
- DenseMap<unsigned, unsigned>& ImmediateDominatingParent) {
+ MachineBasicBlock &MBB,
+ DenseMap<unsigned, unsigned> &CurrentDominatingParent,
+ DenseMap<unsigned, unsigned> &ImmediateDominatingParent) {
// Sort defs by their order in the original basic block, as the code below
// assumes that it is processing definitions in dominance order.
- std::vector<MachineInstr*>& DefInstrs = PHISrcDefs[&MBB];
+ 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;
+ const MachineOperand &MO = *I;
// FIXME: This would be faster if it were possible to bail out of checking
// an instruction's operands after the explicit defs, but this is incorrect
// handle it here by tracking defining machine instructions rather than
// virtual registers. For now, we just handle the situation conservatively
// in a way that will possibly lead to false interferences.
- unsigned NewParent = CurrentDominatingParent[DestColor];
+ unsigned &CurrentParent = CurrentDominatingParent[DestColor];
+ unsigned NewParent = CurrentParent;
if (NewParent == DestReg)
continue;
// could be improved by using a heuristic that decides which of the two
// registers to isolate.
isolateReg(DestReg);
- CurrentDominatingParent[DestColor] = NewParent;
+ CurrentParent = NewParent;
} else {
// If there is no interference, update ImmediateDominatingParent and set
// the CurrentDominatingParent for this color to the current register.
ImmediateDominatingParent[DestReg] = NewParent;
- CurrentDominatingParent[DestColor] = DestReg;
+ CurrentParent = DestReg;
}
}
}
// We now walk the PHIs in successor blocks and check for interferences. This
- // is necesary because the use of a PHI's operands are logically contained in
+ // is necessary because the use of a PHI's operands are logically contained in
// the predecessor block. The def of a PHI's destination register is processed
// along with the other defs in a basic block.
- // The map CurrentPHIForColor maps a color to a pair of a MachineInstr* and a
- // virtual register, which is the operand of that PHI corresponding to the
- // current basic block.
- // FIXME: This should use a container that doesn't always perform heap
- // allocation.
- DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
+ 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;
+ MachineInstr *PHI = BBI;
// If a PHI is already isolated, either by being isolated directly or
// having all of its operands isolated, ignore it.
// Pop registers from the stack represented by ImmediateDominatingParent
// until we find a parent that dominates the current instruction.
- unsigned NewParent = CurrentDominatingParent[Color];
+ unsigned &CurrentParent = CurrentDominatingParent[Color];
+ unsigned NewParent = CurrentParent;
while (NewParent
&& (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
|| !getRegColor(NewParent)))
NewParent = ImmediateDominatingParent[NewParent];
- CurrentDominatingParent[Color] = NewParent;
+ CurrentParent = NewParent;
// If there is an interference with a register, always isolate the
// register rather than the PHI. It is also possible to isolate the
&& NewParent != PredOperandReg)
isolateReg(NewParent);
- std::pair<MachineInstr*, unsigned> CurrentPHI = CurrentPHIForColor[Color];
+ std::pair<MachineInstr*, unsigned>
+ &CurrentPHI = CurrentPHIForColor[Color];
// If two PHIs have the same operand from every shared predecessor, then
// they don't actually interfere. Otherwise, isolate the current PHI. This
if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
isolatePHI(PHI);
else
- CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
+ CurrentPHI = std::make_pair(PHI, PredOperandReg);
}
}
}
-void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
- MachineBasicBlock* MBB) {
+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);
+ MachineOperand &SrcMO = PHI->getOperand(i);
// If a source is defined by an implicit def, there is no need to insert a
// copy in the predecessor.
assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
"Machine PHI Operands must all be virtual registers!");
- MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
+ MachineBasicBlock *PredBB = PHI->getOperand(i + 1).getMBB();
unsigned SrcColor = getRegColor(SrcReg);
// If neither the PHI nor the operand were isolated, then we only need to
// set the phi-kill flag on the VNInfo at this PHI.
if (PHIColor && SrcColor == PHIColor) {
- LiveInterval& SrcInterval = LI->getInterval(SrcReg);
+ LiveInterval &SrcInterval = LI->getInterval(SrcReg);
SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
- VNInfo* SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
+ VNInfo *SrcVNI = SrcInterval.getVNInfoBefore(PredIndex);
+ (void)SrcVNI;
assert(SrcVNI);
- SrcVNI->setHasPHIKill(true);
continue;
}
}
if (!CopyReg) {
- const TargetRegisterClass* RC = MRI->getRegClass(SrcReg);
+ 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,
+ MachineInstr *CopyInstr = BuildMI(*PredBB,
CopyInsertPoint,
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
CopyReg).addReg(SrcReg, 0, SrcSubReg);
LI->InsertMachineInstrInMaps(CopyInstr);
+ ++NumSrcCopiesInserted;
// addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
// the newly added range.
// never rely on LiveIntervals being correct while inserting copies.
// FIXME: Should this just count uses at PHIs like the normal PHIElimination
// pass does?
- LiveInterval& SrcLI = LI->getInterval(SrcReg);
+ LiveInterval &SrcLI = LI->getInterval(SrcReg);
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
unsigned DestColor = getRegColor(DestReg);
if (PHIColor && DestColor == PHIColor) {
- LiveInterval& DestLI = LI->getInterval(DestReg);
+ LiveInterval &DestLI = LI->getInterval(DestReg);
// Set the phi-def flag for the VN at this PHI.
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
- VNInfo* DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
+ VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getRegSlot());
assert(DestVNI);
- DestVNI->setIsPHIDef(true);
// Prior to PHI elimination, the live ranges of PHIs begin at their defining
// instruction. After PHI elimination, PHI instructions are replaced by VNs
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
DestVNI->def = MBBStartIndex;
DestLI.addRange(LiveRange(MBBStartIndex,
- PHIIndex.getDefIndex(),
+ PHIIndex.getRegSlot(),
DestVNI));
return;
}
- const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
+ const TargetRegisterClass *RC = MRI->getRegClass(DestReg);
unsigned CopyReg = MRI->createVirtualRegister(RC);
- MachineInstr* CopyInstr = BuildMI(*MBB,
+ 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;
// Add the region from the beginning of MBB to the copy instruction to
// CopyReg's live interval, and give the VNInfo the phidef flag.
- LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
+ LiveInterval &CopyLI = LI->getOrCreateInterval(CopyReg);
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
- VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
- CopyInstr,
+ VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex,
LI->getVNInfoAllocator());
- CopyVNI->setIsPHIDef(true);
CopyLI.addRange(LiveRange(MBBStartIndex,
- DestCopyIndex.getDefIndex(),
+ DestCopyIndex.getRegSlot(),
CopyVNI));
// Adjust DestReg's live interval to adjust for its new definition at
// CopyInstr.
- LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
+ LiveInterval &DestLI = LI->getOrCreateInterval(DestReg);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
- DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
+ DestLI.removeRange(PHIIndex.getRegSlot(), DestCopyIndex.getRegSlot());
- VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
+ VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
assert(DestVNI);
- DestVNI->def = DestCopyIndex.getDefIndex();
+ DestVNI->def = DestCopyIndex.getRegSlot();
InsertedDestCopies[CopyReg] = CopyInstr;
}
if (Reg == NewReg)
return;
- LiveInterval& OldLI = LI->getInterval(Reg);
- LiveInterval& NewLI = LI->getInterval(NewReg);
+ LiveInterval &OldLI = LI->getInterval(Reg);
+ LiveInterval &NewLI = LI->getInterval(NewReg);
// Merge the live ranges of the two registers.
DenseMap<VNInfo*, VNInfo*> VNMap;
for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
LRI != LRE; ++LRI) {
LiveRange OldLR = *LRI;
- VNInfo* OldVN = OldLR.valno;
+ VNInfo *OldVN = OldLR.valno;
- VNInfo*& NewVN = VNMap[OldVN];
+ VNInfo *&NewVN = VNMap[OldVN];
if (!NewVN) {
NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
VNMap[OldVN] = NewVN;