lib/Target/Hexagon/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 "RDFRegisters.h"
  10 #include "llvm/ADT/BitVector.h"
  11 #include "llvm/CodeGen/MachineFunction.h"
  12 #include "llvm/CodeGen/MachineInstr.h"
  13 #include "llvm/CodeGen/MachineOperand.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(i, &TRI); U.isValid(); ++U)
  91         PU.set(*U);
  92     }
  93     MaskInfos[M].Units = PU.flip();
  94   }
  95 }
  96
  97 RegisterRef PhysicalRegisterInfo::normalize(RegisterRef RR) const {
  98   return RR;
  99 }
 100
 101 std::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
 131 bool 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
 162 bool 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
 197 bool 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
 225 RegisterRef 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
 240 bool 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
 253 bool 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
 268 RegisterAggr &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
 282 RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) {
 283   Units |= RG.Units;
 284   return *this;
 285 }
 286
 287 RegisterAggr &RegisterAggr::intersect(RegisterRef RR) {
 288   return intersect(RegisterAggr(PRI).insert(RR));
 289 }
 290
 291 RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) {
 292   Units &= RG.Units;
 293   return *this;
 294 }
 295
 296 RegisterAggr &RegisterAggr::clear(RegisterRef RR) {
 297   return clear(RegisterAggr(PRI).insert(RR));
 298 }
 299
 300 RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) {
 301   Units.reset(RG.Units);
 302   return *this;
 303 }
 304
 305 RegisterRef 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
 315 RegisterRef RegisterAggr::clearIn(RegisterRef RR) const {
 316   return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();
 317 }
 318
 319 RegisterRef 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
 364 void 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
 371 RegisterAggr::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 }