Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
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
// Implement an interface to specify and query how an illegal operation on a
10
// given type should be expanded.
11
//
12
// Issues to be resolved:
13
//   + Make it fast.
14
//   + Support weird types like i3, <7 x i3>, ...
15
//   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
16
//
17
//===----------------------------------------------------------------------===//
18
19
#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
20
#include "llvm/ADT/SmallBitVector.h"
21
#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
22
#include "llvm/CodeGen/MachineInstr.h"
23
#include "llvm/CodeGen/MachineOperand.h"
24
#include "llvm/CodeGen/MachineRegisterInfo.h"
25
#include "llvm/CodeGen/TargetOpcodes.h"
26
#include "llvm/MC/MCInstrDesc.h"
27
#include "llvm/MC/MCInstrInfo.h"
28
#include "llvm/Support/Debug.h"
29
#include "llvm/Support/ErrorHandling.h"
30
#include "llvm/Support/LowLevelTypeImpl.h"
31
#include "llvm/Support/MathExtras.h"
32
#include <algorithm>
33
#include <map>
34
35
using namespace llvm;
36
using namespace LegalizeActions;
37
38
#define DEBUG_TYPE "legalizer-info"
39
40
cl::opt<bool> llvm::DisableGISelLegalityCheck(
41
    "disable-gisel-legality-check",
42
    cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
43
    cl::Hidden);
44
45
0
raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
46
0
  switch (Action) {
47
0
  case Legal:
48
0
    OS << "Legal";
49
0
    break;
50
0
  case NarrowScalar:
51
0
    OS << "NarrowScalar";
52
0
    break;
53
0
  case WidenScalar:
54
0
    OS << "WidenScalar";
55
0
    break;
56
0
  case FewerElements:
57
0
    OS << "FewerElements";
58
0
    break;
59
0
  case MoreElements:
60
0
    OS << "MoreElements";
61
0
    break;
62
0
  case Lower:
63
0
    OS << "Lower";
64
0
    break;
65
0
  case Libcall:
66
0
    OS << "Libcall";
67
0
    break;
68
0
  case Custom:
69
0
    OS << "Custom";
70
0
    break;
71
0
  case Unsupported:
72
0
    OS << "Unsupported";
73
0
    break;
74
0
  case NotFound:
75
0
    OS << "NotFound";
76
0
    break;
77
0
  case UseLegacyRules:
78
0
    OS << "UseLegacyRules";
79
0
    break;
80
0
  }
81
0
  return OS;
82
0
}
83
84
0
raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
85
0
  OS << Opcode << ", Tys={";
86
0
  for (const auto &Type : Types) {
87
0
    OS << Type << ", ";
88
0
  }
89
0
  OS << "}, Opcode=";
90
0
91
0
  OS << Opcode << ", MMOs={";
92
0
  for (const auto &MMODescr : MMODescrs) {
93
0
    OS << MMODescr.SizeInBits << ", ";
94
0
  }
95
0
  OS << "}";
96
0
97
0
  return OS;
