contrib/llvm/lib/Target/Hexagon/HexagonBlockRanges.h

   1 //===--- HexagonBlockRanges.h ---------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 #ifndef HEXAGON_BLOCK_RANGES_H
  10 #define HEXAGON_BLOCK_RANGES_H
  11
  12 #include "llvm/ADT/BitVector.h"
  13 #include "llvm/CodeGen/MachineBasicBlock.h"
  14 #include "llvm/MC/MCRegisterInfo.h"  // For MCPhysReg.
  15 #include <map>
  16 #include <set>
  17 #include <vector>
  18
  19 namespace llvm {
  20   class Function;
  21   class HexagonSubtarget;
  22   class MachineBasicBlock;
  23   class MachineFunction;
  24   class MachineInstr;
  25   class MCInstrDesc;
  26   class raw_ostream;
  27   class TargetInstrInfo;
  28   class TargetRegisterClass;
  29   class TargetRegisterInfo;
  30   class Type;
  31
  32 struct HexagonBlockRanges {
  33   HexagonBlockRanges(MachineFunction &MF);
  34
  35   struct RegisterRef {
  36     unsigned Reg, Sub;
  37     bool operator<(RegisterRef R) const {
  38       return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
  39     }
  40   };
  41   typedef std::set<RegisterRef> RegisterSet;
  42
  43   // This is to represent an "index", which is an abstraction of a position
  44   // of an instruction within a basic block.
  45   class IndexType {
  46   public:
  47     enum : unsigned {
  48       None  = 0,
  49       Entry = 1,
  50       Exit  = 2,
  51       First = 11  // 10th + 1st
  52     };
  53     static bool isInstr(IndexType X) { return X.Index >= First; }
  54
  55     IndexType() : Index(None) {}
  56     IndexType(unsigned Idx) : Index(Idx) {}
  57     operator unsigned() const;
  58     bool operator== (unsigned x) const;
  59     bool operator== (IndexType Idx) const;
  60     bool operator!= (unsigned x) const;
  61     bool operator!= (IndexType Idx) const;
  62     IndexType operator++ ();
  63     bool operator< (unsigned Idx) const;
  64     bool operator< (IndexType Idx) const;
  65     bool operator<= (IndexType Idx) const;
  66
  67   private:
  68     bool operator>  (IndexType Idx) const;
  69     bool operator>= (IndexType Idx) const;
  70
  71     unsigned Index;
  72   };
  73
  74   // A range of indices, essentially a representation of a live range.
  75   // This is also used to represent "dead ranges", i.e. ranges where a
  76   // register is dead.
  77   class IndexRange : public std::pair<IndexType,IndexType> {
  78   public:
  79     IndexRange() : Fixed(false), TiedEnd(false) {}
  80     IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)
  81       : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
  82     IndexType start() const { return first; }
  83     IndexType end() const   { return second; }
  84
  85     bool operator< (const IndexRange &A) const {
  86       return start() < A.start();
  87     }
  88     bool overlaps(const IndexRange &A) const;
  89     bool contains(const IndexRange &A) const;
  90     void merge(const IndexRange &A);
  91
  92     bool Fixed;      // Can be renamed?  "Fixed" means "no".
  93     bool TiedEnd;    // The end is not a use, but a dead def tied to a use.
  94
  95   private:
  96     void setStart(const IndexType &S) { first = S; }
  97     void setEnd(const IndexType &E)   { second = E; }
  98   };
  99
 100   // A list of index ranges. This represents liveness of a register
 101   // in a basic block.
 102   class RangeList : public std::vector<IndexRange> {
 103   public:
 104     void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
 105       push_back(IndexRange(Start, End, Fixed, TiedEnd));
 106     }
 107     void add(const IndexRange &Range) {
 108       push_back(Range);
 109     }
 110     void include(const RangeList &RL);
 111     void unionize(bool MergeAdjacent = false);
 112     void subtract(const IndexRange &Range);
 113
 114   private:
 115     void addsub(const IndexRange &A, const IndexRange &B);
 116   };
 117
 118   class InstrIndexMap {
 119   public:
 120     InstrIndexMap(MachineBasicBlock &B);
 121     MachineInstr *getInstr(IndexType Idx) const;
 122     IndexType getIndex(MachineInstr *MI) const;
 123     MachineBasicBlock &getBlock() const { return Block; }
 124     IndexType getPrevIndex(IndexType Idx) const;
 125     IndexType getNextIndex(IndexType Idx) const;
 126     void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI);
 127
 128     friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map);
 129     IndexType First, Last;
 130
 131   private:
 132     MachineBasicBlock &Block;
 133     std::map<IndexType,MachineInstr*> Map;
 134   };
 135
 136   typedef std::map<RegisterRef,RangeList> RegToRangeMap;
 137   RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap);
 138   RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap);
 139   static RegisterSet expandToSubRegs(RegisterRef R,
 140       const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
 141
 142   struct PrintRangeMap {
 143     PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
 144         : Map(M), TRI(I) {}
 145
 146     friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);
 147   private:
 148     const RegToRangeMap &Map;
 149     const TargetRegisterInfo &TRI;
 150   };
 151
 152 private:
 153   RegisterSet getLiveIns(const MachineBasicBlock &B);
 154
 155   void computeInitialLiveRanges(InstrIndexMap &IndexMap,
 156       RegToRangeMap &LiveMap);
 157
 158   MachineFunction &MF;
 159   const HexagonSubtarget &HST;
 160   const TargetInstrInfo &TII;
 161   const TargetRegisterInfo &TRI;
 162   BitVector Reserved;
 163 };
 164
 165
 166 inline HexagonBlockRanges::IndexType::operator unsigned() const {
 167   assert(Index >= First);
 168   return Index;
 169 }
 170
 171 inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
 172   return Index == x;
 173 }
 174
 175 inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
 176   return Index == Idx.Index;
 177 }
 178
 179 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
 180   return Index != x;
 181 }
 182
 183 inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
 184   return Index != Idx.Index;
 185 }
 186
 187 inline
 188 HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {
 189   assert(Index != None);
 190   assert(Index != Exit);
 191   if (Index == Entry)
 192     Index = First;
 193   else
 194     ++Index;
 195   return *this;
 196 }
 197
 198 inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
 199   return operator< (IndexType(Idx));
 200 }
 201
 202 inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {
 203   // !(x < x).
 204   if (Index == Idx.Index)
 205     return false;
 206   // !(None < x) for all x.
 207   // !(x < None) for all x.
 208   if (Index == None || Idx.Index == None)
 209     return false;
 210   // !(Exit < x) for all x.
 211   // !(x < Entry) for all x.
 212   if (Index == Exit || Idx.Index == Entry)
 213     return false;
 214   // Entry < x for all x != Entry.
 215   // x < Exit for all x != Exit.
 216   if (Index == Entry || Idx.Index == Exit)
 217     return true;
 218
 219   return Index < Idx.Index;
 220 }
 221
 222 inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
 223   return operator==(Idx) || operator<(Idx);
 224 }
 225
 226
 227 raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
 228 raw_ostream &operator<< (raw_ostream &OS,
 229       const HexagonBlockRanges::IndexRange &IR);
 230 raw_ostream &operator<< (raw_ostream &OS,
 231       const HexagonBlockRanges::RangeList &RL);
 232 raw_ostream &operator<< (raw_ostream &OS,
 233       const HexagonBlockRanges::InstrIndexMap &M);
 234 raw_ostream &operator<< (raw_ostream &OS,
 235       const HexagonBlockRanges::PrintRangeMap &P);
 236
 237 } // namespace llvm
 238
 239 #endif