Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/CodeGen/GlobalISel/LegalizerInfo.h ------------------*- 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
//
9
/// Interface for Targets to specify which operations they can successfully
10
/// select and how the others should be expanded most efficiently.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
15
#define LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/None.h"
19
#include "llvm/ADT/Optional.h"
20
#include "llvm/ADT/STLExtras.h"
21
#include "llvm/ADT/SmallBitVector.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/CodeGen/MachineFunction.h"
24
#include "llvm/CodeGen/TargetOpcodes.h"
25
#include "llvm/Support/raw_ostream.h"
26
#include "llvm/Support/LowLevelTypeImpl.h"
27
#include <cassert>
28
#include <cstdint>
29
#include <tuple>
30
#include <unordered_map>
31
#include <utility>
32
33
namespace llvm {
34
35
extern cl::opt<bool> DisableGISelLegalityCheck;
36
37
class MachineInstr;
38
class MachineIRBuilder;
39
class MachineRegisterInfo;
40
class MCInstrInfo;
41
class GISelChangeObserver;
42
43
namespace LegalizeActions {
44
enum LegalizeAction : std::uint8_t {
45
  /// The operation is expected to be selectable directly by the target, and
46
  /// no transformation is necessary.
47
  Legal,
48
49
  /// The operation should be synthesized from multiple instructions acting on
50
  /// a narrower scalar base-type. For example a 64-bit add might be
51
  /// implemented in terms of 32-bit add-with-carry.
52
  NarrowScalar,
53
54
  /// The operation should be implemented in terms of a wider scalar
55
  /// base-type. For example a <2 x s8> add could be implemented as a <2
56
  /// x s32> add (ignoring the high bits).
57
  WidenScalar,
58
59
  /// The (vector) operation should be implemented by splitting it into
60
  /// sub-vectors where the operation is legal. For example a <8 x s64> add
61
  /// might be implemented as 4 separate <2 x s64> adds.
62
  FewerElements,
63
64
  /// The (vector) operation should be implemented by widening the input
65
  /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
66
  /// rarely legal, but you might perform an <8 x i8> and then only look at
67
  /// the first two results.
68
  MoreElements,
69
70
  /// The operation itself must be expressed in terms of simpler actions on
71
  /// this target. E.g. a SREM replaced by an SDIV and subtraction.
72
  Lower,
73
74
  /// The operation should be implemented as a call to some kind of runtime
75
  /// support library. For example this usually happens on machines that don't
76
  /// support floating-point operations natively.
77
  Libcall,
78
79
  /// The target wants to do something special with this combination of
80
  /// operand and type. A callback will be issued when it is needed.
81
  Custom,
82
83
  /// This operation is completely unsupported on the target. A programming
84
  /// error has occurred.
85
  Unsupported,
86
87
  /// Sentinel value for when no action was found in the specified table.
88
  NotFound,
89
90
  /// Fall back onto the old rules.
91
  /// TODO: Remove this once we've migrated
92
  UseLegacyRules,
93
};
94
} // end namespace LegalizeActions
95
raw_ostream &operator<<(raw_ostream &OS, LegalizeActions::LegalizeAction Action);
96
97
using LegalizeActions::LegalizeAction;
98
99
/// Legalization is decided based on an instruction's opcode, which type slot
100
/// we're considering, and what the existing type is. These aspects are gathered
101
/// together for convenience in the InstrAspect class.
102
struct InstrAspect {
103
  unsigned Opcode;
104
  unsigned Idx = 0;
105
  LLT Type;
106
107
2.05M
  InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
108
  InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
109
655k
      : Opcode(Opcode), Idx(Idx), Type(Type) {}
110
111
0
  bool operator==(const InstrAspect &RHS) const {
112
0
    return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
113
0
  }
114
};
115
116
/// The LegalityQuery object bundles together all the information that's needed
117
/// to decide whether a given operation is legal or not.
118
/// For efficiency, it doesn't make a copy of Types so care must be taken not
119
/// to free it before using the query.
120
struct LegalityQuery {
121
  unsigned Opcode;
122
  ArrayRef<LLT> Types;
123
124
  struct MemDesc {
125
    uint64_t SizeInBits;
126
    uint64_t AlignInBits;
127
    AtomicOrdering Ordering;
128
  };
129
130
  /// Operations which require memory can use this to place requirements on the
131
  /// memory type for each MMO.
132
  ArrayRef<MemDesc> MMODescrs;
133
134
  constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types,
135
                          const ArrayRef<MemDesc> MMODescrs)
136
14.1M
      : Opcode(Opcode), Types(Types), MMODescrs(MMODescrs) {}
137
  constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types)
138
371k
      : LegalityQuery(Opcode, Types, {}) {}
Unexecuted instantiation: llvm::LegalityQuery::LegalityQuery(unsigned int, llvm::ArrayRef<llvm::LLT>)
llvm::LegalityQuery::LegalityQuery(unsigned int, llvm::ArrayRef<llvm::LLT>)
Line
Count
Source
138
371k
      : LegalityQuery(Opcode, Types, {}) {}
139
140
  raw_ostream &print(raw_ostream &OS) const;
141
};
142
143
/// The result of a query. It either indicates a final answer of Legal or
144
/// Unsupported or describes an action that must be taken to make an operation
145
/// more legal.
146
struct LegalizeActionStep {
147
  /// The action to take or the final answer.
148
  LegalizeAction Action;
149
  /// If describing an action, the type index to change. Otherwise zero.
150
  unsigned TypeIdx;
151
  /// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
152
  LLT NewType;
153
154
  LegalizeActionStep(LegalizeAction Action, unsigned TypeIdx,
155
                     const LLT &NewType)
156
14.5M
      : Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}
157
158
  bool operator==(const LegalizeActionStep &RHS) const {
159
    return std::tie(Action, TypeIdx, NewType) ==
160
        std::tie(RHS.Action, RHS.TypeIdx, RHS.NewType);
161
  }
162
};
163
164
using LegalityPredicate = std::function<bool (const LegalityQuery &)>;
165
using LegalizeMutation =
166
    std::function<std::pair<unsigned, LLT>(const LegalityQuery &)>;
167
168
namespace LegalityPredicates {
169
struct TypePairAndMemDesc {
170
  LLT Type0;
171
  LLT Type1;
172
  uint64_t MemSize;
173
  uint64_t Align;
174
175
0
  bool operator==(const TypePairAndMemDesc &Other) const {
176
0
    return Type0 == Other.Type0 && Type1 == Other.Type1 &&
177
0
           Align == Other.Align &&
178
0
           MemSize == Other.MemSize;
179
0
  }
180
181
  /// \returns true if this memory access is legal with for the acecss described
182
  /// by \p Other (The alignment is sufficient for the size and result type).
183
8.62M
  bool isCompatible(const TypePairAndMemDesc &Other) const {
184
8.62M
    return Type0 == Other.Type0 && 
Type1 == Other.Type12.17M
&&
185
8.62M
           
Align >= Other.Align2.17M
&&
186
8.62M
           
MemSize == Other.MemSize2.17M
;
187
8.62M
  }
188
};
189
190
/// True iff P0 and P1 are true.
191
template<typename Predicate>
192
317k
Predicate all(Predicate P0, Predicate P1) {
193
317k
  return [=](const LegalityQuery &Query) {
194
113k
    return P0(Query) && 
P1(Query)112k
;
195
113k
  };
196
317k
}
197
/// True iff all given predicates are true.
198
template<typename Predicate, typename... Args>
199
162
Predicate all(Predicate P0, Predicate P1, Args... args) {
200
162
  return all(all(P0, P1), args...);
201
162
}
std::__1::function<bool (llvm::LegalityQuery const&)> llvm::LegalityPredicates::all<std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)> >(std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)>)
Line
Count
Source
199
54
Predicate all(Predicate P0, Predicate P1, Args... args) {
200
54
  return all(all(P0, P1), args...);
201
54
}
std::__1::function<bool (llvm::LegalityQuery const&)> llvm::LegalityPredicates::all<std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)> >(std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)>, std::__1::function<bool (llvm::LegalityQuery const&)>)
Line
Count
Source
199
108
Predicate all(Predicate P0, Predicate P1, Args... args) {
200
108
  return all(all(P0, P1), args...);
201
108
}
202
/// True iff the given type index is the specified types.
203
LegalityPredicate typeIs(unsigned TypeIdx, LLT TypesInit);
204
/// True iff the given type index is one of the specified types.
205
LegalityPredicate typeInSet(unsigned TypeIdx,
206
                            std::initializer_list<LLT> TypesInit);
