Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/CodeGen/GlobalISel/RegisterBankInfo.cpp --------------*- C++ -*-==//
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
/// \file
9
/// This file implements the RegisterBankInfo class.
10
//===----------------------------------------------------------------------===//
11
12
#include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
13
#include "llvm/ADT/SmallString.h"
14
#include "llvm/ADT/SmallVector.h"
15
#include "llvm/ADT/Statistic.h"
16
#include "llvm/ADT/iterator_range.h"
17
#include "llvm/CodeGen/GlobalISel/RegisterBank.h"
18
#include "llvm/CodeGen/MachineBasicBlock.h"
19
#include "llvm/CodeGen/MachineFunction.h"
20
#include "llvm/CodeGen/MachineRegisterInfo.h"
21
#include "llvm/CodeGen/TargetOpcodes.h"
22
#include "llvm/CodeGen/TargetRegisterInfo.h"
23
#include "llvm/CodeGen/TargetSubtargetInfo.h"
24
#include "llvm/Config/llvm-config.h"
25
#include "llvm/IR/Type.h"
26
#include "llvm/Support/Debug.h"
27
#include "llvm/Support/raw_ostream.h"
28
29
#include <algorithm> // For std::max.
30
31
#define DEBUG_TYPE "registerbankinfo"
32
33
using namespace llvm;
34
35
STATISTIC(NumPartialMappingsCreated,
36
          "Number of partial mappings dynamically created");
37
STATISTIC(NumPartialMappingsAccessed,
38
          "Number of partial mappings dynamically accessed");
39
STATISTIC(NumValueMappingsCreated,
40
          "Number of value mappings dynamically created");
41
STATISTIC(NumValueMappingsAccessed,
42
          "Number of value mappings dynamically accessed");
43
STATISTIC(NumOperandsMappingsCreated,
44
          "Number of operands mappings dynamically created");
45
STATISTIC(NumOperandsMappingsAccessed,
46
          "Number of operands mappings dynamically accessed");
47
STATISTIC(NumInstructionMappingsCreated,
48
          "Number of instruction mappings dynamically created");
49
STATISTIC(NumInstructionMappingsAccessed,
50
          "Number of instruction mappings dynamically accessed");
51
52
const unsigned RegisterBankInfo::DefaultMappingID = UINT_MAX;
53
const unsigned RegisterBankInfo::InvalidMappingID = UINT_MAX - 1;
54
55
//------------------------------------------------------------------------------
56
// RegisterBankInfo implementation.
57
//------------------------------------------------------------------------------
58
RegisterBankInfo::RegisterBankInfo(RegisterBank **RegBanks,
59
                                   unsigned NumRegBanks)
60
46.8k
    : RegBanks(RegBanks), NumRegBanks(NumRegBanks) {
61
#ifndef NDEBUG
62
  for (unsigned Idx = 0, End = getNumRegBanks(); Idx != End; ++Idx) {
63
    assert(RegBanks[Idx] != nullptr && "Invalid RegisterBank");
64
    assert(RegBanks[Idx]->isValid() && "RegisterBank should be valid");
65
  }
66
#endif // NDEBUG
67
}
68
69
0
bool RegisterBankInfo::verify(const TargetRegisterInfo &TRI) const {
70
#ifndef NDEBUG
71
  for (unsigned Idx = 0, End = getNumRegBanks(); Idx != End; ++Idx) {
72
    const RegisterBank &RegBank = getRegBank(Idx);
73
    assert(Idx == RegBank.getID() &&
74
           "ID does not match the index in the array");
75
    LLVM_DEBUG(dbgs() << "Verify " << RegBank << '\n');
76
    assert(RegBank.verify(TRI) && "RegBank is invalid");
77
  }
78
#endif // NDEBUG
79
  return true;
80
0
}
81
82
const RegisterBank *
83
RegisterBankInfo::getRegBank(Register Reg, const MachineRegisterInfo &MRI,
84
65.8M
                             const TargetRegisterInfo &TRI) const {
85
65.8M
  if (TargetRegisterInfo::isPhysicalRegister(Reg))
86
14.2M
    return &getRegBankFromRegClass(getMinimalPhysRegClass(Reg, TRI));
87
51.6M
88
51.6M
  assert(Reg && "NoRegister does not have a register bank");
89
51.6M
  const RegClassOrRegBank &RegClassOrBank = MRI.getRegClassOrRegBank(Reg);
90
51.6M
  if (auto *RB = RegClassOrBank.dyn_cast<const RegisterBank *>())
91
30.1M
    return RB;
92
21.4M
  if (auto *RC = RegClassOrBank.dyn_cast<const TargetRegisterClass *>())
93
8.12M
    return &getRegBankFromRegClass(*RC);
94
13.3M
  return nullptr;
95
13.3M
}
96
97
const TargetRegisterClass &
98
RegisterBankInfo::getMinimalPhysRegClass(Register Reg,
99
20.6M
                                         const TargetRegisterInfo &TRI) const {
100
20.6M
  assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
101
20.6M
         "Reg must be a physreg");
102
20.6M
  const auto &RegRCIt = PhysRegMinimalRCs.find(Reg);
103
20.6M
  if (RegRCIt != PhysRegMinimalRCs.end())
104
20.5M
    return *RegRCIt->second;
