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 "llvm/CodeGen/MachineBasicBlock.h"
  26 #include <iostream>
  27 #include <map>
  28
  29 namespace llvm {
  30
  31     class LiveVariables;
  32     class MRegisterInfo;
  33
  34     class LiveIntervals : public MachineFunctionPass
  35     {
  36     public:
  37         struct Interval {
  38             typedef std::pair<unsigned, unsigned> Range;
  39             typedef std::vector<Range> Ranges;
  40             unsigned reg;   // the register of this interval
  41             Ranges ranges; // the ranges this register is valid
  42
  43             Interval(unsigned r)
  44                 : reg(r) {
  45
  46             }
  47
  48             unsigned start() const {
  49                 assert(!ranges.empty() && "empty interval for register");
  50                 return ranges.front().first;
  51             }
  52
  53             unsigned end() const {
  54                 assert(!ranges.empty() && "empty interval for register");
  55                 return ranges.back().second;
  56             }
  57
  58             bool expired(unsigned index) const {
  59                 return end() <= index;
  60             }
  61
  62             bool overlaps(unsigned index) const {
  63                 for (Ranges::const_iterator
  64                          i = ranges.begin(), e = ranges.end(); i != e; ++i) {
  65                     if (index >= i->first && index < i->second) {
  66                         return true;
  67                     }
  68                 }
  69                 return false;
  70             }
  71
  72             void addRange(unsigned start, unsigned end) {
  73                 Range range = std::make_pair(start, end);
  74                 Ranges::iterator it =
  75                     std::lower_bound(ranges.begin(), ranges.end(), range);
  76
  77                 if (it == ranges.end()) {
  78                     it = ranges.insert(it, range);
  79                     goto exit;
  80                 }
  81
  82                 assert(range.first <= it->first && "got wrong iterator?");
  83                 // merge ranges if necesary
  84                 if (range.first < it->first) {
  85                     if (range.second >= it->first) {
  86                         it->first = range.first;
  87                     }
  88                     else {
  89                         it = ranges.insert(it, range);
  90                         assert(it != ranges.end() && "wtf?");
  91                         goto exit;
  92                     }
  93                 }
  94
  95             exit:
  96                 mergeRangesIfNecessary(it);
  97             }
  98
  99         private:
 100             void mergeRangesIfNecessary(Ranges::iterator it) {
 101                 while (it != ranges.begin()) {
 102                     Ranges::iterator prev = it - 1;
 103                     if (prev->second < it->first) {
 104                         break;
 105                     }
 106                     prev->second = it->second;
 107                     ranges.erase(it);
 108                     it = prev;
 109                 }
 110             }
 111         };
 112
 113         struct StartPointComp {
 114             bool operator()(const Interval& lhs, const Interval& rhs) {
 115                 return lhs.ranges.front().first < rhs.ranges.front().first;
 116             }
 117         };
 118
 119         struct EndPointComp {
 120             bool operator()(const Interval& lhs, const Interval& rhs) {
 121                 return lhs.ranges.back().second < rhs.ranges.back().second;
 122             }
 123         };
 124
 125         typedef std::vector<Interval> Intervals;
 126         typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
 127
 128     private:
 129         MachineFunction* mf_;
 130         const TargetMachine* tm_;
 131         const MRegisterInfo* mri_;
 132         MachineBasicBlock* currentMbb_;
 133         MachineBasicBlock::iterator currentInstr_;
 134         LiveVariables* lv_;
 135
 136         std::vector<bool> allocatableRegisters_;
 137
 138         typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
 139         MbbIndex2MbbMap mbbi2mbbMap_;
 140
 141         typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
 142         Mi2IndexMap mi2iMap_;
 143
 144         typedef std::map<unsigned, unsigned> Reg2IntervalMap;
 145         Reg2IntervalMap r2iMap_;
 146
 147         Intervals intervals_;
 148
 149     public:
 150         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 151         Intervals& getIntervals() { return intervals_; }
 152         MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
 153             MachineBasicBlockPtrs result;
 154             for (MbbIndex2MbbMap::const_iterator
 155                      it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
 156                  it != itEnd; ++it) {
 157                 result.push_back(it->second);
 158             }
 159             return result;
 160         }
 161
 162     private:
 163         /// runOnMachineFunction - pass entry point
 164         bool runOnMachineFunction(MachineFunction&);
 165
 166         /// computeIntervals - compute live intervals
 167         void computeIntervals();
 168
 169
 170         /// handleRegisterDef - update intervals for a register def
 171         /// (calls handlePhysicalRegisterDef and
 172         /// handleVirtualRegisterDef)
 173         void handleRegisterDef(MachineBasicBlock* mbb,
 174                                MachineBasicBlock::iterator mi,
 175                                unsigned reg);
 176
 177         /// handleVirtualRegisterDef - update intervals for a virtual
 178         /// register def
 179         void handleVirtualRegisterDef(MachineBasicBlock* mbb,
 180                                       MachineBasicBlock::iterator mi,
 181                                       unsigned reg);
 182
 183         /// handlePhysicalRegisterDef - update intervals for a
 184         /// physical register def
 185         void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
 186                                        MachineBasicBlock::iterator mi,
 187                                        unsigned reg);
 188
 189         unsigned getInstructionIndex(MachineInstr* instr) const;
 190
 191         void printRegName(unsigned reg) const;
 192     };
 193
 194     inline bool operator==(const LiveIntervals::Interval& lhs,
 195                            const LiveIntervals::Interval& rhs) {
 196         return lhs.reg == rhs.reg;
 197     }
 198
 199     std::ostream& operator<<(std::ostream& os,
 200                              const LiveIntervals::Interval& li);
 201
 202 } // End llvm namespace
 203
 204 #endif