lib/CodeGen/LiveIntervalAnalysis.h

   1 //===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LiveInterval analysis pass.  Given some numbering of
  11 // each the machine instructions (in this implemention depth-first order) an
  12 // interval [i, j) is said to be a live interval for register v if there is no
  13 // instruction with number j' > j such that v is live at j' abd there is no
  14 // instruction with number i' < i such that v is live at i'. In this
  15 // implementation intervals can have holes, i.e. an interval might look like
  16 // [1,20), [50,65), [1000,1001).
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
  21 #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
  22
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "LiveInterval.h"
  25
  26 namespace llvm {
  27
  28     class LiveVariables;
  29     class MRegisterInfo;
  30     class VirtRegMap;
  31
  32     class LiveIntervals : public MachineFunctionPass {
  33         MachineFunction* mf_;
  34         const TargetMachine* tm_;
  35         const MRegisterInfo* mri_;
  36         LiveVariables* lv_;
  37
  38         typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
  39         Mi2IndexMap mi2iMap_;
  40
  41         typedef std::vector<MachineInstr*> Index2MiMap;
  42         Index2MiMap i2miMap_;
  43
  44         /// r2iMap_ - This map OWNS the interval pointed to by the map.  When
  45         /// this map is destroyed or when entries are modified, this intervals
  46         /// should be destroyed or modified as well.
  47         std::map<unsigned, LiveInterval*> r2iMap_;
  48
  49         typedef std::map<unsigned, unsigned> Reg2RegMap;
  50         Reg2RegMap r2rMap_;
  51
  52     public:
  53         struct InstrSlots
  54         {
  55             enum {
  56                 LOAD  = 0,
  57                 USE   = 1,
  58                 DEF   = 2,
  59                 STORE = 3,
  60                 NUM   = 4,
  61             };
  62         };
  63
  64         static unsigned getBaseIndex(unsigned index) {
  65             return index - (index % InstrSlots::NUM);
  66         }
  67         static unsigned getBoundaryIndex(unsigned index) {
  68             return getBaseIndex(index + InstrSlots::NUM - 1);
  69         }
  70         static unsigned getLoadIndex(unsigned index) {
  71             return getBaseIndex(index) + InstrSlots::LOAD;
  72         }
  73         static unsigned getUseIndex(unsigned index) {
  74             return getBaseIndex(index) + InstrSlots::USE;
  75         }
  76         static unsigned getDefIndex(unsigned index) {
  77             return getBaseIndex(index) + InstrSlots::DEF;
  78         }
  79         static unsigned getStoreIndex(unsigned index) {
  80             return getBaseIndex(index) + InstrSlots::STORE;
  81         }
  82
  83         typedef std::map<unsigned, LiveInterval*>::const_iterator iterator;
  84         iterator begin() const { return r2iMap_.begin(); }
  85         iterator end() const { return r2iMap_.end(); }
  86       unsigned getNumIntervals() const { return r2iMap_.size(); }
  87
  88         LiveInterval &getInterval(unsigned reg) const {
  89           std::map<unsigned, LiveInterval*>::const_iterator I =
  90               r2iMap_.find(reg);
  91           assert(I != r2iMap_.end() && "Interval does not exist for register");
  92           return *I->second;
  93         }
  94
  95         /// getInstructionIndex - returns the base index of instr
  96         unsigned getInstructionIndex(MachineInstr* instr) const {
  97           Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
  98           assert(it != mi2iMap_.end() && "Invalid instruction!");
  99           return it->second;
 100         }
 101
 102         /// getInstructionFromIndex - given an index in any slot of an
 103         /// instruction return a pointer the instruction
 104         MachineInstr* getInstructionFromIndex(unsigned index) const {
 105           index /= InstrSlots::NUM; // convert index to vector index
 106           assert(index < i2miMap_.size() &&
 107                  "index does not correspond to an instruction");
 108           return i2miMap_[index];
 109         }
 110
 111         std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
 112                                                          VirtRegMap& vrm,
 113                                                          int slot);
 114
 115         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 116         virtual void releaseMemory();
 117
 118         /// runOnMachineFunction - pass entry point
 119         virtual bool runOnMachineFunction(MachineFunction&);
 120
 121     private:
 122         /// computeIntervals - compute live intervals
 123         void computeIntervals();
 124
 125         /// joinIntervals - join compatible live intervals
 126         void joinIntervals();
 127
 128         /// joinIntervalsInMachineBB - Join intervals based on move
 129         /// instructions in the specified basic block.
 130         void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
 131
 132         /// handleRegisterDef - update intervals for a register def
 133         /// (calls handlePhysicalRegisterDef and
 134         /// handleVirtualRegisterDef)
 135         void handleRegisterDef(MachineBasicBlock* mbb,
 136                                MachineBasicBlock::iterator mi,
 137                                unsigned reg);
 138
 139         /// handleVirtualRegisterDef - update intervals for a virtual
 140         /// register def
 141         void handleVirtualRegisterDef(MachineBasicBlock* mbb,
 142                                       MachineBasicBlock::iterator mi,
 143                                       LiveInterval& interval);
 144
 145         /// handlePhysicalRegisterDef - update intervals for a
 146         /// physical register def
 147         void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
 148                                        MachineBasicBlock::iterator mi,
 149                                        LiveInterval& interval);
 150
 151         /// Return true if the two specified registers belong to different
 152         /// register classes.  The registers may be either phys or virt regs.
 153         bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
 154
 155         bool overlapsAliases(const LiveInterval *lhs,
 156                              const LiveInterval *rhs) const;
 157
 158         LiveInterval *createInterval(unsigned Reg) const;
 159
 160         LiveInterval &getOrCreateInterval(unsigned reg) {
 161           LiveInterval *&LI = r2iMap_[reg];
 162           if (LI == 0)
 163             LI = createInterval(reg);
 164           return *LI;
 165         }
 166
 167         /// rep - returns the representative of this register
 168         unsigned rep(unsigned reg) {
 169           Reg2RegMap::iterator it = r2rMap_.find(reg);
 170           if (it != r2rMap_.end())
 171             return it->second = rep(it->second);
 172           return reg;
 173         }
 174
 175         void printRegName(unsigned reg) const;
 176     };
 177
 178 } // End llvm namespace
 179
 180 #endif