98
0
}
99
100
#ifndef NDEBUG
101
// Make sure the rule won't (trivially) loop forever.
102
static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
103
                             const std::pair<unsigned, LLT> &Mutation) {
104
  switch (Rule.getAction()) {
105
  case Custom:
106
  case Lower:
107
  case MoreElements:
108
  case FewerElements:
109
    break;
110
  default:
111
    return Q.Types[Mutation.first] != Mutation.second;
112
  }
113
  return true;
114
}
115
116
// Make sure the returned mutation makes sense for the match type.
117
static bool mutationIsSane(const LegalizeRule &Rule,
118
                           const LegalityQuery &Q,
119
                           std::pair<unsigned, LLT> Mutation) {
120
  // If the user wants a custom mutation, then we can't really say much about
121
  // it. Return true, and trust that they're doing the right thing.
122
  if (Rule.getAction() == Custom)
123
    return true;
124
125
  const unsigned TypeIdx = Mutation.first;
126
  const LLT OldTy = Q.Types[TypeIdx];
127
  const LLT NewTy = Mutation.second;
128
129
  switch (Rule.getAction()) {
130
  case FewerElements:
131
  case MoreElements: {
132
    if (!OldTy.isVector())
133
      return false;
134
135
    if (NewTy.isVector()) {
136
      if (Rule.getAction() == FewerElements) {
137
        // Make sure the element count really decreased.
138
        if (NewTy.getNumElements() >= OldTy.getNumElements())
139
          return false;
140
      } else {
141
        // Make sure the element count really increased.
142
        if (NewTy.getNumElements() <= OldTy.getNumElements())
143
          return false;
144
      }
145
    }
146
147
    // Make sure the element type didn't change.
148
    return NewTy.getScalarType() == OldTy.getElementType();
149
  }
150
  case NarrowScalar:
151
  case WidenScalar: {
152
    if (OldTy.isVector()) {
153
      // Number of elements should not change.
154
      if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
155
        return false;
156
    } else {
157
      // Both types must be vectors
158
      if (NewTy.isVector())
159
        return false;
160
    }
161
162
    if (Rule.getAction() == NarrowScalar)  {
163
      // Make sure the size really decreased.
164
      if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
165
        return false;
166
    } else {
167
      // Make sure the size really increased.
168
      if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
169
        return false;
170
    }
171
172
    return true;
173
  }
174
  default:
175
    return true;
176
  }
177
}
178
#endif
179
180
14.1M
LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
181
14.1M
  LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
182
14.1M
             dbgs() << "\n");
183
14.1M
  if (Rules.empty()) {
184
391k
    LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
185
391k
    return {LegalizeAction::UseLegacyRules, 0, LLT{}};
186
391k
  }
187
15.6M
  
for (const LegalizeRule &Rule : Rules)13.7M
{
188
15.6M
    if (Rule.match(Query)) {
189
13.7M
      LLVM_DEBUG(dbgs() << ".. match\n");
190
13.7M
      std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
191
13.7M
      LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
192
13.7M
                        << Mutation.first << ", " << Mutation.second << "\n");
193
13.7M
      assert(mutationIsSane(Rule, Query, Mutation) &&
194
13.7M
             "legality mutation invalid for match");
195
13.7M
      assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
196
13.7M
      return {Rule.getAction(), Mutation.first, Mutation.second};
197
13.7M
    } else
198
15.6M
      LLVM_DEBUG(dbgs() << ".. no match\n");
199
15.6M
  }
200
13.7M
  
LLVM_DEBUG2.87k
(dbgs() << ".. unsupported\n");
201
2.87k
  return {LegalizeAction::Unsupported, 0, LLT{}};
202
13.7M
}
203
204
0
bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
205
#ifndef NDEBUG
206
  if (Rules.empty()) {
207
    LLVM_DEBUG(
208
        dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
209
    return true;
210
  }
211
  const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
212
  if (FirstUncovered < 0) {
213
    LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
214
                         " user-defined predicate detected\n");
215
    return true;
216
  }
217
  const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
218
  LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
219
                    << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
220
  return AllCovered;
221
#else
222
  return true;
223
0
#endif
224
0
}
225
226
46.8k
LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
227
46.8k
  // Set defaults.
228
46.8k
  // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
229
46.8k
  // fundamental load/store Jakob proposed. Once loads & stores are supported.
230
46.8k
  setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
231
46.8k
  setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
232
46.8k
  setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
233
46.8k
  setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
234
46.8k
  setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
235
46.8k
236
46.8k
  setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
237
46.8k
  setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
238
46.8k
239
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
240
46.8k
      TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
241
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
242
46.8k
      TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
243
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
244
46.8k
      TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
245
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
246
46.8k
      TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
247
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
248
46.8k
      TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
249
46.8k
250
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
251
46.8k
      TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
252
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
253
46.8k
      TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
254
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
255
46.8k
      TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
