diff options
Diffstat (limited to 'lib/CodeGen/LiveVariables.cpp')
| -rw-r--r-- | lib/CodeGen/LiveVariables.cpp | 394 |
1 files changed, 394 insertions, 0 deletions
diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp new file mode 100644 index 0000000000..cb034c017a --- /dev/null +++ b/lib/CodeGen/LiveVariables.cpp @@ -0,0 +1,394 @@ +//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// +// +// 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 +// the value, but it is never used) and the set of registers that are used by +// the instruction, but are never used after the instruction (i.e., they are +// killed). +// +// This class computes live variables using are sparse implementation based on +// the machine code SSA form. This class computes live variable information for +// each virtual and _register allocatable_ physical register in a function. It +// uses the dominance properties of SSA form to efficiently compute live +// variables for virtual registers, and assumes that physical registers are only +// live within a single basic block (allowing it to do a single local analysis +// 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. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/MRegisterInfo.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#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"); + +LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { + assert(MRegisterInfo::isVirtualRegister(RegIdx) && + "getVarInfo: not a virtual register!"); + RegIdx -= MRegisterInfo::FirstVirtualRegister; + if (RegIdx >= VirtRegInfo.size()) { + if (RegIdx >= 2*VirtRegInfo.size()) + VirtRegInfo.resize(RegIdx*2); + else + VirtRegInfo.resize(2*VirtRegInfo.size()); + } + 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) { + unsigned BBNum = MBB->getNumber(); + + // Check to see if this basic block is one of the killing blocks. If so, + // remove it... + for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) + if (VRInfo.Kills[i]->getParent() == MBB) { + VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry + break; + } + + if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion + + if (VRInfo.AliveBlocks.size() <= BBNum) + VRInfo.AliveBlocks.resize(BBNum+1); // Make space... + + if (VRInfo.AliveBlocks[BBNum]) + return; // We already know the block is live + + // 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); +} + +void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, + MachineInstr *MI) { + assert(VRInfo.DefInst && "Register use before def!"); + + // Check to see if this basic block is already a kill block... + if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { + // Yes, this register is killed in this basic block already. Increase the + // live range by updating the kill instruction. + VRInfo.Kills.back() = MI; + return; + } + +#ifndef NDEBUG + for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) + assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); +#endif + + assert(MBB != VRInfo.DefInst->getParent() && + "Should have kill for defblock!"); + + // Add a new kill entry for this basic block. + VRInfo.Kills.push_back(MI); + + // Update all dominating blocks to mark them known live. + for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), + E = MBB->pred_end(); PI != E; ++PI) + MarkVirtRegAliveInBlock(VRInfo, *PI); +} + +void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { + PhysRegInfo[Reg] = MI; + PhysRegUsed[Reg] = true; + + for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + unsigned Alias = *AliasSet; ++AliasSet) { + PhysRegInfo[Alias] = MI; + PhysRegUsed[Alias] = true; + } +} + +void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { + // Does this kill a previous version of this register? + if (MachineInstr *LastUse = PhysRegInfo[Reg]) { + if (PhysRegUsed[Reg]) + RegistersKilled[LastUse].push_back(Reg); + else + RegistersDead[LastUse].push_back(Reg); + } + PhysRegInfo[Reg] = MI; + PhysRegUsed[Reg] = false; + + for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + unsigned Alias = *AliasSet; ++AliasSet) { + if (MachineInstr *LastUse = PhysRegInfo[Alias]) { + if (PhysRegUsed[Alias]) + RegistersKilled[LastUse].push_back(Alias); + else + RegistersDead[LastUse].push_back(Alias); + } + PhysRegInfo[Alias] = MI; + PhysRegUsed[Alias] = false; + } +} + +bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { + const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); + RegInfo = MF.getTarget().getRegisterInfo(); + assert(RegInfo && "Target doesn't have register information?"); + + AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF); + + // PhysRegInfo - Keep track of which instruction was the last use of a + // physical register. This is a purely local property, because all physical + // register references as presumed dead across basic blocks. + // + PhysRegInfo = (MachineInstr**)alloca(sizeof(MachineInstr*) * + RegInfo->getNumRegs()); + PhysRegUsed = (bool*)alloca(sizeof(bool)*RegInfo->getNumRegs()); + std::fill(PhysRegInfo, PhysRegInfo+RegInfo->getNumRegs(), (MachineInstr*)0); + + /// Get some space for a respectable number of registers... + VirtRegInfo.resize(64); + + // Mark live-in registers as live-in. + for (MachineFunction::livein_iterator I = MF.livein_begin(), + E = MF.livein_end(); I != E; ++I) { + assert(MRegisterInfo::isPhysicalRegister(I->first) && + "Cannot have a live-in virtual register!"); + HandlePhysRegDef(I->first, 0); + } + + // 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 + // 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) { + MachineBasicBlock *MBB = *DFI; + unsigned BBNum = MBB->getNumber(); + + // Loop over all of the instructions, processing them. + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + MachineInstr *MI = I; + const TargetInstrDescriptor &MID = TII.get(MI->getOpcode()); + + // Process all of the operands of the instruction... + unsigned NumOperandsToProcess = MI->getNumOperands(); + + // Unless it is a PHI node. In this case, ONLY process the DEF, not any + // of the uses. They will be handled in other basic blocks. + if (MI->getOpcode() == TargetInstrInfo::PHI) + NumOperandsToProcess = 1; + + // Loop over implicit uses, using them. + 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 (MRegisterInfo::isVirtualRegister(MO.getReg())){ + HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); + } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && + AllocatablePhysicalRegisters[MO.getReg()]) { + HandlePhysRegUse(MO.getReg(), MI); + } + } + } + + // Loop over implicit defs, defining them. + 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 (MRegisterInfo::isVirtualRegister(MO.getReg())) { + VarInfo &VRInfo = getVarInfo(MO.getReg()); + + assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); + VRInfo.DefInst = MI; + // Defaults to dead + VRInfo.Kills.push_back(MI); + } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && + AllocatablePhysicalRegisters[MO.getReg()]) { + HandlePhysRegDef(MO.getReg(), MI); + } + } + } + } + + // Handle any virtual assignments from PHI nodes which might be at the + // 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... + } + } + } + } + } + + // Finally, if the last block in the function is a return, make sure to mark + // it as using all of the live-out values in the function. + if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) { + MachineInstr *Ret = &MBB->back(); + for (MachineFunction::liveout_iterator I = MF.liveout_begin(), + E = MF.liveout_end(); I != E; ++I) { + assert(MRegisterInfo::isPhysicalRegister(*I) && + "Cannot have a live-in virtual register!"); + HandlePhysRegUse(*I, Ret); + } + } + + // Loop over PhysRegInfo, killing any registers that are available at the + // end of the basic block. This also resets the PhysRegInfo map. + for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) + if (PhysRegInfo[i]) + HandlePhysRegDef(i, 0); + } + + // Convert the information we have gathered into VirtRegInfo and transform it + // into a form usable by RegistersKilled. + // + 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[VirtRegInfo[i].Kills[j]].push_back( + i + MRegisterInfo::FirstVirtualRegister); + + else + 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. +#ifndef NDEBUG + for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i) + assert(Visited.count(&*i) != 0 && "unreachable basic block found"); +#endif + + return false; +} + +/// 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 LiveVariables::instructionChanged(MachineInstr *OldMI, + MachineInstr *NewMI) { + // If the instruction defines any virtual registers, update the VarInfo for + // the instruction. + for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = OldMI->getOperand(i); + if (MO.isRegister() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) { + unsigned Reg = MO.getReg(); + VarInfo &VI = getVarInfo(Reg); + if (MO.isDef()) { + // Update the defining instruction. + if (VI.DefInst == OldMI) + VI.DefInst = NewMI; + } + if (MO.isUse()) { + // 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 + } + } + } + + // Move the killed information over... + killed_iterator I, E; + tie(I, E) = killed_range(OldMI); + 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); + 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); + } +} |