// first redefinition of the vreg that we have seen, go back and change
// the live range in the PHI block to be a different value number.
if (interval.containsOneValue()) {
- // Remove the old range that we now know has an incorrect number.
+
VNInfo *VNI = interval.getValNumInfo(0);
- MachineInstr *Killer = vi.Kills[0];
- SlotIndex Start = getMBBStartIdx(Killer->getParent());
- SlotIndex End = getInstructionIndex(Killer).getDefIndex();
- DEBUG({
- errs() << " Removing [" << Start << "," << End << "] from: ";
- interval.print(errs(), tri_);
- errs() << "\n";
- });
- interval.removeRange(Start, End);
- assert(interval.ranges.size() == 1 &&
- "Newly discovered PHI interval has >1 ranges.");
+ // Phi elimination may have reused the register for multiple identical
+ // phi nodes. There will be a kill per phi. Remove the old ranges that
+ // we now know have an incorrect number.
+ for (unsigned ki=0, ke=vi.Kills.size(); ki != ke; ++ki) {
+ MachineInstr *Killer = vi.Kills[ki];
+ SlotIndex Start = getMBBStartIdx(Killer->getParent());
+ SlotIndex End = getInstructionIndex(Killer).getDefIndex();
+ DEBUG({
+ errs() << "\n\t\trenaming [" << Start << "," << End << "] in: ";
+ interval.print(errs(), tri_);
+ });
+ interval.removeRange(Start, End);
+
+ // Replace the interval with one of a NEW value number. Note that
+ // this value number isn't actually defined by an instruction, weird
+ // huh? :)
+ LiveRange LR(Start, End,
+ interval.getNextValue(SlotIndex(Start, true),
+ 0, false, VNInfoAllocator));
+ LR.valno->setIsPHIDef(true);
+ interval.addRange(LR);
+ LR.valno->addKill(End);
+ }
+
MachineBasicBlock *killMBB = getMBBFromIndex(VNI->def);
VNI->addKill(indexes_->getTerminatorGap(killMBB));
VNI->setHasPHIKill(true);
errs() << " RESULT: ";
interval.print(errs(), tri_);
});
-
- // Replace the interval with one of a NEW value number. Note that this
- // value number isn't actually defined by an instruction, weird huh? :)
- LiveRange LR(Start, End,
- interval.getNextValue(SlotIndex(getMBBStartIdx(Killer->getParent()), true),
- 0, false, VNInfoAllocator));
- LR.valno->setIsPHIDef(true);
- DEBUG(errs() << " replace range with " << LR);
- interval.addRange(LR);
- LR.valno->addKill(End);
- DEBUG({
- errs() << " RESULT: ";
- interval.print(errs(), tri_);
- });
}
// In the case of PHI elimination, each variable definition is only
STATISTIC(NumAtomic, "Number of atomic phis lowered");
STATISTIC(NumSplits, "Number of critical edges split on demand");
+STATISTIC(NumReused, "Number of reused lowered phis");
char PHIElimination::ID = 0;
static RegisterPass<PHIElimination>
DefMI->eraseFromParent();
}
+ // Clean up the lowered PHI instructions.
+ for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end();
+ I != E; ++I)
+ Fn.DeleteMachineInstr(I->first);
+ LoweredPHIs.clear();
+
ImpDefs.clear();
VRegPHIUseCount.clear();
return Changed;
void llvm::PHIElimination::LowerAtomicPHINode(
MachineBasicBlock &MBB,
MachineBasicBlock::iterator AfterPHIsIt) {
+ ++NumAtomic;
// Unlink the PHI node from the basic block, but don't delete the PHI yet.
MachineInstr *MPhi = MBB.remove(MBB.begin());
MachineFunction &MF = *MBB.getParent();
const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
unsigned IncomingReg = 0;
+ bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
// Insert a register to register copy at the top of the current block (but
// after any remaining phi nodes) which copies the new incoming register
BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg);
else {
- IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
+ // Can we reuse an earlier PHI node? This only happens for critical edges,
+ // typically those created by tail duplication.
+ unsigned &entry = LoweredPHIs[MPhi];
+ if (entry) {
+ // An identical PHI node was already lowered. Reuse the incoming register.
+ IncomingReg = entry;
+ reusedIncoming = true;
+ ++NumReused;
+ DEBUG(errs() << "Reusing %reg" << IncomingReg << " for " << *MPhi);
+ } else {
+ entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
+ }
TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC);
}
MachineInstr *PHICopy = prior(AfterPHIsIt);
if (IncomingReg) {
+ LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
+
// Increment use count of the newly created virtual register.
- LV->getVarInfo(IncomingReg).NumUses++;
+ VI.NumUses++;
+
+ // When we are reusing the incoming register, it may already have been
+ // killed in this block. The old kill will also have been inserted at
+ // AfterPHIsIt, so it appears before the current PHICopy.
+ if (reusedIncoming)
+ if (MachineInstr *OldKill = VI.findKill(&MBB)) {
+ DEBUG(errs() << "Remove old kill from " << *OldKill);
+ LV->removeVirtualRegisterKilled(IncomingReg, OldKill);
+ DEBUG(MBB.dump());
+ }
// Add information to LiveVariables to know that the incoming value is
// killed. Note that because the value is defined in several places (once
// Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
- --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(),
+ --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
MPhi->getOperand(i).getReg())];
// Now loop over all of the incoming arguments, changing them to copy into the
FindCopyInsertPoint(opBlock, MBB, SrcReg);
// Insert the copy.
- TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC);
+ if (!reusedIncoming && IncomingReg)
+ TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC);
// Now update live variable information if we have it. Otherwise we're done
if (!LV) continue;
// point later.
// Is it used by any PHI instructions in this block?
- bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0;
+ bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)];
// Okay, if we now know that the value is not live out of the block, we can
// add a kill marker in this block saying that it kills the incoming value!
// terminator instruction at the end of the block may also use the value.
// In this case, we should mark *it* as being the killing block, not the
// copy.
- MachineBasicBlock::iterator KillInst = prior(InsertPos);
+ MachineBasicBlock::iterator KillInst;
MachineBasicBlock::iterator Term = opBlock.getFirstTerminator();
- if (Term != opBlock.end()) {
- if (Term->readsRegister(SrcReg))
- KillInst = Term;
+ if (Term != opBlock.end() && Term->readsRegister(SrcReg)) {
+ KillInst = Term;
// Check that no other terminators use values.
#ifndef NDEBUG
"they are the first terminator in a block!");
}
#endif
+ } else if (reusedIncoming || !IncomingReg) {
+ // We may have to rewind a bit if we didn't insert a copy this time.
+ KillInst = Term;
+ while (KillInst != opBlock.begin())
+ if ((--KillInst)->readsRegister(SrcReg))
+ break;
+ } else {
+ // We just inserted this copy.
+ KillInst = prior(InsertPos);
}
+ assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
// Finally, mark it killed.
LV->addVirtualRegisterKilled(SrcReg, KillInst);
}
}
- // Really delete the PHI instruction now!
- MF.DeleteMachineInstr(MPhi);
- ++NumAtomic;
+ // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
+ if (reusedIncoming || !IncomingReg)
+ MF.DeleteMachineInstr(MPhi);
}
/// analyzePHINodes - Gather information about the PHI nodes in here. In
for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
- ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
+ ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(),
BBI->getOperand(i).getReg())];
}
return NMBB;
}
+
+unsigned
+PHIElimination::PHINodeTraits::getHashValue(const MachineInstr *MI) {
+ if (!MI || MI==getEmptyKey() || MI==getTombstoneKey())
+ return DenseMapInfo<MachineInstr*>::getHashValue(MI);
+ unsigned hash = 0;
+ for (unsigned ni = 1, ne = MI->getNumOperands(); ni != ne; ni += 2)
+ hash = hash*37 + DenseMapInfo<BBVRegPair>::
+ getHashValue(BBVRegPair(MI->getOperand(ni+1).getMBB()->getNumber(),
+ MI->getOperand(ni).getReg()));
+ return hash;
+}
+
+bool PHIElimination::PHINodeTraits::isEqual(const MachineInstr *LHS,
+ const MachineInstr *RHS) {
+ const MachineInstr *EmptyKey = getEmptyKey();
+ const MachineInstr *TombstoneKey = getTombstoneKey();
+ if (!LHS || !RHS || LHS==EmptyKey || RHS==EmptyKey ||
+ LHS==TombstoneKey || RHS==TombstoneKey)
+ return LHS==RHS;
+
+ unsigned ne = LHS->getNumOperands();
+ if (ne != RHS->getNumOperands())
+ return false;
+ // Ignore operand 0, the defined register.
+ for (unsigned ni = 1; ni != ne; ni += 2)
+ if (LHS->getOperand(ni).getReg() != RHS->getOperand(ni).getReg() ||
+ LHS->getOperand(ni+1).getMBB() != RHS->getOperand(ni+1).getMBB())
+ return false;
+ return true;
+}
projects / oota-llvm.git / commitdiff