256
46.8k
  setLegalizeScalarToDifferentSizeStrategy(
257
46.8k
      TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
258
46.8k
  setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
259
46.8k
}
260
261
46.8k
void LegalizerInfo::computeTables() {
262
46.8k
  assert(TablesInitialized == false);
263
46.8k
264
6.09M
  for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; 
++OpcodeIdx6.04M
) {
265
6.04M
    const unsigned Opcode = FirstOp + OpcodeIdx;
266
6.68M
    for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
267
6.04M
         
++TypeIdx637k
) {
268
637k
      // 0. Collect information specified through the setAction API, i.e.
269
637k
      // for specific bit sizes.
270
637k
      // For scalar types:
271
637k
      SizeAndActionsVec ScalarSpecifiedActions;
272
637k
      // For pointer types:
273
637k
      std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
274
637k
      // For vector types:
275
637k
      std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
276
2.50M
      for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
277
2.50M
        const LLT Type = LLT2Action.first;
278
2.50M
        const LegalizeAction Action = LLT2Action.second;
279
2.50M
280
2.50M
        auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
281
2.50M
        if (Type.isPointer())
282
175k
          AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
283
175k
              SizeAction);
284
2.33M
        else if (Type.isVector())
285
860k
          ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
286
860k
              .push_back(SizeAction);
287
1.47M
        else
288
1.47M
          ScalarSpecifiedActions.push_back(SizeAction);
289
2.50M
      }
290
637k
291
637k
      // 1. Handle scalar types
292
637k
      {
293
637k
        // Decide how to handle bit sizes for which no explicit specification
294
637k
        // was given.
295
637k
        SizeChangeStrategy S = &unsupportedForDifferentSizes;
296
637k
        if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
297
637k
            
ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr244k
)
298
229k
          S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
299
637k
        llvm::sort(ScalarSpecifiedActions);
300
637k
        checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
301
637k
        setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
302
637k
      }
303
637k
304
637k
      // 2. Handle pointer types
305
637k
      for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
306
175k
        llvm::sort(PointerSpecifiedActions.second);
307
175k
        checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
308
175k
        // For pointer types, we assume that there isn't a meaningfull way
309
175k
        // to change the number of bits used in the pointer.
310
175k
        setPointerAction(
311
175k
            Opcode, TypeIdx, PointerSpecifiedActions.first,
312
175k
            unsupportedForDifferentSizes(PointerSpecifiedActions.second));
313
175k
      }
314
637k
315
637k
      // 3. Handle vector types
316
637k
      SizeAndActionsVec ElementSizesSeen;
317
637k
      for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
318
580k
        llvm::sort(VectorSpecifiedActions.second);
319
580k
        const uint16_t ElementSize = VectorSpecifiedActions.first;
320
580k
        ElementSizesSeen.push_back({ElementSize, Legal});
321
580k
        checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
322
580k
        // For vector types, we assume that the best way to adapt the number
323
580k
        // of elements is to the next larger number of elements type for which
324
580k
        // the vector type is legal, unless there is no such type. In that case,
325
580k
        // legalize towards a vector type with a smaller number of elements.
326
580k
        SizeAndActionsVec NumElementsActions;
327
860k
        for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
328
860k
          assert(BitsizeAndAction.first % ElementSize == 0);
329
860k
          const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
330
860k
          NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
331
860k
        }
332
580k
        setVectorNumElementAction(
333
580k
            Opcode, TypeIdx, ElementSize,
334
580k
            moreToWiderTypesAndLessToWidest(NumElementsActions));
335
580k
      }
336
637k
      llvm::sort(ElementSizesSeen);
337
637k
      SizeChangeStrategy VectorElementSizeChangeStrategy =
338
637k
          &unsupportedForDifferentSizes;
339
637k
      if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
340
637k
          
VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr1
)
341
1
        VectorElementSizeChangeStrategy =
342
1
            VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
343
637k
      setScalarInVectorAction(
344
637k
          Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
345
637k
    }
346
6.04M
  }
347
46.8k
348
46.8k
  TablesInitialized = true;
349
46.8k
}
350
351
// FIXME: inefficient implementation for now. Without ComputeValueVTs we're
352
// probably going to need specialized lookup structures for various types before
353
// we have any hope of doing well with something like <13 x i3>. Even the common
354
// cases should do better than what we have now.
355
std::pair<LegalizeAction, LLT>
356
6.29k
LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
357
6.29k
  assert(TablesInitialized && "backend forgot to call computeTables");
