lib/Target/Hexagon/HexagonBlockRanges.h

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