#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Config/alloca.h"
#include <algorithm>
char LiveVariables::ID = 0;
static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis");
+
+void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequiredID(UnreachableMachineBlockElimID);
+ AU.setPreservesAll();
+}
+
void LiveVariables::VarInfo::dump() const {
cerr << " Alive in blocks: ";
- for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i)
- if (AliveBlocks[i]) cerr << i << ", ";
- cerr << " Used in blocks: ";
- for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i)
- if (UsedBlocks[i]) cerr << i << ", ";
+ for (SparseBitVector<>::iterator I = AliveBlocks.begin(),
+ E = AliveBlocks.end(); I != E; ++I)
+ cerr << *I << ", ";
cerr << "\n Killed by:";
if (Kills.empty())
cerr << " No instructions.\n";
else
VirtRegInfo.resize(2*VirtRegInfo.size());
}
- VarInfo &VI = VirtRegInfo[RegIdx];
- VI.AliveBlocks.resize(MF->getNumBlockIDs());
- VI.UsedBlocks.resize(MF->getNumBlockIDs());
- return VI;
+ return VirtRegInfo[RegIdx];
}
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo,
if (MBB == DefBlock) return; // Terminate recursion
- if (VRInfo.AliveBlocks[BBNum])
+ if (VRInfo.AliveBlocks.test(BBNum))
return; // We already know the block is live
// Mark the variable known alive in this bb
- VRInfo.AliveBlocks[BBNum] = true;
+ VRInfo.AliveBlocks.set(BBNum);
for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(),
E = MBB->pred_rend(); PI != E; ++PI)
unsigned BBNum = MBB->getNumber();
VarInfo& VRInfo = getVarInfo(reg);
- VRInfo.UsedBlocks[BBNum] = true;
VRInfo.NumUses++;
// Check to see if this basic block is already a kill block.
// Add a new kill entry for this basic block. If this virtual register is
// already marked as alive in this basic block, that means it is alive in at
// least one of the successor blocks, it's not a kill.
- if (!VRInfo.AliveBlocks[BBNum])
+ if (!VRInfo.AliveBlocks.test(BBNum))
VRInfo.Kills.push_back(MI);
// Update all dominating blocks to mark them as "known live".
MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI);
}
+void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) {
+ VarInfo &VRInfo = getVarInfo(Reg);
+
+ if (VRInfo.AliveBlocks.empty())
+ // If vr is not alive in any block, then defaults to dead.
+ VRInfo.Kills.push_back(MI);
+}
+
/// FindLastPartialDef - Return the last partial def of the specified register.
/// Also returns the sub-register that's defined.
MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg,
LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
true/*IsImp*/));
PhysRegDef[Reg] = LastPartialDef;
- std::set<unsigned> Processed;
+ SmallSet<unsigned, 8> Processed;
for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
unsigned SubReg = *SubRegs; ++SubRegs) {
if (Processed.count(SubReg))
}
}
- // There was an earlier def of a super-register. Add implicit def to that MI.
- //
- // A: EAX = ...
- // B: ... = AX
- //
- // Add implicit def to A if there isn't a use of AX (or EAX) before B.
- if (!PhysRegUse[Reg]) {
- MachineInstr *Def = PhysRegDef[Reg];
- if (Def && !Def->modifiesRegister(Reg))
- Def->addOperand(MachineOperand::CreateReg(Reg,
- true /*IsDef*/,
- true /*IsImp*/));
- }
-
// Remember this use.
PhysRegUse[Reg] = MI;
for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
return true;
}
-bool LiveVariables::HandlePhysRegKill(unsigned Reg) {
+bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) {
if (!PhysRegUse[Reg] && !PhysRegDef[Reg])
return false;
// AX<dead> = AL<imp-def>
// = AL<kill>
// AX =
- std::set<unsigned> PartUses;
+ SmallSet<unsigned, 8> PartUses;
for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
unsigned SubReg = *SubRegs; ++SubRegs) {
if (MachineInstr *Use = PhysRegUse[SubReg]) {
}
}
}
- if (LastRefOrPartRef == PhysRegDef[Reg])
- // Not used at all.
+
+ if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI)
+ // If the last reference is the last def, then it's not used at all.
+ // That is, unless we are currently processing the last reference itself.
LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
/* Partial uses. Mark register def dead and add implicit def of
void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
// What parts of the register are previously defined?
- std::set<unsigned> Live;
+ SmallSet<unsigned, 32> Live;
if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
Live.insert(Reg);
for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS)
// Start from the largest piece, find the last time any part of the register
// is referenced.
- if (!HandlePhysRegKill(Reg)) {
+ if (!HandlePhysRegKill(Reg, MI)) {
// Only some of the sub-registers are used.
for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
unsigned SubReg = *SubRegs; ++SubRegs) {
if (!Live.count(SubReg))
// Skip if this sub-register isn't defined.
continue;
- if (HandlePhysRegKill(SubReg)) {
+ if (HandlePhysRegKill(SubReg, MI)) {
Live.erase(SubReg);
for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
Live.erase(*SS);
if (MI) {
// Does this extend the live range of a super-register?
- std::set<unsigned> Processed;
+ SmallSet<unsigned, 8> Processed;
for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg);
unsigned SuperReg = *SuperRegs; ++SuperRegs) {
if (Processed.count(SuperReg))
}
} else {
// Otherwise, the super register is killed.
- if (HandlePhysRegKill(SuperReg)) {
+ if (HandlePhysRegKill(SuperReg, MI)) {
PhysRegDef[SuperReg] = NULL;
PhysRegUse[SuperReg] = NULL;
for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) {
SmallVector<unsigned, 4> DefRegs;
for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
const MachineOperand &MO = MI->getOperand(i);
- if (MO.isRegister() && MO.getReg()) {
- unsigned MOReg = MO.getReg();
- if (!MOReg)
- continue;
- if (MO.isUse())
- UseRegs.push_back(MOReg);
- if (MO.isDef())
- DefRegs.push_back(MOReg);
- }
+ if (!MO.isReg() || MO.getReg() == 0)
+ continue;
+ unsigned MOReg = MO.getReg();
+ if (MO.isUse())
+ UseRegs.push_back(MOReg);
+ if (MO.isDef())
+ DefRegs.push_back(MOReg);
}
// Process all uses.
unsigned MOReg = UseRegs[i];
if (TargetRegisterInfo::isVirtualRegister(MOReg))
HandleVirtRegUse(MOReg, MBB, MI);
- else if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
- !ReservedRegisters[MOReg])
+ else if (!ReservedRegisters[MOReg])
HandlePhysRegUse(MOReg, MI);
}
// Process all defs.
for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
unsigned MOReg = DefRegs[i];
- if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
- VarInfo &VRInfo = getVarInfo(MOReg);
-
- if (VRInfo.AliveBlocks.none())
- // If vr is not alive in any block, then defaults to dead.
- VRInfo.Kills.push_back(MI);
- } else if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
- !ReservedRegisters[MOReg]) {
+ if (TargetRegisterInfo::isVirtualRegister(MOReg))
+ HandleVirtRegDef(MOReg, MI);
+ else if (!ReservedRegisters[MOReg])
HandlePhysRegDef(MOReg, MI);
- }
}
}
return false;
}
-/// instructionChanged - When the address of an instruction changes, this method
-/// should be called so that live variables can update its internal data
-/// structures. This removes the records for OldMI, transfering them to the
-/// records for NewMI.
-void LiveVariables::instructionChanged(MachineInstr *OldMI,
- MachineInstr *NewMI) {
- // If the instruction defines any virtual registers, update the VarInfo,
- // kill and dead information for the instruction.
- for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = OldMI->getOperand(i);
- if (MO.isRegister() && MO.getReg() &&
- TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
- unsigned Reg = MO.getReg();
- VarInfo &VI = getVarInfo(Reg);
- if (MO.isDef()) {
- if (MO.isDead()) {
- MO.setIsDead(false);
- addVirtualRegisterDead(Reg, NewMI);
- }
- }
- if (MO.isKill()) {
- MO.setIsKill(false);
- addVirtualRegisterKilled(Reg, NewMI);
- }
- // If this is a kill of the value, update the VI kills list.
- if (VI.removeKill(OldMI))
- VI.Kills.push_back(NewMI); // Yes, there was a kill of it
- }
- }
+/// replaceKillInstruction - Update register kill info by replacing a kill
+/// instruction with a new one.
+void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI,
+ MachineInstr *NewMI) {
+ VarInfo &VI = getVarInfo(Reg);
+ std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI);
}
/// removeVirtualRegistersKilled - Remove all killed info for the specified
void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isKill()) {
+ if (MO.isReg() && MO.isKill()) {
MO.setIsKill(false);
unsigned Reg = MO.getReg();
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
bool removed = getVarInfo(Reg).removeKill(MI);
assert(removed && "kill not in register's VarInfo?");
- }
- }
- }
-}
-
-/// removeVirtualRegistersDead - Remove all of the dead registers for the
-/// specified instruction from the live variable information.
-void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) {
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isDead()) {
- MO.setIsDead(false);
- unsigned Reg = MO.getReg();
- if (TargetRegisterInfo::isVirtualRegister(Reg)) {
- bool removed = getVarInfo(Reg).removeKill(MI);
- assert(removed && "kill not in register's VarInfo?");
+ removed = true;
}
}
}
projects / oota-llvm.git / blobdiff