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