Home | History | Annotate | Download | only in TableGen
      1 //===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the CodeGenDAGPatterns class, which is used to read and
     11 // represent the patterns present in a .td file for instructions.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "CodeGenDAGPatterns.h"
     16 #include "llvm/ADT/STLExtras.h"
     17 #include "llvm/ADT/SmallString.h"
     18 #include "llvm/ADT/StringExtras.h"
     19 #include "llvm/ADT/Twine.h"
     20 #include "llvm/Support/Debug.h"
     21 #include "llvm/Support/ErrorHandling.h"
     22 #include "llvm/TableGen/Error.h"
     23 #include "llvm/TableGen/Record.h"
     24 #include <algorithm>
     25 #include <cstdio>
     26 #include <set>
     27 using namespace llvm;
     28 
     29 #define DEBUG_TYPE "dag-patterns"
     30 
     31 //===----------------------------------------------------------------------===//
     32 //  EEVT::TypeSet Implementation
     33 //===----------------------------------------------------------------------===//
     34 
     35 static inline bool isInteger(MVT::SimpleValueType VT) {
     36   return MVT(VT).isInteger();
     37 }
     38 static inline bool isFloatingPoint(MVT::SimpleValueType VT) {
     39   return MVT(VT).isFloatingPoint();
     40 }
     41 static inline bool isVector(MVT::SimpleValueType VT) {
     42   return MVT(VT).isVector();
     43 }
     44 static inline bool isScalar(MVT::SimpleValueType VT) {
     45   return !MVT(VT).isVector();
     46 }
     47 
     48 EEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) {
     49   if (VT == MVT::iAny)
     50     EnforceInteger(TP);
     51   else if (VT == MVT::fAny)
     52     EnforceFloatingPoint(TP);
     53   else if (VT == MVT::vAny)
     54     EnforceVector(TP);
     55   else {
     56     assert((VT < MVT::LAST_VALUETYPE || VT == MVT::iPTR ||
     57             VT == MVT::iPTRAny || VT == MVT::Any) && "Not a concrete type!");
     58     TypeVec.push_back(VT);
     59   }
     60 }
     61 
     62 
     63 EEVT::TypeSet::TypeSet(ArrayRef<MVT::SimpleValueType> VTList) {
     64   assert(!VTList.empty() && "empty list?");
     65   TypeVec.append(VTList.begin(), VTList.end());
     66 
     67   if (!VTList.empty())
     68     assert(VTList[0] != MVT::iAny && VTList[0] != MVT::vAny &&
     69            VTList[0] != MVT::fAny);
     70 
     71   // Verify no duplicates.
     72   array_pod_sort(TypeVec.begin(), TypeVec.end());
     73   assert(std::unique(TypeVec.begin(), TypeVec.end()) == TypeVec.end());
     74 }
     75 
     76 /// FillWithPossibleTypes - Set to all legal types and return true, only valid
     77 /// on completely unknown type sets.
     78 bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP,
     79                                           bool (*Pred)(MVT::SimpleValueType),
     80                                           const char *PredicateName) {
     81   assert(isCompletelyUnknown());
     82   ArrayRef<MVT::SimpleValueType> LegalTypes =
     83     TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
     84 
     85   if (TP.hasError())
     86     return false;
     87 
     88   for (MVT::SimpleValueType VT : LegalTypes)
     89     if (!Pred || Pred(VT))
     90       TypeVec.push_back(VT);
     91 
     92   // If we have nothing that matches the predicate, bail out.
     93   if (TypeVec.empty()) {
     94     TP.error("Type inference contradiction found, no " +
     95              std::string(PredicateName) + " types found");
     96     return false;
     97   }
     98   // No need to sort with one element.
     99   if (TypeVec.size() == 1) return true;
    100 
    101   // Remove duplicates.
    102   array_pod_sort(TypeVec.begin(), TypeVec.end());
    103   TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end());
    104 
    105   return true;
    106 }
    107 
    108 /// hasIntegerTypes - Return true if this TypeSet contains iAny or an
    109 /// integer value type.
    110 bool EEVT::TypeSet::hasIntegerTypes() const {
    111   return std::any_of(TypeVec.begin(), TypeVec.end(), isInteger);
    112 }
    113 
    114 /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or
    115 /// a floating point value type.
    116 bool EEVT::TypeSet::hasFloatingPointTypes() const {
    117   return std::any_of(TypeVec.begin(), TypeVec.end(), isFloatingPoint);
    118 }
    119 
    120 /// hasScalarTypes - Return true if this TypeSet contains a scalar value type.
    121 bool EEVT::TypeSet::hasScalarTypes() const {
    122   return std::any_of(TypeVec.begin(), TypeVec.end(), isScalar);
    123 }
    124 
    125 /// hasVectorTypes - Return true if this TypeSet contains a vAny or a vector
    126 /// value type.
    127 bool EEVT::TypeSet::hasVectorTypes() const {
    128   return std::any_of(TypeVec.begin(), TypeVec.end(), isVector);
    129 }
    130 
    131 
    132 std::string EEVT::TypeSet::getName() const {
    133   if (TypeVec.empty()) return "<empty>";
    134 
    135   std::string Result;
    136 
    137   for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) {
    138     std::string VTName = llvm::getEnumName(TypeVec[i]);
    139     // Strip off MVT:: prefix if present.
    140     if (VTName.substr(0,5) == "MVT::")
    141       VTName = VTName.substr(5);
    142     if (i) Result += ':';
    143     Result += VTName;
    144   }
    145 
    146   if (TypeVec.size() == 1)
    147     return Result;
    148   return "{" + Result + "}";
    149 }
    150 
    151 /// MergeInTypeInfo - This merges in type information from the specified
    152 /// argument.  If 'this' changes, it returns true.  If the two types are
    153 /// contradictory (e.g. merge f32 into i32) then this flags an error.
    154 bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){
    155   if (InVT.isCompletelyUnknown() || *this == InVT || TP.hasError())
    156     return false;
    157 
    158   if (isCompletelyUnknown()) {
    159     *this = InVT;
    160     return true;
    161   }
    162 
    163   assert(!TypeVec.empty() && !InVT.TypeVec.empty() && "No unknowns");
    164 
    165   // Handle the abstract cases, seeing if we can resolve them better.
    166   switch (TypeVec[0]) {
    167   default: break;
    168   case MVT::iPTR:
    169   case MVT::iPTRAny:
    170     if (InVT.hasIntegerTypes()) {
    171       EEVT::TypeSet InCopy(InVT);
    172       InCopy.EnforceInteger(TP);
    173       InCopy.EnforceScalar(TP);
    174 
    175       if (InCopy.isConcrete()) {
    176         // If the RHS has one integer type, upgrade iPTR to i32.
    177         TypeVec[0] = InVT.TypeVec[0];
    178         return true;
    179       }
    180 
    181       // If the input has multiple scalar integers, this doesn't add any info.
    182       if (!InCopy.isCompletelyUnknown())
    183         return false;
    184     }
    185     break;
    186   }
    187 
    188   // If the input constraint is iAny/iPTR and this is an integer type list,
    189   // remove non-integer types from the list.
    190   if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) &&
    191       hasIntegerTypes()) {
    192     bool MadeChange = EnforceInteger(TP);
    193 
    194     // If we're merging in iPTR/iPTRAny and the node currently has a list of
    195     // multiple different integer types, replace them with a single iPTR.
    196     if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) &&
    197         TypeVec.size() != 1) {
    198       TypeVec.assign(1, InVT.TypeVec[0]);
    199       MadeChange = true;
    200     }
    201 
    202     return MadeChange;
    203   }
    204 
    205   // If this is a type list and the RHS is a typelist as well, eliminate entries
    206   // from this list that aren't in the other one.
    207   TypeSet InputSet(*this);
    208 
    209   TypeVec.clear();
    210   std::set_intersection(InputSet.TypeVec.begin(), InputSet.TypeVec.end(),
    211                         InVT.TypeVec.begin(), InVT.TypeVec.end(),
    212                         std::back_inserter(TypeVec));
    213 
    214   // If the intersection is the same size as the original set then we're done.
    215   if (TypeVec.size() == InputSet.TypeVec.size())
    216     return false;
    217 
    218   // If we removed all of our types, we have a type contradiction.
    219   if (!TypeVec.empty())
    220     return true;
    221 
    222   // FIXME: Really want an SMLoc here!
    223   TP.error("Type inference contradiction found, merging '" +
    224            InVT.getName() + "' into '" + InputSet.getName() + "'");
    225   return false;
    226 }
    227 
    228 /// EnforceInteger - Remove all non-integer types from this set.
    229 bool EEVT::TypeSet::EnforceInteger(TreePattern &TP) {
    230   if (TP.hasError())
    231     return false;
    232   // If we know nothing, then get the full set.
    233   if (TypeVec.empty())
    234     return FillWithPossibleTypes(TP, isInteger, "integer");
    235 
    236   if (!hasFloatingPointTypes())
    237     return false;
    238 
    239   TypeSet InputSet(*this);
    240 
    241   // Filter out all the fp types.
    242   TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(),
    243                                std::not1(std::ptr_fun(isInteger))),
    244                 TypeVec.end());
    245 
    246   if (TypeVec.empty()) {
    247     TP.error("Type inference contradiction found, '" +
    248              InputSet.getName() + "' needs to be integer");
    249     return false;
    250   }
    251   return true;
    252 }
    253 
    254 /// EnforceFloatingPoint - Remove all integer types from this set.
    255 bool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) {
    256   if (TP.hasError())
    257     return false;
    258   // If we know nothing, then get the full set.
    259   if (TypeVec.empty())
    260     return FillWithPossibleTypes(TP, isFloatingPoint, "floating point");
    261 
    262   if (!hasIntegerTypes())
    263     return false;
    264 
    265   TypeSet InputSet(*this);
    266 
    267   // Filter out all the integer types.
    268   TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(),
    269                                std::not1(std::ptr_fun(isFloatingPoint))),
    270                 TypeVec.end());
    271 
    272   if (TypeVec.empty()) {
    273     TP.error("Type inference contradiction found, '" +
    274              InputSet.getName() + "' needs to be floating point");
    275     return false;
    276   }
    277   return true;
    278 }
    279 
    280 /// EnforceScalar - Remove all vector types from this.
    281 bool EEVT::TypeSet::EnforceScalar(TreePattern &TP) {
    282   if (TP.hasError())
    283     return false;
    284 
    285   // If we know nothing, then get the full set.
    286   if (TypeVec.empty())
    287     return FillWithPossibleTypes(TP, isScalar, "scalar");
    288 
    289   if (!hasVectorTypes())
    290     return false;
    291 
    292   TypeSet InputSet(*this);
    293 
    294   // Filter out all the vector types.
    295   TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(),
    296                                std::not1(std::ptr_fun(isScalar))),
    297                 TypeVec.end());
    298 
    299   if (TypeVec.empty()) {
    300     TP.error("Type inference contradiction found, '" +
    301              InputSet.getName() + "' needs to be scalar");
    302     return false;
    303   }
    304   return true;
    305 }
    306 
    307 /// EnforceVector - Remove all vector types from this.
    308 bool EEVT::TypeSet::EnforceVector(TreePattern &TP) {
    309   if (TP.hasError())
    310     return false;
    311 
    312   // If we know nothing, then get the full set.
    313   if (TypeVec.empty())
    314     return FillWithPossibleTypes(TP, isVector, "vector");
    315 
    316   TypeSet InputSet(*this);
    317   bool MadeChange = false;
    318 
    319   // Filter out all the scalar types.
    320   TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(),
    321                                std::not1(std::ptr_fun(isVector))),
    322                 TypeVec.end());
    323 
    324   if (TypeVec.empty()) {
    325     TP.error("Type inference contradiction found, '" +
    326              InputSet.getName() + "' needs to be a vector");
    327     return false;
    328   }
    329   return MadeChange;
    330 }
    331 
    332 
    333 
    334 /// EnforceSmallerThan - 'this' must be a smaller VT than Other. For vectors
    335 /// this should be based on the element type. Update this and other based on
    336 /// this information.
    337 bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) {
    338   if (TP.hasError())
    339     return false;
    340 
    341   // Both operands must be integer or FP, but we don't care which.
    342   bool MadeChange = false;
    343 
    344   if (isCompletelyUnknown())
    345     MadeChange = FillWithPossibleTypes(TP);
    346 
    347   if (Other.isCompletelyUnknown())
    348     MadeChange = Other.FillWithPossibleTypes(TP);
    349 
    350   // If one side is known to be integer or known to be FP but the other side has
    351   // no information, get at least the type integrality info in there.
    352   if (!hasFloatingPointTypes())
    353     MadeChange |= Other.EnforceInteger(TP);
    354   else if (!hasIntegerTypes())
    355     MadeChange |= Other.EnforceFloatingPoint(TP);
    356   if (!Other.hasFloatingPointTypes())
    357     MadeChange |= EnforceInteger(TP);
    358   else if (!Other.hasIntegerTypes())
    359     MadeChange |= EnforceFloatingPoint(TP);
    360 
    361   assert(!isCompletelyUnknown() && !Other.isCompletelyUnknown() &&
    362          "Should have a type list now");
    363 
    364   // If one contains vectors but the other doesn't pull vectors out.
    365   if (!hasVectorTypes())
    366     MadeChange |= Other.EnforceScalar(TP);
    367   else if (!hasScalarTypes())
    368     MadeChange |= Other.EnforceVector(TP);
    369   if (!Other.hasVectorTypes())
    370     MadeChange |= EnforceScalar(TP);
    371   else if (!Other.hasScalarTypes())
    372     MadeChange |= EnforceVector(TP);
    373 
    374   // This code does not currently handle nodes which have multiple types,
    375   // where some types are integer, and some are fp.  Assert that this is not
    376   // the case.
    377   assert(!(hasIntegerTypes() && hasFloatingPointTypes()) &&
    378          !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) &&
    379          "SDTCisOpSmallerThanOp does not handle mixed int/fp types!");
    380 
    381   if (TP.hasError())
    382     return false;
    383 
    384   // Okay, find the smallest type from current set and remove anything the
    385   // same or smaller from the other set. We need to ensure that the scalar
    386   // type size is smaller than the scalar size of the smallest type. For
    387   // vectors, we also need to make sure that the total size is no larger than
    388   // the size of the smallest type.
    389   {
    390     TypeSet InputSet(Other);
    391     MVT Smallest = *std::min_element(TypeVec.begin(), TypeVec.end(),
    392       [](MVT A, MVT B) {
    393         return A.getScalarSizeInBits() < B.getScalarSizeInBits() ||
    394                (A.getScalarSizeInBits() == B.getScalarSizeInBits() &&
    395                 A.getSizeInBits() < B.getSizeInBits());
    396       });
    397 
    398     auto I = std::remove_if(Other.TypeVec.begin(), Other.TypeVec.end(),
    399       [Smallest](MVT OtherVT) {
    400         // Don't compare vector and non-vector types.
    401         if (OtherVT.isVector() != Smallest.isVector())
    402           return false;
    403         // The getSizeInBits() check here is only needed for vectors, but is
    404         // a subset of the scalar check for scalars so no need to qualify.
    405         return OtherVT.getScalarSizeInBits() <= Smallest.getScalarSizeInBits()||
    406                OtherVT.getSizeInBits() < Smallest.getSizeInBits();
    407       });
    408     MadeChange |= I != Other.TypeVec.end(); // If we're about to remove types.
    409     Other.TypeVec.erase(I, Other.TypeVec.end());
    410 
    411     if (Other.TypeVec.empty()) {
    412       TP.error("Type inference contradiction found, '" + InputSet.getName() +
    413                "' has nothing larger than '" + getName() +"'!");
    414       return false;
    415     }
    416   }
    417 
    418   // Okay, find the largest type from the other set and remove anything the
    419   // same or smaller from the current set. We need to ensure that the scalar
    420   // type size is larger than the scalar size of the largest type. For
    421   // vectors, we also need to make sure that the total size is no smaller than
    422   // the size of the largest type.
    423   {
    424     TypeSet InputSet(*this);
    425     MVT Largest = *std::max_element(Other.TypeVec.begin(), Other.TypeVec.end(),
    426       [](MVT A, MVT B) {
    427         return A.getScalarSizeInBits() < B.getScalarSizeInBits() ||
    428                (A.getScalarSizeInBits() == B.getScalarSizeInBits() &&
    429                 A.getSizeInBits() < B.getSizeInBits());
    430       });
    431     auto I = std::remove_if(TypeVec.begin(), TypeVec.end(),
    432       [Largest](MVT OtherVT) {
    433         // Don't compare vector and non-vector types.
    434         if (OtherVT.isVector() != Largest.isVector())
    435           return false;
    436         return OtherVT.getScalarSizeInBits() >= Largest.getScalarSizeInBits() ||
    437                OtherVT.getSizeInBits() > Largest.getSizeInBits();
    438       });
    439     MadeChange |= I != TypeVec.end(); // If we're about to remove types.
    440     TypeVec.erase(I, TypeVec.end());
    441 
    442     if (TypeVec.empty()) {
    443       TP.error("Type inference contradiction found, '" + InputSet.getName() +
    444                "' has nothing smaller than '" + Other.getName() +"'!");
    445       return false;
    446     }
    447   }
    448 
    449   return MadeChange;
    450 }
    451 
    452 /// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type
    453 /// whose element is specified by VTOperand.
    454 bool EEVT::TypeSet::EnforceVectorEltTypeIs(MVT::SimpleValueType VT,
    455                                            TreePattern &TP) {
    456   bool MadeChange = false;
    457 
    458   MadeChange |= EnforceVector(TP);
    459 
    460   TypeSet InputSet(*this);
    461 
    462   // Filter out all the types which don't have the right element type.
    463   auto I = std::remove_if(TypeVec.begin(), TypeVec.end(),
    464     [VT](MVT VVT) {
    465       return VVT.getVectorElementType().SimpleTy != VT;
    466     });
    467   MadeChange |= I != TypeVec.end();
    468   TypeVec.erase(I, TypeVec.end());
    469 
    470   if (TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    471     TP.error("Type inference contradiction found, forcing '" +
    472              InputSet.getName() + "' to have a vector element of type " +
    473              getEnumName(VT));
    474     return false;
    475   }
    476 
    477   return MadeChange;
    478 }
    479 
    480 /// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type
    481 /// whose element is specified by VTOperand.
    482 bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand,
    483                                            TreePattern &TP) {
    484   if (TP.hasError())
    485     return false;
    486 
    487   // "This" must be a vector and "VTOperand" must be a scalar.
    488   bool MadeChange = false;
    489   MadeChange |= EnforceVector(TP);
    490   MadeChange |= VTOperand.EnforceScalar(TP);
    491 
    492   // If we know the vector type, it forces the scalar to agree.
    493   if (isConcrete()) {
    494     MVT IVT = getConcrete();
    495     IVT = IVT.getVectorElementType();
    496     return MadeChange || VTOperand.MergeInTypeInfo(IVT.SimpleTy, TP);
    497   }
    498 
    499   // If the scalar type is known, filter out vector types whose element types
    500   // disagree.
    501   if (!VTOperand.isConcrete())
    502     return MadeChange;
    503 
    504   MVT::SimpleValueType VT = VTOperand.getConcrete();
    505 
    506   MadeChange |= EnforceVectorEltTypeIs(VT, TP);
    507 
    508   return MadeChange;
    509 }
    510 
    511 /// EnforceVectorSubVectorTypeIs - 'this' is now constrained to be a
    512 /// vector type specified by VTOperand.
    513 bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand,
    514                                                  TreePattern &TP) {
    515   if (TP.hasError())
    516     return false;
    517 
    518   // "This" must be a vector and "VTOperand" must be a vector.
    519   bool MadeChange = false;
    520   MadeChange |= EnforceVector(TP);
    521   MadeChange |= VTOperand.EnforceVector(TP);
    522 
    523   // If one side is known to be integer or known to be FP but the other side has
    524   // no information, get at least the type integrality info in there.
    525   if (!hasFloatingPointTypes())
    526     MadeChange |= VTOperand.EnforceInteger(TP);
    527   else if (!hasIntegerTypes())
    528     MadeChange |= VTOperand.EnforceFloatingPoint(TP);
    529   if (!VTOperand.hasFloatingPointTypes())
    530     MadeChange |= EnforceInteger(TP);
    531   else if (!VTOperand.hasIntegerTypes())
    532     MadeChange |= EnforceFloatingPoint(TP);
    533 
    534   assert(!isCompletelyUnknown() && !VTOperand.isCompletelyUnknown() &&
    535          "Should have a type list now");
    536 
    537   // If we know the vector type, it forces the scalar types to agree.
    538   // Also force one vector to have more elements than the other.
    539   if (isConcrete()) {
    540     MVT IVT = getConcrete();
    541     unsigned NumElems = IVT.getVectorNumElements();
    542     IVT = IVT.getVectorElementType();
    543 
    544     EEVT::TypeSet EltTypeSet(IVT.SimpleTy, TP);
    545     MadeChange |= VTOperand.EnforceVectorEltTypeIs(EltTypeSet, TP);
    546 
    547     // Only keep types that have less elements than VTOperand.
    548     TypeSet InputSet(VTOperand);
    549 
    550     auto I = std::remove_if(VTOperand.TypeVec.begin(), VTOperand.TypeVec.end(),
    551                             [NumElems](MVT VVT) {
    552                               return VVT.getVectorNumElements() >= NumElems;
    553                             });
    554     MadeChange |= I != VTOperand.TypeVec.end();
    555     VTOperand.TypeVec.erase(I, VTOperand.TypeVec.end());
    556 
    557     if (VTOperand.TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    558       TP.error("Type inference contradiction found, forcing '" +
    559                InputSet.getName() + "' to have less vector elements than '" +
    560                getName() + "'");
    561       return false;
    562     }
    563   } else if (VTOperand.isConcrete()) {
    564     MVT IVT = VTOperand.getConcrete();
    565     unsigned NumElems = IVT.getVectorNumElements();
    566     IVT = IVT.getVectorElementType();
    567 
    568     EEVT::TypeSet EltTypeSet(IVT.SimpleTy, TP);
    569     MadeChange |= EnforceVectorEltTypeIs(EltTypeSet, TP);
    570 
    571     // Only keep types that have more elements than 'this'.
    572     TypeSet InputSet(*this);
    573 
    574     auto I = std::remove_if(TypeVec.begin(), TypeVec.end(),
    575                             [NumElems](MVT VVT) {
    576                               return VVT.getVectorNumElements() <= NumElems;
    577                             });
    578     MadeChange |= I != TypeVec.end();
    579     TypeVec.erase(I, TypeVec.end());
    580 
    581     if (TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    582       TP.error("Type inference contradiction found, forcing '" +
    583                InputSet.getName() + "' to have more vector elements than '" +
    584                VTOperand.getName() + "'");
    585       return false;
    586     }
    587   }
    588 
    589   return MadeChange;
    590 }
    591 
    592 /// EnforceVectorSameNumElts - 'this' is now constrained to
    593 /// be a vector with same num elements as VTOperand.
    594 bool EEVT::TypeSet::EnforceVectorSameNumElts(EEVT::TypeSet &VTOperand,
    595                                              TreePattern &TP) {
    596   if (TP.hasError())
    597     return false;
    598 
    599   // "This" must be a vector and "VTOperand" must be a vector.
    600   bool MadeChange = false;
    601   MadeChange |= EnforceVector(TP);
    602   MadeChange |= VTOperand.EnforceVector(TP);
    603 
    604   // If we know one of the vector types, it forces the other type to agree.
    605   if (isConcrete()) {
    606     MVT IVT = getConcrete();
    607     unsigned NumElems = IVT.getVectorNumElements();
    608 
    609     // Only keep types that have same elements as 'this'.
    610     TypeSet InputSet(VTOperand);
    611 
    612     auto I = std::remove_if(VTOperand.TypeVec.begin(), VTOperand.TypeVec.end(),
    613                             [NumElems](MVT VVT) {
    614                               return VVT.getVectorNumElements() != NumElems;
    615                             });
    616     MadeChange |= I != VTOperand.TypeVec.end();
    617     VTOperand.TypeVec.erase(I, VTOperand.TypeVec.end());
    618 
    619     if (VTOperand.TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    620       TP.error("Type inference contradiction found, forcing '" +
    621                InputSet.getName() + "' to have same number elements as '" +
    622                getName() + "'");
    623       return false;
    624     }
    625   } else if (VTOperand.isConcrete()) {
    626     MVT IVT = VTOperand.getConcrete();
    627     unsigned NumElems = IVT.getVectorNumElements();
    628 
    629     // Only keep types that have same elements as VTOperand.
    630     TypeSet InputSet(*this);
    631 
    632     auto I = std::remove_if(TypeVec.begin(), TypeVec.end(),
    633                             [NumElems](MVT VVT) {
    634                               return VVT.getVectorNumElements() != NumElems;
    635                             });
    636     MadeChange |= I != TypeVec.end();
    637     TypeVec.erase(I, TypeVec.end());
    638 
    639     if (TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    640       TP.error("Type inference contradiction found, forcing '" +
    641                InputSet.getName() + "' to have same number elements than '" +
    642                VTOperand.getName() + "'");
    643       return false;
    644     }
    645   }
    646 
    647   return MadeChange;
    648 }
    649 
    650 /// EnforceSameSize - 'this' is now constrained to be same size as VTOperand.
    651 bool EEVT::TypeSet::EnforceSameSize(EEVT::TypeSet &VTOperand,
    652                                     TreePattern &TP) {
    653   if (TP.hasError())
    654     return false;
    655 
    656   bool MadeChange = false;
    657 
    658   // If we know one of the types, it forces the other type agree.
    659   if (isConcrete()) {
    660     MVT IVT = getConcrete();
    661     unsigned Size = IVT.getSizeInBits();
    662 
    663     // Only keep types that have the same size as 'this'.
    664     TypeSet InputSet(VTOperand);
    665 
    666     auto I = std::remove_if(VTOperand.TypeVec.begin(), VTOperand.TypeVec.end(),
    667                             [&](MVT VT) {
    668                               return VT.getSizeInBits() != Size;
    669                             });
    670     MadeChange |= I != VTOperand.TypeVec.end();
    671     VTOperand.TypeVec.erase(I, VTOperand.TypeVec.end());
    672 
    673     if (VTOperand.TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    674       TP.error("Type inference contradiction found, forcing '" +
    675                InputSet.getName() + "' to have same size as '" +
    676                getName() + "'");
    677       return false;
    678     }
    679   } else if (VTOperand.isConcrete()) {
    680     MVT IVT = VTOperand.getConcrete();
    681     unsigned Size = IVT.getSizeInBits();
    682 
    683     // Only keep types that have the same size as VTOperand.
    684     TypeSet InputSet(*this);
    685 
    686     auto I = std::remove_if(TypeVec.begin(), TypeVec.end(),
    687                             [&](MVT VT) {
    688                               return VT.getSizeInBits() != Size;
    689                             });
    690     MadeChange |= I != TypeVec.end();
    691     TypeVec.erase(I, TypeVec.end());
    692 
    693     if (TypeVec.empty()) {  // FIXME: Really want an SMLoc here!
    694       TP.error("Type inference contradiction found, forcing '" +
    695                InputSet.getName() + "' to have same size as '" +
    696                VTOperand.getName() + "'");
    697       return false;
    698     }
    699   }
    700 
    701   return MadeChange;
    702 }
    703 
    704 //===----------------------------------------------------------------------===//
    705 // Helpers for working with extended types.
    706 
    707 /// Dependent variable map for CodeGenDAGPattern variant generation
    708 typedef std::map<std::string, int> DepVarMap;
    709 
    710 static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) {
    711   if (N->isLeaf()) {
    712     if (isa<DefInit>(N->getLeafValue()))
    713       DepMap[N->getName()]++;
    714   } else {
    715     for (size_t i = 0, e = N->getNumChildren(); i != e; ++i)
    716       FindDepVarsOf(N->getChild(i), DepMap);
    717   }
    718 }
    719 
    720 /// Find dependent variables within child patterns
    721 static void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) {
    722   DepVarMap depcounts;
    723   FindDepVarsOf(N, depcounts);
    724   for (const std::pair<std::string, int> &Pair : depcounts) {
    725     if (Pair.second > 1)
    726       DepVars.insert(Pair.first);
    727   }
    728 }
    729 
    730 #ifndef NDEBUG
    731 /// Dump the dependent variable set:
    732 static void DumpDepVars(MultipleUseVarSet &DepVars) {
    733   if (DepVars.empty()) {
    734     DEBUG(errs() << "<empty set>");
    735   } else {
    736     DEBUG(errs() << "[ ");
    737     for (const std::string &DepVar : DepVars) {
    738       DEBUG(errs() << DepVar << " ");
    739     }
    740     DEBUG(errs() << "]");
    741   }
    742 }
    743 #endif
    744 
    745 
    746 //===----------------------------------------------------------------------===//
    747 // TreePredicateFn Implementation
    748 //===----------------------------------------------------------------------===//
    749 
    750 /// TreePredicateFn constructor.  Here 'N' is a subclass of PatFrag.
    751 TreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) {
    752   assert((getPredCode().empty() || getImmCode().empty()) &&
    753         ".td file corrupt: can't have a node predicate *and* an imm predicate");
    754 }
    755 
    756 std::string TreePredicateFn::getPredCode() const {
    757   return PatFragRec->getRecord()->getValueAsString("PredicateCode");
    758 }
    759 
    760 std::string TreePredicateFn::getImmCode() const {
    761   return PatFragRec->getRecord()->getValueAsString("ImmediateCode");
    762 }
    763 
    764 
    765 /// isAlwaysTrue - Return true if this is a noop predicate.
    766 bool TreePredicateFn::isAlwaysTrue() const {
    767   return getPredCode().empty() && getImmCode().empty();
    768 }
    769 
    770 /// Return the name to use in the generated code to reference this, this is
    771 /// "Predicate_foo" if from a pattern fragment "foo".
    772 std::string TreePredicateFn::getFnName() const {
    773   return "Predicate_" + PatFragRec->getRecord()->getName();
    774 }
    775 
    776 /// getCodeToRunOnSDNode - Return the code for the function body that
    777 /// evaluates this predicate.  The argument is expected to be in "Node",
    778 /// not N.  This handles casting and conversion to a concrete node type as
    779 /// appropriate.
    780 std::string TreePredicateFn::getCodeToRunOnSDNode() const {
    781   // Handle immediate predicates first.
    782   std::string ImmCode = getImmCode();
    783   if (!ImmCode.empty()) {
    784     std::string Result =
    785       "    int64_t Imm = cast<ConstantSDNode>(Node)->getSExtValue();\n";
    786     return Result + ImmCode;
    787   }
    788 
    789   // Handle arbitrary node predicates.
    790   assert(!getPredCode().empty() && "Don't have any predicate code!");
    791   std::string ClassName;
    792   if (PatFragRec->getOnlyTree()->isLeaf())
    793     ClassName = "SDNode";
    794   else {
    795     Record *Op = PatFragRec->getOnlyTree()->getOperator();
    796     ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName();
    797   }
    798   std::string Result;
    799   if (ClassName == "SDNode")
    800     Result = "    SDNode *N = Node;\n";
    801   else
    802     Result = "    auto *N = cast<" + ClassName + ">(Node);\n";
    803 
    804   return Result + getPredCode();
    805 }
    806 
    807 //===----------------------------------------------------------------------===//
    808 // PatternToMatch implementation
    809 //
    810 
    811 
    812 /// getPatternSize - Return the 'size' of this pattern.  We want to match large
    813 /// patterns before small ones.  This is used to determine the size of a
    814 /// pattern.
    815 static unsigned getPatternSize(const TreePatternNode *P,
    816                                const CodeGenDAGPatterns &CGP) {
    817   unsigned Size = 3;  // The node itself.
    818   // If the root node is a ConstantSDNode, increases its size.
    819   // e.g. (set R32:$dst, 0).
    820   if (P->isLeaf() && isa<IntInit>(P->getLeafValue()))
    821     Size += 2;
    822 
    823   // FIXME: This is a hack to statically increase the priority of patterns
    824   // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD.
    825   // Later we can allow complexity / cost for each pattern to be (optionally)
    826   // specified. To get best possible pattern match we'll need to dynamically
    827   // calculate the complexity of all patterns a dag can potentially map to.
    828   const ComplexPattern *AM = P->getComplexPatternInfo(CGP);
    829   if (AM) {
    830     Size += AM->getNumOperands() * 3;
    831 
    832     // We don't want to count any children twice, so return early.
    833     return Size;
    834   }
    835 
    836   // If this node has some predicate function that must match, it adds to the
    837   // complexity of this node.
    838   if (!P->getPredicateFns().empty())
    839     ++Size;
    840 
    841   // Count children in the count if they are also nodes.
    842   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
    843     TreePatternNode *Child = P->getChild(i);
    844     if (!Child->isLeaf() && Child->getNumTypes() &&
    845         Child->getType(0) != MVT::Other)
    846       Size += getPatternSize(Child, CGP);
    847     else if (Child->isLeaf()) {
    848       if (isa<IntInit>(Child->getLeafValue()))
    849         Size += 5;  // Matches a ConstantSDNode (+3) and a specific value (+2).
    850       else if (Child->getComplexPatternInfo(CGP))
    851         Size += getPatternSize(Child, CGP);
    852       else if (!Child->getPredicateFns().empty())
    853         ++Size;
    854     }
    855   }
    856 
    857   return Size;
    858 }
    859 
    860 /// Compute the complexity metric for the input pattern.  This roughly
    861 /// corresponds to the number of nodes that are covered.
    862 int PatternToMatch::
    863 getPatternComplexity(const CodeGenDAGPatterns &CGP) const {
    864   return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity();
    865 }
    866 
    867 
    868 /// getPredicateCheck - Return a single string containing all of this
    869 /// pattern's predicates concatenated with "&&" operators.
    870 ///
    871 std::string PatternToMatch::getPredicateCheck() const {
    872   SmallVector<Record *, 4> PredicateRecs;
    873   for (Init *I : Predicates->getValues()) {
    874     if (DefInit *Pred = dyn_cast<DefInit>(I)) {
    875       Record *Def = Pred->getDef();
    876       if (!Def->isSubClassOf("Predicate")) {
    877 #ifndef NDEBUG
    878         Def->dump();
    879 #endif
    880         llvm_unreachable("Unknown predicate type!");
    881       }
    882       PredicateRecs.push_back(Def);
    883     }
    884   }
    885   // Sort so that different orders get canonicalized to the same string.
    886   std::sort(PredicateRecs.begin(), PredicateRecs.end(), LessRecord());
    887 
    888   SmallString<128> PredicateCheck;
    889   for (Record *Pred : PredicateRecs) {
    890     if (!PredicateCheck.empty())
    891       PredicateCheck += " && ";
    892     PredicateCheck += "(" + Pred->getValueAsString("CondString") + ")";
    893   }
    894 
    895   return PredicateCheck.str();
    896 }
    897 
    898 //===----------------------------------------------------------------------===//
    899 // SDTypeConstraint implementation
    900 //
    901 
    902 SDTypeConstraint::SDTypeConstraint(Record *R) {
    903   OperandNo = R->getValueAsInt("OperandNum");
    904 
    905   if (R->isSubClassOf("SDTCisVT")) {
    906     ConstraintType = SDTCisVT;
    907     x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT"));
    908     if (x.SDTCisVT_Info.VT == MVT::isVoid)
    909       PrintFatalError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT");
    910 
    911   } else if (R->isSubClassOf("SDTCisPtrTy")) {
    912     ConstraintType = SDTCisPtrTy;
    913   } else if (R->isSubClassOf("SDTCisInt")) {
    914     ConstraintType = SDTCisInt;
    915   } else if (R->isSubClassOf("SDTCisFP")) {
    916     ConstraintType = SDTCisFP;
    917   } else if (R->isSubClassOf("SDTCisVec")) {
    918     ConstraintType = SDTCisVec;
    919   } else if (R->isSubClassOf("SDTCisSameAs")) {
    920     ConstraintType = SDTCisSameAs;
    921     x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum");
    922   } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {
    923     ConstraintType = SDTCisVTSmallerThanOp;
    924     x.SDTCisVTSmallerThanOp_Info.OtherOperandNum =
    925       R->getValueAsInt("OtherOperandNum");
    926   } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) {
    927     ConstraintType = SDTCisOpSmallerThanOp;
    928     x.SDTCisOpSmallerThanOp_Info.BigOperandNum =
    929       R->getValueAsInt("BigOperandNum");
    930   } else if (R->isSubClassOf("SDTCisEltOfVec")) {
    931     ConstraintType = SDTCisEltOfVec;
    932     x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum");
    933   } else if (R->isSubClassOf("SDTCisSubVecOfVec")) {
    934     ConstraintType = SDTCisSubVecOfVec;
    935     x.SDTCisSubVecOfVec_Info.OtherOperandNum =
    936       R->getValueAsInt("OtherOpNum");
    937   } else if (R->isSubClassOf("SDTCVecEltisVT")) {
    938     ConstraintType = SDTCVecEltisVT;
    939     x.SDTCVecEltisVT_Info.VT = getValueType(R->getValueAsDef("VT"));
    940     if (MVT(x.SDTCVecEltisVT_Info.VT).isVector())
    941       PrintFatalError(R->getLoc(), "Cannot use vector type as SDTCVecEltisVT");
    942     if (!MVT(x.SDTCVecEltisVT_Info.VT).isInteger() &&
    943         !MVT(x.SDTCVecEltisVT_Info.VT).isFloatingPoint())
    944       PrintFatalError(R->getLoc(), "Must use integer or floating point type "
    945                                    "as SDTCVecEltisVT");
    946   } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) {
    947     ConstraintType = SDTCisSameNumEltsAs;
    948     x.SDTCisSameNumEltsAs_Info.OtherOperandNum =
    949       R->getValueAsInt("OtherOperandNum");
    950   } else if (R->isSubClassOf("SDTCisSameSizeAs")) {
    951     ConstraintType = SDTCisSameSizeAs;
    952     x.SDTCisSameSizeAs_Info.OtherOperandNum =
    953       R->getValueAsInt("OtherOperandNum");
    954   } else {
    955     PrintFatalError("Unrecognized SDTypeConstraint '" + R->getName() + "'!\n");
    956   }
    957 }
    958 
    959 /// getOperandNum - Return the node corresponding to operand #OpNo in tree
    960 /// N, and the result number in ResNo.
    961 static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N,
    962                                       const SDNodeInfo &NodeInfo,
    963                                       unsigned &ResNo) {
    964   unsigned NumResults = NodeInfo.getNumResults();
    965   if (OpNo < NumResults) {
    966     ResNo = OpNo;
    967     return N;
    968   }
    969 
    970   OpNo -= NumResults;
    971 
    972   if (OpNo >= N->getNumChildren()) {
    973     std::string S;
    974     raw_string_ostream OS(S);
    975     OS << "Invalid operand number in type constraint "
    976            << (OpNo+NumResults) << " ";
    977     N->print(OS);
    978     PrintFatalError(OS.str());
    979   }
    980 
    981   return N->getChild(OpNo);
    982 }
    983 
    984 /// ApplyTypeConstraint - Given a node in a pattern, apply this type
    985 /// constraint to the nodes operands.  This returns true if it makes a
    986 /// change, false otherwise.  If a type contradiction is found, flag an error.
    987 bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
    988                                            const SDNodeInfo &NodeInfo,
    989                                            TreePattern &TP) const {
    990   if (TP.hasError())
    991     return false;
    992 
    993   unsigned ResNo = 0; // The result number being referenced.
    994   TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo);
    995 
    996   switch (ConstraintType) {
    997   case SDTCisVT:
    998     // Operand must be a particular type.
    999     return NodeToApply->UpdateNodeType(ResNo, x.SDTCisVT_Info.VT, TP);
   1000   case SDTCisPtrTy:
   1001     // Operand must be same as target pointer type.
   1002     return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP);
   1003   case SDTCisInt:
   1004     // Require it to be one of the legal integer VTs.
   1005     return NodeToApply->getExtType(ResNo).EnforceInteger(TP);
   1006   case SDTCisFP:
   1007     // Require it to be one of the legal fp VTs.
   1008     return NodeToApply->getExtType(ResNo).EnforceFloatingPoint(TP);
   1009   case SDTCisVec:
   1010     // Require it to be one of the legal vector VTs.
   1011     return NodeToApply->getExtType(ResNo).EnforceVector(TP);
   1012   case SDTCisSameAs: {
   1013     unsigned OResNo = 0;
   1014     TreePatternNode *OtherNode =
   1015       getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo);
   1016     return NodeToApply->UpdateNodeType(ResNo, OtherNode->getExtType(OResNo),TP)|
   1017            OtherNode->UpdateNodeType(OResNo,NodeToApply->getExtType(ResNo),TP);
   1018   }
   1019   case SDTCisVTSmallerThanOp: {
   1020     // The NodeToApply must be a leaf node that is a VT.  OtherOperandNum must
   1021     // have an integer type that is smaller than the VT.
   1022     if (!NodeToApply->isLeaf() ||
   1023         !isa<DefInit>(NodeToApply->getLeafValue()) ||
   1024         !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
   1025                ->isSubClassOf("ValueType")) {
   1026       TP.error(N->getOperator()->getName() + " expects a VT operand!");
   1027       return false;
   1028     }
   1029     MVT::SimpleValueType VT =
   1030      getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef());
   1031 
   1032     EEVT::TypeSet TypeListTmp(VT, TP);
   1033 
   1034     unsigned OResNo = 0;
   1035     TreePatternNode *OtherNode =
   1036       getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo,
   1037                     OResNo);
   1038 
   1039     return TypeListTmp.EnforceSmallerThan(OtherNode->getExtType(OResNo), TP);
   1040   }
   1041   case SDTCisOpSmallerThanOp: {
   1042     unsigned BResNo = 0;
   1043     TreePatternNode *BigOperand =
   1044       getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo,
   1045                     BResNo);
   1046     return NodeToApply->getExtType(ResNo).
   1047                   EnforceSmallerThan(BigOperand->getExtType(BResNo), TP);
   1048   }
   1049   case SDTCisEltOfVec: {
   1050     unsigned VResNo = 0;
   1051     TreePatternNode *VecOperand =
   1052       getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo,
   1053                     VResNo);
   1054 
   1055     // Filter vector types out of VecOperand that don't have the right element
   1056     // type.
   1057     return VecOperand->getExtType(VResNo).
   1058       EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), TP);
   1059   }
   1060   case SDTCisSubVecOfVec: {
   1061     unsigned VResNo = 0;
   1062     TreePatternNode *BigVecOperand =
   1063       getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo,
   1064                     VResNo);
   1065 
   1066     // Filter vector types out of BigVecOperand that don't have the
   1067     // right subvector type.
   1068     return BigVecOperand->getExtType(VResNo).
   1069       EnforceVectorSubVectorTypeIs(NodeToApply->getExtType(ResNo), TP);
   1070   }
   1071   case SDTCVecEltisVT: {
   1072     return NodeToApply->getExtType(ResNo).
   1073       EnforceVectorEltTypeIs(x.SDTCVecEltisVT_Info.VT, TP);
   1074   }
   1075   case SDTCisSameNumEltsAs: {
   1076     unsigned OResNo = 0;
   1077     TreePatternNode *OtherNode =
   1078       getOperandNum(x.SDTCisSameNumEltsAs_Info.OtherOperandNum,
   1079                     N, NodeInfo, OResNo);
   1080     return OtherNode->getExtType(OResNo).
   1081       EnforceVectorSameNumElts(NodeToApply->getExtType(ResNo), TP);
   1082   }
   1083   case SDTCisSameSizeAs: {
   1084     unsigned OResNo = 0;
   1085     TreePatternNode *OtherNode =
   1086       getOperandNum(x.SDTCisSameSizeAs_Info.OtherOperandNum,
   1087                     N, NodeInfo, OResNo);
   1088     return OtherNode->getExtType(OResNo).
   1089       EnforceSameSize(NodeToApply->getExtType(ResNo), TP);
   1090   }
   1091   }
   1092   llvm_unreachable("Invalid ConstraintType!");
   1093 }
   1094 
   1095 // Update the node type to match an instruction operand or result as specified
   1096 // in the ins or outs lists on the instruction definition. Return true if the
   1097 // type was actually changed.
   1098 bool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo,
   1099                                              Record *Operand,
   1100                                              TreePattern &TP) {
   1101   // The 'unknown' operand indicates that types should be inferred from the
   1102   // context.
   1103   if (Operand->isSubClassOf("unknown_class"))
   1104     return false;
   1105 
   1106   // The Operand class specifies a type directly.
   1107   if (Operand->isSubClassOf("Operand"))
   1108     return UpdateNodeType(ResNo, getValueType(Operand->getValueAsDef("Type")),
   1109                           TP);
   1110 
   1111   // PointerLikeRegClass has a type that is determined at runtime.
   1112   if (Operand->isSubClassOf("PointerLikeRegClass"))
   1113     return UpdateNodeType(ResNo, MVT::iPTR, TP);
   1114 
   1115   // Both RegisterClass and RegisterOperand operands derive their types from a
   1116   // register class def.
   1117   Record *RC = nullptr;
   1118   if (Operand->isSubClassOf("RegisterClass"))
   1119     RC = Operand;
   1120   else if (Operand->isSubClassOf("RegisterOperand"))
   1121     RC = Operand->getValueAsDef("RegClass");
   1122 
   1123   assert(RC && "Unknown operand type");
   1124   CodeGenTarget &Tgt = TP.getDAGPatterns().getTargetInfo();
   1125   return UpdateNodeType(ResNo, Tgt.getRegisterClass(RC).getValueTypes(), TP);
   1126 }
   1127 
   1128 
   1129 //===----------------------------------------------------------------------===//
   1130 // SDNodeInfo implementation
   1131 //
   1132 SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
   1133   EnumName    = R->getValueAsString("Opcode");
   1134   SDClassName = R->getValueAsString("SDClass");
   1135   Record *TypeProfile = R->getValueAsDef("TypeProfile");
   1136   NumResults = TypeProfile->getValueAsInt("NumResults");
   1137   NumOperands = TypeProfile->getValueAsInt("NumOperands");
   1138 
   1139   // Parse the properties.
   1140   Properties = 0;
   1141   for (Record *Property : R->getValueAsListOfDefs("Properties")) {
   1142     if (Property->getName() == "SDNPCommutative") {
   1143       Properties |= 1 << SDNPCommutative;
   1144     } else if (Property->getName() == "SDNPAssociative") {
   1145       Properties |= 1 << SDNPAssociative;
   1146     } else if (Property->getName() == "SDNPHasChain") {
   1147       Properties |= 1 << SDNPHasChain;
   1148     } else if (Property->getName() == "SDNPOutGlue") {
   1149       Properties |= 1 << SDNPOutGlue;
   1150     } else if (Property->getName() == "SDNPInGlue") {
   1151       Properties |= 1 << SDNPInGlue;
   1152     } else if (Property->getName() == "SDNPOptInGlue") {
   1153       Properties |= 1 << SDNPOptInGlue;
   1154     } else if (Property->getName() == "SDNPMayStore") {
   1155       Properties |= 1 << SDNPMayStore;
   1156     } else if (Property->getName() == "SDNPMayLoad") {
   1157       Properties |= 1 << SDNPMayLoad;
   1158     } else if (Property->getName() == "SDNPSideEffect") {
   1159       Properties |= 1 << SDNPSideEffect;
   1160     } else if (Property->getName() == "SDNPMemOperand") {
   1161       Properties |= 1 << SDNPMemOperand;
   1162     } else if (Property->getName() == "SDNPVariadic") {
   1163       Properties |= 1 << SDNPVariadic;
   1164     } else {
   1165       PrintFatalError("Unknown SD Node property '" +
   1166                       Property->getName() + "' on node '" +
   1167                       R->getName() + "'!");
   1168     }
   1169   }
   1170 
   1171 
   1172   // Parse the type constraints.
   1173   std::vector<Record*> ConstraintList =
   1174     TypeProfile->getValueAsListOfDefs("Constraints");
   1175   TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end());
   1176 }
   1177 
   1178 /// getKnownType - If the type constraints on this node imply a fixed type
   1179 /// (e.g. all stores return void, etc), then return it as an
   1180 /// MVT::SimpleValueType.  Otherwise, return EEVT::Other.
   1181 MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const {
   1182   unsigned NumResults = getNumResults();
   1183   assert(NumResults <= 1 &&
   1184          "We only work with nodes with zero or one result so far!");
   1185   assert(ResNo == 0 && "Only handles single result nodes so far");
   1186 
   1187   for (const SDTypeConstraint &Constraint : TypeConstraints) {
   1188     // Make sure that this applies to the correct node result.
   1189     if (Constraint.OperandNo >= NumResults)  // FIXME: need value #
   1190       continue;
   1191 
   1192     switch (Constraint.ConstraintType) {
   1193     default: break;
   1194     case SDTypeConstraint::SDTCisVT:
   1195       return Constraint.x.SDTCisVT_Info.VT;
   1196     case SDTypeConstraint::SDTCisPtrTy:
   1197       return MVT::iPTR;
   1198     }
   1199   }
   1200   return MVT::Other;
   1201 }
   1202 
   1203 //===----------------------------------------------------------------------===//
   1204 // TreePatternNode implementation
   1205 //
   1206 
   1207 TreePatternNode::~TreePatternNode() {
   1208 #if 0 // FIXME: implement refcounted tree nodes!
   1209   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1210     delete getChild(i);
   1211 #endif
   1212 }
   1213 
   1214 static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) {
   1215   if (Operator->getName() == "set" ||
   1216       Operator->getName() == "implicit")
   1217     return 0;  // All return nothing.
   1218 
   1219   if (Operator->isSubClassOf("Intrinsic"))
   1220     return CDP.getIntrinsic(Operator).IS.RetVTs.size();
   1221 
   1222   if (Operator->isSubClassOf("SDNode"))
   1223     return CDP.getSDNodeInfo(Operator).getNumResults();
   1224 
   1225   if (Operator->isSubClassOf("PatFrag")) {
   1226     // If we've already parsed this pattern fragment, get it.  Otherwise, handle
   1227     // the forward reference case where one pattern fragment references another
   1228     // before it is processed.
   1229     if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator))
   1230       return PFRec->getOnlyTree()->getNumTypes();
   1231 
   1232     // Get the result tree.
   1233     DagInit *Tree = Operator->getValueAsDag("Fragment");
   1234     Record *Op = nullptr;
   1235     if (Tree)
   1236       if (DefInit *DI = dyn_cast<DefInit>(Tree->getOperator()))
   1237         Op = DI->getDef();
   1238     assert(Op && "Invalid Fragment");
   1239     return GetNumNodeResults(Op, CDP);
   1240   }
   1241 
   1242   if (Operator->isSubClassOf("Instruction")) {
   1243     CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator);
   1244 
   1245     unsigned NumDefsToAdd = InstInfo.Operands.NumDefs;
   1246 
   1247     // Subtract any defaulted outputs.
   1248     for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) {
   1249       Record *OperandNode = InstInfo.Operands[i].Rec;
   1250 
   1251       if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&
   1252           !CDP.getDefaultOperand(OperandNode).DefaultOps.empty())
   1253         --NumDefsToAdd;
   1254     }
   1255 
   1256     // Add on one implicit def if it has a resolvable type.
   1257     if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other)
   1258       ++NumDefsToAdd;
   1259     return NumDefsToAdd;
   1260   }
   1261 
   1262   if (Operator->isSubClassOf("SDNodeXForm"))
   1263     return 1;  // FIXME: Generalize SDNodeXForm
   1264 
   1265   if (Operator->isSubClassOf("ValueType"))
   1266     return 1;  // A type-cast of one result.
   1267 
   1268   if (Operator->isSubClassOf("ComplexPattern"))
   1269     return 1;
   1270 
   1271   Operator->dump();
   1272   PrintFatalError("Unhandled node in GetNumNodeResults");
   1273 }
   1274 
   1275 void TreePatternNode::print(raw_ostream &OS) const {
   1276   if (isLeaf())
   1277     OS << *getLeafValue();
   1278   else
   1279     OS << '(' << getOperator()->getName();
   1280 
   1281   for (unsigned i = 0, e = Types.size(); i != e; ++i)
   1282     OS << ':' << getExtType(i).getName();
   1283 
   1284   if (!isLeaf()) {
   1285     if (getNumChildren() != 0) {
   1286       OS << " ";
   1287       getChild(0)->print(OS);
   1288       for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
   1289         OS << ", ";
   1290         getChild(i)->print(OS);
   1291       }
   1292     }
   1293     OS << ")";
   1294   }
   1295 
   1296   for (const TreePredicateFn &Pred : PredicateFns)
   1297     OS << "<<P:" << Pred.getFnName() << ">>";
   1298   if (TransformFn)
   1299     OS << "<<X:" << TransformFn->getName() << ">>";
   1300   if (!getName().empty())
   1301     OS << ":$" << getName();
   1302 
   1303 }
   1304 void TreePatternNode::dump() const {
   1305   print(errs());
   1306 }
   1307 
   1308 /// isIsomorphicTo - Return true if this node is recursively
   1309 /// isomorphic to the specified node.  For this comparison, the node's
   1310 /// entire state is considered. The assigned name is ignored, since
   1311 /// nodes with differing names are considered isomorphic. However, if
   1312 /// the assigned name is present in the dependent variable set, then
   1313 /// the assigned name is considered significant and the node is
   1314 /// isomorphic if the names match.
   1315 bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N,
   1316                                      const MultipleUseVarSet &DepVars) const {
   1317   if (N == this) return true;
   1318   if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() ||
   1319       getPredicateFns() != N->getPredicateFns() ||
   1320       getTransformFn() != N->getTransformFn())
   1321     return false;
   1322 
   1323   if (isLeaf()) {
   1324     if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) {
   1325       if (DefInit *NDI = dyn_cast<DefInit>(N->getLeafValue())) {
   1326         return ((DI->getDef() == NDI->getDef())
   1327                 && (DepVars.find(getName()) == DepVars.end()
   1328                     || getName() == N->getName()));
   1329       }
   1330     }
   1331     return getLeafValue() == N->getLeafValue();
   1332   }
   1333 
   1334   if (N->getOperator() != getOperator() ||
   1335       N->getNumChildren() != getNumChildren()) return false;
   1336   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1337     if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars))
   1338       return false;
   1339   return true;
   1340 }
   1341 
   1342 /// clone - Make a copy of this tree and all of its children.
   1343 ///
   1344 TreePatternNode *TreePatternNode::clone() const {
   1345   TreePatternNode *New;
   1346   if (isLeaf()) {
   1347     New = new TreePatternNode(getLeafValue(), getNumTypes());
   1348   } else {
   1349     std::vector<TreePatternNode*> CChildren;
   1350     CChildren.reserve(Children.size());
   1351     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1352       CChildren.push_back(getChild(i)->clone());
   1353     New = new TreePatternNode(getOperator(), CChildren, getNumTypes());
   1354   }
   1355   New->setName(getName());
   1356   New->Types = Types;
   1357   New->setPredicateFns(getPredicateFns());
   1358   New->setTransformFn(getTransformFn());
   1359   return New;
   1360 }
   1361 
   1362 /// RemoveAllTypes - Recursively strip all the types of this tree.
   1363 void TreePatternNode::RemoveAllTypes() {
   1364   // Reset to unknown type.
   1365   std::fill(Types.begin(), Types.end(), EEVT::TypeSet());
   1366   if (isLeaf()) return;
   1367   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1368     getChild(i)->RemoveAllTypes();
   1369 }
   1370 
   1371 
   1372 /// SubstituteFormalArguments - Replace the formal arguments in this tree
   1373 /// with actual values specified by ArgMap.
   1374 void TreePatternNode::
   1375 SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
   1376   if (isLeaf()) return;
   1377 
   1378   for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
   1379     TreePatternNode *Child = getChild(i);
   1380     if (Child->isLeaf()) {
   1381       Init *Val = Child->getLeafValue();
   1382       // Note that, when substituting into an output pattern, Val might be an
   1383       // UnsetInit.
   1384       if (isa<UnsetInit>(Val) || (isa<DefInit>(Val) &&
   1385           cast<DefInit>(Val)->getDef()->getName() == "node")) {
   1386         // We found a use of a formal argument, replace it with its value.
   1387         TreePatternNode *NewChild = ArgMap[Child->getName()];
   1388         assert(NewChild && "Couldn't find formal argument!");
   1389         assert((Child->getPredicateFns().empty() ||
   1390                 NewChild->getPredicateFns() == Child->getPredicateFns()) &&
   1391                "Non-empty child predicate clobbered!");
   1392         setChild(i, NewChild);
   1393       }
   1394     } else {
   1395       getChild(i)->SubstituteFormalArguments(ArgMap);
   1396     }
   1397   }
   1398 }
   1399 
   1400 
   1401 /// InlinePatternFragments - If this pattern refers to any pattern
   1402 /// fragments, inline them into place, giving us a pattern without any
   1403 /// PatFrag references.
   1404 TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
   1405   if (TP.hasError())
   1406     return nullptr;
   1407 
   1408   if (isLeaf())
   1409      return this;  // nothing to do.
   1410   Record *Op = getOperator();
   1411 
   1412   if (!Op->isSubClassOf("PatFrag")) {
   1413     // Just recursively inline children nodes.
   1414     for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
   1415       TreePatternNode *Child = getChild(i);
   1416       TreePatternNode *NewChild = Child->InlinePatternFragments(TP);
   1417 
   1418       assert((Child->getPredicateFns().empty() ||
   1419               NewChild->getPredicateFns() == Child->getPredicateFns()) &&
   1420              "Non-empty child predicate clobbered!");
   1421 
   1422       setChild(i, NewChild);
   1423     }
   1424     return this;
   1425   }
   1426 
   1427   // Otherwise, we found a reference to a fragment.  First, look up its
   1428   // TreePattern record.
   1429   TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);
   1430 
   1431   // Verify that we are passing the right number of operands.
   1432   if (Frag->getNumArgs() != Children.size()) {
   1433     TP.error("'" + Op->getName() + "' fragment requires " +
   1434              utostr(Frag->getNumArgs()) + " operands!");
   1435     return nullptr;
   1436   }
   1437 
   1438   TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
   1439 
   1440   TreePredicateFn PredFn(Frag);
   1441   if (!PredFn.isAlwaysTrue())
   1442     FragTree->addPredicateFn(PredFn);
   1443 
   1444   // Resolve formal arguments to their actual value.
   1445   if (Frag->getNumArgs()) {
   1446     // Compute the map of formal to actual arguments.
   1447     std::map<std::string, TreePatternNode*> ArgMap;
   1448     for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
   1449       ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
   1450 
   1451     FragTree->SubstituteFormalArguments(ArgMap);
   1452   }
   1453 
   1454   FragTree->setName(getName());
   1455   for (unsigned i = 0, e = Types.size(); i != e; ++i)
   1456     FragTree->UpdateNodeType(i, getExtType(i), TP);
   1457 
   1458   // Transfer in the old predicates.
   1459   for (const TreePredicateFn &Pred : getPredicateFns())
   1460     FragTree->addPredicateFn(Pred);
   1461 
   1462   // Get a new copy of this fragment to stitch into here.
   1463   //delete this;    // FIXME: implement refcounting!
   1464 
   1465   // The fragment we inlined could have recursive inlining that is needed.  See
   1466   // if there are any pattern fragments in it and inline them as needed.
   1467   return FragTree->InlinePatternFragments(TP);
   1468 }
   1469 
   1470 /// getImplicitType - Check to see if the specified record has an implicit
   1471 /// type which should be applied to it.  This will infer the type of register
   1472 /// references from the register file information, for example.
   1473 ///
   1474 /// When Unnamed is set, return the type of a DAG operand with no name, such as
   1475 /// the F8RC register class argument in:
   1476 ///
   1477 ///   (COPY_TO_REGCLASS GPR:$src, F8RC)
   1478 ///
   1479 /// When Unnamed is false, return the type of a named DAG operand such as the
   1480 /// GPR:$src operand above.
   1481 ///
   1482 static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo,
   1483                                      bool NotRegisters,
   1484                                      bool Unnamed,
   1485                                      TreePattern &TP) {
   1486   // Check to see if this is a register operand.
   1487   if (R->isSubClassOf("RegisterOperand")) {
   1488     assert(ResNo == 0 && "Regoperand ref only has one result!");
   1489     if (NotRegisters)
   1490       return EEVT::TypeSet(); // Unknown.
   1491     Record *RegClass = R->getValueAsDef("RegClass");
   1492     const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
   1493     return EEVT::TypeSet(T.getRegisterClass(RegClass).getValueTypes());
   1494   }
   1495 
   1496   // Check to see if this is a register or a register class.
   1497   if (R->isSubClassOf("RegisterClass")) {
   1498     assert(ResNo == 0 && "Regclass ref only has one result!");
   1499     // An unnamed register class represents itself as an i32 immediate, for
   1500     // example on a COPY_TO_REGCLASS instruction.
   1501     if (Unnamed)
   1502       return EEVT::TypeSet(MVT::i32, TP);
   1503 
   1504     // In a named operand, the register class provides the possible set of
   1505     // types.
   1506     if (NotRegisters)
   1507       return EEVT::TypeSet(); // Unknown.
   1508     const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
   1509     return EEVT::TypeSet(T.getRegisterClass(R).getValueTypes());
   1510   }
   1511 
   1512   if (R->isSubClassOf("PatFrag")) {
   1513     assert(ResNo == 0 && "FIXME: PatFrag with multiple results?");
   1514     // Pattern fragment types will be resolved when they are inlined.
   1515     return EEVT::TypeSet(); // Unknown.
   1516   }
   1517 
   1518   if (R->isSubClassOf("Register")) {
   1519     assert(ResNo == 0 && "Registers only produce one result!");
   1520     if (NotRegisters)
   1521       return EEVT::TypeSet(); // Unknown.
   1522     const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
   1523     return EEVT::TypeSet(T.getRegisterVTs(R));
   1524   }
   1525 
   1526   if (R->isSubClassOf("SubRegIndex")) {
   1527     assert(ResNo == 0 && "SubRegisterIndices only produce one result!");
   1528     return EEVT::TypeSet(MVT::i32, TP);
   1529   }
   1530 
   1531   if (R->isSubClassOf("ValueType")) {
   1532     assert(ResNo == 0 && "This node only has one result!");
   1533     // An unnamed VTSDNode represents itself as an MVT::Other immediate.
   1534     //
   1535     //   (sext_inreg GPR:$src, i16)
   1536     //                         ~~~
   1537     if (Unnamed)
   1538       return EEVT::TypeSet(MVT::Other, TP);
   1539     // With a name, the ValueType simply provides the type of the named
   1540     // variable.
   1541     //
   1542     //   (sext_inreg i32:$src, i16)
   1543     //               ~~~~~~~~
   1544     if (NotRegisters)
   1545       return EEVT::TypeSet(); // Unknown.
   1546     return EEVT::TypeSet(getValueType(R), TP);
   1547   }
   1548 
   1549   if (R->isSubClassOf("CondCode")) {
   1550     assert(ResNo == 0 && "This node only has one result!");
   1551     // Using a CondCodeSDNode.
   1552     return EEVT::TypeSet(MVT::Other, TP);
   1553   }
   1554 
   1555   if (R->isSubClassOf("ComplexPattern")) {
   1556     assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?");
   1557     if (NotRegisters)
   1558       return EEVT::TypeSet(); // Unknown.
   1559    return EEVT::TypeSet(TP.getDAGPatterns().getComplexPattern(R).getValueType(),
   1560                          TP);
   1561   }
   1562   if (R->isSubClassOf("PointerLikeRegClass")) {
   1563     assert(ResNo == 0 && "Regclass can only have one result!");
   1564     return EEVT::TypeSet(MVT::iPTR, TP);
   1565   }
   1566 
   1567   if (R->getName() == "node" || R->getName() == "srcvalue" ||
   1568       R->getName() == "zero_reg") {
   1569     // Placeholder.
   1570     return EEVT::TypeSet(); // Unknown.
   1571   }
   1572 
   1573   if (R->isSubClassOf("Operand"))
   1574     return EEVT::TypeSet(getValueType(R->getValueAsDef("Type")));
   1575 
   1576   TP.error("Unknown node flavor used in pattern: " + R->getName());
   1577   return EEVT::TypeSet(MVT::Other, TP);
   1578 }
   1579 
   1580 
   1581 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
   1582 /// CodeGenIntrinsic information for it, otherwise return a null pointer.
   1583 const CodeGenIntrinsic *TreePatternNode::
   1584 getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const {
   1585   if (getOperator() != CDP.get_intrinsic_void_sdnode() &&
   1586       getOperator() != CDP.get_intrinsic_w_chain_sdnode() &&
   1587       getOperator() != CDP.get_intrinsic_wo_chain_sdnode())
   1588     return nullptr;
   1589 
   1590   unsigned IID = cast<IntInit>(getChild(0)->getLeafValue())->getValue();
   1591   return &CDP.getIntrinsicInfo(IID);
   1592 }
   1593 
   1594 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
   1595 /// return the ComplexPattern information, otherwise return null.
   1596 const ComplexPattern *
   1597 TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const {
   1598   Record *Rec;
   1599   if (isLeaf()) {
   1600     DefInit *DI = dyn_cast<DefInit>(getLeafValue());
   1601     if (!DI)
   1602       return nullptr;
   1603     Rec = DI->getDef();
   1604   } else
   1605     Rec = getOperator();
   1606 
   1607   if (!Rec->isSubClassOf("ComplexPattern"))
   1608     return nullptr;
   1609   return &CGP.getComplexPattern(Rec);
   1610 }
   1611 
   1612 unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const {
   1613   // A ComplexPattern specifically declares how many results it fills in.
   1614   if (const ComplexPattern *CP = getComplexPatternInfo(CGP))
   1615     return CP->getNumOperands();
   1616 
   1617   // If MIOperandInfo is specified, that gives the count.
   1618   if (isLeaf()) {
   1619     DefInit *DI = dyn_cast<DefInit>(getLeafValue());
   1620     if (DI && DI->getDef()->isSubClassOf("Operand")) {
   1621       DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo");
   1622       if (MIOps->getNumArgs())
   1623         return MIOps->getNumArgs();
   1624     }
   1625   }
   1626 
   1627   // Otherwise there is just one result.
   1628   return 1;
   1629 }
   1630 
   1631 /// NodeHasProperty - Return true if this node has the specified property.
   1632 bool TreePatternNode::NodeHasProperty(SDNP Property,
   1633                                       const CodeGenDAGPatterns &CGP) const {
   1634   if (isLeaf()) {
   1635     if (const ComplexPattern *CP = getComplexPatternInfo(CGP))
   1636       return CP->hasProperty(Property);
   1637     return false;
   1638   }
   1639 
   1640   Record *Operator = getOperator();
   1641   if (!Operator->isSubClassOf("SDNode")) return false;
   1642 
   1643   return CGP.getSDNodeInfo(Operator).hasProperty(Property);
   1644 }
   1645 
   1646 
   1647 
   1648 
   1649 /// TreeHasProperty - Return true if any node in this tree has the specified
   1650 /// property.
   1651 bool TreePatternNode::TreeHasProperty(SDNP Property,
   1652                                       const CodeGenDAGPatterns &CGP) const {
   1653   if (NodeHasProperty(Property, CGP))
   1654     return true;
   1655   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1656     if (getChild(i)->TreeHasProperty(Property, CGP))
   1657       return true;
   1658   return false;
   1659 }
   1660 
   1661 /// isCommutativeIntrinsic - Return true if the node corresponds to a
   1662 /// commutative intrinsic.
   1663 bool
   1664 TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const {
   1665   if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP))
   1666     return Int->isCommutative;
   1667   return false;
   1668 }
   1669 
   1670 static bool isOperandClass(const TreePatternNode *N, StringRef Class) {
   1671   if (!N->isLeaf())
   1672     return N->getOperator()->isSubClassOf(Class);
   1673 
   1674   DefInit *DI = dyn_cast<DefInit>(N->getLeafValue());
   1675   if (DI && DI->getDef()->isSubClassOf(Class))
   1676     return true;
   1677 
   1678   return false;
   1679 }
   1680 
   1681 static void emitTooManyOperandsError(TreePattern &TP,
   1682                                      StringRef InstName,
   1683                                      unsigned Expected,
   1684                                      unsigned Actual) {
   1685   TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) +
   1686            " operands but expected only " + Twine(Expected) + "!");
   1687 }
   1688 
   1689 static void emitTooFewOperandsError(TreePattern &TP,
   1690                                     StringRef InstName,
   1691                                     unsigned Actual) {
   1692   TP.error("Instruction '" + InstName +
   1693            "' expects more than the provided " + Twine(Actual) + " operands!");
   1694 }
   1695 
   1696 /// ApplyTypeConstraints - Apply all of the type constraints relevant to
   1697 /// this node and its children in the tree.  This returns true if it makes a
   1698 /// change, false otherwise.  If a type contradiction is found, flag an error.
   1699 bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
   1700   if (TP.hasError())
   1701     return false;
   1702 
   1703   CodeGenDAGPatterns &CDP = TP.getDAGPatterns();
   1704   if (isLeaf()) {
   1705     if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) {
   1706       // If it's a regclass or something else known, include the type.
   1707       bool MadeChange = false;
   1708       for (unsigned i = 0, e = Types.size(); i != e; ++i)
   1709         MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i,
   1710                                                         NotRegisters,
   1711                                                         !hasName(), TP), TP);
   1712       return MadeChange;
   1713     }
   1714 
   1715     if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) {
   1716       assert(Types.size() == 1 && "Invalid IntInit");
   1717 
   1718       // Int inits are always integers. :)
   1719       bool MadeChange = Types[0].EnforceInteger(TP);
   1720 
   1721       if (!Types[0].isConcrete())
   1722         return MadeChange;
   1723 
   1724       MVT::SimpleValueType VT = getType(0);
   1725       if (VT == MVT::iPTR || VT == MVT::iPTRAny)
   1726         return MadeChange;
   1727 
   1728       unsigned Size = MVT(VT).getSizeInBits();
   1729       // Make sure that the value is representable for this type.
   1730       if (Size >= 32) return MadeChange;
   1731 
   1732       // Check that the value doesn't use more bits than we have. It must either
   1733       // be a sign- or zero-extended equivalent of the original.
   1734       int64_t SignBitAndAbove = II->getValue() >> (Size - 1);
   1735       if (SignBitAndAbove == -1 || SignBitAndAbove == 0 || SignBitAndAbove == 1)
   1736         return MadeChange;
   1737 
   1738       TP.error("Integer value '" + itostr(II->getValue()) +
   1739                "' is out of range for type '" + getEnumName(getType(0)) + "'!");
   1740       return false;
   1741     }
   1742     return false;
   1743   }
   1744 
   1745   // special handling for set, which isn't really an SDNode.
   1746   if (getOperator()->getName() == "set") {
   1747     assert(getNumTypes() == 0 && "Set doesn't produce a value");
   1748     assert(getNumChildren() >= 2 && "Missing RHS of a set?");
   1749     unsigned NC = getNumChildren();
   1750 
   1751     TreePatternNode *SetVal = getChild(NC-1);
   1752     bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters);
   1753 
   1754     for (unsigned i = 0; i < NC-1; ++i) {
   1755       TreePatternNode *Child = getChild(i);
   1756       MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters);
   1757 
   1758       // Types of operands must match.
   1759       MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP);
   1760       MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP);
   1761     }
   1762     return MadeChange;
   1763   }
   1764 
   1765   if (getOperator()->getName() == "implicit") {
   1766     assert(getNumTypes() == 0 && "Node doesn't produce a value");
   1767 
   1768     bool MadeChange = false;
   1769     for (unsigned i = 0; i < getNumChildren(); ++i)
   1770       MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
   1771     return MadeChange;
   1772   }
   1773 
   1774   if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {
   1775     bool MadeChange = false;
   1776 
   1777     // Apply the result type to the node.
   1778     unsigned NumRetVTs = Int->IS.RetVTs.size();
   1779     unsigned NumParamVTs = Int->IS.ParamVTs.size();
   1780 
   1781     for (unsigned i = 0, e = NumRetVTs; i != e; ++i)
   1782       MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP);
   1783 
   1784     if (getNumChildren() != NumParamVTs + 1) {
   1785       TP.error("Intrinsic '" + Int->Name + "' expects " +
   1786                utostr(NumParamVTs) + " operands, not " +
   1787                utostr(getNumChildren() - 1) + " operands!");
   1788       return false;
   1789     }
   1790 
   1791     // Apply type info to the intrinsic ID.
   1792     MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP);
   1793 
   1794     for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) {
   1795       MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters);
   1796 
   1797       MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i];
   1798       assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case");
   1799       MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP);
   1800     }
   1801     return MadeChange;
   1802   }
   1803 
   1804   if (getOperator()->isSubClassOf("SDNode")) {
   1805     const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator());
   1806 
   1807     // Check that the number of operands is sane.  Negative operands -> varargs.
   1808     if (NI.getNumOperands() >= 0 &&
   1809         getNumChildren() != (unsigned)NI.getNumOperands()) {
   1810       TP.error(getOperator()->getName() + " node requires exactly " +
   1811                itostr(NI.getNumOperands()) + " operands!");
   1812       return false;
   1813     }
   1814 
   1815     bool MadeChange = NI.ApplyTypeConstraints(this, TP);
   1816     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1817       MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
   1818     return MadeChange;
   1819   }
   1820 
   1821   if (getOperator()->isSubClassOf("Instruction")) {
   1822     const DAGInstruction &Inst = CDP.getInstruction(getOperator());
   1823     CodeGenInstruction &InstInfo =
   1824       CDP.getTargetInfo().getInstruction(getOperator());
   1825 
   1826     bool MadeChange = false;
   1827 
   1828     // Apply the result types to the node, these come from the things in the
   1829     // (outs) list of the instruction.
   1830     unsigned NumResultsToAdd = std::min(InstInfo.Operands.NumDefs,
   1831                                         Inst.getNumResults());
   1832     for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo)
   1833       MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP);
   1834 
   1835     // If the instruction has implicit defs, we apply the first one as a result.
   1836     // FIXME: This sucks, it should apply all implicit defs.
   1837     if (!InstInfo.ImplicitDefs.empty()) {
   1838       unsigned ResNo = NumResultsToAdd;
   1839 
   1840       // FIXME: Generalize to multiple possible types and multiple possible
   1841       // ImplicitDefs.
   1842       MVT::SimpleValueType VT =
   1843         InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo());
   1844 
   1845       if (VT != MVT::Other)
   1846         MadeChange |= UpdateNodeType(ResNo, VT, TP);
   1847     }
   1848 
   1849     // If this is an INSERT_SUBREG, constrain the source and destination VTs to
   1850     // be the same.
   1851     if (getOperator()->getName() == "INSERT_SUBREG") {
   1852       assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled");
   1853       MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP);
   1854       MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP);
   1855     } else if (getOperator()->getName() == "REG_SEQUENCE") {
   1856       // We need to do extra, custom typechecking for REG_SEQUENCE since it is
   1857       // variadic.
   1858 
   1859       unsigned NChild = getNumChildren();
   1860       if (NChild < 3) {
   1861         TP.error("REG_SEQUENCE requires at least 3 operands!");
   1862         return false;
   1863       }
   1864 
   1865       if (NChild % 2 == 0) {
   1866         TP.error("REG_SEQUENCE requires an odd number of operands!");
   1867         return false;
   1868       }
   1869 
   1870       if (!isOperandClass(getChild(0), "RegisterClass")) {
   1871         TP.error("REG_SEQUENCE requires a RegisterClass for first operand!");
   1872         return false;
   1873       }
   1874 
   1875       for (unsigned I = 1; I < NChild; I += 2) {
   1876         TreePatternNode *SubIdxChild = getChild(I + 1);
   1877         if (!isOperandClass(SubIdxChild, "SubRegIndex")) {
   1878           TP.error("REG_SEQUENCE requires a SubRegIndex for operand " +
   1879                    itostr(I + 1) + "!");
   1880           return false;
   1881         }
   1882       }
   1883     }
   1884 
   1885     unsigned ChildNo = 0;
   1886     for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) {
   1887       Record *OperandNode = Inst.getOperand(i);
   1888 
   1889       // If the instruction expects a predicate or optional def operand, we
   1890       // codegen this by setting the operand to it's default value if it has a
   1891       // non-empty DefaultOps field.
   1892       if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&
   1893           !CDP.getDefaultOperand(OperandNode).DefaultOps.empty())
   1894         continue;
   1895 
   1896       // Verify that we didn't run out of provided operands.
   1897       if (ChildNo >= getNumChildren()) {
   1898         emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren());
   1899         return false;
   1900       }
   1901 
   1902       TreePatternNode *Child = getChild(ChildNo++);
   1903       unsigned ChildResNo = 0;  // Instructions always use res #0 of their op.
   1904 
   1905       // If the operand has sub-operands, they may be provided by distinct
   1906       // child patterns, so attempt to match each sub-operand separately.
   1907       if (OperandNode->isSubClassOf("Operand")) {
   1908         DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo");
   1909         if (unsigned NumArgs = MIOpInfo->getNumArgs()) {
   1910           // But don't do that if the whole operand is being provided by
   1911           // a single ComplexPattern-related Operand.
   1912 
   1913           if (Child->getNumMIResults(CDP) < NumArgs) {
   1914             // Match first sub-operand against the child we already have.
   1915             Record *SubRec = cast<DefInit>(MIOpInfo->getArg(0))->getDef();
   1916             MadeChange |=
   1917               Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP);
   1918 
   1919             // And the remaining sub-operands against subsequent children.
   1920             for (unsigned Arg = 1; Arg < NumArgs; ++Arg) {
   1921               if (ChildNo >= getNumChildren()) {
   1922                 emitTooFewOperandsError(TP, getOperator()->getName(),
   1923                                         getNumChildren());
   1924                 return false;
   1925               }
   1926               Child = getChild(ChildNo++);
   1927 
   1928               SubRec = cast<DefInit>(MIOpInfo->getArg(Arg))->getDef();
   1929               MadeChange |=
   1930                 Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP);
   1931             }
   1932             continue;
   1933           }
   1934         }
   1935       }
   1936 
   1937       // If we didn't match by pieces above, attempt to match the whole
   1938       // operand now.
   1939       MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP);
   1940     }
   1941 
   1942     if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) {
   1943       emitTooManyOperandsError(TP, getOperator()->getName(),
   1944                                ChildNo, getNumChildren());
   1945       return false;
   1946     }
   1947 
   1948     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   1949       MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
   1950     return MadeChange;
   1951   }
   1952 
   1953   if (getOperator()->isSubClassOf("ComplexPattern")) {
   1954     bool MadeChange = false;
   1955 
   1956     for (unsigned i = 0; i < getNumChildren(); ++i)
   1957       MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
   1958 
   1959     return MadeChange;
   1960   }
   1961 
   1962   assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!");
   1963 
   1964   // Node transforms always take one operand.
   1965   if (getNumChildren() != 1) {
   1966     TP.error("Node transform '" + getOperator()->getName() +
   1967              "' requires one operand!");
   1968     return false;
   1969   }
   1970 
   1971   bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters);
   1972 
   1973 
   1974   // If either the output or input of the xform does not have exact
   1975   // type info. We assume they must be the same. Otherwise, it is perfectly
   1976   // legal to transform from one type to a completely different type.
   1977 #if 0
   1978   if (!hasTypeSet() || !getChild(0)->hasTypeSet()) {
   1979     bool MadeChange = UpdateNodeType(getChild(0)->getExtType(), TP);
   1980     MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP);
   1981     return MadeChange;
   1982   }
   1983 #endif
   1984   return MadeChange;
   1985 }
   1986 
   1987 /// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the
   1988 /// RHS of a commutative operation, not the on LHS.
   1989 static bool OnlyOnRHSOfCommutative(TreePatternNode *N) {
   1990   if (!N->isLeaf() && N->getOperator()->getName() == "imm")
   1991     return true;
   1992   if (N->isLeaf() && isa<IntInit>(N->getLeafValue()))
   1993     return true;
   1994   return false;
   1995 }
   1996 
   1997 
   1998 /// canPatternMatch - If it is impossible for this pattern to match on this
   1999 /// target, fill in Reason and return false.  Otherwise, return true.  This is
   2000 /// used as a sanity check for .td files (to prevent people from writing stuff
   2001 /// that can never possibly work), and to prevent the pattern permuter from
   2002 /// generating stuff that is useless.
   2003 bool TreePatternNode::canPatternMatch(std::string &Reason,
   2004                                       const CodeGenDAGPatterns &CDP) {
   2005   if (isLeaf()) return true;
   2006 
   2007   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
   2008     if (!getChild(i)->canPatternMatch(Reason, CDP))
   2009       return false;
   2010 
   2011   // If this is an intrinsic, handle cases that would make it not match.  For
   2012   // example, if an operand is required to be an immediate.
   2013   if (getOperator()->isSubClassOf("Intrinsic")) {
   2014     // TODO:
   2015     return true;
   2016   }
   2017 
   2018   if (getOperator()->isSubClassOf("ComplexPattern"))
   2019     return true;
   2020 
   2021   // If this node is a commutative operator, check that the LHS isn't an
   2022   // immediate.
   2023   const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator());
   2024   bool isCommIntrinsic = isCommutativeIntrinsic(CDP);
   2025   if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
   2026     // Scan all of the operands of the node and make sure that only the last one
   2027     // is a constant node, unless the RHS also is.
   2028     if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) {
   2029       bool Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id.
   2030       for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i)
   2031         if (OnlyOnRHSOfCommutative(getChild(i))) {
   2032           Reason="Immediate value must be on the RHS of commutative operators!";
   2033           return false;
   2034         }
   2035     }
   2036   }
   2037 
   2038   return true;
   2039 }
   2040 
   2041 //===----------------------------------------------------------------------===//
   2042 // TreePattern implementation
   2043 //
   2044 
   2045 TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
   2046                          CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
   2047                          isInputPattern(isInput), HasError(false) {
   2048   for (Init *I : RawPat->getValues())
   2049     Trees.push_back(ParseTreePattern(I, ""));
   2050 }
   2051 
   2052 TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
   2053                          CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
   2054                          isInputPattern(isInput), HasError(false) {
   2055   Trees.push_back(ParseTreePattern(Pat, ""));
   2056 }
   2057 
   2058 TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
   2059                          CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
   2060                          isInputPattern(isInput), HasError(false) {
   2061   Trees.push_back(Pat);
   2062 }
   2063 
   2064 void TreePattern::error(const Twine &Msg) {
   2065   if (HasError)
   2066     return;
   2067   dump();
   2068   PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg);
   2069   HasError = true;
   2070 }
   2071 
   2072 void TreePattern::ComputeNamedNodes() {
   2073   for (TreePatternNode *Tree : Trees)
   2074     ComputeNamedNodes(Tree);
   2075 }
   2076 
   2077 void TreePattern::ComputeNamedNodes(TreePatternNode *N) {
   2078   if (!N->getName().empty())
   2079     NamedNodes[N->getName()].push_back(N);
   2080 
   2081   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
   2082     ComputeNamedNodes(N->getChild(i));
   2083 }
   2084 
   2085 
   2086 TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){
   2087   if (DefInit *DI = dyn_cast<DefInit>(TheInit)) {
   2088     Record *R = DI->getDef();
   2089 
   2090     // Direct reference to a leaf DagNode or PatFrag?  Turn it into a
   2091     // TreePatternNode of its own.  For example:
   2092     ///   (foo GPR, imm) -> (foo GPR, (imm))
   2093     if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag"))
   2094       return ParseTreePattern(
   2095         DagInit::get(DI, "",
   2096                      std::vector<std::pair<Init*, std::string> >()),
   2097         OpName);
   2098 
   2099     // Input argument?
   2100     TreePatternNode *Res = new TreePatternNode(DI, 1);
   2101     if (R->getName() == "node" && !OpName.empty()) {
   2102       if (OpName.empty())
   2103         error("'node' argument requires a name to match with operand list");
   2104       Args.push_back(OpName);
   2105     }
   2106 
   2107     Res->setName(OpName);
   2108     return Res;
   2109   }
   2110 
   2111   // ?:$name or just $name.
   2112   if (isa<UnsetInit>(TheInit)) {
   2113     if (OpName.empty())
   2114       error("'?' argument requires a name to match with operand list");
   2115     TreePatternNode *Res = new TreePatternNode(TheInit, 1);
   2116     Args.push_back(OpName);
   2117     Res->setName(OpName);
   2118     return Res;
   2119   }
   2120 
   2121   if (IntInit *II = dyn_cast<IntInit>(TheInit)) {
   2122     if (!OpName.empty())
   2123       error("Constant int argument should not have a name!");
   2124     return new TreePatternNode(II, 1);
   2125   }
   2126 
   2127   if (BitsInit *BI = dyn_cast<BitsInit>(TheInit)) {
   2128     // Turn this into an IntInit.
   2129     Init *II = BI->convertInitializerTo(IntRecTy::get());
   2130     if (!II || !isa<IntInit>(II))
   2131       error("Bits value must be constants!");
   2132     return ParseTreePattern(II, OpName);
   2133   }
   2134 
   2135   DagInit *Dag = dyn_cast<DagInit>(TheInit);
   2136   if (!Dag) {
   2137     TheInit->dump();
   2138     error("Pattern has unexpected init kind!");
   2139   }
   2140   DefInit *OpDef = dyn_cast<DefInit>(Dag->getOperator());
   2141   if (!OpDef) error("Pattern has unexpected operator type!");
   2142   Record *Operator = OpDef->getDef();
   2143 
   2144   if (Operator->isSubClassOf("ValueType")) {
   2145     // If the operator is a ValueType, then this must be "type cast" of a leaf
   2146     // node.
   2147     if (Dag->getNumArgs() != 1)
   2148       error("Type cast only takes one operand!");
   2149 
   2150     TreePatternNode *New = ParseTreePattern(Dag->getArg(0), Dag->getArgName(0));
   2151 
   2152     // Apply the type cast.
   2153     assert(New->getNumTypes() == 1 && "FIXME: Unhandled");
   2154     New->UpdateNodeType(0, getValueType(Operator), *this);
   2155 
   2156     if (!OpName.empty())
   2157       error("ValueType cast should not have a name!");
   2158     return New;
   2159   }
   2160 
   2161   // Verify that this is something that makes sense for an operator.
   2162   if (!Operator->isSubClassOf("PatFrag") &&
   2163       !Operator->isSubClassOf("SDNode") &&
   2164       !Operator->isSubClassOf("Instruction") &&
   2165       !Operator->isSubClassOf("SDNodeXForm") &&
   2166       !Operator->isSubClassOf("Intrinsic") &&
   2167       !Operator->isSubClassOf("ComplexPattern") &&
   2168       Operator->getName() != "set" &&
   2169       Operator->getName() != "implicit")
   2170     error("Unrecognized node '" + Operator->getName() + "'!");
   2171 
   2172   //  Check to see if this is something that is illegal in an input pattern.
   2173   if (isInputPattern) {
   2174     if (Operator->isSubClassOf("Instruction") ||
   2175         Operator->isSubClassOf("SDNodeXForm"))
   2176       error("Cannot use '" + Operator->getName() + "' in an input pattern!");
   2177   } else {
   2178     if (Operator->isSubClassOf("Intrinsic"))
   2179       error("Cannot use '" + Operator->getName() + "' in an output pattern!");
   2180 
   2181     if (Operator->isSubClassOf("SDNode") &&
   2182         Operator->getName() != "imm" &&
   2183         Operator->getName() != "fpimm" &&
   2184         Operator->getName() != "tglobaltlsaddr" &&
   2185         Operator->getName() != "tconstpool" &&
   2186         Operator->getName() != "tjumptable" &&
   2187         Operator->getName() != "tframeindex" &&
   2188         Operator->getName() != "texternalsym" &&
   2189         Operator->getName() != "tblockaddress" &&
   2190         Operator->getName() != "tglobaladdr" &&
   2191         Operator->getName() != "bb" &&
   2192         Operator->getName() != "vt" &&
   2193         Operator->getName() != "mcsym")
   2194       error("Cannot use '" + Operator->getName() + "' in an output pattern!");
   2195   }
   2196 
   2197   std::vector<TreePatternNode*> Children;
   2198 
   2199   // Parse all the operands.
   2200   for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i)
   2201     Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgName(i)));
   2202 
   2203   // If the operator is an intrinsic, then this is just syntactic sugar for for
   2204   // (intrinsic_* <number>, ..children..).  Pick the right intrinsic node, and
   2205   // convert the intrinsic name to a number.
   2206   if (Operator->isSubClassOf("Intrinsic")) {
   2207     const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator);
   2208     unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1;
   2209 
   2210     // If this intrinsic returns void, it must have side-effects and thus a
   2211     // chain.
   2212     if (Int.IS.RetVTs.empty())
   2213       Operator = getDAGPatterns().get_intrinsic_void_sdnode();
   2214     else if (Int.ModRef != CodeGenIntrinsic::NoMem)
   2215       // Has side-effects, requires chain.
   2216       Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode();
   2217     else // Otherwise, no chain.
   2218       Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode();
   2219 
   2220     TreePatternNode *IIDNode = new TreePatternNode(IntInit::get(IID), 1);
   2221     Children.insert(Children.begin(), IIDNode);
   2222   }
   2223 
   2224   if (Operator->isSubClassOf("ComplexPattern")) {
   2225     for (unsigned i = 0; i < Children.size(); ++i) {
   2226       TreePatternNode *Child = Children[i];
   2227 
   2228       if (Child->getName().empty())
   2229         error("All arguments to a ComplexPattern must be named");
   2230 
   2231       // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)"
   2232       // and "(MY_PAT $b, $a)" should not be allowed in the same pattern;
   2233       // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)".
   2234       auto OperandId = std::make_pair(Operator, i);
   2235       auto PrevOp = ComplexPatternOperands.find(Child->getName());
   2236       if (PrevOp != ComplexPatternOperands.end()) {
   2237         if (PrevOp->getValue() != OperandId)
   2238           error("All ComplexPattern operands must appear consistently: "
   2239                 "in the same order in just one ComplexPattern instance.");
   2240       } else
   2241         ComplexPatternOperands[Child->getName()] = OperandId;
   2242     }
   2243   }
   2244 
   2245   unsigned NumResults = GetNumNodeResults(Operator, CDP);
   2246   TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults);
   2247   Result->setName(OpName);
   2248 
   2249   if (!Dag->getName().empty()) {
   2250     assert(Result->getName().empty());
   2251     Result->setName(Dag->getName());
   2252   }
   2253   return Result;
   2254 }
   2255 
   2256 /// SimplifyTree - See if we can simplify this tree to eliminate something that
   2257 /// will never match in favor of something obvious that will.  This is here
   2258 /// strictly as a convenience to target authors because it allows them to write
   2259 /// more type generic things and have useless type casts fold away.
   2260 ///
   2261 /// This returns true if any change is made.
   2262 static bool SimplifyTree(TreePatternNode *&N) {
   2263   if (N->isLeaf())
   2264     return false;
   2265 
   2266   // If we have a bitconvert with a resolved type and if the source and
   2267   // destination types are the same, then the bitconvert is useless, remove it.
   2268   if (N->getOperator()->getName() == "bitconvert" &&
   2269       N->getExtType(0).isConcrete() &&
   2270       N->getExtType(0) == N->getChild(0)->getExtType(0) &&
   2271       N->getName().empty()) {
   2272     N = N->getChild(0);
   2273     SimplifyTree(N);
   2274     return true;
   2275   }
   2276 
   2277   // Walk all children.
   2278   bool MadeChange = false;
   2279   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
   2280     TreePatternNode *Child = N->getChild(i);
   2281     MadeChange |= SimplifyTree(Child);
   2282     N->setChild(i, Child);
   2283   }
   2284   return MadeChange;
   2285 }
   2286 
   2287 
   2288 
   2289 /// InferAllTypes - Infer/propagate as many types throughout the expression
   2290 /// patterns as possible.  Return true if all types are inferred, false
   2291 /// otherwise.  Flags an error if a type contradiction is found.
   2292 bool TreePattern::
   2293 InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) {
   2294   if (NamedNodes.empty())
   2295     ComputeNamedNodes();
   2296 
   2297   bool MadeChange = true;
   2298   while (MadeChange) {
   2299     MadeChange = false;
   2300     for (TreePatternNode *Tree : Trees) {
   2301       MadeChange |= Tree->ApplyTypeConstraints(*this, false);
   2302       MadeChange |= SimplifyTree(Tree);
   2303     }
   2304 
   2305     // If there are constraints on our named nodes, apply them.
   2306     for (auto &Entry : NamedNodes) {
   2307       SmallVectorImpl<TreePatternNode*> &Nodes = Entry.second;
   2308 
   2309       // If we have input named node types, propagate their types to the named
   2310       // values here.
   2311       if (InNamedTypes) {
   2312         if (!InNamedTypes->count(Entry.getKey())) {
   2313           error("Node '" + std::string(Entry.getKey()) +
   2314                 "' in output pattern but not input pattern");
   2315           return true;
   2316         }
   2317 
   2318         const SmallVectorImpl<TreePatternNode*> &InNodes =
   2319           InNamedTypes->find(Entry.getKey())->second;
   2320 
   2321         // The input types should be fully resolved by now.
   2322         for (TreePatternNode *Node : Nodes) {
   2323           // If this node is a register class, and it is the root of the pattern
   2324           // then we're mapping something onto an input register.  We allow
   2325           // changing the type of the input register in this case.  This allows
   2326           // us to match things like:
   2327           //  def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>;
   2328           if (Node == Trees[0] && Node->isLeaf()) {
   2329             DefInit *DI = dyn_cast<DefInit>(Node->getLeafValue());
   2330             if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||
   2331                        DI->getDef()->isSubClassOf("RegisterOperand")))
   2332               continue;
   2333           }
   2334 
   2335           assert(Node->getNumTypes() == 1 &&
   2336                  InNodes[0]->getNumTypes() == 1 &&
   2337                  "FIXME: cannot name multiple result nodes yet");
   2338           MadeChange |= Node->UpdateNodeType(0, InNodes[0]->getExtType(0),
   2339                                              *this);
   2340         }
   2341       }
   2342 
   2343       // If there are multiple nodes with the same name, they must all have the
   2344       // same type.
   2345       if (Entry.second.size() > 1) {
   2346         for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) {
   2347           TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1];
   2348           assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 &&
   2349                  "FIXME: cannot name multiple result nodes yet");
   2350 
   2351           MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this);
   2352           MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this);
   2353         }
   2354       }
   2355     }
   2356   }
   2357 
   2358   bool HasUnresolvedTypes = false;
   2359   for (const TreePatternNode *Tree : Trees)
   2360     HasUnresolvedTypes |= Tree->ContainsUnresolvedType();
   2361   return !HasUnresolvedTypes;
   2362 }
   2363 
   2364 void TreePattern::print(raw_ostream &OS) const {
   2365   OS << getRecord()->getName();
   2366   if (!Args.empty()) {
   2367     OS << "(" << Args[0];
   2368     for (unsigned i = 1, e = Args.size(); i != e; ++i)
   2369       OS << ", " << Args[i];
   2370     OS << ")";
   2371   }
   2372   OS << ": ";
   2373 
   2374   if (Trees.size() > 1)
   2375     OS << "[\n";
   2376   for (const TreePatternNode *Tree : Trees) {
   2377     OS << "\t";
   2378     Tree->print(OS);
   2379     OS << "\n";
   2380   }
   2381 
   2382   if (Trees.size() > 1)
   2383     OS << "]\n";
   2384 }
   2385 
   2386 void TreePattern::dump() const { print(errs()); }
   2387 
   2388 //===----------------------------------------------------------------------===//
   2389 // CodeGenDAGPatterns implementation
   2390 //
   2391 
   2392 CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) :
   2393   Records(R), Target(R) {
   2394 
   2395   Intrinsics = LoadIntrinsics(Records, false);
   2396   TgtIntrinsics = LoadIntrinsics(Records, true);
   2397   ParseNodeInfo();
   2398   ParseNodeTransforms();
   2399   ParseComplexPatterns();
   2400   ParsePatternFragments();
   2401   ParseDefaultOperands();
   2402   ParseInstructions();
   2403   ParsePatternFragments(/*OutFrags*/true);
   2404   ParsePatterns();
   2405 
   2406   // Generate variants.  For example, commutative patterns can match
   2407   // multiple ways.  Add them to PatternsToMatch as well.
   2408   GenerateVariants();
   2409 
   2410   // Infer instruction flags.  For example, we can detect loads,
   2411   // stores, and side effects in many cases by examining an
   2412   // instruction's pattern.
   2413   InferInstructionFlags();
   2414 
   2415   // Verify that instruction flags match the patterns.
   2416   VerifyInstructionFlags();
   2417 }
   2418 
   2419 Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const {
   2420   Record *N = Records.getDef(Name);
   2421   if (!N || !N->isSubClassOf("SDNode"))
   2422     PrintFatalError("Error getting SDNode '" + Name + "'!");
   2423 
   2424   return N;
   2425 }
   2426 
   2427 // Parse all of the SDNode definitions for the target, populating SDNodes.
   2428 void CodeGenDAGPatterns::ParseNodeInfo() {
   2429   std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode");
   2430   while (!Nodes.empty()) {
   2431     SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back()));
   2432     Nodes.pop_back();
   2433   }
   2434 
   2435   // Get the builtin intrinsic nodes.
   2436   intrinsic_void_sdnode     = getSDNodeNamed("intrinsic_void");
   2437   intrinsic_w_chain_sdnode  = getSDNodeNamed("intrinsic_w_chain");
   2438   intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain");
   2439 }
   2440 
   2441 /// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms
   2442 /// map, and emit them to the file as functions.
   2443 void CodeGenDAGPatterns::ParseNodeTransforms() {
   2444   std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm");
   2445   while (!Xforms.empty()) {
   2446     Record *XFormNode = Xforms.back();
   2447     Record *SDNode = XFormNode->getValueAsDef("Opcode");
   2448     std::string Code = XFormNode->getValueAsString("XFormFunction");
   2449     SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code)));
   2450 
   2451     Xforms.pop_back();
   2452   }
   2453 }
   2454 
   2455 void CodeGenDAGPatterns::ParseComplexPatterns() {
   2456   std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern");
   2457   while (!AMs.empty()) {
   2458     ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back()));
   2459     AMs.pop_back();
   2460   }
   2461 }
   2462 
   2463 
   2464 /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
   2465 /// file, building up the PatternFragments map.  After we've collected them all,
   2466 /// inline fragments together as necessary, so that there are no references left
   2467 /// inside a pattern fragment to a pattern fragment.
   2468 ///
   2469 void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {
   2470   std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
   2471 
   2472   // First step, parse all of the fragments.
   2473   for (Record *Frag : Fragments) {
   2474     if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
   2475       continue;
   2476 
   2477     DagInit *Tree = Frag->getValueAsDag("Fragment");
   2478     TreePattern *P =
   2479         (PatternFragments[Frag] = llvm::make_unique<TreePattern>(
   2480              Frag, Tree, !Frag->isSubClassOf("OutPatFrag"),
   2481              *this)).get();
   2482 
   2483     // Validate the argument list, converting it to set, to discard duplicates.
   2484     std::vector<std::string> &Args = P->getArgList();
   2485     std::set<std::string> OperandsSet(Args.begin(), Args.end());
   2486 
   2487     if (OperandsSet.count(""))
   2488       P->error("Cannot have unnamed 'node' values in pattern fragment!");
   2489 
   2490     // Parse the operands list.
   2491     DagInit *OpsList = Frag->getValueAsDag("Operands");
   2492     DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator());
   2493     // Special cases: ops == outs == ins. Different names are used to
   2494     // improve readability.
   2495     if (!OpsOp ||
   2496         (OpsOp->getDef()->getName() != "ops" &&
   2497          OpsOp->getDef()->getName() != "outs" &&
   2498          OpsOp->getDef()->getName() != "ins"))
   2499       P->error("Operands list should start with '(ops ... '!");
   2500 
   2501     // Copy over the arguments.
   2502     Args.clear();
   2503     for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) {
   2504       if (!isa<DefInit>(OpsList->getArg(j)) ||
   2505           cast<DefInit>(OpsList->getArg(j))->getDef()->getName() != "node")
   2506         P->error("Operands list should all be 'node' values.");
   2507       if (OpsList->getArgName(j).empty())
   2508         P->error("Operands list should have names for each operand!");
   2509       if (!OperandsSet.count(OpsList->getArgName(j)))
   2510         P->error("'" + OpsList->getArgName(j) +
   2511                  "' does not occur in pattern or was multiply specified!");
   2512       OperandsSet.erase(OpsList->getArgName(j));
   2513       Args.push_back(OpsList->getArgName(j));
   2514     }
   2515 
   2516     if (!OperandsSet.empty())
   2517       P->error("Operands list does not contain an entry for operand '" +
   2518                *OperandsSet.begin() + "'!");
   2519 
   2520     // If there is a code init for this fragment, keep track of the fact that
   2521     // this fragment uses it.
   2522     TreePredicateFn PredFn(P);
   2523     if (!PredFn.isAlwaysTrue())
   2524       P->getOnlyTree()->addPredicateFn(PredFn);
   2525 
   2526     // If there is a node transformation corresponding to this, keep track of
   2527     // it.
   2528     Record *Transform = Frag->getValueAsDef("OperandTransform");
   2529     if (!getSDNodeTransform(Transform).second.empty())    // not noop xform?
   2530       P->getOnlyTree()->setTransformFn(Transform);
   2531   }
   2532 
   2533   // Now that we've parsed all of the tree fragments, do a closure on them so
   2534   // that there are not references to PatFrags left inside of them.
   2535   for (Record *Frag : Fragments) {
   2536     if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
   2537       continue;
   2538 
   2539     TreePattern &ThePat = *PatternFragments[Frag];
   2540     ThePat.InlinePatternFragments();
   2541 
   2542     // Infer as many types as possible.  Don't worry about it if we don't infer
   2543     // all of them, some may depend on the inputs of the pattern.
   2544     ThePat.InferAllTypes();
   2545     ThePat.resetError();
   2546 
   2547     // If debugging, print out the pattern fragment result.
   2548     DEBUG(ThePat.dump());
   2549   }
   2550 }
   2551 
   2552 void CodeGenDAGPatterns::ParseDefaultOperands() {
   2553   std::vector<Record*> DefaultOps;
   2554   DefaultOps = Records.getAllDerivedDefinitions("OperandWithDefaultOps");
   2555 
   2556   // Find some SDNode.
   2557   assert(!SDNodes.empty() && "No SDNodes parsed?");
   2558   Init *SomeSDNode = DefInit::get(SDNodes.begin()->first);
   2559 
   2560   for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) {
   2561     DagInit *DefaultInfo = DefaultOps[i]->getValueAsDag("DefaultOps");
   2562 
   2563     // Clone the DefaultInfo dag node, changing the operator from 'ops' to
   2564     // SomeSDnode so that we can parse this.
   2565     std::vector<std::pair<Init*, std::string> > Ops;
   2566     for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op)
   2567       Ops.push_back(std::make_pair(DefaultInfo->getArg(op),
   2568                                    DefaultInfo->getArgName(op)));
   2569     DagInit *DI = DagInit::get(SomeSDNode, "", Ops);
   2570 
   2571     // Create a TreePattern to parse this.
   2572     TreePattern P(DefaultOps[i], DI, false, *this);
   2573     assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!");
   2574 
   2575     // Copy the operands over into a DAGDefaultOperand.
   2576     DAGDefaultOperand DefaultOpInfo;
   2577 
   2578     TreePatternNode *T = P.getTree(0);
   2579     for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) {
   2580       TreePatternNode *TPN = T->getChild(op);
   2581       while (TPN->ApplyTypeConstraints(P, false))
   2582         /* Resolve all types */;
   2583 
   2584       if (TPN->ContainsUnresolvedType()) {
   2585         PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" +
   2586                         DefaultOps[i]->getName() +
   2587                         "' doesn't have a concrete type!");
   2588       }
   2589       DefaultOpInfo.DefaultOps.push_back(TPN);
   2590     }
   2591 
   2592     // Insert it into the DefaultOperands map so we can find it later.
   2593     DefaultOperands[DefaultOps[i]] = DefaultOpInfo;
   2594   }
   2595 }
   2596 
   2597 /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an
   2598 /// instruction input.  Return true if this is a real use.
   2599 static bool HandleUse(TreePattern *I, TreePatternNode *Pat,
   2600                       std::map<std::string, TreePatternNode*> &InstInputs) {
   2601   // No name -> not interesting.
   2602   if (Pat->getName().empty()) {
   2603     if (Pat->isLeaf()) {
   2604       DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());
   2605       if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||
   2606                  DI->getDef()->isSubClassOf("RegisterOperand")))
   2607         I->error("Input " + DI->getDef()->getName() + " must be named!");
   2608     }
   2609     return false;
   2610   }
   2611 
   2612   Record *Rec;
   2613   if (Pat->isLeaf()) {
   2614     DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());
   2615     if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!");
   2616     Rec = DI->getDef();
   2617   } else {
   2618     Rec = Pat->getOperator();
   2619   }
   2620 
   2621   // SRCVALUE nodes are ignored.
   2622   if (Rec->getName() == "srcvalue")
   2623     return false;
   2624 
   2625   TreePatternNode *&Slot = InstInputs[Pat->getName()];
   2626   if (!Slot) {
   2627     Slot = Pat;
   2628     return true;
   2629   }
   2630   Record *SlotRec;
   2631   if (Slot->isLeaf()) {
   2632     SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef();
   2633   } else {
   2634     assert(Slot->getNumChildren() == 0 && "can't be a use with children!");
   2635     SlotRec = Slot->getOperator();
   2636   }
   2637 
   2638   // Ensure that the inputs agree if we've already seen this input.
   2639   if (Rec != SlotRec)
   2640     I->error("All $" + Pat->getName() + " inputs must agree with each other");
   2641   if (Slot->getExtTypes() != Pat->getExtTypes())
   2642     I->error("All $" + Pat->getName() + " inputs must agree with each other");
   2643   return true;
   2644 }
   2645 
   2646 /// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
   2647 /// part of "I", the instruction), computing the set of inputs and outputs of
   2648 /// the pattern.  Report errors if we see anything naughty.
   2649 void CodeGenDAGPatterns::
   2650 FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
   2651                             std::map<std::string, TreePatternNode*> &InstInputs,
   2652                             std::map<std::string, TreePatternNode*>&InstResults,
   2653                             std::vector<Record*> &InstImpResults) {
   2654   if (Pat->isLeaf()) {
   2655     bool isUse = HandleUse(I, Pat, InstInputs);
   2656     if (!isUse && Pat->getTransformFn())
   2657       I->error("Cannot specify a transform function for a non-input value!");
   2658     return;
   2659   }
   2660 
   2661   if (Pat->getOperator()->getName() == "implicit") {
   2662     for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
   2663       TreePatternNode *Dest = Pat->getChild(i);
   2664       if (!Dest->isLeaf())
   2665         I->error("implicitly defined value should be a register!");
   2666 
   2667       DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
   2668       if (!Val || !Val->getDef()->isSubClassOf("Register"))
   2669         I->error("implicitly defined value should be a register!");
   2670       InstImpResults.push_back(Val->getDef());
   2671     }
   2672     return;
   2673   }
   2674 
   2675   if (Pat->getOperator()->getName() != "set") {
   2676     // If this is not a set, verify that the children nodes are not void typed,
   2677     // and recurse.
   2678     for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
   2679       if (Pat->getChild(i)->getNumTypes() == 0)
   2680         I->error("Cannot have void nodes inside of patterns!");
   2681       FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults,
   2682                                   InstImpResults);
   2683     }
   2684 
   2685     // If this is a non-leaf node with no children, treat it basically as if
   2686     // it were a leaf.  This handles nodes like (imm).
   2687     bool isUse = HandleUse(I, Pat, InstInputs);
   2688 
   2689     if (!isUse && Pat->getTransformFn())
   2690       I->error("Cannot specify a transform function for a non-input value!");
   2691     return;
   2692   }
   2693 
   2694   // Otherwise, this is a set, validate and collect instruction results.
   2695   if (Pat->getNumChildren() == 0)
   2696     I->error("set requires operands!");
   2697 
   2698   if (Pat->getTransformFn())
   2699     I->error("Cannot specify a transform function on a set node!");
   2700 
   2701   // Check the set destinations.
   2702   unsigned NumDests = Pat->getNumChildren()-1;
   2703   for (unsigned i = 0; i != NumDests; ++i) {
   2704     TreePatternNode *Dest = Pat->getChild(i);
   2705     if (!Dest->isLeaf())
   2706       I->error("set destination should be a register!");
   2707 
   2708     DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
   2709     if (!Val) {
   2710       I->error("set destination should be a register!");
   2711       continue;
   2712     }
   2713 
   2714     if (Val->getDef()->isSubClassOf("RegisterClass") ||
   2715         Val->getDef()->isSubClassOf("ValueType") ||
   2716         Val->getDef()->isSubClassOf("RegisterOperand") ||
   2717         Val->getDef()->isSubClassOf("PointerLikeRegClass")) {
   2718       if (Dest->getName().empty())
   2719         I->error("set destination must have a name!");
   2720       if (InstResults.count(Dest->getName()))
   2721         I->error("cannot set '" + Dest->getName() +"' multiple times");
   2722       InstResults[Dest->getName()] = Dest;
   2723     } else if (Val->getDef()->isSubClassOf("Register")) {
   2724       InstImpResults.push_back(Val->getDef());
   2725     } else {
   2726       I->error("set destination should be a register!");
   2727     }
   2728   }
   2729 
   2730   // Verify and collect info from the computation.
   2731   FindPatternInputsAndOutputs(I, Pat->getChild(NumDests),
   2732                               InstInputs, InstResults, InstImpResults);
   2733 }
   2734 
   2735 //===----------------------------------------------------------------------===//
   2736 // Instruction Analysis
   2737 //===----------------------------------------------------------------------===//
   2738 
   2739 class InstAnalyzer {
   2740   const CodeGenDAGPatterns &CDP;
   2741 public:
   2742   bool hasSideEffects;
   2743   bool mayStore;
   2744   bool mayLoad;
   2745   bool isBitcast;
   2746   bool isVariadic;
   2747 
   2748   InstAnalyzer(const CodeGenDAGPatterns &cdp)
   2749     : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false),
   2750       isBitcast(false), isVariadic(false) {}
   2751 
   2752   void Analyze(const TreePattern *Pat) {
   2753     // Assume only the first tree is the pattern. The others are clobber nodes.
   2754     AnalyzeNode(Pat->getTree(0));
   2755   }
   2756 
   2757   void Analyze(const PatternToMatch *Pat) {
   2758     AnalyzeNode(Pat->getSrcPattern());
   2759   }
   2760 
   2761 private:
   2762   bool IsNodeBitcast(const TreePatternNode *N) const {
   2763     if (hasSideEffects || mayLoad || mayStore || isVariadic)
   2764       return false;
   2765 
   2766     if (N->getNumChildren() != 2)
   2767       return false;
   2768 
   2769     const TreePatternNode *N0 = N->getChild(0);
   2770     if (!N0->isLeaf() || !isa<DefInit>(N0->getLeafValue()))
   2771       return false;
   2772 
   2773     const TreePatternNode *N1 = N->getChild(1);
   2774     if (N1->isLeaf())
   2775       return false;
   2776     if (N1->getNumChildren() != 1 || !N1->getChild(0)->isLeaf())
   2777       return false;
   2778 
   2779     const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator());
   2780     if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1)
   2781       return false;
   2782     return OpInfo.getEnumName() == "ISD::BITCAST";
   2783   }
   2784 
   2785 public:
   2786   void AnalyzeNode(const TreePatternNode *N) {
   2787     if (N->isLeaf()) {
   2788       if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) {
   2789         Record *LeafRec = DI->getDef();
   2790         // Handle ComplexPattern leaves.
   2791         if (LeafRec->isSubClassOf("ComplexPattern")) {
   2792           const ComplexPattern &CP = CDP.getComplexPattern(LeafRec);
   2793           if (CP.hasProperty(SDNPMayStore)) mayStore = true;
   2794           if (CP.hasProperty(SDNPMayLoad)) mayLoad = true;
   2795           if (CP.hasProperty(SDNPSideEffect)) hasSideEffects = true;
   2796         }
   2797       }
   2798       return;
   2799     }
   2800 
   2801     // Analyze children.
   2802     for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
   2803       AnalyzeNode(N->getChild(i));
   2804 
   2805     // Ignore set nodes, which are not SDNodes.
   2806     if (N->getOperator()->getName() == "set") {
   2807       isBitcast = IsNodeBitcast(N);
   2808       return;
   2809     }
   2810 
   2811     // Notice properties of the node.
   2812     if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true;
   2813     if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true;
   2814     if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true;
   2815     if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true;
   2816 
   2817     if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
   2818       // If this is an intrinsic, analyze it.
   2819       if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem)
   2820         mayLoad = true;// These may load memory.
   2821 
   2822       if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteArgMem)
   2823         mayStore = true;// Intrinsics that can write to memory are 'mayStore'.
   2824 
   2825       if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem)
   2826         // WriteMem intrinsics can have other strange effects.
   2827         hasSideEffects = true;
   2828     }
   2829   }
   2830 
   2831 };
   2832 
   2833 static bool InferFromPattern(CodeGenInstruction &InstInfo,
   2834                              const InstAnalyzer &PatInfo,
   2835                              Record *PatDef) {
   2836   bool Error = false;
   2837 
   2838   // Remember where InstInfo got its flags.
   2839   if (InstInfo.hasUndefFlags())
   2840       InstInfo.InferredFrom = PatDef;
   2841 
   2842   // Check explicitly set flags for consistency.
   2843   if (InstInfo.hasSideEffects != PatInfo.hasSideEffects &&
   2844       !InstInfo.hasSideEffects_Unset) {
   2845     // Allow explicitly setting hasSideEffects = 1 on instructions, even when
   2846     // the pattern has no side effects. That could be useful for div/rem
   2847     // instructions that may trap.
   2848     if (!InstInfo.hasSideEffects) {
   2849       Error = true;
   2850       PrintError(PatDef->getLoc(), "Pattern doesn't match hasSideEffects = " +
   2851                  Twine(InstInfo.hasSideEffects));
   2852     }
   2853   }
   2854 
   2855   if (InstInfo.mayStore != PatInfo.mayStore && !InstInfo.mayStore_Unset) {
   2856     Error = true;
   2857     PrintError(PatDef->getLoc(), "Pattern doesn't match mayStore = " +
   2858                Twine(InstInfo.mayStore));
   2859   }
   2860 
   2861   if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) {
   2862     // Allow explicitly setting mayLoad = 1, even when the pattern has no loads.
   2863     // Some targets translate immediates to loads.
   2864     if (!InstInfo.mayLoad) {
   2865       Error = true;
   2866       PrintError(PatDef->getLoc(), "Pattern doesn't match mayLoad = " +
   2867                  Twine(InstInfo.mayLoad));
   2868     }
   2869   }
   2870 
   2871   // Transfer inferred flags.
   2872   InstInfo.hasSideEffects |= PatInfo.hasSideEffects;
   2873   InstInfo.mayStore |= PatInfo.mayStore;
   2874   InstInfo.mayLoad |= PatInfo.mayLoad;
   2875 
   2876   // These flags are silently added without any verification.
   2877   InstInfo.isBitcast |= PatInfo.isBitcast;
   2878 
   2879   // Don't infer isVariadic. This flag means something different on SDNodes and
   2880   // instructions. For example, a CALL SDNode is variadic because it has the
   2881   // call arguments as operands, but a CALL instruction is not variadic - it
   2882   // has argument registers as implicit, not explicit uses.
   2883 
   2884   return Error;
   2885 }
   2886 
   2887 /// hasNullFragReference - Return true if the DAG has any reference to the
   2888 /// null_frag operator.
   2889 static bool hasNullFragReference(DagInit *DI) {
   2890   DefInit *OpDef = dyn_cast<DefInit>(DI->getOperator());
   2891   if (!OpDef) return false;
   2892   Record *Operator = OpDef->getDef();
   2893 
   2894   // If this is the null fragment, return true.
   2895   if (Operator->getName() == "null_frag") return true;
   2896   // If any of the arguments reference the null fragment, return true.
   2897   for (unsigned i = 0, e = DI->getNumArgs(); i != e; ++i) {
   2898     DagInit *Arg = dyn_cast<DagInit>(DI->getArg(i));
   2899     if (Arg && hasNullFragReference(Arg))
   2900       return true;
   2901   }
   2902 
   2903   return false;
   2904 }
   2905 
   2906 /// hasNullFragReference - Return true if any DAG in the list references
   2907 /// the null_frag operator.
   2908 static bool hasNullFragReference(ListInit *LI) {
   2909   for (Init *I : LI->getValues()) {
   2910     DagInit *DI = dyn_cast<DagInit>(I);
   2911     assert(DI && "non-dag in an instruction Pattern list?!");
   2912     if (hasNullFragReference(DI))
   2913       return true;
   2914   }
   2915   return false;
   2916 }
   2917 
   2918 /// Get all the instructions in a tree.
   2919 static void
   2920 getInstructionsInTree(TreePatternNode *Tree, SmallVectorImpl<Record*> &Instrs) {
   2921   if (Tree->isLeaf())
   2922     return;
   2923   if (Tree->getOperator()->isSubClassOf("Instruction"))
   2924     Instrs.push_back(Tree->getOperator());
   2925   for (unsigned i = 0, e = Tree->getNumChildren(); i != e; ++i)
   2926     getInstructionsInTree(Tree->getChild(i), Instrs);
   2927 }
   2928 
   2929 /// Check the class of a pattern leaf node against the instruction operand it
   2930 /// represents.
   2931 static bool checkOperandClass(CGIOperandList::OperandInfo &OI,
   2932                               Record *Leaf) {
   2933   if (OI.Rec == Leaf)
   2934     return true;
   2935 
   2936   // Allow direct value types to be used in instruction set patterns.
   2937   // The type will be checked later.
   2938   if (Leaf->isSubClassOf("ValueType"))
   2939     return true;
   2940 
   2941   // Patterns can also be ComplexPattern instances.
   2942   if (Leaf->isSubClassOf("ComplexPattern"))
   2943     return true;
   2944 
   2945   return false;
   2946 }
   2947 
   2948 const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(
   2949     CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) {
   2950 
   2951   assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!");
   2952 
   2953   // Parse the instruction.
   2954   TreePattern *I = new TreePattern(CGI.TheDef, Pat, true, *this);
   2955   // Inline pattern fragments into it.
   2956   I->InlinePatternFragments();
   2957 
   2958   // Infer as many types as possible.  If we cannot infer all of them, we can
   2959   // never do anything with this instruction pattern: report it to the user.
   2960   if (!I->InferAllTypes())
   2961     I->error("Could not infer all types in pattern!");
   2962 
   2963   // InstInputs - Keep track of all of the inputs of the instruction, along
   2964   // with the record they are declared as.
   2965   std::map<std::string, TreePatternNode*> InstInputs;
   2966 
   2967   // InstResults - Keep track of all the virtual registers that are 'set'
   2968   // in the instruction, including what reg class they are.
   2969   std::map<std::string, TreePatternNode*> InstResults;
   2970 
   2971   std::vector<Record*> InstImpResults;
   2972 
   2973   // Verify that the top-level forms in the instruction are of void type, and
   2974   // fill in the InstResults map.
   2975   for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
   2976     TreePatternNode *Pat = I->getTree(j);
   2977     if (Pat->getNumTypes() != 0)
   2978       I->error("Top-level forms in instruction pattern should have"
   2979                " void types");
   2980 
   2981     // Find inputs and outputs, and verify the structure of the uses/defs.
   2982     FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,
   2983                                 InstImpResults);
   2984   }
   2985 
   2986   // Now that we have inputs and outputs of the pattern, inspect the operands
   2987   // list for the instruction.  This determines the order that operands are
   2988   // added to the machine instruction the node corresponds to.
   2989   unsigned NumResults = InstResults.size();
   2990 
   2991   // Parse the operands list from the (ops) list, validating it.
   2992   assert(I->getArgList().empty() && "Args list should still be empty here!");
   2993 
   2994   // Check that all of the results occur first in the list.
   2995   std::vector<Record*> Results;
   2996   SmallVector<TreePatternNode *, 2> ResNodes;
   2997   for (unsigned i = 0; i != NumResults; ++i) {
   2998     if (i == CGI.Operands.size())
   2999       I->error("'" + InstResults.begin()->first +
   3000                "' set but does not appear in operand list!");
   3001     const std::string &OpName = CGI.Operands[i].Name;
   3002 
   3003     // Check that it exists in InstResults.
   3004     TreePatternNode *RNode = InstResults[OpName];
   3005     if (!RNode)
   3006       I->error("Operand $" + OpName + " does not exist in operand list!");
   3007 
   3008     ResNodes.push_back(RNode);
   3009 
   3010     Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();
   3011     if (!R)
   3012       I->error("Operand $" + OpName + " should be a set destination: all "
   3013                "outputs must occur before inputs in operand list!");
   3014 
   3015     if (!checkOperandClass(CGI.Operands[i], R))
   3016       I->error("Operand $" + OpName + " class mismatch!");
   3017 
   3018     // Remember the return type.
   3019     Results.push_back(CGI.Operands[i].Rec);
   3020 
   3021     // Okay, this one checks out.
   3022     InstResults.erase(OpName);
   3023   }
   3024 
   3025   // Loop over the inputs next.  Make a copy of InstInputs so we can destroy
   3026   // the copy while we're checking the inputs.
   3027   std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs);
   3028 
   3029   std::vector<TreePatternNode*> ResultNodeOperands;
   3030   std::vector<Record*> Operands;
   3031   for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {
   3032     CGIOperandList::OperandInfo &Op = CGI.Operands[i];
   3033     const std::string &OpName = Op.Name;
   3034     if (OpName.empty())
   3035       I->error("Operand #" + utostr(i) + " in operands list has no name!");
   3036 
   3037     if (!InstInputsCheck.count(OpName)) {
   3038       // If this is an operand with a DefaultOps set filled in, we can ignore
   3039       // this.  When we codegen it, we will do so as always executed.
   3040       if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {
   3041         // Does it have a non-empty DefaultOps field?  If so, ignore this
   3042         // operand.
   3043         if (!getDefaultOperand(Op.Rec).DefaultOps.empty())
   3044           continue;
   3045       }
   3046       I->error("Operand $" + OpName +
   3047                " does not appear in the instruction pattern");
   3048     }
   3049     TreePatternNode *InVal = InstInputsCheck[OpName];
   3050     InstInputsCheck.erase(OpName);   // It occurred, remove from map.
   3051 
   3052     if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {
   3053       Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef();
   3054       if (!checkOperandClass(Op, InRec))
   3055         I->error("Operand $" + OpName + "'s register class disagrees"
   3056                  " between the operand and pattern");
   3057     }
   3058     Operands.push_back(Op.Rec);
   3059 
   3060     // Construct the result for the dest-pattern operand list.
   3061     TreePatternNode *OpNode = InVal->clone();
   3062 
   3063     // No predicate is useful on the result.
   3064     OpNode->clearPredicateFns();
   3065 
   3066     // Promote the xform function to be an explicit node if set.
   3067     if (Record *Xform = OpNode->getTransformFn()) {
   3068       OpNode->setTransformFn(nullptr);
   3069       std::vector<TreePatternNode*> Children;
   3070       Children.push_back(OpNode);
   3071       OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes());
   3072     }
   3073 
   3074     ResultNodeOperands.push_back(OpNode);
   3075   }
   3076 
   3077   if (!InstInputsCheck.empty())
   3078     I->error("Input operand $" + InstInputsCheck.begin()->first +
   3079              " occurs in pattern but not in operands list!");
   3080 
   3081   TreePatternNode *ResultPattern =
   3082     new TreePatternNode(I->getRecord(), ResultNodeOperands,
   3083                         GetNumNodeResults(I->getRecord(), *this));
   3084   // Copy fully inferred output node types to instruction result pattern.
   3085   for (unsigned i = 0; i != NumResults; ++i) {
   3086     assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled");
   3087     ResultPattern->setType(i, ResNodes[i]->getExtType(0));
   3088   }
   3089 
   3090   // Create and insert the instruction.
   3091   // FIXME: InstImpResults should not be part of DAGInstruction.
   3092   DAGInstruction TheInst(I, Results, Operands, InstImpResults);
   3093   DAGInsts.insert(std::make_pair(I->getRecord(), TheInst));
   3094 
   3095   // Use a temporary tree pattern to infer all types and make sure that the
   3096   // constructed result is correct.  This depends on the instruction already
   3097   // being inserted into the DAGInsts map.
   3098   TreePattern Temp(I->getRecord(), ResultPattern, false, *this);
   3099   Temp.InferAllTypes(&I->getNamedNodesMap());
   3100 
   3101   DAGInstruction &TheInsertedInst = DAGInsts.find(I->getRecord())->second;
   3102   TheInsertedInst.setResultPattern(Temp.getOnlyTree());
   3103 
   3104   return TheInsertedInst;
   3105 }
   3106 
   3107 /// ParseInstructions - Parse all of the instructions, inlining and resolving
   3108 /// any fragments involved.  This populates the Instructions list with fully
   3109 /// resolved instructions.
   3110 void CodeGenDAGPatterns::ParseInstructions() {
   3111   std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
   3112 
   3113   for (Record *Instr : Instrs) {
   3114     ListInit *LI = nullptr;
   3115 
   3116     if (isa<ListInit>(Instr->getValueInit("Pattern")))
   3117       LI = Instr->getValueAsListInit("Pattern");
   3118 
   3119     // If there is no pattern, only collect minimal information about the
   3120     // instruction for its operand list.  We have to assume that there is one
   3121     // result, as we have no detailed info. A pattern which references the
   3122     // null_frag operator is as-if no pattern were specified. Normally this
   3123     // is from a multiclass expansion w/ a SDPatternOperator passed in as
   3124     // null_frag.
   3125     if (!LI || LI->empty() || hasNullFragReference(LI)) {
   3126       std::vector<Record*> Results;
   3127       std::vector<Record*> Operands;
   3128 
   3129       CodeGenInstruction &InstInfo = Target.getInstruction(Instr);
   3130 
   3131       if (InstInfo.Operands.size() != 0) {
   3132         for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j)
   3133           Results.push_back(InstInfo.Operands[j].Rec);
   3134 
   3135         // The rest are inputs.
   3136         for (unsigned j = InstInfo.Operands.NumDefs,
   3137                e = InstInfo.Operands.size(); j < e; ++j)
   3138           Operands.push_back(InstInfo.Operands[j].Rec);
   3139       }
   3140 
   3141       // Create and insert the instruction.
   3142       std::vector<Record*> ImpResults;
   3143       Instructions.insert(std::make_pair(Instr,
   3144                           DAGInstruction(nullptr, Results, Operands, ImpResults)));
   3145       continue;  // no pattern.
   3146     }
   3147 
   3148     CodeGenInstruction &CGI = Target.getInstruction(Instr);
   3149     const DAGInstruction &DI = parseInstructionPattern(CGI, LI, Instructions);
   3150 
   3151     (void)DI;
   3152     DEBUG(DI.getPattern()->dump());
   3153   }
   3154 
   3155   // If we can, convert the instructions to be patterns that are matched!
   3156   for (auto &Entry : Instructions) {
   3157     DAGInstruction &TheInst = Entry.second;
   3158     TreePattern *I = TheInst.getPattern();
   3159     if (!I) continue;  // No pattern.
   3160 
   3161     // FIXME: Assume only the first tree is the pattern. The others are clobber
   3162     // nodes.
   3163     TreePatternNode *Pattern = I->getTree(0);
   3164     TreePatternNode *SrcPattern;
   3165     if (Pattern->getOperator()->getName() == "set") {
   3166       SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
   3167     } else{
   3168       // Not a set (store or something?)
   3169       SrcPattern = Pattern;
   3170     }
   3171 
   3172     Record *Instr = Entry.first;
   3173     AddPatternToMatch(I,
   3174                       PatternToMatch(Instr,
   3175                                      Instr->getValueAsListInit("Predicates"),
   3176                                      SrcPattern,
   3177                                      TheInst.getResultPattern(),
   3178                                      TheInst.getImpResults(),
   3179                                      Instr->getValueAsInt("AddedComplexity"),
   3180                                      Instr->getID()));
   3181   }
   3182 }
   3183 
   3184 
   3185 typedef std::pair<const TreePatternNode*, unsigned> NameRecord;
   3186 
   3187 static void FindNames(const TreePatternNode *P,
   3188                       std::map<std::string, NameRecord> &Names,
   3189                       TreePattern *PatternTop) {
   3190   if (!P->getName().empty()) {
   3191     NameRecord &Rec = Names[P->getName()];
   3192     // If this is the first instance of the name, remember the node.
   3193     if (Rec.second++ == 0)
   3194       Rec.first = P;
   3195     else if (Rec.first->getExtTypes() != P->getExtTypes())
   3196       PatternTop->error("repetition of value: $" + P->getName() +
   3197                         " where different uses have different types!");
   3198   }
   3199 
   3200   if (!P->isLeaf()) {
   3201     for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
   3202       FindNames(P->getChild(i), Names, PatternTop);
   3203   }
   3204 }
   3205 
   3206 void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,
   3207                                            const PatternToMatch &PTM) {
   3208   // Do some sanity checking on the pattern we're about to match.
   3209   std::string Reason;
   3210   if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) {
   3211     PrintWarning(Pattern->getRecord()->getLoc(),
   3212       Twine("Pattern can never match: ") + Reason);
   3213     return;
   3214   }
   3215 
   3216   // If the source pattern's root is a complex pattern, that complex pattern
   3217   // must specify the nodes it can potentially match.
   3218   if (const ComplexPattern *CP =
   3219         PTM.getSrcPattern()->getComplexPatternInfo(*this))
   3220     if (CP->getRootNodes().empty())
   3221       Pattern->error("ComplexPattern at root must specify list of opcodes it"
   3222                      " could match");
   3223 
   3224 
   3225   // Find all of the named values in the input and output, ensure they have the
   3226   // same type.
   3227   std::map<std::string, NameRecord> SrcNames, DstNames;
   3228   FindNames(PTM.getSrcPattern(), SrcNames, Pattern);
   3229   FindNames(PTM.getDstPattern(), DstNames, Pattern);
   3230 
   3231   // Scan all of the named values in the destination pattern, rejecting them if
   3232   // they don't exist in the input pattern.
   3233   for (const auto &Entry : DstNames) {
   3234     if (SrcNames[Entry.first].first == nullptr)
   3235       Pattern->error("Pattern has input without matching name in output: $" +
   3236                      Entry.first);
   3237   }
   3238 
   3239   // Scan all of the named values in the source pattern, rejecting them if the
   3240   // name isn't used in the dest, and isn't used to tie two values together.
   3241   for (const auto &Entry : SrcNames)
   3242     if (DstNames[Entry.first].first == nullptr &&
   3243         SrcNames[Entry.first].second == 1)
   3244       Pattern->error("Pattern has dead named input: $" + Entry.first);
   3245 
   3246   PatternsToMatch.push_back(PTM);
   3247 }
   3248 
   3249 
   3250 
   3251 void CodeGenDAGPatterns::InferInstructionFlags() {
   3252   const std::vector<const CodeGenInstruction*> &Instructions =
   3253     Target.getInstructionsByEnumValue();
   3254 
   3255   // First try to infer flags from the primary instruction pattern, if any.
   3256   SmallVector<CodeGenInstruction*, 8> Revisit;
   3257   unsigned Errors = 0;
   3258   for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
   3259     CodeGenInstruction &InstInfo =
   3260       const_cast<CodeGenInstruction &>(*Instructions[i]);
   3261 
   3262     // Get the primary instruction pattern.
   3263     const TreePattern *Pattern = getInstruction(InstInfo.TheDef).getPattern();
   3264     if (!Pattern) {
   3265       if (InstInfo.hasUndefFlags())
   3266         Revisit.push_back(&InstInfo);
   3267       continue;
   3268     }
   3269     InstAnalyzer PatInfo(*this);
   3270     PatInfo.Analyze(Pattern);
   3271     Errors += InferFromPattern(InstInfo, PatInfo, InstInfo.TheDef);
   3272   }
   3273 
   3274   // Second, look for single-instruction patterns defined outside the
   3275   // instruction.
   3276   for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) {
   3277     const PatternToMatch &PTM = *I;
   3278 
   3279     // We can only infer from single-instruction patterns, otherwise we won't
   3280     // know which instruction should get the flags.
   3281     SmallVector<Record*, 8> PatInstrs;
   3282     getInstructionsInTree(PTM.getDstPattern(), PatInstrs);
   3283     if (PatInstrs.size() != 1)
   3284       continue;
   3285 
   3286     // Get the single instruction.
   3287     CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());
   3288 
   3289     // Only infer properties from the first pattern. We'll verify the others.
   3290     if (InstInfo.InferredFrom)
   3291       continue;
   3292 
   3293     InstAnalyzer PatInfo(*this);
   3294     PatInfo.Analyze(&PTM);
   3295     Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord());
   3296   }
   3297 
   3298   if (Errors)
   3299     PrintFatalError("pattern conflicts");
   3300 
   3301   // Revisit instructions with undefined flags and no pattern.
   3302   if (Target.guessInstructionProperties()) {
   3303     for (CodeGenInstruction *InstInfo : Revisit) {
   3304       if (InstInfo->InferredFrom)
   3305         continue;
   3306       // The mayLoad and mayStore flags default to false.
   3307       // Conservatively assume hasSideEffects if it wasn't explicit.
   3308       if (InstInfo->hasSideEffects_Unset)
   3309         InstInfo->hasSideEffects = true;
   3310     }
   3311     return;
   3312   }
   3313 
   3314   // Complain about any flags that are still undefined.
   3315   for (CodeGenInstruction *InstInfo : Revisit) {
   3316     if (InstInfo->InferredFrom)
   3317       continue;
   3318     if (InstInfo->hasSideEffects_Unset)
   3319       PrintError(InstInfo->TheDef->getLoc(),
   3320                  "Can't infer hasSideEffects from patterns");
   3321     if (InstInfo->mayStore_Unset)
   3322       PrintError(InstInfo->TheDef->getLoc(),
   3323                  "Can't infer mayStore from patterns");
   3324     if (InstInfo->mayLoad_Unset)
   3325       PrintError(InstInfo->TheDef->getLoc(),
   3326                  "Can't infer mayLoad from patterns");
   3327   }
   3328 }
   3329 
   3330 
   3331 /// Verify instruction flags against pattern node properties.
   3332 void CodeGenDAGPatterns::VerifyInstructionFlags() {
   3333   unsigned Errors = 0;
   3334   for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) {
   3335     const PatternToMatch &PTM = *I;
   3336     SmallVector<Record*, 8> Instrs;
   3337     getInstructionsInTree(PTM.getDstPattern(), Instrs);
   3338     if (Instrs.empty())
   3339       continue;
   3340 
   3341     // Count the number of instructions with each flag set.
   3342     unsigned NumSideEffects = 0;
   3343     unsigned NumStores = 0;
   3344     unsigned NumLoads = 0;
   3345     for (const Record *Instr : Instrs) {
   3346       const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);
   3347       NumSideEffects += InstInfo.hasSideEffects;
   3348       NumStores += InstInfo.mayStore;
   3349       NumLoads += InstInfo.mayLoad;
   3350     }
   3351 
   3352     // Analyze the source pattern.
   3353     InstAnalyzer PatInfo(*this);
   3354     PatInfo.Analyze(&PTM);
   3355 
   3356     // Collect error messages.
   3357     SmallVector<std::string, 4> Msgs;
   3358 
   3359     // Check for missing flags in the output.
   3360     // Permit extra flags for now at least.
   3361     if (PatInfo.hasSideEffects && !NumSideEffects)
   3362       Msgs.push_back("pattern has side effects, but hasSideEffects isn't set");
   3363 
   3364     // Don't verify store flags on instructions with side effects. At least for
   3365     // intrinsics, side effects implies mayStore.
   3366     if (!PatInfo.hasSideEffects && PatInfo.mayStore && !NumStores)
   3367       Msgs.push_back("pattern may store, but mayStore isn't set");
   3368 
   3369     // Similarly, mayStore implies mayLoad on intrinsics.
   3370     if (!PatInfo.mayStore && PatInfo.mayLoad && !NumLoads)
   3371       Msgs.push_back("pattern may load, but mayLoad isn't set");
   3372 
   3373     // Print error messages.
   3374     if (Msgs.empty())
   3375       continue;
   3376     ++Errors;
   3377 
   3378     for (const std::string &Msg : Msgs)
   3379       PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msg) + " on the " +
   3380                  (Instrs.size() == 1 ?
   3381                   "instruction" : "output instructions"));
   3382     // Provide the location of the relevant instruction definitions.
   3383     for (const Record *Instr : Instrs) {
   3384       if (Instr != PTM.getSrcRecord())
   3385         PrintError(Instr->getLoc(), "defined here");
   3386       const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);
   3387       if (InstInfo.InferredFrom &&
   3388           InstInfo.InferredFrom != InstInfo.TheDef &&
   3389           InstInfo.InferredFrom != PTM.getSrcRecord())
   3390         PrintError(InstInfo.InferredFrom->getLoc(), "inferred from pattern");
   3391     }
   3392   }
   3393   if (Errors)
   3394     PrintFatalError("Errors in DAG patterns");
   3395 }
   3396 
   3397 /// Given a pattern result with an unresolved type, see if we can find one
   3398 /// instruction with an unresolved result type.  Force this result type to an
   3399 /// arbitrary element if it's possible types to converge results.
   3400 static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) {
   3401   if (N->isLeaf())
   3402     return false;
   3403 
   3404   // Analyze children.
   3405   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
   3406     if (ForceArbitraryInstResultType(N->getChild(i), TP))
   3407       return true;
   3408 
   3409   if (!N->getOperator()->isSubClassOf("Instruction"))
   3410     return false;
   3411 
   3412   // If this type is already concrete or completely unknown we can't do
   3413   // anything.
   3414   for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) {
   3415     if (N->getExtType(i).isCompletelyUnknown() || N->getExtType(i).isConcrete())
   3416       continue;
   3417 
   3418     // Otherwise, force its type to the first possibility (an arbitrary choice).
   3419     if (N->getExtType(i).MergeInTypeInfo(N->getExtType(i).getTypeList()[0], TP))
   3420       return true;
   3421   }
   3422 
   3423   return false;
   3424 }
   3425 
   3426 void CodeGenDAGPatterns::ParsePatterns() {
   3427   std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
   3428 
   3429   for (Record *CurPattern : Patterns) {
   3430     DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
   3431 
   3432     // If the pattern references the null_frag, there's nothing to do.
   3433     if (hasNullFragReference(Tree))
   3434       continue;
   3435 
   3436     TreePattern *Pattern = new TreePattern(CurPattern, Tree, true, *this);
   3437 
   3438     // Inline pattern fragments into it.
   3439     Pattern->InlinePatternFragments();
   3440 
   3441     ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
   3442     if (LI->empty()) continue;  // no pattern.
   3443 
   3444     // Parse the instruction.
   3445     TreePattern Result(CurPattern, LI, false, *this);
   3446 
   3447     // Inline pattern fragments into it.
   3448     Result.InlinePatternFragments();
   3449 
   3450     if (Result.getNumTrees() != 1)
   3451       Result.error("Cannot handle instructions producing instructions "
   3452                    "with temporaries yet!");
   3453 
   3454     bool IterateInference;
   3455     bool InferredAllPatternTypes, InferredAllResultTypes;
   3456     do {
   3457       // Infer as many types as possible.  If we cannot infer all of them, we
   3458       // can never do anything with this pattern: report it to the user.
   3459       InferredAllPatternTypes =
   3460         Pattern->InferAllTypes(&Pattern->getNamedNodesMap());
   3461 
   3462       // Infer as many types as possible.  If we cannot infer all of them, we
   3463       // can never do anything with this pattern: report it to the user.
   3464       InferredAllResultTypes =
   3465           Result.InferAllTypes(&Pattern->getNamedNodesMap());
   3466 
   3467       IterateInference = false;
   3468 
   3469       // Apply the type of the result to the source pattern.  This helps us
   3470       // resolve cases where the input type is known to be a pointer type (which
   3471       // is considered resolved), but the result knows it needs to be 32- or
   3472       // 64-bits.  Infer the other way for good measure.
   3473       for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(),
   3474                                         Pattern->getTree(0)->getNumTypes());
   3475            i != e; ++i) {
   3476         IterateInference = Pattern->getTree(0)->UpdateNodeType(
   3477             i, Result.getTree(0)->getExtType(i), Result);
   3478         IterateInference |= Result.getTree(0)->UpdateNodeType(
   3479             i, Pattern->getTree(0)->getExtType(i), Result);
   3480       }
   3481 
   3482       // If our iteration has converged and the input pattern's types are fully
   3483       // resolved but the result pattern is not fully resolved, we may have a
   3484       // situation where we have two instructions in the result pattern and
   3485       // the instructions require a common register class, but don't care about
   3486       // what actual MVT is used.  This is actually a bug in our modelling:
   3487       // output patterns should have register classes, not MVTs.
   3488       //
   3489       // In any case, to handle this, we just go through and disambiguate some
   3490       // arbitrary types to the result pattern's nodes.
   3491       if (!IterateInference && InferredAllPatternTypes &&
   3492           !InferredAllResultTypes)
   3493         IterateInference =
   3494             ForceArbitraryInstResultType(Result.getTree(0), Result);
   3495     } while (IterateInference);
   3496 
   3497     // Verify that we inferred enough types that we can do something with the
   3498     // pattern and result.  If these fire the user has to add type casts.
   3499     if (!InferredAllPatternTypes)
   3500       Pattern->error("Could not infer all types in pattern!");
   3501     if (!InferredAllResultTypes) {
   3502       Pattern->dump();
   3503       Result.error("Could not infer all types in pattern result!");
   3504     }
   3505 
   3506     // Validate that the input pattern is correct.
   3507     std::map<std::string, TreePatternNode*> InstInputs;
   3508     std::map<std::string, TreePatternNode*> InstResults;
   3509     std::vector<Record*> InstImpResults;
   3510     for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j)
   3511       FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j),
   3512                                   InstInputs, InstResults,
   3513                                   InstImpResults);
   3514 
   3515     // Promote the xform function to be an explicit node if set.
   3516     TreePatternNode *DstPattern = Result.getOnlyTree();
   3517     std::vector<TreePatternNode*> ResultNodeOperands;
   3518     for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) {
   3519       TreePatternNode *OpNode = DstPattern->getChild(ii);
   3520       if (Record *Xform = OpNode->getTransformFn()) {
   3521         OpNode->setTransformFn(nullptr);
   3522         std::vector<TreePatternNode*> Children;
   3523         Children.push_back(OpNode);
   3524         OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes());
   3525       }
   3526       ResultNodeOperands.push_back(OpNode);
   3527     }
   3528     DstPattern = Result.getOnlyTree();
   3529     if (!DstPattern->isLeaf())
   3530       DstPattern = new TreePatternNode(DstPattern->getOperator(),
   3531                                        ResultNodeOperands,
   3532                                        DstPattern->getNumTypes());
   3533 
   3534     for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i)
   3535       DstPattern->setType(i, Result.getOnlyTree()->getExtType(i));
   3536 
   3537     TreePattern Temp(Result.getRecord(), DstPattern, false, *this);
   3538     Temp.InferAllTypes();
   3539 
   3540 
   3541     AddPatternToMatch(Pattern,
   3542                     PatternToMatch(CurPattern,
   3543                                    CurPattern->getValueAsListInit("Predicates"),
   3544                                    Pattern->getTree(0),
   3545                                    Temp.getOnlyTree(), InstImpResults,
   3546                                    CurPattern->getValueAsInt("AddedComplexity"),
   3547                                    CurPattern->getID()));
   3548   }
   3549 }
   3550 
   3551 /// CombineChildVariants - Given a bunch of permutations of each child of the
   3552 /// 'operator' node, put them together in all possible ways.
   3553 static void CombineChildVariants(TreePatternNode *Orig,
   3554                const std::vector<std::vector<TreePatternNode*> > &ChildVariants,
   3555                                  std::vector<TreePatternNode*> &OutVariants,
   3556                                  CodeGenDAGPatterns &CDP,
   3557                                  const MultipleUseVarSet &DepVars) {
   3558   // Make sure that each operand has at least one variant to choose from.
   3559   for (const auto &Variants : ChildVariants)
   3560     if (Variants.empty())
   3561       return;
   3562 
   3563   // The end result is an all-pairs construction of the resultant pattern.
   3564   std::vector<unsigned> Idxs;
   3565   Idxs.resize(ChildVariants.size());
   3566   bool NotDone;
   3567   do {
   3568 #ifndef NDEBUG
   3569     DEBUG(if (!Idxs.empty()) {
   3570             errs() << Orig->getOperator()->getName() << ": Idxs = [ ";
   3571               for (unsigned Idx : Idxs) {
   3572                 errs() << Idx << " ";
   3573             }
   3574             errs() << "]\n";
   3575           });
   3576 #endif
   3577     // Create the variant and add it to the output list.
   3578     std::vector<TreePatternNode*> NewChildren;
   3579     for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)
   3580       NewChildren.push_back(ChildVariants[i][Idxs[i]]);
   3581     auto R = llvm::make_unique<TreePatternNode>(
   3582         Orig->getOperator(), NewChildren, Orig->getNumTypes());
   3583 
   3584     // Copy over properties.
   3585     R->setName(Orig->getName());
   3586     R->setPredicateFns(Orig->getPredicateFns());
   3587     R->setTransformFn(Orig->getTransformFn());
   3588     for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i)
   3589       R->setType(i, Orig->getExtType(i));
   3590 
   3591     // If this pattern cannot match, do not include it as a variant.
   3592     std::string ErrString;
   3593     // Scan to see if this pattern has already been emitted.  We can get
   3594     // duplication due to things like commuting:
   3595     //   (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a)
   3596     // which are the same pattern.  Ignore the dups.
   3597     if (R->canPatternMatch(ErrString, CDP) &&
   3598         std::none_of(OutVariants.begin(), OutVariants.end(),
   3599                      [&](TreePatternNode *Variant) {
   3600                        return R->isIsomorphicTo(Variant, DepVars);
   3601                      }))
   3602       OutVariants.push_back(R.release());
   3603 
   3604     // Increment indices to the next permutation by incrementing the
   3605     // indices from last index backward, e.g., generate the sequence
   3606     // [0, 0], [0, 1], [1, 0], [1, 1].
   3607     int IdxsIdx;
   3608     for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
   3609       if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size())
   3610         Idxs[IdxsIdx] = 0;
   3611       else
   3612         break;
   3613     }
   3614     NotDone = (IdxsIdx >= 0);
   3615   } while (NotDone);
   3616 }
   3617 
   3618 /// CombineChildVariants - A helper function for binary operators.
   3619 ///
   3620 static void CombineChildVariants(TreePatternNode *Orig,
   3621                                  const std::vector<TreePatternNode*> &LHS,
   3622                                  const std::vector<TreePatternNode*> &RHS,
   3623                                  std::vector<TreePatternNode*> &OutVariants,
   3624                                  CodeGenDAGPatterns &CDP,
   3625                                  const MultipleUseVarSet &DepVars) {
   3626   std::vector<std::vector<TreePatternNode*> > ChildVariants;
   3627   ChildVariants.push_back(LHS);
   3628   ChildVariants.push_back(RHS);
   3629   CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars);
   3630 }
   3631 
   3632 
   3633 static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N,
   3634                                      std::vector<TreePatternNode *> &Children) {
   3635   assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!");
   3636   Record *Operator = N->getOperator();
   3637 
   3638   // Only permit raw nodes.
   3639   if (!N->getName().empty() || !N->getPredicateFns().empty() ||
   3640       N->getTransformFn()) {
   3641     Children.push_back(N);
   3642     return;
   3643   }
   3644 
   3645   if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator)
   3646     Children.push_back(N->getChild(0));
   3647   else
   3648     GatherChildrenOfAssociativeOpcode(N->getChild(0), Children);
   3649 
   3650   if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator)
   3651     Children.push_back(N->getChild(1));
   3652   else
   3653     GatherChildrenOfAssociativeOpcode(N->getChild(1), Children);
   3654 }
   3655 
   3656 /// GenerateVariantsOf - Given a pattern N, generate all permutations we can of
   3657 /// the (potentially recursive) pattern by using algebraic laws.
   3658 ///
   3659 static void GenerateVariantsOf(TreePatternNode *N,
   3660                                std::vector<TreePatternNode*> &OutVariants,
   3661                                CodeGenDAGPatterns &CDP,
   3662                                const MultipleUseVarSet &DepVars) {
   3663   // We cannot permute leaves or ComplexPattern uses.
   3664   if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) {
   3665     OutVariants.push_back(N);
   3666     return;
   3667   }
   3668 
   3669   // Look up interesting info about the node.
   3670   const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator());
   3671 
   3672   // If this node is associative, re-associate.
   3673   if (NodeInfo.hasProperty(SDNPAssociative)) {
   3674     // Re-associate by pulling together all of the linked operators
   3675     std::vector<TreePatternNode*> MaximalChildren;
   3676     GatherChildrenOfAssociativeOpcode(N, MaximalChildren);
   3677 
   3678     // Only handle child sizes of 3.  Otherwise we'll end up trying too many
   3679     // permutations.
   3680     if (MaximalChildren.size() == 3) {
   3681       // Find the variants of all of our maximal children.
   3682       std::vector<TreePatternNode*> AVariants, BVariants, CVariants;
   3683       GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars);
   3684       GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars);
   3685       GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars);
   3686 
   3687       // There are only two ways we can permute the tree:
   3688       //   (A op B) op C    and    A op (B op C)
   3689       // Within these forms, we can also permute A/B/C.
   3690 
   3691       // Generate legal pair permutations of A/B/C.
   3692       std::vector<TreePatternNode*> ABVariants;
   3693       std::vector<TreePatternNode*> BAVariants;
   3694       std::vector<TreePatternNode*> ACVariants;
   3695       std::vector<TreePatternNode*> CAVariants;
   3696       std::vector<TreePatternNode*> BCVariants;
   3697       std::vector<TreePatternNode*> CBVariants;
   3698       CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars);
   3699       CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars);
   3700       CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars);
   3701       CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars);
   3702       CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars);
   3703       CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars);
   3704 
   3705       // Combine those into the result: (x op x) op x
   3706       CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars);
   3707       CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars);
   3708       CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars);
   3709       CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars);
   3710       CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars);
   3711       CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars);
   3712 
   3713       // Combine those into the result: x op (x op x)
   3714       CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars);
   3715       CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars);
   3716       CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars);
   3717       CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars);
   3718       CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars);
   3719       CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars);
   3720       return;
   3721     }
   3722   }
   3723 
   3724   // Compute permutations of all children.
   3725   std::vector<std::vector<TreePatternNode*> > ChildVariants;
   3726   ChildVariants.resize(N->getNumChildren());
   3727   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
   3728     GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars);
   3729 
   3730   // Build all permutations based on how the children were formed.
   3731   CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars);
   3732 
   3733   // If this node is commutative, consider the commuted order.
   3734   bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP);
   3735   if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
   3736     assert((N->getNumChildren()==2 || isCommIntrinsic) &&
   3737            "Commutative but doesn't have 2 children!");
   3738     // Don't count children which are actually register references.
   3739     unsigned NC = 0;
   3740     for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
   3741       TreePatternNode *Child = N->getChild(i);
   3742       if (Child->isLeaf())
   3743         if (DefInit *DI = dyn_cast<DefInit>(Child->getLeafValue())) {
   3744           Record *RR = DI->getDef();
   3745           if (RR->isSubClassOf("Register"))
   3746             continue;
   3747         }
   3748       NC++;
   3749     }
   3750     // Consider the commuted order.
   3751     if (isCommIntrinsic) {
   3752       // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd
   3753       // operands are the commutative operands, and there might be more operands
   3754       // after those.
   3755       assert(NC >= 3 &&
   3756              "Commutative intrinsic should have at least 3 children!");
   3757       std::vector<std::vector<TreePatternNode*> > Variants;
   3758       Variants.push_back(ChildVariants[0]); // Intrinsic id.
   3759       Variants.push_back(ChildVariants[2]);
   3760       Variants.push_back(ChildVariants[1]);
   3761       for (unsigned i = 3; i != NC; ++i)
   3762         Variants.push_back(ChildVariants[i]);
   3763       CombineChildVariants(N, Variants, OutVariants, CDP, DepVars);
   3764     } else if (NC == 2)
   3765       CombineChildVariants(N, ChildVariants[1], ChildVariants[0],
   3766                            OutVariants, CDP, DepVars);
   3767   }
   3768 }
   3769 
   3770 
   3771 // GenerateVariants - Generate variants.  For example, commutative patterns can
   3772 // match multiple ways.  Add them to PatternsToMatch as well.
   3773 void CodeGenDAGPatterns::GenerateVariants() {
   3774   DEBUG(errs() << "Generating instruction variants.\n");
   3775 
   3776   // Loop over all of the patterns we've collected, checking to see if we can
   3777   // generate variants of the instruction, through the exploitation of
   3778   // identities.  This permits the target to provide aggressive matching without
   3779   // the .td file having to contain tons of variants of instructions.
   3780   //
   3781   // Note that this loop adds new patterns to the PatternsToMatch list, but we
   3782   // intentionally do not reconsider these.  Any variants of added patterns have
   3783   // already been added.
   3784   //
   3785   for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
   3786     MultipleUseVarSet             DepVars;
   3787     std::vector<TreePatternNode*> Variants;
   3788     FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars);
   3789     DEBUG(errs() << "Dependent/multiply used variables: ");
   3790     DEBUG(DumpDepVars(DepVars));
   3791     DEBUG(errs() << "\n");
   3792     GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this,
   3793                        DepVars);
   3794 
   3795     assert(!Variants.empty() && "Must create at least original variant!");
   3796     Variants.erase(Variants.begin());  // Remove the original pattern.
   3797 
   3798     if (Variants.empty())  // No variants for this pattern.
   3799       continue;
   3800 
   3801     DEBUG(errs() << "FOUND VARIANTS OF: ";
   3802           PatternsToMatch[i].getSrcPattern()->dump();
   3803           errs() << "\n");
   3804 
   3805     for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
   3806       TreePatternNode *Variant = Variants[v];
   3807 
   3808       DEBUG(errs() << "  VAR#" << v <<  ": ";
   3809             Variant->dump();
   3810             errs() << "\n");
   3811 
   3812       // Scan to see if an instruction or explicit pattern already matches this.
   3813       bool AlreadyExists = false;
   3814       for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {
   3815         // Skip if the top level predicates do not match.
   3816         if (PatternsToMatch[i].getPredicates() !=
   3817             PatternsToMatch[p].getPredicates())
   3818           continue;
   3819         // Check to see if this variant already exists.
   3820         if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(),
   3821                                     DepVars)) {
   3822           DEBUG(errs() << "  *** ALREADY EXISTS, ignoring variant.\n");
   3823           AlreadyExists = true;
   3824           break;
   3825         }
   3826       }
   3827       // If we already have it, ignore the variant.
   3828       if (AlreadyExists) continue;
   3829 
   3830       // Otherwise, add it to the list of patterns we have.
   3831       PatternsToMatch.emplace_back(
   3832           PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(),
   3833           Variant, PatternsToMatch[i].getDstPattern(),
   3834           PatternsToMatch[i].getDstRegs(),
   3835           PatternsToMatch[i].getAddedComplexity(), Record::getNewUID());
   3836     }
   3837 
   3838     DEBUG(errs() << "\n");
   3839   }
   3840 }
   3841