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