1 //===- RDFRegisters.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_CODEGEN_RDFREGISTERS_H 10 #define LLVM_CODEGEN_RDFREGISTERS_H 11 12 #include "llvm/ADT/BitVector.h" 13 #include "llvm/ADT/STLExtras.h" 14 #include "llvm/CodeGen/TargetRegisterInfo.h" 15 #include "llvm/MC/LaneBitmask.h" 16 #include <cassert> 17 #include <cstdint> 18 #include <map> 19 #include <set> 20 #include <vector> 21 22 namespace llvm { 23 24 class MachineFunction; 25 class raw_ostream; 26 27 namespace rdf { 28 29 using RegisterId = uint32_t; 30 31 // Template class for a map translating uint32_t into arbitrary types. 32 // The map will act like an indexed set: upon insertion of a new object, 33 // it will automatically assign a new index to it. Index of 0 is treated 34 // as invalid and is never allocated. 35 template <typename T, unsigned N = 32> 36 struct IndexedSet { IndexedSetIndexedSet37 IndexedSet() { Map.reserve(N); } 38 getIndexedSet39 T get(uint32_t Idx) const { 40 // Index Idx corresponds to Map[Idx-1]. 41 assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size()); 42 return Map[Idx-1]; 43 } 44 insertIndexedSet45 uint32_t insert(T Val) { 46 // Linear search. 47 auto F = llvm::find(Map, Val); 48 if (F != Map.end()) 49 return F - Map.begin() + 1; 50 Map.push_back(Val); 51 return Map.size(); // Return actual_index + 1. 52 } 53 findIndexedSet54 uint32_t find(T Val) const { 55 auto F = llvm::find(Map, Val); 56 assert(F != Map.end()); 57 return F - Map.begin() + 1; 58 } 59 sizeIndexedSet60 uint32_t size() const { return Map.size(); } 61 62 using const_iterator = typename std::vector<T>::const_iterator; 63 beginIndexedSet64 const_iterator begin() const { return Map.begin(); } endIndexedSet65 const_iterator end() const { return Map.end(); } 66 67 private: 68 std::vector<T> Map; 69 }; 70 71 struct RegisterRef { 72 RegisterId Reg = 0; 73 LaneBitmask Mask = LaneBitmask::getNone(); 74 75 RegisterRef() = default; 76 explicit RegisterRef(RegisterId R, LaneBitmask M = LaneBitmask::getAll()) RegRegisterRef77 : Reg(R), Mask(R != 0 ? M : LaneBitmask::getNone()) {} 78 79 operator bool() const { 80 return Reg != 0 && Mask.any(); 81 } 82 83 bool operator== (const RegisterRef &RR) const { 84 return Reg == RR.Reg && Mask == RR.Mask; 85 } 86 87 bool operator!= (const RegisterRef &RR) const { 88 return !operator==(RR); 89 } 90 91 bool operator< (const RegisterRef &RR) const { 92 return Reg < RR.Reg || (Reg == RR.Reg && Mask < RR.Mask); 93 } 94 hashRegisterRef95 size_t hash() const { 96 return std::hash<RegisterId>{}(Reg) ^ 97 std::hash<LaneBitmask::Type>{}(Mask.getAsInteger()); 98 } 99 }; 100 101 102 struct PhysicalRegisterInfo { 103 PhysicalRegisterInfo(const TargetRegisterInfo &tri, 104 const MachineFunction &mf); 105 isRegMaskIdPhysicalRegisterInfo106 static bool isRegMaskId(RegisterId R) { 107 return Register::isStackSlot(R); 108 } 109 getRegMaskIdPhysicalRegisterInfo110 RegisterId getRegMaskId(const uint32_t *RM) const { 111 return Register::index2StackSlot(RegMasks.find(RM)); 112 } 113 getRegMaskBitsPhysicalRegisterInfo114 const uint32_t *getRegMaskBits(RegisterId R) const { 115 return RegMasks.get(Register::stackSlot2Index(R)); 116 } 117 aliasPhysicalRegisterInfo118 bool alias(RegisterRef RA, RegisterRef RB) const { 119 if (!isRegMaskId(RA.Reg)) 120 return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB); 121 return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB); 122 } 123 124 std::set<RegisterId> getAliasSet(RegisterId Reg) const; 125 getRefForUnitPhysicalRegisterInfo126 RegisterRef getRefForUnit(uint32_t U) const { 127 return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask); 128 } 129 getMaskUnitsPhysicalRegisterInfo130 const BitVector &getMaskUnits(RegisterId MaskId) const { 131 return MaskInfos[Register::stackSlot2Index(MaskId)].Units; 132 } 133 getUnitAliasesPhysicalRegisterInfo134 const BitVector &getUnitAliases(uint32_t U) const { 135 return AliasInfos[U].Regs; 136 } 137 138 RegisterRef mapTo(RegisterRef RR, unsigned R) const; getTRIPhysicalRegisterInfo139 const TargetRegisterInfo &getTRI() const { return TRI; } 140 141 private: 142 struct RegInfo { 143 const TargetRegisterClass *RegClass = nullptr; 144 }; 145 struct UnitInfo { 146 RegisterId Reg = 0; 147 LaneBitmask Mask; 148 }; 149 struct MaskInfo { 150 BitVector Units; 151 }; 152 struct AliasInfo { 153 BitVector Regs; 154 }; 155 156 const TargetRegisterInfo &TRI; 157 IndexedSet<const uint32_t*> RegMasks; 158 std::vector<RegInfo> RegInfos; 159 std::vector<UnitInfo> UnitInfos; 160 std::vector<MaskInfo> MaskInfos; 161 std::vector<AliasInfo> AliasInfos; 162 163 bool aliasRR(RegisterRef RA, RegisterRef RB) const; 164 bool aliasRM(RegisterRef RR, RegisterRef RM) const; 165 bool aliasMM(RegisterRef RM, RegisterRef RN) const; 166 }; 167 168 struct RegisterAggr { RegisterAggrRegisterAggr169 RegisterAggr(const PhysicalRegisterInfo &pri) 170 : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {} 171 RegisterAggr(const RegisterAggr &RG) = default; 172 countRegisterAggr173 unsigned count() const { return Units.count(); } emptyRegisterAggr174 bool empty() const { return Units.none(); } 175 bool hasAliasOf(RegisterRef RR) const; 176 bool hasCoverOf(RegisterRef RR) const; 177 178 bool operator==(const RegisterAggr &A) const { 179 return DenseMapInfo<BitVector>::isEqual(Units, A.Units); 180 } 181 isCoverOfRegisterAggr182 static bool isCoverOf(RegisterRef RA, RegisterRef RB, 183 const PhysicalRegisterInfo &PRI) { 184 return RegisterAggr(PRI).insert(RA).hasCoverOf(RB); 185 } 186 187 RegisterAggr &insert(RegisterRef RR); 188 RegisterAggr &insert(const RegisterAggr &RG); 189 RegisterAggr &intersect(RegisterRef RR); 190 RegisterAggr &intersect(const RegisterAggr &RG); 191 RegisterAggr &clear(RegisterRef RR); 192 RegisterAggr &clear(const RegisterAggr &RG); 193 194 RegisterRef intersectWith(RegisterRef RR) const; 195 RegisterRef clearIn(RegisterRef RR) const; 196 RegisterRef makeRegRef() const; 197 hashRegisterAggr198 size_t hash() const { 199 return DenseMapInfo<BitVector>::getHashValue(Units); 200 } 201 202 void print(raw_ostream &OS) const; 203 204 struct rr_iterator { 205 using MapType = std::map<RegisterId, LaneBitmask>; 206 207 private: 208 MapType Masks; 209 MapType::iterator Pos; 210 unsigned Index; 211 const RegisterAggr *Owner; 212 213 public: 214 rr_iterator(const RegisterAggr &RG, bool End); 215 216 RegisterRef operator*() const { 217 return RegisterRef(Pos->first, Pos->second); 218 } 219 220 rr_iterator &operator++() { 221 ++Pos; 222 ++Index; 223 return *this; 224 } 225 226 bool operator==(const rr_iterator &I) const { 227 assert(Owner == I.Owner); 228 (void)Owner; 229 return Index == I.Index; 230 } 231 232 bool operator!=(const rr_iterator &I) const { 233 return !(*this == I); 234 } 235 }; 236 rr_beginRegisterAggr237 rr_iterator rr_begin() const { 238 return rr_iterator(*this, false); 239 } rr_endRegisterAggr240 rr_iterator rr_end() const { 241 return rr_iterator(*this, true); 242 } 243 244 private: 245 BitVector Units; 246 const PhysicalRegisterInfo &PRI; 247 }; 248 249 // Optionally print the lane mask, if it is not ~0. 250 struct PrintLaneMaskOpt { PrintLaneMaskOptPrintLaneMaskOpt251 PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {} 252 LaneBitmask Mask; 253 }; 254 raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P); 255 256 raw_ostream &operator<< (raw_ostream &OS, const RegisterAggr &A); 257 } // end namespace rdf 258 259 } // end namespace llvm 260 261 namespace std { 262 template <> struct hash<llvm::rdf::RegisterRef> { 263 size_t operator()(llvm::rdf::RegisterRef A) const { 264 return A.hash(); 265 } 266 }; 267 template <> struct hash<llvm::rdf::RegisterAggr> { 268 size_t operator()(const llvm::rdf::RegisterAggr &A) const { 269 return A.hash(); 270 } 271 }; 272 template <> struct equal_to<llvm::rdf::RegisterAggr> { 273 bool operator()(const llvm::rdf::RegisterAggr &A, 274 const llvm::rdf::RegisterAggr &B) const { 275 return A == B; 276 } 277 }; 278 } 279 #endif // LLVM_CODEGEN_RDFREGISTERS_H 280