#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Config/alloca.h"
+#include <algorithm>
+#include <iostream>
using namespace llvm;
-static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis");
+static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis");
+
+void LiveVariables::VarInfo::dump() const {
+ std::cerr << "Register Defined by: ";
+ if (DefInst)
+ std::cerr << *DefInst;
+ else
+ std::cerr << "<null>\n";
+ std::cerr << " Alive in blocks: ";
+ for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i)
+ if (AliveBlocks[i]) std::cerr << i << ", ";
+ std::cerr << "\n Killed by:";
+ if (Kills.empty())
+ std::cerr << " No instructions.\n";
+ else {
+ for (unsigned i = 0, e = Kills.size(); i != e; ++i)
+ std::cerr << "\n #" << i << ": " << *Kills[i];
+ std::cerr << "\n";
+ }
+}
LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
assert(MRegisterInfo::isVirtualRegister(RegIdx) &&
return VirtRegInfo[RegIdx];
}
+bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const {
+ std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I =
+ RegistersKilled.find(MI);
+ if (I == RegistersKilled.end()) return false;
+
+ // Do a binary search, as these lists can grow pretty big, particularly for
+ // call instructions on targets with lots of call-clobbered registers.
+ return std::binary_search(I->second.begin(), I->second.end(), Reg);
+}
+bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const {
+ std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I =
+ RegistersDead.find(MI);
+ if (I == RegistersDead.end()) return false;
+
+ // Do a binary search, as these lists can grow pretty big, particularly for
+ // call instructions on targets with lots of call-clobbered registers.
+ return std::binary_search(I->second.begin(), I->second.end(), Reg);
+}
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
MachineBasicBlock *MBB) {
// Does this kill a previous version of this register?
if (MachineInstr *LastUse = PhysRegInfo[Reg]) {
if (PhysRegUsed[Reg])
- RegistersKilled.insert(std::make_pair(LastUse, Reg));
+ RegistersKilled[LastUse].push_back(Reg);
else
- RegistersDead.insert(std::make_pair(LastUse, Reg));
+ RegistersDead[LastUse].push_back(Reg);
}
PhysRegInfo[Reg] = MI;
PhysRegUsed[Reg] = false;
unsigned Alias = *AliasSet; ++AliasSet) {
if (MachineInstr *LastUse = PhysRegInfo[Alias]) {
if (PhysRegUsed[Alias])
- RegistersKilled.insert(std::make_pair(LastUse, Alias));
+ RegistersKilled[LastUse].push_back(Alias);
else
- RegistersDead.insert(std::make_pair(LastUse, Alias));
+ RegistersDead[LastUse].push_back(Alias);
}
PhysRegInfo[Alias] = MI;
PhysRegUsed[Alias] = false;
HandlePhysRegDef(I->first, 0);
}
+ analyzePHINodes(MF);
+
// Calculate live variable information in depth first order on the CFG of the
// function. This guarantees that we will see the definition of a virtual
// register before its uses due to dominance properties of SSA (except for PHI
NumOperandsToProcess = 1;
// Loop over implicit uses, using them.
- for (const unsigned *ImplicitUses = MID.ImplicitUses;
- *ImplicitUses; ++ImplicitUses)
- HandlePhysRegUse(*ImplicitUses, MI);
+ if (MID.ImplicitUses) {
+ for (const unsigned *ImplicitUses = MID.ImplicitUses;
+ *ImplicitUses; ++ImplicitUses)
+ HandlePhysRegUse(*ImplicitUses, MI);
+ }
// Process all explicit uses...
for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
MachineOperand &MO = MI->getOperand(i);
- if (MO.isUse() && MO.isRegister() && MO.getReg()) {
+ if (MO.isRegister() && MO.isUse() && MO.getReg()) {
if (MRegisterInfo::isVirtualRegister(MO.getReg())){
HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI);
} else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
}
// Loop over implicit defs, defining them.
- for (const unsigned *ImplicitDefs = MID.ImplicitDefs;
- *ImplicitDefs; ++ImplicitDefs)
- HandlePhysRegDef(*ImplicitDefs, MI);
+ if (MID.ImplicitDefs) {
+ for (const unsigned *ImplicitDefs = MID.ImplicitDefs;
+ *ImplicitDefs; ++ImplicitDefs)
+ HandlePhysRegDef(*ImplicitDefs, MI);
+ }
// Process all explicit defs...
for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
MachineOperand &MO = MI->getOperand(i);
- if (MO.isDef() && MO.isRegister() && MO.getReg()) {
+ if (MO.isRegister() && MO.isDef() && MO.getReg()) {
if (MRegisterInfo::isVirtualRegister(MO.getReg())) {
VarInfo &VRInfo = getVarInfo(MO.getReg());
// bottom of this basic block. We check all of our successor blocks to see
// if they have PHI nodes, and if so, we simulate an assignment at the end
// of the current block.
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- E = MBB->succ_end(); SI != E; ++SI) {
- MachineBasicBlock *Succ = *SI;
-
- // PHI nodes are guaranteed to be at the top of the block...
- for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end();
- MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) {
- for (unsigned i = 1; ; i += 2) {
- assert(MI->getNumOperands() > i+1 &&
- "Didn't find an entry for our predecessor??");
- if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.getVRegValueOrNull()) {
- VarInfo &VRInfo = getVarInfo(MO.getReg());
-
- // Only mark it alive only in the block we are representing...
- MarkVirtRegAliveInBlock(VRInfo, MBB);
- break; // Found the PHI entry for this block...
- }
- }
- }
+ if (!PHIVarInfo[MBB].empty()) {
+ std::vector<unsigned>& VarInfoVec = PHIVarInfo[MBB];
+
+ for (std::vector<unsigned>::iterator I = VarInfoVec.begin(),
+ E = VarInfoVec.end(); I != E; ++I) {
+ VarInfo& VRInfo = getVarInfo(*I);
+ assert(VRInfo.DefInst && "Register use before def (or no def)!");
+
+ // Only mark it alive only in the block we are representing.
+ MarkVirtRegAliveInBlock(VRInfo, MBB);
}
}
for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i)
for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) {
if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst)
- RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j],
- i + MRegisterInfo::FirstVirtualRegister));
+ RegistersDead[VirtRegInfo[i].Kills[j]].push_back(
+ i + MRegisterInfo::FirstVirtualRegister);
else
- RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j],
- i + MRegisterInfo::FirstVirtualRegister));
+ RegistersKilled[VirtRegInfo[i].Kills[j]].push_back(
+ i + MRegisterInfo::FirstVirtualRegister);
}
+ // Walk through the RegistersKilled/Dead sets, and sort the registers killed
+ // or dead. This allows us to use efficient binary search for membership
+ // testing.
+ for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
+ I = RegistersKilled.begin(), E = RegistersKilled.end(); I != E; ++I)
+ std::sort(I->second.begin(), I->second.end());
+ for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
+ I = RegistersDead.begin(), E = RegistersDead.end(); I != E; ++I)
+ std::sort(I->second.begin(), I->second.end());
+
// Check to make sure there are no unreachable blocks in the MC CFG for the
// function. If so, it is due to a bug in the instruction selector or some
// other part of the code generator if this happens.
assert(Visited.count(&*i) != 0 && "unreachable basic block found");
#endif
+ PHIVarInfo.clear();
return false;
}
// Move the killed information over...
killed_iterator I, E;
tie(I, E) = killed_range(OldMI);
- std::vector<unsigned> Regs;
- for (killed_iterator A = I; A != E; ++A)
- Regs.push_back(A->second);
- RegistersKilled.erase(I, E);
-
- for (unsigned i = 0, e = Regs.size(); i != e; ++i)
- RegistersKilled.insert(std::make_pair(NewMI, Regs[i]));
- Regs.clear();
+ if (I != E) {
+ std::vector<unsigned> &V = RegistersKilled[NewMI];
+ bool WasEmpty = V.empty();
+ V.insert(V.end(), I, E);
+ if (!WasEmpty)
+ std::sort(V.begin(), V.end()); // Keep the reg list sorted.
+ RegistersKilled.erase(OldMI);
+ }
// Move the dead information over...
tie(I, E) = dead_range(OldMI);
- for (killed_iterator A = I; A != E; ++A)
- Regs.push_back(A->second);
- RegistersDead.erase(I, E);
+ if (I != E) {
+ std::vector<unsigned> &V = RegistersDead[NewMI];
+ bool WasEmpty = V.empty();
+ V.insert(V.end(), I, E);
+ if (!WasEmpty)
+ std::sort(V.begin(), V.end()); // Keep the reg list sorted.
+ RegistersDead.erase(OldMI);
+ }
+}
+
+/// removeVirtualRegistersKilled - Remove all killed info for the specified
+/// instruction.
+void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
+ std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
+ RegistersKilled.find(MI);
+ if (I == RegistersKilled.end()) return;
+
+ std::vector<unsigned> &Regs = I->second;
+ for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+ if (MRegisterInfo::isVirtualRegister(Regs[i])) {
+ bool removed = getVarInfo(Regs[i]).removeKill(MI);
+ assert(removed && "kill not in register's VarInfo?");
+ }
+ }
+ RegistersKilled.erase(I);
+}
+
+/// removeVirtualRegistersDead - Remove all of the dead registers for the
+/// specified instruction from the live variable information.
+void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) {
+ std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
+ RegistersDead.find(MI);
+ if (I == RegistersDead.end()) return;
+
+ std::vector<unsigned> &Regs = I->second;
+ for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+ if (MRegisterInfo::isVirtualRegister(Regs[i])) {
+ bool removed = getVarInfo(Regs[i]).removeKill(MI);
+ assert(removed && "kill not in register's VarInfo?");
+ }
+ }
+ RegistersDead.erase(I);
+}
- for (unsigned i = 0, e = Regs.size(); i != e; ++i)
- RegistersDead.insert(std::make_pair(NewMI, Regs[i]));
+/// analyzePHINodes - Gather information about the PHI nodes in here. In
+/// particular, we want to map the variable information of a virtual
+/// register which is used in a PHI node. We map that to the BB the vreg is
+/// coming from.
+///
+void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
+ 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)
+ for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
+ PHIVarInfo[BBI->getOperand(i + 1).getMachineBasicBlock()].
+ push_back(BBI->getOperand(i).getReg());
}
projects / oota-llvm.git / blobdiff