Coverage Report

Created: 2019-02-20 00:17

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