105
77.7k
  const TargetRegisterClass *PhysRC = TRI.getMinimalPhysRegClass(Reg);
106
77.7k
  PhysRegMinimalRCs[Reg] = PhysRC;
107
77.7k
  return *PhysRC;
108
77.7k
}
109
110
const RegisterBank *RegisterBankInfo::getRegBankFromConstraints(
111
    const MachineInstr &MI, unsigned OpIdx, const TargetInstrInfo &TII,
112
629k
    const TargetRegisterInfo &TRI) const {
113
629k
  // The mapping of the registers may be available via the
114
629k
  // register class constraints.
115
629k
  const TargetRegisterClass *RC = MI.getRegClassConstraint(OpIdx, &TII, &TRI);
116
629k
117
629k
  if (!RC)
118
626k
    return nullptr;
119
3.49k
120
3.49k
  const RegisterBank &RegBank = getRegBankFromRegClass(*RC);
121
3.49k
  // Sanity check that the target properly implemented getRegBankFromRegClass.
122
3.49k
  assert(RegBank.covers(*RC) &&
123
3.49k
         "The mapping of the register bank does not make sense");
124
3.49k
  return &RegBank;
125
3.49k
}
126
127
const TargetRegisterClass *RegisterBankInfo::constrainGenericRegister(
128
12.5M
    Register Reg, const TargetRegisterClass &RC, MachineRegisterInfo &MRI) {
129
12.5M
130
12.5M
  // If the register already has a class, fallback to MRI::constrainRegClass.
131
12.5M
  auto &RegClassOrBank = MRI.getRegClassOrRegBank(Reg);
132
12.5M
  if (RegClassOrBank.is<const TargetRegisterClass *>())
133
6.46M
    return MRI.constrainRegClass(Reg, &RC);
134
6.07M
135
6.07M
  const RegisterBank *RB = RegClassOrBank.get<const RegisterBank *>();
136
6.07M
  // Otherwise, all we can do is ensure the bank covers the class, and set it.
137
6.07M
  if (RB && 
!RB->covers(RC)6.00M
)
138
24
    return nullptr;
139
6.07M
140
6.07M
  // If nothing was set or the class is simply compatible, set it.
141
6.07M
  MRI.setRegClass(Reg, &RC);
142
6.07M
  return &RC;
143
6.07M
}
144
145
/// Check whether or not \p MI should be treated like a copy
146
/// for the mappings.
147
/// Copy like instruction are special for mapping because
148
/// they don't have actual register constraints. Moreover,
149
/// they sometimes have register classes assigned and we can
150
/// just use that instead of failing to provide a generic mapping.
151
551k
static bool isCopyLike(const MachineInstr &MI) {
152
551k
  return MI.isCopy() || 
MI.isPHI()543k
||
153
551k
         
MI.getOpcode() == TargetOpcode::REG_SEQUENCE68.2k
;
154
551k
}
155
156
const RegisterBankInfo::InstructionMapping &
157
551k
RegisterBankInfo::getInstrMappingImpl(const MachineInstr &MI) const {
158
551k
  // For copies we want to walk over the operands and try to find one
159
551k
  // that has a register bank since the instruction itself will not get
160
551k
  // us any constraint.
161
551k
  bool IsCopyLike = isCopyLike(MI);
162
551k
  // For copy like instruction, only the mapping of the definition
163
551k
  // is important. The rest is not constrained.
164
551k
  unsigned NumOperandsForMapping = IsCopyLike ? 
1483k
:
MI.getNumOperands()68.2k
;
165
551k
166
551k
  const MachineFunction &MF = *MI.getMF();
167
551k
  const TargetSubtargetInfo &STI = MF.getSubtarget();
168
551k
  const TargetRegisterInfo &TRI = *STI.getRegisterInfo();
169
551k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
170
551k
  // We may need to query the instruction encoding to guess the mapping.
171
551k
  const TargetInstrInfo &TII = *STI.getInstrInfo();
172
551k
173
551k
  // Before doing anything complicated check if the mapping is not
174
551k
  // directly available.
175
551k
  bool CompleteMapping = true;
176
551k
177
551k
  SmallVector<const ValueMapping *, 8> OperandsMapping(NumOperandsForMapping);
178
1.37M
  for (unsigned OpIdx = 0, EndIdx = MI.getNumOperands(); OpIdx != EndIdx;
179
1.31M
       
++OpIdx825k
) {
180
1.31M
    const MachineOperand &MO = MI.getOperand(OpIdx);
181
1.31M
    if (!MO.isReg())
182
200k
      continue;
183
1.11M
    Register Reg = MO.getReg();
184
1.11M
    if (!Reg)
185
3
      continue;
186
1.11M
    // The register bank of Reg is just a side effect of the current
187
1.11M
    // excution and in particular, there is no reason to believe this
188
1.11M
    // is the best default mapping for the current instruction.  Keep
189
1.11M
    // it as an alternative register bank if we cannot figure out
190
1.11M
    // something.
191
1.11M
    const RegisterBank *AltRegBank = getRegBank(Reg, MRI, TRI);
192
1.11M
    // For copy-like instruction, we want to reuse the register bank
193
1.11M
    // that is already set on Reg, if any, since those instructions do
194
1.11M
    // not have any constraints.
195
1.11M
    const RegisterBank *CurRegBank = IsCopyLike ? 
AltRegBank1.10M
:
nullptr7.89k
;
196
1.11M
    if (!CurRegBank) {
197
629k
      // If this is a target specific instruction, we can deduce
198
629k
      // the register bank from the encoding constraints.
199
629k
      CurRegBank = getRegBankFromConstraints(MI, OpIdx, TII, TRI);
200
629k
      if (!CurRegBank) {
201
626k
        // All our attempts failed, give up.
202
626k
        CompleteMapping = false;
203
626k
204
626k
        if (!IsCopyLike)
205
4.40k
          // MI does not carry enough information to guess the mapping.
206
4.40k
          return getInvalidInstructionMapping();
207
621k
        continue;
208
621k
      }
209
629k
    }
210
486k
211
486k
    unsigned Size = getSizeInBits(Reg, MRI, TRI);
212
486k
    const ValueMapping *ValMapping = &getValueMapping(0, Size, *CurRegBank);
213
486k
    if (IsCopyLike) {
214
483k
      if (!OperandsMapping[0]) {
215
483k
        if (MI.isRegSequence()) {
216
1
          // For reg_sequence, the result size does not match the input.
217
1
          unsigned ResultSize = getSizeInBits(MI.getOperand(0).getReg(),
218
1
                                              MRI, TRI);
219
1
          OperandsMapping[0] = &getValueMapping(0, ResultSize, *CurRegBank);
220
483k
        } else {
221
483k
          OperandsMapping[0] = ValMapping;
222
483k
        }
223
483k
      }
224
483k
225
483k
      // The default handling assumes any register bank can be copied to any
226
483k
      // other. If this isn't the case, the target should specially deal with
227
483k
      // reg_sequence/phi. There may also be unsatisfiable copies.
228
2.50M
      for (; OpIdx != EndIdx; 
++OpIdx2.02M
) {
229
2.02M
        const MachineOperand &MO = MI.getOperand(OpIdx);
230
2.02M
        if (!MO.isReg())
231
1.00M
          continue;
232
1.01M
        Register Reg = MO.getReg();
233
1.01M
        if (!Reg)
234
0
          continue;
235
1.01M
236
1.01M
        const RegisterBank *AltRegBank = getRegBank(Reg, MRI, TRI);
237
1.01M
        if (AltRegBank &&
238
1.01M
            
cannotCopy(*CurRegBank, *AltRegBank, getSizeInBits(Reg, MRI, TRI))905k
)
239
2
          return getInvalidInstructionMapping();
240
1.01M
      }
241
483k
242
483k
      CompleteMapping = true;
243
483k
      break;
244
3.49k
    }
245
3.49k
246
3.49k
    OperandsMapping[OpIdx] = ValMapping;
247
3.49k
  }
248
551k
249
551k
  
if (547k
IsCopyLike547k
&&
!CompleteMapping483k
) {
250
0
    // No way to deduce the type from what we have.
251
0
    return getInvalidInstructionMapping();
252
0
  }
253
547k
254
547k
  assert(CompleteMapping && "Setting an uncomplete mapping");
255
547k
  return getInstructionMapping(
256
547k
      DefaultMappingID, /*Cost*/ 1,
257
547k
      /*OperandsMapping*/ getOperandsMapping(OperandsMapping),
258
547k
      NumOperandsForMapping);
259
547k
}
260
261
/// Hashing function for PartialMapping.
262
static hash_code hashPartialMapping(unsigned StartIdx, unsigned Length,
263
974k
                                    const RegisterBank *RegBank) {
264
974k
  return hash_combine(StartIdx, Length, RegBank ? RegBank->getID() : 
00
);
265
974k
}
266
267
/// Overloaded version of hash_value for a PartialMapping.
268
hash_code
269
487k
llvm::hash_value(const RegisterBankInfo::PartialMapping &PartMapping) {
270
487k
  return hashPartialMapping(PartMapping.StartIdx, PartMapping.Length,
271
487k
                            PartMapping.RegBank);
272
487k
}
273
274
const RegisterBankInfo::PartialMapping &
275
RegisterBankInfo::getPartialMapping(unsigned StartIdx, unsigned Length,
276
487k
                                    const RegisterBank &RegBank) const {
277
487k
  ++NumPartialMappingsAccessed;
278
487k
279
487k
  hash_code Hash = hashPartialMapping(StartIdx, Length, &RegBank);
280
487k
  const auto &It = MapOfPartialMappings.find(Hash);
281
487k
  if (It != MapOfPartialMappings.end())
282
473k
    return *It->second;
283
13.1k
284
13.1k
  ++NumPartialMappingsCreated;
285
13.1k
286
13.1k
  auto &PartMapping = MapOfPartialMappings[Hash];
287
13.1k
  PartMapping = llvm::make_unique<PartialMapping>(StartIdx, Length, RegBank);
288
13.1k
  return *PartMapping;
289
13.1k
}
290
291
const RegisterBankInfo::ValueMapping &
292
RegisterBankInfo::getValueMapping(unsigned StartIdx, unsigned Length,
293
487k
                                  const RegisterBank &RegBank) const {
294
487k
  return getValueMapping(&getPartialMapping(StartIdx, Length, RegBank), 1);
295
487k
}
296
297
static hash_code
298
hashValueMapping(const RegisterBankInfo::PartialMapping *BreakDown,
299
487k
                 unsigned NumBreakDowns) {
300
487k
  if (LLVM_LIKELY(NumBreakDowns == 1))
301
487k
    return hash_value(*BreakDown);
302
0
  SmallVector<size_t, 8> Hashes(NumBreakDowns);
303
0
  for (unsigned Idx = 0; Idx != NumBreakDowns; ++Idx)
304
0
    Hashes.push_back(hash_value(BreakDown[Idx]));
305
0
  return hash_combine_range(Hashes.begin(), Hashes.end());
306
0
}
307
308
const RegisterBankInfo::ValueMapping &
309
RegisterBankInfo::getValueMapping(const PartialMapping *BreakDown,
310
487k
                                  unsigned NumBreakDowns) const {
311
487k
  ++NumValueMappingsAccessed;
312
487k
313
487k
  hash_code Hash = hashValueMapping(BreakDown, NumBreakDowns);
314
487k
  const auto &It = MapOfValueMappings.find(Hash);
315
487k
  if (It != MapOfValueMappings.end())
316
473k
    return *It->second;
317
13.1k
318
13.1k
  ++NumValueMappingsCreated;
319
13.1k
320
13.1k
  auto &ValMapping = MapOfValueMappings[Hash];
321
13.1k
  ValMapping = llvm::make_unique<ValueMapping>(BreakDown, NumBreakDowns);
322
13.1k
  return *ValMapping;
323
13.1k
}
324
325
template <typename Iterator>
326
const RegisterBankInfo::ValueMapping *
327
9.45M
RegisterBankInfo::getOperandsMapping(Iterator Begin, Iterator End) const {
328
9.45M
329
9.45M
  ++NumOperandsMappingsAccessed;
330
9.45M
331
9.45M
  // The addresses of the value mapping are unique.
332
9.45M
  // Therefore, we can use them directly to hash the operand mapping.
333
9.45M
  hash_code Hash = hash_combine_range(Begin, End);
334
9.45M
  auto &Res = MapOfOperandsMappings[Hash];
335
9.45M
  if (Res)
336
9.35M
    return Res.get();
337
101k
338
101k
  ++NumOperandsMappingsCreated;
339
101k
340
101k
  // Create the array of ValueMapping.
341
101k
  // Note: this array will not hash to this instance of operands
342
101k
  // mapping, because we use the pointer of the ValueMapping
343
101k
  // to hash and we expect them to uniquely identify an instance
344
101k
  // of value mapping.
345
101k
  Res = llvm::make_unique<ValueMapping[]>(std::distance(Begin, End));
346
101k
  unsigned Idx = 0;
347
338k
  for (Iterator It = Begin; It != End; 
++It, ++Idx237k
) {
348
237k
    const ValueMapping *ValMap = *It;
349
237k
    if (!ValMap)
350
38.7k
      continue;
351
198k
    Res[Idx] = *ValMap;
352
198k
  }
353
101k
  return Res.get();
354
101k
}
355
356
const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
357
    const SmallVectorImpl<const RegisterBankInfo::ValueMapping *> &OpdsMapping)
