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