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   struct VarInfo {
  32     /// DefBlock - The basic block which defines this value...
  33     MachineBasicBlock *DefBlock;
  34     MachineInstr      *DefInst;
  35
  36     /// AliveBlocks - Set of blocks of which this value is alive completely
  37     /// through.  This is a bit set which uses the basic block number as an
  38     /// index.
  39     ///
  40     std::vector<bool> AliveBlocks;
  41
  42     /// Kills - List of MachineBasicblock's which contain the last use of this
  43     /// virtual register (kill it).  This also includes the specific instruction
  44     /// which kills the value.
  45     ///
  46     std::vector<std::pair<MachineBasicBlock*, MachineInstr*> > Kills;
  47
  48     VarInfo() : DefBlock(0), DefInst(0) {}
  49   };
  50
  51   /// VirtRegInfo - This list is a mapping from virtual register number to
  52   /// variable information.  FirstVirtualRegister is subtracted from the virtual
  53   /// register number before indexing into this list.
  54   ///
  55   std::vector<VarInfo> VirtRegInfo;
  56
  57   /// RegistersKilled - This multimap keeps track of all of the registers that
  58   /// are dead immediately after an instruction reads its operands.  If an
  59   /// instruction does not have an entry in this map, it kills no registers.
  60   ///
  61   std::multimap<MachineInstr*, unsigned> RegistersKilled;
  62
  63   /// RegistersDead - This multimap keeps track of all of the registers that are
  64   /// dead immediately after an instruction executes, which are not dead after
  65   /// the operands are evaluated.  In practice, this only contains registers
  66   /// which are defined by an instruction, but never used.
  67   ///
  68   std::multimap<MachineInstr*, unsigned> RegistersDead;
  69
  70   /// AllocatablePhysicalRegisters - This vector keeps track of which registers
  71   /// are actually register allocatable by the target machine.  We can not track
  72   /// liveness for values that are not in this set.
  73   ///
  74   std::vector<bool> AllocatablePhysicalRegisters;
  75 private:   // Intermediate data structures
  76
  77   /// BBMap - Maps LLVM basic blocks to their corresponding machine basic block.
  78   /// This also provides a numbering of the basic blocks in the function.
  79   std::map<const BasicBlock*, std::pair<MachineBasicBlock*, unsigned> > BBMap;
  80
  81   const MRegisterInfo *RegInfo;
  82
  83   MachineInstr **PhysRegInfo;
  84   bool          *PhysRegUsed;
  85
  86 public:
  87
  88   virtual bool runOnMachineFunction(MachineFunction &MF);
  89
  90   /// killed_iterator - Iterate over registers killed by a machine instruction
  91   ///
  92   typedef std::multimap<MachineInstr*,
  93                         unsigned>::const_iterator killed_iterator;
  94
  95   /// killed_begin/end - Get access to the range of registers killed by a
  96   /// machine instruction.
  97   killed_iterator killed_begin(MachineInstr *MI) const {
  98     return RegistersKilled.lower_bound(MI);
  99   }
 100   killed_iterator killed_end(MachineInstr *MI) const {
 101     return RegistersKilled.upper_bound(MI);
 102   }
 103
 104   killed_iterator dead_begin(MachineInstr *MI) const {
 105     return RegistersDead.lower_bound(MI);
 106   }
 107   killed_iterator dead_end(MachineInstr *MI) const {
 108     return RegistersDead.upper_bound(MI);
 109   }
 110
 111   /// addVirtualRegisterKill - Add information about the fact that the specified
 112   /// register is dead after being used by the specified instruction.
 113   ///
 114   void addVirtualRegisterKill(unsigned IncomingReg, MachineInstr *MI) {
 115     RegistersDead.insert(std::make_pair(MI, IncomingReg));
 116   }
 117
 118   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 119     AU.setPreservesAll();
 120   }
 121
 122   virtual void releaseMemory() {
 123     VirtRegInfo.clear();
 124     RegistersKilled.clear();
 125     RegistersDead.clear();
 126   }
 127 private:
 128   VarInfo &getVarInfo(unsigned RegIdx) {
 129     if (RegIdx >= VirtRegInfo.size()) {
 130       if (RegIdx >= 2*VirtRegInfo.size())
 131         VirtRegInfo.resize(RegIdx*2);
 132       else
 133         VirtRegInfo.resize(2*VirtRegInfo.size());
 134     }
 135     return VirtRegInfo[RegIdx];
 136   }
 137
 138   void MarkVirtRegAliveInBlock(VarInfo &VRInfo, const BasicBlock *BB);
 139   void HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
 140                         MachineInstr *MI);
 141   void HandlePhysRegUse(unsigned Reg, MachineInstr *MI);
 142   void HandlePhysRegDef(unsigned Reg, MachineInstr *MI);
 143 };
 144
 145 #endif