358
9.45M
    const {
359
9.45M
  return getOperandsMapping(OpdsMapping.begin(), OpdsMapping.end());
360
9.45M
}
361
362
const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
363
    std::initializer_list<const RegisterBankInfo::ValueMapping *> OpdsMapping)
364
3.00k
    const {
365
3.00k
  return getOperandsMapping(OpdsMapping.begin(), OpdsMapping.end());
366
3.00k
}
367
368
static hash_code
369
hashInstructionMapping(unsigned ID, unsigned Cost,
370
                       const RegisterBankInfo::ValueMapping *OperandsMapping,
371
16.2M
                       unsigned NumOperands) {
372
16.2M
  return hash_combine(ID, Cost, OperandsMapping, NumOperands);
373
16.2M
}
374
375
const RegisterBankInfo::InstructionMapping &
376
RegisterBankInfo::getInstructionMappingImpl(
377
    bool IsInvalid, unsigned ID, unsigned Cost,
378
    const RegisterBankInfo::ValueMapping *OperandsMapping,
379
16.2M
    unsigned NumOperands) const {
380
16.2M
  assert(((IsInvalid && ID == InvalidMappingID && Cost == 0 &&
381
16.2M
           OperandsMapping == nullptr && NumOperands == 0) ||
382
16.2M
          !IsInvalid) &&
383
16.2M
         "Mismatch argument for invalid input");
384
16.2M
  ++NumInstructionMappingsAccessed;
385
16.2M
386
16.2M
  hash_code Hash =
387
16.2M
      hashInstructionMapping(ID, Cost, OperandsMapping, NumOperands);
388
16.2M
  const auto &It = MapOfInstructionMappings.find(Hash);
389
16.2M
  if (It != MapOfInstructionMappings.end())
390
16.1M
    return *It->second;
391
138k
392
138k
  ++NumInstructionMappingsCreated;
393
138k
394
138k
  auto &InstrMapping = MapOfInstructionMappings[Hash];
395
138k
  InstrMapping = llvm::make_unique<InstructionMapping>(
396
138k
      ID, Cost, OperandsMapping, NumOperands);
397
138k
  return *InstrMapping;
398
138k
}
399
400
const RegisterBankInfo::InstructionMapping &
401
0
RegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
402
0
  const RegisterBankInfo::InstructionMapping &Mapping = getInstrMappingImpl(MI);
