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 <list>
  28 #include <map>
  29 #include <vector>
  30
  31 namespace llvm {
  32
  33     class LiveVariables;
  34     class MRegisterInfo;
  35
  36     class LiveIntervals : public MachineFunctionPass
  37     {
  38     public:
  39         struct Interval {
  40             typedef std::pair<unsigned, unsigned> Range;
  41             typedef std::vector<Range> Ranges;
  42             unsigned reg;   // the register of this interval
  43             float weight;   // weight of this interval (number of uses
  44                             // * 10^loopDepth)
  45             Ranges ranges;  // the ranges in which this register is live
  46
  47             Interval(unsigned r);
  48
  49             unsigned start() const {
  50                 assert(!ranges.empty() && "empty interval for register");
  51                 return ranges.front().first;
  52             }
  53
  54             unsigned end() const {
  55                 assert(!ranges.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         typedef std::map<unsigned, unsigned> Reg2RegMap;
  91         typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
  92
  93     private:
  94         MachineFunction* mf_;
  95         const TargetMachine* tm_;
  96         const MRegisterInfo* mri_;
  97         MachineBasicBlock* currentMbb_;
  98         MachineBasicBlock::iterator currentInstr_;
  99         LiveVariables* lv_;
 100
 101         typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
 102         MbbIndex2MbbMap mbbi2mbbMap_;
 103
 104         typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
 105         Mi2IndexMap mi2iMap_;
 106
 107         typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
 108         Reg2IntervalMap r2iMap_;
 109
 110         Reg2RegMap r2rMap_;
 111
 112         Intervals intervals_;
 113
 114     public:
 115         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 116
 117         Intervals& getIntervals() { return intervals_; }
 118
 119         MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
 120             MachineBasicBlockPtrs result;
 121             for (MbbIndex2MbbMap::const_iterator
 122                      it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
 123                  it != itEnd; ++it) {
 124                 result.push_back(it->second);
 125             }
 126             return result;
 127         }
 128
 129         const Reg2RegMap& getJoinedRegMap() const {
 130             return r2rMap_;
 131         }
 132
 133         /// rep - returns the representative of this register
 134         unsigned rep(unsigned reg);
 135
 136     private:
 137         /// runOnMachineFunction - pass entry point
 138         bool runOnMachineFunction(MachineFunction&);
 139
 140         /// computeIntervals - compute live intervals
 141         void computeIntervals();
 142
 143         /// joinIntervals - join compatible live intervals
 144         void joinIntervals();
 145
 146         /// handleRegisterDef - update intervals for a register def
 147         /// (calls handlePhysicalRegisterDef and
 148         /// handleVirtualRegisterDef)
 149         void handleRegisterDef(MachineBasicBlock* mbb,
 150                                MachineBasicBlock::iterator mi,
 151                                unsigned reg);
 152
 153         /// handleVirtualRegisterDef - update intervals for a virtual
 154         /// register def
 155         void handleVirtualRegisterDef(MachineBasicBlock* mbb,
 156                                       MachineBasicBlock::iterator mi,
 157                                       unsigned reg);
 158
 159         /// handlePhysicalRegisterDef - update intervals for a
 160         /// physical register def
 161         void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
 162                                        MachineBasicBlock::iterator mi,
 163                                        unsigned reg);
 164
 165         unsigned getInstructionIndex(MachineInstr* instr) const;
 166
 167         void printRegName(unsigned reg) const;
 168     };
 169
 170     inline bool operator==(const LiveIntervals::Interval& lhs,
 171                            const LiveIntervals::Interval& rhs) {
 172         return lhs.reg == rhs.reg;
 173     }
 174
 175     std::ostream& operator<<(std::ostream& os,
 176                              const LiveIntervals::Interval& li);
 177
 178 } // End llvm namespace
 179
 180 #endif