358
6.29k
  // These *have* to be implemented for now, they're the fundamental basis of
359
6.29k
  // how everything else is transformed.
360
6.29k
  if (Aspect.Type.isScalar() || 
Aspect.Type.isPointer()1.12k
)
361
5.79k
    return findScalarLegalAction(Aspect);
362
498
  assert(Aspect.Type.isVector());
363
498
  return findVectorLegalAction(Aspect);
364
498
}
365
366
/// Helper function to get LLT for the given type index.
367
static LLT getTypeFromTypeIdx(const MachineInstr &MI,
368
                              const MachineRegisterInfo &MRI, unsigned OpIdx,
369
21.2M
                              unsigned TypeIdx) {
370
21.2M
  assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
371
21.2M
  // G_UNMERGE_VALUES has variable number of operands, but there is only
372
21.2M
  // one source type and one destination type as all destinations must be the
373
21.2M
  // same type. So, get the last operand if TypeIdx == 1.
374
21.2M
  if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 
TypeIdx == 13.01k
)
375
1.50k
    return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
376
21.2M
  return MRI.getType(MI.getOperand(OpIdx).getReg());
377
21.2M
}
378
379
17.3M
unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
380
17.3M
  assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
381
17.3M
  return Opcode - FirstOp;
382
17.3M
}
383
384
15.4M
unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
385
15.4M
  unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
386
15.4M
  if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
387
977k
    LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
388
977k
                      << "\n");
389
977k
    OpcodeIdx = getOpcodeIdxForOpcode(Alias);
390
977k
    LLVM_DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to "
391
977k
                      << RulesForOpcode[OpcodeIdx].getAlias() << "\n");
392
977k
    assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
393
977k
  }
394
15.4M
395
15.4M
  return OpcodeIdx;
396
15.4M
}
397
398
const LegalizeRuleSet &
399
14.1M
LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
400
14.1M
  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
401
14.1M
  return RulesForOpcode[OpcodeIdx];
402
14.1M
}
403
404
1.24M
LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
405
1.24M
  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
406
1.24M
  auto &Result = RulesForOpcode[OpcodeIdx];
407
1.24M
  assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
408
1.24M
  return Result;
409
1.24M
}
410
411
LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
412
392k
    std::initializer_list<unsigned> Opcodes) {
413
392k
  unsigned Representative = *Opcodes.begin();
414
392k
415
392k
  assert(!empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
416
392k
         "Initializer list must have at least two opcodes");
417
392k
418
1.36M
  for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; 
++I970k
)
419
970k
    aliasActionDefinitions(Representative, *I);
420
392k
421
392k
  auto &Return = getActionDefinitionsBuilder(Representative);
422
392k
  Return.setIsAliasedByAnother();
423
392k
  return Return;
424
392k
}
425
426
void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
427
970k
                                           unsigned OpcodeFrom) {
428
970k
  assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
429
970k
  assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
430
970k
  const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
431
970k
  RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
432
970k
}
433
434
LegalizeActionStep
435
14.1M
LegalizerInfo::getAction(const LegalityQuery &Query) const {
436
14.1M
  LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
437
14.1M
  if (Step.Action != LegalizeAction::UseLegacyRules) {
438
13.7M
    return Step;
439
13.7M
  }
440
391k
441
396k
  
for (unsigned i = 0; 391k
i < Query.Types.size();
++i4.49k
) {
442
6.29k
    auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
443
6.29k
    if (Action.first != Legal) {
444
1.80k
      LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
445
1.80k
                        << Action.first << ", " << Action.second << "\n");
446
1.80k
      return {Action.first, i, Action.second};
447
1.80k
    } else
448
6.29k
      LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
449
6.29k
  }
450
391k
  
LLVM_DEBUG390k
(dbgs() << ".. (legacy) Legal\n");
451
390k
  return {Legal, 0, LLT{}};
