contrib/llvm/lib/Target/Hexagon/RDFRegisters.cpp

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