#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
- /// 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
void unionRegs(unsigned, unsigned);
/// Get the color of a register. The color is 0 if the register has been
- 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.
// Lowers a PHI instruction, inserting copies of the source and destination
// registers as necessary.
// overlapping lifetimes.
void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
// 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;
+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 StrongPHIElimination::ID = 0;
INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
"Eliminate PHI nodes for register allocation, intelligently", false, false)
// 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());
// 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());
for (MachineInstr::mop_iterator OI = MI->operands_begin(),
OE = MI->operands_end(); OI != OE; ++OI) {
for (MachineInstr::mop_iterator OI = MI->operands_begin(),
OE = MI->operands_end(); OI != OE; ++OI) {
unsigned SrcReg = SrcMO.getReg();
addReg(SrcReg);
unionRegs(DestReg, SrcReg);
unsigned SrcReg = SrcMO.getReg();
addReg(SrcReg);
unionRegs(DestReg, SrcReg);
I != E; ++I) {
MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
while (BBI != BBE && BBI->isPHI()) {
I != E; ++I) {
MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
while (BBI != BBE && BBI->isPHI()) {
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.");
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.");
// register.
for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
E = InsertedSrcCopySet.end(); I != E; ++I) {
// register.
for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
E = InsertedSrcCopySet.end(); I != E; ++I) {
unsigned SrcReg = I->second;
if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
SrcReg = RenamedRegister;
unsigned SrcReg = I->second;
if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
SrcReg = RenamedRegister;
- 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;
}
unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
if (RI == RegNodeMap.end())
return 0;
if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
return 0;
return Node->getLeader()->value;
}
void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
return 0;
return Node->getLeader()->value;
}
void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
/// interference in multiple distinct sets at once.
void
StrongPHIElimination::SplitInterferencesForBasicBlock(
/// 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.
// Sort defs by their order in the original basic block, as the code below
// assumes that it is processing definitions in dominance order.
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) {
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) {
// 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
// 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.
// 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.
} else {
// If there is no interference, update ImmediateDominatingParent and set
// the CurrentDominatingParent for this color to the current register.
ImmediateDominatingParent[DestReg] = NewParent;
} else {
// If there is no interference, update ImmediateDominatingParent and set
// the CurrentDominatingParent for this color to the current register.
ImmediateDominatingParent[DestReg] = NewParent;
// the predecessor block. The def of a PHI's destination register is processed
// along with the other defs in a basic block.
// the predecessor block. The def of a PHI's destination register is processed
// along with the other defs in a basic block.
SE = MBB.succ_end(); SI != SE; ++SI) {
for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
BBI != BBE && BBI->isPHI(); ++BBI) {
SE = MBB.succ_end(); SI != SE; ++SI) {
for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
BBI != BBE && BBI->isPHI(); ++BBI) {
// If a PHI is already isolated, either by being isolated directly or
// having all of its operands isolated, ignore it.
// 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.
// Pop registers from the stack represented by ImmediateDominatingParent
// until we find a parent that dominates the current instruction.
while (NewParent
&& (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
|| !getRegColor(NewParent)))
NewParent = ImmediateDominatingParent[NewParent];
while (NewParent
&& (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
|| !getRegColor(NewParent)))
NewParent = ImmediateDominatingParent[NewParent];
// If there is an interference with a register, always isolate the
// register rather than the PHI. It is also possible to isolate the
// If there is an interference with a register, always isolate the
// register rather than the PHI. It is also possible to isolate the
// If two PHIs have the same operand from every shared predecessor, then
// they don't actually interfere. Otherwise, isolate the current PHI. This
// If two PHIs have the same operand from every shared predecessor, then
// they don't actually interfere. Otherwise, isolate the current PHI. This
-void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
- MachineBasicBlock* MBB) {
+void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
+ MachineBasicBlock *MBB) {
// If a source is defined by an implicit def, there is no need to insert a
// copy in the predecessor.
// 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!");
assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
"Machine PHI Operands must all be virtual registers!");
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) {
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) {
CopyReg = MRI->createVirtualRegister(RC);
MachineBasicBlock::iterator
CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
unsigned SrcSubReg = SrcMO.getSubReg();
CopyReg = MRI->createVirtualRegister(RC);
MachineBasicBlock::iterator
CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
unsigned SrcSubReg = SrcMO.getSubReg();
CopyInsertPoint,
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
CopyReg).addReg(SrcReg, 0, SrcSubReg);
LI->InsertMachineInstrInMaps(CopyInstr);
CopyInsertPoint,
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
CopyReg).addReg(SrcReg, 0, SrcSubReg);
LI->InsertMachineInstrInMaps(CopyInstr);
// never rely on LiveIntervals being correct while inserting copies.
// FIXME: Should this just count uses at PHIs like the normal PHIElimination
// pass does?
// never rely on LiveIntervals being correct while inserting copies.
// FIXME: Should this just count uses at PHIs like the normal PHIElimination
// pass does?
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
DestVNI->def = MBBStartIndex;
DestLI.addRange(LiveRange(MBBStartIndex,
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
DestVNI->def = MBBStartIndex;
DestLI.addRange(LiveRange(MBBStartIndex,
MBB->SkipPHIsAndLabels(MBB->begin()),
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
DestReg).addReg(CopyReg);
LI->InsertMachineInstrInMaps(CopyInstr);
PHI->getOperand(0).setReg(CopyReg);
MBB->SkipPHIsAndLabels(MBB->begin()),
PHI->getDebugLoc(),
TII->get(TargetOpcode::COPY),
DestReg).addReg(CopyReg);
LI->InsertMachineInstrInMaps(CopyInstr);
PHI->getOperand(0).setReg(CopyReg);
// Add the region from the beginning of MBB to the copy instruction to
// CopyReg's live interval, and give the VNInfo the phidef flag.
// Add the region from the beginning of MBB to the copy instruction to
// CopyReg's live interval, and give the VNInfo the phidef flag.
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
LI->getVNInfoAllocator());
CopyVNI->setIsPHIDef(true);
CopyLI.addRange(LiveRange(MBBStartIndex,
LI->getVNInfoAllocator());
CopyVNI->setIsPHIDef(true);
CopyLI.addRange(LiveRange(MBBStartIndex,
// 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;
// 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;