421 lines · 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-exception6//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/Format.h"19#include "llvm/Support/MathExtras.h"20#include "llvm/Support/raw_ostream.h"21#include <cassert>22#include <cstdint>23#include <set>24#include <utility>25 26namespace llvm::rdf {27 28PhysicalRegisterInfo::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 } else43 RI.RegClass = RC;44 }45 }46 47 UnitInfos.resize(TRI.getNumRegUnits());48 49 for (MCRegUnit U : TRI.regunits()) {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<MCRegUnit, LaneBitmask> P = *I;62 UnitInfo &UI = UnitInfos[P.first];63 UI.Reg = F;64 UI.Mask = P.second;65 }66 }67 }68 69 for (const uint32_t *RM : TRI.getRegMasks())70 RegMasks.insert(RM);71 for (const MachineBasicBlock &B : mf)72 for (const MachineInstr &In : B)73 for (const MachineOperand &Op : In.operands())74 if (Op.isRegMask())75 RegMasks.insert(Op.getRegMask());76 77 MaskInfos.resize(RegMasks.size() + 1);78 for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) {79 BitVector PU(TRI.getNumRegUnits());80 const uint32_t *MB = RegMasks.get(M);81 for (unsigned I = 1, E = TRI.getNumRegs(); I != E; ++I) {82 if (!(MB[I / 32] & (1u << (I % 32))))83 continue;84 for (MCRegUnit Unit : TRI.regunits(MCRegister::from(I)))85 PU.set(static_cast<unsigned>(Unit));86 }87 MaskInfos[M].Units = PU.flip();88 }89 90 AliasInfos.resize(TRI.getNumRegUnits());91 for (MCRegUnit U : TRI.regunits()) {92 BitVector AS(TRI.getNumRegs());93 for (MCRegUnitRootIterator R(U, &TRI); R.isValid(); ++R)94 for (MCPhysReg S : TRI.superregs_inclusive(*R))95 AS.set(S);96 AliasInfos[U].Regs = AS;97 }98}99 100bool PhysicalRegisterInfo::alias(RegisterRef RA, RegisterRef RB) const {101 return !disjoint(getUnits(RA), getUnits(RB));102}103 104std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterRef RR) const {105 // Do not include Reg in the alias set.106 std::set<RegisterId> AS;107 assert(!RR.isUnit() && "No units allowed");108 if (RR.isMask()) {109 // XXX SLOW110 const uint32_t *MB = getRegMaskBits(RR);111 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {112 if (MB[i / 32] & (1u << (i % 32)))113 continue;114 AS.insert(i);115 }116 return AS;117 }118 119 assert(RR.isReg());120 for (MCRegAliasIterator AI(RR.asMCReg(), &TRI, false); AI.isValid(); ++AI)121 AS.insert(*AI);122 123 return AS;124}125 126std::set<RegisterId> PhysicalRegisterInfo::getUnits(RegisterRef RR) const {127 std::set<RegisterId> Units;128 129 if (RR.isReg()) {130 if (RR.Mask.none())131 return Units; // Empty132 for (MCRegUnitMaskIterator UM(RR.asMCReg(), &TRI); UM.isValid(); ++UM) {133 auto [U, M] = *UM;134 if ((M & RR.Mask).any())135 Units.insert(static_cast<unsigned>(U));136 }137 return Units;138 }139 140 assert(RR.isMask());141 unsigned NumRegs = TRI.getNumRegs();142 const uint32_t *MB = getRegMaskBits(RR);143 for (unsigned I = 0, E = (NumRegs + 31) / 32; I != E; ++I) {144 uint32_t C = ~MB[I]; // Clobbered regs145 if (I == 0) // Reg 0 should be ignored146 C &= maskLeadingOnes<unsigned>(31);147 if (I + 1 == E && NumRegs % 32 != 0) // Last word may be partial148 C &= maskTrailingOnes<unsigned>(NumRegs % 32);149 if (C == 0)150 continue;151 while (C != 0) {152 unsigned T = llvm::countr_zero(C);153 unsigned CR = 32 * I + T; // Clobbered reg154 for (MCRegUnit U : TRI.regunits(CR))155 Units.insert(static_cast<unsigned>(U));156 C &= ~(1u << T);157 }158 }159 return Units;160}161 162RegisterRef PhysicalRegisterInfo::mapTo(RegisterRef RR, RegisterId R) const {163 if (RR.Id == R)164 return RR;165 if (unsigned Idx = TRI.getSubRegIndex(RegisterRef(R).asMCReg(), RR.asMCReg()))166 return RegisterRef(R, TRI.composeSubRegIndexLaneMask(Idx, RR.Mask));167 if (unsigned Idx =168 TRI.getSubRegIndex(RR.asMCReg(), RegisterRef(R).asMCReg())) {169 const RegInfo &RI = RegInfos[R];170 LaneBitmask RCM =171 RI.RegClass ? RI.RegClass->LaneMask : LaneBitmask::getAll();172 LaneBitmask M = TRI.reverseComposeSubRegIndexLaneMask(Idx, RR.Mask);173 return RegisterRef(R, M & RCM);174 }175 llvm_unreachable("Invalid arguments: unrelated registers?");176}177 178bool PhysicalRegisterInfo::equal_to(RegisterRef A, RegisterRef B) const {179 if (!A.isReg() || !B.isReg()) {180 // For non-regs, or comparing reg and non-reg, use only the Id member.181 return A.Id == B.Id;182 }183 184 if (A.Id == B.Id)185 return A.Mask == B.Mask;186 187 // Compare reg units lexicographically.188 MCRegUnitMaskIterator AI(A.asMCReg(), &getTRI());189 MCRegUnitMaskIterator BI(B.asMCReg(), &getTRI());190 while (AI.isValid() && BI.isValid()) {191 auto [AReg, AMask] = *AI;192 auto [BReg, BMask] = *BI;193 194 // If both iterators point to a unit contained in both A and B, then195 // compare the units.196 if ((AMask & A.Mask).any() && (BMask & B.Mask).any()) {197 if (AReg != BReg)198 return false;199 // Units are equal, move on to the next ones.200 ++AI;201 ++BI;202 continue;203 }204 205 if ((AMask & A.Mask).none())206 ++AI;207 if ((BMask & B.Mask).none())208 ++BI;209 }210 // One or both have reached the end.211 return static_cast<int>(AI.isValid()) == static_cast<int>(BI.isValid());212}213 214bool PhysicalRegisterInfo::less(RegisterRef A, RegisterRef B) const {215 if (!A.isReg() || !B.isReg()) {216 // For non-regs, or comparing reg and non-reg, use only the Id member.217 return A.Id < B.Id;218 }219 220 if (A.Id == B.Id)221 return A.Mask < B.Mask;222 if (A.Mask == B.Mask)223 return A.Id < B.Id;224 225 // Compare reg units lexicographically.226 llvm::MCRegUnitMaskIterator AI(A.asMCReg(), &getTRI());227 llvm::MCRegUnitMaskIterator BI(B.asMCReg(), &getTRI());228 while (AI.isValid() && BI.isValid()) {229 auto [AReg, AMask] = *AI;230 auto [BReg, BMask] = *BI;231 232 // If both iterators point to a unit contained in both A and B, then233 // compare the units.234 if ((AMask & A.Mask).any() && (BMask & B.Mask).any()) {235 if (AReg != BReg)236 return AReg < BReg;237 // Units are equal, move on to the next ones.238 ++AI;239 ++BI;240 continue;241 }242 243 if ((AMask & A.Mask).none())244 ++AI;245 if ((BMask & B.Mask).none())246 ++BI;247 }248 // One or both have reached the end: assume invalid < valid.249 return static_cast<int>(AI.isValid()) < static_cast<int>(BI.isValid());250}251 252void PhysicalRegisterInfo::print(raw_ostream &OS, RegisterRef A) const {253 if (A.isReg()) {254 MCRegister Reg = A.asMCReg();255 if (Reg && Reg.id() < TRI.getNumRegs())256 OS << TRI.getName(Reg);257 else258 OS << printReg(Reg, &TRI);259 OS << PrintLaneMaskShort(A.Mask);260 } else if (A.isUnit()) {261 OS << printRegUnit(A.asMCRegUnit(), &TRI);262 } else {263 unsigned Idx = A.asMaskIdx();264 const char *Fmt = Idx < 0x10000 ? "%04x" : "%08x";265 OS << "M#" << format(Fmt, Idx);266 }267}268 269void PhysicalRegisterInfo::print(raw_ostream &OS, const RegisterAggr &A) const {270 OS << '{';271 for (unsigned U : A.units())272 OS << ' ' << printRegUnit(static_cast<MCRegUnit>(U), &TRI);273 OS << " }";274}275 276bool RegisterAggr::hasAliasOf(RegisterRef RR) const {277 if (RR.isMask())278 return Units.anyCommon(PRI.getMaskUnits(RR));279 280 for (MCRegUnitMaskIterator U(RR.asMCReg(), &PRI.getTRI()); U.isValid(); ++U) {281 auto [Unit, LaneMask] = *U;282 if ((LaneMask & RR.Mask).any())283 if (Units.test(static_cast<unsigned>(Unit)))284 return true;285 }286 return false;287}288 289bool RegisterAggr::hasCoverOf(RegisterRef RR) const {290 if (RR.isMask()) {291 BitVector T(PRI.getMaskUnits(RR));292 return T.reset(Units).none();293 }294 295 for (MCRegUnitMaskIterator U(RR.asMCReg(), &PRI.getTRI()); U.isValid(); ++U) {296 auto [Unit, LaneMask] = *U;297 if ((LaneMask & RR.Mask).any())298 if (!Units.test(static_cast<unsigned>(Unit)))299 return false;300 }301 return true;302}303 304RegisterAggr &RegisterAggr::insert(RegisterRef RR) {305 if (RR.isMask()) {306 Units |= PRI.getMaskUnits(RR);307 return *this;308 }309 310 for (MCRegUnitMaskIterator U(RR.asMCReg(), &PRI.getTRI()); U.isValid(); ++U) {311 auto [Unit, LaneMask] = *U;312 if ((LaneMask & RR.Mask).any())313 Units.set(static_cast<unsigned>(Unit));314 }315 return *this;316}317 318RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) {319 Units |= RG.Units;320 return *this;321}322 323RegisterAggr &RegisterAggr::intersect(RegisterRef RR) {324 return intersect(RegisterAggr(PRI).insert(RR));325}326 327RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) {328 Units &= RG.Units;329 return *this;330}331 332RegisterAggr &RegisterAggr::clear(RegisterRef RR) {333 return clear(RegisterAggr(PRI).insert(RR));334}335 336RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) {337 Units.reset(RG.Units);338 return *this;339}340 341RegisterRef RegisterAggr::intersectWith(RegisterRef RR) const {342 RegisterAggr T(PRI);343 T.insert(RR).intersect(*this);344 if (T.empty())345 return RegisterRef();346 RegisterRef NR = T.makeRegRef();347 assert(NR);348 return NR;349}350 351RegisterRef RegisterAggr::clearIn(RegisterRef RR) const {352 return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();353}354 355RegisterRef RegisterAggr::makeRegRef() const {356 int U = Units.find_first();357 if (U < 0)358 return RegisterRef();359 360 // Find the set of all registers that are aliased to all the units361 // in this aggregate.362 363 // Get all the registers aliased to the first unit in the bit vector.364 BitVector Regs = PRI.getUnitAliases(static_cast<MCRegUnit>(U));365 U = Units.find_next(U);366 367 // For each other unit, intersect it with the set of all registers368 // aliased that unit.369 while (U >= 0) {370 Regs &= PRI.getUnitAliases(static_cast<MCRegUnit>(U));371 U = Units.find_next(U);372 }373 374 // If there is at least one register remaining, pick the first one,375 // and consolidate the masks of all of its units contained in this376 // aggregate.377 378 int F = Regs.find_first();379 if (F <= 0)380 return RegisterRef();381 382 LaneBitmask M;383 for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) {384 auto [Unit, LaneMask] = *I;385 if (Units.test(static_cast<unsigned>(Unit)))386 M |= LaneMask;387 }388 return RegisterRef(F, M);389}390 391RegisterAggr::ref_iterator::ref_iterator(const RegisterAggr &RG, bool End)392 : Owner(&RG) {393 for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) {394 RegisterRef R = RG.PRI.getRefForUnit(static_cast<MCRegUnit>(U));395 Masks[R.Id] |= R.Mask;396 }397 Pos = End ? Masks.end() : Masks.begin();398 Index = End ? Masks.size() : 0;399}400 401raw_ostream &operator<<(raw_ostream &OS, const RegisterAggr &A) {402 A.getPRI().print(OS, A);403 return OS;404}405 406raw_ostream &operator<<(raw_ostream &OS, const PrintLaneMaskShort &P) {407 if (P.Mask.all())408 return OS;409 if (P.Mask.none())410 return OS << ":*none*";411 412 LaneBitmask::Type Val = P.Mask.getAsInteger();413 if ((Val & 0xffff) == Val)414 return OS << ':' << format("%04llX", Val);415 if ((Val & 0xffffffff) == Val)416 return OS << ':' << format("%08llX", Val);417 return OS << ':' << PrintLaneMask(P.Mask);418}419 420} // namespace llvm::rdf421