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

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