207
/// True iff the given types for the given pair of type indexes is one of the
208
/// specified type pairs.
209
LegalityPredicate
210
typePairInSet(unsigned TypeIdx0, unsigned TypeIdx1,
211
              std::initializer_list<std::pair<LLT, LLT>> TypesInit);
212
/// True iff the given types for the given pair of type indexes is one of the
213
/// specified type pairs.
214
LegalityPredicate typePairAndMemDescInSet(
215
    unsigned TypeIdx0, unsigned TypeIdx1, unsigned MMOIdx,
216
    std::initializer_list<TypePairAndMemDesc> TypesAndMemDescInit);
217
/// True iff the specified type index is a scalar.
218
LegalityPredicate isScalar(unsigned TypeIdx);
219
/// True iff the specified type index is a vector.
220
LegalityPredicate isVector(unsigned TypeIdx);
221
/// True iff the specified type index is a pointer (with any address space).
222
LegalityPredicate isPointer(unsigned TypeIdx);
223
/// True iff the specified type index is a pointer with the specified address
224
/// space.
225
LegalityPredicate isPointer(unsigned TypeIdx, unsigned AddrSpace);
226
227
/// True iff the specified type index is a scalar that's narrower than the given
228
/// size.
229
LegalityPredicate narrowerThan(unsigned TypeIdx, unsigned Size);
230
231
/// True iff the specified type index is a scalar that's wider than the given
232
/// size.
233
LegalityPredicate widerThan(unsigned TypeIdx, unsigned Size);
234
235
/// True iff the specified type index is a scalar or vector with an element type
236
/// that's narrower than the given size.
237
LegalityPredicate scalarOrEltNarrowerThan(unsigned TypeIdx, unsigned Size);
238
239
/// True iff the specified type index is a scalar or a vector with an element
240
/// type that's wider than the given size.
241
LegalityPredicate scalarOrEltWiderThan(unsigned TypeIdx, unsigned Size);
242
243
/// True iff the specified type index is a scalar whose size is not a power of
244
/// 2.
245
LegalityPredicate sizeNotPow2(unsigned TypeIdx);
246
247
/// True iff the specified type index is a scalar or vector whose element size
248
/// is not a power of 2.
249
LegalityPredicate scalarOrEltSizeNotPow2(unsigned TypeIdx);
250
251
/// True iff the specified type indices are both the same bit size.
252
LegalityPredicate sameSize(unsigned TypeIdx0, unsigned TypeIdx1);
253
/// True iff the specified MMO index has a size that is not a power of 2
254
LegalityPredicate memSizeInBytesNotPow2(unsigned MMOIdx);
255
/// True iff the specified type index is a vector whose element count is not a
256
/// power of 2.
257
LegalityPredicate numElementsNotPow2(unsigned TypeIdx);
258
/// True iff the specified MMO index has at an atomic ordering of at Ordering or
259
/// stronger.
260
LegalityPredicate atomicOrderingAtLeastOrStrongerThan(unsigned MMOIdx,
261
                                                      AtomicOrdering Ordering);