403
0
  if (Mapping.isValid())
404
0
    return Mapping;
405
0
  llvm_unreachable("The target must implement this");
406
0
}
407
408
RegisterBankInfo::InstructionMappings
409
3.40k
RegisterBankInfo::getInstrPossibleMappings(const MachineInstr &MI) const {
410
3.40k
  InstructionMappings PossibleMappings;
411
3.40k
  const auto &Mapping = getInstrMapping(MI);
412
3.40k
  if (Mapping.isValid()) {
413
3.40k
    // Put the default mapping first.
414
3.40k
    PossibleMappings.push_back(&Mapping);
415
3.40k
  }
416
3.40k
417
3.40k
  // Then the alternative mapping, if any.
418
3.40k
  InstructionMappings AltMappings = getInstrAlternativeMappings(MI);
419
3.40k
  for (const InstructionMapping *AltMapping : AltMappings)
420
1.60k
    PossibleMappings.push_back(AltMapping);
421
#ifndef NDEBUG
422
  for (const InstructionMapping *Mapping : PossibleMappings)
423
    assert(Mapping->verify(MI) && "Mapping is invalid");
424
#endif
425
  return PossibleMappings;
426
3.40k
}
427
428
RegisterBankInfo::InstructionMappings
429
2.86k
RegisterBankInfo::getInstrAlternativeMappings(const MachineInstr &MI) const {
430
2.86k
  // No alternative for MI.
431
2.86k
  return InstructionMappings();
432
2.86k
}
433
434
16.2M
void RegisterBankInfo::applyDefaultMapping(const OperandsMapper &OpdMapper) {
435
16.2M
  MachineInstr &MI = OpdMapper.getMI();
436
16.2M
  MachineRegisterInfo &MRI = OpdMapper.getMRI();
437
16.2M
  LLVM_DEBUG(dbgs() << "Applying default-like mapping\n");
438
16.2M
  for (unsigned OpIdx = 0,
439
16.2M
                EndIdx = OpdMapper.getInstrMapping().getNumOperands();
440
48.6M
       OpIdx != EndIdx; 
++OpIdx32.4M
) {
441
32.4M
    LLVM_DEBUG(dbgs() << "OpIdx " << OpIdx);
442
32.4M
    MachineOperand &MO = MI.getOperand(OpIdx);
443
32.4M
    if (!MO.isReg()) {
444
5.26M
      LLVM_DEBUG(dbgs() << " is not a register, nothing to be done\n");
445
5.26M
      continue;
446
5.26M
    }
447
27.1M
    if (!MO.getReg()) {
448
13
      LLVM_DEBUG(dbgs() << " is %%noreg, nothing to be done\n");
449
13
      continue;
450
13
    }
451
27.1M
    assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns !=
452
27.1M
               0 &&
453
27.1M
           "Invalid mapping");
454
27.1M
    assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns ==
455
27.1M
               1 &&
456
27.1M
           "This mapping is too complex for this function");
