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