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