457
27.1M
    iterator_range<SmallVectorImpl<Register>::const_iterator> NewRegs =
458
27.1M
        OpdMapper.getVRegs(OpIdx);
459
27.1M
    if (empty(NewRegs)) {
460
27.1M
      LLVM_DEBUG(dbgs() << " has not been repaired, nothing to be done\n");
461
27.1M
      continue;
462
27.1M
    }
463
11.5k
    Register OrigReg = MO.getReg();
464
11.5k
    Register NewReg = *NewRegs.begin();
465
11.5k
    LLVM_DEBUG(dbgs() << " changed, replace " << printReg(OrigReg, nullptr));
466
11.5k
    MO.setReg(NewReg);
467
11.5k
    LLVM_DEBUG(dbgs() << " with " << printReg(NewReg, nullptr));
468
11.5k
469
11.5k
    // The OperandsMapper creates plain scalar, we may have to fix that.
470
11.5k
    // Check if the types match and if not, fix that.
471
11.5k
    LLT OrigTy = MRI.getType(OrigReg);
472
11.5k
    LLT NewTy = MRI.getType(NewReg);
473
11.5k
    if (OrigTy != NewTy) {
474
308
      // The default mapping is not supposed to change the size of
475
308
      // the storage. However, right now we don't necessarily bump all
476
308
      // the types to storage size. For instance, we can consider
477
308
      // s16 G_AND legal whereas the storage size is going to be 32.
478
308
      assert(OrigTy.getSizeInBits() <= NewTy.getSizeInBits() &&
479
308
             "Types with difference size cannot be handled by the default "
480
308
             "mapping");
481
308
      LLVM_DEBUG(dbgs() << "\nChange type of new opd from " << NewTy << " to "
482
308
                        << OrigTy);
483
308
      MRI.setType(NewReg, OrigTy);
484
308
    }
485
11.5k
    LLVM_DEBUG(dbgs() << '\n');
486
11.5k
  }
