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
  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             unsigned start() const {
  46                 assert(!ranges.empty() && "empty interval for register");
  47                 return ranges.front().first;
  48             }
  49
  50             unsigned end() const {
  51                 assert(!ranges.empty() && "empty interval for register");
  52                 return ranges.back().second;
  53             }
  54
  55             bool expiredAt(unsigned index) const {
  56                 return end() <= (index + 1);
  57             }
  58
  59             bool liveAt(unsigned index) const;
  60
  61             bool overlaps(const Interval& other) const;
  62
  63             void addRange(unsigned start, unsigned end);
  64
  65             void join(const Interval& other);
  66
  67         private:
  68             Ranges::iterator mergeRangesForward(Ranges::iterator it);
  69
  70             Ranges::iterator mergeRangesBackward(Ranges::iterator it);
  71         };
  72
  73         struct StartPointComp {
  74             bool operator()(const Interval& lhs, const Interval& rhs) {
  75                 return lhs.ranges.front().first < rhs.ranges.front().first;
  76             }
  77         };
  78
  79         struct EndPointComp {
  80             bool operator()(const Interval& lhs, const Interval& rhs) {
  81                 return lhs.ranges.back().second < rhs.ranges.back().second;
  82             }
  83         };
  84
  85         typedef std::list<Interval> Intervals;
  86         typedef std::map<unsigned, unsigned> Reg2RegMap;
  87         typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
  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<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
  98         MbbIndex2MbbMap mbbi2mbbMap_;
  99
 100         typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
 101         Mi2IndexMap mi2iMap_;
 102
 103         typedef std::vector<MachineInstr*> Index2MiMap;
 104         Index2MiMap i2miMap_;
 105
 106         typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
 107         Reg2IntervalMap r2iMap_;
 108
 109         Reg2RegMap r2rMap_;
 110
 111         Intervals intervals_;
 112
 113     public:
 114         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 115         virtual void releaseMemory();
 116
 117         /// runOnMachineFunction - pass entry point
 118         virtual bool runOnMachineFunction(MachineFunction&);
 119
 120         unsigned getInstructionIndex(MachineInstr* instr) const;
 121
 122         MachineInstr* getInstructionFromIndex(unsigned index) const;
 123
 124         Intervals& getIntervals() { return intervals_; }
 125
 126         void updateSpilledInterval(Interval& i);
 127
 128     private:
 129         /// computeIntervals - compute live intervals
 130         void computeIntervals();
 131
 132         /// joinIntervals - join compatible live intervals
 133         void joinIntervals();
 134
 135         /// handleRegisterDef - update intervals for a register def
 136         /// (calls handlePhysicalRegisterDef and
 137         /// handleVirtualRegisterDef)
 138         void handleRegisterDef(MachineBasicBlock* mbb,
 139                                MachineBasicBlock::iterator mi,
 140                                unsigned reg);
 141
 142         /// handleVirtualRegisterDef - update intervals for a virtual
 143         /// register def
 144         void handleVirtualRegisterDef(MachineBasicBlock* mbb,
 145                                       MachineBasicBlock::iterator mi,
 146                                       unsigned reg);
 147
 148         /// handlePhysicalRegisterDef - update intervals for a
 149         /// physical register def
 150         void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
 151                                        MachineBasicBlock::iterator mi,
 152                                        unsigned reg);
 153
 154         bool overlapsAliases(const Interval& lhs, const Interval& rhs) const;
 155
 156         /// rep - returns the representative of this register
 157         unsigned rep(unsigned reg);
 158
 159         void printRegName(unsigned reg) const;
 160     };
 161
 162     inline bool operator==(const LiveIntervals::Interval& lhs,
 163                            const LiveIntervals::Interval& rhs) {
 164         return lhs.reg == rhs.reg;
 165     }
 166
 167     std::ostream& operator<<(std::ostream& os,
 168                              const LiveIntervals::Interval& li);
 169
 170 } // End llvm namespace
 171
 172 #endif