#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Config/alloca.h"
#include <algorithm>
using namespace llvm;
+char LiveVariables::ID = 0;
static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis");
void LiveVariables::VarInfo::dump() const {
}
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
- MachineBasicBlock *MBB) {
+ MachineBasicBlock *MBB,
+ std::vector<MachineBasicBlock*> &WorkList) {
unsigned BBNum = MBB->getNumber();
// Check to see if this basic block is one of the killing blocks. If so,
// Mark the variable known alive in this bb
VRInfo.AliveBlocks[BBNum] = true;
- for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
- E = MBB->pred_end(); PI != E; ++PI)
- MarkVirtRegAliveInBlock(VRInfo, *PI);
+ for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(),
+ E = MBB->pred_rend(); PI != E; ++PI)
+ WorkList.push_back(*PI);
+}
+
+void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
+ MachineBasicBlock *MBB) {
+ std::vector<MachineBasicBlock*> WorkList;
+ MarkVirtRegAliveInBlock(VRInfo, MBB, WorkList);
+ while (!WorkList.empty()) {
+ MachineBasicBlock *Pred = WorkList.back();
+ WorkList.pop_back();
+ MarkVirtRegAliveInBlock(VRInfo, Pred, WorkList);
+ }
}
+
void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
MachineInstr *MI) {
assert(VRInfo.DefInst && "Register use before def!");
PhysRegPartUse[SuperReg] = MI;
}
+bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI,
+ SmallSet<unsigned, 4> &SubKills) {
+ for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg);
+ unsigned SubReg = *SubRegs; ++SubRegs) {
+ MachineInstr *LastRef = PhysRegInfo[SubReg];
+ if (LastRef != RefMI)
+ SubKills.insert(SubReg);
+ else if (!HandlePhysRegKill(SubReg, RefMI, SubKills))
+ SubKills.insert(SubReg);
+ }
+
+ if (*RegInfo->getImmediateSubRegisters(Reg) == 0) {
+ // No sub-registers, just check if reg is killed by RefMI.
+ if (PhysRegInfo[Reg] == RefMI)
+ return true;
+ } else if (SubKills.empty())
+ // None of the sub-registers are killed elsewhere...
+ return true;
+ return false;
+}
+
+void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI,
+ SmallSet<unsigned, 4> &SubKills) {
+ if (SubKills.count(Reg) == 0)
+ addRegisterKilled(Reg, MI, true);
+ else {
+ for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg);
+ unsigned SubReg = *SubRegs; ++SubRegs)
+ addRegisterKills(SubReg, MI, SubKills);
+ }
+}
+
+bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI) {
+ SmallSet<unsigned, 4> SubKills;
+ if (HandlePhysRegKill(Reg, RefMI, SubKills)) {
+ addRegisterKilled(Reg, RefMI);
+ return true;
+ } else {
+ // Some sub-registers are killed by another MI.
+ for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg);
+ unsigned SubReg = *SubRegs; ++SubRegs)
+ addRegisterKills(SubReg, RefMI, SubKills);
+ return false;
+ }
+}
+
void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
// Does this kill a previous version of this register?
if (MachineInstr *LastRef = PhysRegInfo[Reg]) {
- if (PhysRegUsed[Reg])
- addRegisterKilled(Reg, LastRef);
- else if (PhysRegPartUse[Reg])
+ if (PhysRegUsed[Reg]) {
+ if (!HandlePhysRegKill(Reg, LastRef)) {
+ if (PhysRegPartUse[Reg])
+ addRegisterKilled(Reg, PhysRegPartUse[Reg], true);
+ }
+ } else if (PhysRegPartUse[Reg])
// Add implicit use / kill to last use of a sub-register.
addRegisterKilled(Reg, PhysRegPartUse[Reg], true);
else
addRegisterDead(Reg, LastRef);
}
- PhysRegInfo[Reg] = MI;
- PhysRegUsed[Reg] = false;
- PhysRegPartUse[Reg] = NULL;
for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
unsigned SubReg = *SubRegs; ++SubRegs) {
if (MachineInstr *LastRef = PhysRegInfo[SubReg]) {
- if (PhysRegUsed[SubReg])
- addRegisterKilled(SubReg, LastRef);
- else if (PhysRegPartUse[SubReg])
+ if (PhysRegUsed[SubReg]) {
+ if (!HandlePhysRegKill(SubReg, LastRef)) {
+ if (PhysRegPartUse[SubReg])
+ addRegisterKilled(SubReg, PhysRegPartUse[SubReg], true);
+ }
+ } else if (PhysRegPartUse[SubReg])
// Add implicit use / kill to last use of a sub-register.
addRegisterKilled(SubReg, PhysRegPartUse[SubReg], true);
else
addRegisterDead(SubReg, LastRef);
}
- PhysRegInfo[SubReg] = MI;
- PhysRegUsed[SubReg] = false;
}
- if (MI)
+ if (MI) {
for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg);
unsigned SuperReg = *SuperRegs; ++SuperRegs) {
if (PhysRegInfo[SuperReg]) {
MI->addRegOperand(SuperReg, true/*IsDef*/,true/*IsImp*/);
PhysRegInfo[SuperReg] = MI;
PhysRegUsed[SuperReg] = false;
+ PhysRegPartUse[SuperReg] = NULL;
} else {
// Remember this partial def.
PhysRegPartDef[SuperReg].push_back(MI);
}
+ }
+
+ PhysRegInfo[Reg] = MI;
+ PhysRegUsed[Reg] = false;
+ PhysRegPartUse[Reg] = NULL;
+ for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
+ unsigned SubReg = *SubRegs; ++SubRegs) {
+ PhysRegInfo[SubReg] = MI;
+ PhysRegUsed[SubReg] = false;
+ PhysRegPartUse[SubReg] = NULL;
+ }
}
}
// nodes, which are treated as a special case).
//
MachineBasicBlock *Entry = MF->begin();
- std::set<MachineBasicBlock*> Visited;
- for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited),
- E = df_ext_end(Entry, Visited); DFI != E; ++DFI) {
+ SmallPtrSet<MachineBasicBlock*,16> Visited;
+ for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
+ DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
+ DFI != E; ++DFI) {
MachineBasicBlock *MBB = *DFI;
// Mark live-in registers as live-in.
"Cannot have a live-in virtual register!");
HandlePhysRegUse(*I, Ret);
// Add live-out registers as implicit uses.
- Ret->addRegOperand(*I, false, true);
+ if (Ret->findRegisterUseOperandIdx(*I) == -1)
+ Ret->addRegOperand(*I, false, true);
}
}
// Clear some states between BB's. These are purely local information.
for (unsigned i = 0; i != NumRegs; ++i)
PhysRegPartDef[i].clear();
+ std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0);
+ std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false);
std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0);
}
if (VI.DefInst == OldMI)
VI.DefInst = NewMI;
}
- if (MO.isUse()) {
- if (MO.isKill()) {
- MO.unsetIsKill();
- 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
+ if (MO.isKill()) {
+ MO.unsetIsKill();
+ 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
}
}
}
projects / oota-llvm.git / blobdiff