487
16.2M
}
488
489
unsigned RegisterBankInfo::getSizeInBits(Register Reg,
490
                                         const MachineRegisterInfo &MRI,
491
13.1M
                                         const TargetRegisterInfo &TRI) const {
492
13.1M
  if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
493
6.41M
    // The size is not directly available for physical registers.
494
6.41M
    // Instead, we need to access a register class that contains Reg and
495
6.41M
    // get the size of that register class.
496
6.41M
    // Because this is expensive, we'll cache the register class by calling
497
6.41M
    auto *RC = &getMinimalPhysRegClass(Reg, TRI);
498
6.41M
    assert(RC && "Expecting Register class");
499
6.41M
    return TRI.getRegSizeInBits(*RC);
500
6.41M
  }
501
6.75M
  return TRI.getRegSizeInBits(Reg, MRI);
502
6.75M
}
503
504
//------------------------------------------------------------------------------
505
// Helper classes implementation.
506
//------------------------------------------------------------------------------
507
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
508
LLVM_DUMP_METHOD void RegisterBankInfo::PartialMapping::dump() const {
509
  print(dbgs());
510
  dbgs() << '\n';
511
}
512
#endif
513
514
0
bool RegisterBankInfo::PartialMapping::verify() const {
515
0
  assert(RegBank && "Register bank not set");
516
0
  assert(Length && "Empty mapping");
517
0
  assert((StartIdx <= getHighBitIdx()) && "Overflow, switch to APInt?");
518
0
  // Check if the minimum width fits into RegBank.
519
0
  assert(RegBank->getSize() >= Length && "Register bank too small for Mask");
520
0
  return true;
521
0
}
522
523
0
void RegisterBankInfo::PartialMapping::print(raw_ostream &OS) const {
524
0
  OS << "[" << StartIdx << ", " << getHighBitIdx() << "], RegBank = ";
525
0
  if (RegBank)
526
0
    OS << *RegBank;
527
0
  else
528
0
    OS << "nullptr";
529
0
}
530
531
0
bool RegisterBankInfo::ValueMapping::partsAllUniform() const {
532
0
  if (NumBreakDowns < 2)
533
0
    return true;
534
0
535
0
  const PartialMapping *First = begin();
536
0
  for (const PartialMapping *Part = First + 1; Part != end(); ++Part) {
537
0
    if (Part->Length != First->Length || Part->RegBank != First->RegBank)
538
0
      return false;
539
0
  }
540
0
541
0
  return true;
542
0
}
543
544
0
bool RegisterBankInfo::ValueMapping::verify(unsigned MeaningfulBitWidth) const {
545
0
  assert(NumBreakDowns && "Value mapped nowhere?!");
546
0
  unsigned OrigValueBitWidth = 0;
547
0
  for (const RegisterBankInfo::PartialMapping &PartMap : *this) {
548
0
    // Check that each register bank is big enough to hold the partial value:
549
0
    // this check is done by PartialMapping::verify
550
0
    assert(PartMap.verify() && "Partial mapping is invalid");
551
0
    // The original value should completely be mapped.
552
0
    // Thus the maximum accessed index + 1 is the size of the original value.
553
0
    OrigValueBitWidth =
554
0
        std::max(OrigValueBitWidth, PartMap.getHighBitIdx() + 1);
555
0
  }
556
0
  assert(OrigValueBitWidth >= MeaningfulBitWidth &&
557
0
         "Meaningful bits not covered by the mapping");
558
0
  APInt ValueMask(OrigValueBitWidth, 0);
559
0
  for (const RegisterBankInfo::PartialMapping &PartMap : *this) {
560
0
    // Check that the union of the partial mappings covers the whole value,
561
0
    // without overlaps.
562
0
    // The high bit is exclusive in the APInt API, thus getHighBitIdx + 1.
563
0
    APInt PartMapMask = APInt::getBitsSet(OrigValueBitWidth, PartMap.StartIdx,
564
0
                                          PartMap.getHighBitIdx() + 1);
565
0
    ValueMask ^= PartMapMask;
566
0
    assert((ValueMask & PartMapMask) == PartMapMask &&
567
0
           "Some partial mappings overlap");
568
0
  }
569
0
  assert(ValueMask.isAllOnesValue() && "Value is not fully mapped");
570
0
  return true;
571
0
}
572
573
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
574
LLVM_DUMP_METHOD void RegisterBankInfo::ValueMapping::dump() const {
575
  print(dbgs());
576
  dbgs() << '\n';
577
}
578
#endif
579
580
0
void RegisterBankInfo::ValueMapping::print(raw_ostream &OS) const {
581
0
  OS << "#BreakDown: " << NumBreakDowns << " ";
582
0
  bool IsFirst = true;
583
0
  for (const PartialMapping &PartMap : *this) {
584
0
    if (!IsFirst)
585
0
      OS << ", ";
586
0
    OS << '[' << PartMap << ']';
587
0
    IsFirst = false;
588
0
  }
589
0
}
590
591
bool RegisterBankInfo::InstructionMapping::verify(
592
0
    const MachineInstr &MI) const {
593
0
  // Check that all the register operands are properly mapped.
594
0
  // Check the constructor invariant.
595
0
  // For PHI, we only care about mapping the definition.
596
0
  assert(NumOperands == (isCopyLike(MI) ? 1 : MI.getNumOperands()) &&
597
0
         "NumOperands must match, see constructor");
598
0
  assert(MI.getParent() && MI.getMF() &&
599
0
         "MI must be connected to a MachineFunction");
600
0
  const MachineFunction &MF = *MI.getMF();
601
0
  const RegisterBankInfo *RBI = MF.getSubtarget().getRegBankInfo();
602
0
  (void)RBI;
603
0
604
0
  for (unsigned Idx = 0; Idx < NumOperands; ++Idx) {
605
0
    const MachineOperand &MO = MI.getOperand(Idx);
606
0
    if (!MO.isReg()) {
607
0
      assert(!getOperandMapping(Idx).isValid() &&
608
0
             "We should not care about non-reg mapping");
609
0
      continue;
610
0
    }
611
0
    Register Reg = MO.getReg();
612
0
    if (!Reg)
613
0
      continue;
614
0
    assert(getOperandMapping(Idx).isValid() &&
615
0
           "We must have a mapping for reg operands");
616
0
    const RegisterBankInfo::ValueMapping &MOMapping = getOperandMapping(Idx);
617
0
    (void)MOMapping;
618
0
    // Register size in bits.
619
0
    // This size must match what the mapping expects.
620
0
    assert(MOMapping.verify(RBI->getSizeInBits(
621
0
               Reg, MF.getRegInfo(), *MF.getSubtarget().getRegisterInfo())) &&
622
0
           "Value mapping is invalid");
623
0
  }
624
0
  return true;
625
0
}
626
627
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
628
LLVM_DUMP_METHOD void RegisterBankInfo::InstructionMapping::dump() const {
629
  print(dbgs());
630
  dbgs() << '\n';
631
}
632
#endif
633
634
0
void RegisterBankInfo::InstructionMapping::print(raw_ostream &OS) const {
635
0
  OS << "ID: " << getID() << " Cost: " << getCost() << " Mapping: ";
636
0
637
0
  for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
638
0
    const ValueMapping &ValMapping = getOperandMapping(OpIdx);
639
0
    if (OpIdx)
640
0
      OS << ", ";
641
0
    OS << "{ Idx: " << OpIdx << " Map: " << ValMapping << '}';
642
0
  }
