Line data Source code
1 : //==- TargetRegisterInfo.cpp - Target Register Information Implementation --==//
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 : // This file implements the TargetRegisterInfo interface.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "llvm/CodeGen/TargetRegisterInfo.h"
15 : #include "llvm/ADT/ArrayRef.h"
16 : #include "llvm/ADT/BitVector.h"
17 : #include "llvm/ADT/STLExtras.h"
18 : #include "llvm/ADT/StringExtras.h"
19 : #include "llvm/CodeGen/MachineFrameInfo.h"
20 : #include "llvm/CodeGen/MachineFunction.h"
21 : #include "llvm/CodeGen/MachineRegisterInfo.h"
22 : #include "llvm/CodeGen/TargetFrameLowering.h"
23 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
24 : #include "llvm/CodeGen/VirtRegMap.h"
25 : #include "llvm/Config/llvm-config.h"
26 : #include "llvm/IR/Attributes.h"
27 : #include "llvm/IR/Function.h"
28 : #include "llvm/MC/MCRegisterInfo.h"
29 : #include "llvm/Support/Compiler.h"
30 : #include "llvm/Support/Debug.h"
31 : #include "llvm/Support/MachineValueType.h"
32 : #include "llvm/Support/MathExtras.h"
33 : #include "llvm/Support/Printable.h"
34 : #include "llvm/Support/raw_ostream.h"
35 : #include <cassert>
36 : #include <utility>
37 :
38 : #define DEBUG_TYPE "target-reg-info"
39 :
40 : using namespace llvm;
41 :
42 41319 : TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
43 : regclass_iterator RCB, regclass_iterator RCE,
44 : const char *const *SRINames,
45 : const LaneBitmask *SRILaneMasks,
46 : LaneBitmask SRICoveringLanes,
47 : const RegClassInfo *const RCIs,
48 41319 : unsigned Mode)
49 : : InfoDesc(ID), SubRegIndexNames(SRINames),
50 : SubRegIndexLaneMasks(SRILaneMasks),
51 : RegClassBegin(RCB), RegClassEnd(RCE),
52 : CoveringLanes(SRICoveringLanes),
53 41319 : RCInfos(RCIs), HwMode(Mode) {
54 41319 : }
55 :
56 : TargetRegisterInfo::~TargetRegisterInfo() = default;
57 :
58 2011683 : void TargetRegisterInfo::markSuperRegs(BitVector &RegisterSet, unsigned Reg)
59 : const {
60 10575221 : for (MCSuperRegIterator AI(Reg, this, true); AI.isValid(); ++AI)
61 : RegisterSet.set(*AI);
62 2011683 : }
63 :
64 0 : bool TargetRegisterInfo::checkAllSuperRegsMarked(const BitVector &RegisterSet,
65 : ArrayRef<MCPhysReg> Exceptions) const {
66 : // Check that all super registers of reserved regs are reserved as well.
67 0 : BitVector Checked(getNumRegs());
68 0 : for (unsigned Reg : RegisterSet.set_bits()) {
69 0 : if (Checked[Reg])
70 : continue;
71 0 : for (MCSuperRegIterator SR(Reg, this); SR.isValid(); ++SR) {
72 0 : if (!RegisterSet[*SR] && !is_contained(Exceptions, Reg)) {
73 0 : dbgs() << "Error: Super register " << printReg(*SR, this)
74 0 : << " of reserved register " << printReg(Reg, this)
75 0 : << " is not reserved.\n";
76 : return false;
77 : }
78 :
79 : // We transitively check superregs. So we can remember this for later
80 : // to avoid compiletime explosion in deep register hierarchies.
81 : Checked.set(*SR);
82 : }
83 : }
84 0 : return true;
85 : }
86 :
87 : namespace llvm {
88 :
89 510232 : Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI,
90 : unsigned SubIdx, const MachineRegisterInfo *MRI) {
91 : return Printable([Reg, TRI, SubIdx, MRI](raw_ostream &OS) {
92 : if (!Reg)
93 : OS << "$noreg";
94 : else if (TargetRegisterInfo::isStackSlot(Reg))
95 : OS << "SS#" << TargetRegisterInfo::stackSlot2Index(Reg);
96 : else if (TargetRegisterInfo::isVirtualRegister(Reg)) {
97 : StringRef Name = MRI ? MRI->getVRegName(Reg) : "";
98 : if (Name != "") {
99 : OS << '%' << Name;
100 : } else {
101 : OS << '%' << TargetRegisterInfo::virtReg2Index(Reg);
102 : }
103 : }
104 : else if (!TRI)
105 : OS << '$' << "physreg" << Reg;
106 : else if (Reg < TRI->getNumRegs()) {
107 : OS << '$';
108 : printLowerCase(TRI->getName(Reg), OS);
109 : } else
110 : llvm_unreachable("Register kind is unsupported.");
111 :
112 : if (SubIdx) {
113 : if (TRI)
114 : OS << ':' << TRI->getSubRegIndexName(SubIdx);
115 : else
116 : OS << ":sub(" << SubIdx << ')';
117 : }
118 510232 : });
119 : }
120 :
121 0 : Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI) {
122 : return Printable([Unit, TRI](raw_ostream &OS) {
123 : // Generic printout when TRI is missing.
124 : if (!TRI) {
125 : OS << "Unit~" << Unit;
126 : return;
127 : }
128 :
129 : // Check for invalid register units.
130 : if (Unit >= TRI->getNumRegUnits()) {
131 : OS << "BadUnit~" << Unit;
132 : return;
133 : }
134 :
135 : // Normal units have at least one root.
136 : MCRegUnitRootIterator Roots(Unit, TRI);
137 : assert(Roots.isValid() && "Unit has no roots.");
138 : OS << TRI->getName(*Roots);
139 : for (++Roots; Roots.isValid(); ++Roots)
140 : OS << '~' << TRI->getName(*Roots);
141 0 : });
142 : }
143 :
144 0 : Printable printVRegOrUnit(unsigned Unit, const TargetRegisterInfo *TRI) {
145 : return Printable([Unit, TRI](raw_ostream &OS) {
146 : if (TRI && TRI->isVirtualRegister(Unit)) {
147 : OS << '%' << TargetRegisterInfo::virtReg2Index(Unit);
148 : } else {
149 : OS << printRegUnit(Unit, TRI);
150 : }
151 0 : });
152 : }
153 :
154 69701 : Printable printRegClassOrBank(unsigned Reg, const MachineRegisterInfo &RegInfo,
155 : const TargetRegisterInfo *TRI) {
156 : return Printable([Reg, &RegInfo, TRI](raw_ostream &OS) {
157 : if (RegInfo.getRegClassOrNull(Reg))
158 : OS << StringRef(TRI->getRegClassName(RegInfo.getRegClass(Reg))).lower();
159 : else if (RegInfo.getRegBankOrNull(Reg))
160 : OS << StringRef(RegInfo.getRegBankOrNull(Reg)->getName()).lower();
161 : else {
162 : OS << "_";
163 : assert((RegInfo.def_empty(Reg) || RegInfo.getType(Reg).isValid()) &&
164 : "Generic registers must have a valid type");
165 : }
166 69701 : });
167 : }
168 :
169 : } // end namespace llvm
170 :
171 : /// getAllocatableClass - Return the maximal subclass of the given register
172 : /// class that is alloctable, or NULL.
173 : const TargetRegisterClass *
174 19412306 : TargetRegisterInfo::getAllocatableClass(const TargetRegisterClass *RC) const {
175 19412306 : if (!RC || RC->isAllocatable())
176 : return RC;
177 :
178 30088 : for (BitMaskClassIterator It(RC->getSubClassMask(), *this); It.isValid();
179 : ++It) {
180 15305 : const TargetRegisterClass *SubRC = getRegClass(It.getID());
181 30610 : if (SubRC->isAllocatable())
182 260 : return SubRC;
183 : }
184 14783 : return nullptr;
185 : }
186 :
187 : /// getMinimalPhysRegClass - Returns the Register Class of a physical
188 : /// register of the given type, picking the most sub register class of
189 : /// the right type that contains this physreg.
190 : const TargetRegisterClass *
191 1392033 : TargetRegisterInfo::getMinimalPhysRegClass(unsigned reg, MVT VT) const {
192 : assert(isPhysicalRegister(reg) && "reg must be a physical register");
193 :
194 : // Pick the most sub register class of the right type that contains
195 : // this physreg.
196 : const TargetRegisterClass* BestRC = nullptr;
197 133055976 : for (const TargetRegisterClass* RC : regclasses()) {
198 146027404 : if ((VT == MVT::Other || isTypeLegalForClass(*RC, VT)) &&
199 168919960 : RC->contains(reg) && (!BestRC || BestRC->hasSubClass(RC)))
200 : BestRC = RC;
201 : }
202 :
203 : assert(BestRC && "Couldn't find the register class");
204 1392033 : return BestRC;
205 : }
206 :
207 : /// getAllocatableSetForRC - Toggle the bits that represent allocatable
208 : /// registers for the specific register class.
209 4255 : static void getAllocatableSetForRC(const MachineFunction &MF,
210 : const TargetRegisterClass *RC, BitVector &R){
211 : assert(RC->isAllocatable() && "invalid for nonallocatable sets");
212 : ArrayRef<MCPhysReg> Order = RC->getRawAllocationOrder(MF);
213 202403 : for (unsigned i = 0; i != Order.size(); ++i)
214 198148 : R.set(Order[i]);
215 4255 : }
216 :
217 3595 : BitVector TargetRegisterInfo::getAllocatableSet(const MachineFunction &MF,
218 : const TargetRegisterClass *RC) const {
219 3595 : BitVector Allocatable(getNumRegs());
220 3595 : if (RC) {
221 : // A register class with no allocatable subclass returns an empty set.
222 3584 : const TargetRegisterClass *SubClass = getAllocatableClass(RC);
223 3584 : if (SubClass)
224 3584 : getAllocatableSetForRC(MF, SubClass, Allocatable);
225 : } else {
226 902 : for (const TargetRegisterClass *C : regclasses())
227 1782 : if (C->isAllocatable())
228 671 : getAllocatableSetForRC(MF, C, Allocatable);
229 : }
230 :
231 : // Mask out the reserved registers
232 3595 : BitVector Reserved = getReservedRegs(MF);
233 3595 : Allocatable &= Reserved.flip();
234 :
235 3595 : return Allocatable;
236 : }
237 :
238 : static inline
239 11130150 : const TargetRegisterClass *firstCommonClass(const uint32_t *A,
240 : const uint32_t *B,
241 : const TargetRegisterInfo *TRI,
242 : const MVT::SimpleValueType SVT =
243 : MVT::SimpleValueType::Any) {
244 : const MVT VT(SVT);
245 27328999 : for (unsigned I = 0, E = TRI->getNumRegClasses(); I < E; I += 32)
246 19507794 : if (unsigned Common = *A++ & *B++) {
247 : const TargetRegisterClass *RC =
248 3308954 : TRI->getRegClass(I + countTrailingZeros(Common));
249 3311154 : if (SVT == MVT::SimpleValueType::Any || TRI->isTypeLegalForClass(*RC, VT))
250 3308945 : return RC;
251 : }
252 : return nullptr;
253 : }
254 :
255 : const TargetRegisterClass *
256 20398092 : TargetRegisterInfo::getCommonSubClass(const TargetRegisterClass *A,
257 : const TargetRegisterClass *B,
258 : const MVT::SimpleValueType SVT) const {
259 : // First take care of the trivial cases.
260 20398092 : if (A == B)
261 : return A;
262 8713639 : if (!A || !B)
263 : return nullptr;
264 :
265 : // Register classes are ordered topologically, so the largest common
266 : // sub-class it the common sub-class with the smallest ID.
267 8713636 : return firstCommonClass(A->getSubClassMask(), B->getSubClassMask(), this, SVT);
268 : }
269 :
270 : const TargetRegisterClass *
271 1912367 : TargetRegisterInfo::getMatchingSuperRegClass(const TargetRegisterClass *A,
272 : const TargetRegisterClass *B,
273 : unsigned Idx) const {
274 : assert(A && B && "Missing register class");
275 : assert(Idx && "Bad sub-register index");
276 :
277 : // Find Idx in the list of super-register indices.
278 4038157 : for (SuperRegClassIterator RCI(B, this); RCI.isValid(); ++RCI)
279 4033498 : if (RCI.getSubReg() == Idx)
280 : // The bit mask contains all register classes that are projected into B
281 : // by Idx. Find a class that is also a sub-class of A.
282 1907708 : return firstCommonClass(RCI.getMask(), A->getSubClassMask(), this);
283 : return nullptr;
284 : }
285 :
286 69651 : const TargetRegisterClass *TargetRegisterInfo::
287 : getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
288 : const TargetRegisterClass *RCB, unsigned SubB,
289 : unsigned &PreA, unsigned &PreB) const {
290 : assert(RCA && SubA && RCB && SubB && "Invalid arguments");
291 :
292 : // Search all pairs of sub-register indices that project into RCA and RCB
293 : // respectively. This is quadratic, but usually the sets are very small. On
294 : // most targets like X86, there will only be a single sub-register index
295 : // (e.g., sub_16bit projecting into GR16).
296 : //
297 : // The worst case is a register class like DPR on ARM.
298 : // We have indices dsub_0..dsub_7 projecting into that class.
299 : //
300 : // It is very common that one register class is a sub-register of the other.
301 : // Arrange for RCA to be the larger register so the answer will be found in
302 : // the first iteration. This makes the search linear for the most common
303 : // case.
304 : const TargetRegisterClass *BestRC = nullptr;
305 : unsigned *BestPreA = &PreA;
306 : unsigned *BestPreB = &PreB;
307 69651 : if (getRegSizeInBits(*RCA) < getRegSizeInBits(*RCB)) {
308 : std::swap(RCA, RCB);
309 : std::swap(SubA, SubB);
310 : std::swap(BestPreA, BestPreB);
311 : }
312 :
313 : // Also terminate the search one we have found a register class as small as
314 : // RCA.
315 : unsigned MinSize = getRegSizeInBits(*RCA);
316 :
317 116905 : for (SuperRegClassIterator IA(RCA, this, true); IA.isValid(); ++IA) {
318 : unsigned FinalA = composeSubRegIndices(IA.getSubReg(), SubA);
319 556060 : for (SuperRegClassIterator IB(RCB, this, true); IB.isValid(); ++IB) {
320 : // Check if a common super-register class exists for this index pair.
321 : const TargetRegisterClass *RC =
322 508806 : firstCommonClass(IA.getMask(), IB.getMask(), this);
323 508806 : if (!RC || getRegSizeInBits(*RC) < MinSize)
324 : continue;
325 :
326 : // The indexes must compose identically: PreA+SubA == PreB+SubB.
327 : unsigned FinalB = composeSubRegIndices(IB.getSubReg(), SubB);
328 408582 : if (FinalA != FinalB)
329 : continue;
330 :
331 : // Is RC a better candidate than BestRC?
332 77891 : if (BestRC && getRegSizeInBits(*RC) >= getRegSizeInBits(*BestRC))
333 : continue;
334 :
335 : // Yes, RC is the smallest super-register seen so far.
336 : BestRC = RC;
337 63715 : *BestPreA = IA.getSubReg();
338 63715 : *BestPreB = IB.getSubReg();
339 :
340 : // Bail early if we reached MinSize. We won't find a better candidate.
341 63715 : if (getRegSizeInBits(*BestRC) == MinSize)
342 : return BestRC;
343 : }
344 : }
345 7321 : return BestRC;
346 : }
347 :
348 : /// Check if the registers defined by the pair (RegisterClass, SubReg)
349 : /// share the same register file.
350 162156 : static bool shareSameRegisterFile(const TargetRegisterInfo &TRI,
351 : const TargetRegisterClass *DefRC,
352 : unsigned DefSubReg,
353 : const TargetRegisterClass *SrcRC,
354 : unsigned SrcSubReg) {
355 : // Same register class.
356 162156 : if (DefRC == SrcRC)
357 : return true;
358 :
359 : // Both operands are sub registers. Check if they share a register class.
360 : unsigned SrcIdx, DefIdx;
361 120973 : if (SrcSubReg && DefSubReg) {
362 0 : return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg,
363 0 : SrcIdx, DefIdx) != nullptr;
364 : }
365 :
366 : // At most one of the register is a sub register, make it Src to avoid
367 : // duplicating the test.
368 120973 : if (!SrcSubReg) {
369 : std::swap(DefSubReg, SrcSubReg);
370 : std::swap(DefRC, SrcRC);
371 : }
372 :
373 : // One of the register is a sub register, check if we can get a superclass.
374 120973 : if (SrcSubReg)
375 93877 : return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr;
376 :
377 : // Plain copy.
378 27096 : return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr;
379 : }
380 :
381 162156 : bool TargetRegisterInfo::shouldRewriteCopySrc(const TargetRegisterClass *DefRC,
382 : unsigned DefSubReg,
383 : const TargetRegisterClass *SrcRC,
384 : unsigned SrcSubReg) const {
385 : // If this source does not incur a cross register bank copy, use it.
386 162156 : return shareSameRegisterFile(*this, DefRC, DefSubReg, SrcRC, SrcSubReg);
387 : }
388 :
389 : // Compute target-independent register allocator hints to help eliminate copies.
390 : bool
391 1698182 : TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg,
392 : ArrayRef<MCPhysReg> Order,
393 : SmallVectorImpl<MCPhysReg> &Hints,
394 : const MachineFunction &MF,
395 : const VirtRegMap *VRM,
396 : const LiveRegMatrix *Matrix) const {
397 1698182 : const MachineRegisterInfo &MRI = MF.getRegInfo();
398 : const std::pair<unsigned, SmallVector<unsigned, 4>> &Hints_MRI =
399 : MRI.getRegAllocationHints(VirtReg);
400 :
401 : // First hint may be a target hint.
402 1698182 : bool Skip = (Hints_MRI.first != 0);
403 2627159 : for (auto Reg : Hints_MRI.second) {
404 928977 : if (Skip) {
405 : Skip = false;
406 169760 : continue;
407 : }
408 :
409 : // Target-independent hints are either a physical or a virtual register.
410 928977 : unsigned Phys = Reg;
411 928977 : if (VRM && isVirtualRegister(Phys))
412 264573 : Phys = VRM->getPhys(Phys);
413 :
414 : // Check that Phys is a valid hint in VirtReg's register class.
415 1857954 : if (!isPhysicalRegister(Phys))
416 : continue;
417 785264 : if (MRI.isReserved(Phys))
418 : continue;
419 : // Check that Phys is in the allocation order. We shouldn't heed hints
420 : // from VirtReg's register class if they aren't in the allocation order. The
421 : // target probably has a reason for removing the register.
422 785264 : if (!is_contained(Order, Phys))
423 : continue;
424 :
425 : // All clear, tell the register allocator to prefer this register.
426 759217 : Hints.push_back(Phys);
427 : }
428 1698182 : return false;
429 : }
430 :
431 157074 : bool TargetRegisterInfo::canRealignStack(const MachineFunction &MF) const {
432 157074 : return !MF.getFunction().hasFnAttribute("no-realign-stack");
433 : }
434 :
435 74770351 : bool TargetRegisterInfo::needsStackRealignment(
436 : const MachineFunction &MF) const {
437 74770351 : const MachineFrameInfo &MFI = MF.getFrameInfo();
438 74770351 : const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
439 74770351 : const Function &F = MF.getFunction();
440 74770351 : unsigned StackAlign = TFI->getStackAlignment();
441 149398062 : bool requiresRealignment = ((MFI.getMaxAlignment() > StackAlign) ||
442 : F.hasFnAttribute(Attribute::StackAlignment));
443 74770350 : if (F.hasFnAttribute("stackrealign") || requiresRealignment) {
444 145995 : if (canRealignStack(MF))
445 117475 : return true;
446 : LLVM_DEBUG(dbgs() << "Can't realign function's stack: " << F.getName()
447 : << "\n");
448 : }
449 : return false;
450 : }
451 :
452 362 : bool TargetRegisterInfo::regmaskSubsetEqual(const uint32_t *mask0,
453 : const uint32_t *mask1) const {
454 362 : unsigned N = (getNumRegs()+31) / 32;
455 3682 : for (unsigned I = 0; I < N; ++I)
456 3345 : if ((mask0[I] & mask1[I]) != mask0[I])
457 : return false;
458 : return true;
459 : }
460 :
461 44439 : unsigned TargetRegisterInfo::getRegSizeInBits(unsigned Reg,
462 : const MachineRegisterInfo &MRI) const {
463 : const TargetRegisterClass *RC{};
464 44439 : if (isPhysicalRegister(Reg)) {
465 : // The size is not directly available for physical registers.
466 : // Instead, we need to access a register class that contains Reg and
467 : // get the size of that register class.
468 21793 : RC = getMinimalPhysRegClass(Reg);
469 : } else {
470 22646 : LLT Ty = MRI.getType(Reg);
471 22646 : unsigned RegSize = Ty.isValid() ? Ty.getSizeInBits() : 0;
472 : // If Reg is not a generic register, query the register class to
473 : // get its size.
474 22619 : if (RegSize)
475 22619 : return RegSize;
476 : // Since Reg is not a generic register, it must have a register class.
477 : RC = MRI.getRegClass(Reg);
478 : }
479 : assert(RC && "Unable to deduce the register class");
480 21820 : return getRegSizeInBits(*RC);
481 : }
482 :
483 : unsigned
484 128232 : TargetRegisterInfo::lookThruCopyLike(unsigned SrcReg,
485 : const MachineRegisterInfo *MRI) const {
486 : while (true) {
487 137723 : const MachineInstr *MI = MRI->getVRegDef(SrcReg);
488 : if (!MI->isCopyLike())
489 94067 : return SrcReg;
490 :
491 : unsigned CopySrcReg;
492 43656 : if (MI->isCopy())
493 41831 : CopySrcReg = MI->getOperand(1).getReg();
494 : else {
495 : assert(MI->isSubregToReg() && "Bad opcode for lookThruCopyLike");
496 1825 : CopySrcReg = MI->getOperand(2).getReg();
497 : }
498 :
499 43656 : if (!isVirtualRegister(CopySrcReg))
500 34165 : return CopySrcReg;
501 :
502 : SrcReg = CopySrcReg;
503 : }
504 : }
505 :
506 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
507 : LLVM_DUMP_METHOD
508 : void TargetRegisterInfo::dumpReg(unsigned Reg, unsigned SubRegIndex,
509 : const TargetRegisterInfo *TRI) {
510 : dbgs() << printReg(Reg, TRI, SubRegIndex) << "\n";
511 : }
512 : #endif
|