//===-- 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;
+ std::vector<MachineInstr*> Kills;
- VarInfo() : DefBlock(0), DefInst(0) {}
+ 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<std::pair<MachineBasicBlock*, MachineInstr*> >::iterator
- i = Kills.begin(); i != Kills.end(); ++i) {
- if (i->second == 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
/// 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);
}
/// removeVirtualRegisterDead - Remove the specified virtual
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