1fe71893183f504feff290e343bf740bd32432129Chris Lattner//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===// 26cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// 36cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// The LLVM Compiler Infrastructure 46cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// 56cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// This file is distributed under the University of Illinois Open Source 66cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// License. See LICENSE.TXT for details. 76cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// 86cefb77a7073057fecd721ae141140d75ce76512Chris Lattner//===----------------------------------------------------------------------===// 96cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// 10fe71893183f504feff290e343bf740bd32432129Chris Lattner// This file declares the CodeGenDAGPatterns class, which is used to read and 116cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// represent the patterns present in a .td file for instructions. 126cefb77a7073057fecd721ae141140d75ce76512Chris Lattner// 136cefb77a7073057fecd721ae141140d75ce76512Chris Lattner//===----------------------------------------------------------------------===// 146cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 156cefb77a7073057fecd721ae141140d75ce76512Chris Lattner#ifndef CODEGEN_DAGPATTERNS_H 166cefb77a7073057fecd721ae141140d75ce76512Chris Lattner#define CODEGEN_DAGPATTERNS_H 176cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 186cefb77a7073057fecd721ae141140d75ce76512Chris Lattner#include "CodeGenTarget.h" 196cefb77a7073057fecd721ae141140d75ce76512Chris Lattner#include "CodeGenIntrinsics.h" 202cacec55f947c716b058a39038889550d7e39b3cChris Lattner#include "llvm/ADT/SmallVector.h" 212cacec55f947c716b058a39038889550d7e39b3cChris Lattner#include "llvm/ADT/StringMap.h" 22655b8de7b2ab773a977e0c524307e71354d8af29Craig Topper#include "llvm/Support/ErrorHandling.h" 23e14d2e210dc7fe28009f44818a057622a73322e4Chris Lattner#include <set> 24e14d2e210dc7fe28009f44818a057622a73322e4Chris Lattner#include <algorithm> 25e14d2e210dc7fe28009f44818a057622a73322e4Chris Lattner#include <vector> 26e14d2e210dc7fe28009f44818a057622a73322e4Chris Lattner#include <map> 276cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 286cefb77a7073057fecd721ae141140d75ce76512Chris Lattnernamespace llvm { 296cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class Record; 30afd54269ab9951c0dcdea076c4d6f48a345e9d27David Greene class Init; 316cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class ListInit; 326cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class DagInit; 336cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class SDNodeInfo; 346cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class TreePattern; 356cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class TreePatternNode; 36fe71893183f504feff290e343bf740bd32432129Chris Lattner class CodeGenDAGPatterns; 376cefb77a7073057fecd721ae141140d75ce76512Chris Lattner class ComplexPattern; 386cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 39e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson/// EEVT::DAGISelGenValueType - These are some extended forms of 40825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson/// MVT::SimpleValueType that we use as lattice values during type inference. 41cdfa01bf0fd4fd9228e8cf32eae9205d067e147aBob Wilson/// The existing MVT iAny, fAny and vAny types suffice to represent 42cdfa01bf0fd4fd9228e8cf32eae9205d067e147aBob Wilson/// arbitrary integer, floating-point, and vector types, so only an unknown 43cdfa01bf0fd4fd9228e8cf32eae9205d067e147aBob Wilson/// value is needed. 44e50ed30282bb5b4a9ed952580523f2dda16215acOwen Andersonnamespace EEVT { 452cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// TypeSet - This is either empty if it's completely unknown, or holds a set 462cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// of types. It is used during type inference because register classes can 472cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// have multiple possible types and we don't know which one they get until 482cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// type inference is complete. 492cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// 502cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// TypeSet can have three states: 512cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// Vector is empty: The type is completely unknown, it can be any valid 522cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// target type. 532cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// Vector has multiple constrained types: (e.g. v4i32 + v4f32) it is one 542cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// of those types only. 552cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// Vector has one concrete type: The type is completely known. 562cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// 572cacec55f947c716b058a39038889550d7e39b3cChris Lattner class TypeSet { 58774ce29399364823dba62217ebf7bc8701005140Chris Lattner SmallVector<MVT::SimpleValueType, 4> TypeVec; 592cacec55f947c716b058a39038889550d7e39b3cChris Lattner public: 602cacec55f947c716b058a39038889550d7e39b3cChris Lattner TypeSet() {} 612cacec55f947c716b058a39038889550d7e39b3cChris Lattner TypeSet(MVT::SimpleValueType VT, TreePattern &TP); 62398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach TypeSet(const std::vector<MVT::SimpleValueType> &VTList); 63398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 642cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool isCompletelyUnknown() const { return TypeVec.empty(); } 65398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 662cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool isConcrete() const { 672cacec55f947c716b058a39038889550d7e39b3cChris Lattner if (TypeVec.size() != 1) return false; 682cacec55f947c716b058a39038889550d7e39b3cChris Lattner unsigned char T = TypeVec[0]; (void)T; 692cacec55f947c716b058a39038889550d7e39b3cChris Lattner assert(T < MVT::LAST_VALUETYPE || T == MVT::iPTR || T == MVT::iPTRAny); 702cacec55f947c716b058a39038889550d7e39b3cChris Lattner return true; 712cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 72398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 732cacec55f947c716b058a39038889550d7e39b3cChris Lattner MVT::SimpleValueType getConcrete() const { 742cacec55f947c716b058a39038889550d7e39b3cChris Lattner assert(isConcrete() && "Type isn't concrete yet"); 752cacec55f947c716b058a39038889550d7e39b3cChris Lattner return (MVT::SimpleValueType)TypeVec[0]; 762cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 77398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 782cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool isDynamicallyResolved() const { 792cacec55f947c716b058a39038889550d7e39b3cChris Lattner return getConcrete() == MVT::iPTR || getConcrete() == MVT::iPTRAny; 802cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 81398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 822cacec55f947c716b058a39038889550d7e39b3cChris Lattner const SmallVectorImpl<MVT::SimpleValueType> &getTypeList() const { 832cacec55f947c716b058a39038889550d7e39b3cChris Lattner assert(!TypeVec.empty() && "Not a type list!"); 842cacec55f947c716b058a39038889550d7e39b3cChris Lattner return TypeVec; 852cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 86398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 876c6ba364931acb113973ad3e6d69736969c59299Chris Lattner bool isVoid() const { 886c6ba364931acb113973ad3e6d69736969c59299Chris Lattner return TypeVec.size() == 1 && TypeVec[0] == MVT::isVoid; 896c6ba364931acb113973ad3e6d69736969c59299Chris Lattner } 90398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 912cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// hasIntegerTypes - Return true if this TypeSet contains any integer value 922cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// types. 932cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool hasIntegerTypes() const; 94398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 952cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or 962cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// a floating point value type. 972cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool hasFloatingPointTypes() const; 98398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 992cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// hasVectorTypes - Return true if this TypeSet contains a vector value 1002cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// type. 1012cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool hasVectorTypes() const; 102398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1032cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// getName() - Return this TypeSet as a string. 1042cacec55f947c716b058a39038889550d7e39b3cChris Lattner std::string getName() const; 105398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1062cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// MergeInTypeInfo - This merges in type information from the specified 1072cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// argument. If 'this' changes, it returns true. If the two types are 1082cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// contradictory (e.g. merge f32 into i32) then this throws an exception. 1092cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP); 1102cacec55f947c716b058a39038889550d7e39b3cChris Lattner 1112cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool MergeInTypeInfo(MVT::SimpleValueType InVT, TreePattern &TP) { 1122cacec55f947c716b058a39038889550d7e39b3cChris Lattner return MergeInTypeInfo(EEVT::TypeSet(InVT, TP), TP); 1132cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 1142cacec55f947c716b058a39038889550d7e39b3cChris Lattner 1152cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// Force this type list to only contain integer types. 1162cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool EnforceInteger(TreePattern &TP); 1172cacec55f947c716b058a39038889550d7e39b3cChris Lattner 1182cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// Force this type list to only contain floating point types. 1192cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool EnforceFloatingPoint(TreePattern &TP); 12083ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands 1212cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// EnforceScalar - Remove all vector types from this type list. 1222cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool EnforceScalar(TreePattern &TP); 1236cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 1242cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// EnforceVector - Remove all non-vector types from this type list. 1252cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool EnforceVector(TreePattern &TP); 12636e3e668be0c4914660575d7cea800b0d51a4116Bob Wilson 1272cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update 1282cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// this an other based on this information. 1292cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP); 130398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1312cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 1322cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// whose element is VT. 13366fb9d26c64b75ad6619608905c4005f0777bf5dChris Lattner bool EnforceVectorEltTypeIs(EEVT::TypeSet &VT, TreePattern &TP); 134398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1356032269837c08a94b70b0e36f8e473c293ff5fd4David Greene /// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to 1366032269837c08a94b70b0e36f8e473c293ff5fd4David Greene /// be a vector type VT. 1376032269837c08a94b70b0e36f8e473c293ff5fd4David Greene bool EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VT, TreePattern &TP); 1386032269837c08a94b70b0e36f8e473c293ff5fd4David Greene 1392cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool operator!=(const TypeSet &RHS) const { return TypeVec != RHS.TypeVec; } 1402cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool operator==(const TypeSet &RHS) const { return TypeVec == RHS.TypeVec; } 141398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1425a9b8fb95c9a4c6fd5e06c1e89fa9263d39cd252Chris Lattner private: 1435a9b8fb95c9a4c6fd5e06c1e89fa9263d39cd252Chris Lattner /// FillWithPossibleTypes - Set to all legal types and return true, only 144774ce29399364823dba62217ebf7bc8701005140Chris Lattner /// valid on completely unknown type sets. If Pred is non-null, only MVTs 145774ce29399364823dba62217ebf7bc8701005140Chris Lattner /// that pass the predicate are added. 146774ce29399364823dba62217ebf7bc8701005140Chris Lattner bool FillWithPossibleTypes(TreePattern &TP, 147774ce29399364823dba62217ebf7bc8701005140Chris Lattner bool (*Pred)(MVT::SimpleValueType) = 0, 148774ce29399364823dba62217ebf7bc8701005140Chris Lattner const char *PredicateName = 0); 1492cacec55f947c716b058a39038889550d7e39b3cChris Lattner }; 1506cefb77a7073057fecd721ae141140d75ce76512Chris Lattner} 1516cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 152327d0651f8c3b1480d8fc1f4d96e07a1452eaa8cScott Michel/// Set type used to track multiply used variables in patterns 153327d0651f8c3b1480d8fc1f4d96e07a1452eaa8cScott Micheltypedef std::set<std::string> MultipleUseVarSet; 154327d0651f8c3b1480d8fc1f4d96e07a1452eaa8cScott Michel 1556cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// SDTypeConstraint - This is a discriminated union of constraints, 1566cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// corresponding to the SDTypeConstraint tablegen class in Target.td. 1576cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerstruct SDTypeConstraint { 1586cefb77a7073057fecd721ae141140d75ce76512Chris Lattner SDTypeConstraint(Record *R); 159398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1606cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned OperandNo; // The operand # this constraint applies to. 161398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach enum { 162398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs, 1636032269837c08a94b70b0e36f8e473c293ff5fd4David Greene SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec, 1646032269837c08a94b70b0e36f8e473c293ff5fd4David Greene SDTCisSubVecOfVec 1656cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } ConstraintType; 166398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 1676cefb77a7073057fecd721ae141140d75ce76512Chris Lattner union { // The discriminated union. 1686cefb77a7073057fecd721ae141140d75ce76512Chris Lattner struct { 1692cacec55f947c716b058a39038889550d7e39b3cChris Lattner MVT::SimpleValueType VT; 1706cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } SDTCisVT_Info; 1716cefb77a7073057fecd721ae141140d75ce76512Chris Lattner struct { 1726cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned OtherOperandNum; 1736cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } SDTCisSameAs_Info; 1746cefb77a7073057fecd721ae141140d75ce76512Chris Lattner struct { 1756cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned OtherOperandNum; 1766cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } SDTCisVTSmallerThanOp_Info; 1776cefb77a7073057fecd721ae141140d75ce76512Chris Lattner struct { 1786cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned BigOperandNum; 1796cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } SDTCisOpSmallerThanOp_Info; 1806cefb77a7073057fecd721ae141140d75ce76512Chris Lattner struct { 1816cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned OtherOperandNum; 182b5af3344c196de5ed3f45b250dfb864be6e9ddc5Nate Begeman } SDTCisEltOfVec_Info; 1836032269837c08a94b70b0e36f8e473c293ff5fd4David Greene struct { 1846032269837c08a94b70b0e36f8e473c293ff5fd4David Greene unsigned OtherOperandNum; 1856032269837c08a94b70b0e36f8e473c293ff5fd4David Greene } SDTCisSubVecOfVec_Info; 1866cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } x; 1876cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 1886cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// ApplyTypeConstraint - Given a node in a pattern, apply this type 1896cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// constraint to the nodes operands. This returns true if it makes a 1906cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// change, false otherwise. If a type contradiction is found, throw an 1916cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// exception. 1926cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, 1936cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePattern &TP) const; 1946cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 1956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 1966cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// SDNodeInfo - One of these records is created for each SDNode instance in 1976cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// the target .td file. This represents the various dag nodes we will be 1986cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// processing. 1996cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerclass SDNodeInfo { 2006cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *Def; 2016cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::string EnumName; 2026cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::string SDClassName; 2036cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned Properties; 2046cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned NumResults; 2056cefb77a7073057fecd721ae141140d75ce76512Chris Lattner int NumOperands; 2066cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<SDTypeConstraint> TypeConstraints; 2076cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerpublic: 2086cefb77a7073057fecd721ae141140d75ce76512Chris Lattner SDNodeInfo(Record *R); // Parse the specified record. 209398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 2106cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumResults() const { return NumResults; } 211398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 2122a22cdc716ea652d6c9ebdaae028b5c75ab2793aChris Lattner /// getNumOperands - This is the number of operands required or -1 if 2132a22cdc716ea652d6c9ebdaae028b5c75ab2793aChris Lattner /// variadic. 2146cefb77a7073057fecd721ae141140d75ce76512Chris Lattner int getNumOperands() const { return NumOperands; } 2156cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getRecord() const { return Def; } 2166cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::string &getEnumName() const { return EnumName; } 2176cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::string &getSDClassName() const { return SDClassName; } 218398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 2196cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<SDTypeConstraint> &getTypeConstraints() const { 2206cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return TypeConstraints; 2216cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 222398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 223225798143dbec36685f9d1e2fa82f5c4e70b0bf5Chris Lattner /// getKnownType - If the type constraints on this node imply a fixed type 224225798143dbec36685f9d1e2fa82f5c4e70b0bf5Chris Lattner /// (e.g. all stores return void, etc), then return it as an 225aac5b5b2e5eaf2e5bd62f9b96270e31d46125f4fChris Lattner /// MVT::SimpleValueType. Otherwise, return MVT::Other. 226084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner MVT::SimpleValueType getKnownType(unsigned ResNo) const; 227398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 2286cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// hasProperty - Return true if this node has the specified property. 2296cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 2306cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } 2316cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 2326cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// ApplyTypeConstraints - Given a node in a pattern, apply the type 2336cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// constraints for this node to the operands of the node. This returns 2346cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// true if it makes a change, false otherwise. If a type contradiction is 2356cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// found, throw an exception. 2366cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const { 2376cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool MadeChange = false; 2386cefb77a7073057fecd721ae141140d75ce76512Chris Lattner for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) 2396cefb77a7073057fecd721ae141140d75ce76512Chris Lattner MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP); 2406cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return MadeChange; 2416cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 2426cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 243543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 244543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner/// TreePredicateFn - This is an abstraction that represents the predicates on 245543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner/// a PatFrag node. This is a simple one-word wrapper around a pointer to 246543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner/// provide nice accessors. 247543790673c747ab2793fc657e239ce5f78419dc0Chris Lattnerclass TreePredicateFn { 248543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// PatFragRec - This is the TreePattern for the PatFrag that we 249543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// originally came from. 250543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner TreePattern *PatFragRec; 251543790673c747ab2793fc657e239ce5f78419dc0Chris Lattnerpublic: 252543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 2537ed1391ff66012e4963081cfb20b6166e8784f50Chris Lattner TreePredicateFn(TreePattern *N); 254543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 255543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 256543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner TreePattern *getOrigPatFragRecord() const { return PatFragRec; } 257543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 258543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// isAlwaysTrue - Return true if this is a noop predicate. 259543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner bool isAlwaysTrue() const; 260543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 2611518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner bool isImmediatePattern() const { return !getImmCode().empty(); } 2621518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner 2631518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner /// getImmediatePredicateCode - Return the code that evaluates this pattern if 2641518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner /// this is an immediate predicate. It is an error to call this on a 2651518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner /// non-immediate pattern. 2661518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner std::string getImmediatePredicateCode() const { 2671518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner std::string Result = getImmCode(); 2681518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner assert(!Result.empty() && "Isn't an immediate pattern!"); 2691518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner return Result; 2701518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner } 2711518afddea6c0a4275a9ac64a9ffe2b6b4c0600aChris Lattner 272543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 273543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner bool operator==(const TreePredicateFn &RHS) const { 274543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner return PatFragRec == RHS.PatFragRec; 275543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner } 276543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 277543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); } 278543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 279543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// Return the name to use in the generated code to reference this, this is 280543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// "Predicate_foo" if from a pattern fragment "foo". 281543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner std::string getFnName() const; 282543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 283543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// getCodeToRunOnSDNode - Return the code for the function body that 284543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// evaluates this predicate. The argument is expected to be in "Node", 285543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// not N. This handles casting and conversion to a concrete node type as 286543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner /// appropriate. 287543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner std::string getCodeToRunOnSDNode() const; 288543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 289543790673c747ab2793fc657e239ce5f78419dc0Chris Lattnerprivate: 290543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner std::string getPredCode() const; 2917ed1391ff66012e4963081cfb20b6166e8784f50Chris Lattner std::string getImmCode() const; 292543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner}; 293543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 2946cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 2956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped 2966cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// patterns), and as such should be ref counted. We currently just leak all 2976cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// TreePatternNode objects! 2986cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerclass TreePatternNode { 299d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner /// The type of each node result. Before and during type inference, each 300d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner /// result may be a set of possible types. After (successful) type inference, 301d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner /// each is a single concrete type. 302d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner SmallVector<EEVT::TypeSet, 1> Types; 303398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3046cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// Operator - The Record for the operator if this is an interior node (not 3056cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// a leaf). 3066cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *Operator; 307398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3086cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf. 3096cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 31005bce0beee87512e52428d4b80f5a8e79a949576David Greene Init *Val; 311398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3126cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// Name - The name given to this node with the :$foo notation. 3136cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 3146cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::string Name; 315398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3160540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman /// PredicateFns - The predicate functions to execute on this node to check 3170540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman /// for a match. If this list is empty, no predicate is involved. 318543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner std::vector<TreePredicateFn> PredicateFns; 319398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3206cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// TransformFn - The transformation function to execute on this node before 3216cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// it can be substituted into the resulting instruction on a pattern match. 3226cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *TransformFn; 323398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3246cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<TreePatternNode*> Children; 3256cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerpublic: 326d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch, 327398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach unsigned NumResults) 328d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner : Operator(Op), Val(0), TransformFn(0), Children(Ch) { 329d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner Types.resize(NumResults); 330d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner } 33105bce0beee87512e52428d4b80f5a8e79a949576David Greene TreePatternNode(Init *val, unsigned NumResults) // leaf ctor 3322cacec55f947c716b058a39038889550d7e39b3cChris Lattner : Operator(0), Val(val), TransformFn(0) { 333d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner Types.resize(NumResults); 3346cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 3356cefb77a7073057fecd721ae141140d75ce76512Chris Lattner ~TreePatternNode(); 336398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3376cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::string &getName() const { return Name; } 338c217305f764447eb65e7bf7f9205c14632885969Chris Lattner void setName(StringRef N) { Name.assign(N.begin(), N.end()); } 339398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3406cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool isLeaf() const { return Val != 0; } 341398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3422cacec55f947c716b058a39038889550d7e39b3cChris Lattner // Type accessors. 343d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner unsigned getNumTypes() const { return Types.size(); } 344d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner MVT::SimpleValueType getType(unsigned ResNo) const { 345d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return Types[ResNo].getConcrete(); 346d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner } 347d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner const SmallVectorImpl<EEVT::TypeSet> &getExtTypes() const { return Types; } 348d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner const EEVT::TypeSet &getExtType(unsigned ResNo) const { return Types[ResNo]; } 349d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner EEVT::TypeSet &getExtType(unsigned ResNo) { return Types[ResNo]; } 350d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner void setType(unsigned ResNo, const EEVT::TypeSet &T) { Types[ResNo] = T; } 351398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 352d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner bool hasTypeSet(unsigned ResNo) const { 353d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return Types[ResNo].isConcrete(); 354d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner } 355d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner bool isTypeCompletelyUnknown(unsigned ResNo) const { 356d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return Types[ResNo].isCompletelyUnknown(); 357d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner } 358d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner bool isTypeDynamicallyResolved(unsigned ResNo) const { 359d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return Types[ResNo].isDynamicallyResolved(); 360d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner } 361398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 36205bce0beee87512e52428d4b80f5a8e79a949576David Greene Init *getLeafValue() const { assert(isLeaf()); return Val; } 3636cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getOperator() const { assert(!isLeaf()); return Operator; } 364398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 3656cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumChildren() const { return Children.size(); } 3666cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *getChild(unsigned N) const { return Children[N]; } 3676cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void setChild(unsigned i, TreePatternNode *N) { 3686cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Children[i] = N; 3696cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 370398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 371e39650a805425ffdbd79692c7d1bad80f7332daeChris Lattner /// hasChild - Return true if N is any of our children. 372e39650a805425ffdbd79692c7d1bad80f7332daeChris Lattner bool hasChild(const TreePatternNode *N) const { 373e39650a805425ffdbd79692c7d1bad80f7332daeChris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 374e39650a805425ffdbd79692c7d1bad80f7332daeChris Lattner if (Children[i] == N) return true; 375e39650a805425ffdbd79692c7d1bad80f7332daeChris Lattner return false; 376e39650a805425ffdbd79692c7d1bad80f7332daeChris Lattner } 377e67bde5bb1959dbd7085981cb0bcf6f7c749f724Chris Lattner 378543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner bool hasAnyPredicate() const { return !PredicateFns.empty(); } 379543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner 380543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner const std::vector<TreePredicateFn> &getPredicateFns() const { 381543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner return PredicateFns; 382543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner } 3830540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman void clearPredicateFns() { PredicateFns.clear(); } 384543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner void setPredicateFns(const std::vector<TreePredicateFn> &Fns) { 3850540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman assert(PredicateFns.empty() && "Overwriting non-empty predicate list!"); 3860540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman PredicateFns = Fns; 3870540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman } 388543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner void addPredicateFn(const TreePredicateFn &Fn) { 389543790673c747ab2793fc657e239ce5f78419dc0Chris Lattner assert(!Fn.isAlwaysTrue() && "Empty predicate string!"); 3900540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) == 3910540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman PredicateFns.end()) 3920540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman PredicateFns.push_back(Fn); 3930540e17788f0d09d784fb9bd9b354e02f1c5e4a4Dan Gohman } 3946cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 3956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getTransformFn() const { return TransformFn; } 3966cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void setTransformFn(Record *Fn) { TransformFn = Fn; } 397398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 398e67bde5bb1959dbd7085981cb0bcf6f7c749f724Chris Lattner /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 399e67bde5bb1959dbd7085981cb0bcf6f7c749f724Chris Lattner /// CodeGenIntrinsic information for it, otherwise return a null pointer. 400e67bde5bb1959dbd7085981cb0bcf6f7c749f724Chris Lattner const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const; 4016bd9567a6a1ba62118cdd258ddc52ea8f82ff511Evan Cheng 40247661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner /// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 40347661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner /// return the ComplexPattern information, otherwise return null. 40447661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner const ComplexPattern * 40547661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const; 40647661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner 40747661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner /// NodeHasProperty - Return true if this node has the specified property. 408751d5aa1eadf041f00acf76f3b641549c8be3998Chris Lattner bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 409398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 41047661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner /// TreeHasProperty - Return true if any node in this tree has the specified 41147661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner /// property. 412751d5aa1eadf041f00acf76f3b641549c8be3998Chris Lattner bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 413398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4146bd9567a6a1ba62118cdd258ddc52ea8f82ff511Evan Cheng /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is 4156bd9567a6a1ba62118cdd258ddc52ea8f82ff511Evan Cheng /// marked isCommutative. 4166bd9567a6a1ba62118cdd258ddc52ea8f82ff511Evan Cheng bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const; 417398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4181a55180238dbcf11113f610aea010447e51f595bDaniel Dunbar void print(raw_ostream &OS) const; 4196cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void dump() const; 420398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4216cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerpublic: // Higher level manipulation routines. 4226cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 4236cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// clone - Return a new copy of this tree. 4246cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 4256cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *clone() const; 42647661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner 42747661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner /// RemoveAllTypes - Recursively strip all the types of this tree. 42847661320363a8bf0bb1401a8c1893755fb77c8f6Chris Lattner void RemoveAllTypes(); 429398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4306cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// isIsomorphicTo - Return true if this node is recursively isomorphic to 4316cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// the specified node. For this comparison, all of the state of the node 4326cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// is considered, except for the assigned name. Nodes with differing names 4336cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// that are otherwise identical are considered isomorphic. 434327d0651f8c3b1480d8fc1f4d96e07a1452eaa8cScott Michel bool isIsomorphicTo(const TreePatternNode *N, 435327d0651f8c3b1480d8fc1f4d96e07a1452eaa8cScott Michel const MultipleUseVarSet &DepVars) const; 436398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4376cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// SubstituteFormalArguments - Replace the formal arguments in this tree 4386cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// with actual values specified by ArgMap. 4396cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void SubstituteFormalArguments(std::map<std::string, 4406cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode*> &ArgMap); 4416cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 4426cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// InlinePatternFragments - If this pattern refers to any pattern 4436cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// fragments, inline them into place, giving us a pattern without any 4446cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// PatFrag references. 4456cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *InlinePatternFragments(TreePattern &TP); 446398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4476c01ca9e29816e36e96112ed541ecf3414a7aad2Bob Wilson /// ApplyTypeConstraints - Apply all of the type constraints relevant to 4486cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// this node and its children in the tree. This returns true if it makes a 4496cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// change, false otherwise. If a type contradiction is found, throw an 4506cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// exception. 4516cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); 452398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4536cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// UpdateNodeType - Set the node type of N to VT if VT contains 4546cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// information. If N already contains a conflicting type, then throw an 4556cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// exception. This returns true if any information was updated. 4566cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 457d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner bool UpdateNodeType(unsigned ResNo, const EEVT::TypeSet &InTy, 458d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner TreePattern &TP) { 459d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return Types[ResNo].MergeInTypeInfo(InTy, TP); 4602cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 4612cacec55f947c716b058a39038889550d7e39b3cChris Lattner 462d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy, 463d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner TreePattern &TP) { 464d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return Types[ResNo].MergeInTypeInfo(EEVT::TypeSet(InTy, TP), TP); 4656cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 466398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4676cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// ContainsUnresolvedType - Return true if this tree contains any 4686cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// unresolved types. 4696cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool ContainsUnresolvedType() const { 470d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner for (unsigned i = 0, e = Types.size(); i != e; ++i) 471d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner if (!Types[i].isConcrete()) return true; 472398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4736cefb77a7073057fecd721ae141140d75ce76512Chris Lattner for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 4746cefb77a7073057fecd721ae141140d75ce76512Chris Lattner if (getChild(i)->ContainsUnresolvedType()) return true; 4756cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return false; 4766cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 477398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4786cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// canPatternMatch - If it is impossible for this pattern to match on this 4796cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// target, fill in Reason and return false. Otherwise, return true. 480ee4fa1977dd3a495a8857eef924ee5961db765c6Dan Gohman bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP); 4816cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 4826cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 483383fed9c7aa3b09195bcc2f5f2635ff8bc7819e3Chris Lattnerinline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) { 484383fed9c7aa3b09195bcc2f5f2635ff8bc7819e3Chris Lattner TPN.print(OS); 485383fed9c7aa3b09195bcc2f5f2635ff8bc7819e3Chris Lattner return OS; 486383fed9c7aa3b09195bcc2f5f2635ff8bc7819e3Chris Lattner} 487398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4886cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 4896cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// TreePattern - Represent a pattern, used for instructions, pattern 4906cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// fragments, etc. 4916cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// 4926cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerclass TreePattern { 4936cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// Trees - The list of pattern trees which corresponds to this pattern. 4946cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// Note that PatFrag's only have a single tree. 4956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 4966cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<TreePatternNode*> Trees; 497398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 4982cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// NamedNodes - This is all of the nodes that have names in the trees in this 4992cacec55f947c716b058a39038889550d7e39b3cChris Lattner /// pattern. 5002cacec55f947c716b058a39038889550d7e39b3cChris Lattner StringMap<SmallVector<TreePatternNode*,1> > NamedNodes; 501398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5026cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// TheRecord - The actual TableGen record corresponding to this pattern. 5036cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 5046cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *TheRecord; 505398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5066cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// Args - This is a list of all of the arguments to this pattern (for 5076cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// PatFrag patterns), which are the 'node' markers in this pattern. 5086cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<std::string> Args; 509398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5106cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// CDP - the top-level object coordinating this madness. 5116cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 512fe71893183f504feff290e343bf740bd32432129Chris Lattner CodeGenDAGPatterns &CDP; 5136cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 5146cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// isInputPattern - True if this is an input pattern, something to match. 5156cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// False if this is an output pattern, something to emit. 5166cefb77a7073057fecd721ae141140d75ce76512Chris Lattner bool isInputPattern; 5176cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerpublic: 518398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5196cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// TreePattern constructor - Parse the specified DagInits into the 5206cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// current record. 52105bce0beee87512e52428d4b80f5a8e79a949576David Greene TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 522fe71893183f504feff290e343bf740bd32432129Chris Lattner CodeGenDAGPatterns &ise); 52305bce0beee87512e52428d4b80f5a8e79a949576David Greene TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 524fe71893183f504feff290e343bf740bd32432129Chris Lattner CodeGenDAGPatterns &ise); 5256cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 526fe71893183f504feff290e343bf740bd32432129Chris Lattner CodeGenDAGPatterns &ise); 527398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5286cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// getTrees - Return the tree patterns which corresponds to this pattern. 5296cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 5306cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<TreePatternNode*> &getTrees() const { return Trees; } 5316cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumTrees() const { return Trees.size(); } 5326cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *getTree(unsigned i) const { return Trees[i]; } 5336cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *getOnlyTree() const { 5346cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); 5356cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return Trees[0]; 5366cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 537398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5382cacec55f947c716b058a39038889550d7e39b3cChris Lattner const StringMap<SmallVector<TreePatternNode*,1> > &getNamedNodesMap() { 5392cacec55f947c716b058a39038889550d7e39b3cChris Lattner if (NamedNodes.empty()) 5402cacec55f947c716b058a39038889550d7e39b3cChris Lattner ComputeNamedNodes(); 5412cacec55f947c716b058a39038889550d7e39b3cChris Lattner return NamedNodes; 5422cacec55f947c716b058a39038889550d7e39b3cChris Lattner } 543398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5446cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// getRecord - Return the actual TableGen record corresponding to this 5456cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// pattern. 5466cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// 5476cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getRecord() const { return TheRecord; } 548398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5496cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumArgs() const { return Args.size(); } 5506cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::string &getArgName(unsigned i) const { 5516cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(i < Args.size() && "Argument reference out of range!"); 5526cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return Args[i]; 5536cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 5546cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<std::string> &getArgList() { return Args; } 555398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 556fe71893183f504feff290e343bf740bd32432129Chris Lattner CodeGenDAGPatterns &getDAGPatterns() const { return CDP; } 5576cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 5586cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// InlinePatternFragments - If this pattern refers to any pattern 5596cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// fragments, inline them into place, giving us a pattern without any 5606cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// PatFrag references. 5616cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void InlinePatternFragments() { 5626cefb77a7073057fecd721ae141140d75ce76512Chris Lattner for (unsigned i = 0, e = Trees.size(); i != e; ++i) 5636cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Trees[i] = Trees[i]->InlinePatternFragments(*this); 5646cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 565398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5666cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// InferAllTypes - Infer/propagate as many types throughout the expression 567da4231f134989af7dc6bd3408821ba573def27b2Jim Grosbach /// patterns as possible. Return true if all types are inferred, false 5686cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// otherwise. Throw an exception if a type contradiction is found. 5692cacec55f947c716b058a39038889550d7e39b3cChris Lattner bool InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > 5702cacec55f947c716b058a39038889550d7e39b3cChris Lattner *NamedTypes=0); 571398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5726cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// error - Throw an exception, prefixing it with information about this 5736cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// pattern. 5746cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void error(const std::string &Msg) const; 575398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5761a55180238dbcf11113f610aea010447e51f595bDaniel Dunbar void print(raw_ostream &OS) const; 5776cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void dump() const; 578398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 5796cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerprivate: 58005bce0beee87512e52428d4b80f5a8e79a949576David Greene TreePatternNode *ParseTreePattern(Init *DI, StringRef OpName); 5812cacec55f947c716b058a39038889550d7e39b3cChris Lattner void ComputeNamedNodes(); 5822cacec55f947c716b058a39038889550d7e39b3cChris Lattner void ComputeNamedNodes(TreePatternNode *N); 5836cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 5846cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 5856d3d7656539188b496089a3313ed4d13759adba3Tom Stellard/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps 5866d3d7656539188b496089a3313ed4d13759adba3Tom Stellard/// that has a set ExecuteAlways / DefaultOps field. 5876cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerstruct DAGDefaultOperand { 5886cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<TreePatternNode*> DefaultOps; 5896cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 5906cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 5916cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerclass DAGInstruction { 5926cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePattern *Pattern; 5936cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<Record*> Results; 5946cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<Record*> Operands; 5956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<Record*> ImpResults; 5966cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *ResultPattern; 5976cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerpublic: 5986cefb77a7073057fecd721ae141140d75ce76512Chris Lattner DAGInstruction(TreePattern *TP, 5996cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<Record*> &results, 6006cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<Record*> &operands, 60162bcec82b2762d5cdc84fe39c7d634c784ed6673Chris Lattner const std::vector<Record*> &impresults) 602398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach : Pattern(TP), Results(results), Operands(operands), 60362bcec82b2762d5cdc84fe39c7d634c784ed6673Chris Lattner ImpResults(impresults), ResultPattern(0) {} 6046cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 605f1ab4f18aad3950d0b9ff1273a276bb8d195d2d6Chris Lattner const TreePattern *getPattern() const { return Pattern; } 6066cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumResults() const { return Results.size(); } 6076cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 6086cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getNumImpResults() const { return ImpResults.size(); } 6096cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<Record*>& getImpResults() const { return ImpResults; } 610398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6116cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void setResultPattern(TreePatternNode *R) { ResultPattern = R; } 612398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6136cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getResult(unsigned RN) const { 6146cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(RN < Results.size()); 6156cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return Results[RN]; 6166cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 617398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6186cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getOperand(unsigned ON) const { 6196cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(ON < Operands.size()); 6206cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return Operands[ON]; 6216cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 6226cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 6236cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getImpResult(unsigned RN) const { 6246cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(RN < ImpResults.size()); 6256cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return ImpResults[RN]; 6266cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 627398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6286cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *getResultPattern() const { return ResultPattern; } 6296cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 630398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 631fe71893183f504feff290e343bf740bd32432129Chris Lattner/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns 6326cefb77a7073057fecd721ae141140d75ce76512Chris Lattner/// processed to produce isel. 633b49985a8499e18675db7e9baf920d6ef4e2b65cfChris Lattnerclass PatternToMatch { 634b49985a8499e18675db7e9baf920d6ef4e2b65cfChris Lattnerpublic: 63505bce0beee87512e52428d4b80f5a8e79a949576David Greene PatternToMatch(Record *srcrecord, ListInit *preds, 6366cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *src, TreePatternNode *dst, 6376cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<Record*> &dstregs, 638117ccb7e518f05e4bf3df058fc402262f897ff0bChris Lattner unsigned complexity, unsigned uid) 639997759ac22dc1de6f324b1c09c0a2a558236c489Jim Grosbach : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src), DstPattern(dst), 640117ccb7e518f05e4bf3df058fc402262f897ff0bChris Lattner Dstregs(dstregs), AddedComplexity(complexity), ID(uid) {} 6416cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 642997759ac22dc1de6f324b1c09c0a2a558236c489Jim Grosbach Record *SrcRecord; // Originating Record for the pattern. 64305bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *Predicates; // Top level predicate conditions to match. 6446cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *SrcPattern; // Source pattern to match. 6456cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *DstPattern; // Resulting pattern. 6466cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<Record*> Dstregs; // Physical register defs being matched. 6476cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned AddedComplexity; // Add to matching pattern complexity. 648117ccb7e518f05e4bf3df058fc402262f897ff0bChris Lattner unsigned ID; // Unique ID for the record. 6496cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 650997759ac22dc1de6f324b1c09c0a2a558236c489Jim Grosbach Record *getSrcRecord() const { return SrcRecord; } 65105bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *getPredicates() const { return Predicates; } 6526cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *getSrcPattern() const { return SrcPattern; } 6536cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode *getDstPattern() const { return DstPattern; } 6546cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const std::vector<Record*> &getDstRegs() const { return Dstregs; } 6556cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getAddedComplexity() const { return AddedComplexity; } 65622bb31103de3337f0bb74c7bee16d1817d4dca14Dan Gohman 65722bb31103de3337f0bb74c7bee16d1817d4dca14Dan Gohman std::string getPredicateCheck() const; 658398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 65948e86dbe29e331357b0df11075b7974009c65f34Chris Lattner /// Compute the complexity metric for the input pattern. This roughly 66048e86dbe29e331357b0df11075b7974009c65f34Chris Lattner /// corresponds to the number of nodes that are covered. 66148e86dbe29e331357b0df11075b7974009c65f34Chris Lattner unsigned getPatternComplexity(const CodeGenDAGPatterns &CGP) const; 6626cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 6636cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 6646f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar// Deterministic comparison of Record*. 6656f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbarstruct RecordPtrCmp { 6666f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar bool operator()(const Record *LHS, const Record *RHS) const; 6676f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar}; 668398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 669fe71893183f504feff290e343bf740bd32432129Chris Lattnerclass CodeGenDAGPatterns { 6706cefb77a7073057fecd721ae141140d75ce76512Chris Lattner RecordKeeper &Records; 6716cefb77a7073057fecd721ae141140d75ce76512Chris Lattner CodeGenTarget Target; 6726cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<CodeGenIntrinsic> Intrinsics; 67349de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen std::vector<CodeGenIntrinsic> TgtIntrinsics; 674398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6756f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar std::map<Record*, SDNodeInfo, RecordPtrCmp> SDNodes; 6766f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar std::map<Record*, std::pair<Record*, std::string>, RecordPtrCmp> SDNodeXForms; 6776f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar std::map<Record*, ComplexPattern, RecordPtrCmp> ComplexPatterns; 6786f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar std::map<Record*, TreePattern*, RecordPtrCmp> PatternFragments; 6796f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar std::map<Record*, DAGDefaultOperand, RecordPtrCmp> DefaultOperands; 6806f5cc82686d6f25abc3e373b241bc2cb47d87268Daniel Dunbar std::map<Record*, DAGInstruction, RecordPtrCmp> Instructions; 681398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6826cefb77a7073057fecd721ae141140d75ce76512Chris Lattner // Specific SDNode definitions: 6836cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *intrinsic_void_sdnode; 6846cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; 685398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6866cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// PatternsToMatch - All of the things we are matching on the DAG. The first 6876cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// value is the pattern to match, the second pattern is the result to 6886cefb77a7073057fecd721ae141140d75ce76512Chris Lattner /// emit. 6896cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<PatternToMatch> PatternsToMatch; 6906cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerpublic: 691398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach CodeGenDAGPatterns(RecordKeeper &R); 692fe71893183f504feff290e343bf740bd32432129Chris Lattner ~CodeGenDAGPatterns(); 693398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 694ee4fa1977dd3a495a8857eef924ee5961db765c6Dan Gohman CodeGenTarget &getTargetInfo() { return Target; } 6956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const CodeGenTarget &getTargetInfo() const { return Target; } 696398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6976cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *getSDNodeNamed(const std::string &Name) const; 698398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 6996cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const SDNodeInfo &getSDNodeInfo(Record *R) const { 7006cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(SDNodes.count(R) && "Unknown node!"); 7016cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return SDNodes.find(R)->second; 7026cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 703398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 704443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner // Node transformation lookups. 705443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner typedef std::pair<Record*, std::string> NodeXForm; 706443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner const NodeXForm &getSDNodeTransform(Record *R) const { 7076cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(SDNodeXForms.count(R) && "Invalid transform!"); 7086cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return SDNodeXForms.find(R)->second; 7096cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 710398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7115b9e7ef627aa1e2f49a6ee85e718199799841f7eBenjamin Kramer typedef std::map<Record*, NodeXForm, RecordPtrCmp>::const_iterator 7125b9e7ef627aa1e2f49a6ee85e718199799841f7eBenjamin Kramer nx_iterator; 713443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner nx_iterator nx_begin() const { return SDNodeXForms.begin(); } 714443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner nx_iterator nx_end() const { return SDNodeXForms.end(); } 715443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner 716398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7176cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const ComplexPattern &getComplexPattern(Record *R) const { 7186cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(ComplexPatterns.count(R) && "Unknown addressing mode!"); 7196cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return ComplexPatterns.find(R)->second; 7206cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 721398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7226cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const CodeGenIntrinsic &getIntrinsic(Record *R) const { 7236cefb77a7073057fecd721ae141140d75ce76512Chris Lattner for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 7246cefb77a7073057fecd721ae141140d75ce76512Chris Lattner if (Intrinsics[i].TheDef == R) return Intrinsics[i]; 72549de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 72649de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i]; 727655b8de7b2ab773a977e0c524307e71354d8af29Craig Topper llvm_unreachable("Unknown intrinsic!"); 7286cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 729398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7306cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 73149de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen if (IID-1 < Intrinsics.size()) 73249de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen return Intrinsics[IID-1]; 73349de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen if (IID-Intrinsics.size()-1 < TgtIntrinsics.size()) 73449de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen return TgtIntrinsics[IID-Intrinsics.size()-1]; 735655b8de7b2ab773a977e0c524307e71354d8af29Craig Topper llvm_unreachable("Bad intrinsic ID!"); 7366cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 737398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7386cefb77a7073057fecd721ae141140d75ce76512Chris Lattner unsigned getIntrinsicID(Record *R) const { 7396cefb77a7073057fecd721ae141140d75ce76512Chris Lattner for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 7406cefb77a7073057fecd721ae141140d75ce76512Chris Lattner if (Intrinsics[i].TheDef == R) return i; 74149de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 74249de98214b82fefeb8f16efbf8cdd8813a85469bDale Johannesen if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size(); 743655b8de7b2ab773a977e0c524307e71354d8af29Craig Topper llvm_unreachable("Unknown intrinsic!"); 7446cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 745398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 746b49985a8499e18675db7e9baf920d6ef4e2b65cfChris Lattner const DAGDefaultOperand &getDefaultOperand(Record *R) const { 7476cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); 7486cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return DefaultOperands.find(R)->second; 7496cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 750398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7516cefb77a7073057fecd721ae141140d75ce76512Chris Lattner // Pattern Fragment information. 7526cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePattern *getPatternFragment(Record *R) const { 7536cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); 7546cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return PatternFragments.find(R)->second; 7556cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 756d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner TreePattern *getPatternFragmentIfRead(Record *R) const { 757d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner if (!PatternFragments.count(R)) return 0; 758d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner return PatternFragments.find(R)->second; 759d7349194650386d97a1d779369cb46f20ba9f252Chris Lattner } 760398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7615b9e7ef627aa1e2f49a6ee85e718199799841f7eBenjamin Kramer typedef std::map<Record*, TreePattern*, RecordPtrCmp>::const_iterator 7625b9e7ef627aa1e2f49a6ee85e718199799841f7eBenjamin Kramer pf_iterator; 7636cefb77a7073057fecd721ae141140d75ce76512Chris Lattner pf_iterator pf_begin() const { return PatternFragments.begin(); } 7646cefb77a7073057fecd721ae141140d75ce76512Chris Lattner pf_iterator pf_end() const { return PatternFragments.end(); } 7656cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 7666cefb77a7073057fecd721ae141140d75ce76512Chris Lattner // Patterns to match information. 76760d8139d1b1db8b23c066623d65302dd3dcc4572Chris Lattner typedef std::vector<PatternToMatch>::const_iterator ptm_iterator; 76860d8139d1b1db8b23c066623d65302dd3dcc4572Chris Lattner ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } 76960d8139d1b1db8b23c066623d65302dd3dcc4572Chris Lattner ptm_iterator ptm_end() const { return PatternsToMatch.end(); } 770398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 771398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 772398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7736cefb77a7073057fecd721ae141140d75ce76512Chris Lattner const DAGInstruction &getInstruction(Record *R) const { 7746cefb77a7073057fecd721ae141140d75ce76512Chris Lattner assert(Instructions.count(R) && "Unknown instruction!"); 7756cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return Instructions.find(R)->second; 7766cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 777398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 7786cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *get_intrinsic_void_sdnode() const { 7796cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return intrinsic_void_sdnode; 7806cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 7816cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *get_intrinsic_w_chain_sdnode() const { 7826cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return intrinsic_w_chain_sdnode; 7836cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 7846cefb77a7073057fecd721ae141140d75ce76512Chris Lattner Record *get_intrinsic_wo_chain_sdnode() const { 7856cefb77a7073057fecd721ae141140d75ce76512Chris Lattner return intrinsic_wo_chain_sdnode; 7866cefb77a7073057fecd721ae141140d75ce76512Chris Lattner } 787398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 78811ee508d7bd37f2b007da735fbd2c1497ed51848Jakob Stoklund Olesen bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); } 78911ee508d7bd37f2b007da735fbd2c1497ed51848Jakob Stoklund Olesen 7906cefb77a7073057fecd721ae141140d75ce76512Chris Lattnerprivate: 7916cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void ParseNodeInfo(); 792443e3f9dd61b8d0974bb13d484195ce1a9b7536cChris Lattner void ParseNodeTransforms(); 7936cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void ParseComplexPatterns(); 794dc32f9802adc139e3d7ee5e25fe656b1d3999bc2Chris Lattner void ParsePatternFragments(); 7956cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void ParseDefaultOperands(); 7966cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void ParseInstructions(); 7976cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void ParsePatterns(); 798ee4fa1977dd3a495a8857eef924ee5961db765c6Dan Gohman void InferInstructionFlags(); 7996cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void GenerateVariants(); 800325907d0860f8316edcc3bb00bf7b8b04497c177Jakob Stoklund Olesen void VerifyInstructionFlags(); 801398abb4a9aef6da6118c31b6563ec68d1766b913Jim Grosbach 80225b6f91c549225ae4fc9855b9c82a46d05dfd4d8Chris Lattner void AddPatternToMatch(const TreePattern *Pattern, const PatternToMatch &PTM); 8036cefb77a7073057fecd721ae141140d75ce76512Chris Lattner void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 8046cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::map<std::string, 8056cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode*> &InstInputs, 8066cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::map<std::string, 8076cefb77a7073057fecd721ae141140d75ce76512Chris Lattner TreePatternNode*> &InstResults, 8086cefb77a7073057fecd721ae141140d75ce76512Chris Lattner std::vector<Record*> &InstImpResults); 8096cefb77a7073057fecd721ae141140d75ce76512Chris Lattner}; 8106cefb77a7073057fecd721ae141140d75ce76512Chris Lattner} // end namespace llvm 8116cefb77a7073057fecd721ae141140d75ce76512Chris Lattner 8126cefb77a7073057fecd721ae141140d75ce76512Chris Lattner#endif 813