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 }
382