include/llvm/CodeGen/LiveIntervals.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 expiredAt(unsigned index) const {
  59                 return end() <= index;
  60             }
  61
  62             void addRange(unsigned start, unsigned end);
  63
  64         private:
  65             void mergeRangesForward(Ranges::iterator it);
  66
  67             void mergeRangesBackward(Ranges::iterator it);
  68         };
  69
  70         struct StartPointComp {
  71             bool operator()(const Interval& lhs, const Interval& rhs) {
  72                 return lhs.ranges.front().first < rhs.ranges.front().first;
  73             }
  74         };
  75
  76         struct EndPointComp {
  77             bool operator()(const Interval& lhs, const Interval& rhs) {
  78                 return lhs.ranges.back().second < rhs.ranges.back().second;
  79             }
  80         };
  81
  82         typedef std::vector<Interval> Intervals;
  83         typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
  84
  85     private:
  86         MachineFunction* mf_;
  87         const TargetMachine* tm_;
  88         const MRegisterInfo* mri_;
  89         MachineBasicBlock* currentMbb_;
  90         MachineBasicBlock::iterator currentInstr_;
  91         LiveVariables* lv_;
  92
  93         std::vector<bool> allocatableRegisters_;
  94
  95         typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
  96         MbbIndex2MbbMap mbbi2mbbMap_;
  97
  98         typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
  99         Mi2IndexMap mi2iMap_;
 100
 101         typedef std::map<unsigned, unsigned> Reg2IntervalMap;
 102         Reg2IntervalMap r2iMap_;
 103
 104         Intervals intervals_;
 105
 106     public:
 107         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 108         Intervals& getIntervals() { return intervals_; }
 109         MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
 110             MachineBasicBlockPtrs result;
 111             for (MbbIndex2MbbMap::const_iterator
 112                      it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
 113                  it != itEnd; ++it) {
 114                 result.push_back(it->second);
 115             }
 116             return result;
 117         }
 118
 119     private:
 120         /// runOnMachineFunction - pass entry point
 121         bool runOnMachineFunction(MachineFunction&);
 122
 123         /// computeIntervals - compute live intervals
 124         void computeIntervals();
 125
 126
 127         /// handleRegisterDef - update intervals for a register def
 128         /// (calls handlePhysicalRegisterDef and
 129         /// handleVirtualRegisterDef)
 130         void handleRegisterDef(MachineBasicBlock* mbb,
 131                                MachineBasicBlock::iterator mi,
 132                                unsigned reg);
 133
 134         /// handleVirtualRegisterDef - update intervals for a virtual
 135         /// register def
 136         void handleVirtualRegisterDef(MachineBasicBlock* mbb,
 137                                       MachineBasicBlock::iterator mi,
 138                                       unsigned reg);
 139
 140         /// handlePhysicalRegisterDef - update intervals for a
 141         /// physical register def
 142         void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
 143                                        MachineBasicBlock::iterator mi,
 144                                        unsigned reg);
 145
 146         unsigned getInstructionIndex(MachineInstr* instr) const;
 147
 148         void printRegName(unsigned reg) const;
 149     };
 150
 151     inline bool operator==(const LiveIntervals::Interval& lhs,
 152                            const LiveIntervals::Interval& rhs) {
 153         return lhs.reg == rhs.reg;
 154     }
 155
 156     std::ostream& operator<<(std::ostream& os,
 157                              const LiveIntervals::Interval& li);
 158
 159 } // End llvm namespace
 160
 161 #endif