#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Config/alloca.h"
+#include <algorithm>
using namespace llvm;
static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis");
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,
// 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;
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.
// 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);
-
- for (unsigned i = 0, e = Regs.size(); i != e; ++i)
- RegistersDead.insert(std::make_pair(NewMI, Regs[i]));
+ 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);
+ }
}