643
0
}
644
645
const int RegisterBankInfo::OperandsMapper::DontKnowIdx = -1;
646
647
RegisterBankInfo::OperandsMapper::OperandsMapper(
648
    MachineInstr &MI, const InstructionMapping &InstrMapping,
649
    MachineRegisterInfo &MRI)
650
16.2M
    : MRI(MRI), MI(MI), InstrMapping(InstrMapping) {
651
16.2M
  unsigned NumOpds = InstrMapping.getNumOperands();
652
16.2M
  OpToNewVRegIdx.resize(NumOpds, OperandsMapper::DontKnowIdx);
653
16.2M
  assert(InstrMapping.verify(MI) && "Invalid mapping for MI");
654
16.2M
}
655
656
iterator_range<SmallVectorImpl<Register>::iterator>
657
11.8k
RegisterBankInfo::OperandsMapper::getVRegsMem(unsigned OpIdx) {
658
11.8k
  assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
659
11.8k
  unsigned NumPartialVal =
660
11.8k
      getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns;
661
11.8k
  int StartIdx = OpToNewVRegIdx[OpIdx];
662
11.8k
663
11.8k
  if (StartIdx == OperandsMapper::DontKnowIdx) {
664
11.8k
    // This is the first time we try to access OpIdx.
665
11.8k
    // Create the cells that will hold all the partial values at the
666
11.8k
    // end of the list of NewVReg.
667
11.8k
    StartIdx = NewVRegs.size();
668
11.8k
    OpToNewVRegIdx[OpIdx] = StartIdx;
669
24.1k
    for (unsigned i = 0; i < NumPartialVal; 
++i12.2k
)
670
12.2k
      NewVRegs.push_back(0);
671
11.8k
  }
672
11.8k
  SmallVectorImpl<Register>::iterator End =
673
11.8k
      getNewVRegsEnd(StartIdx, NumPartialVal);
674
11.8k
675
11.8k
  return make_range(&NewVRegs[StartIdx], End);
676
11.8k
}
677
678
SmallVectorImpl<Register>::const_iterator
679
RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
680
23.7k
                                                 unsigned NumVal) const {
681
23.7k
  return const_cast<OperandsMapper *>(this)->getNewVRegsEnd(StartIdx, NumVal);
682
23.7k
}
683
SmallVectorImpl<Register>::iterator
684
RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
685
35.6k
                                                 unsigned NumVal) {
686
35.6k
  assert((NewVRegs.size() == StartIdx + NumVal ||
687
35.6k
          NewVRegs.size() > StartIdx + NumVal) &&
688
35.6k
         "NewVRegs too small to contain all the partial mapping");
689
35.6k
  return NewVRegs.size() <= StartIdx + NumVal ? 
NewVRegs.end()31.3k
690
35.6k
                                              : 
&NewVRegs[StartIdx + NumVal]4.30k
;
691
35.6k
}
692
693
11.8k
void RegisterBankInfo::OperandsMapper::createVRegs(unsigned OpIdx) {
694
11.8k
  assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
695
11.8k
  iterator_range<SmallVectorImpl<Register>::iterator> NewVRegsForOpIdx =
696
11.8k
      getVRegsMem(OpIdx);
697
11.8k
  const ValueMapping &ValMapping = getInstrMapping().getOperandMapping(OpIdx);
698
11.8k
  const PartialMapping *PartMap = ValMapping.begin();
699
12.2k
  for (Register &NewVReg : NewVRegsForOpIdx) {
700
12.2k
    assert(PartMap != ValMapping.end() && "Out-of-bound access");
701
12.2k
    assert(NewVReg == 0 && "Register has already been created");
702
12.2k
    // The new registers are always bound to scalar with the right size.
703
12.2k
    // The actual type has to be set when the target does the mapping
704
12.2k
    // of the instruction.
705
12.2k
    // The rationale is that this generic code cannot guess how the
706
12.2k
    // target plans to split the input type.
707
12.2k
    NewVReg = MRI.createGenericVirtualRegister(LLT::scalar(PartMap->Length));
708
12.2k
    MRI.setRegBank(NewVReg, *PartMap->RegBank);
709
12.2k
    ++PartMap;
710
12.2k
  }
711
11.8k
}
712
713
void RegisterBankInfo::OperandsMapper::setVRegs(unsigned OpIdx,
714
                                                unsigned PartialMapIdx,
715
0
                                                Register NewVReg) {
716
0
  assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
717
0
  assert(getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns >
718
0
             PartialMapIdx &&
719
0
         "Out-of-bound access for partial mapping");
720
0
  // Make sure the memory is initialized for that operand.
721
0
  (void)getVRegsMem(OpIdx);
722
0
  assert(NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] == 0 &&
723
0
         "This value is already set");