262
} // end namespace LegalityPredicates
263
264
namespace LegalizeMutations {
265
/// Select this specific type for the given type index.
266
LegalizeMutation changeTo(unsigned TypeIdx, LLT Ty);
267
268
/// Keep the same type as the given type index.
269
LegalizeMutation changeTo(unsigned TypeIdx, unsigned FromTypeIdx);
270
271
/// Keep the same scalar or element type as the given type index.
272
LegalizeMutation changeElementTo(unsigned TypeIdx, unsigned FromTypeIdx);
273
274
/// Keep the same scalar or element type as the given type.
275
LegalizeMutation changeElementTo(unsigned TypeIdx, LLT Ty);
276
277
/// Widen the scalar type or vector element type for the given type index to the
278
/// next power of 2.
279
LegalizeMutation widenScalarOrEltToNextPow2(unsigned TypeIdx, unsigned Min = 0);
280
281
/// Add more elements to the type for the given type index to the next power of
282
/// 2.
283
LegalizeMutation moreElementsToNextPow2(unsigned TypeIdx, unsigned Min = 0);
284
/// Break up the vector type for the given type index into the element type.
285
LegalizeMutation scalarize(unsigned TypeIdx);
286
} // end namespace LegalizeMutations
287
288
/// A single rule in a legalizer info ruleset.
289
/// The specified action is chosen when the predicate is true. Where appropriate
290
/// for the action (e.g. for WidenScalar) the new type is selected using the
291
/// given mutator.
292
class LegalizeRule {
293
  LegalityPredicate Predicate;
294
  LegalizeAction Action;
295
  LegalizeMutation Mutation;
296
297
public:
298
  LegalizeRule(LegalityPredicate Predicate, LegalizeAction Action,
299
               LegalizeMutation Mutation = nullptr)
300
4.12M
      : Predicate(Predicate), Action(Action), Mutation(Mutation) {}
301
302
  /// Test whether the LegalityQuery matches.
303
15.6M
  bool match(const LegalityQuery &Query) const {
304
15.6M
    return Predicate(Query);
305
15.6M
  }
306
307
13.7M
  LegalizeAction getAction() const { return Action; }
308
309
  /// Determine the change to make.
310
13.7M
  std::pair<unsigned, LLT> determineMutation(const LegalityQuery &Query) const {
311
13.7M
    if (Mutation)
312
1.31M
      return Mutation(Query);
313
12.4M
    return std::make_pair(0, LLT{});
314
12.4M
  }
315
};
316
317
class LegalizeRuleSet {
318
  /// When non-zero, the opcode we are an alias of
319
  unsigned AliasOf;
320
  /// If true, there is another opcode that aliases this one
321
  bool IsAliasedByAnother;
322
  SmallVector<LegalizeRule, 2> Rules;
323
324
#ifndef NDEBUG
325
  /// If bit I is set, this rule set contains a rule that may handle (predicate
326
  /// or perform an action upon (or both)) the type index I. The uncertainty
327
  /// comes from free-form rules executing user-provided lambda functions. We
328
  /// conservatively assume such rules do the right thing and cover all type
329
  /// indices. The bitset is intentionally 1 bit wider than it absolutely needs
330
  /// to be to distinguish such cases from the cases where all type indices are
331
  /// individually handled.
332
  SmallBitVector TypeIdxsCovered{MCOI::OPERAND_LAST_GENERIC -
333
                                 MCOI::OPERAND_FIRST_GENERIC + 2};
334
#endif
335
336
4.33M
  unsigned typeIdx(unsigned TypeIdx) {
337
4.33M
    assert(TypeIdx <=
338
4.33M
               (MCOI::OPERAND_LAST_GENERIC - MCOI::OPERAND_FIRST_GENERIC) &&
339
4.33M
           "Type Index is out of bounds");
340
#ifndef NDEBUG
341
    TypeIdxsCovered.set(TypeIdx);
342
#endif
343
    return TypeIdx;
344
4.33M
  }
345
449k
  void markAllTypeIdxsAsCovered() {
346
#ifndef NDEBUG
347
    TypeIdxsCovered.set();
348
#endif
349
  }
350
351
4.12M
  void add(const LegalizeRule &Rule) {
352
4.12M
    assert(AliasOf == 0 &&
353
4.12M
           "RuleSet is aliased, change the representative opcode instead");
354
4.12M
    Rules.push_back(Rule);
355
4.12M
  }
356
357
1.09M
  static bool always(const LegalityQuery &) { return true; }
358
359
  /// Use the given action when the predicate is true.
360
  /// Action should not be an action that requires mutation.
361
  LegalizeRuleSet &actionIf(LegalizeAction Action,
362
1.50M
                            LegalityPredicate Predicate) {
363
1.50M
    add({Predicate, Action});
364
1.50M
    return *this;
365
1.50M
  }
366
  /// Use the given action when the predicate is true.
367
  /// Action should be an action that requires mutation.
368
  LegalizeRuleSet &actionIf(LegalizeAction Action, LegalityPredicate Predicate,
369
2.61M
                            LegalizeMutation Mutation) {
370
2.61M
    add({Predicate, Action, Mutation});
371
2.61M
    return *this;
372
2.61M
  }
373
  /// Use the given action when type index 0 is any type in the given list.
374
  /// Action should not be an action that requires mutation.
375
  LegalizeRuleSet &actionFor(LegalizeAction Action,
376
519k
                             std::initializer_list<LLT> Types) {
377
519k
    using namespace LegalityPredicates;
378
519k
    return actionIf(Action, typeInSet(typeIdx(0), Types));
379
519k
  }
380
  /// Use the given action when type index 0 is any type in the given list.
381
  /// Action should be an action that requires mutation.
382
  LegalizeRuleSet &actionFor(LegalizeAction Action,
383
                             std::initializer_list<LLT> Types,
384
19.4k
                             LegalizeMutation Mutation) {
385
19.4k
    using namespace LegalityPredicates;
386
19.4k
    return actionIf(Action, typeInSet(typeIdx(0), Types), Mutation);
387
19.4k
  }
388
  /// Use the given action when type indexes 0 and 1 is any type pair in the
389
  /// given list.
390
  /// Action should not be an action that requires mutation.
391
  LegalizeRuleSet &actionFor(LegalizeAction Action,
392
303k
                             std::initializer_list<std::pair<LLT, LLT>> Types) {
393
303k
    using namespace LegalityPredicates;
394
303k
    return actionIf(Action, typePairInSet(typeIdx(0), typeIdx(1), Types));
395
303k
  }
396
  /// Use the given action when type indexes 0 and 1 is any type pair in the
397
  /// given list.
398
  /// Action should be an action that requires mutation.
399
  LegalizeRuleSet &actionFor(LegalizeAction Action,
400
                             std::initializer_list<std::pair<LLT, LLT>> Types,
401
27.7k
                             LegalizeMutation Mutation) {
402
27.7k
    using namespace LegalityPredicates;
403
27.7k
    return actionIf(Action, typePairInSet(typeIdx(0), typeIdx(1), Types),
404
27.7k
                    Mutation);
405
27.7k
  }
406
  /// Use the given action when type indexes 0 and 1 are both in the given list.
407
  /// That is, the type pair is in the cartesian product of the list.
408
  /// Action should not be an action that requires mutation.
409
  LegalizeRuleSet &actionForCartesianProduct(LegalizeAction Action,
410
71.5k
                                             std::initializer_list<LLT> Types) {
411
71.5k
    using namespace LegalityPredicates;
412
71.5k
    return actionIf(Action, all(typeInSet(typeIdx(0), Types),
413
71.5k
                                typeInSet(typeIdx(1), Types)));
414
71.5k
  }
415
  /// Use the given action when type indexes 0 and 1 are both in their
416
  /// respective lists.
417
  /// That is, the type pair is in the cartesian product of the lists
418
  /// Action should not be an action that requires mutation.
419
  LegalizeRuleSet &
420
  actionForCartesianProduct(LegalizeAction Action,
421
                            std::initializer_list<LLT> Types0,
422
216k
                            std::initializer_list<LLT> Types1) {
423
216k
    using namespace LegalityPredicates;
424
216k
    return actionIf(Action, all(typeInSet(typeIdx(0), Types0),
425
216k
                                typeInSet(typeIdx(1), Types1)));
426
216k
  }
427
  /// Use the given action when type indexes 0, 1, and 2 are all in their
428
  /// respective lists.
429
  /// That is, the type triple is in the cartesian product of the lists
430
  /// Action should not be an action that requires mutation.
431
  LegalizeRuleSet &actionForCartesianProduct(
432
      LegalizeAction Action, std::initializer_list<LLT> Types0,
433
0
      std::initializer_list<LLT> Types1, std::initializer_list<LLT> Types2) {
434
0
    using namespace LegalityPredicates;
435
0
    return actionIf(Action, all(typeInSet(typeIdx(0), Types0),
436
0
                                all(typeInSet(typeIdx(1), Types1),
437
0
                                    typeInSet(typeIdx(2), Types2))));
438
0
  }
439
440
public:
441
6.04M
  LegalizeRuleSet() : AliasOf(0), IsAliasedByAnother(false), Rules() {}
442
443
0
  bool isAliasedByAnother() { return IsAliasedByAnother; }
444
392k
  void setIsAliasedByAnother() { IsAliasedByAnother = true; }
445
970k
  void aliasTo(unsigned Opcode) {
446
970k
    assert((AliasOf == 0 || AliasOf == Opcode) &&
447
970k
           "Opcode is already aliased to another opcode");
448
970k
    assert(Rules.empty() && "Aliasing will discard rules");
449
970k
    AliasOf = Opcode;
450
970k
  }
451
15.4M
  unsigned getAlias() const { return AliasOf; }
452
453
  /// The instruction is legal if predicate is true.
454
145k
  LegalizeRuleSet &legalIf(LegalityPredicate Predicate) {
455
145k
    // We have no choice but conservatively assume that the free-form
456
145k
    // user-provided Predicate properly handles all type indices:
457
145k
    markAllTypeIdxsAsCovered();
458
145k
    return actionIf(LegalizeAction::Legal, Predicate);
459
145k
  }
460
  /// The instruction is legal when type index 0 is any type in the given list.
461
452k
  LegalizeRuleSet &legalFor(std::initializer_list<LLT> Types) {
462
452k
    return actionFor(LegalizeAction::Legal, Types);
463
452k
  }
464
  /// The instruction is legal when type indexes 0 and 1 is any type pair in the
465
  /// given list.
466
295k
  LegalizeRuleSet &legalFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
467
295k
    return actionFor(LegalizeAction::Legal, Types);
468
295k
  }
469
  /// The instruction is legal when type indexes 0 and 1 along with the memory
470
  /// size and minimum alignment is any type and size tuple in the given list.
471
  LegalizeRuleSet &legalForTypesWithMemDesc(
472
      std::initializer_list<LegalityPredicates::TypePairAndMemDesc>
473
76.4k
          TypesAndMemDesc) {
474
76.4k
    return actionIf(LegalizeAction::Legal,
475
76.4k
                    LegalityPredicates::typePairAndMemDescInSet(
476
76.4k
                        typeIdx(0), typeIdx(1), /*MMOIdx*/ 0, TypesAndMemDesc));
477
76.4k
  }
478
  /// The instruction is legal when type indexes 0 and 1 are both in the given
479
  /// list. That is, the type pair is in the cartesian product of the list.
480
71.5k
  LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types) {
481
71.5k
    return actionForCartesianProduct(LegalizeAction::Legal, Types);
482
71.5k
  }
483
  /// The instruction is legal when type indexes 0 and 1 are both their
484
  /// respective lists.
485
  LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types0,
486
155k
                                            std::initializer_list<LLT> Types1) {
487
155k
    return actionForCartesianProduct(LegalizeAction::Legal, Types0, Types1);
488
155k
  }
489
  /// The instruction is legal when type indexes 0, 1, and 2 are both their
490
  /// respective lists.
491
  LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types0,
492
                                            std::initializer_list<LLT> Types1,
493
0
                                            std::initializer_list<LLT> Types2) {
494
0
    return actionForCartesianProduct(LegalizeAction::Legal, Types0, Types1,
495
0
                                     Types2);
496
0
  }
497
498
9.10k
  LegalizeRuleSet &alwaysLegal() {
499
9.10k
    using namespace LegalizeMutations;
500
9.10k
    markAllTypeIdxsAsCovered();
501
9.10k
    return actionIf(LegalizeAction::Legal, always);
502
9.10k
  }
503
504
  /// The instruction is lowered.
505
20.0k
  LegalizeRuleSet &lower() {
506
20.0k
    using namespace LegalizeMutations;
507
20.0k
    // We have no choice but conservatively assume that predicate-less lowering
508
20.0k
    // properly handles all type indices by design:
509
20.0k
    markAllTypeIdxsAsCovered();
510
20.0k
    return actionIf(LegalizeAction::Lower, always);
511
20.0k
  }
512
  /// The instruction is lowered if predicate is true. Keep type index 0 as the
