lib/CodeGen/LiveIntervalAnalysis.h

   1 //===-- llvm/CodeGen/LiveInterval.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_LIVEINTERVALS_H
  21 #define LLVM_CODEGEN_LIVEINTERVALS_H
  22
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include <list>
  25
  26 namespace llvm {
  27
  28     class LiveVariables;
  29     class MRegisterInfo;
  30     class VirtRegMap;
  31
  32     struct LiveInterval {
  33         typedef std::pair<unsigned, unsigned> Range;
  34         typedef std::vector<Range> Ranges;
  35         unsigned reg;   // the register of this interval
  36         float weight;   // weight of this interval:
  37                         //     (number of uses *10^loopDepth)
  38         Ranges ranges;  // the ranges in which this register is live
  39
  40         explicit LiveInterval(unsigned r);
  41
  42         bool empty() const { return ranges.empty(); }
  43
  44         bool spilled() const;
  45
  46         unsigned start() const {
  47             assert(!empty() && "empty interval for register");
  48             return ranges.front().first;
  49         }
  50
  51         unsigned end() const {
  52             assert(!empty() && "empty interval for register");
  53             return ranges.back().second;
  54         }
  55
  56         bool expiredAt(unsigned index) const {
  57             return end() <= (index + 1);
  58         }
  59
  60         bool liveAt(unsigned index) const;
  61
  62         bool overlaps(const LiveInterval& other) const;
  63
  64         void addRange(unsigned start, unsigned end);
  65
  66         void join(const LiveInterval& other);
  67
  68         bool operator<(const LiveInterval& other) const {
  69             return start() < other.start();
  70         }
  71
  72         bool operator==(const LiveInterval& other) const {
  73             return reg == other.reg;
  74         }
  75
  76     private:
  77         Ranges::iterator mergeRangesForward(Ranges::iterator it);
  78         Ranges::iterator mergeRangesBackward(Ranges::iterator it);
  79     };
  80
  81     std::ostream& operator<<(std::ostream& os, const LiveInterval& li);
  82
  83     class LiveIntervals : public MachineFunctionPass
  84     {
  85     public:
  86         typedef std::list<LiveInterval> Intervals;
  87
  88     private:
  89         MachineFunction* mf_;
  90         const TargetMachine* tm_;
  91         const MRegisterInfo* mri_;
  92         MachineBasicBlock* currentMbb_;
  93         MachineBasicBlock::iterator currentInstr_;
  94         LiveVariables* lv_;
  95
  96         typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
  97         Mi2IndexMap mi2iMap_;
  98
  99         typedef std::vector<MachineInstr*> Index2MiMap;
 100         Index2MiMap i2miMap_;
 101
 102         typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
 103         Reg2IntervalMap r2iMap_;
 104
 105         typedef std::map<unsigned, unsigned> Reg2RegMap;
 106         Reg2RegMap r2rMap_;
 107
 108         Intervals intervals_;
 109
 110     public:
 111         struct InstrSlots
 112         {
 113             enum {
 114                 LOAD  = 0,
 115                 USE   = 1,
 116                 DEF   = 2,
 117                 STORE = 3,
 118                 NUM   = 4,
 119             };
 120         };
 121
 122         static unsigned getBaseIndex(unsigned index) {
 123             return index - (index % InstrSlots::NUM);
 124         }
 125         static unsigned getBoundaryIndex(unsigned index) {
 126             return getBaseIndex(index + InstrSlots::NUM - 1);
 127         }
 128         static unsigned getLoadIndex(unsigned index) {
 129             return getBaseIndex(index) + InstrSlots::LOAD;
 130         }
 131         static unsigned getUseIndex(unsigned index) {
 132             return getBaseIndex(index) + InstrSlots::USE;
 133         }
 134         static unsigned getDefIndex(unsigned index) {
 135             return getBaseIndex(index) + InstrSlots::DEF;
 136         }
 137         static unsigned getStoreIndex(unsigned index) {
 138             return getBaseIndex(index) + InstrSlots::STORE;
 139         }
 140
 141         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 142         virtual void releaseMemory();
 143
 144         /// runOnMachineFunction - pass entry point
 145         virtual bool runOnMachineFunction(MachineFunction&);
 146
 147         LiveInterval& getInterval(unsigned reg) {
 148             assert(r2iMap_.count(reg)&& "Interval does not exist for register");
 149             return *r2iMap_.find(reg)->second;
 150         }
 151
 152         /// getInstructionIndex - returns the base index of instr
 153         unsigned getInstructionIndex(MachineInstr* instr) const;
 154
 155         /// getInstructionFromIndex - given an index in any slot of an
 156         /// instruction return a pointer the instruction
 157         MachineInstr* getInstructionFromIndex(unsigned index) const;
 158
 159         Intervals& getIntervals() { return intervals_; }
 160
 161         std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
 162                                                          VirtRegMap& vrm,
 163                                                          int slot);
 164
 165     private:
 166         /// computeIntervals - compute live intervals
 167         void computeIntervals();
 168
 169         /// joinIntervals - join compatible live intervals
 170         void joinIntervals();
 171
 172         /// handleRegisterDef - update intervals for a register def
 173         /// (calls handlePhysicalRegisterDef and
 174         /// handleVirtualRegisterDef)
 175         void handleRegisterDef(MachineBasicBlock* mbb,
 176                                MachineBasicBlock::iterator mi,
 177                                unsigned reg);
 178
 179         /// handleVirtualRegisterDef - update intervals for a virtual
 180         /// register def
 181         void handleVirtualRegisterDef(MachineBasicBlock* mbb,
 182                                       MachineBasicBlock::iterator mi,
 183                                       LiveInterval& interval);
 184
 185         /// handlePhysicalRegisterDef - update intervals for a
 186         /// physical register def
 187         void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
 188                                        MachineBasicBlock::iterator mi,
 189                                        LiveInterval& interval);
 190
 191         bool overlapsAliases(const LiveInterval& lhs,
 192                              const LiveInterval& rhs) const;
 193
 194
 195         LiveInterval& getOrCreateInterval(unsigned reg);
 196
 197         /// rep - returns the representative of this register
 198         unsigned rep(unsigned reg);
 199
 200         void printRegName(unsigned reg) const;
 201     };
 202
 203 } // End llvm namespace
 204
 205 #endif