724
0
  NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] = NewVReg;
725
0
}
726
727
iterator_range<SmallVectorImpl<Register>::const_iterator>
728
RegisterBankInfo::OperandsMapper::getVRegs(unsigned OpIdx,
729
27.1M
                                           bool ForDebug) const {
730
27.1M
  (void)ForDebug;
731
27.1M
  assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
732
27.1M
  int StartIdx = OpToNewVRegIdx[OpIdx];
733
27.1M
734
27.1M
  if (StartIdx == OperandsMapper::DontKnowIdx)
735
27.1M
    return make_range(NewVRegs.end(), NewVRegs.end());
736
23.7k
737
23.7k
  unsigned PartMapSize =
738
23.7k
      getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns;
739
23.7k
  SmallVectorImpl<Register>::const_iterator End =
740
23.7k
      getNewVRegsEnd(StartIdx, PartMapSize);
741
23.7k
  iterator_range<SmallVectorImpl<Register>::const_iterator> Res =
742
23.7k
      make_range(&NewVRegs[StartIdx], End);
743
#ifndef NDEBUG
744
  for (Register VReg : Res)
745
    assert((VReg || ForDebug) && "Some registers are uninitialized");
746
#endif
747
  return Res;
748
23.7k
}
749
750
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
751
LLVM_DUMP_METHOD void RegisterBankInfo::OperandsMapper::dump() const {
752
  print(dbgs(), true);
753
  dbgs() << '\n';
754
}
755
#endif
756
757
void RegisterBankInfo::OperandsMapper::print(raw_ostream &OS,
758
0
                                             bool ForDebug) const {
759
0
  unsigned NumOpds = getInstrMapping().getNumOperands();
760
0
  if (ForDebug) {
761
0
    OS << "Mapping for " << getMI() << "\nwith " << getInstrMapping() << '\n';
762
0
    // Print out the internal state of the index table.
763
0
    OS << "Populated indices (CellNumber, IndexInNewVRegs): ";
764
0
    bool IsFirst = true;
765
0
    for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
766
0
      if (OpToNewVRegIdx[Idx] != DontKnowIdx) {
767
0
        if (!IsFirst)
768
0
          OS << ", ";
769
0
        OS << '(' << Idx << ", " << OpToNewVRegIdx[Idx] << ')';
770
0
        IsFirst = false;
771
0
      }
772
0
    }
773
0
    OS << '\n';
774
0
  } else
775
0
    OS << "Mapping ID: " << getInstrMapping().getID() << ' ';
776
0
777
0
  OS << "Operand Mapping: ";
778
0
  // If we have a function, we can pretty print the name of the registers.
779
0
  // Otherwise we will print the raw numbers.
780
0
  const TargetRegisterInfo *TRI =
781
0
      getMI().getParent() && getMI().getMF()
782
0
          ? getMI().getMF()->getSubtarget().getRegisterInfo()
783
0
          : nullptr;
784
0
  bool IsFirst = true;
785
0
  for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
786
0
    if (OpToNewVRegIdx[Idx] == DontKnowIdx)
787
0
      continue;
788
0
    if (!IsFirst)
789
0
      OS << ", ";
790
0
    IsFirst = false;
791
0
    OS << '(' << printReg(getMI().getOperand(Idx).getReg(), TRI) << ", [";
792
0
    bool IsFirstNewVReg = true;
793
0
    for (Register VReg : getVRegs(Idx)) {
794
0
      if (!IsFirstNewVReg)
795
0
        OS << ", ";
796
0
      IsFirstNewVReg = false;
797
0
      OS << printReg(VReg, TRI);
798
0
    }
799
0
    OS << "])";
800
0
  }
801
0
}