513
  /// same type.
514
27.3k
  LegalizeRuleSet &lowerIf(LegalityPredicate Predicate) {
515
27.3k
    using namespace LegalizeMutations;
516
27.3k
    // We have no choice but conservatively assume that lowering with a
517
27.3k
    // free-form user provided Predicate properly handles all type indices:
518
27.3k
    markAllTypeIdxsAsCovered();
519
27.3k
    return actionIf(LegalizeAction::Lower, Predicate);
520
27.3k
  }
521
  /// The instruction is lowered if predicate is true.
522
  LegalizeRuleSet &lowerIf(LegalityPredicate Predicate,
523
0
                           LegalizeMutation Mutation) {
524
0
    // We have no choice but conservatively assume that lowering with a
525
0
    // free-form user provided Predicate properly handles all type indices:
526
0
    markAllTypeIdxsAsCovered();
527
0
    return actionIf(LegalizeAction::Lower, Predicate, Mutation);
528
0
  }
529
  /// The instruction is lowered when type index 0 is any type in the given
530
  /// list. Keep type index 0 as the same type.
531
19.4k
  LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types) {
532
19.4k
    return actionFor(LegalizeAction::Lower, Types,
533
19.4k
                     LegalizeMutations::changeTo(0, 0));
534
19.4k
  }
535
  /// The instruction is lowered when type index 0 is any type in the given
536
  /// list.
537
  LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types,
538
0
                            LegalizeMutation Mutation) {
539
0
    return actionFor(LegalizeAction::Lower, Types, Mutation);
540
0
  }
541
  /// The instruction is lowered when type indexes 0 and 1 is any type pair in
542
  /// the given list. Keep type index 0 as the same type.
543
27.7k
  LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
544
27.7k
    return actionFor(LegalizeAction::Lower, Types,
545
27.7k
                     LegalizeMutations::changeTo(0, 0));
546
27.7k
  }
547
  /// The instruction is lowered when type indexes 0 and 1 is any type pair in
548
  /// the given list.
549
  LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types,
550
0
                            LegalizeMutation Mutation) {
551
0
    return actionFor(LegalizeAction::Lower, Types, Mutation);
552
0
  }
553
  /// The instruction is lowered when type indexes 0 and 1 are both in their
554
  /// respective lists.
555
  LegalizeRuleSet &lowerForCartesianProduct(std::initializer_list<LLT> Types0,
556
0
                                            std::initializer_list<LLT> Types1) {
557
0
    using namespace LegalityPredicates;
558
0
    return actionForCartesianProduct(LegalizeAction::Lower, Types0, Types1);
559
0
  }
560
  /// The instruction is lowered when when type indexes 0, 1, and 2 are all in
561
  /// their respective lists.
562
  LegalizeRuleSet &lowerForCartesianProduct(std::initializer_list<LLT> Types0,
563
                                            std::initializer_list<LLT> Types1,
564
0
                                            std::initializer_list<LLT> Types2) {
565
0
    using namespace LegalityPredicates;
566
0
    return actionForCartesianProduct(LegalizeAction::Lower, Types0, Types1,
567
0
                                     Types2);
568
0
  }
569
570
  /// Like legalIf, but for the Libcall action.
571
0
  LegalizeRuleSet &libcallIf(LegalityPredicate Predicate) {
572
0
    // We have no choice but conservatively assume that a libcall with a
573
0
    // free-form user provided Predicate properly handles all type indices:
574
0
    markAllTypeIdxsAsCovered();
575
0
    return actionIf(LegalizeAction::Libcall, Predicate);
576
0
  }
577
60.2k
  LegalizeRuleSet &libcallFor(std::initializer_list<LLT> Types) {
578
60.2k
    return actionFor(LegalizeAction::Libcall, Types);
579
60.2k
  }
580
  LegalizeRuleSet &
581
4.45k
  libcallFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
582
4.45k
    return actionFor(LegalizeAction::Libcall, Types);
583
4.45k
  }
584
  LegalizeRuleSet &
585
0
  libcallForCartesianProduct(std::initializer_list<LLT> Types) {
586
0
    return actionForCartesianProduct(LegalizeAction::Libcall, Types);
587
0
  }
588
  LegalizeRuleSet &
589
  libcallForCartesianProduct(std::initializer_list<LLT> Types0,
590
49.7k
                             std::initializer_list<LLT> Types1) {
591
49.7k
    return actionForCartesianProduct(LegalizeAction::Libcall, Types0, Types1);
592
49.7k
  }
593
594
  /// Widen the scalar to the one selected by the mutation if the predicate is
595
  /// true.
596
  LegalizeRuleSet &widenScalarIf(LegalityPredicate Predicate,
597
96.5k
                                 LegalizeMutation Mutation) {
598
96.5k
    // We have no choice but conservatively assume that an action with a
599
96.5k
    // free-form user provided Predicate properly handles all type indices:
600
96.5k
    markAllTypeIdxsAsCovered();
601
96.5k
    return actionIf(LegalizeAction::WidenScalar, Predicate, Mutation);
602
96.5k
  }
603
  /// Narrow the scalar to the one selected by the mutation if the predicate is
604
  /// true.
605
  LegalizeRuleSet &narrowScalarIf(LegalityPredicate Predicate,
606
10.9k
                                  LegalizeMutation Mutation) {
607
10.9k
    // We have no choice but conservatively assume that an action with a
608
10.9k
    // free-form user provided Predicate properly handles all type indices:
609
10.9k
    markAllTypeIdxsAsCovered();
610
10.9k
    return actionIf(LegalizeAction::NarrowScalar, Predicate, Mutation);
611
10.9k
  }
612
613
  /// Add more elements to reach the type selected by the mutation if the
614
  /// predicate is true.
615
  LegalizeRuleSet &moreElementsIf(LegalityPredicate Predicate,
616
22.6k
                                  LegalizeMutation Mutation) {
617
22.6k
    // We have no choice but conservatively assume that an action with a
618
22.6k
    // free-form user provided Predicate properly handles all type indices:
619
22.6k
    markAllTypeIdxsAsCovered();
620
22.6k
    return actionIf(LegalizeAction::MoreElements, Predicate, Mutation);
621
22.6k
  }
622
  /// Remove elements to reach the type selected by the mutation if the
623
  /// predicate is true.
624
  LegalizeRuleSet &fewerElementsIf(LegalityPredicate Predicate,
625
80.1k
                                   LegalizeMutation Mutation) {
626
80.1k
    // We have no choice but conservatively assume that an action with a
627
80.1k
    // free-form user provided Predicate properly handles all type indices:
628
80.1k
    markAllTypeIdxsAsCovered();
629
80.1k
    return actionIf(LegalizeAction::FewerElements, Predicate, Mutation);
630
80.1k
  }
631
632
  /// The instruction is unsupported.
633
0
  LegalizeRuleSet &unsupported() {
634
0
    return actionIf(LegalizeAction::Unsupported, always);
635
0
  }
636
40.0k
  LegalizeRuleSet &unsupportedIf(LegalityPredicate Predicate) {
637
40.0k
    return actionIf(LegalizeAction::Unsupported, Predicate);
638
40.0k
  }
639
37.6k
  LegalizeRuleSet &unsupportedIfMemSizeNotPow2() {
640
37.6k
    return actionIf(LegalizeAction::Unsupported,
641
37.6k
                    LegalityPredicates::memSizeInBytesNotPow2(0));
642
37.6k
  }
643
644
37.1k
  LegalizeRuleSet &customIf(LegalityPredicate Predicate) {
645
37.1k
    // We have no choice but conservatively assume that a custom action with a
646
37.1k
    // free-form user provided Predicate properly handles all type indices:
647
37.1k
    markAllTypeIdxsAsCovered();
648
37.1k
    return actionIf(LegalizeAction::Custom, Predicate);
649
37.1k
  }
650
6.93k
  LegalizeRuleSet &customFor(std::initializer_list<LLT> Types) {
651
6.93k
    return actionFor(LegalizeAction::Custom, Types);
652
6.93k
  }
653
654
  /// The instruction is custom when type indexes 0 and 1 is any type pair in the
655
  /// given list.
656
3.64k
  LegalizeRuleSet &customFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