452
391k
}
453
454
LegalizeActionStep
455
LegalizerInfo::getAction(const MachineInstr &MI,
456
13.8M
                         const MachineRegisterInfo &MRI) const {
457
13.8M
  SmallVector<LLT, 2> Types;
458
13.8M
  SmallBitVector SeenTypes(8);
459
13.8M
  const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
460
13.8M
  // FIXME: probably we'll need to cache the results here somehow?
461
47.9M
  for (unsigned i = 0; i < MI.getDesc().getNumOperands(); 
++i34.1M
) {
462
34.1M
    if (!OpInfo[i].isGenericType())
463
6.53M
      continue;
464
27.6M
465
27.6M
    // We must only record actions once for each TypeIdx; otherwise we'd
466
27.6M
    // try to legalize operands multiple times down the line.
467
27.6M
    unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
468
27.6M
    if (SeenTypes[TypeIdx])
469
6.31M
      continue;
470
21.2M
471
21.2M
    SeenTypes.set(TypeIdx);
472
21.2M
473
21.2M
    LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
474
21.2M
    Types.push_back(Ty);
475
21.2M
  }
476
13.8M
477
13.8M
  SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
478
13.8M
  for (const auto &MMO : MI.memoperands())
479
2.05M
    MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
480
2.05M
                         8 * MMO->getAlignment(),
481
2.05M
                         MMO->getOrdering()});
482
13.8M
483
13.8M
  return getAction({MI.getOpcode(), Types, MemDescrs});
484
13.8M
}
485
486
bool LegalizerInfo::isLegal(const MachineInstr &MI,
487
0
                            const MachineRegisterInfo &MRI) const {
488
0
  return getAction(MI, MRI).Action == Legal;
489
0
}
490
491
bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
492
0
                                    const MachineRegisterInfo &MRI) const {
493
0
  auto Action = getAction(MI, MRI).Action;
494
0
  // If the action is custom, it may not necessarily modify the instruction,
495
0
  // so we have to assume it's legal.
496
0
  return Action == Legal || Action == Custom;
497
0
}
498
499
bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
500
                                   MachineIRBuilder &MIRBuilder,
501
0
                                   GISelChangeObserver &Observer) const {
502
0
  return false;
503
0
}
504
505
LegalizerInfo::SizeAndActionsVec
506
LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
507
    const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
508
1.86M
    LegalizeAction DecreaseAction) {
509
1.86M
  SizeAndActionsVec result;
510
1.86M
  unsigned LargestSizeSoFar = 0;
511
1.86M
  if (v.size() >= 1 && 
v[0].first != 11.30M
)
512
1.25M
    result.push_back({1, IncreaseAction});
513
4.39M
  for (size_t i = 0; i < v.size(); 
++i2.52M
) {
514
2.52M
    result.push_back(v[i]);
515
2.52M
    LargestSizeSoFar = v[i].first;
516
2.52M
    if (i + 1 < v.size() && 
v[i + 1].first != v[i].first + 11.21M
) {
517
1.21M
      result.push_back({LargestSizeSoFar + 1, IncreaseAction});
518
1.21M
      LargestSizeSoFar = v[i].first + 1;
519
1.21M
    }
520
2.52M
  }
521
1.86M
  result.push_back({LargestSizeSoFar + 1, DecreaseAction});
522
1.86M
  return result;
523
1.86M
}
524
525
LegalizerInfo::SizeAndActionsVec
526
LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
527
    const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
528
59.4k
    LegalizeAction IncreaseAction) {
529
59.4k
  SizeAndActionsVec result;
530
59.4k
  if (v.size() == 0 || 
v[0].first != 145.8k
)
531
44.1k
    result.push_back({1, IncreaseAction});
532
260k
  for (size_t i = 0; i < v.size(); 
++i201k
) {
533
201k
    result.push_back(v[i]);
534
201k
    if (
i + 1 == v.size()201k
||
v[i + 1].first != v[i].first + 1155k
) {
535
201k
      result.push_back({v[i].first + 1, DecreaseAction});
536
201k
    }
537
201k
  }
538
59.4k
  return result;
539
59.4k
}
540
541
LegalizerInfo::SizeAndAction
542
5.16k
LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
543
5.16k
  assert(Size >= 1);
