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