657
3.64k
    return actionFor(LegalizeAction::Custom, Types);
658
3.64k
  }
659
660
0
  LegalizeRuleSet &customForCartesianProduct(std::initializer_list<LLT> Types) {
661
0
    return actionForCartesianProduct(LegalizeAction::Custom, Types);
662
0
  }
663
  LegalizeRuleSet &
664
  customForCartesianProduct(std::initializer_list<LLT> Types0,
665
11.3k
                            std::initializer_list<LLT> Types1) {
666
11.3k
    return actionForCartesianProduct(LegalizeAction::Custom, Types0, Types1);
667
11.3k
  }
668
669
  /// Unconditionally custom lower.
670
2.56k
  LegalizeRuleSet &custom() {
671
2.56k
    return customIf(always);
672
2.56k
  }
673
674
  /// Widen the scalar to the next power of two that is at least MinSize.
675
  /// No effect if the type is not a scalar or is a power of two.
676
  LegalizeRuleSet &widenScalarToNextPow2(unsigned TypeIdx,
677
359k
                                         unsigned MinSize = 0) {
678
359k
    using namespace LegalityPredicates;
679
359k
    return actionIf(
680
359k
        LegalizeAction::WidenScalar, sizeNotPow2(typeIdx(TypeIdx)),
681
359k
        LegalizeMutations::widenScalarOrEltToNextPow2(TypeIdx, MinSize));
682
359k
  }
683
684
  /// Widen the scalar or vector element type to the next power of two that is
685
  /// at least MinSize.  No effect if the scalar size is a power of two.
686
  LegalizeRuleSet &widenScalarOrEltToNextPow2(unsigned TypeIdx,
687
9.10k
                                              unsigned MinSize = 0) {
688
9.10k
    using namespace LegalityPredicates;
689
9.10k
    return actionIf(
690
9.10k
        LegalizeAction::WidenScalar, scalarOrEltSizeNotPow2(typeIdx(TypeIdx)),
691
9.10k
        LegalizeMutations::widenScalarOrEltToNextPow2(TypeIdx, MinSize));
692
9.10k
  }
693
694
0
  LegalizeRuleSet &narrowScalar(unsigned TypeIdx, LegalizeMutation Mutation) {
695
0
    using namespace LegalityPredicates;
696
0
    return actionIf(LegalizeAction::NarrowScalar, isScalar(typeIdx(TypeIdx)),
697
0
                    Mutation);
698
0
  }
699
700
184k
  LegalizeRuleSet &scalarize(unsigned TypeIdx) {
701
184k
    using namespace LegalityPredicates;
702
184k
    return actionIf(LegalizeAction::FewerElements, isVector(typeIdx(TypeIdx)),
703
184k
                    LegalizeMutations::scalarize(TypeIdx));
704
184k
  }
705
706
  /// Ensure the scalar or element is at least as wide as Ty.
707
7.28k
  LegalizeRuleSet &minScalarOrElt(unsigned TypeIdx, const LLT &Ty) {
708
7.28k
    using namespace LegalityPredicates;
709
7.28k
    using namespace LegalizeMutations;
710
7.28k
    return actionIf(LegalizeAction::WidenScalar,
711
7.28k
                    scalarOrEltNarrowerThan(TypeIdx, Ty.getScalarSizeInBits()),
712
7.28k
                    changeElementTo(typeIdx(TypeIdx), Ty));
713
7.28k
  }
714
715
  /// Ensure the scalar or element is at least as wide as Ty.
716
  LegalizeRuleSet &minScalarOrEltIf(LegalityPredicate Predicate,
717
18.2k
                                    unsigned TypeIdx, const LLT &Ty) {
718
18.2k
    using namespace LegalityPredicates;
719
18.2k
    using namespace LegalizeMutations;
720
18.2k
    return actionIf(LegalizeAction::WidenScalar,
721
18.2k
                    all(Predicate, scalarOrEltNarrowerThan(
722
18.2k
                                       TypeIdx, Ty.getScalarSizeInBits())),
723
18.2k
                    changeElementTo(typeIdx(TypeIdx), Ty));
724
18.2k
  }
725
726
  /// Ensure the scalar is at least as wide as Ty.
727
850k
  LegalizeRuleSet &minScalar(unsigned TypeIdx, const LLT &Ty) {
728
850k
    using namespace LegalityPredicates;
729
850k
    using namespace LegalizeMutations;
730
850k
    return actionIf(LegalizeAction::WidenScalar,
731
850k
                    narrowerThan(TypeIdx, Ty.getSizeInBits()),
732
850k
                    changeTo(typeIdx(TypeIdx), Ty));
733
850k
  }
734
735
  /// Ensure the scalar is at most as wide as Ty.
736
3.64k
  LegalizeRuleSet &maxScalarOrElt(unsigned TypeIdx, const LLT &Ty) {
737
3.64k
    using namespace LegalityPredicates;
738
3.64k
    using namespace LegalizeMutations;
739
3.64k
    return actionIf(LegalizeAction::NarrowScalar,
740
3.64k
                    scalarOrEltWiderThan(TypeIdx, Ty.getScalarSizeInBits()),
741
3.64k
                    changeElementTo(typeIdx(TypeIdx), Ty));
742
3.64k
  }
743
744
  /// Ensure the scalar is at most as wide as Ty.
745
655k
  LegalizeRuleSet &maxScalar(unsigned TypeIdx, const LLT &Ty) {
746
655k
    using namespace LegalityPredicates;
747
655k
    using namespace LegalizeMutations;
748
655k
    return actionIf(LegalizeAction::NarrowScalar,
749
655k
                    widerThan(TypeIdx, Ty.getSizeInBits()),
750
655k
                    changeTo(typeIdx(TypeIdx), Ty));
751
655k
  }
752
753
  /// Conditionally limit the maximum size of the scalar.
754
  /// For example, when the maximum size of one type depends on the size of
755
  /// another such as extracting N bits from an M bit container.
756
  LegalizeRuleSet &maxScalarIf(LegalityPredicate Predicate, unsigned TypeIdx,
757
36.4k
                               const LLT &Ty) {
758
36.4k
    using namespace LegalityPredicates;
759
36.4k
    using namespace LegalizeMutations;
760
36.4k
    return actionIf(
761
36.4k
        LegalizeAction::NarrowScalar,
762
36.4k
        [=](const LegalityQuery &Query) {
763
0
          return widerThan(TypeIdx, Ty.getSizeInBits()) && Predicate(Query);
764
0
        },
765
36.4k
        changeElementTo(typeIdx(TypeIdx), Ty));
766
36.4k
  }
767
768
  /// Limit the range of scalar sizes to MinTy and MaxTy.
769
  LegalizeRuleSet &clampScalar(unsigned TypeIdx, const LLT &MinTy,
770
613k
                               const LLT &MaxTy) {
771
613k
    assert(MinTy.isScalar() && MaxTy.isScalar() && "Expected scalar types");
772
613k
    return minScalar(TypeIdx, MinTy).maxScalar(TypeIdx, MaxTy);
773
613k
  }
774
775
  /// Limit the range of scalar sizes to MinTy and MaxTy.
776
  LegalizeRuleSet &clampScalarOrElt(unsigned TypeIdx, const LLT &MinTy,
777
3.64k
                                    const LLT &MaxTy) {
778
3.64k
    return minScalarOrElt(TypeIdx, MinTy).maxScalarOrElt(TypeIdx, MaxTy);
779
3.64k
  }
780
781
  /// Widen the scalar to match the size of another.
782
30.9k
  LegalizeRuleSet &minScalarSameAs(unsigned TypeIdx, unsigned LargeTypeIdx) {
783
30.9k
    typeIdx(TypeIdx);
784
30.9k
    return widenScalarIf(
785
30.9k
        [=](const LegalityQuery &Query) {
786
609
          return Query.Types[LargeTypeIdx].getScalarSizeInBits() >
787
609
                 Query.Types[TypeIdx].getSizeInBits();
788
609
        },
789
30.9k
        [=](const LegalityQuery &Query) {
790
5
          LLT T = Query.Types[LargeTypeIdx];
791
5
          return std::make_pair(TypeIdx,
792
5
                                T.isVector() ? 
T.getElementType()0
: T);
793
5
        });
794
30.9k
  }
