#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
}
void LiveVariables::VarInfo::dump() const {
- errs() << " Alive in blocks: ";
+ dbgs() << " Alive in blocks: ";
for (SparseBitVector<>::iterator I = AliveBlocks.begin(),
E = AliveBlocks.end(); I != E; ++I)
- errs() << *I << ", ";
- errs() << "\n Killed by:";
+ dbgs() << *I << ", ";
+ dbgs() << "\n Killed by:";
if (Kills.empty())
- errs() << " No instructions.\n";
+ dbgs() << " No instructions.\n";
else {
for (unsigned i = 0, e = Kills.size(); i != e; ++i)
- errs() << "\n #" << i << ": " << *Kills[i];
- errs() << "\n";
+ dbgs() << "\n #" << i << ": " << *Kills[i];
+ dbgs() << "\n";
}
}
/// implicit defs to a machine instruction if there was an earlier def of its
/// super-register.
void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) {
+ MachineInstr *LastDef = PhysRegDef[Reg];
// If there was a previous use or a "full" def all is well.
- if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) {
+ if (!LastDef && !PhysRegUse[Reg]) {
// Otherwise, the last sub-register def implicitly defines this register.
// e.g.
// AH =
}
}
}
+ else if (LastDef && !PhysRegUse[Reg] &&
+ !LastDef->findRegisterDefOperand(Reg))
+ // Last def defines the super register, add an implicit def of reg.
+ LastDef->addOperand(MachineOperand::CreateReg(Reg,
+ true/*IsDef*/, true/*IsImp*/));
// Remember this use.
PhysRegUse[Reg] = MI;
PhysRegUse[SubReg] = MI;
}
+/// FindLastRefOrPartRef - Return the last reference or partial reference of
+/// the specified register.
+MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) {
+ MachineInstr *LastDef = PhysRegDef[Reg];
+ MachineInstr *LastUse = PhysRegUse[Reg];
+ if (!LastDef && !LastUse)
+ return false;
+
+ MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
+ unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
+ unsigned LastPartDefDist = 0;
+ for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+ unsigned SubReg = *SubRegs; ++SubRegs) {
+ MachineInstr *Def = PhysRegDef[SubReg];
+ if (Def && Def != LastDef) {
+ // There was a def of this sub-register in between. This is a partial
+ // def, keep track of the last one.
+ unsigned Dist = DistanceMap[Def];
+ if (Dist > LastPartDefDist)
+ LastPartDefDist = Dist;
+ } else if (MachineInstr *Use = PhysRegUse[SubReg]) {
+ unsigned Dist = DistanceMap[Use];
+ if (Dist > LastRefOrPartRefDist) {
+ LastRefOrPartRefDist = Dist;
+ LastRefOrPartRef = Use;
+ }
+ }
+ }
+
+ return LastRefOrPartRef;
+}
+
bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) {
MachineInstr *LastDef = PhysRegDef[Reg];
MachineInstr *LastUse = PhysRegUse[Reg];
if (NeedDef)
PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
true/*IsDef*/, true/*IsImp*/));
- LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
+ MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
+ if (LastSubRef)
+ LastSubRef->addRegisterKilled(SubReg, TRI, true);
+ else {
+ LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
+ PhysRegUse[SubReg] = LastRefOrPartRef;
+ for (const unsigned *SSRegs = TRI->getSubRegisters(SubReg);
+ unsigned SSReg = *SSRegs; ++SSRegs)
+ PhysRegUse[SSReg] = LastRefOrPartRef;
+ }
for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
PartUses.erase(*SS);
}
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
MachineInstr *MI = I;
+ if (MI->isDebugValue())
+ continue;
DistanceMap.insert(std::make_pair(MI, Dist++));
// Process all of the operands of the instruction...
// Unless it is a PHI node. In this case, ONLY process the DEF, not any
// of the uses. They will be handled in other basic blocks.
- if (MI->getOpcode() == TargetInstrInfo::PHI)
+ if (MI->isPHI())
NumOperandsToProcess = 1;
SmallVector<unsigned, 4> UseRegs;
for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
I != E; ++I)
for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
- BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
+ BBI != BBE && BBI->isPHI(); ++BBI)
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()]
.push_back(BBI->getOperand(i).getReg());
}
-void LiveVariables::addNewBlock(MachineBasicBlock *A, MachineBasicBlock *B) {
- unsigned NumA = A->getNumber();
- unsigned NumB = B->getNumber();
+bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
+ unsigned Reg,
+ MachineRegisterInfo &MRI) {
+ unsigned Num = MBB.getNumber();
- // Update info for all live variables
- for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) {
- VarInfo &VI = VirtRegInfo[i];
+ // Reg is live-through.
+ if (AliveBlocks.test(Num))
+ return true;
- // Anything live through B is also live through A.
- if (VI.AliveBlocks.test(NumB)) {
- VI.AliveBlocks.set(NumA);
- continue;
- }
+ // Registers defined in MBB cannot be live in.
+ const MachineInstr *Def = MRI.getVRegDef(Reg);
+ if (Def && Def->getParent() == &MBB)
+ return false;
- // If we're not killed in B, we are not live in
- if (!VI.findKill(B))
- continue;
+ // Reg was not defined in MBB, was it killed here?
+ return findKill(&MBB);
+}
- unsigned Reg = i+TargetRegisterInfo::FirstVirtualRegister;
+bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {
+ LiveVariables::VarInfo &VI = getVarInfo(Reg);
+
+ // Loop over all of the successors of the basic block, checking to see if
+ // the value is either live in the block, or if it is killed in the block.
+ std::vector<MachineBasicBlock*> OpSuccBlocks;
+ for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
+ E = MBB.succ_end(); SI != E; ++SI) {
+ MachineBasicBlock *SuccMBB = *SI;
+
+ // Is it alive in this successor?
+ unsigned SuccIdx = SuccMBB->getNumber();
+ if (VI.AliveBlocks.test(SuccIdx))
+ return true;
+ OpSuccBlocks.push_back(SuccMBB);
+ }
- // Find a def outside B
- for (MachineRegisterInfo::def_iterator di = MRI->def_begin(Reg),
- de=MRI->def_end(); di != de; ++di) {
- if (di->getParent() != B) {
- // Reg was defined outside B and killed in B - it must be live in.
- VI.AliveBlocks.set(NumA);
- break;
- }
- }
+ // Check to see if this value is live because there is a use in a successor
+ // that kills it.
+ switch (OpSuccBlocks.size()) {
+ case 1: {
+ MachineBasicBlock *SuccMBB = OpSuccBlocks[0];
+ for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
+ if (VI.Kills[i]->getParent() == SuccMBB)
+ return true;
+ break;
+ }
+ case 2: {
+ MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1];
+ for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
+ if (VI.Kills[i]->getParent() == SuccMBB1 ||
+ VI.Kills[i]->getParent() == SuccMBB2)
+ return true;
+ break;
+ }
+ default:
+ std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
+ for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
+ if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
+ VI.Kills[i]->getParent()))
+ return true;
+ }
+ return false;
+}
+
+/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
+/// variables that are live out of DomBB will be marked as passing live through
+/// BB.
+void LiveVariables::addNewBlock(MachineBasicBlock *BB,
+ MachineBasicBlock *DomBB,
+ MachineBasicBlock *SuccBB) {
+ const unsigned NumNew = BB->getNumber();
+
+ // All registers used by PHI nodes in SuccBB must be live through BB.
+ for (MachineBasicBlock::const_iterator BBI = SuccBB->begin(),
+ BBE = SuccBB->end(); BBI != BBE && BBI->isPHI(); ++BBI)
+ for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
+ if (BBI->getOperand(i+1).getMBB() == BB)
+ getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
+
+ // Update info for all live variables
+ for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
+ E = MRI->getLastVirtReg()+1; Reg != E; ++Reg) {
+ VarInfo &VI = getVarInfo(Reg);
+ if (!VI.AliveBlocks.test(NumNew) && VI.isLiveIn(*SuccBB, Reg, *MRI))
+ VI.AliveBlocks.set(NumNew);
}
}
projects / oota-llvm.git / blobdiff