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