Coverage Report

Created: 2018-11-12 17:33

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