544
5.16k
  // Find the last element in Vec that has a bitsize equal to or smaller than
545
5.16k
  // the requested bit size.
546
5.16k
  // That is the element just before the first element that is bigger than Size.
547
5.16k
  auto It = partition_point(
548
10.5k
      Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
549
5.16k
  assert(It != Vec.begin() && "Does Vec not start with size 1?");
550
5.16k
  int VecIdx = It - Vec.begin() - 1;
551
5.16k
552
5.16k
  LegalizeAction Action = Vec[VecIdx].second;
553
5.16k
  switch (Action) {
554
5.16k
  case Legal:
555
4.99k
  case Lower:
556
4.99k
  case Libcall:
557
4.99k
  case Custom:
558
4.99k
    return {Size, Action};
559
4.99k
  case FewerElements:
560
31
    // FIXME: is this special case still needed and correct?
561
31
    // Special case for scalarization:
562
31
    if (Vec == SizeAndActionsVec({{1, FewerElements}}))
563
0
      return {1, FewerElements};
564
31
    LLVM_FALLTHROUGH;
565
47
  case NarrowScalar: {
566
47
    // The following needs to be a loop, as for now, we do allow needing to
567
47
    // go over "Unsupported" bit sizes before finding a legalizable bit size.
568
47
    // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
569
47
    // we need to iterate over s9, and then to s32 to return (s32, Legal).
570
47
    // If we want to get rid of the below loop, we should have stronger asserts
571
47
    // when building the SizeAndActionsVecs, probably not allowing
572
47
    // "Unsupported" unless at the ends of the vector.
573
47
    for (int i = VecIdx - 1; i >= 0; 
--i0
)
574
47
      if (!needsLegalizingToDifferentSize(Vec[i].second) &&
575
47
          Vec[i].second != Unsupported)
576
47
        return {Vec[i].first, Action};
577
47
    
llvm_unreachable0
("");
578
47
  }
579
118
  case WidenScalar:
580
118
  case MoreElements: {
581
118
    // See above, the following needs to be a loop, at least for now.
582
224
    for (std::size_t i = VecIdx + 1; i < Vec.size(); 
++i106
)
583
224
      if (!needsLegalizingToDifferentSize(Vec[i].second) &&
584
224
          
Vec[i].second != Unsupported118
)
585
118
        return {Vec[i].first, Action};
586
118
    
llvm_unreachable0
("");
587
118
  }
588
118
  case Unsupported:
589
3
    return {Size, Unsupported};
590
118
  case NotFound:
591
0
  case UseLegacyRules:
592
0
    llvm_unreachable("NotFound");
593
0
  }
594
0
  llvm_unreachable("Action has an unknown enum value");
595
0
}
596
597
std::pair<LegalizeAction, LLT>
598
5.79k
LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
599
5.79k
  assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
600
5.79k
  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
601
0
    return {NotFound, LLT()};
602
5.79k
  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
603
5.79k
  if (Aspect.Type.isPointer() &&
604
5.79k
      AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
605
630
          AddrSpace2PointerActions[OpcodeIdx].end()) {
606
0
    return {NotFound, LLT()};
607
0
  }
608
5.79k
  const SmallVector<SizeAndActionsVec, 1> &Actions =
609
5.79k
      Aspect.Type.isPointer()
610
5.79k
          ? AddrSpace2PointerActions[OpcodeIdx]
611
630
                .find(Aspect.Type.getAddressSpace())
612
630
                ->second
613
5.79k
          : 
ScalarActions[OpcodeIdx]5.16k
;
614
5.79k
  if (Aspect.Idx >= Actions.size())
615
1.47k
    return {NotFound, LLT()};
616
4.32k
  const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
617
4.32k
  // FIXME: speed up this search, e.g. by using a results cache for repeated
618
4.32k
  // queries?
619
4.32k
  auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
