1//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- 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// This file declares the CodeGenDAGPatterns class, which is used to read and
10// represent the patterns present in a .td file for instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_UTILS_TABLEGEN_COMMON_CODEGENDAGPATTERNS_H
15#define LLVM_UTILS_TABLEGEN_COMMON_CODEGENDAGPATTERNS_H
16
17#include "Basic/CodeGenIntrinsics.h"
18#include "Basic/SDNodeProperties.h"
19#include "CodeGenTarget.h"
20#include "llvm/ADT/IntrusiveRefCntPtr.h"
21#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/PointerUnion.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/ADT/StringMap.h"
25#include "llvm/ADT/StringSet.h"
26#include "llvm/ADT/Twine.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/MathExtras.h"
29#include "llvm/TableGen/Record.h"
30#include <algorithm>
31#include <array>
32#include <map>
33#include <numeric>
34#include <vector>
35
36namespace llvm {
37
38class Init;
39class ListInit;
40class DagInit;
41class SDNodeInfo;
42class TreePattern;
43class TreePatternNode;
44class CodeGenDAGPatterns;
45
46/// Shared pointer for TreePatternNode.
47using TreePatternNodePtr = IntrusiveRefCntPtr<TreePatternNode>;
48
49/// This represents a set of MVTs. Since the underlying type for the MVT
50/// is uint16_t, there are at most 65536 values. To reduce the number of memory
51/// allocations and deallocations, represent the set as a sequence of bits.
52/// To reduce the allocations even further, make MachineValueTypeSet own
53/// the storage and use std::array as the bit container.
54struct MachineValueTypeSet {
55 static unsigned constexpr Capacity = 512;
56 using WordType = uint64_t;
57 static unsigned constexpr WordWidth = CHAR_BIT * sizeof(WordType);
58 static unsigned constexpr NumWords = Capacity / WordWidth;
59 static_assert(NumWords * WordWidth == Capacity,
60 "Capacity should be a multiple of WordWidth");
61
62 LLVM_ATTRIBUTE_ALWAYS_INLINE
63 MachineValueTypeSet() { clear(); }
64
65 LLVM_ATTRIBUTE_ALWAYS_INLINE
66 unsigned size() const {
67 unsigned Count = 0;
68 for (WordType W : Words)
69 Count += llvm::popcount(Value: W);
70 return Count;
71 }
72 LLVM_ATTRIBUTE_ALWAYS_INLINE
73 void clear() { Words.fill(u: 0); }
74 LLVM_ATTRIBUTE_ALWAYS_INLINE
75 bool empty() const {
76 for (WordType W : Words)
77 if (W != 0)
78 return false;
79 return true;
80 }
81 LLVM_ATTRIBUTE_ALWAYS_INLINE
82 unsigned count(MVT T) const {
83 assert(T.SimpleTy < Capacity && "Capacity needs to be enlarged");
84 return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1;
85 }
86 std::pair<MachineValueTypeSet &, bool> insert(MVT T) {
87 assert(T.SimpleTy < Capacity && "Capacity needs to be enlarged");
88 bool V = count(T);
89 Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth);
90 return {*this, V};
91 }
92 MachineValueTypeSet &insert(const MachineValueTypeSet &S) {
93 for (unsigned i = 0; i != NumWords; ++i)
94 Words[i] |= S.Words[i];
95 return *this;
96 }
97 LLVM_ATTRIBUTE_ALWAYS_INLINE
98 void erase(MVT T) {
99 assert(T.SimpleTy < Capacity && "Capacity needs to be enlarged");
100 Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth));
101 }
102
103 void writeToStream(raw_ostream &OS) const;
104
105 struct const_iterator {
106 // Some implementations of the C++ library require these traits to be
107 // defined.
108 using iterator_category = std::forward_iterator_tag;
109 using value_type = MVT;
110 using difference_type = ptrdiff_t;
111 using pointer = const MVT *;
112 using reference = const MVT &;
113
114 LLVM_ATTRIBUTE_ALWAYS_INLINE
115 MVT operator*() const {
116 assert(Pos != Capacity);
117 return MVT::SimpleValueType(Pos);
118 }
119 LLVM_ATTRIBUTE_ALWAYS_INLINE
120 const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) {
121 Pos = End ? Capacity : find_from_pos(P: 0);
122 }
123 LLVM_ATTRIBUTE_ALWAYS_INLINE
124 const_iterator &operator++() {
125 assert(Pos != Capacity);
126 Pos = find_from_pos(P: Pos + 1);
127 return *this;
128 }
129
130 LLVM_ATTRIBUTE_ALWAYS_INLINE
131 bool operator==(const const_iterator &It) const {
132 return Set == It.Set && Pos == It.Pos;
133 }
134 LLVM_ATTRIBUTE_ALWAYS_INLINE
135 bool operator!=(const const_iterator &It) const { return !operator==(It); }
136
137 private:
138 unsigned find_from_pos(unsigned P) const {
139 unsigned SkipWords = P / WordWidth;
140
141 for (unsigned i = SkipWords; i != NumWords; ++i) {
142 WordType W = Set->Words[i];
143
144 // If P is in the middle of a word, process it manually here, because
145 // the trailing bits need to be masked off to use countr_zero.
146 if (i == SkipWords) {
147 unsigned SkipBits = P % WordWidth;
148 W &= maskTrailingZeros<WordType>(N: SkipBits);
149 }
150
151 if (W != 0)
152 return i * WordWidth + llvm::countr_zero(Val: W);
153 }
154 return Capacity;
155 }
156
157 const MachineValueTypeSet *Set;
158 unsigned Pos;
159 };
160
161 LLVM_ATTRIBUTE_ALWAYS_INLINE
162 const_iterator begin() const { return const_iterator(this, false); }
163 LLVM_ATTRIBUTE_ALWAYS_INLINE
164 const_iterator end() const { return const_iterator(this, true); }
165
166 LLVM_ATTRIBUTE_ALWAYS_INLINE
167 bool operator==(const MachineValueTypeSet &S) const {
168 return Words == S.Words;
169 }
170 LLVM_ATTRIBUTE_ALWAYS_INLINE
171 bool operator!=(const MachineValueTypeSet &S) const { return !operator==(S); }
172
173private:
174 friend struct const_iterator;
175 std::array<WordType, NumWords> Words;
176};
177
178raw_ostream &operator<<(raw_ostream &OS, const MachineValueTypeSet &T);
179
180struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
181 using SetType = MachineValueTypeSet;
182 unsigned AddrSpace = std::numeric_limits<unsigned>::max();
183
184 TypeSetByHwMode() = default;
185 TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
186 TypeSetByHwMode &operator=(const TypeSetByHwMode &) = default;
187 TypeSetByHwMode(MVT VT) : TypeSetByHwMode(ValueTypeByHwMode(VT)) {}
188 TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList);
189
190 SetType &getOrCreate(unsigned Mode) { return Map[Mode]; }
191
192 bool isValueTypeByHwMode(bool AllowEmpty) const;
193 ValueTypeByHwMode getValueTypeByHwMode(bool SkipEmpty = false) const;
194
195 LLVM_ATTRIBUTE_ALWAYS_INLINE
196 bool isMachineValueType() const {
197 return isSimple() && getSimple().size() == 1;
198 }
199
200 LLVM_ATTRIBUTE_ALWAYS_INLINE
201 MVT getMachineValueType() const {
202 assert(isMachineValueType());
203 return *getSimple().begin();
204 }
205
206 bool isPossible() const;
207
208 bool isPointer() const { return getValueTypeByHwMode().isPointer(); }
209
210 unsigned getPtrAddrSpace() const {
211 assert(isPointer());
212 return getValueTypeByHwMode().PtrAddrSpace;
213 }
214
215 bool insert(const ValueTypeByHwMode &VVT);
216 bool constrain(const TypeSetByHwMode &VTS);
217 template <typename Predicate> bool constrain(Predicate P);
218 template <typename Predicate>
219 bool assign_if(const TypeSetByHwMode &VTS, Predicate P);
220
221 void writeToStream(raw_ostream &OS) const;
222
223 bool operator==(const TypeSetByHwMode &VTS) const;
224 bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); }
225
226 void dump() const;
227 bool validate() const;
228
229private:
230 unsigned PtrAddrSpace = std::numeric_limits<unsigned>::max();
231 /// Intersect two sets. Return true if anything has changed.
232 bool intersect(SetType &Out, const SetType &In);
233};
234
235raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T);
236
237struct TypeInfer {
238 TypeInfer(TreePattern &T) : TP(T) {}
239
240 /// The protocol in the following functions (Merge*, force*, Enforce*,
241 /// expand*) is to return "true" if a change has been made, "false"
242 /// otherwise.
243
244 bool MergeInTypeInfo(TypeSetByHwMode &Out, const TypeSetByHwMode &In) const;
245 bool MergeInTypeInfo(TypeSetByHwMode &Out, MVT InVT) const {
246 return MergeInTypeInfo(Out, In: TypeSetByHwMode(InVT));
247 }
248 bool MergeInTypeInfo(TypeSetByHwMode &Out,
249 const ValueTypeByHwMode &InVT) const {
250 return MergeInTypeInfo(Out, In: TypeSetByHwMode(InVT));
251 }
252
253 /// Reduce the set \p Out to have at most one element for each mode.
254 bool forceArbitrary(TypeSetByHwMode &Out);
255
256 /// The following four functions ensure that upon return the set \p Out
257 /// will only contain types of the specified kind: integer, floating-point,
258 /// scalar, or vector.
259 /// If \p Out is empty, all legal types of the specified kind will be added
260 /// to it. Otherwise, all types that are not of the specified kind will be
261 /// removed from \p Out.
262 bool EnforceInteger(TypeSetByHwMode &Out);
263 bool EnforceFloatingPoint(TypeSetByHwMode &Out);
264 bool EnforceScalar(TypeSetByHwMode &Out);
265 bool EnforceVector(TypeSetByHwMode &Out);
266
267 /// If \p Out is empty, fill it with all legal types. Otherwise, leave it
268 /// unchanged.
269 bool EnforceAny(TypeSetByHwMode &Out);
270 /// Make sure that for each type in \p Small, there exists a larger type
271 /// in \p Big. \p SmallIsVT indicates that this is being called for
272 /// SDTCisVTSmallerThanOp. In that case the TypeSetByHwMode is re-created for
273 /// each call and needs special consideration in how we detect changes.
274 bool EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big,
275 bool SmallIsVT = false);
276 /// 1. Ensure that for each type T in \p Vec, T is a vector type, and that
277 /// for each type U in \p Elem, U is a scalar type.
278 /// 2. Ensure that for each (scalar) type U in \p Elem, there exists a
279 /// (vector) type T in \p Vec, such that U is the element type of T.
280 bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, TypeSetByHwMode &Elem);
281 bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
282 const ValueTypeByHwMode &VVT);
283 /// Ensure that for each type T in \p Sub, T is a vector type, and there
284 /// exists a type U in \p Vec such that U is a vector type with the same
285 /// element type as T and at least as many elements as T.
286 bool EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec, TypeSetByHwMode &Sub);
287 /// 1. Ensure that \p V has a scalar type iff \p W has a scalar type.
288 /// 2. Ensure that for each vector type T in \p V, there exists a vector
289 /// type U in \p W, such that T and U have the same number of elements.
290 /// 3. Ensure that for each vector type U in \p W, there exists a vector
291 /// type T in \p V, such that T and U have the same number of elements
292 /// (reverse of 2).
293 bool EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W);
294 /// 1. Ensure that for each type T in \p A, there exists a type U in \p B,
295 /// such that T and U have equal size in bits.
296 /// 2. Ensure that for each type U in \p B, there exists a type T in \p A
297 /// such that T and U have equal size in bits (reverse of 1).
298 bool EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B);
299
300 /// For each overloaded type (i.e. of form *Any), replace it with the
301 /// corresponding subset of legal, specific types.
302 void expandOverloads(TypeSetByHwMode &VTS) const;
303 void expandOverloads(TypeSetByHwMode::SetType &Out,
304 const TypeSetByHwMode::SetType &Legal) const;
305
306 struct ValidateOnExit {
307 ValidateOnExit(const TypeSetByHwMode &T, const TypeInfer &TI)
308 : Infer(TI), VTS(T) {}
309 ~ValidateOnExit();
310 const TypeInfer &Infer;
311 const TypeSetByHwMode &VTS;
312 };
313
314 struct SuppressValidation {
315 SuppressValidation(TypeInfer &TI) : Infer(TI), SavedValidate(TI.Validate) {
316 Infer.Validate = false;
317 }
318 ~SuppressValidation() { Infer.Validate = SavedValidate; }
319 TypeInfer &Infer;
320 bool SavedValidate;
321 };
322
323 TreePattern &TP;
324 bool Validate = true; // Indicate whether to validate types.
325
326private:
327 const TypeSetByHwMode &getLegalTypes() const;
328
329 /// Cached legal types (in default mode).
330 mutable bool LegalTypesCached = false;
331 mutable TypeSetByHwMode LegalCache;
332};
333
334/// Set type used to track multiply used variables in patterns
335using MultipleUseVarSet = StringSet<>;
336
337/// SDTypeConstraint - This is a discriminated union of constraints,
338/// corresponding to the SDTypeConstraint tablegen class in Target.td.
339struct SDTypeConstraint {
340 SDTypeConstraint() = default;
341 SDTypeConstraint(const Record *R, const CodeGenHwModes &CGH);
342
343 unsigned OperandNo; // The operand # this constraint applies to.
344 enum KindTy {
345 SDTCisVT,
346 SDTCisPtrTy,
347 SDTCisInt,
348 SDTCisFP,
349 SDTCisVec,
350 SDTCisSameAs,
351 SDTCisVTSmallerThanOp,
352 SDTCisOpSmallerThanOp,
353 SDTCisEltOfVec,
354 SDTCisSubVecOfVec,
355 SDTCVecEltisVT,
356 SDTCisSameNumEltsAs,
357 SDTCisSameSizeAs
358 } ConstraintType;
359
360 unsigned OtherOperandNo;
361
362 // The VT for SDTCisVT and SDTCVecEltisVT.
363 // Must not be in the union because it has a non-trivial destructor.
364 ValueTypeByHwMode VVT;
365
366 /// ApplyTypeConstraint - Given a node in a pattern, apply this type
367 /// constraint to the nodes operands. This returns true if it makes a
368 /// change, false otherwise. If a type contradiction is found, an error
369 /// is flagged.
370 bool ApplyTypeConstraint(TreePatternNode &N, const SDNodeInfo &NodeInfo,
371 TreePattern &TP) const;
372
373 friend bool operator==(const SDTypeConstraint &LHS,
374 const SDTypeConstraint &RHS);
375 friend bool operator<(const SDTypeConstraint &LHS,
376 const SDTypeConstraint &RHS);
377};
378
379bool operator==(const SDTypeConstraint &LHS, const SDTypeConstraint &RHS);
380bool operator<(const SDTypeConstraint &LHS, const SDTypeConstraint &RHS);
381
382/// ScopedName - A name of a node associated with a "scope" that indicates
383/// the context (e.g. instance of Pattern or PatFrag) in which the name was
384/// used. This enables substitution of pattern fragments while keeping track
385/// of what name(s) were originally given to various nodes in the tree.
386class ScopedName {
387 unsigned Scope;
388 std::string Identifier;
389
390public:
391 ScopedName(unsigned Scope, StringRef Identifier)
392 : Scope(Scope), Identifier(Identifier.str()) {
393 assert(Scope != 0 &&
394 "Scope == 0 is used to indicate predicates without arguments");
395 }
396
397 unsigned getScope() const { return Scope; }
398 const std::string &getIdentifier() const { return Identifier; }
399
400 bool operator==(const ScopedName &o) const;
401 bool operator!=(const ScopedName &o) const;
402};
403
404/// SDNodeInfo - One of these records is created for each SDNode instance in
405/// the target .td file. This represents the various dag nodes we will be
406/// processing.
407class SDNodeInfo {
408 const Record *Def;
409 StringRef EnumName;
410 StringRef SDClassName;
411 unsigned NumResults;
412 int NumOperands;
413 unsigned Properties;
414 bool IsStrictFP;
415 uint32_t TSFlags;
416 std::vector<SDTypeConstraint> TypeConstraints;
417
418public:
419 // Parse the specified record.
420 SDNodeInfo(const Record *R, const CodeGenHwModes &CGH);
421
422 unsigned getNumResults() const { return NumResults; }
423
424 /// getNumOperands - This is the number of operands required or -1 if
425 /// variadic.
426 int getNumOperands() const { return NumOperands; }
427 const Record *getRecord() const { return Def; }
428 StringRef getEnumName() const { return EnumName; }
429 StringRef getSDClassName() const { return SDClassName; }
430
431 const std::vector<SDTypeConstraint> &getTypeConstraints() const {
432 return TypeConstraints;
433 }
434
435 /// getKnownType - If the type constraints on this node imply a fixed type
436 /// (e.g. all stores return void, etc), then return it as an
437 /// MVT. Otherwise, return MVT::Other.
438 MVT getKnownType(unsigned ResNo) const;
439
440 unsigned getProperties() const { return Properties; }
441
442 /// hasProperty - Return true if this node has the specified property.
443 ///
444 bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); }
445
446 bool isStrictFP() const { return IsStrictFP; }
447
448 uint32_t getTSFlags() const { return TSFlags; }
449
450 /// ApplyTypeConstraints - Given a node in a pattern, apply the type
451 /// constraints for this node to the operands of the node. This returns
452 /// true if it makes a change, false otherwise. If a type contradiction is
453 /// found, an error is flagged.
454 bool ApplyTypeConstraints(TreePatternNode &N, TreePattern &TP) const;
455};
456
457/// TreePredicateFn - This is an abstraction that represents the predicates on
458/// a PatFrag node. This is a simple one-word wrapper around a pointer to
459/// provide nice accessors.
460class TreePredicateFn {
461 /// PatFragRec - This is the TreePattern for the PatFrag that we
462 /// originally came from.
463 TreePattern *PatFragRec;
464
465public:
466 /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag.
467 TreePredicateFn(TreePattern *N);
468
469 TreePattern *getOrigPatFragRecord() const { return PatFragRec; }
470
471 /// isAlwaysTrue - Return true if this is a noop predicate.
472 bool isAlwaysTrue() const;
473
474 bool isImmediatePattern() const { return hasImmCode(); }
475
476 /// getImmediatePredicateCode - Return the code that evaluates this pattern if
477 /// this is an immediate predicate. It is an error to call this on a
478 /// non-immediate pattern.
479 std::string getImmediatePredicateCode() const {
480 std::string Result = getImmCode();
481 assert(!Result.empty() && "Isn't an immediate pattern!");
482 return Result;
483 }
484
485 bool operator==(const TreePredicateFn &RHS) const {
486 return PatFragRec == RHS.PatFragRec;
487 }
488
489 bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); }
490
491 /// Return the name to use in the generated code to reference this, this is
492 /// "Predicate_foo" if from a pattern fragment "foo".
493 std::string getFnName() const;
494
495 /// getCodeToRunOnSDNode - Return the code for the function body that
496 /// evaluates this predicate. The argument is expected to be in "Node",
497 /// not N. This handles casting and conversion to a concrete node type as
498 /// appropriate.
499 std::string getCodeToRunOnSDNode() const;
500
501 /// Get the data type of the argument to getImmediatePredicateCode().
502 StringRef getImmType() const;
503
504 /// Get a string that describes the type returned by getImmType() but is
505 /// usable as part of an identifier.
506 StringRef getImmTypeIdentifier() const;
507
508 // Predicate code uses the PatFrag's captured operands.
509 bool usesOperands() const;
510
511 // Check if the HasNoUse predicate is set.
512 bool hasNoUse() const;
513 // Check if the HasOneUse predicate is set.
514 bool hasOneUse() const;
515
516 // Is the desired predefined predicate for a load?
517 bool isLoad() const;
518 // Is the desired predefined predicate for a store?
519 bool isStore() const;
520 // Is the desired predefined predicate for an atomic?
521 bool isAtomic() const;
522
523 /// Is this predicate the predefined unindexed load predicate?
524 /// Is this predicate the predefined unindexed store predicate?
525 bool isUnindexed() const;
526 /// Is this predicate the predefined non-extending load predicate?
527 bool isNonExtLoad() const;
528 /// Is this predicate the predefined any-extend load predicate?
529 bool isAnyExtLoad() const;
530 /// Is this predicate the predefined sign-extend load predicate?
531 bool isSignExtLoad() const;
532 /// Is this predicate the predefined zero-extend load predicate?
533 bool isZeroExtLoad() const;
534 /// Is this predicate the predefined non-truncating store predicate?
535 bool isNonTruncStore() const;
536 /// Is this predicate the predefined truncating store predicate?
537 bool isTruncStore() const;
538
539 /// Is this predicate the predefined monotonic atomic predicate?
540 bool isAtomicOrderingMonotonic() const;
541 /// Is this predicate the predefined acquire atomic predicate?
542 bool isAtomicOrderingAcquire() const;
543 /// Is this predicate the predefined release atomic predicate?
544 bool isAtomicOrderingRelease() const;
545 /// Is this predicate the predefined acquire-release atomic predicate?
546 bool isAtomicOrderingAcquireRelease() const;
547 /// Is this predicate the predefined sequentially consistent atomic predicate?
548 bool isAtomicOrderingSequentiallyConsistent() const;
549
550 /// Is this predicate the predefined acquire-or-stronger atomic predicate?
551 bool isAtomicOrderingAcquireOrStronger() const;
552 /// Is this predicate the predefined weaker-than-acquire atomic predicate?
553 bool isAtomicOrderingWeakerThanAcquire() const;
554
555 /// Is this predicate the predefined release-or-stronger atomic predicate?
556 bool isAtomicOrderingReleaseOrStronger() const;
557 /// Is this predicate the predefined weaker-than-release atomic predicate?
558 bool isAtomicOrderingWeakerThanRelease() const;
559
560 /// If non-null, indicates that this predicate is a predefined memory VT
561 /// predicate for a load/store and returns the ValueType record for the memory
562 /// VT.
563 const Record *getMemoryVT() const;
564 /// If non-null, indicates that this predicate is a predefined memory VT
565 /// predicate (checking only the scalar type) for load/store and returns the
566 /// ValueType record for the memory VT.
567 const Record *getScalarMemoryVT() const;
568
569 const ListInit *getAddressSpaces() const;
570 int64_t getMinAlignment() const;
571
572 // If true, indicates that GlobalISel-based C++ code was supplied.
573 bool hasGISelPredicateCode() const;
574 std::string getGISelPredicateCode() const;
575
576 // If true, indicates that GlobalISel-based C++ code was supplied for checking
577 // register operands.
578 bool hasGISelLeafPredicateCode() const;
579 std::string getGISelLeafPredicateCode() const;
580
581private:
582 bool hasPredCode() const;
583 bool hasImmCode() const;
584 std::string getPredCode() const;
585 std::string getImmCode() const;
586 bool immCodeUsesAPInt() const;
587 bool immCodeUsesAPFloat() const;
588
589 bool isPredefinedPredicateEqualTo(StringRef Field, bool Value) const;
590};
591
592struct TreePredicateCall {
593 TreePredicateFn Fn;
594
595 // Scope -- unique identifier for retrieving named arguments. 0 is used when
596 // the predicate does not use named arguments.
597 unsigned Scope;
598
599 TreePredicateCall(const TreePredicateFn &Fn, unsigned Scope)
600 : Fn(Fn), Scope(Scope) {}
601
602 bool operator==(const TreePredicateCall &o) const {
603 return Fn == o.Fn && Scope == o.Scope;
604 }
605 bool operator!=(const TreePredicateCall &o) const { return !(*this == o); }
606};
607
608class TreePatternNode : public RefCountedBase<TreePatternNode> {
609 /// The type of each node result. Before and during type inference, each
610 /// result may be a set of possible types. After (successful) type inference,
611 /// each is a single concrete type.
612 std::vector<TypeSetByHwMode> Types;
613
614 /// The index of each result in results of the pattern.
615 std::vector<unsigned> ResultPerm;
616
617 /// OperatorOrVal - The Record for the operator if this is an interior node
618 /// (not a leaf) or the init value (e.g. the "GPRC" record, or "7") for a
619 /// leaf.
620 PointerUnion<const Record *, const Init *> OperatorOrVal;
621
622 /// Name - The name given to this node with the :$foo notation.
623 ///
624 StringRef Name;
625
626 std::vector<ScopedName> NamesAsPredicateArg;
627
628 /// PredicateCalls - The predicate functions to execute on this node to check
629 /// for a match. If this list is empty, no predicate is involved.
630 std::vector<TreePredicateCall> PredicateCalls;
631
632 /// TransformFn - The transformation function to execute on this node before
633 /// it can be substituted into the resulting instruction on a pattern match.
634 const Record *TransformFn;
635
636 std::vector<TreePatternNodePtr> Children;
637
638 /// If this was instantiated from a PatFrag node, and the PatFrag was derived
639 /// from "GISelFlags": the original Record derived from GISelFlags.
640 const Record *GISelFlags = nullptr;
641
642public:
643 TreePatternNode(const Record *Op, std::vector<TreePatternNodePtr> Ch,
644 unsigned NumResults)
645 : OperatorOrVal(Op), TransformFn(nullptr), Children(std::move(Ch)) {
646 Types.resize(new_size: NumResults);
647 ResultPerm.resize(new_size: NumResults);
648 std::iota(first: ResultPerm.begin(), last: ResultPerm.end(), value: 0);
649 }
650 TreePatternNode(const Init *val, unsigned NumResults) // leaf ctor
651 : OperatorOrVal(val), TransformFn(nullptr) {
652 Types.resize(new_size: NumResults);
653 ResultPerm.resize(new_size: NumResults);
654 std::iota(first: ResultPerm.begin(), last: ResultPerm.end(), value: 0);
655 }
656
657 bool hasName() const { return !Name.empty(); }
658 StringRef getName() const { return Name; }
659 void setName(StringRef N) { Name = N; }
660
661 const std::vector<ScopedName> &getNamesAsPredicateArg() const {
662 return NamesAsPredicateArg;
663 }
664 void setNamesAsPredicateArg(const std::vector<ScopedName> &Names) {
665 NamesAsPredicateArg = Names;
666 }
667 void addNameAsPredicateArg(const ScopedName &N) {
668 NamesAsPredicateArg.push_back(x: N);
669 }
670
671 bool isLeaf() const { return isa<const Init *>(Val: OperatorOrVal); }
672
673 // Type accessors.
674 unsigned getNumTypes() const { return Types.size(); }
675 ValueTypeByHwMode getType(unsigned ResNo) const {
676 return Types[ResNo].getValueTypeByHwMode(/*SkipEmpty=*/SkipEmpty: true);
677 }
678 const std::vector<TypeSetByHwMode> &getExtTypes() const { return Types; }
679 const TypeSetByHwMode &getExtType(unsigned ResNo) const {
680 return Types[ResNo];
681 }
682 TypeSetByHwMode &getExtType(unsigned ResNo) { return Types[ResNo]; }
683 void setType(unsigned ResNo, const TypeSetByHwMode &T) { Types[ResNo] = T; }
684 MVT getSimpleType(unsigned ResNo) const {
685 return Types[ResNo].getMachineValueType();
686 }
687
688 bool hasConcreteType(unsigned ResNo) const {
689 return Types[ResNo].isValueTypeByHwMode(AllowEmpty: false);
690 }
691 bool isTypeCompletelyUnknown(unsigned ResNo, TreePattern &TP) const {
692 return Types[ResNo].empty();
693 }
694
695 unsigned getNumResults() const { return ResultPerm.size(); }
696 unsigned getResultIndex(unsigned ResNo) const { return ResultPerm[ResNo]; }
697 void setResultIndex(unsigned ResNo, unsigned RI) { ResultPerm[ResNo] = RI; }
698
699 const Init *getLeafValue() const {
700 assert(isLeaf());
701 return cast<const Init *>(Val: OperatorOrVal);
702 }
703 const Record *getOperator() const {
704 assert(!isLeaf());
705 return cast<const Record *>(Val: OperatorOrVal);
706 }
707
708 using child_iterator = pointee_iterator<decltype(Children)::iterator>;
709 using child_const_iterator =
710 pointee_iterator<decltype(Children)::const_iterator>;
711
712 iterator_range<child_iterator> children() {
713 return make_pointee_range(Range&: Children);
714 }
715
716 iterator_range<child_const_iterator> children() const {
717 return make_pointee_range(Range: Children);
718 }
719
720 unsigned getNumChildren() const { return Children.size(); }
721 const TreePatternNode &getChild(unsigned N) const {
722 return *Children[N].get();
723 }
724 TreePatternNode &getChild(unsigned N) { return *Children[N].get(); }
725 const TreePatternNodePtr &getChildShared(unsigned N) const {
726 return Children[N];
727 }
728 TreePatternNodePtr &getChildSharedPtr(unsigned N) { return Children[N]; }
729 void setChild(unsigned i, TreePatternNodePtr N) { Children[i] = N; }
730
731 /// hasChild - Return true if N is any of our children.
732 bool hasChild(const TreePatternNode *N) const {
733 for (const TreePatternNodePtr &Child : Children)
734 if (Child.get() == N)
735 return true;
736 return false;
737 }
738
739 bool hasProperTypeByHwMode() const;
740 bool hasPossibleType() const;
741 bool setDefaultMode(unsigned Mode);
742
743 bool hasAnyPredicate() const { return !PredicateCalls.empty(); }
744
745 const std::vector<TreePredicateCall> &getPredicateCalls() const {
746 return PredicateCalls;
747 }
748 void clearPredicateCalls() { PredicateCalls.clear(); }
749 void setPredicateCalls(const std::vector<TreePredicateCall> &Calls) {
750 assert(PredicateCalls.empty() && "Overwriting non-empty predicate list!");
751 PredicateCalls = Calls;
752 }
753 void addPredicateCall(const TreePredicateCall &Call) {
754 assert(!Call.Fn.isAlwaysTrue() && "Empty predicate string!");
755 assert(!is_contained(PredicateCalls, Call) &&
756 "predicate applied recursively");
757 PredicateCalls.push_back(x: Call);
758 }
759 void addPredicateCall(const TreePredicateFn &Fn, unsigned Scope) {
760 assert((Scope != 0) == Fn.usesOperands());
761 addPredicateCall(Call: TreePredicateCall(Fn, Scope));
762 }
763
764 const Record *getTransformFn() const { return TransformFn; }
765 void setTransformFn(const Record *Fn) { TransformFn = Fn; }
766
767 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
768 /// CodeGenIntrinsic information for it, otherwise return a null pointer.
769 const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const;
770
771 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
772 /// return the ComplexPattern information, otherwise return null.
773 const ComplexPattern *
774 getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const;
775
776 /// Returns the number of MachineInstr operands that would be produced by this
777 /// node if it mapped directly to an output Instruction's
778 /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it
779 /// for Operands; otherwise 1.
780 unsigned getNumMIResults(const CodeGenDAGPatterns &CGP) const;
781
782 /// NodeHasProperty - Return true if this node has the specified property.
783 bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;
784
785 /// TreeHasProperty - Return true if any node in this tree has the specified
786 /// property.
787 bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;
788
789 /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is
790 /// marked isCommutative.
791 bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const;
792
793 void setGISelFlagsRecord(const Record *R) { GISelFlags = R; }
794 const Record *getGISelFlagsRecord() const { return GISelFlags; }
795
796 void print(raw_ostream &OS) const;
797 void dump() const;
798
799public: // Higher level manipulation routines.
800 /// clone - Return a new copy of this tree.
801 ///
802 TreePatternNodePtr clone() const;
803
804 /// RemoveAllTypes - Recursively strip all the types of this tree.
805 void RemoveAllTypes();
806
807 /// isIsomorphicTo - Return true if this node is recursively isomorphic to
808 /// the specified node. For this comparison, all of the state of the node
809 /// is considered, except for the assigned name. Nodes with differing names
810 /// that are otherwise identical are considered isomorphic.
811 bool isIsomorphicTo(const TreePatternNode &N,
812 const MultipleUseVarSet &DepVars) const;
813
814 /// SubstituteFormalArguments - Replace the formal arguments in this tree
815 /// with actual values specified by ArgMap.
816 void
817 SubstituteFormalArguments(std::map<StringRef, TreePatternNodePtr> &ArgMap);
818
819 /// InlinePatternFragments - If \p T pattern refers to any pattern
820 /// fragments, return the set of inlined versions (this can be more than
821 /// one if a PatFrags record has multiple alternatives).
822 void InlinePatternFragments(TreePattern &TP,
823 std::vector<TreePatternNodePtr> &OutAlternatives);
824
825 /// ApplyTypeConstraints - Apply all of the type constraints relevant to
826 /// this node and its children in the tree. This returns true if it makes a
827 /// change, false otherwise. If a type contradiction is found, flag an error.
828 bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters);
829
830 /// UpdateNodeType - Set the node type of N to VT if VT contains
831 /// information. If N already contains a conflicting type, then flag an
832 /// error. This returns true if any information was updated.
833 ///
834 bool UpdateNodeType(unsigned ResNo, const TypeSetByHwMode &InTy,
835 TreePattern &TP);
836 bool UpdateNodeType(unsigned ResNo, MVT InTy, TreePattern &TP);
837 bool UpdateNodeType(unsigned ResNo, const ValueTypeByHwMode &InTy,
838 TreePattern &TP);
839
840 // Update node type with types inferred from an instruction operand or result
841 // def from the ins/outs lists.
842 // Return true if the type changed.
843 bool UpdateNodeTypeFromInst(unsigned ResNo, const Record *Operand,
844 TreePattern &TP);
845
846 /// ContainsUnresolvedType - Return true if this tree contains any
847 /// unresolved types.
848 bool ContainsUnresolvedType(TreePattern &TP) const;
849
850 /// canPatternMatch - If it is impossible for this pattern to match on this
851 /// target, fill in Reason and return false. Otherwise, return true.
852 bool canPatternMatch(std::string &Reason,
853 const CodeGenDAGPatterns &CDP) const;
854};
855
856inline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) {
857 TPN.print(OS);
858 return OS;
859}
860
861/// TreePattern - Represent a pattern, used for instructions, pattern
862/// fragments, etc.
863///
864class TreePattern {
865 /// Trees - The list of pattern trees which corresponds to this pattern.
866 /// Note that PatFrag's only have a single tree.
867 ///
868 std::vector<TreePatternNodePtr> Trees;
869
870 /// NamedNodes - This is all of the nodes that have names in the trees in this
871 /// pattern.
872 StringMap<SmallVector<TreePatternNode *, 1>> NamedNodes;
873
874 /// TheRecord - The actual TableGen record corresponding to this pattern.
875 ///
876 const Record *TheRecord;
877
878 /// Args - This is a list of all of the arguments to this pattern (for
879 /// PatFrag patterns), which are the 'node' markers in this pattern.
880 std::vector<std::string> Args;
881
882 /// CDP - the top-level object coordinating this madness.
883 ///
884 CodeGenDAGPatterns &CDP;
885
886 /// isInputPattern - True if this is an input pattern, something to match.
887 /// False if this is an output pattern, something to emit.
888 bool isInputPattern;
889
890 /// hasError - True if the currently processed nodes have unresolvable types
891 /// or other non-fatal errors
892 bool HasError;
893
894 /// It's important that the usage of operands in ComplexPatterns is
895 /// consistent: each named operand can be defined by at most one
896 /// ComplexPattern. This records the ComplexPattern instance and the operand
897 /// number for each operand encountered in a ComplexPattern to aid in that
898 /// check.
899 StringMap<std::pair<const Record *, unsigned>> ComplexPatternOperands;
900
901 TypeInfer Infer;
902
903public:
904 /// TreePattern constructor - Parse the specified DagInits into the
905 /// current record.
906 TreePattern(const Record *TheRec, const ListInit *RawPat, bool isInput,
907 CodeGenDAGPatterns &ise);
908 TreePattern(const Record *TheRec, const DagInit *Pat, bool isInput,
909 CodeGenDAGPatterns &ise);
910 TreePattern(const Record *TheRec, ArrayRef<const Init *> Args,
911 ArrayRef<const StringInit *> ArgNames, bool isInput,
912 CodeGenDAGPatterns &ise);
913 TreePattern(const Record *TheRec, TreePatternNodePtr Pat, bool isInput,
914 CodeGenDAGPatterns &ise);
915
916 /// getTrees - Return the tree patterns which corresponds to this pattern.
917 ///
918 const std::vector<TreePatternNodePtr> &getTrees() const { return Trees; }
919 unsigned getNumTrees() const { return Trees.size(); }
920 const TreePatternNodePtr &getTree(unsigned i) const { return Trees[i]; }
921 const TreePatternNodePtr &getOnlyTree() const {
922 assert(Trees.size() == 1 && "Doesn't have exactly one pattern!");
923 return Trees[0];
924 }
925
926 const StringMap<SmallVector<TreePatternNode *, 1>> &getNamedNodesMap() {
927 if (NamedNodes.empty())
928 ComputeNamedNodes();
929 return NamedNodes;
930 }
931
932 /// getRecord - Return the actual TableGen record corresponding to this
933 /// pattern.
934 ///
935 const Record *getRecord() const { return TheRecord; }
936
937 unsigned getNumArgs() const { return Args.size(); }
938 const std::string &getArgName(unsigned i) const {
939 assert(i < Args.size() && "Argument reference out of range!");
940 return Args[i];
941 }
942 std::vector<std::string> &getArgList() { return Args; }
943
944 CodeGenDAGPatterns &getDAGPatterns() const { return CDP; }
945
946 /// InlinePatternFragments - If this pattern refers to any pattern
947 /// fragments, inline them into place, giving us a pattern without any
948 /// PatFrags references. This may increase the number of trees in the
949 /// pattern if a PatFrags has multiple alternatives.
950 void InlinePatternFragments() {
951 std::vector<TreePatternNodePtr> Copy;
952 Trees.swap(x&: Copy);
953 for (const TreePatternNodePtr &C : Copy)
954 C->InlinePatternFragments(TP&: *this, OutAlternatives&: Trees);
955 }
956
957 /// InferAllTypes - Infer/propagate as many types throughout the expression
958 /// patterns as possible. Return true if all types are inferred, false
959 /// otherwise. Bail out if a type contradiction is found.
960 bool InferAllTypes(
961 const StringMap<SmallVector<TreePatternNode *, 1>> *NamedTypes = nullptr);
962
963 /// error - If this is the first error in the current resolution step,
964 /// print it and set the error flag. Otherwise, continue silently.
965 void error(const Twine &Msg);
966 bool hasError() const { return HasError; }
967 void resetError() { HasError = false; }
968
969 TypeInfer &getInfer() { return Infer; }
970
971 void print(raw_ostream &OS) const;
972 void dump() const;
973
974private:
975 TreePatternNodePtr ParseTreePattern(const Init *DI, StringRef OpName);
976 TreePatternNodePtr
977 ParseRootlessTreePattern(ArrayRef<const Init *> Args,
978 ArrayRef<const StringInit *> ArgNames);
979 void ComputeNamedNodes();
980 void ComputeNamedNodes(TreePatternNode &N);
981};
982
983inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
984 const TypeSetByHwMode &InTy,
985 TreePattern &TP) {
986 TypeSetByHwMode VTS(InTy);
987 TP.getInfer().expandOverloads(VTS);
988 return TP.getInfer().MergeInTypeInfo(Out&: Types[ResNo], In: VTS);
989}
990
991inline bool TreePatternNode::UpdateNodeType(unsigned ResNo, MVT InTy,
992 TreePattern &TP) {
993 TypeSetByHwMode VTS(InTy);
994 TP.getInfer().expandOverloads(VTS);
995 return TP.getInfer().MergeInTypeInfo(Out&: Types[ResNo], In: VTS);
996}
997
998inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
999 const ValueTypeByHwMode &InTy,
1000 TreePattern &TP) {
1001 TypeSetByHwMode VTS(InTy);
1002 TP.getInfer().expandOverloads(VTS);
1003 return TP.getInfer().MergeInTypeInfo(Out&: Types[ResNo], In: VTS);
1004}
1005
1006/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps
1007/// that has a set ExecuteAlways / DefaultOps field.
1008struct DAGDefaultOperand {
1009 std::vector<TreePatternNodePtr> DefaultOps;
1010};
1011
1012class DAGInstruction {
1013 std::vector<const Record *> Results;
1014 std::vector<const Record *> Operands;
1015 std::vector<const Record *> ImpResults;
1016 TreePatternNodePtr SrcPattern;
1017 TreePatternNodePtr ResultPattern;
1018
1019public:
1020 DAGInstruction(std::vector<const Record *> &&Results,
1021 std::vector<const Record *> &&Operands,
1022 std::vector<const Record *> &&ImpResults,
1023 TreePatternNodePtr SrcPattern = nullptr,
1024 TreePatternNodePtr ResultPattern = nullptr)
1025 : Results(std::move(Results)), Operands(std::move(Operands)),
1026 ImpResults(std::move(ImpResults)), SrcPattern(SrcPattern),
1027 ResultPattern(ResultPattern) {}
1028
1029 unsigned getNumResults() const { return Results.size(); }
1030 unsigned getNumOperands() const { return Operands.size(); }
1031 unsigned getNumImpResults() const { return ImpResults.size(); }
1032 ArrayRef<const Record *> getImpResults() const { return ImpResults; }
1033
1034 const Record *getResult(unsigned RN) const {
1035 assert(RN < Results.size());
1036 return Results[RN];
1037 }
1038
1039 const Record *getOperand(unsigned ON) const {
1040 assert(ON < Operands.size());
1041 return Operands[ON];
1042 }
1043
1044 const Record *getImpResult(unsigned RN) const {
1045 assert(RN < ImpResults.size());
1046 return ImpResults[RN];
1047 }
1048
1049 TreePatternNodePtr getSrcPattern() const { return SrcPattern; }
1050 TreePatternNodePtr getResultPattern() const { return ResultPattern; }
1051};
1052
1053/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns
1054/// processed to produce isel.
1055class PatternToMatch {
1056 const Record *SrcRecord; // Originating Record for the pattern.
1057 const ListInit *Predicates; // Top level predicate conditions to match.
1058 TreePatternNodePtr SrcPattern; // Source pattern to match.
1059 TreePatternNodePtr DstPattern; // Resulting pattern.
1060 std::vector<const Record *> Dstregs; // Physical register defs being matched.
1061 std::string HwModeFeatures;
1062 int AddedComplexity; // Add to matching pattern complexity.
1063 bool GISelShouldIgnore; // Should GlobalISel ignore importing this pattern.
1064 unsigned ID; // Unique ID for the record.
1065
1066public:
1067 PatternToMatch(const Record *srcrecord, const ListInit *preds,
1068 TreePatternNodePtr src, TreePatternNodePtr dst,
1069 ArrayRef<const Record *> dstregs, int complexity, unsigned uid,
1070 bool ignore, const Twine &hwmodefeatures = "")
1071 : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src),
1072 DstPattern(dst), Dstregs(dstregs), HwModeFeatures(hwmodefeatures.str()),
1073 AddedComplexity(complexity), GISelShouldIgnore(ignore), ID(uid) {}
1074
1075 const Record *getSrcRecord() const { return SrcRecord; }
1076 const ListInit *getPredicates() const { return Predicates; }
1077 TreePatternNode &getSrcPattern() const { return *SrcPattern; }
1078 TreePatternNodePtr getSrcPatternShared() const { return SrcPattern; }
1079 TreePatternNode &getDstPattern() const { return *DstPattern; }
1080 TreePatternNodePtr getDstPatternShared() const { return DstPattern; }
1081 ArrayRef<const Record *> getDstRegs() const { return Dstregs; }
1082 StringRef getHwModeFeatures() const { return HwModeFeatures; }
1083 int getAddedComplexity() const { return AddedComplexity; }
1084 bool getGISelShouldIgnore() const { return GISelShouldIgnore; }
1085 unsigned getID() const { return ID; }
1086
1087 std::string getPredicateCheck() const;
1088 void
1089 getPredicateRecords(SmallVectorImpl<const Record *> &PredicateRecs) const;
1090
1091 /// Compute the complexity metric for the input pattern. This roughly
1092 /// corresponds to the number of nodes that are covered.
1093 int getPatternComplexity(const CodeGenDAGPatterns &CGP) const;
1094};
1095
1096class CodeGenDAGPatterns {
1097public:
1098 using NodeXForm = std::pair<const Record *, std::string>;
1099
1100private:
1101 const RecordKeeper &Records;
1102 CodeGenTarget Target;
1103 CodeGenIntrinsicTable Intrinsics;
1104
1105 std::map<const Record *, SDNodeInfo, LessRecordByID> SDNodes;
1106
1107 std::map<const Record *, NodeXForm, LessRecordByID> SDNodeXForms;
1108 std::map<const Record *, ComplexPattern, LessRecordByID> ComplexPatterns;
1109 std::map<const Record *, std::unique_ptr<TreePattern>, LessRecordByID>
1110 PatternFragments;
1111 std::map<const Record *, DAGDefaultOperand, LessRecordByID> DefaultOperands;
1112 std::map<const Record *, DAGInstruction, LessRecordByID> Instructions;
1113
1114 // Specific SDNode definitions:
1115 const Record *intrinsic_void_sdnode;
1116 const Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode;
1117
1118 /// PatternsToMatch - All of the things we are matching on the DAG. The first
1119 /// value is the pattern to match, the second pattern is the result to
1120 /// emit.
1121 std::vector<PatternToMatch> PatternsToMatch;
1122
1123 TypeSetByHwMode LegalVTS;
1124 TypeSetByHwMode LegalPtrVTS;
1125
1126 unsigned NumScopes = 0;
1127
1128public:
1129 CodeGenDAGPatterns(const RecordKeeper &R, bool ExpandHwMode = true);
1130
1131 CodeGenTarget &getTargetInfo() { return Target; }
1132 const CodeGenTarget &getTargetInfo() const { return Target; }
1133 const TypeSetByHwMode &getLegalTypes() const { return LegalVTS; }
1134 const TypeSetByHwMode &getLegalPtrTypes() const { return LegalPtrVTS; }
1135
1136 const Record *getSDNodeNamed(StringRef Name) const;
1137
1138 const SDNodeInfo &getSDNodeInfo(const Record *R) const {
1139 auto F = SDNodes.find(x: R);
1140 assert(F != SDNodes.end() && "Unknown node!");
1141 return F->second;
1142 }
1143
1144 // Node transformation lookups.
1145 const NodeXForm &getSDNodeTransform(const Record *R) const {
1146 auto F = SDNodeXForms.find(x: R);
1147 assert(F != SDNodeXForms.end() && "Invalid transform!");
1148 return F->second;
1149 }
1150
1151 const ComplexPattern &getComplexPattern(const Record *R) const {
1152 auto F = ComplexPatterns.find(x: R);
1153 assert(F != ComplexPatterns.end() && "Unknown addressing mode!");
1154 return F->second;
1155 }
1156
1157 const CodeGenIntrinsic &getIntrinsic(const Record *R) const {
1158 for (const CodeGenIntrinsic &Intrinsic : Intrinsics)
1159 if (Intrinsic.TheDef == R)
1160 return Intrinsic;
1161 llvm_unreachable("Unknown intrinsic!");
1162 }
1163
1164 const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const {
1165 if (IID - 1 < Intrinsics.size())
1166 return Intrinsics[IID - 1];
1167 llvm_unreachable("Bad intrinsic ID!");
1168 }
1169
1170 unsigned getIntrinsicID(const Record *R) const {
1171 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
1172 if (Intrinsics[i].TheDef == R)
1173 return i;
1174 llvm_unreachable("Unknown intrinsic!");
1175 }
1176
1177 const DAGDefaultOperand &getDefaultOperand(const Record *R) const {
1178 auto F = DefaultOperands.find(x: R);
1179 assert(F != DefaultOperands.end() && "Isn't an analyzed default operand!");
1180 return F->second;
1181 }
1182
1183 // Pattern Fragment information.
1184 TreePattern *getPatternFragment(const Record *R) const {
1185 auto F = PatternFragments.find(x: R);
1186 assert(F != PatternFragments.end() && "Invalid pattern fragment request!");
1187 return F->second.get();
1188 }
1189 TreePattern *getPatternFragmentIfRead(const Record *R) const {
1190 auto F = PatternFragments.find(x: R);
1191 if (F == PatternFragments.end())
1192 return nullptr;
1193 return F->second.get();
1194 }
1195
1196 using pf_iterator = decltype(PatternFragments)::const_iterator;
1197 pf_iterator pf_begin() const { return PatternFragments.begin(); }
1198 pf_iterator pf_end() const { return PatternFragments.end(); }
1199 iterator_range<pf_iterator> ptfs() const { return PatternFragments; }
1200
1201 // Patterns to match information.
1202 using ptm_iterator = std::vector<PatternToMatch>::const_iterator;
1203 ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); }
1204 ptm_iterator ptm_end() const { return PatternsToMatch.end(); }
1205 iterator_range<ptm_iterator> ptms() const { return PatternsToMatch; }
1206
1207 /// Parse the Pattern for an instruction, and insert the result in DAGInsts.
1208 using DAGInstMap = std::map<const Record *, DAGInstruction, LessRecordByID>;
1209 void parseInstructionPattern(const CodeGenInstruction &CGI,
1210 const ListInit *Pattern, DAGInstMap &DAGInsts);
1211
1212 const DAGInstruction &getInstruction(const Record *R) const {
1213 auto F = Instructions.find(x: R);
1214 assert(F != Instructions.end() && "Unknown instruction!");
1215 return F->second;
1216 }
1217
1218 const Record *get_intrinsic_void_sdnode() const {
1219 return intrinsic_void_sdnode;
1220 }
1221 const Record *get_intrinsic_w_chain_sdnode() const {
1222 return intrinsic_w_chain_sdnode;
1223 }
1224 const Record *get_intrinsic_wo_chain_sdnode() const {
1225 return intrinsic_wo_chain_sdnode;
1226 }
1227
1228 unsigned allocateScope() { return ++NumScopes; }
1229
1230 bool operandHasDefault(const Record *Op) const {
1231 return Op->isSubClassOf(Name: "OperandWithDefaultOps") &&
1232 !getDefaultOperand(R: Op).DefaultOps.empty();
1233 }
1234
1235private:
1236 TypeSetByHwMode ComputeLegalPtrTypes() const;
1237 void ParseNodeInfo();
1238 void ParseNodeTransforms();
1239 void ParseComplexPatterns();
1240 void ParsePatternFragments(bool OutFrags = false);
1241 void ParseDefaultOperands();
1242 void ParseInstructions();
1243 void ParsePatterns();
1244 void ExpandHwModeBasedTypes();
1245 void InferInstructionFlags();
1246 void GenerateVariants();
1247 void VerifyInstructionFlags();
1248
1249 void ParseOnePattern(const Record *TheDef, TreePattern &Pattern,
1250 TreePattern &Result,
1251 ArrayRef<const Record *> InstImpResults,
1252 bool ShouldIgnore = false);
1253 void AddPatternToMatch(TreePattern *Pattern, PatternToMatch &&PTM);
1254
1255 using InstInputsTy = std::map<StringRef, TreePatternNodePtr>;
1256 using InstResultsTy =
1257 MapVector<StringRef, TreePatternNodePtr, std::map<StringRef, unsigned>>;
1258 void FindPatternInputsAndOutputs(TreePattern &I, TreePatternNodePtr Pat,
1259 InstInputsTy &InstInputs,
1260 InstResultsTy &InstResults,
1261 std::vector<const Record *> &InstImpResults);
1262 unsigned getNewUID();
1263};
1264
1265inline bool SDNodeInfo::ApplyTypeConstraints(TreePatternNode &N,
1266 TreePattern &TP) const {
1267 bool MadeChange = false;
1268 for (const SDTypeConstraint &TypeConstraint : TypeConstraints)
1269 MadeChange |= TypeConstraint.ApplyTypeConstraint(N, NodeInfo: *this, TP);
1270 return MadeChange;
1271}
1272
1273} // end namespace llvm
1274
1275#endif // LLVM_UTILS_TABLEGEN_COMMON_CODEGENDAGPATTERNS_H
1276