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 ⤅ 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 247