include/llvm/CodeGen/LiveVariables.h

   1 //===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
   2 //
   3 // This file implements the LiveVariable analysis pass.  For each machine
   4 // instruction in the function, this pass calculates the set of registers that
   5 // are immediately dead after the instruction (i.e., the instruction calculates
   6 // the value, but it is never used) and the set of registers that are used by
   7 // the instruction, but are never used after the instruction (i.e., they are
   8 // killed).
   9 //
  10 // This class computes live variables using are sparse implementation based on
  11 // the machine code SSA form.  This class computes live variable information for
  12 // each virtual and _register allocatable_ physical register in a function.  It
  13 // uses the dominance properties of SSA form to efficiently compute live
  14 // variables for virtual registers, and assumes that physical registers are only
  15 // live within a single basic block (allowing it to do a single local analysis
  16 // to resolve physical register lifetimes in each basic block).  If a physical
  17 // register is not register allocatable, it is not tracked.  This is useful for
  18 // things like the stack pointer and condition codes.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_CODEGEN_LIVEVARIABLES_H
  23 #define LLVM_CODEGEN_LIVEVARIABLES_H
  24
  25 #include "llvm/CodeGen/MachineFunctionPass.h"
  26 #include <map>
  27
  28 class MRegisterInfo;
  29
  30 class LiveVariables : public MachineFunctionPass {
  31 public:
  32   struct VarInfo {
  33     /// DefBlock - The basic block which defines this value...
  34     MachineBasicBlock *DefBlock;
  35     MachineInstr      *DefInst;
  36
  37     /// AliveBlocks - Set of blocks of which this value is alive completely
  38     /// through.  This is a bit set which uses the basic block number as an
  39     /// index.
  40     ///
  41     std::vector<bool> AliveBlocks;
  42
  43     /// Kills - List of MachineBasicblock's which contain the last use of this
  44     /// virtual register (kill it).  This also includes the specific instruction
  45     /// which kills the value.
  46     ///
  47     std::vector<std::pair<MachineBasicBlock*, MachineInstr*> > Kills;
  48
  49     VarInfo() : DefBlock(0), DefInst(0) {}
  50
  51     /// removeKill - Delete a kill corresponding to the specified machine instr
  52     void removeKill(MachineInstr *MI) {
  53       for (unsigned i = 0; ; ++i) {
  54         assert(i < Kills.size() && "Machine instr is not a kill!");
  55         if (Kills[i].second == MI) {
  56           Kills.erase(Kills.begin()+i);
  57           return;
  58         }
  59       }
  60     }
  61   };
  62
  63 private:
  64   /// VirtRegInfo - This list is a mapping from virtual register number to
  65   /// variable information.  FirstVirtualRegister is subtracted from the virtual
  66   /// register number before indexing into this list.
  67   ///
  68   std::vector<VarInfo> VirtRegInfo;
  69
  70   /// RegistersKilled - This multimap keeps track of all of the registers that
  71   /// are dead immediately after an instruction reads its operands.  If an
  72   /// instruction does not have an entry in this map, it kills no registers.
  73   ///
  74   std::multimap<MachineInstr*, unsigned> RegistersKilled;
  75
  76   /// RegistersDead - This multimap keeps track of all of the registers that are
  77   /// dead immediately after an instruction executes, which are not dead after
  78   /// the operands are evaluated.  In practice, this only contains registers
  79   /// which are defined by an instruction, but never used.
  80   ///
  81   std::multimap<MachineInstr*, unsigned> RegistersDead;
  82
  83   /// AllocatablePhysicalRegisters - This vector keeps track of which registers
  84   /// are actually register allocatable by the target machine.  We can not track
  85   /// liveness for values that are not in this set.
  86   ///
  87   std::vector<bool> AllocatablePhysicalRegisters;
  88
  89 private:   // Intermediate data structures
  90
  91   /// BBMap - Maps LLVM basic blocks to their corresponding machine basic block.
  92   /// This also provides a numbering of the basic blocks in the function.
  93   std::map<const BasicBlock*, std::pair<MachineBasicBlock*, unsigned> > BBMap;
  94
  95   const MRegisterInfo *RegInfo;
  96
  97   MachineInstr **PhysRegInfo;
  98   bool          *PhysRegUsed;
  99
 100 public:
 101
 102   virtual bool runOnMachineFunction(MachineFunction &MF);
 103
 104   /// getMachineBasicBlockIndex - Turn a MachineBasicBlock into an index number
 105   /// suitable for use with VarInfo's.
 106   ///
 107   const std::pair<MachineBasicBlock*, unsigned>
 108       &getMachineBasicBlockInfo(MachineBasicBlock *MBB) const;
 109   const std::pair<MachineBasicBlock*, unsigned>
 110       &getBasicBlockInfo(const BasicBlock *BB) const {
 111     return BBMap.find(BB)->second;
 112   }
 113
 114
 115   /// killed_iterator - Iterate over registers killed by a machine instruction
 116   ///
 117   typedef std::multimap<MachineInstr*, unsigned>::iterator killed_iterator;
 118
 119   /// killed_begin/end - Get access to the range of registers killed by a
 120   /// machine instruction.
 121   killed_iterator killed_begin(MachineInstr *MI) {
 122     return RegistersKilled.lower_bound(MI);
 123   }
 124   killed_iterator killed_end(MachineInstr *MI) {
 125     return RegistersKilled.upper_bound(MI);
 126   }
 127   std::pair<killed_iterator, killed_iterator>
 128   killed_range(MachineInstr *MI) {
 129     return RegistersKilled.equal_range(MI);
 130   }
 131
 132   killed_iterator dead_begin(MachineInstr *MI) {
 133     return RegistersDead.lower_bound(MI);
 134   }
 135   killed_iterator dead_end(MachineInstr *MI) {
 136     return RegistersDead.upper_bound(MI);
 137   }
 138   std::pair<killed_iterator, killed_iterator>
 139   dead_range(MachineInstr *MI) {
 140     return RegistersDead.equal_range(MI);
 141   }
 142
 143   //===--------------------------------------------------------------------===//
 144   //  API to update live variable information
 145
 146   /// addVirtualRegisterKilled - Add information about the fact that the
 147   /// specified register is killed after being used by the specified
 148   /// instruction.
 149   ///
 150   void addVirtualRegisterKilled(unsigned IncomingReg, MachineBasicBlock *MBB,
 151                                 MachineInstr *MI) {
 152     RegistersKilled.insert(std::make_pair(MI, IncomingReg));
 153     getVarInfo(IncomingReg).Kills.push_back(std::make_pair(MBB, MI));
 154   }
 155
 156   /// removeVirtualRegistersKilled - Remove all of the specified killed
 157   /// registers from the live variable information.
 158   void removeVirtualRegistersKilled(killed_iterator B, killed_iterator E) {
 159     for (killed_iterator I = B; I != E; ++I)  // Remove VarInfo entries...
 160       getVarInfo(I->second).removeKill(I->first);
 161     RegistersKilled.erase(B, E);
 162   }
 163
 164   /// addVirtualRegisterDead - Add information about the fact that the specified
 165   /// register is dead after being used by the specified instruction.
 166   ///
 167   void addVirtualRegisterDead(unsigned IncomingReg, MachineBasicBlock *MBB,
 168                               MachineInstr *MI) {
 169     RegistersDead.insert(std::make_pair(MI, IncomingReg));
 170     getVarInfo(IncomingReg).Kills.push_back(std::make_pair(MBB, MI));
 171   }
 172
 173   /// removeVirtualRegistersKilled - Remove all of the specified killed
 174   /// registers from the live variable information.
 175   void removeVirtualRegistersDead(killed_iterator B, killed_iterator E) {
 176     for (killed_iterator I = B; I != E; ++I)  // Remove VarInfo entries...
 177       getVarInfo(I->second).removeKill(I->first);
 178     RegistersDead.erase(B, E);
 179   }
 180
 181   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 182     AU.setPreservesAll();
 183   }
 184
 185   virtual void releaseMemory() {
 186     VirtRegInfo.clear();
 187     RegistersKilled.clear();
 188     RegistersDead.clear();
 189     BBMap.clear();
 190   }
 191
 192   /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
 193   /// register.
 194   VarInfo &getVarInfo(unsigned RegIdx);
 195
 196   void MarkVirtRegAliveInBlock(VarInfo &VRInfo, const BasicBlock *BB);
 197   void HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
 198                         MachineInstr *MI);
 199   void HandlePhysRegUse(unsigned Reg, MachineInstr *MI);
 200   void HandlePhysRegDef(unsigned Reg, MachineInstr *MI);
 201 };
 202
 203 #endif