795
796
  /// Conditionally widen the scalar or elt to match the size of another.
797
  LegalizeRuleSet &minScalarEltSameAsIf(LegalityPredicate Predicate,
798
9.10k
                                   unsigned TypeIdx, unsigned LargeTypeIdx) {
799
9.10k
    typeIdx(TypeIdx);
800
9.10k
    return widenScalarIf(
801
9.10k
        [=](const LegalityQuery &Query) {
802
732
          return Query.Types[LargeTypeIdx].getScalarSizeInBits() >
803
732
                     Query.Types[TypeIdx].getScalarSizeInBits() &&
804
732
                 
Predicate(Query)701
;
805
732
        },
806
9.10k
        [=](const LegalityQuery &Query) {
807
697
          LLT T = Query.Types[LargeTypeIdx];
808
697
          return std::make_pair(TypeIdx, T);
809
697
        });
810
9.10k
  }
811
812
  /// Add more elements to the vector to reach the next power of two.
813
  /// No effect if the type is not a vector or the element count is a power of
814
  /// two.
815
18.2k
  LegalizeRuleSet &moreElementsToNextPow2(unsigned TypeIdx) {
816
18.2k
    using namespace LegalityPredicates;
817
18.2k
    return actionIf(LegalizeAction::MoreElements,
818
18.2k
                    numElementsNotPow2(typeIdx(TypeIdx)),
819
18.2k
                    LegalizeMutations::moreElementsToNextPow2(TypeIdx));
820
18.2k
  }
821
822
  /// Limit the number of elements in EltTy vectors to at least MinElements.
823
  LegalizeRuleSet &clampMinNumElements(unsigned TypeIdx, const LLT &EltTy,
824
80.1k
                                       unsigned MinElements) {
825
80.1k
    // Mark the type index as covered:
826
80.1k
    typeIdx(TypeIdx);
827
80.1k
    return actionIf(
828
80.1k
        LegalizeAction::MoreElements,
829
80.1k
        [=](const LegalityQuery &Query) {
830
4.30k
          LLT VecTy = Query.Types[TypeIdx];
831
4.30k
          return VecTy.isVector() && 
VecTy.getElementType() == EltTy4.30k
&&
832
4.30k
                 
VecTy.getNumElements() < MinElements1.52k
;
833
4.30k
        },
834
80.1k
        [=](const LegalityQuery &Query) {
835
12
          LLT VecTy = Query.Types[TypeIdx];
836
12
          return std::make_pair(
837
12
              TypeIdx, LLT::vector(MinElements, VecTy.getElementType()));
838
12
        });
839
80.1k
  }
840
  /// Limit the number of elements in EltTy vectors to at most MaxElements.
841
  LegalizeRuleSet &clampMaxNumElements(unsigned TypeIdx, const LLT &EltTy,
842
137k
                                       unsigned MaxElements) {
843
137k
    // Mark the type index as covered:
844
137k
    typeIdx(TypeIdx);
845
137k
    return actionIf(
846
137k
        LegalizeAction::FewerElements,
847
137k
        [=](const LegalityQuery &Query) {
848
6.22k
          LLT VecTy = Query.Types[TypeIdx];
849
6.22k
          return VecTy.isVector() && 
VecTy.getElementType() == EltTy6.12k
&&
850
6.22k
                 
VecTy.getNumElements() > MaxElements1.76k
;
851
6.22k
        },
852
137k
        [=](const LegalityQuery &Query) {
853
441
          LLT VecTy = Query.Types[TypeIdx];
854
441
          LLT NewTy = LLT::scalarOrVector(MaxElements, VecTy.getElementType());
855
441
          return std::make_pair(TypeIdx, NewTy);
856
441
        });
857
137k
  }
858
  /// Limit the number of elements for the given vectors to at least MinTy's
859
  /// number of elements and at most MaxTy's number of elements.
860
  ///
861
  /// No effect if the type is not a vector or does not have the same element
862
  /// type as the constraints.
863
  /// The element type of MinTy and MaxTy must match.
864
  LegalizeRuleSet &clampNumElements(unsigned TypeIdx, const LLT &MinTy,
865
80.1k
                                    const LLT &MaxTy) {
866
80.1k
    assert(MinTy.getElementType() == MaxTy.getElementType() &&
867
80.1k
           "Expected element types to agree");
868
80.1k
869
80.1k
    const LLT &EltTy = MinTy.getElementType();
870
80.1k
    return clampMinNumElements(TypeIdx, EltTy, MinTy.getNumElements())
871
80.1k
        .clampMaxNumElements(TypeIdx, EltTy, MaxTy.getNumElements());
872
80.1k
  }
873
874
  /// Fallback on the previous implementation. This should only be used while
875
  /// porting a rule.
876
0
  LegalizeRuleSet &fallback() {
877
0
    add({always, LegalizeAction::UseLegacyRules});
878
0
    return *this;
879
0
  }
880
881
  /// Check if there is no type index which is obviously not handled by the
882
  /// LegalizeRuleSet in any way at all.
883
  /// \pre Type indices of the opcode form a dense [0, \p NumTypeIdxs) set.
884
  bool verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const;
885
886
  /// Apply the ruleset to the given LegalityQuery.
887
  LegalizeActionStep apply(const LegalityQuery &Query) const;
888
};
889
890
class LegalizerInfo {
891
public:
892
  LegalizerInfo();
893
34.0k
  virtual ~LegalizerInfo() = default;
894
895
  unsigned getOpcodeIdxForOpcode(unsigned Opcode) const;
896
  unsigned getActionDefinitionsIdx(unsigned Opcode) const;
897
898
  /// Compute any ancillary tables needed to quickly decide how an operation
899
  /// should be handled. This must be called after all "set*Action"methods but
900
  /// before any query is made or incorrect results may be returned.
901
  void computeTables();
902
903
  /// Perform simple self-diagnostic and assert if there is anything obviously
904
  /// wrong with the actions set up.
905
  void verify(const MCInstrInfo &MII) const;
906
907
271
  static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
908
271
    using namespace LegalizeActions;
909
271
    switch (Action) {
910
271
    case NarrowScalar:
911
106
    case WidenScalar:
912
106
    case FewerElements:
913
106
    case MoreElements:
914
106
    case Unsupported:
915
106
      return true;
916
165
    default:
917
165
      return false;
918
271
    }
919
271
  }
920
921
  using SizeAndAction = std::pair<uint16_t, LegalizeAction>;
922
  using SizeAndActionsVec = std::vector<SizeAndAction>;
923
  using SizeChangeStrategy =
924
      std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
925
926
  /// More friendly way to set an action for common types that have an LLT
927
  /// representation.
928
  /// The LegalizeAction must be one for which NeedsLegalizingToDifferentSize
929
  /// returns false.
930
2.70M
  void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
931
2.70M
    assert(!needsLegalizingToDifferentSize(Action));
932
2.70M
    TablesInitialized = false;
933
2.70M
    const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
934
2.70M
    if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
935
617k
      SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
936
2.70M
    SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
937
2.70M
  }
938
939
  /// The setAction calls record the non-size-changing legalization actions
940
  /// to take on specificly-sized types. The SizeChangeStrategy defines what
941
  /// to do when the size of the type needs to be changed to reach a legally
942
  /// sized type (i.e., one that was defined through a setAction call).
943
  /// e.g.
944
  /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
945
  /// setLegalizeScalarToDifferentSizeStrategy(
946
  ///   G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
947
  /// will end up defining getAction({G_ADD, 0, T}) to return the following
948
  /// actions for different scalar types T:
949
  ///  LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
950
  ///  LLT::scalar(32):                 {Legal, 0, LLT::scalar(32)}
951
  ///  LLT::scalar(33)..:               {NarrowScalar, 0, LLT::scalar(32)}
952
  ///
953
  /// If no SizeChangeAction gets defined, through this function,
954
  /// the default is unsupportedForDifferentSizes.
955
  void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
956
                                                const unsigned TypeIdx,
957
587k
                                                SizeChangeStrategy S) {
958
587k
    const unsigned OpcodeIdx = Opcode - FirstOp;
959
587k
    if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
960
541k
      ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
961
587k
    ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
962
587k
  }
963
964
  /// See also setLegalizeScalarToDifferentSizeStrategy.
