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