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