965
  /// This function allows to set the SizeChangeStrategy for vector elements.
966
  void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
967
                                                       const unsigned TypeIdx,
968
                                                       SizeChangeStrategy S) {
969
    const unsigned OpcodeIdx = Opcode - FirstOp;
970
    if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
971
      VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
972
    VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
973
  }
974
975
  /// A SizeChangeStrategy for the common case where legalization for a
976
  /// particular operation consists of only supporting a specific set of type
977
  /// sizes. E.g.
978
  ///   setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
979
  ///   setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
980
  ///   setLegalizeScalarToDifferentSizeStrategy(
981
  ///     G_DIV, 0, unsupportedForDifferentSizes);
982
  /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
983
  /// and Unsupported for all other scalar types T.
984
  static SizeAndActionsVec
985
1.22M
  unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
986
1.22M
    using namespace LegalizeActions;
987
1.22M
    return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
988
1.22M
                                                     Unsupported);
989
1.22M
  }
990
991
  /// A SizeChangeStrategy for the common case where legalization for a
992
  /// particular operation consists of widening the type to a large legal type,
993
  /// unless there is no such type and then instead it should be narrowed to the
994
  /// largest legal type.
995
  static SizeAndActionsVec
996
30.5k
  widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
997
30.5k
    using namespace LegalizeActions;
998
30.5k
    assert(v.size() > 0 &&
999
30.5k
           "At least one size that can be legalized towards is needed"
1000
30.5k
           " for this SizeChangeStrategy");
1001
30.5k
    return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
1002
30.5k
                                                     NarrowScalar);
1003
30.5k
  }
1004
1005
  static SizeAndActionsVec
1006
34.1k
  widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
1007
34.1k
    using namespace LegalizeActions;
1008
34.1k
    return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
1009
34.1k
                                                     Unsupported);
1010
34.1k
  }
1011
1012
  static SizeAndActionsVec
1013
28.8k
  narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
1014
28.8k
    using namespace LegalizeActions;
1015
28.8k
    return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
1016
28.8k
                                                       Unsupported);
1017
28.8k
  }
1018
1019
  static SizeAndActionsVec
1020
30.5k
  narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec &v) {
1021
30.5k
    using namespace LegalizeActions;
1022
30.5k
    assert(v.size() > 0 &&
1023
30.5k
           "At least one size that can be legalized towards is needed"
1024
30.5k
           " for this SizeChangeStrategy");
1025
30.5k
    return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
1026
30.5k
                                                       WidenScalar);
1027
30.5k
  }
1028
1029
  /// A SizeChangeStrategy for the common case where legalization for a
1030
  /// particular vector operation consists of having more elements in the
1031
  /// vector, to a type that is legal. Unless there is no such type and then
1032
  /// instead it should be legalized towards the widest vector that's still
1033
  /// legal. E.g.
1034
  ///   setAction({G_ADD, LLT::vector(8, 8)}, Legal);
1035
  ///   setAction({G_ADD, LLT::vector(16, 8)}, Legal);
1036
  ///   setAction({G_ADD, LLT::vector(2, 32)}, Legal);
1037
  ///   setAction({G_ADD, LLT::vector(4, 32)}, Legal);
1038
  ///   setLegalizeVectorElementToDifferentSizeStrategy(
1039
  ///     G_ADD, 0, moreToWiderTypesAndLessToWidest);
1040
  /// will result in the following getAction results:
1041
  ///   * getAction({G_ADD, LLT::vector(8,8)}) returns
1042
  ///       (Legal, vector(8,8)).
1043
  ///   * getAction({G_ADD, LLT::vector(9,8)}) returns
1044
  ///       (MoreElements, vector(16,8)).
1045
  ///   * getAction({G_ADD, LLT::vector(8,32)}) returns
1046
  ///       (FewerElements, vector(4,32)).
1047
  static SizeAndActionsVec
1048
580k
  moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
1049
580k
    using namespace LegalizeActions;
1050
580k
    return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
1051
580k
                                                     FewerElements);
1052
580k
  }
1053
1054
  /// Helper function to implement many typical SizeChangeStrategy functions.
1055
  static SizeAndActionsVec
1056
  increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
1057
                                            LegalizeAction IncreaseAction,
1058
                                            LegalizeAction DecreaseAction);
1059
  /// Helper function to implement many typical SizeChangeStrategy functions.
1060
  static SizeAndActionsVec
1061
  decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v,
1062
                                              LegalizeAction DecreaseAction,
1063
                                              LegalizeAction IncreaseAction);
1064
1065
  /// Get the action definitions for the given opcode. Use this to run a
1066
  /// LegalityQuery through the definitions.
1067
  const LegalizeRuleSet &getActionDefinitions(unsigned Opcode) const;
1068
1069
  /// Get the action definition builder for the given opcode. Use this to define
1070
  /// the action definitions.
1071
  ///
1072
  /// It is an error to request an opcode that has already been requested by the
1073
  /// multiple-opcode variant.
1074
  LegalizeRuleSet &getActionDefinitionsBuilder(unsigned Opcode);
1075
1076
  /// Get the action definition builder for the given set of opcodes. Use this
1077
  /// to define the action definitions for multiple opcodes at once. The first
1078
  /// opcode given will be considered the representative opcode and will hold
1079
  /// the definitions whereas the other opcodes will be configured to refer to
1080
  /// the representative opcode. This lowers memory requirements and very
1081
  /// slightly improves performance.
1082
  ///
1083
  /// It would be very easy to introduce unexpected side-effects as a result of
1084
  /// this aliasing if it were permitted to request different but intersecting
1085
  /// sets of opcodes but that is difficult to keep track of. It is therefore an
1086
  /// error to request the same opcode twice using this API, to request an
1087
  /// opcode that already has definitions, or to use the single-opcode API on an
1088
  /// opcode that has already been requested by this API.
1089
  LegalizeRuleSet &
1090
  getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes);
1091
  void aliasActionDefinitions(unsigned OpcodeTo, unsigned OpcodeFrom);
1092
1093
  /// Determine what action should be taken to legalize the described
1094
  /// instruction. Requires computeTables to have been called.
1095
  ///
1096
  /// \returns a description of the next legalization step to perform.
1097
  LegalizeActionStep getAction(const LegalityQuery &Query) const;
1098
1099
  /// Determine what action should be taken to legalize the given generic
1100
  /// instruction.
1101
  ///
1102
  /// \returns a description of the next legalization step to perform.
1103
  LegalizeActionStep getAction(const MachineInstr &MI,
1104
                               const MachineRegisterInfo &MRI) const;
1105
1106
0
  bool isLegal(const LegalityQuery &Query) const {
1107
0
    return getAction(Query).Action == LegalizeAction::Legal;
1108
0
  }
1109
  bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
1110
  bool isLegalOrCustom(const MachineInstr &MI,
1111
                       const MachineRegisterInfo &MRI) const;
1112
1113
  virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
1114
                              MachineIRBuilder &MIRBuilder,
1115
                              GISelChangeObserver &Observer) const;
1116
1117
  /// Return true if MI is either legal or has been legalized and false
1118
  /// if not legal.
1119
  virtual bool legalizeIntrinsic(MachineInstr &MI, MachineRegisterInfo &MRI,
1120
                                 MachineIRBuilder &MIRBuilder) const;
1121
1122
private:
1123
  /// Determine what action should be taken to legalize the given generic
1124
  /// instruction opcode, type-index and type. Requires computeTables to have
1125
  /// been called.
1126
  ///
1127
  /// \returns a pair consisting of the kind of legalization that should be
1128
  /// performed and the destination type.
1129
  std::pair<LegalizeAction, LLT>
1130
  getAspectAction(const InstrAspect &Aspect) const;
1131
1132
  /// The SizeAndActionsVec is a representation mapping between all natural
1133
  /// numbers and an Action. The natural number represents the bit size of
1134
  /// the InstrAspect. For example, for a target with native support for 32-bit
1135
  /// and 64-bit additions, you'd express that as:
1136
  /// setScalarAction(G_ADD, 0,
1137
  ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
1138
  ///            {32, Legal},       // bit sizes [32, 33[
1139
  ///            {33, WidenScalar}, // bit sizes [33, 64[
