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/ADT/BitVector.h"
15 #include "llvm/CodeGen/MachineFrameInfo.h"
16 #include "llvm/CodeGen/MachineFunction.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/VirtRegMap.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/Format.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/Target/TargetFrameLowering.h"
24 #include "llvm/Target/TargetRegisterInfo.h"
25 
26 #define DEBUG_TYPE "target-reg-info"
27 
28 using namespace llvm;
29 
30 TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
31                              regclass_iterator RCB, regclass_iterator RCE,
32                              const char *const *SRINames,
33                              const LaneBitmask *SRILaneMasks,
34                              LaneBitmask SRICoveringLanes)
35   : InfoDesc(ID), SubRegIndexNames(SRINames),
36     SubRegIndexLaneMasks(SRILaneMasks),
37     RegClassBegin(RCB), RegClassEnd(RCE),
38     CoveringLanes(SRICoveringLanes) {
39 }
40 
41 TargetRegisterInfo::~TargetRegisterInfo() {}
42 
43 void TargetRegisterInfo::markSuperRegs(BitVector &RegisterSet, unsigned Reg)
44     const {
45   for (MCSuperRegIterator AI(Reg, this, true); AI.isValid(); ++AI)
46     RegisterSet.set(*AI);
47 }
48 
49 bool TargetRegisterInfo::checkAllSuperRegsMarked(const BitVector &RegisterSet,
50     ArrayRef<MCPhysReg> Exceptions) const {
51   // Check that all super registers of reserved regs are reserved as well.
52   BitVector Checked(getNumRegs());
53   for (unsigned Reg : RegisterSet.set_bits()) {
54     if (Checked[Reg])
55       continue;
56     for (MCSuperRegIterator SR(Reg, this); SR.isValid(); ++SR) {
57       if (!RegisterSet[*SR] && !is_contained(Exceptions, Reg)) {
58         dbgs() << "Error: Super register " << PrintReg(*SR, this)
59                << " of reserved register " << PrintReg(Reg, this)
60                << " is not reserved.\n";
61         return false;
62       }
63 
64       // We transitively check superregs. So we can remember this for later
65       // to avoid compiletime explosion in deep register hierarchies.
66       Checked.set(*SR);
67     }
68   }
69   return true;
70 }
71 
72 namespace llvm {
73 
74 Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI,
75                    unsigned SubIdx) {
76   return Printable([Reg, TRI, SubIdx](raw_ostream &OS) {
77     if (!Reg)
78       OS << "%noreg";
79     else if (TargetRegisterInfo::isStackSlot(Reg))
80       OS << "SS#" << TargetRegisterInfo::stackSlot2Index(Reg);
81     else if (TargetRegisterInfo::isVirtualRegister(Reg))
82       OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Reg);
83     else if (TRI && Reg < TRI->getNumRegs())
84       OS << '%' << TRI->getName(Reg);
85     else
86       OS << "%physreg" << Reg;
87     if (SubIdx) {
88       if (TRI)
89         OS << ':' << TRI->getSubRegIndexName(SubIdx);
90       else
91         OS << ":sub(" << SubIdx << ')';
92     }
93   });
94 }
95 
96 Printable PrintRegUnit(unsigned Unit, const TargetRegisterInfo *TRI) {
97   return Printable([Unit, TRI](raw_ostream &OS) {
98     // Generic printout when TRI is missing.
99     if (!TRI) {
100       OS << "Unit~" << Unit;
101       return;
102     }
103 
104     // Check for invalid register units.
105     if (Unit >= TRI->getNumRegUnits()) {
106       OS << "BadUnit~" << Unit;
107       return;
108     }
109 
110     // Normal units have at least one root.
111     MCRegUnitRootIterator Roots(Unit, TRI);
112     assert(Roots.isValid() && "Unit has no roots.");
113     OS << TRI->getName(*Roots);
114     for (++Roots; Roots.isValid(); ++Roots)
115       OS << '~' << TRI->getName(*Roots);
116   });
117 }
118 
119 Printable PrintVRegOrUnit(unsigned Unit, const TargetRegisterInfo *TRI) {
120   return Printable([Unit, TRI](raw_ostream &OS) {
121     if (TRI && TRI->isVirtualRegister(Unit)) {
122       OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Unit);
123     } else {
124       OS << PrintRegUnit(Unit, TRI);
125     }
126   });
127 }
128 
129 } // End of llvm namespace
130 
131 /// getAllocatableClass - Return the maximal subclass of the given register
132 /// class that is alloctable, or NULL.
133 const TargetRegisterClass *
134 TargetRegisterInfo::getAllocatableClass(const TargetRegisterClass *RC) const {
135   if (!RC || RC->isAllocatable())
136     return RC;
137 
138   for (BitMaskClassIterator It(RC->getSubClassMask(), *this); It.isValid();
139        ++It) {
140     const TargetRegisterClass *SubRC = getRegClass(It.getID());
141     if (SubRC->isAllocatable())
142       return SubRC;
143   }
144   return nullptr;
145 }
146 
147 /// getMinimalPhysRegClass - Returns the Register Class of a physical
148 /// register of the given type, picking the most sub register class of
149 /// the right type that contains this physreg.
150 const TargetRegisterClass *
151 TargetRegisterInfo::getMinimalPhysRegClass(unsigned reg, MVT VT) const {
152   assert(isPhysicalRegister(reg) && "reg must be a physical register");
153 
154   // Pick the most sub register class of the right type that contains
155   // this physreg.
156   const TargetRegisterClass* BestRC = nullptr;
157   for (const TargetRegisterClass* RC : regclasses()) {
158     if ((VT == MVT::Other || isTypeLegalForClass(*RC, VT)) &&
159         RC->contains(reg) && (!BestRC || BestRC->hasSubClass(RC)))
160       BestRC = RC;
161   }
162 
163   assert(BestRC && "Couldn't find the register class");
164   return BestRC;
165 }
166 
167 /// getAllocatableSetForRC - Toggle the bits that represent allocatable
168 /// registers for the specific register class.
169 static void getAllocatableSetForRC(const MachineFunction &MF,
170                                    const TargetRegisterClass *RC, BitVector &R){
171   assert(RC->isAllocatable() && "invalid for nonallocatable sets");
172   ArrayRef<MCPhysReg> Order = RC->getRawAllocationOrder(MF);
173   for (unsigned i = 0; i != Order.size(); ++i)
174     R.set(Order[i]);
175 }
176 
177 BitVector TargetRegisterInfo::getAllocatableSet(const MachineFunction &MF,
178                                           const TargetRegisterClass *RC) const {
179   BitVector Allocatable(getNumRegs());
180   if (RC) {
181     // A register class with no allocatable subclass returns an empty set.
182     const TargetRegisterClass *SubClass = getAllocatableClass(RC);
183     if (SubClass)
184       getAllocatableSetForRC(MF, SubClass, Allocatable);
185   } else {
186     for (const TargetRegisterClass *C : regclasses())
187       if (C->isAllocatable())
188         getAllocatableSetForRC(MF, C, Allocatable);
189   }
190 
191   // Mask out the reserved registers
192   BitVector Reserved = getReservedRegs(MF);
193   Allocatable &= Reserved.flip();
194 
195   return Allocatable;
196 }
197 
198 static inline
199 const TargetRegisterClass *firstCommonClass(const uint32_t *A,
200                                             const uint32_t *B,
201                                             const TargetRegisterInfo *TRI,
202                                             const MVT::SimpleValueType SVT =
203                                             MVT::SimpleValueType::Any) {
204   const MVT VT(SVT);
205   for (unsigned I = 0, E = TRI->getNumRegClasses(); I < E; I += 32)
206     if (unsigned Common = *A++ & *B++) {
207       const TargetRegisterClass *RC =
208           TRI->getRegClass(I + countTrailingZeros(Common));
209       if (SVT == MVT::SimpleValueType::Any || TRI->isTypeLegalForClass(*RC, VT))
210         return RC;
211     }
212   return nullptr;
213 }
214 
215 const TargetRegisterClass *
216 TargetRegisterInfo::getCommonSubClass(const TargetRegisterClass *A,
217                                       const TargetRegisterClass *B,
218                                       const MVT::SimpleValueType SVT) const {
219   // First take care of the trivial cases.
220   if (A == B)
221     return A;
222   if (!A || !B)
223     return nullptr;
224 
225   // Register classes are ordered topologically, so the largest common
226   // sub-class it the common sub-class with the smallest ID.
227   return firstCommonClass(A->getSubClassMask(), B->getSubClassMask(), this, SVT);
228 }
229 
230 const TargetRegisterClass *
231 TargetRegisterInfo::getMatchingSuperRegClass(const TargetRegisterClass *A,
232                                              const TargetRegisterClass *B,
233                                              unsigned Idx) const {
234   assert(A && B && "Missing register class");
235   assert(Idx && "Bad sub-register index");
236 
237   // Find Idx in the list of super-register indices.
238   for (SuperRegClassIterator RCI(B, this); RCI.isValid(); ++RCI)
239     if (RCI.getSubReg() == Idx)
240       // The bit mask contains all register classes that are projected into B
241       // by Idx. Find a class that is also a sub-class of A.
242       return firstCommonClass(RCI.getMask(), A->getSubClassMask(), this);
243   return nullptr;
244 }
245 
246 const TargetRegisterClass *TargetRegisterInfo::
247 getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
248                        const TargetRegisterClass *RCB, unsigned SubB,
249                        unsigned &PreA, unsigned &PreB) const {
250   assert(RCA && SubA && RCB && SubB && "Invalid arguments");
251 
252   // Search all pairs of sub-register indices that project into RCA and RCB
253   // respectively. This is quadratic, but usually the sets are very small. On
254   // most targets like X86, there will only be a single sub-register index
255   // (e.g., sub_16bit projecting into GR16).
256   //
257   // The worst case is a register class like DPR on ARM.
258   // We have indices dsub_0..dsub_7 projecting into that class.
259   //
260   // It is very common that one register class is a sub-register of the other.
261   // Arrange for RCA to be the larger register so the answer will be found in
262   // the first iteration. This makes the search linear for the most common
263   // case.
264   const TargetRegisterClass *BestRC = nullptr;
265   unsigned *BestPreA = &PreA;
266   unsigned *BestPreB = &PreB;
267   if (getRegSizeInBits(*RCA) < getRegSizeInBits(*RCB)) {
268     std::swap(RCA, RCB);
269     std::swap(SubA, SubB);
270     std::swap(BestPreA, BestPreB);
271   }
272 
273   // Also terminate the search one we have found a register class as small as
274   // RCA.
275   unsigned MinSize = getRegSizeInBits(*RCA);
276 
277   for (SuperRegClassIterator IA(RCA, this, true); IA.isValid(); ++IA) {
278     unsigned FinalA = composeSubRegIndices(IA.getSubReg(), SubA);
279     for (SuperRegClassIterator IB(RCB, this, true); IB.isValid(); ++IB) {
280       // Check if a common super-register class exists for this index pair.
281       const TargetRegisterClass *RC =
282         firstCommonClass(IA.getMask(), IB.getMask(), this);
283       if (!RC || getRegSizeInBits(*RC) < MinSize)
284         continue;
285 
286       // The indexes must compose identically: PreA+SubA == PreB+SubB.
287       unsigned FinalB = composeSubRegIndices(IB.getSubReg(), SubB);
288       if (FinalA != FinalB)
289         continue;
290 
291       // Is RC a better candidate than BestRC?
292       if (BestRC && getRegSizeInBits(*RC) >= getRegSizeInBits(*BestRC))
293         continue;
294 
295       // Yes, RC is the smallest super-register seen so far.
296       BestRC = RC;
297       *BestPreA = IA.getSubReg();
298       *BestPreB = IB.getSubReg();
299 
300       // Bail early if we reached MinSize. We won't find a better candidate.
301       if (getRegSizeInBits(*BestRC) == MinSize)
302         return BestRC;
303     }
304   }
305   return BestRC;
306 }
307 
308 /// \brief Check if the registers defined by the pair (RegisterClass, SubReg)
309 /// share the same register file.
310 static bool shareSameRegisterFile(const TargetRegisterInfo &TRI,
311                                   const TargetRegisterClass *DefRC,
312                                   unsigned DefSubReg,
313                                   const TargetRegisterClass *SrcRC,
314                                   unsigned SrcSubReg) {
315   // Same register class.
316   if (DefRC == SrcRC)
317     return true;
318 
319   // Both operands are sub registers. Check if they share a register class.
320   unsigned SrcIdx, DefIdx;
321   if (SrcSubReg && DefSubReg) {
322     return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg,
323                                       SrcIdx, DefIdx) != nullptr;
324   }
325 
326   // At most one of the register is a sub register, make it Src to avoid
327   // duplicating the test.
328   if (!SrcSubReg) {
329     std::swap(DefSubReg, SrcSubReg);
330     std::swap(DefRC, SrcRC);
331   }
332 
333   // One of the register is a sub register, check if we can get a superclass.
334   if (SrcSubReg)
335     return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr;
336 
337   // Plain copy.
338   return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr;
339 }
340 
341 bool TargetRegisterInfo::shouldRewriteCopySrc(const TargetRegisterClass *DefRC,
342                                               unsigned DefSubReg,
343                                               const TargetRegisterClass *SrcRC,
344                                               unsigned SrcSubReg) const {
345   // If this source does not incur a cross register bank copy, use it.
346   return shareSameRegisterFile(*this, DefRC, DefSubReg, SrcRC, SrcSubReg);
347 }
348 
349 // Compute target-independent register allocator hints to help eliminate copies.
350 void
351 TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg,
352                                           ArrayRef<MCPhysReg> Order,
353                                           SmallVectorImpl<MCPhysReg> &Hints,
354                                           const MachineFunction &MF,
355                                           const VirtRegMap *VRM,
356                                           const LiveRegMatrix *Matrix) const {
357   const MachineRegisterInfo &MRI = MF.getRegInfo();
358   std::pair<unsigned, unsigned> Hint = MRI.getRegAllocationHint(VirtReg);
359 
360   // Hints with HintType != 0 were set by target-dependent code.
361   // Such targets must provide their own implementation of
362   // TRI::getRegAllocationHints to interpret those hint types.
363   assert(Hint.first == 0 && "Target must implement TRI::getRegAllocationHints");
364 
365   // Target-independent hints are either a physical or a virtual register.
366   unsigned Phys = Hint.second;
367   if (VRM && isVirtualRegister(Phys))
368     Phys = VRM->getPhys(Phys);
369 
370   // Check that Phys is a valid hint in VirtReg's register class.
371   if (!isPhysicalRegister(Phys))
372     return;
373   if (MRI.isReserved(Phys))
374     return;
375   // Check that Phys is in the allocation order. We shouldn't heed hints
376   // from VirtReg's register class if they aren't in the allocation order. The
377   // target probably has a reason for removing the register.
378   if (!is_contained(Order, Phys))
379     return;
380 
381   // All clear, tell the register allocator to prefer this register.
382   Hints.push_back(Phys);
383 }
384 
385 bool TargetRegisterInfo::canRealignStack(const MachineFunction &MF) const {
386   return !MF.getFunction()->hasFnAttribute("no-realign-stack");
387 }
388 
389 bool TargetRegisterInfo::needsStackRealignment(
390     const MachineFunction &MF) const {
391   const MachineFrameInfo &MFI = MF.getFrameInfo();
392   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
393   const Function *F = MF.getFunction();
394   unsigned StackAlign = TFI->getStackAlignment();
395   bool requiresRealignment = ((MFI.getMaxAlignment() > StackAlign) ||
396                               F->hasFnAttribute(Attribute::StackAlignment));
397   if (MF.getFunction()->hasFnAttribute("stackrealign") || requiresRealignment) {
398     if (canRealignStack(MF))
399       return true;
400     DEBUG(dbgs() << "Can't realign function's stack: " << F->getName() << "\n");
401   }
402   return false;
403 }
404 
405 bool TargetRegisterInfo::regmaskSubsetEqual(const uint32_t *mask0,
406                                             const uint32_t *mask1) const {
407   unsigned N = (getNumRegs()+31) / 32;
408   for (unsigned I = 0; I < N; ++I)
409     if ((mask0[I] & mask1[I]) != mask0[I])
410       return false;
411   return true;
412 }
413 
414 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
415 LLVM_DUMP_METHOD
416 void TargetRegisterInfo::dumpReg(unsigned Reg, unsigned SubRegIndex,
417                                  const TargetRegisterInfo *TRI) {
418   dbgs() << PrintReg(Reg, TRI, SubRegIndex) << "\n";
419 }
420 #endif
421