1//===- RDFRegisters.cpp ---------------------------------------------------===// 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#include "llvm/ADT/BitVector.h" 10#include "llvm/CodeGen/MachineFunction.h" 11#include "llvm/CodeGen/MachineInstr.h" 12#include "llvm/CodeGen/MachineOperand.h" 13#include "llvm/CodeGen/RDFRegisters.h" 14#include "llvm/CodeGen/TargetRegisterInfo.h" 15#include "llvm/MC/LaneBitmask.h" 16#include "llvm/MC/MCRegisterInfo.h" 17#include "llvm/Support/ErrorHandling.h" 18#include "llvm/Support/raw_ostream.h" 19#include <cassert> 20#include <cstdint> 21#include <set> 22#include <utility> 23 24using namespace llvm; 25using namespace rdf; 26 27PhysicalRegisterInfo::PhysicalRegisterInfo(const TargetRegisterInfo &tri, 28 const MachineFunction &mf) 29 : TRI(tri) { 30 RegInfos.resize(TRI.getNumRegs()); 31 32 BitVector BadRC(TRI.getNumRegs()); 33 for (const TargetRegisterClass *RC : TRI.regclasses()) { 34 for (MCPhysReg R : *RC) { 35 RegInfo &RI = RegInfos[R]; 36 if (RI.RegClass != nullptr && !BadRC[R]) { 37 if (RC->LaneMask != RI.RegClass->LaneMask) { 38 BadRC.set(R); 39 RI.RegClass = nullptr; 40 } 41 } else 42 RI.RegClass = RC; 43 } 44 } 45 46 UnitInfos.resize(TRI.getNumRegUnits()); 47 48 for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) { 49 if (UnitInfos[U].Reg != 0) 50 continue; 51 MCRegUnitRootIterator R(U, &TRI); 52 assert(R.isValid()); 53 RegisterId F = *R; 54 ++R; 55 if (R.isValid()) { 56 UnitInfos[U].Mask = LaneBitmask::getAll(); 57 UnitInfos[U].Reg = F; 58 } else { 59 for (MCRegUnitMaskIterator I(F, &TRI); I.isValid(); ++I) { 60 std::pair<uint32_t,LaneBitmask> P = *I; 61 UnitInfo &UI = UnitInfos[P.first]; 62 UI.Reg = F; 63 if (P.second.any()) { 64 UI.Mask = P.second; 65 } else { 66 if (const TargetRegisterClass *RC = RegInfos[F].RegClass) 67 UI.Mask = RC->LaneMask; 68 else 69 UI.Mask = LaneBitmask::getAll(); 70 } 71 } 72 } 73 } 74 75 for (const uint32_t *RM : TRI.getRegMasks()) 76 RegMasks.insert(RM); 77 for (const MachineBasicBlock &B : mf) 78 for (const MachineInstr &In : B) 79 for (const MachineOperand &Op : In.operands()) 80 if (Op.isRegMask()) 81 RegMasks.insert(Op.getRegMask()); 82 83 MaskInfos.resize(RegMasks.size()+1); 84 for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) { 85 BitVector PU(TRI.getNumRegUnits()); 86 const uint32_t *MB = RegMasks.get(M); 87 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) { 88 if (!(MB[i/32] & (1u << (i%32)))) 89 continue; 90 for (MCRegUnitIterator U(i, &TRI); U.isValid(); ++U) 91 PU.set(*U); 92 } 93 MaskInfos[M].Units = PU.flip(); 94 } 95} 96 97RegisterRef PhysicalRegisterInfo::normalize(RegisterRef RR) const { 98 return RR; 99} 100 101std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const { 102 // Do not include RR in the alias set. 103 std::set<RegisterId> AS; 104 assert(isRegMaskId(Reg) || Register::isPhysicalRegister(Reg)); 105 if (isRegMaskId(Reg)) { 106 // XXX SLOW 107 const uint32_t *MB = getRegMaskBits(Reg); 108 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) { 109 if (MB[i/32] & (1u << (i%32))) 110 continue; 111 AS.insert(i); 112 } 113 for (const uint32_t *RM : RegMasks) { 114 RegisterId MI = getRegMaskId(RM); 115 if (MI != Reg && aliasMM(RegisterRef(Reg), RegisterRef(MI))) 116 AS.insert(MI); 117 } 118 return AS; 119 } 120 121 for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI) 122 AS.insert(*AI); 123 for (const uint32_t *RM : RegMasks) { 124 RegisterId MI = getRegMaskId(RM); 125 if (aliasRM(RegisterRef(Reg), RegisterRef(MI))) 126 AS.insert(MI); 127 } 128 return AS; 129} 130 131bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const { 132 assert(Register::isPhysicalRegister(RA.Reg)); 133 assert(Register::isPhysicalRegister(RB.Reg)); 134 135 MCRegUnitMaskIterator UMA(RA.Reg, &TRI); 136 MCRegUnitMaskIterator UMB(RB.Reg, &TRI); 137 // Reg units are returned in the numerical order. 138 while (UMA.isValid() && UMB.isValid()) { 139 // Skip units that are masked off in RA. 140 std::pair<RegisterId,LaneBitmask> PA = *UMA; 141 if (PA.second.any() && (PA.second & RA.Mask).none()) { 142 ++UMA; 143 continue; 144 } 145 // Skip units that are masked off in RB. 146 std::pair<RegisterId,LaneBitmask> PB = *UMB; 147 if (PB.second.any() && (PB.second & RB.Mask).none()) { 148 ++UMB; 149 continue; 150 } 151 152 if (PA.first == PB.first) 153 return true; 154 if (PA.first < PB.first) 155 ++UMA; 156 else if (PB.first < PA.first) 157 ++UMB; 158 } 159 return false; 160} 161 162bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const { 163 assert(Register::isPhysicalRegister(RR.Reg) && isRegMaskId(RM.Reg)); 164 const uint32_t *MB = getRegMaskBits(RM.Reg); 165 bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32)); 166 // If the lane mask information is "full", e.g. when the given lane mask 167 // is a superset of the lane mask from the register class, check the regmask 168 // bit directly. 169 if (RR.Mask == LaneBitmask::getAll()) 170 return !Preserved; 171 const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass; 172 if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask) 173 return !Preserved; 174 175 // Otherwise, check all subregisters whose lane mask overlaps the given 176 // mask. For each such register, if it is preserved by the regmask, then 177 // clear the corresponding bits in the given mask. If at the end, all 178 // bits have been cleared, the register does not alias the regmask (i.e. 179 // is it preserved by it). 180 LaneBitmask M = RR.Mask; 181 for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) { 182 LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex()); 183 if ((SM & RR.Mask).none()) 184 continue; 185 unsigned SR = SI.getSubReg(); 186 if (!(MB[SR/32] & (1u << (SR%32)))) 187 continue; 188 // The subregister SR is preserved. 189 M &= ~SM; 190 if (M.none()) 191 return false; 192 } 193 194 return true; 195} 196 197bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const { 198 assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg)); 199 unsigned NumRegs = TRI.getNumRegs(); 200 const uint32_t *BM = getRegMaskBits(RM.Reg); 201 const uint32_t *BN = getRegMaskBits(RN.Reg); 202 203 for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) { 204 // Intersect the negations of both words. Disregard reg=0, 205 // i.e. 0th bit in the 0th word. 206 uint32_t C = ~BM[w] & ~BN[w]; 207 if (w == 0) 208 C &= ~1; 209 if (C) 210 return true; 211 } 212 213 // Check the remaining registers in the last word. 214 unsigned TailRegs = NumRegs % 32; 215 if (TailRegs == 0) 216 return false; 217 unsigned TW = NumRegs / 32; 218 uint32_t TailMask = (1u << TailRegs) - 1; 219 if (~BM[TW] & ~BN[TW] & TailMask) 220 return true; 221 222 return false; 223} 224 225RegisterRef PhysicalRegisterInfo::mapTo(RegisterRef RR, unsigned R) const { 226 if (RR.Reg == R) 227 return RR; 228 if (unsigned Idx = TRI.getSubRegIndex(R, RR.Reg)) 229 return RegisterRef(R, TRI.composeSubRegIndexLaneMask(Idx, RR.Mask)); 230 if (unsigned Idx = TRI.getSubRegIndex(RR.Reg, R)) { 231 const RegInfo &RI = RegInfos[R]; 232 LaneBitmask RCM = RI.RegClass ? RI.RegClass->LaneMask 233 : LaneBitmask::getAll(); 234 LaneBitmask M = TRI.reverseComposeSubRegIndexLaneMask(Idx, RR.Mask); 235 return RegisterRef(R, M & RCM); 236 } 237 llvm_unreachable("Invalid arguments: unrelated registers?"); 238} 239 240bool RegisterAggr::hasAliasOf(RegisterRef RR) const { 241 if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) 242 return Units.anyCommon(PRI.getMaskUnits(RR.Reg)); 243 244 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) { 245 std::pair<uint32_t,LaneBitmask> P = *U; 246 if (P.second.none() || (P.second & RR.Mask).any()) 247 if (Units.test(P.first)) 248 return true; 249 } 250 return false; 251} 252 253bool RegisterAggr::hasCoverOf(RegisterRef RR) const { 254 if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { 255 BitVector T(PRI.getMaskUnits(RR.Reg)); 256 return T.reset(Units).none(); 257 } 258 259 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) { 260 std::pair<uint32_t,LaneBitmask> P = *U; 261 if (P.second.none() || (P.second & RR.Mask).any()) 262 if (!Units.test(P.first)) 263 return false; 264 } 265 return true; 266} 267 268RegisterAggr &RegisterAggr::insert(RegisterRef RR) { 269 if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { 270 Units |= PRI.getMaskUnits(RR.Reg); 271 return *this; 272 } 273 274 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) { 275 std::pair<uint32_t,LaneBitmask> P = *U; 276 if (P.second.none() || (P.second & RR.Mask).any()) 277 Units.set(P.first); 278 } 279 return *this; 280} 281 282RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) { 283 Units |= RG.Units; 284 return *this; 285} 286 287RegisterAggr &RegisterAggr::intersect(RegisterRef RR) { 288 return intersect(RegisterAggr(PRI).insert(RR)); 289} 290 291RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) { 292 Units &= RG.Units; 293 return *this; 294} 295 296RegisterAggr &RegisterAggr::clear(RegisterRef RR) { 297 return clear(RegisterAggr(PRI).insert(RR)); 298} 299 300RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) { 301 Units.reset(RG.Units); 302 return *this; 303} 304 305RegisterRef RegisterAggr::intersectWith(RegisterRef RR) const { 306 RegisterAggr T(PRI); 307 T.insert(RR).intersect(*this); 308 if (T.empty()) 309 return RegisterRef(); 310 RegisterRef NR = T.makeRegRef(); 311 assert(NR); 312 return NR; 313} 314 315RegisterRef RegisterAggr::clearIn(RegisterRef RR) const { 316 return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef(); 317} 318 319RegisterRef RegisterAggr::makeRegRef() const { 320 int U = Units.find_first(); 321 if (U < 0) 322 return RegisterRef(); 323 324 auto AliasedRegs = [this] (uint32_t Unit, BitVector &Regs) { 325 for (MCRegUnitRootIterator R(Unit, &PRI.getTRI()); R.isValid(); ++R) 326 for (MCSuperRegIterator S(*R, &PRI.getTRI(), true); S.isValid(); ++S) 327 Regs.set(*S); 328 }; 329 330 // Find the set of all registers that are aliased to all the units 331 // in this aggregate. 332 333 // Get all the registers aliased to the first unit in the bit vector. 334 BitVector Regs(PRI.getTRI().getNumRegs()); 335 AliasedRegs(U, Regs); 336 U = Units.find_next(U); 337 338 // For each other unit, intersect it with the set of all registers 339 // aliased that unit. 340 while (U >= 0) { 341 BitVector AR(PRI.getTRI().getNumRegs()); 342 AliasedRegs(U, AR); 343 Regs &= AR; 344 U = Units.find_next(U); 345 } 346 347 // If there is at least one register remaining, pick the first one, 348 // and consolidate the masks of all of its units contained in this 349 // aggregate. 350 351 int F = Regs.find_first(); 352 if (F <= 0) 353 return RegisterRef(); 354 355 LaneBitmask M; 356 for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) { 357 std::pair<uint32_t,LaneBitmask> P = *I; 358 if (Units.test(P.first)) 359 M |= P.second.none() ? LaneBitmask::getAll() : P.second; 360 } 361 return RegisterRef(F, M); 362} 363 364void RegisterAggr::print(raw_ostream &OS) const { 365 OS << '{'; 366 for (int U = Units.find_first(); U >= 0; U = Units.find_next(U)) 367 OS << ' ' << printRegUnit(U, &PRI.getTRI()); 368 OS << " }"; 369} 370 371RegisterAggr::rr_iterator::rr_iterator(const RegisterAggr &RG, 372 bool End) 373 : Owner(&RG) { 374 for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) { 375 RegisterRef R = RG.PRI.getRefForUnit(U); 376 Masks[R.Reg] |= R.Mask; 377 } 378 Pos = End ? Masks.end() : Masks.begin(); 379 Index = End ? Masks.size() : 0; 380} 381