620
4.32k
  return {SizeAndAction.second,
621
4.32k
          Aspect.Type.isScalar() ? 
LLT::scalar(SizeAndAction.first)3.69k
622
4.32k
                                 : LLT::pointer(Aspect.Type.getAddressSpace(),
623
630
                                                SizeAndAction.first)};
624
4.32k
}
625
626
std::pair<LegalizeAction, LLT>
627
498
LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
628
498
  assert(Aspect.Type.isVector());
629
498
  // First legalize the vector element size, then legalize the number of
630
498
  // lanes in the vector.
631
498
  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
632
0
    return {NotFound, Aspect.Type};
633
498
  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
634
498
  const unsigned TypeIdx = Aspect.Idx;
635
498
  if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
636
79
    return {NotFound, Aspect.Type};
637
419
  const SizeAndActionsVec &ElemSizeVec =
638
419
      ScalarInVectorActions[OpcodeIdx][TypeIdx];
639
419
640
419
  LLT IntermediateType;
641
419
  auto ElementSizeAndAction =
642
419
      findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
643
419
  IntermediateType =
644
419
      LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
645
419
  if (ElementSizeAndAction.second != Legal)
646
2
    return {ElementSizeAndAction.second, IntermediateType};
647
417
648
417
  auto i = NumElements2Actions[OpcodeIdx].find(
649
417
      IntermediateType.getScalarSizeInBits());
650
417
  if (i == NumElements2Actions[OpcodeIdx].end()) {
651
0
    return {NotFound, IntermediateType};
652
0
  }
653
417
  const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
654
417
  auto NumElementsAndAction =
655
417
      findAction(NumElementsVec, IntermediateType.getNumElements());
656
417
  return {NumElementsAndAction.second,
657
417
          LLT::vector(NumElementsAndAction.first,
658
417
                      IntermediateType.getScalarSizeInBits())};
659
417
}
660
661
bool LegalizerInfo::legalizeIntrinsic(MachineInstr &MI,
662
                                      MachineRegisterInfo &MRI,
663
0
                                      MachineIRBuilder &MIRBuilder) const {
664
0
  return true;
665
0
}
666
667
/// \pre Type indices of every opcode form a dense set starting from 0.
668
46.8k
void LegalizerInfo::verify(const MCInstrInfo &MII) const {
669
#ifndef NDEBUG
670
  std::vector<unsigned> FailedOpcodes;
671
  for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
672
    const MCInstrDesc &MCID = MII.get(Opcode);
673
    const unsigned NumTypeIdxs = std::accumulate(
674
        MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
675
        [](unsigned Acc, const MCOperandInfo &OpInfo) {
676
          return OpInfo.isGenericType()
677
                     ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
678
                     : Acc;
679
        });
680
    LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
681
                      << "): " << NumTypeIdxs << " type ind"
682
                      << (NumTypeIdxs == 1 ? "ex" : "ices") << "\n");
683
    const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
684
    if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
685
      FailedOpcodes.push_back(Opcode);
686
  }
687
  if (!FailedOpcodes.empty()) {
688
    errs() << "The following opcodes have ill-defined legalization rules:";
689
    for (unsigned Opcode : FailedOpcodes)
690
      errs() << " " << MII.getName(Opcode);
691
    errs() << "\n";
692
693
    report_fatal_error("ill-defined LegalizerInfo"
694
                       ", try -debug-only=legalizer-info for details");
695
  }
696
#endif
697
}
698
699
#ifndef NDEBUG
700
// FIXME: This should be in the MachineVerifier, but it can't use the
701
// LegalizerInfo as it's currently in the separate GlobalISel library.
702
// Note that RegBankSelected property already checked in the verifier
703
// has the same layering problem, but we only use inline methods so
704
// end up not needing to link against the GlobalISel library.
705
const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
706
  if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
707
    const MachineRegisterInfo &MRI = MF.getRegInfo();
708
    for (const MachineBasicBlock &MBB : MF)
709
      for (const MachineInstr &MI : MBB)
710
        if (isPreISelGenericOpcode(MI.getOpcode()) &&
711
            !MLI->isLegalOrCustom(MI, MRI))
712
          return &MI;
713
  }
714
  return nullptr;
715
}
716
#endif