//===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
-//
+//
// This file implements the LiveVariable analysis pass. For each machine
// instruction in the function, this pass calculates the set of registers that
// are immediately dead after the instruction (i.e., the instruction calculates
// to resolve physical register lifetimes in each basic block). If a physical
// register is not register allocatable, it is not tracked. This is useful for
// things like the stack pointer and condition codes.
-//
+//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_LIVEVARIABLES_H
class LiveVariables : public MachineFunctionPass {
public:
struct VarInfo {
- /// DefBlock - The basic block which defines this value...
- MachineBasicBlock *DefBlock;
+ /// DefInst - The machine instruction that defines this register.
MachineInstr *DefInst;
/// AliveBlocks - Set of blocks of which this value is alive completely
///
std::vector<bool> AliveBlocks;
- /// Kills - List of MachineBasicblock's which contain the last use of this
- /// virtual register (kill it). This also includes the specific instruction
- /// which kills the value.
+ /// Kills - List of MachineInstruction's which are the last use of this
+ /// virtual register (kill it) in their basic block.
///
- std::vector<std::pair<MachineBasicBlock*, MachineInstr*> > Kills;
-
- VarInfo() : DefBlock(0), DefInst(0) {}
-
- /// removeKill - Delete a kill corresponding to the specified machine instr
- void removeKill(MachineInstr *MI) {
- for (unsigned i = 0; ; ++i) {
- assert(i < Kills.size() && "Machine instr is not a kill!");
- if (Kills[i].second == MI) {
- Kills.erase(Kills.begin()+i);
- return;
+ std::vector<MachineInstr*> Kills;
+
+ VarInfo() : DefInst(0) {}
+
+ /// removeKill - Delete a kill corresponding to the specified
+ /// machine instruction. Returns true if there was a kill
+ /// corresponding to this instruction, false otherwise.
+ bool removeKill(MachineInstr *MI) {
+ for (std::vector<MachineInstr*>::iterator i = Kills.begin(),
+ e = Kills.end(); i != e; ++i)
+ if (*i == MI) {
+ Kills.erase(i);
+ return true;
}
- }
+ return false;
}
};
std::vector<bool> AllocatablePhysicalRegisters;
private: // Intermediate data structures
-
- /// BBMap - Maps LLVM basic blocks to their corresponding machine basic block.
- /// This also provides a numbering of the basic blocks in the function.
- std::map<const BasicBlock*, std::pair<MachineBasicBlock*, unsigned> > BBMap;
-
const MRegisterInfo *RegInfo;
MachineInstr **PhysRegInfo;
bool *PhysRegUsed;
+ void HandlePhysRegUse(unsigned Reg, MachineInstr *MI);
+ void HandlePhysRegDef(unsigned Reg, MachineInstr *MI);
+
public:
virtual bool runOnMachineFunction(MachineFunction &MF);
- /// getMachineBasicBlockIndex - Turn a MachineBasicBlock into an index number
- /// suitable for use with VarInfo's.
- ///
- const std::pair<MachineBasicBlock*, unsigned>
- &getMachineBasicBlockInfo(MachineBasicBlock *MBB) const;
- const std::pair<MachineBasicBlock*, unsigned>
- &getBasicBlockInfo(const BasicBlock *BB) const {
- return BBMap.find(BB)->second;
- }
-
-
/// killed_iterator - Iterate over registers killed by a machine instruction
///
typedef std::multimap<MachineInstr*, unsigned>::iterator killed_iterator;
-
+
/// killed_begin/end - Get access to the range of registers killed by a
/// machine instruction.
killed_iterator killed_begin(MachineInstr *MI) {
return RegistersKilled.equal_range(MI);
}
+ /// KillsRegister - Return true if the specified instruction kills the
+ /// specified register.
+ bool KillsRegister(MachineInstr *MI, unsigned Reg) {
+ std::pair<killed_iterator, killed_iterator> KIP = killed_range(MI);
+ for (; KIP.first != KIP.second; ++KIP.first)
+ if (KIP.first->second == Reg)
+ return true;
+ return false;
+ }
+
killed_iterator dead_begin(MachineInstr *MI) {
return RegistersDead.lower_bound(MI);
}
//===--------------------------------------------------------------------===//
// API to update live variable information
+ /// 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 instructionChanged(MachineInstr *OldMI, MachineInstr *NewMI);
+
/// addVirtualRegisterKilled - Add information about the fact that the
/// specified register is killed after being used by the specified
/// instruction.
///
- void addVirtualRegisterKilled(unsigned IncomingReg, MachineBasicBlock *MBB,
- MachineInstr *MI) {
+ void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI) {
RegistersKilled.insert(std::make_pair(MI, IncomingReg));
- getVarInfo(IncomingReg).Kills.push_back(std::make_pair(MBB, MI));
+ getVarInfo(IncomingReg).Kills.push_back(MI);
+ }
+
+ /// removeVirtualRegisterKilled - Remove the specified virtual
+ /// register from the live variable information. Returns true if the
+ /// variable was marked as killed by the specified instruction,
+ /// false otherwise.
+ bool removeVirtualRegisterKilled(unsigned reg,
+ MachineBasicBlock *MBB,
+ MachineInstr *MI) {
+ if (!getVarInfo(reg).removeKill(MI))
+ return false;
+ for (killed_iterator i = killed_begin(MI), e = killed_end(MI); i != e; ) {
+ if (i->second == reg)
+ RegistersKilled.erase(i++);
+ else
+ ++i;
+ }
+ return true;
}
/// removeVirtualRegistersKilled - Remove all of the specified killed
/// registers from the live variable information.
void removeVirtualRegistersKilled(killed_iterator B, killed_iterator E) {
- for (killed_iterator I = B; I != E; ++I) // Remove VarInfo entries...
- getVarInfo(I->second).removeKill(I->first);
+ for (killed_iterator I = B; I != E; ++I) { // Remove VarInfo entries...
+ bool removed = getVarInfo(I->second).removeKill(I->first);
+ assert(removed && "kill not in register's VarInfo?");
+ }
RegistersKilled.erase(B, E);
}
/// addVirtualRegisterDead - Add information about the fact that the specified
/// register is dead after being used by the specified instruction.
///
- void addVirtualRegisterDead(unsigned IncomingReg, MachineBasicBlock *MBB,
- MachineInstr *MI) {
+ void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI) {
RegistersDead.insert(std::make_pair(MI, IncomingReg));
- getVarInfo(IncomingReg).Kills.push_back(std::make_pair(MBB, MI));
+ getVarInfo(IncomingReg).Kills.push_back(MI);
}
- /// removeVirtualRegistersKilled - Remove all of the specified killed
+ /// removeVirtualRegisterDead - Remove the specified virtual
+ /// register from the live variable information. Returns true if the
+ /// variable was marked dead at the specified instruction, false
+ /// otherwise.
+ bool removeVirtualRegisterDead(unsigned reg,
+ MachineBasicBlock *MBB,
+ MachineInstr *MI) {
+ if (!getVarInfo(reg).removeKill(MI))
+ return false;
+
+ for (killed_iterator i = killed_begin(MI), e = killed_end(MI); i != e; ) {
+ if (i->second == reg)
+ RegistersKilled.erase(i++);
+ else
+ ++i;
+ }
+ return true;
+ }
+
+ /// removeVirtualRegistersDead - Remove all of the specified dead
/// registers from the live variable information.
void removeVirtualRegistersDead(killed_iterator B, killed_iterator E) {
for (killed_iterator I = B; I != E; ++I) // Remove VarInfo entries...
VirtRegInfo.clear();
RegistersKilled.clear();
RegistersDead.clear();
- BBMap.clear();
}
/// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
/// register.
VarInfo &getVarInfo(unsigned RegIdx);
- const std::vector<bool>& getAllocatablePhysicalRegisters() const {
- return AllocatablePhysicalRegisters;
- }
-
- void MarkVirtRegAliveInBlock(VarInfo &VRInfo, const BasicBlock *BB);
+ void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *BB);
void HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
- MachineInstr *MI);
- void HandlePhysRegUse(unsigned Reg, MachineInstr *MI);
- void HandlePhysRegDef(unsigned Reg, MachineInstr *MI);
+ MachineInstr *MI);
};
} // End llvm namespace
projects / oota-llvm.git / blobdiff