1140
  ///            {64, Legal},       // bit sizes [64, 65[
1141
  ///            {65, NarrowScalar} // bit sizes [65, +inf[
1142
  ///           });
1143
  /// It may be that only 64-bit pointers are supported on your target:
1144
  /// setPointerAction(G_GEP, 0, LLT:pointer(1),
1145
  ///           {{1, Unsupported},  // bit sizes [ 1, 63[
1146
  ///            {64, Legal},       // bit sizes [64, 65[
1147
  ///            {65, Unsupported}, // bit sizes [65, +inf[
1148
  ///           });
1149
  void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
1150
1.01M
                       const SizeAndActionsVec &SizeAndActions) {
1151
1.01M
    const unsigned OpcodeIdx = Opcode - FirstOp;
1152
1.01M
    SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
1153
1.01M
    setActions(TypeIndex, Actions, SizeAndActions);
1154
1.01M
  }
1155
  void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
1156
                        const unsigned AddressSpace,
1157
175k
                        const SizeAndActionsVec &SizeAndActions) {
1158
175k
    const unsigned OpcodeIdx = Opcode - FirstOp;
1159
175k
    if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
1160
175k
        AddrSpace2PointerActions[OpcodeIdx].end())
1161
144k
      AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
1162
175k
    SmallVector<SizeAndActionsVec, 1> &Actions =
1163
175k
        AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
1164
175k
    setActions(TypeIndex, Actions, SizeAndActions);
1165
175k
  }
1166
1167
  /// If an operation on a given vector type (say <M x iN>) isn't explicitly
1168
  /// specified, we proceed in 2 stages. First we legalize the underlying scalar
1169
  /// (so that there's at least one legal vector with that scalar), then we
1170
  /// adjust the number of elements in the vector so that it is legal. The
1171
  /// desired action in the first step is controlled by this function.
1172
  void setScalarInVectorAction(const unsigned Opcode, const unsigned TypeIndex,
1173
637k
                               const SizeAndActionsVec &SizeAndActions) {
1174
637k
    unsigned OpcodeIdx = Opcode - FirstOp;
1175
637k
    SmallVector<SizeAndActionsVec, 1> &Actions =
1176
637k
        ScalarInVectorActions[OpcodeIdx];
1177
637k
    setActions(TypeIndex, Actions, SizeAndActions);
1178
637k
  }
1179
1180
  /// See also setScalarInVectorAction.
1181
  /// This function let's you specify the number of elements in a vector that
1182
  /// are legal for a legal element size.
1183
  void setVectorNumElementAction(const unsigned Opcode,
1184
                                 const unsigned TypeIndex,
1185
                                 const unsigned ElementSize,
1186
580k
                                 const SizeAndActionsVec &SizeAndActions) {
1187
580k
    const unsigned OpcodeIdx = Opcode - FirstOp;
1188
580k
    if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
1189
580k
        NumElements2Actions[OpcodeIdx].end())
1190
436k
      NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
1191
580k
    SmallVector<SizeAndActionsVec, 1> &Actions =
1192
580k
        NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
1193
580k
    setActions(TypeIndex, Actions, SizeAndActions);
1194
580k
  }
1195
1196
  /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
1197
  /// i.e. it's OK if it doesn't start from size 1.
1198
1.39M
  static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
1199
1.39M
    using namespace LegalizeActions;
1200
#ifndef NDEBUG
1201
    // The sizes should be in increasing order
1202
    int prev_size = -1;
1203
    for(auto SizeAndAction: v) {
1204
      assert(SizeAndAction.first > prev_size);
1205
      prev_size = SizeAndAction.first;
1206
    }
1207
    // - for every Widen action, there should be a larger bitsize that
1208
    //   can be legalized towards (e.g. Legal, Lower, Libcall or Custom
1209
    //   action).
1210
    // - for every Narrow action, there should be a smaller bitsize that
1211
    //   can be legalized towards.
1212
    int SmallestNarrowIdx = -1;
1213
    int LargestWidenIdx = -1;
1214
    int SmallestLegalizableToSameSizeIdx = -1;
1215
    int LargestLegalizableToSameSizeIdx = -1;
1216
    for(size_t i=0; i<v.size(); ++i) {
1217
      switch (v[i].second) {
1218
        case FewerElements:
1219
        case NarrowScalar:
1220
          if (SmallestNarrowIdx == -1)
1221
            SmallestNarrowIdx = i;
1222
          break;
1223
        case WidenScalar:
1224
        case MoreElements:
1225
          LargestWidenIdx = i;
1226
          break;
1227
        case Unsupported:
1228
          break;
1229
        default:
1230
          if (SmallestLegalizableToSameSizeIdx == -1)
1231
            SmallestLegalizableToSameSizeIdx = i;
1232
          LargestLegalizableToSameSizeIdx = i;
1233
      }
1234
    }
1235
    if (SmallestNarrowIdx != -1) {
1236
      assert(SmallestLegalizableToSameSizeIdx != -1);
1237
      assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
1238
    }
1239
    if (LargestWidenIdx != -1)
1240
      assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
1241
#endif
1242
  }
1243
1244
  /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
1245
  /// from size 1.
1246
2.40M
  static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
1247
#ifndef NDEBUG
1248
    // Data structure invariant: The first bit size must be size 1.
1249
    assert(v.size() >= 1);
1250
    assert(v[0].first == 1);
1251
    checkPartialSizeAndActionsVector(v);
1252
#endif
1253
  }
1254
1255
  /// Sets actions for all bit sizes on a particular generic opcode, type
1256
  /// index and scalar or pointer type.
1257
  void setActions(unsigned TypeIndex,
1258
                  SmallVector<SizeAndActionsVec, 1> &Actions,
1259
2.40M
                  const SizeAndActionsVec &SizeAndActions) {
1260
2.40M
    checkFullSizeAndActionsVector(SizeAndActions);
1261
2.40M
    if (Actions.size() <= TypeIndex)
1262
1.79M
      Actions.resize(TypeIndex + 1);
1263
2.40M
    Actions[TypeIndex] = SizeAndActions;
1264
2.40M
  }
1265
1266
  static SizeAndAction findAction(const SizeAndActionsVec &Vec,
1267
                                  const uint32_t Size);
1268
1269
  /// Returns the next action needed to get the scalar or pointer type closer
1270
  /// to being legal
1271
  /// E.g. findLegalAction({G_REM, 13}) should return
1272
  /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
1273
  /// probably be called, which should return (Lower, 32).
1274
  /// This is assuming the setScalarAction on G_REM was something like:
1275
  /// setScalarAction(G_REM, 0,
1276
  ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
1277
  ///            {32, Lower},       // bit sizes [32, 33[
1278
  ///            {33, NarrowScalar} // bit sizes [65, +inf[
1279
  ///           });
1280
  std::pair<LegalizeAction, LLT>
1281
  findScalarLegalAction(const InstrAspect &Aspect) const;
1282
1283
  /// Returns the next action needed towards legalizing the vector type.
1284
  std::pair<LegalizeAction, LLT>
1285
  findVectorLegalAction(const InstrAspect &Aspect) const;
1286
1287
  static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
1288
  static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
1289
1290
  // Data structures used temporarily during construction of legality data:
1291
  using TypeMap = DenseMap<LLT, LegalizeAction>;
1292
  SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
1293
  SmallVector<SizeChangeStrategy, 1>
1294
      ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
1295
  SmallVector<SizeChangeStrategy, 1>
1296
      VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
1297
  bool TablesInitialized;
1298
1299
  // Data structures used by getAction:
1300
  SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
1301
  SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
1302
  std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
1303
      AddrSpace2PointerActions[LastOp - FirstOp + 1];
1304
  std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
1305
      NumElements2Actions[LastOp - FirstOp + 1];
1306
1307
  LegalizeRuleSet RulesForOpcode[LastOp - FirstOp + 1];
1308
};
1309
1310
#ifndef NDEBUG
1311
/// Checks that MIR is fully legal, returns an illegal instruction if it's not,
1312
/// nullptr otherwise
1313
const MachineInstr *machineFunctionIsIllegal(const MachineFunction &MF);
1314
#endif
1315
1316
} // end namespace llvm.
1317
1318
#endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H