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