llvm/lib/CodeGen/RDFRegisters.cpp

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