brintos / llvm-project-archived public Read only

1//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the CodeGenDAGPatterns class, which is used to read and10// represent the patterns present in a .td file for instructions.11//12//===----------------------------------------------------------------------===//13 14#include "CodeGenDAGPatterns.h"15#include "CodeGenInstruction.h"16#include "CodeGenRegisters.h"17#include "SubtargetFeatureInfo.h"18#include "llvm/ADT/DenseSet.h"19#include "llvm/ADT/MapVector.h"20#include "llvm/ADT/STLExtras.h"21#include "llvm/ADT/SmallSet.h"22#include "llvm/ADT/SmallString.h"23#include "llvm/ADT/StringExtras.h"24#include "llvm/ADT/StringMap.h"25#include "llvm/ADT/Twine.h"26#include "llvm/Support/Debug.h"27#include "llvm/Support/ErrorHandling.h"28#include "llvm/Support/InterleavedRange.h"29#include "llvm/Support/TypeSize.h"30#include "llvm/TableGen/Error.h"31#include "llvm/TableGen/Record.h"32#include <algorithm>33#include <cstdio>34#include <iterator>35#include <set>36using namespace llvm;37 38#define DEBUG_TYPE "dag-patterns"39 40static inline bool isIntegerOrPtr(MVT VT) {41  return VT.isInteger() || VT == MVT::iPTR;42}43static inline bool isFloatingPoint(MVT VT) { return VT.isFloatingPoint(); }44static inline bool isVector(MVT VT) { return VT.isVector(); }45static inline bool isScalar(MVT VT) { return !VT.isVector(); }46 47template <typename Predicate>48static bool berase_if(MachineValueTypeSet &S, Predicate P) {49  bool Erased = false;50  // It is ok to iterate over MachineValueTypeSet and remove elements from it51  // at the same time.52  for (MVT T : S) {53    if (!P(T))54      continue;55    Erased = true;56    S.erase(T);57  }58  return Erased;59}60 61void MachineValueTypeSet::writeToStream(raw_ostream &OS) const {62  SmallVector<MVT, 4> Types(begin(), end());63  array_pod_sort(Types.begin(), Types.end());64 65  OS << '[';66  ListSeparator LS(" ");67  for (const MVT &T : Types)68    OS << LS << ValueTypeByHwMode::getMVTName(T);69  OS << ']';70}71 72// --- TypeSetByHwMode73 74// This is a parameterized type-set class. For each mode there is a list75// of types that are currently possible for a given tree node. Type76// inference will apply to each mode separately.77 78TypeSetByHwMode::TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList) {79  // Take the address space from the first type in the list.80  if (!VTList.empty())81    AddrSpace = VTList[0].PtrAddrSpace;82 83  for (const ValueTypeByHwMode &VVT : VTList)84    insert(VVT);85}86 87bool TypeSetByHwMode::isValueTypeByHwMode(bool AllowEmpty) const {88  for (const auto &I : *this) {89    if (I.second.size() > 1)90      return false;91    if (!AllowEmpty && I.second.empty())92      return false;93  }94  return true;95}96 97ValueTypeByHwMode TypeSetByHwMode::getValueTypeByHwMode() const {98  assert(isValueTypeByHwMode(true) &&99         "The type set has multiple types for at least one HW mode");100  ValueTypeByHwMode VVT;101  VVT.PtrAddrSpace = AddrSpace;102 103  for (const auto &I : *this) {104    MVT T = I.second.empty() ? MVT::Other : *I.second.begin();105    VVT.getOrCreateTypeForMode(I.first, T);106  }107  return VVT;108}109 110bool TypeSetByHwMode::isPossible() const {111  for (const auto &I : *this)112    if (!I.second.empty())113      return true;114  return false;115}116 117bool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) {118  bool Changed = false;119  bool ContainsDefault = false;120  MVT DT = MVT::Other;121 122  for (const auto &P : VVT) {123    unsigned M = P.first;124    // Make sure there exists a set for each specific mode from VVT.125    Changed |= getOrCreate(M).insert(P.second).second;126    // Cache VVT's default mode.127    if (DefaultMode == M) {128      ContainsDefault = true;129      DT = P.second;130    }131  }132 133  // If VVT has a default mode, add the corresponding type to all134  // modes in "this" that do not exist in VVT.135  if (ContainsDefault)136    for (auto &I : *this)137      if (!VVT.hasMode(I.first))138        Changed |= I.second.insert(DT).second;139 140  return Changed;141}142 143// Constrain the type set to be the intersection with VTS.144bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) {145  bool Changed = false;146  if (hasDefault()) {147    for (const auto &I : VTS) {148      unsigned M = I.first;149      if (M == DefaultMode || hasMode(M))150        continue;151      Map.try_emplace(M, Map.at(DefaultMode));152      Changed = true;153    }154  }155 156  for (auto &I : *this) {157    unsigned M = I.first;158    SetType &S = I.second;159    if (VTS.hasMode(M) || VTS.hasDefault()) {160      Changed |= intersect(I.second, VTS.get(M));161    } else if (!S.empty()) {162      S.clear();163      Changed = true;164    }165  }166  return Changed;167}168 169template <typename Predicate> bool TypeSetByHwMode::constrain(Predicate P) {170  bool Changed = false;171  for (auto &I : *this)172    Changed |= berase_if(I.second, [&P](MVT VT) { return !P(VT); });173  return Changed;174}175 176template <typename Predicate>177bool TypeSetByHwMode::assign_if(const TypeSetByHwMode &VTS, Predicate P) {178  assert(empty());179  for (const auto &I : VTS) {180    SetType &S = getOrCreate(I.first);181    for (auto J : I.second)182      if (P(J))183        S.insert(J);184  }185  return !empty();186}187 188void TypeSetByHwMode::writeToStream(raw_ostream &OS) const {189  SmallVector<unsigned, 4> Modes;190  Modes.reserve(Map.size());191 192  for (const auto &I : *this)193    Modes.push_back(I.first);194  if (Modes.empty()) {195    OS << "{}";196    return;197  }198  array_pod_sort(Modes.begin(), Modes.end());199 200  OS << '{';201  for (unsigned M : Modes) {202    OS << ' ' << getModeName(M) << ':';203    get(M).writeToStream(OS);204  }205  OS << " }";206}207 208bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const {209  // The isSimple call is much quicker than hasDefault - check this first.210  bool IsSimple = isSimple();211  bool VTSIsSimple = VTS.isSimple();212  if (IsSimple && VTSIsSimple)213    return getSimple() == VTS.getSimple();214 215  // Speedup: We have a default if the set is simple.216  bool HaveDefault = IsSimple || hasDefault();217  bool VTSHaveDefault = VTSIsSimple || VTS.hasDefault();218  if (HaveDefault != VTSHaveDefault)219    return false;220 221  SmallSet<unsigned, 4> Modes;222  Modes.insert_range(llvm::make_first_range(*this));223  Modes.insert_range(llvm::make_first_range(VTS));224 225  if (HaveDefault) {226    // Both sets have default mode.227    for (unsigned M : Modes) {228      if (get(M) != VTS.get(M))229        return false;230    }231  } else {232    // Neither set has default mode.233    for (unsigned M : Modes) {234      // If there is no default mode, an empty set is equivalent to not having235      // the corresponding mode.236      bool NoModeThis = !hasMode(M) || get(M).empty();237      bool NoModeVTS = !VTS.hasMode(M) || VTS.get(M).empty();238      if (NoModeThis != NoModeVTS)239        return false;240      if (!NoModeThis)241        if (get(M) != VTS.get(M))242          return false;243    }244  }245 246  return true;247}248 249raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineValueTypeSet &T) {250  T.writeToStream(OS);251  return OS;252}253raw_ostream &llvm::operator<<(raw_ostream &OS, const TypeSetByHwMode &T) {254  T.writeToStream(OS);255  return OS;256}257 258LLVM_DUMP_METHOD259void TypeSetByHwMode::dump() const { dbgs() << *this << '\n'; }260 261bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {262  auto IntersectP = [&](std::optional<MVT> WildVT, function_ref<bool(MVT)> P) {263    // Complement of In within this partition.264    auto CompIn = [&](MVT T) -> bool { return !In.count(T) && P(T); };265 266    if (!WildVT)267      return berase_if(Out, CompIn);268 269    bool OutW = Out.count(*WildVT), InW = In.count(*WildVT);270    if (OutW == InW)271      return berase_if(Out, CompIn);272 273    // Compute the intersection of scalars separately to account for only one274    // set containing WildVT.275    // The intersection of WildVT with a set of corresponding types that does276    // not include WildVT will result in the most specific type:277    // - WildVT is more specific than any set with two elements or more278    // - WildVT is less specific than any single type.279    // For example, for iPTR and scalar integer types280    // { iPTR } * { i32 }     -> { i32 }281    // { iPTR } * { i32 i64 } -> { iPTR }282    // and283    // { iPTR i32 } * { i32 }          -> { i32 }284    // { iPTR i32 } * { i32 i64 }      -> { i32 i64 }285    // { iPTR i32 } * { i32 i64 i128 } -> { iPTR i32 }286 287    // Looking at just this partition, let In' = elements only in In,288    // Out' = elements only in Out, and IO = elements common to both. Normally289    // IO would be returned as the result of the intersection, but we need to290    // account for WildVT being a "wildcard" of sorts. Since elements in IO are291    // those that match both sets exactly, they will all belong to the output.292    // If any of the "leftovers" (i.e. In' or Out') contain WildVT, it means293    // that the other set doesn't have it, but it could have (1) a more294    // specific type, or (2) a set of types that is less specific. The295    // "leftovers" from the other set is what we want to examine more closely.296 297    auto Leftovers = [&](const SetType &A, const SetType &B) {298      SetType Diff = A;299      berase_if(Diff, [&](MVT T) { return B.count(T) || !P(T); });300      return Diff;301    };302 303    if (InW) {304      SetType OutLeftovers = Leftovers(Out, In);305      if (OutLeftovers.size() < 2) {306        // WildVT not added to Out. Keep the possible single leftover.307        return false;308      }309      // WildVT replaces the leftovers.310      berase_if(Out, CompIn);311      Out.insert(*WildVT);312      return true;313    }314 315    // OutW == true316    SetType InLeftovers = Leftovers(In, Out);317    unsigned SizeOut = Out.size();318    berase_if(Out, CompIn); // This will remove at least the WildVT.319    if (InLeftovers.size() < 2) {320      // WildVT deleted from Out. Add back the possible single leftover.321      Out.insert(InLeftovers);322      return true;323    }324 325    // Keep the WildVT in Out.326    Out.insert(*WildVT);327    // If WildVT was the only element initially removed from Out, then Out328    // has not changed.329    return SizeOut != Out.size();330  };331 332  // Note: must be non-overlapping333  using WildPartT = std::pair<MVT, std::function<bool(MVT)>>;334  static const WildPartT WildParts[] = {335      {MVT::iPTR, [](MVT T) { return T.isScalarInteger() || T == MVT::iPTR; }},336      {MVT::cPTR,337       [](MVT T) { return T.isCheriCapability() || T == MVT::cPTR; }},338  };339 340  bool Changed = false;341  for (const auto &I : WildParts)342    Changed |= IntersectP(I.first, I.second);343 344  Changed |= IntersectP(std::nullopt, [&](MVT T) {345    return !any_of(WildParts, [=](const WildPartT &I) { return I.second(T); });346  });347 348  return Changed;349}350 351bool TypeSetByHwMode::validate() const {352  if (empty())353    return true;354  bool AllEmpty = true;355  for (const auto &I : *this)356    AllEmpty &= I.second.empty();357  return !AllEmpty;358}359 360// --- TypeInfer361 362bool TypeInfer::MergeInTypeInfo(TypeSetByHwMode &Out,363                                const TypeSetByHwMode &In) const {364  ValidateOnExit _1(Out, *this);365  In.validate();366  if (In.empty() || Out == In || TP.hasError())367    return false;368  if (Out.empty()) {369    Out = In;370    return true;371  }372 373  bool Changed = Out.constrain(In);374  if (Changed && Out.empty())375    TP.error("Type contradiction");376 377  return Changed;378}379 380bool TypeInfer::forceArbitrary(TypeSetByHwMode &Out) {381  ValidateOnExit _1(Out, *this);382  if (TP.hasError())383    return false;384  assert(!Out.empty() && "cannot pick from an empty set");385 386  bool Changed = false;387  for (auto &I : Out) {388    TypeSetByHwMode::SetType &S = I.second;389    if (S.size() <= 1)390      continue;391    MVT T = *S.begin(); // Pick the first element.392    S.clear();393    S.insert(T);394    Changed = true;395  }396  return Changed;397}398 399bool TypeInfer::EnforceInteger(TypeSetByHwMode &Out) {400  ValidateOnExit _1(Out, *this);401  if (TP.hasError())402    return false;403  if (!Out.empty())404    return Out.constrain(isIntegerOrPtr);405 406  return Out.assign_if(getLegalTypes(), isIntegerOrPtr);407}408 409bool TypeInfer::EnforceFloatingPoint(TypeSetByHwMode &Out) {410  ValidateOnExit _1(Out, *this);411  if (TP.hasError())412    return false;413  if (!Out.empty())414    return Out.constrain(isFloatingPoint);415 416  return Out.assign_if(getLegalTypes(), isFloatingPoint);417}418 419bool TypeInfer::EnforceScalar(TypeSetByHwMode &Out) {420  ValidateOnExit _1(Out, *this);421  if (TP.hasError())422    return false;423  if (!Out.empty())424    return Out.constrain(isScalar);425 426  return Out.assign_if(getLegalTypes(), isScalar);427}428 429bool TypeInfer::EnforceVector(TypeSetByHwMode &Out) {430  ValidateOnExit _1(Out, *this);431  if (TP.hasError())432    return false;433  if (!Out.empty())434    return Out.constrain(isVector);435 436  return Out.assign_if(getLegalTypes(), isVector);437}438 439bool TypeInfer::EnforceAny(TypeSetByHwMode &Out) {440  ValidateOnExit _1(Out, *this);441  if (TP.hasError() || !Out.empty())442    return false;443 444  Out = getLegalTypes();445  return true;446}447 448template <typename Iter, typename Pred, typename Less>449static Iter min_if(Iter B, Iter E, Pred P, Less L) {450  if (B == E)451    return E;452  Iter Min = E;453  for (Iter I = B; I != E; ++I) {454    if (!P(*I))455      continue;456    if (Min == E || L(*I, *Min))457      Min = I;458  }459  return Min;460}461 462template <typename Iter, typename Pred, typename Less>463static Iter max_if(Iter B, Iter E, Pred P, Less L) {464  if (B == E)465    return E;466  Iter Max = E;467  for (Iter I = B; I != E; ++I) {468    if (!P(*I))469      continue;470    if (Max == E || L(*Max, *I))471      Max = I;472  }473  return Max;474}475 476/// Make sure that for each type in Small, there exists a larger type in Big.477bool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big,478                                   bool SmallIsVT) {479  ValidateOnExit _1(Small, *this), _2(Big, *this);480  if (TP.hasError())481    return false;482  bool Changed = false;483 484  assert((!SmallIsVT || !Small.empty()) &&485         "Small should not be empty for SDTCisVTSmallerThanOp");486 487  if (Small.empty())488    Changed |= EnforceAny(Small);489  if (Big.empty())490    Changed |= EnforceAny(Big);491 492  assert(Small.hasDefault() && Big.hasDefault());493 494  SmallVector<unsigned, 4> Modes;495  union_modes(Small, Big, Modes);496 497  // 1. Only allow integer or floating point types and make sure that498  //    both sides are both integer or both floating point.499  // 2. Make sure that either both sides have vector types, or neither500  //    of them does.501  for (unsigned M : Modes) {502    TypeSetByHwMode::SetType &S = Small.get(M);503    TypeSetByHwMode::SetType &B = Big.get(M);504 505    assert((!SmallIsVT || !S.empty()) && "Expected non-empty type");506 507    if (any_of(S, isIntegerOrPtr) && any_of(B, isIntegerOrPtr)) {508      auto NotInt = [](MVT VT) { return !isIntegerOrPtr(VT); };509      Changed |= berase_if(S, NotInt);510      Changed |= berase_if(B, NotInt);511    } else if (any_of(S, isFloatingPoint) && any_of(B, isFloatingPoint)) {512      auto NotFP = [](MVT VT) { return !isFloatingPoint(VT); };513      Changed |= berase_if(S, NotFP);514      Changed |= berase_if(B, NotFP);515    } else if (SmallIsVT && B.empty()) {516      // B is empty and since S is a specific VT, it will never be empty. Don't517      // report this as a change, just clear S and continue. This prevents an518      // infinite loop.519      S.clear();520    } else if (S.empty() || B.empty()) {521      Changed = !S.empty() || !B.empty();522      S.clear();523      B.clear();524    } else {525      TP.error("Incompatible types");526      return Changed;527    }528 529    if (none_of(S, isVector) || none_of(B, isVector)) {530      Changed |= berase_if(S, isVector);531      Changed |= berase_if(B, isVector);532    }533  }534 535  auto LT = [](MVT A, MVT B) -> bool {536    // Always treat non-scalable MVTs as smaller than scalable MVTs for the537    // purposes of ordering.538    auto ASize = std::tuple(A.isScalableVector(), A.getScalarSizeInBits(),539                            A.getSizeInBits().getKnownMinValue());540    auto BSize = std::tuple(B.isScalableVector(), B.getScalarSizeInBits(),541                            B.getSizeInBits().getKnownMinValue());542    return ASize < BSize;543  };544  auto SameKindLE = [](MVT A, MVT B) -> bool {545    // This function is used when removing elements: when a vector is compared546    // to a non-vector or a scalable vector to any non-scalable MVT, it should547    // return false (to avoid removal).548    if (std::tuple(A.isVector(), A.isScalableVector()) !=549        std::tuple(B.isVector(), B.isScalableVector()))550      return false;551 552    return std::tuple(A.getScalarSizeInBits(),553                      A.getSizeInBits().getKnownMinValue()) <=554           std::tuple(B.getScalarSizeInBits(),555                      B.getSizeInBits().getKnownMinValue());556  };557 558  for (unsigned M : Modes) {559    TypeSetByHwMode::SetType &S = Small.get(M);560    TypeSetByHwMode::SetType &B = Big.get(M);561    // MinS = min scalar in Small, remove all scalars from Big that are562    // smaller-or-equal than MinS.563    auto MinS = min_if(S.begin(), S.end(), isScalar, LT);564    if (MinS != S.end())565      Changed |=566          berase_if(B, std::bind(SameKindLE, std::placeholders::_1, *MinS));567 568    // MaxS = max scalar in Big, remove all scalars from Small that are569    // larger than MaxS.570    auto MaxS = max_if(B.begin(), B.end(), isScalar, LT);571    if (MaxS != B.end())572      Changed |=573          berase_if(S, std::bind(SameKindLE, *MaxS, std::placeholders::_1));574 575    // MinV = min vector in Small, remove all vectors from Big that are576    // smaller-or-equal than MinV.577    auto MinV = min_if(S.begin(), S.end(), isVector, LT);578    if (MinV != S.end())579      Changed |=580          berase_if(B, std::bind(SameKindLE, std::placeholders::_1, *MinV));581 582    // MaxV = max vector in Big, remove all vectors from Small that are583    // larger than MaxV.584    auto MaxV = max_if(B.begin(), B.end(), isVector, LT);585    if (MaxV != B.end())586      Changed |=587          berase_if(S, std::bind(SameKindLE, *MaxV, std::placeholders::_1));588  }589 590  return Changed;591}592 593/// 1. Ensure that for each type T in Vec, T is a vector type, and that594///    for each type U in Elem, U is a scalar type.595/// 2. Ensure that for each (scalar) type U in Elem, there exists a (vector)596///    type T in Vec, such that U is the element type of T.597bool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,598                                       TypeSetByHwMode &Elem) {599  ValidateOnExit _1(Vec, *this), _2(Elem, *this);600  if (TP.hasError())601    return false;602  bool Changed = false;603 604  if (Vec.empty())605    Changed |= EnforceVector(Vec);606  if (Elem.empty())607    Changed |= EnforceScalar(Elem);608 609  SmallVector<unsigned, 4> Modes;610  union_modes(Vec, Elem, Modes);611  for (unsigned M : Modes) {612    TypeSetByHwMode::SetType &V = Vec.get(M);613    TypeSetByHwMode::SetType &E = Elem.get(M);614 615    Changed |= berase_if(V, isScalar); // Scalar = !vector616    Changed |= berase_if(E, isVector); // Vector = !scalar617    assert(!V.empty() && !E.empty());618 619    MachineValueTypeSet VT, ST;620    // Collect element types from the "vector" set.621    for (MVT T : V)622      VT.insert(T.getVectorElementType());623    // Collect scalar types from the "element" set.624    for (MVT T : E)625      ST.insert(T);626 627    // Remove from V all (vector) types whose element type is not in S.628    Changed |= berase_if(V, [&ST](MVT T) -> bool {629      return !ST.count(T.getVectorElementType());630    });631    // Remove from E all (scalar) types, for which there is no corresponding632    // type in V.633    Changed |= berase_if(E, [&VT](MVT T) -> bool { return !VT.count(T); });634  }635 636  return Changed;637}638 639bool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,640                                       const ValueTypeByHwMode &VVT) {641  TypeSetByHwMode Tmp(VVT);642  ValidateOnExit _1(Vec, *this), _2(Tmp, *this);643  return EnforceVectorEltTypeIs(Vec, Tmp);644}645 646/// Ensure that for each type T in Sub, T is a vector type, and there647/// exists a type U in Vec such that U is a vector type with the same648/// element type as T and at least as many elements as T.649bool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,650                                             TypeSetByHwMode &Sub) {651  ValidateOnExit _1(Vec, *this), _2(Sub, *this);652  if (TP.hasError())653    return false;654 655  /// Return true if B is a suB-vector of P, i.e. P is a suPer-vector of B.656  auto IsSubVec = [](MVT B, MVT P) -> bool {657    if (!B.isVector() || !P.isVector())658      return false;659    // Logically a <4 x i32> is a valid subvector of <n x 4 x i32>660    // but until there are obvious use-cases for this, keep the661    // types separate.662    if (B.isScalableVector() != P.isScalableVector())663      return false;664    if (B.getVectorElementType() != P.getVectorElementType())665      return false;666    return B.getVectorMinNumElements() < P.getVectorMinNumElements();667  };668 669  /// Return true if S has no element (vector type) that T is a sub-vector of,670  /// i.e. has the same element type as T and more elements.671  auto NoSubV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool {672    for (auto I : S)673      if (IsSubVec(T, I))674        return false;675    return true;676  };677 678  /// Return true if S has no element (vector type) that T is a super-vector679  /// of, i.e. has the same element type as T and fewer elements.680  auto NoSupV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool {681    for (auto I : S)682      if (IsSubVec(I, T))683        return false;684    return true;685  };686 687  bool Changed = false;688 689  if (Vec.empty())690    Changed |= EnforceVector(Vec);691  if (Sub.empty())692    Changed |= EnforceVector(Sub);693 694  SmallVector<unsigned, 4> Modes;695  union_modes(Vec, Sub, Modes);696  for (unsigned M : Modes) {697    TypeSetByHwMode::SetType &S = Sub.get(M);698    TypeSetByHwMode::SetType &V = Vec.get(M);699 700    Changed |= berase_if(S, isScalar);701 702    // Erase all types from S that are not sub-vectors of a type in V.703    Changed |= berase_if(S, std::bind(NoSubV, V, std::placeholders::_1));704 705    // Erase all types from V that are not super-vectors of a type in S.706    Changed |= berase_if(V, std::bind(NoSupV, S, std::placeholders::_1));707  }708 709  return Changed;710}711 712/// 1. Ensure that V has a scalar type iff W has a scalar type.713/// 2. Ensure that for each vector type T in V, there exists a vector714///    type U in W, such that T and U have the same number of elements.715/// 3. Ensure that for each vector type U in W, there exists a vector716///    type T in V, such that T and U have the same number of elements717///    (reverse of 2).718bool TypeInfer::EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W) {719  ValidateOnExit _1(V, *this), _2(W, *this);720  if (TP.hasError())721    return false;722 723  bool Changed = false;724  if (V.empty())725    Changed |= EnforceAny(V);726  if (W.empty())727    Changed |= EnforceAny(W);728 729  // An actual vector type cannot have 0 elements, so we can treat scalars730  // as zero-length vectors. This way both vectors and scalars can be731  // processed identically.732  auto NoLength = [](const SmallDenseSet<ElementCount> &Lengths,733                     MVT T) -> bool {734    return !Lengths.contains(T.isVector() ? T.getVectorElementCount()735                                          : ElementCount());736  };737 738  SmallVector<unsigned, 4> Modes;739  union_modes(V, W, Modes);740  for (unsigned M : Modes) {741    TypeSetByHwMode::SetType &VS = V.get(M);742    TypeSetByHwMode::SetType &WS = W.get(M);743 744    SmallDenseSet<ElementCount> VN, WN;745    for (MVT T : VS)746      VN.insert(T.isVector() ? T.getVectorElementCount() : ElementCount());747    for (MVT T : WS)748      WN.insert(T.isVector() ? T.getVectorElementCount() : ElementCount());749 750    Changed |= berase_if(VS, std::bind(NoLength, WN, std::placeholders::_1));751    Changed |= berase_if(WS, std::bind(NoLength, VN, std::placeholders::_1));752  }753  return Changed;754}755 756namespace {757struct TypeSizeComparator {758  bool operator()(const TypeSize &LHS, const TypeSize &RHS) const {759    return std::tuple(LHS.isScalable(), LHS.getKnownMinValue()) <760           std::tuple(RHS.isScalable(), RHS.getKnownMinValue());761  }762};763} // end anonymous namespace764 765/// 1. Ensure that for each type T in A, there exists a type U in B,766///    such that T and U have equal size in bits.767/// 2. Ensure that for each type U in B, there exists a type T in A768///    such that T and U have equal size in bits (reverse of 1).769bool TypeInfer::EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B) {770  ValidateOnExit _1(A, *this), _2(B, *this);771  if (TP.hasError())772    return false;773  bool Changed = false;774  if (A.empty())775    Changed |= EnforceAny(A);776  if (B.empty())777    Changed |= EnforceAny(B);778 779  using TypeSizeSet = SmallSet<TypeSize, 2, TypeSizeComparator>;780 781  auto NoSize = [](const TypeSizeSet &Sizes, MVT T) -> bool {782    return !Sizes.contains(T.getSizeInBits());783  };784 785  SmallVector<unsigned, 4> Modes;786  union_modes(A, B, Modes);787  for (unsigned M : Modes) {788    TypeSetByHwMode::SetType &AS = A.get(M);789    TypeSetByHwMode::SetType &BS = B.get(M);790    TypeSizeSet AN, BN;791 792    for (MVT T : AS)793      AN.insert(T.getSizeInBits());794    for (MVT T : BS)795      BN.insert(T.getSizeInBits());796 797    Changed |= berase_if(AS, std::bind(NoSize, BN, std::placeholders::_1));798    Changed |= berase_if(BS, std::bind(NoSize, AN, std::placeholders::_1));799  }800 801  return Changed;802}803 804void TypeInfer::expandOverloads(TypeSetByHwMode &VTS) const {805  ValidateOnExit _1(VTS, *this);806  const TypeSetByHwMode &Legal = getLegalTypes();807  assert(Legal.isSimple() && "Default-mode only expected");808  const TypeSetByHwMode::SetType &LegalTypes = Legal.getSimple();809 810  for (auto &I : VTS)811    expandOverloads(I.second, LegalTypes);812}813 814void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,815                                const TypeSetByHwMode::SetType &Legal) const {816  if (Out.count(MVT::pAny)) {817    Out.erase(MVT::pAny);818    Out.insert(MVT::iPTR);819    for (MVT T : MVT::cheri_capability_valuetypes()) {820      if (Legal.count(T))821        Out.insert(MVT::cPTR);822    }823  } else if (Out.count(MVT::iAny)) {824    Out.erase(MVT::iAny);825    for (MVT T : MVT::integer_valuetypes())826      if (Legal.count(T))827        Out.insert(T);828    for (MVT T : MVT::integer_fixedlen_vector_valuetypes())829      if (Legal.count(T))830        Out.insert(T);831    for (MVT T : MVT::integer_scalable_vector_valuetypes())832      if (Legal.count(T))833        Out.insert(T);834  } else if (Out.count(MVT::fAny)) {835    Out.erase(MVT::fAny);836    for (MVT T : MVT::fp_valuetypes())837      if (Legal.count(T))838        Out.insert(T);839    for (MVT T : MVT::fp_fixedlen_vector_valuetypes())840      if (Legal.count(T))841        Out.insert(T);842    for (MVT T : MVT::fp_scalable_vector_valuetypes())843      if (Legal.count(T))844        Out.insert(T);845  } else if (Out.count(MVT::vAny)) {846    Out.erase(MVT::vAny);847    for (MVT T : MVT::vector_valuetypes())848      if (Legal.count(T))849        Out.insert(T);850  } else if (Out.count(MVT::Any)) {851    Out.erase(MVT::Any);852    for (MVT T : MVT::all_valuetypes())853      if (Legal.count(T))854        Out.insert(T);855  }856}857 858const TypeSetByHwMode &TypeInfer::getLegalTypes() const {859  if (!LegalTypesCached) {860    TypeSetByHwMode::SetType &LegalTypes = LegalCache.getOrCreate(DefaultMode);861    // Stuff all types from all modes into the default mode.862    const TypeSetByHwMode &LTS = TP.getDAGPatterns().getLegalTypes();863    for (const auto &I : LTS)864      LegalTypes.insert(I.second);865    LegalTypesCached = true;866  }867  assert(LegalCache.isSimple() && "Default-mode only expected");868  return LegalCache;869}870 871TypeInfer::ValidateOnExit::~ValidateOnExit() {872  if (Infer.Validate && !VTS.validate()) {873#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)874    errs() << "Type set is empty for each HW mode:\n"875              "possible type contradiction in the pattern below "876              "(use -print-records with llvm-tblgen to see all "877              "expanded records).\n";878    Infer.TP.dump();879    errs() << "Generated from record:\n";880    Infer.TP.getRecord()->dump();881#endif882    PrintFatalError(Infer.TP.getRecord()->getLoc(),883                    "Type set is empty for each HW mode in '" +884                        Infer.TP.getRecord()->getName() + "'");885  }886}887 888//===----------------------------------------------------------------------===//889// ScopedName Implementation890//===----------------------------------------------------------------------===//891 892bool ScopedName::operator==(const ScopedName &o) const {893  return Scope == o.Scope && Identifier == o.Identifier;894}895 896bool ScopedName::operator!=(const ScopedName &o) const { return !(*this == o); }897 898//===----------------------------------------------------------------------===//899// TreePredicateFn Implementation900//===----------------------------------------------------------------------===//901 902/// TreePredicateFn constructor.  Here 'N' is a subclass of PatFrag.903TreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) {904  assert(905      (!hasPredCode() || !hasImmCode()) &&906      ".td file corrupt: can't have a node predicate *and* an imm predicate");907 908  if (hasGISelPredicateCode() && hasGISelLeafPredicateCode())909    PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),910                    ".td file corrupt: can't have GISelPredicateCode *and* "911                    "GISelLeafPredicateCode");912}913 914bool TreePredicateFn::hasPredCode() const {915  return isLoad() || isStore() || isAtomic() || hasNoUse() || hasOneUse() ||916         !PatFragRec->getRecord()->getValueAsString("PredicateCode").empty();917}918 919std::string TreePredicateFn::getPredCode() const {920  std::string Code;921 922  if (!isLoad() && !isStore() && !isAtomic() && getMemoryVT())923    PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),924                    "MemoryVT requires IsLoad or IsStore or IsAtomic");925 926  if (!isLoad() && !isStore()) {927    if (isUnindexed())928      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),929                      "IsUnindexed requires IsLoad or IsStore");930 931    if (getScalarMemoryVT())932      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),933                      "ScalarMemoryVT requires IsLoad or IsStore");934  }935 936  if (isLoad() + isStore() + isAtomic() > 1)937    PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),938                    "IsLoad, IsStore, and IsAtomic are mutually exclusive");939 940  if (isLoad()) {941    if (!isUnindexed() && !isNonExtLoad() && !isAnyExtLoad() &&942        !isSignExtLoad() && !isZeroExtLoad() && getMemoryVT() == nullptr &&943        getScalarMemoryVT() == nullptr && getAddressSpaces() == nullptr &&944        getMinAlignment() < 1)945      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),946                      "IsLoad cannot be used by itself");947  } else if (!isAtomic()) {948    if (isNonExtLoad())949      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),950                      "IsNonExtLoad requires IsLoad or IsAtomic");951    if (isAnyExtLoad())952      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),953                      "IsAnyExtLoad requires IsLoad or IsAtomic");954    if (isSignExtLoad())955      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),956                      "IsSignExtLoad requires IsLoad or IsAtomic");957    if (isZeroExtLoad())958      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),959                      "IsZeroExtLoad requires IsLoad or IsAtomic");960  }961 962  if (isStore()) {963    if (!isUnindexed() && !isTruncStore() && !isNonTruncStore() &&964        getMemoryVT() == nullptr && getScalarMemoryVT() == nullptr &&965        getAddressSpaces() == nullptr && getMinAlignment() < 1)966      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),967                      "IsStore cannot be used by itself");968  } else {969    if (isNonTruncStore())970      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),971                      "IsNonTruncStore requires IsStore");972    if (isTruncStore())973      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),974                      "IsTruncStore requires IsStore");975  }976 977  if (isAtomic()) {978    if (getMemoryVT() == nullptr && getAddressSpaces() == nullptr &&979        // FIXME: Should atomic loads be IsLoad, IsAtomic, or both?980        !isNonExtLoad() && !isAnyExtLoad() && !isZeroExtLoad() &&981        !isSignExtLoad() && !isAtomicOrderingMonotonic() &&982        !isAtomicOrderingAcquire() && !isAtomicOrderingRelease() &&983        !isAtomicOrderingAcquireRelease() &&984        !isAtomicOrderingSequentiallyConsistent() &&985        !isAtomicOrderingAcquireOrStronger() &&986        !isAtomicOrderingReleaseOrStronger() &&987        !isAtomicOrderingWeakerThanAcquire() &&988        !isAtomicOrderingWeakerThanRelease())989      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),990                      "IsAtomic cannot be used by itself");991  } else {992    if (isAtomicOrderingMonotonic())993      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),994                      "IsAtomicOrderingMonotonic requires IsAtomic");995    if (isAtomicOrderingAcquire())996      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),997                      "IsAtomicOrderingAcquire requires IsAtomic");998    if (isAtomicOrderingRelease())999      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1000                      "IsAtomicOrderingRelease requires IsAtomic");1001    if (isAtomicOrderingAcquireRelease())1002      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1003                      "IsAtomicOrderingAcquireRelease requires IsAtomic");1004    if (isAtomicOrderingSequentiallyConsistent())1005      PrintFatalError(1006          getOrigPatFragRecord()->getRecord()->getLoc(),1007          "IsAtomicOrderingSequentiallyConsistent requires IsAtomic");1008    if (isAtomicOrderingAcquireOrStronger())1009      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1010                      "IsAtomicOrderingAcquireOrStronger requires IsAtomic");1011    if (isAtomicOrderingReleaseOrStronger())1012      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1013                      "IsAtomicOrderingReleaseOrStronger requires IsAtomic");1014    if (isAtomicOrderingWeakerThanAcquire())1015      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1016                      "IsAtomicOrderingWeakerThanAcquire requires IsAtomic");1017  }1018 1019  if (isLoad() || isStore() || isAtomic()) {1020    if (const ListInit *AddressSpaces = getAddressSpaces()) {1021      Code += "unsigned AddrSpace = cast<MemSDNode>(N)->getAddressSpace();\n"1022              " if (";1023 1024      ListSeparator LS(" && ");1025      for (const Init *Val : AddressSpaces->getElements()) {1026        Code += LS;1027 1028        const IntInit *IntVal = dyn_cast<IntInit>(Val);1029        if (!IntVal) {1030          PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1031                          "AddressSpaces element must be integer");1032        }1033 1034        Code += "AddrSpace != " + utostr(IntVal->getValue());1035      }1036 1037      Code += ")\nreturn false;\n";1038    }1039 1040    int64_t MinAlign = getMinAlignment();1041    if (MinAlign > 0) {1042      Code += "if (cast<MemSDNode>(N)->getAlign() < Align(";1043      Code += utostr(MinAlign);1044      Code += "))\nreturn false;\n";1045    }1046 1047    if (const Record *MemoryVT = getMemoryVT())1048      Code += ("if (cast<MemSDNode>(N)->getMemoryVT() != MVT::" +1049               MemoryVT->getName() + ") return false;\n")1050                  .str();1051  }1052 1053  if (isAtomic() && isAtomicOrderingMonotonic())1054    Code += "if (cast<AtomicSDNode>(N)->getMergedOrdering() != "1055            "AtomicOrdering::Monotonic) return false;\n";1056  if (isAtomic() && isAtomicOrderingAcquire())1057    Code += "if (cast<AtomicSDNode>(N)->getMergedOrdering() != "1058            "AtomicOrdering::Acquire) return false;\n";1059  if (isAtomic() && isAtomicOrderingRelease())1060    Code += "if (cast<AtomicSDNode>(N)->getMergedOrdering() != "1061            "AtomicOrdering::Release) return false;\n";1062  if (isAtomic() && isAtomicOrderingAcquireRelease())1063    Code += "if (cast<AtomicSDNode>(N)->getMergedOrdering() != "1064            "AtomicOrdering::AcquireRelease) return false;\n";1065  if (isAtomic() && isAtomicOrderingSequentiallyConsistent())1066    Code += "if (cast<AtomicSDNode>(N)->getMergedOrdering() != "1067            "AtomicOrdering::SequentiallyConsistent) return false;\n";1068 1069  if (isAtomic() && isAtomicOrderingAcquireOrStronger())1070    Code +=1071        "if (!isAcquireOrStronger(cast<AtomicSDNode>(N)->getMergedOrdering())) "1072        "return false;\n";1073  if (isAtomic() && isAtomicOrderingWeakerThanAcquire())1074    Code +=1075        "if (isAcquireOrStronger(cast<AtomicSDNode>(N)->getMergedOrdering())) "1076        "return false;\n";1077 1078  if (isAtomic() && isAtomicOrderingReleaseOrStronger())1079    Code +=1080        "if (!isReleaseOrStronger(cast<AtomicSDNode>(N)->getMergedOrdering())) "1081        "return false;\n";1082  if (isAtomic() && isAtomicOrderingWeakerThanRelease())1083    Code +=1084        "if (isReleaseOrStronger(cast<AtomicSDNode>(N)->getMergedOrdering())) "1085        "return false;\n";1086 1087  if (isAtomic()) {1088    if ((isNonExtLoad() + isAnyExtLoad() + isSignExtLoad() + isZeroExtLoad()) >1089        1)1090      PrintFatalError(1091          getOrigPatFragRecord()->getRecord()->getLoc(),1092          "IsNonExtLoad, IsAnyExtLoad, IsSignExtLoad, and IsZeroExtLoad are "1093          "mutually exclusive");1094 1095    if (isNonExtLoad())1096      Code += "if (cast<AtomicSDNode>(N)->getExtensionType() != "1097              "ISD::NON_EXTLOAD) return false;\n";1098    if (isAnyExtLoad())1099      Code += "if (cast<AtomicSDNode>(N)->getExtensionType() != ISD::EXTLOAD) "1100              "return false;\n";1101    if (isSignExtLoad())1102      Code += "if (cast<AtomicSDNode>(N)->getExtensionType() != ISD::SEXTLOAD) "1103              "return false;\n";1104    if (isZeroExtLoad())1105      Code += "if (cast<AtomicSDNode>(N)->getExtensionType() != ISD::ZEXTLOAD) "1106              "return false;\n";1107  }1108 1109  if (isLoad() || isStore()) {1110    StringRef SDNodeName = isLoad() ? "LoadSDNode" : "StoreSDNode";1111 1112    if (isUnindexed())1113      Code += ("if (cast<" + SDNodeName +1114               ">(N)->getAddressingMode() != ISD::UNINDEXED) "1115               "return false;\n")1116                  .str();1117 1118    if (isLoad()) {1119      if ((isNonExtLoad() + isAnyExtLoad() + isSignExtLoad() +1120           isZeroExtLoad()) > 1)1121        PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1122                        "IsNonExtLoad, IsAnyExtLoad, IsSignExtLoad, and "1123                        "IsZeroExtLoad are mutually exclusive");1124      if (isNonExtLoad())1125        Code += "if (cast<LoadSDNode>(N)->getExtensionType() != "1126                "ISD::NON_EXTLOAD) return false;\n";1127      if (isAnyExtLoad())1128        Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::EXTLOAD) "1129                "return false;\n";1130      if (isSignExtLoad())1131        Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::SEXTLOAD) "1132                "return false;\n";1133      if (isZeroExtLoad())1134        Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::ZEXTLOAD) "1135                "return false;\n";1136    } else {1137      if ((isNonTruncStore() + isTruncStore()) > 1)1138        PrintFatalError(1139            getOrigPatFragRecord()->getRecord()->getLoc(),1140            "IsNonTruncStore, and IsTruncStore are mutually exclusive");1141      if (isNonTruncStore())1142        Code +=1143            " if (cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n";1144      if (isTruncStore())1145        Code +=1146            " if (!cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n";1147    }1148 1149    if (const Record *ScalarMemoryVT = getScalarMemoryVT())1150      Code += ("if (cast<" + SDNodeName +1151               ">(N)->getMemoryVT().getScalarType() != MVT::" +1152               ScalarMemoryVT->getName() + ") return false;\n")1153                  .str();1154  }1155 1156  if (hasNoUse())1157    Code += "if (N->hasAnyUseOfValue(0)) return false;\n";1158  if (hasOneUse())1159    Code += "if (!N->hasNUsesOfValue(1, 0)) return false;\n";1160 1161  std::string PredicateCode =1162      PatFragRec->getRecord()->getValueAsString("PredicateCode").str();1163 1164  Code += PredicateCode;1165 1166  if (PredicateCode.empty() && !Code.empty())1167    Code += "return true;\n";1168 1169  return Code;1170}1171 1172bool TreePredicateFn::hasImmCode() const {1173  return !PatFragRec->getRecord()->getValueAsString("ImmediateCode").empty();1174}1175 1176std::string TreePredicateFn::getImmCode() const {1177  return PatFragRec->getRecord()->getValueAsString("ImmediateCode").str();1178}1179 1180bool TreePredicateFn::immCodeUsesAPInt() const {1181  return getOrigPatFragRecord()->getRecord()->getValueAsBit("IsAPInt");1182}1183 1184bool TreePredicateFn::immCodeUsesAPFloat() const {1185  bool Unset;1186  // The return value will be false when IsAPFloat is unset.1187  return getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset("IsAPFloat",1188                                                                   Unset);1189}1190 1191bool TreePredicateFn::isPredefinedPredicateEqualTo(StringRef Field,1192                                                   bool Value) const {1193  bool Unset;1194  bool Result =1195      getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset(Field, Unset);1196  if (Unset)1197    return false;1198  return Result == Value;1199}1200bool TreePredicateFn::usesOperands() const {1201  return isPredefinedPredicateEqualTo("PredicateCodeUsesOperands", true);1202}1203bool TreePredicateFn::hasNoUse() const {1204  return isPredefinedPredicateEqualTo("HasNoUse", true);1205}1206bool TreePredicateFn::hasOneUse() const {1207  return isPredefinedPredicateEqualTo("HasOneUse", true);1208}1209bool TreePredicateFn::isLoad() const {1210  return isPredefinedPredicateEqualTo("IsLoad", true);1211}1212bool TreePredicateFn::isStore() const {1213  return isPredefinedPredicateEqualTo("IsStore", true);1214}1215bool TreePredicateFn::isAtomic() const {1216  return isPredefinedPredicateEqualTo("IsAtomic", true);1217}1218bool TreePredicateFn::isUnindexed() const {1219  return isPredefinedPredicateEqualTo("IsUnindexed", true);1220}1221bool TreePredicateFn::isNonExtLoad() const {1222  return isPredefinedPredicateEqualTo("IsNonExtLoad", true);1223}1224bool TreePredicateFn::isAnyExtLoad() const {1225  return isPredefinedPredicateEqualTo("IsAnyExtLoad", true);1226}1227bool TreePredicateFn::isSignExtLoad() const {1228  return isPredefinedPredicateEqualTo("IsSignExtLoad", true);1229}1230bool TreePredicateFn::isZeroExtLoad() const {1231  return isPredefinedPredicateEqualTo("IsZeroExtLoad", true);1232}1233bool TreePredicateFn::isNonTruncStore() const {1234  return isPredefinedPredicateEqualTo("IsTruncStore", false);1235}1236bool TreePredicateFn::isTruncStore() const {1237  return isPredefinedPredicateEqualTo("IsTruncStore", true);1238}1239bool TreePredicateFn::isAtomicOrderingMonotonic() const {1240  return isPredefinedPredicateEqualTo("IsAtomicOrderingMonotonic", true);1241}1242bool TreePredicateFn::isAtomicOrderingAcquire() const {1243  return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquire", true);1244}1245bool TreePredicateFn::isAtomicOrderingRelease() const {1246  return isPredefinedPredicateEqualTo("IsAtomicOrderingRelease", true);1247}1248bool TreePredicateFn::isAtomicOrderingAcquireRelease() const {1249  return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireRelease", true);1250}1251bool TreePredicateFn::isAtomicOrderingSequentiallyConsistent() const {1252  return isPredefinedPredicateEqualTo("IsAtomicOrderingSequentiallyConsistent",1253                                      true);1254}1255bool TreePredicateFn::isAtomicOrderingAcquireOrStronger() const {1256  return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger",1257                                      true);1258}1259bool TreePredicateFn::isAtomicOrderingWeakerThanAcquire() const {1260  return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger",1261                                      false);1262}1263bool TreePredicateFn::isAtomicOrderingReleaseOrStronger() const {1264  return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger",1265                                      true);1266}1267bool TreePredicateFn::isAtomicOrderingWeakerThanRelease() const {1268  return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger",1269                                      false);1270}1271const Record *TreePredicateFn::getMemoryVT() const {1272  const Record *R = getOrigPatFragRecord()->getRecord();1273  if (R->isValueUnset("MemoryVT"))1274    return nullptr;1275  return R->getValueAsDef("MemoryVT");1276}1277 1278const ListInit *TreePredicateFn::getAddressSpaces() const {1279  const Record *R = getOrigPatFragRecord()->getRecord();1280  if (R->isValueUnset("AddressSpaces"))1281    return nullptr;1282  return R->getValueAsListInit("AddressSpaces");1283}1284 1285int64_t TreePredicateFn::getMinAlignment() const {1286  const Record *R = getOrigPatFragRecord()->getRecord();1287  if (R->isValueUnset("MinAlignment"))1288    return 0;1289  return R->getValueAsInt("MinAlignment");1290}1291 1292const Record *TreePredicateFn::getScalarMemoryVT() const {1293  const Record *R = getOrigPatFragRecord()->getRecord();1294  if (R->isValueUnset("ScalarMemoryVT"))1295    return nullptr;1296  return R->getValueAsDef("ScalarMemoryVT");1297}1298 1299bool TreePredicateFn::hasGISelPredicateCode() const {1300  return !PatFragRec->getRecord()1301              ->getValueAsString("GISelPredicateCode")1302              .empty();1303}1304 1305std::string TreePredicateFn::getGISelPredicateCode() const {1306  return PatFragRec->getRecord()->getValueAsString("GISelPredicateCode").str();1307}1308 1309bool TreePredicateFn::hasGISelLeafPredicateCode() const {1310  return PatFragRec->getRecord()1311      ->getValueAsOptionalString("GISelLeafPredicateCode")1312      .has_value();1313}1314 1315std::string TreePredicateFn::getGISelLeafPredicateCode() const {1316  return PatFragRec->getRecord()1317      ->getValueAsOptionalString("GISelLeafPredicateCode")1318      .value_or(StringRef())1319      .str();1320}1321 1322StringRef TreePredicateFn::getImmType() const {1323  if (immCodeUsesAPInt())1324    return "const APInt &";1325  if (immCodeUsesAPFloat())1326    return "const APFloat &";1327  return "int64_t";1328}1329 1330StringRef TreePredicateFn::getImmTypeIdentifier() const {1331  if (immCodeUsesAPInt())1332    return "APInt";1333  if (immCodeUsesAPFloat())1334    return "APFloat";1335  return "I64";1336}1337 1338/// isAlwaysTrue - Return true if this is a noop predicate.1339bool TreePredicateFn::isAlwaysTrue() const {1340  return !hasPredCode() && !hasImmCode();1341}1342 1343/// Return the name to use in the generated code to reference this, this is1344/// "Predicate_foo" if from a pattern fragment "foo".1345std::string TreePredicateFn::getFnName() const {1346  return "Predicate_" + PatFragRec->getRecord()->getName().str();1347}1348 1349/// getCodeToRunOnSDNode - Return the code for the function body that1350/// evaluates this predicate.  The argument is expected to be in "Node",1351/// not N.  This handles casting and conversion to a concrete node type as1352/// appropriate.1353std::string TreePredicateFn::getCodeToRunOnSDNode() const {1354  // Handle immediate predicates first.1355  std::string ImmCode = getImmCode();1356  if (!ImmCode.empty()) {1357    if (isLoad())1358      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1359                      "IsLoad cannot be used with ImmLeaf or its subclasses");1360    if (isStore())1361      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1362                      "IsStore cannot be used with ImmLeaf or its subclasses");1363    if (isUnindexed())1364      PrintFatalError(1365          getOrigPatFragRecord()->getRecord()->getLoc(),1366          "IsUnindexed cannot be used with ImmLeaf or its subclasses");1367    if (isNonExtLoad())1368      PrintFatalError(1369          getOrigPatFragRecord()->getRecord()->getLoc(),1370          "IsNonExtLoad cannot be used with ImmLeaf or its subclasses");1371    if (isAnyExtLoad())1372      PrintFatalError(1373          getOrigPatFragRecord()->getRecord()->getLoc(),1374          "IsAnyExtLoad cannot be used with ImmLeaf or its subclasses");1375    if (isSignExtLoad())1376      PrintFatalError(1377          getOrigPatFragRecord()->getRecord()->getLoc(),1378          "IsSignExtLoad cannot be used with ImmLeaf or its subclasses");1379    if (isZeroExtLoad())1380      PrintFatalError(1381          getOrigPatFragRecord()->getRecord()->getLoc(),1382          "IsZeroExtLoad cannot be used with ImmLeaf or its subclasses");1383    if (isNonTruncStore())1384      PrintFatalError(1385          getOrigPatFragRecord()->getRecord()->getLoc(),1386          "IsNonTruncStore cannot be used with ImmLeaf or its subclasses");1387    if (isTruncStore())1388      PrintFatalError(1389          getOrigPatFragRecord()->getRecord()->getLoc(),1390          "IsTruncStore cannot be used with ImmLeaf or its subclasses");1391    if (getMemoryVT())1392      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1393                      "MemoryVT cannot be used with ImmLeaf or its subclasses");1394    if (getScalarMemoryVT())1395      PrintFatalError(1396          getOrigPatFragRecord()->getRecord()->getLoc(),1397          "ScalarMemoryVT cannot be used with ImmLeaf or its subclasses");1398 1399    std::string Result = ("    " + getImmType() + " Imm = ").str();1400    if (immCodeUsesAPFloat())1401      Result += "cast<ConstantFPSDNode>(Op.getNode())->getValueAPF();\n";1402    else if (immCodeUsesAPInt())1403      Result += "Op->getAsAPIntVal();\n";1404    else1405      Result += "cast<ConstantSDNode>(Op.getNode())->getSExtValue();\n";1406    return Result + ImmCode;1407  }1408 1409  // Handle arbitrary node predicates.1410  assert(hasPredCode() && "Don't have any predicate code!");1411 1412  // If this is using PatFrags, there are multiple trees to search. They should1413  // all have the same class.  FIXME: Is there a way to find a common1414  // superclass?1415  StringRef ClassName;1416  for (const auto &Tree : PatFragRec->getTrees()) {1417    StringRef TreeClassName;1418    if (Tree->isLeaf())1419      TreeClassName = "SDNode";1420    else {1421      const Record *Op = Tree->getOperator();1422      const SDNodeInfo &Info = PatFragRec->getDAGPatterns().getSDNodeInfo(Op);1423      TreeClassName = Info.getSDClassName();1424    }1425 1426    if (ClassName.empty())1427      ClassName = TreeClassName;1428    else if (ClassName != TreeClassName) {1429      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),1430                      "PatFrags trees do not have consistent class");1431    }1432  }1433 1434  std::string Result;1435  if (ClassName == "SDNode")1436    Result = "    SDNode *N = Op.getNode();\n";1437  else1438    Result = "    auto *N = cast<" + ClassName.str() + ">(Op.getNode());\n";1439 1440  return (Twine(Result) + "    (void)N;\n" + getPredCode()).str();1441}1442 1443//===----------------------------------------------------------------------===//1444// PatternToMatch implementation1445//1446 1447static bool isImmAllOnesAllZerosMatch(const TreePatternNode &P) {1448  if (!P.isLeaf())1449    return false;1450  const DefInit *DI = dyn_cast<DefInit>(P.getLeafValue());1451  if (!DI)1452    return false;1453 1454  const Record *R = DI->getDef();1455  return R->getName() == "immAllOnesV" || R->getName() == "immAllZerosV";1456}1457 1458/// getPatternSize - Return the 'size' of this pattern.  We want to match large1459/// patterns before small ones.  This is used to determine the size of a1460/// pattern.1461static unsigned getPatternSize(const TreePatternNode &P,1462                               const CodeGenDAGPatterns &CGP) {1463  unsigned Size = 3; // The node itself.1464  // If the root node is a ConstantSDNode, increases its size.1465  // e.g. (set R32:$dst, 0).1466  if (P.isLeaf() && isa<IntInit>(P.getLeafValue()))1467    Size += 2;1468 1469  if (const ComplexPattern *AM = P.getComplexPatternInfo(CGP)) {1470    Size += AM->getComplexity();1471    // We don't want to count any children twice, so return early.1472    return Size;1473  }1474 1475  // If this node has some predicate function that must match, it adds to the1476  // complexity of this node.1477  if (!P.getPredicateCalls().empty())1478    ++Size;1479 1480  // Count children in the count if they are also nodes.1481  for (const TreePatternNode &Child : P.children()) {1482    if (!Child.isLeaf() && Child.getNumTypes()) {1483      const TypeSetByHwMode &T0 = Child.getExtType(0);1484      // At this point, all variable type sets should be simple, i.e. only1485      // have a default mode.1486      if (T0.getMachineValueType() != MVT::Other) {1487        Size += getPatternSize(Child, CGP);1488        continue;1489      }1490    }1491    if (Child.isLeaf()) {1492      if (isa<IntInit>(Child.getLeafValue()))1493        Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2).1494      else if (Child.getComplexPatternInfo(CGP))1495        Size += getPatternSize(Child, CGP);1496      else if (isImmAllOnesAllZerosMatch(Child))1497        Size += 4; // Matches a build_vector(+3) and a predicate (+1).1498      else if (!Child.getPredicateCalls().empty())1499        ++Size;1500    }1501  }1502 1503  return Size;1504}1505 1506/// Compute the complexity metric for the input pattern.  This roughly1507/// corresponds to the number of nodes that are covered.1508int PatternToMatch::getPatternComplexity(const CodeGenDAGPatterns &CGP) const {1509  return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity();1510}1511 1512void PatternToMatch::getPredicateRecords(1513    SmallVectorImpl<const Record *> &PredicateRecs) const {1514  for (const Init *I : Predicates->getElements()) {1515    if (const DefInit *Pred = dyn_cast<DefInit>(I)) {1516      const Record *Def = Pred->getDef();1517      if (!Def->isSubClassOf("Predicate")) {1518#ifndef NDEBUG1519        Def->dump();1520#endif1521        llvm_unreachable("Unknown predicate type!");1522      }1523      PredicateRecs.push_back(Def);1524    }1525  }1526  // Sort so that different orders get canonicalized to the same string.1527  llvm::sort(PredicateRecs, LessRecord());1528  // Remove duplicate predicates.1529  PredicateRecs.erase(llvm::unique(PredicateRecs), PredicateRecs.end());1530}1531 1532/// getPredicateCheck - Return a single string containing all of this1533/// pattern's predicates concatenated with "&&" operators.1534///1535std::string PatternToMatch::getPredicateCheck() const {1536  SmallVector<const Record *, 4> PredicateRecs;1537  getPredicateRecords(PredicateRecs);1538 1539  SmallString<128> PredicateCheck;1540  raw_svector_ostream OS(PredicateCheck);1541  ListSeparator LS(" && ");1542  for (const Record *Pred : PredicateRecs) {1543    StringRef CondString = Pred->getValueAsString("CondString");1544    if (CondString.empty())1545      continue;1546    OS << LS << '(' << CondString << ')';1547  }1548 1549  if (!HwModeFeatures.empty())1550    OS << LS << HwModeFeatures;1551 1552  return std::string(PredicateCheck);1553}1554 1555//===----------------------------------------------------------------------===//1556// SDTypeConstraint implementation1557//1558 1559SDTypeConstraint::SDTypeConstraint(const Record *R, const CodeGenHwModes &CGH) {1560  OperandNo = R->getValueAsInt("OperandNum");1561 1562  if (R->isSubClassOf("SDTCisVT")) {1563    ConstraintType = SDTCisVT;1564    VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH);1565    for (const auto &P : VVT)1566      if (P.second == MVT::isVoid)1567        PrintFatalError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT");1568  } else if (R->isSubClassOf("SDTCisPtrTy")) {1569    ConstraintType = SDTCisPtrTy;1570  } else if (R->isSubClassOf("SDTCisInt")) {1571    ConstraintType = SDTCisInt;1572  } else if (R->isSubClassOf("SDTCisFP")) {1573    ConstraintType = SDTCisFP;1574  } else if (R->isSubClassOf("SDTCisVec")) {1575    ConstraintType = SDTCisVec;1576  } else if (R->isSubClassOf("SDTCisSameAs")) {1577    ConstraintType = SDTCisSameAs;1578    OtherOperandNo = R->getValueAsInt("OtherOperandNum");1579  } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {1580    ConstraintType = SDTCisVTSmallerThanOp;1581    OtherOperandNo = R->getValueAsInt("OtherOperandNum");1582  } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) {1583    ConstraintType = SDTCisOpSmallerThanOp;1584    OtherOperandNo = R->getValueAsInt("BigOperandNum");1585  } else if (R->isSubClassOf("SDTCisEltOfVec")) {1586    ConstraintType = SDTCisEltOfVec;1587    OtherOperandNo = R->getValueAsInt("OtherOpNum");1588  } else if (R->isSubClassOf("SDTCisSubVecOfVec")) {1589    ConstraintType = SDTCisSubVecOfVec;1590    OtherOperandNo = R->getValueAsInt("OtherOpNum");1591  } else if (R->isSubClassOf("SDTCVecEltisVT")) {1592    ConstraintType = SDTCVecEltisVT;1593    VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH);1594    for (const auto &P : VVT) {1595      MVT T = P.second;1596      if (T.isVector())1597        PrintFatalError(R->getLoc(),1598                        "Cannot use vector type as SDTCVecEltisVT");1599      if (!T.isInteger() && !T.isFloatingPoint())1600        PrintFatalError(R->getLoc(), "Must use integer or floating point type "1601                                     "as SDTCVecEltisVT");1602    }1603  } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) {1604    ConstraintType = SDTCisSameNumEltsAs;1605    OtherOperandNo = R->getValueAsInt("OtherOperandNum");1606  } else if (R->isSubClassOf("SDTCisSameSizeAs")) {1607    ConstraintType = SDTCisSameSizeAs;1608    OtherOperandNo = R->getValueAsInt("OtherOperandNum");1609  } else {1610    PrintFatalError(R->getLoc(),1611                    "Unrecognized SDTypeConstraint '" + R->getName() + "'!\n");1612  }1613}1614 1615/// getOperandNum - Return the node corresponding to operand #OpNo in tree1616/// N, and the result number in ResNo.1617static TreePatternNode &getOperandNum(unsigned OpNo, TreePatternNode &N,1618                                      const SDNodeInfo &NodeInfo,1619                                      unsigned &ResNo) {1620  unsigned NumResults = NodeInfo.getNumResults();1621  if (OpNo < NumResults) {1622    ResNo = OpNo;1623    return N;1624  }1625 1626  OpNo -= NumResults;1627 1628  if (OpNo >= N.getNumChildren()) {1629    PrintFatalError([&N, OpNo, NumResults](raw_ostream &OS) {1630      OS << "Invalid operand number in type constraint " << (OpNo + NumResults);1631      N.print(OS);1632    });1633  }1634  return N.getChild(OpNo);1635}1636 1637/// ApplyTypeConstraint - Given a node in a pattern, apply this type1638/// constraint to the nodes operands.  This returns true if it makes a1639/// change, false otherwise.  If a type contradiction is found, flag an error.1640bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode &N,1641                                           const SDNodeInfo &NodeInfo,1642                                           TreePattern &TP) const {1643  if (TP.hasError())1644    return false;1645 1646  unsigned ResNo = 0; // The result number being referenced.1647  TreePatternNode &NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo);1648  TypeInfer &TI = TP.getInfer();1649 1650  switch (ConstraintType) {1651  case SDTCisVT:1652    // Operand must be a particular type.1653    return NodeToApply.UpdateNodeType(ResNo, VVT, TP);1654  case SDTCisPtrTy: {1655    // Operand must be a legal pointer (iPTR, or possibly cPTR) type.1656    const TypeSetByHwMode &PtrTys = TP.getDAGPatterns().getLegalPtrTypes();1657    return NodeToApply.UpdateNodeType(ResNo, PtrTys, TP);1658  }1659  case SDTCisInt:1660    // Require it to be one of the legal integer VTs.1661    return TI.EnforceInteger(NodeToApply.getExtType(ResNo));1662  case SDTCisFP:1663    // Require it to be one of the legal fp VTs.1664    return TI.EnforceFloatingPoint(NodeToApply.getExtType(ResNo));1665  case SDTCisVec:1666    // Require it to be one of the legal vector VTs.1667    return TI.EnforceVector(NodeToApply.getExtType(ResNo));1668  case SDTCisSameAs: {1669    unsigned OResNo = 0;1670    TreePatternNode &OtherNode =1671        getOperandNum(OtherOperandNo, N, NodeInfo, OResNo);1672    return (int)NodeToApply.UpdateNodeType(ResNo, OtherNode.getExtType(OResNo),1673                                           TP) |1674           (int)OtherNode.UpdateNodeType(OResNo, NodeToApply.getExtType(ResNo),1675                                         TP);1676  }1677  case SDTCisVTSmallerThanOp: {1678    // The NodeToApply must be a leaf node that is a VT.  OtherOperandNum must1679    // have an integer type that is smaller than the VT.1680    if (!NodeToApply.isLeaf() || !isa<DefInit>(NodeToApply.getLeafValue()) ||1681        !cast<DefInit>(NodeToApply.getLeafValue())1682             ->getDef()1683             ->isSubClassOf("ValueType")) {1684      TP.error(N.getOperator()->getName() + " expects a VT operand!");1685      return false;1686    }1687    const DefInit *DI = cast<DefInit>(NodeToApply.getLeafValue());1688    const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();1689    auto VVT = getValueTypeByHwMode(DI->getDef(), T.getHwModes());1690    TypeSetByHwMode TypeListTmp(VVT);1691 1692    unsigned OResNo = 0;1693    TreePatternNode &OtherNode =1694        getOperandNum(OtherOperandNo, N, NodeInfo, OResNo);1695 1696    return TI.EnforceSmallerThan(TypeListTmp, OtherNode.getExtType(OResNo),1697                                 /*SmallIsVT*/ true);1698  }1699  case SDTCisOpSmallerThanOp: {1700    unsigned BResNo = 0;1701    TreePatternNode &BigOperand =1702        getOperandNum(OtherOperandNo, N, NodeInfo, BResNo);1703    return TI.EnforceSmallerThan(NodeToApply.getExtType(ResNo),1704                                 BigOperand.getExtType(BResNo));1705  }1706  case SDTCisEltOfVec: {1707    unsigned VResNo = 0;1708    TreePatternNode &VecOperand =1709        getOperandNum(OtherOperandNo, N, NodeInfo, VResNo);1710    // Filter vector types out of VecOperand that don't have the right element1711    // type.1712    return TI.EnforceVectorEltTypeIs(VecOperand.getExtType(VResNo),1713                                     NodeToApply.getExtType(ResNo));1714  }1715  case SDTCisSubVecOfVec: {1716    unsigned VResNo = 0;1717    TreePatternNode &BigVecOperand =1718        getOperandNum(OtherOperandNo, N, NodeInfo, VResNo);1719 1720    // Filter vector types out of BigVecOperand that don't have the1721    // right subvector type.1722    return TI.EnforceVectorSubVectorTypeIs(BigVecOperand.getExtType(VResNo),1723                                           NodeToApply.getExtType(ResNo));1724  }1725  case SDTCVecEltisVT: {1726    return TI.EnforceVectorEltTypeIs(NodeToApply.getExtType(ResNo), VVT);1727  }1728  case SDTCisSameNumEltsAs: {1729    unsigned OResNo = 0;1730    TreePatternNode &OtherNode =1731        getOperandNum(OtherOperandNo, N, NodeInfo, OResNo);1732    return TI.EnforceSameNumElts(OtherNode.getExtType(OResNo),1733                                 NodeToApply.getExtType(ResNo));1734  }1735  case SDTCisSameSizeAs: {1736    unsigned OResNo = 0;1737    TreePatternNode &OtherNode =1738        getOperandNum(OtherOperandNo, N, NodeInfo, OResNo);1739    return TI.EnforceSameSize(OtherNode.getExtType(OResNo),1740                              NodeToApply.getExtType(ResNo));1741  }1742  }1743  llvm_unreachable("Invalid ConstraintType!");1744}1745 1746bool llvm::operator==(const SDTypeConstraint &LHS,1747                      const SDTypeConstraint &RHS) {1748  if (std::tie(LHS.OperandNo, LHS.ConstraintType) !=1749      std::tie(RHS.OperandNo, RHS.ConstraintType))1750    return false;1751  switch (LHS.ConstraintType) {1752  case SDTypeConstraint::SDTCisVT:1753  case SDTypeConstraint::SDTCVecEltisVT:1754    return LHS.VVT == RHS.VVT;1755  case SDTypeConstraint::SDTCisPtrTy:1756  case SDTypeConstraint::SDTCisInt:1757  case SDTypeConstraint::SDTCisFP:1758  case SDTypeConstraint::SDTCisVec:1759    break;1760  case SDTypeConstraint::SDTCisSameAs:1761  case SDTypeConstraint::SDTCisVTSmallerThanOp:1762  case SDTypeConstraint::SDTCisOpSmallerThanOp:1763  case SDTypeConstraint::SDTCisEltOfVec:1764  case SDTypeConstraint::SDTCisSubVecOfVec:1765  case SDTypeConstraint::SDTCisSameNumEltsAs:1766  case SDTypeConstraint::SDTCisSameSizeAs:1767    return LHS.OtherOperandNo == RHS.OtherOperandNo;1768  }1769  return true;1770}1771 1772bool llvm::operator<(const SDTypeConstraint &LHS, const SDTypeConstraint &RHS) {1773  if (std::tie(LHS.OperandNo, LHS.ConstraintType) !=1774      std::tie(RHS.OperandNo, RHS.ConstraintType))1775    return std::tie(LHS.OperandNo, LHS.ConstraintType) <1776           std::tie(RHS.OperandNo, RHS.ConstraintType);1777  switch (LHS.ConstraintType) {1778  case SDTypeConstraint::SDTCisVT:1779  case SDTypeConstraint::SDTCVecEltisVT:1780    return LHS.VVT < RHS.VVT;1781  case SDTypeConstraint::SDTCisPtrTy:1782  case SDTypeConstraint::SDTCisInt:1783  case SDTypeConstraint::SDTCisFP:1784  case SDTypeConstraint::SDTCisVec:1785    break;1786  case SDTypeConstraint::SDTCisSameAs:1787  case SDTypeConstraint::SDTCisVTSmallerThanOp:1788  case SDTypeConstraint::SDTCisOpSmallerThanOp:1789  case SDTypeConstraint::SDTCisEltOfVec:1790  case SDTypeConstraint::SDTCisSubVecOfVec:1791  case SDTypeConstraint::SDTCisSameNumEltsAs:1792  case SDTypeConstraint::SDTCisSameSizeAs:1793    return LHS.OtherOperandNo < RHS.OtherOperandNo;1794  }1795  return false;1796}1797 1798/// RegClassByHwMode acts like ValueTypeByHwMode, taking the type of the1799/// register class from the active mode.1800static TypeSetByHwMode getTypeForRegClassByHwMode(const CodeGenTarget &T,1801                                                  const Record *R) {1802  TypeSetByHwMode TypeSet;1803  RegClassByHwMode Helper(R, T.getHwModes(), T.getRegBank());1804 1805  for (auto [ModeID, RegClass] : Helper) {1806    ArrayRef<ValueTypeByHwMode> RegClassVTs = RegClass->getValueTypes();1807    MachineValueTypeSet &ModeTypeSet = TypeSet.getOrCreate(ModeID);1808    for (const ValueTypeByHwMode &VT : RegClassVTs)1809      ModeTypeSet.insert(VT.getType(ModeID));1810  }1811 1812  return TypeSet;1813}1814 1815// Update the node type to match an instruction operand or result as specified1816// in the ins or outs lists on the instruction definition. Return true if the1817// type was actually changed.1818bool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo,1819                                             const Record *Operand,1820                                             TreePattern &TP) {1821  // The 'unknown' operand indicates that types should be inferred from the1822  // context.1823  if (Operand->isSubClassOf("unknown_class"))1824    return false;1825 1826  // The Operand class specifies a type directly.1827  if (Operand->isSubClassOf("Operand")) {1828    const Record *R = Operand->getValueAsDef("Type");1829    const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();1830    return UpdateNodeType(ResNo, getValueTypeByHwMode(R, T.getHwModes()), TP);1831  }1832 1833  // Both RegisterClass and RegisterOperand operands derive their types from a1834  // register class def.1835  const Record *RC = nullptr;1836  if (Operand->isSubClassOf("RegisterClassLike"))1837    RC = Operand;1838  else if (Operand->isSubClassOf("RegisterOperand"))1839    RC = Operand->getValueAsDef("RegClass");1840 1841  assert(RC && "Unknown operand type");1842  CodeGenTarget &Tgt = TP.getDAGPatterns().getTargetInfo();1843  if (RC->isSubClassOf("RegClassByHwMode"))1844    return UpdateNodeType(ResNo, getTypeForRegClassByHwMode(Tgt, RC), TP);1845 1846  return UpdateNodeType(ResNo, Tgt.getRegisterClass(RC).getValueTypes(), TP);1847}1848 1849bool TreePatternNode::ContainsUnresolvedType(TreePattern &TP) const {1850  for (const TypeSetByHwMode &Type : Types)1851    if (!TP.getInfer().isConcrete(Type, true))1852      return true;1853  for (const TreePatternNode &Child : children())1854    if (Child.ContainsUnresolvedType(TP))1855      return true;1856  return false;1857}1858 1859bool TreePatternNode::hasProperTypeByHwMode() const {1860  for (const TypeSetByHwMode &S : Types)1861    if (!S.isSimple())1862      return true;1863  for (const TreePatternNodePtr &C : Children)1864    if (C->hasProperTypeByHwMode())1865      return true;1866  return false;1867}1868 1869bool TreePatternNode::hasPossibleType() const {1870  for (const TypeSetByHwMode &S : Types)1871    if (!S.isPossible())1872      return false;1873  for (const TreePatternNodePtr &C : Children)1874    if (!C->hasPossibleType())1875      return false;1876  return true;1877}1878 1879bool TreePatternNode::setDefaultMode(unsigned Mode) {1880  for (TypeSetByHwMode &S : Types) {1881    S.makeSimple(Mode);1882    // Check if the selected mode had a type conflict.1883    if (S.get(DefaultMode).empty())1884      return false;1885  }1886  for (const TreePatternNodePtr &C : Children)1887    if (!C->setDefaultMode(Mode))1888      return false;1889  return true;1890}1891 1892//===----------------------------------------------------------------------===//1893// SDNodeInfo implementation1894//1895SDNodeInfo::SDNodeInfo(const Record *R, const CodeGenHwModes &CGH) : Def(R) {1896  EnumName = R->getValueAsString("Opcode");1897  SDClassName = R->getValueAsString("SDClass");1898  const Record *TypeProfile = R->getValueAsDef("TypeProfile");1899  NumResults = TypeProfile->getValueAsInt("NumResults");1900  NumOperands = TypeProfile->getValueAsInt("NumOperands");1901 1902  // Parse the properties.1903  Properties = parseSDPatternOperatorProperties(R);1904  IsStrictFP = R->getValueAsBit("IsStrictFP");1905 1906  std::optional<int64_t> MaybeTSFlags =1907      R->getValueAsBitsInit("TSFlags")->convertInitializerToInt();1908  if (!MaybeTSFlags)1909    PrintFatalError(R->getLoc(), "Invalid TSFlags");1910  assert(isUInt<32>(*MaybeTSFlags) && "TSFlags bit width out of sync");1911  TSFlags = *MaybeTSFlags;1912 1913  // Parse the type constraints.1914  for (const Record *R : TypeProfile->getValueAsListOfDefs("Constraints"))1915    TypeConstraints.emplace_back(R, CGH);1916}1917 1918/// getKnownType - If the type constraints on this node imply a fixed type1919/// (e.g. all stores return void, etc), then return it as an1920/// MVT.  Otherwise, return EEVT::Other.1921MVT SDNodeInfo::getKnownType(unsigned ResNo) const {1922  unsigned NumResults = getNumResults();1923  assert(NumResults <= 1 &&1924         "We only work with nodes with zero or one result so far!");1925  assert(ResNo == 0 && "Only handles single result nodes so far");1926 1927  for (const SDTypeConstraint &Constraint : TypeConstraints) {1928    // Make sure that this applies to the correct node result.1929    if (Constraint.OperandNo >= NumResults) // FIXME: need value #1930      continue;1931 1932    switch (Constraint.ConstraintType) {1933    default:1934      break;1935    case SDTypeConstraint::SDTCisVT:1936      if (Constraint.VVT.isSimple())1937        return Constraint.VVT.getSimple().SimpleTy;1938      break;1939    case SDTypeConstraint::SDTCisPtrTy:1940      return MVT::iPTR;1941    }1942  }1943  return MVT::Other;1944}1945 1946//===----------------------------------------------------------------------===//1947// TreePatternNode implementation1948//1949 1950static unsigned GetNumNodeResults(const Record *Operator,1951                                  CodeGenDAGPatterns &CDP) {1952  if (Operator->getName() == "set")1953    return 0; // All return nothing.1954 1955  if (Operator->isSubClassOf("Intrinsic"))1956    return CDP.getIntrinsic(Operator).IS.RetTys.size();1957 1958  if (Operator->isSubClassOf("SDNode"))1959    return CDP.getSDNodeInfo(Operator).getNumResults();1960 1961  if (Operator->isSubClassOf("PatFrags")) {1962    // If we've already parsed this pattern fragment, get it.  Otherwise, handle1963    // the forward reference case where one pattern fragment references another1964    // before it is processed.1965    if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) {1966      // The number of results of a fragment with alternative records is the1967      // maximum number of results across all alternatives.1968      unsigned NumResults = 0;1969      for (const auto &T : PFRec->getTrees())1970        NumResults = std::max(NumResults, T->getNumTypes());1971      return NumResults;1972    }1973 1974    const ListInit *LI = Operator->getValueAsListInit("Fragments");1975    assert(LI && "Invalid Fragment");1976    unsigned NumResults = 0;1977    for (const Init *I : LI->getElements()) {1978      const Record *Op = nullptr;1979      if (const DagInit *Dag = dyn_cast<DagInit>(I))1980        if (const DefInit *DI = dyn_cast<DefInit>(Dag->getOperator()))1981          Op = DI->getDef();1982      assert(Op && "Invalid Fragment");1983      NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP));1984    }1985    return NumResults;1986  }1987 1988  if (Operator->isSubClassOf("Instruction")) {1989    const CodeGenInstruction &InstInfo =1990        CDP.getTargetInfo().getInstruction(Operator);1991 1992    unsigned NumDefsToAdd = InstInfo.Operands.NumDefs;1993 1994    // Subtract any defaulted outputs.1995    for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) {1996      const Record *OperandNode = InstInfo.Operands[i].Rec;1997 1998      if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&1999          !CDP.getDefaultOperand(OperandNode).DefaultOps.empty())2000        --NumDefsToAdd;2001    }2002 2003    // Add on one implicit def if it has a resolvable type.2004    if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=2005        MVT::Other)2006      ++NumDefsToAdd;2007    return NumDefsToAdd;2008  }2009 2010  if (Operator->isSubClassOf("SDNodeXForm"))2011    return 1; // FIXME: Generalize SDNodeXForm2012 2013  if (Operator->isSubClassOf("ValueType"))2014    return 1; // A type-cast of one result.2015 2016  if (Operator->isSubClassOf("ComplexPattern"))2017    return 1;2018 2019  errs() << *Operator;2020  PrintFatalError("Unhandled node in GetNumNodeResults");2021}2022 2023void TreePatternNode::print(raw_ostream &OS) const {2024  if (isLeaf())2025    OS << *getLeafValue();2026  else2027    OS << '(' << getOperator()->getName();2028 2029  for (unsigned i = 0, e = Types.size(); i != e; ++i) {2030    OS << ':';2031    getExtType(i).writeToStream(OS);2032  }2033 2034  if (!isLeaf()) {2035    if (getNumChildren() != 0) {2036      OS << " ";2037      ListSeparator LS;2038      for (const TreePatternNode &Child : children()) {2039        OS << LS;2040        Child.print(OS);2041      }2042    }2043    OS << ")";2044  }2045 2046  for (const TreePredicateCall &Pred : PredicateCalls) {2047    OS << "<<P:";2048    if (Pred.Scope)2049      OS << Pred.Scope << ":";2050    OS << Pred.Fn.getFnName() << ">>";2051  }2052  if (TransformFn)2053    OS << "<<X:" << TransformFn->getName() << ">>";2054  if (!getName().empty())2055    OS << ":$" << getName();2056 2057  for (const ScopedName &Name : NamesAsPredicateArg)2058    OS << ":$pred:" << Name.getScope() << ":" << Name.getIdentifier();2059}2060void TreePatternNode::dump() const { print(errs()); }2061 2062/// isIsomorphicTo - Return true if this node is recursively2063/// isomorphic to the specified node.  For this comparison, the node's2064/// entire state is considered. The assigned name is ignored, since2065/// nodes with differing names are considered isomorphic. However, if2066/// the assigned name is present in the dependent variable set, then2067/// the assigned name is considered significant and the node is2068/// isomorphic if the names match.2069bool TreePatternNode::isIsomorphicTo(const TreePatternNode &N,2070                                     const MultipleUseVarSet &DepVars) const {2071  if (&N == this)2072    return true;2073  if (N.isLeaf() != isLeaf())2074    return false;2075 2076  // Check operator of non-leaves early since it can be cheaper than checking2077  // types.2078  if (!isLeaf())2079    if (N.getOperator() != getOperator() ||2080        N.getNumChildren() != getNumChildren())2081      return false;2082 2083  if (getExtTypes() != N.getExtTypes() ||2084      getPredicateCalls() != N.getPredicateCalls() ||2085      getTransformFn() != N.getTransformFn())2086    return false;2087 2088  if (isLeaf()) {2089    if (const DefInit *DI = dyn_cast<DefInit>(getLeafValue())) {2090      if (const DefInit *NDI = dyn_cast<DefInit>(N.getLeafValue())) {2091        return ((DI->getDef() == NDI->getDef()) &&2092                (!DepVars.contains(getName()) || getName() == N.getName()));2093      }2094    }2095    return getLeafValue() == N.getLeafValue();2096  }2097 2098  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)2099    if (!getChild(i).isIsomorphicTo(N.getChild(i), DepVars))2100      return false;2101  return true;2102}2103 2104/// clone - Make a copy of this tree and all of its children.2105///2106TreePatternNodePtr TreePatternNode::clone() const {2107  TreePatternNodePtr New;2108  if (isLeaf()) {2109    New = makeIntrusiveRefCnt<TreePatternNode>(getLeafValue(), getNumTypes());2110  } else {2111    std::vector<TreePatternNodePtr> CChildren;2112    CChildren.reserve(Children.size());2113    for (const TreePatternNode &Child : children())2114      CChildren.push_back(Child.clone());2115    New = makeIntrusiveRefCnt<TreePatternNode>(2116        getOperator(), std::move(CChildren), getNumTypes());2117  }2118  New->setName(getName());2119  New->setNamesAsPredicateArg(getNamesAsPredicateArg());2120  New->Types = Types;2121  New->setPredicateCalls(getPredicateCalls());2122  New->setGISelFlagsRecord(getGISelFlagsRecord());2123  New->setTransformFn(getTransformFn());2124  return New;2125}2126 2127/// RemoveAllTypes - Recursively strip all the types of this tree.2128void TreePatternNode::RemoveAllTypes() {2129  // Reset to unknown type.2130  llvm::fill(Types, TypeSetByHwMode());2131  if (isLeaf())2132    return;2133  for (TreePatternNode &Child : children())2134    Child.RemoveAllTypes();2135}2136 2137/// SubstituteFormalArguments - Replace the formal arguments in this tree2138/// with actual values specified by ArgMap.2139void TreePatternNode::SubstituteFormalArguments(2140    std::map<StringRef, TreePatternNodePtr> &ArgMap) {2141  if (isLeaf())2142    return;2143 2144  for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {2145    TreePatternNode &Child = getChild(i);2146    if (Child.isLeaf()) {2147      const Init *Val = Child.getLeafValue();2148      // Note that, when substituting into an output pattern, Val might be an2149      // UnsetInit.2150      if (isa<UnsetInit>(Val) ||2151          (isa<DefInit>(Val) &&2152           cast<DefInit>(Val)->getDef()->getName() == "node")) {2153        // We found a use of a formal argument, replace it with its value.2154        TreePatternNodePtr NewChild = ArgMap[Child.getName()];2155        assert(NewChild && "Couldn't find formal argument!");2156        assert((Child.getPredicateCalls().empty() ||2157                NewChild->getPredicateCalls() == Child.getPredicateCalls()) &&2158               "Non-empty child predicate clobbered!");2159        setChild(i, std::move(NewChild));2160      }2161    } else {2162      getChild(i).SubstituteFormalArguments(ArgMap);2163    }2164  }2165}2166 2167/// InlinePatternFragments - If this pattern refers to any pattern2168/// fragments, return the set of inlined versions (this can be more than2169/// one if a PatFrags record has multiple alternatives).2170void TreePatternNode::InlinePatternFragments(2171    TreePattern &TP, std::vector<TreePatternNodePtr> &OutAlternatives) {2172 2173  if (TP.hasError())2174    return;2175 2176  if (isLeaf()) {2177    OutAlternatives.push_back(this); // nothing to do.2178    return;2179  }2180 2181  const Record *Op = getOperator();2182 2183  if (!Op->isSubClassOf("PatFrags")) {2184    if (getNumChildren() == 0) {2185      OutAlternatives.push_back(this);2186      return;2187    }2188 2189    // Recursively inline children nodes.2190    std::vector<std::vector<TreePatternNodePtr>> ChildAlternatives(2191        getNumChildren());2192    for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {2193      TreePatternNodePtr Child = getChildShared(i);2194      Child->InlinePatternFragments(TP, ChildAlternatives[i]);2195      // If there are no alternatives for any child, there are no2196      // alternatives for this expression as whole.2197      if (ChildAlternatives[i].empty())2198        return;2199 2200      assert((Child->getPredicateCalls().empty() ||2201              llvm::all_of(ChildAlternatives[i],2202                           [&](const TreePatternNodePtr &NewChild) {2203                             return NewChild->getPredicateCalls() ==2204                                    Child->getPredicateCalls();2205                           })) &&2206             "Non-empty child predicate clobbered!");2207    }2208 2209    // The end result is an all-pairs construction of the resultant pattern.2210    std::vector<unsigned> Idxs(ChildAlternatives.size());2211    bool NotDone;2212    do {2213      // Create the variant and add it to the output list.2214      std::vector<TreePatternNodePtr> NewChildren;2215      NewChildren.reserve(ChildAlternatives.size());2216      for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i)2217        NewChildren.push_back(ChildAlternatives[i][Idxs[i]]);2218      TreePatternNodePtr R = makeIntrusiveRefCnt<TreePatternNode>(2219          getOperator(), std::move(NewChildren), getNumTypes());2220 2221      // Copy over properties.2222      R->setName(getName());2223      R->setNamesAsPredicateArg(getNamesAsPredicateArg());2224      R->setPredicateCalls(getPredicateCalls());2225      R->setGISelFlagsRecord(getGISelFlagsRecord());2226      R->setTransformFn(getTransformFn());2227      for (unsigned i = 0, e = getNumTypes(); i != e; ++i)2228        R->setType(i, getExtType(i));2229      for (unsigned i = 0, e = getNumResults(); i != e; ++i)2230        R->setResultIndex(i, getResultIndex(i));2231 2232      // Register alternative.2233      OutAlternatives.push_back(R);2234 2235      // Increment indices to the next permutation by incrementing the2236      // indices from last index backward, e.g., generate the sequence2237      // [0, 0], [0, 1], [1, 0], [1, 1].2238      int IdxsIdx;2239      for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {2240        if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size())2241          Idxs[IdxsIdx] = 0;2242        else2243          break;2244      }2245      NotDone = (IdxsIdx >= 0);2246    } while (NotDone);2247 2248    return;2249  }2250 2251  // Otherwise, we found a reference to a fragment.  First, look up its2252  // TreePattern record.2253  TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);2254 2255  // Verify that we are passing the right number of operands.2256  if (Frag->getNumArgs() != getNumChildren()) {2257    TP.error("'" + Op->getName() + "' fragment requires " +2258             Twine(Frag->getNumArgs()) + " operands!");2259    return;2260  }2261 2262  TreePredicateFn PredFn(Frag);2263  unsigned Scope = 0;2264  if (TreePredicateFn(Frag).usesOperands())2265    Scope = TP.getDAGPatterns().allocateScope();2266 2267  // Compute the map of formal to actual arguments.2268  std::map<StringRef, TreePatternNodePtr> ArgMap;2269  for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {2270    TreePatternNodePtr Child = getChildShared(i);2271    if (Scope != 0) {2272      Child = Child->clone();2273      Child->addNameAsPredicateArg(ScopedName(Scope, Frag->getArgName(i)));2274    }2275    ArgMap[Frag->getArgName(i)] = Child;2276  }2277 2278  // Loop over all fragment alternatives.2279  for (const auto &Alternative : Frag->getTrees()) {2280    TreePatternNodePtr FragTree = Alternative->clone();2281 2282    if (!PredFn.isAlwaysTrue())2283      FragTree->addPredicateCall(PredFn, Scope);2284 2285    // Resolve formal arguments to their actual value.2286    if (Frag->getNumArgs())2287      FragTree->SubstituteFormalArguments(ArgMap);2288 2289    // Transfer types.  Note that the resolved alternative may have fewer2290    // (but not more) results than the PatFrags node.2291    FragTree->setName(getName());2292    for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i)2293      FragTree->UpdateNodeType(i, getExtType(i), TP);2294 2295    if (Op->isSubClassOf("GISelFlags"))2296      FragTree->setGISelFlagsRecord(Op);2297 2298    // Transfer in the old predicates.2299    for (const TreePredicateCall &Pred : getPredicateCalls())2300      FragTree->addPredicateCall(Pred);2301 2302    // The fragment we inlined could have recursive inlining that is needed. See2303    // if there are any pattern fragments in it and inline them as needed.2304    FragTree->InlinePatternFragments(TP, OutAlternatives);2305  }2306}2307 2308/// getImplicitType - Check to see if the specified record has an implicit2309/// type which should be applied to it.  This will infer the type of register2310/// references from the register file information, for example.2311///2312/// When Unnamed is set, return the type of a DAG operand with no name, such as2313/// the F8RC register class argument in:2314///2315///   (COPY_TO_REGCLASS GPR:$src, F8RC)2316///2317/// When Unnamed is false, return the type of a named DAG operand such as the2318/// GPR:$src operand above.2319///2320static TypeSetByHwMode getImplicitType(const Record *R, unsigned ResNo,2321                                       bool NotRegisters, bool Unnamed,2322                                       TreePattern &TP) {2323  CodeGenDAGPatterns &CDP = TP.getDAGPatterns();2324 2325  // Check to see if this is a register operand.2326  if (R->isSubClassOf("RegisterOperand")) {2327    assert(ResNo == 0 && "Regoperand ref only has one result!");2328    if (NotRegisters)2329      return TypeSetByHwMode(); // Unknown.2330    const Record *RegClass = R->getValueAsDef("RegClass");2331    const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();2332 2333    if (RegClass->isSubClassOf("RegClassByHwMode"))2334      return getTypeForRegClassByHwMode(T, RegClass);2335 2336    return TypeSetByHwMode(T.getRegisterClass(RegClass).getValueTypes());2337  }2338 2339  // Check to see if this is a register or a register class.2340  if (R->isSubClassOf("RegisterClass")) {2341    assert(ResNo == 0 && "Regclass ref only has one result!");2342    // An unnamed register class represents itself as an i32 immediate, for2343    // example on a COPY_TO_REGCLASS instruction.2344    if (Unnamed)2345      return TypeSetByHwMode(MVT::i32);2346 2347    // In a named operand, the register class provides the possible set of2348    // types.2349    if (NotRegisters)2350      return TypeSetByHwMode(); // Unknown.2351    const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();2352    return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes());2353  }2354 2355  if (R->isSubClassOf("RegClassByHwMode")) {2356    const CodeGenTarget &T = CDP.getTargetInfo();2357    return getTypeForRegClassByHwMode(T, R);2358  }2359 2360  if (R->isSubClassOf("PatFrags")) {2361    assert(ResNo == 0 && "FIXME: PatFrag with multiple results?");2362    // Pattern fragment types will be resolved when they are inlined.2363    return TypeSetByHwMode(); // Unknown.2364  }2365 2366  if (R->isSubClassOf("Register")) {2367    assert(ResNo == 0 && "Registers only produce one result!");2368    if (NotRegisters)2369      return TypeSetByHwMode(); // Unknown.2370    const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();2371    return TypeSetByHwMode(T.getRegisterVTs(R));2372  }2373 2374  if (R->isSubClassOf("SubRegIndex")) {2375    assert(ResNo == 0 && "SubRegisterIndices only produce one result!");2376    return TypeSetByHwMode(MVT::i32);2377  }2378 2379  if (R->isSubClassOf("ValueType")) {2380    assert(ResNo == 0 && "This node only has one result!");2381    // An unnamed VTSDNode represents itself as an MVT::Other immediate.2382    //2383    //   (sext_inreg GPR:$src, i16)2384    //                         ~~~2385    if (Unnamed)2386      return TypeSetByHwMode(MVT::Other);2387    // With a name, the ValueType simply provides the type of the named2388    // variable.2389    //2390    //   (sext_inreg i32:$src, i16)2391    //               ~~~~~~~~2392    if (NotRegisters)2393      return TypeSetByHwMode(); // Unknown.2394    const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes();2395    return TypeSetByHwMode(getValueTypeByHwMode(R, CGH));2396  }2397 2398  if (R->isSubClassOf("CondCode")) {2399    assert(ResNo == 0 && "This node only has one result!");2400    // Using a CondCodeSDNode.2401    return TypeSetByHwMode(MVT::Other);2402  }2403 2404  if (R->isSubClassOf("ComplexPattern")) {2405    assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?");2406    if (NotRegisters)2407      return TypeSetByHwMode(); // Unknown.2408    const Record *T = CDP.getComplexPattern(R).getValueType();2409    const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes();2410    return TypeSetByHwMode(getValueTypeByHwMode(T, CGH));2411  }2412 2413  if (R->getName() == "node" || R->getName() == "srcvalue" ||2414      R->getName() == "zero_reg" || R->getName() == "immAllOnesV" ||2415      R->getName() == "immAllZerosV" || R->getName() == "undef_tied_input") {2416    // Placeholder.2417    return TypeSetByHwMode(); // Unknown.2418  }2419 2420  if (R->isSubClassOf("Operand")) {2421    const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes();2422    const Record *T = R->getValueAsDef("Type");2423    return TypeSetByHwMode(getValueTypeByHwMode(T, CGH));2424  }2425 2426  TP.error("Unknown node flavor used in pattern: " + R->getName());2427  return TypeSetByHwMode(MVT::Other);2428}2429 2430/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the2431/// CodeGenIntrinsic information for it, otherwise return a null pointer.2432const CodeGenIntrinsic *2433TreePatternNode::getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const {2434  if (getOperator() != CDP.get_intrinsic_void_sdnode() &&2435      getOperator() != CDP.get_intrinsic_w_chain_sdnode() &&2436      getOperator() != CDP.get_intrinsic_wo_chain_sdnode())2437    return nullptr;2438 2439  unsigned IID = cast<IntInit>(getChild(0).getLeafValue())->getValue();2440  return &CDP.getIntrinsicInfo(IID);2441}2442 2443/// getComplexPatternInfo - If this node corresponds to a ComplexPattern,2444/// return the ComplexPattern information, otherwise return null.2445const ComplexPattern *2446TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const {2447  const Record *Rec;2448  if (isLeaf()) {2449    const DefInit *DI = dyn_cast<DefInit>(getLeafValue());2450    if (!DI)2451      return nullptr;2452    Rec = DI->getDef();2453  } else {2454    Rec = getOperator();2455  }2456 2457  if (!Rec->isSubClassOf("ComplexPattern"))2458    return nullptr;2459  return &CGP.getComplexPattern(Rec);2460}2461 2462unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const {2463  // A ComplexPattern specifically declares how many results it fills in.2464  if (const ComplexPattern *CP = getComplexPatternInfo(CGP))2465    return CP->getNumOperands();2466 2467  // If MIOperandInfo is specified, that gives the count.2468  if (isLeaf()) {2469    const DefInit *DI = dyn_cast<DefInit>(getLeafValue());2470    if (DI && DI->getDef()->isSubClassOf("Operand")) {2471      const DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo");2472      if (MIOps->getNumArgs())2473        return MIOps->getNumArgs();2474    }2475  }2476 2477  // Otherwise there is just one result.2478  return 1;2479}2480 2481/// NodeHasProperty - Return true if this node has the specified property.2482bool TreePatternNode::NodeHasProperty(SDNP Property,2483                                      const CodeGenDAGPatterns &CGP) const {2484  if (isLeaf()) {2485    if (const ComplexPattern *CP = getComplexPatternInfo(CGP))2486      return CP->hasProperty(Property);2487 2488    return false;2489  }2490 2491  if (Property != SDNPHasChain) {2492    // The chain proprety is already present on the different intrinsic node2493    // types (intrinsic_w_chain, intrinsic_void), and is not explicitly listed2494    // on the intrinsic. Anything else is specific to the individual intrinsic.2495    if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CGP))2496      return Int->hasProperty(Property);2497  }2498 2499  if (!getOperator()->isSubClassOf("SDPatternOperator"))2500    return false;2501 2502  return CGP.getSDNodeInfo(getOperator()).hasProperty(Property);2503}2504 2505/// TreeHasProperty - Return true if any node in this tree has the specified2506/// property.2507bool TreePatternNode::TreeHasProperty(SDNP Property,2508                                      const CodeGenDAGPatterns &CGP) const {2509  if (NodeHasProperty(Property, CGP))2510    return true;2511  for (const TreePatternNode &Child : children())2512    if (Child.TreeHasProperty(Property, CGP))2513      return true;2514  return false;2515}2516 2517/// isCommutativeIntrinsic - Return true if the node corresponds to a2518/// commutative intrinsic.2519bool TreePatternNode::isCommutativeIntrinsic(2520    const CodeGenDAGPatterns &CDP) const {2521  if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP))2522    return Int->isCommutative;2523  return false;2524}2525 2526static bool isOperandClass(const TreePatternNode &N, StringRef Class) {2527  if (!N.isLeaf())2528    return N.getOperator()->isSubClassOf(Class);2529 2530  const DefInit *DI = dyn_cast<DefInit>(N.getLeafValue());2531  if (DI && DI->getDef()->isSubClassOf(Class))2532    return true;2533 2534  return false;2535}2536 2537static void emitTooManyOperandsError(TreePattern &TP, StringRef InstName,2538                                     unsigned Expected, unsigned Actual) {2539  TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) +2540           " operands but expected only " + Twine(Expected) + "!");2541}2542 2543static void emitTooFewOperandsError(TreePattern &TP, StringRef InstName,2544                                    unsigned Actual) {2545  TP.error("Instruction '" + InstName + "' expects more than the provided " +2546           Twine(Actual) + " operands!");2547}2548 2549/// ApplyTypeConstraints - Apply all of the type constraints relevant to2550/// this node and its children in the tree.  This returns true if it makes a2551/// change, false otherwise.  If a type contradiction is found, flag an error.2552bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {2553  if (TP.hasError())2554    return false;2555 2556  CodeGenDAGPatterns &CDP = TP.getDAGPatterns();2557  if (isLeaf()) {2558    if (const DefInit *DI = dyn_cast<DefInit>(getLeafValue())) {2559      // If it's a regclass or something else known, include the type.2560      bool MadeChange = false;2561      for (unsigned i = 0, e = Types.size(); i != e; ++i)2562        MadeChange |= UpdateNodeType(2563            i, getImplicitType(DI->getDef(), i, NotRegisters, !hasName(), TP),2564            TP);2565      return MadeChange;2566    }2567 2568    if (const IntInit *II = dyn_cast<IntInit>(getLeafValue())) {2569      assert(Types.size() == 1 && "Invalid IntInit");2570 2571      // Int inits are always integers. :)2572      bool MadeChange = TP.getInfer().EnforceInteger(Types[0]);2573 2574      if (!TP.getInfer().isConcrete(Types[0], false))2575        return MadeChange;2576 2577      ValueTypeByHwMode VVT = TP.getInfer().getConcrete(Types[0], false);2578      for (auto &P : VVT) {2579        MVT VT = P.second;2580        // Can only check for types of a known size2581        if (VT == MVT::iPTR)2582          continue;2583 2584        // Check that the value doesn't use more bits than we have. It must2585        // either be a sign- or zero-extended equivalent of the original.2586        unsigned Width = VT.getFixedSizeInBits();2587        int64_t Val = II->getValue();2588        if (!isIntN(Width, Val) && !isUIntN(Width, Val)) {2589          TP.error("Integer value '" + Twine(Val) +2590                   "' is out of range for type '" + getEnumName(VT) + "'!");2591          break;2592        }2593      }2594      return MadeChange;2595    }2596 2597    return false;2598  }2599 2600  if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {2601    bool MadeChange = false;2602 2603    // Apply the result type to the node.2604    unsigned NumRetVTs = Int->IS.RetTys.size();2605    unsigned NumParamVTs = Int->IS.ParamTys.size();2606 2607    for (unsigned i = 0, e = NumRetVTs; i != e; ++i)2608      MadeChange |= UpdateNodeType(2609          i, getValueType(Int->IS.RetTys[i]->getValueAsDef("VT")), TP);2610 2611    if (getNumChildren() != NumParamVTs + 1) {2612      TP.error("Intrinsic '" + Int->Name + "' expects " + Twine(NumParamVTs) +2613               " operands, not " + Twine(getNumChildren() - 1) + " operands!");2614      return false;2615    }2616 2617    // Apply type info to the intrinsic ID.2618    MadeChange |= getChild(0).UpdateNodeType(0, MVT::iPTR, TP);2619 2620    for (unsigned i = 0, e = getNumChildren() - 1; i != e; ++i) {2621      MadeChange |= getChild(i + 1).ApplyTypeConstraints(TP, NotRegisters);2622 2623      MVT OpVT = getValueType(Int->IS.ParamTys[i]->getValueAsDef("VT"));2624      assert(getChild(i + 1).getNumTypes() == 1 && "Unhandled case");2625      MadeChange |= getChild(i + 1).UpdateNodeType(0, OpVT, TP);2626    }2627    return MadeChange;2628  }2629 2630  if (getOperator()->isSubClassOf("SDNode")) {2631    const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator());2632 2633    // Check that the number of operands is sane.  Negative operands -> varargs.2634    if (NI.getNumOperands() >= 0 &&2635        getNumChildren() != (unsigned)NI.getNumOperands()) {2636      TP.error(getOperator()->getName() + " node requires exactly " +2637               Twine(NI.getNumOperands()) + " operands!");2638      return false;2639    }2640 2641    bool MadeChange = false;2642    for (TreePatternNode &Child : children())2643      MadeChange |= Child.ApplyTypeConstraints(TP, NotRegisters);2644    MadeChange |= NI.ApplyTypeConstraints(*this, TP);2645    return MadeChange;2646  }2647 2648  if (getOperator()->isSubClassOf("Instruction")) {2649    const DAGInstruction &Inst = CDP.getInstruction(getOperator());2650    const CodeGenInstruction &InstInfo =2651        CDP.getTargetInfo().getInstruction(getOperator());2652 2653    bool MadeChange = false;2654 2655    // Apply the result types to the node, these come from the things in the2656    // (outs) list of the instruction.2657    unsigned NumResultsToAdd =2658        std::min(InstInfo.Operands.NumDefs, Inst.getNumResults());2659    for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo)2660      MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP);2661 2662    // If the instruction has implicit defs, we apply the first one as a result.2663    // FIXME: This sucks, it should apply all implicit defs.2664    if (!InstInfo.ImplicitDefs.empty()) {2665      unsigned ResNo = NumResultsToAdd;2666 2667      // FIXME: Generalize to multiple possible types and multiple possible2668      // ImplicitDefs.2669      MVT VT = InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo());2670 2671      if (VT != MVT::Other)2672        MadeChange |= UpdateNodeType(ResNo, VT, TP);2673    }2674 2675    // If this is an INSERT_SUBREG, constrain the source and destination VTs to2676    // be the same.2677    if (getOperator()->getName() == "INSERT_SUBREG") {2678      assert(getChild(0).getNumTypes() == 1 && "FIXME: Unhandled");2679      MadeChange |= UpdateNodeType(0, getChild(0).getExtType(0), TP);2680      MadeChange |= getChild(0).UpdateNodeType(0, getExtType(0), TP);2681    } else if (getOperator()->getName() == "REG_SEQUENCE") {2682      // We need to do extra, custom typechecking for REG_SEQUENCE since it is2683      // variadic.2684 2685      unsigned NChild = getNumChildren();2686      if (NChild < 3) {2687        TP.error("REG_SEQUENCE requires at least 3 operands!");2688        return false;2689      }2690 2691      if (NChild % 2 == 0) {2692        TP.error("REG_SEQUENCE requires an odd number of operands!");2693        return false;2694      }2695 2696      if (!isOperandClass(getChild(0), "RegisterClass")) {2697        TP.error("REG_SEQUENCE requires a RegisterClass for first operand!");2698        return false;2699      }2700 2701      for (unsigned I = 1; I < NChild; I += 2) {2702        TreePatternNode &SubIdxChild = getChild(I + 1);2703        if (!isOperandClass(SubIdxChild, "SubRegIndex")) {2704          TP.error("REG_SEQUENCE requires a SubRegIndex for operand " +2705                   Twine(I + 1) + "!");2706          return false;2707        }2708      }2709    }2710 2711    unsigned NumResults = Inst.getNumResults();2712    unsigned NumFixedOperands = InstInfo.Operands.size();2713 2714    // If one or more operands with a default value appear at the end of the2715    // formal operand list for an instruction, we allow them to be overridden2716    // by optional operands provided in the pattern.2717    //2718    // But if an operand B without a default appears at any point after an2719    // operand A with a default, then we don't allow A to be overridden,2720    // because there would be no way to specify whether the next operand in2721    // the pattern was intended to override A or skip it.2722    unsigned NonOverridableOperands = NumFixedOperands;2723    while (NonOverridableOperands > NumResults &&2724           CDP.operandHasDefault(2725               InstInfo.Operands[NonOverridableOperands - 1].Rec))2726      --NonOverridableOperands;2727 2728    unsigned ChildNo = 0;2729    assert(NumResults <= NumFixedOperands);2730    for (unsigned i = NumResults, e = NumFixedOperands; i != e; ++i) {2731      const Record *OperandNode = InstInfo.Operands[i].Rec;2732 2733      // If the operand has a default value, do we use it? We must use the2734      // default if we've run out of children of the pattern DAG to consume,2735      // or if the operand is followed by a non-defaulted one.2736      if (CDP.operandHasDefault(OperandNode) &&2737          (i < NonOverridableOperands || ChildNo >= getNumChildren()))2738        continue;2739 2740      // If we have run out of child nodes and there _isn't_ a default2741      // value we can use for the next operand, give an error.2742      if (ChildNo >= getNumChildren()) {2743        emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren());2744        return false;2745      }2746 2747      TreePatternNode *Child = &getChild(ChildNo++);2748      unsigned ChildResNo = 0; // Instructions always use res #0 of their op.2749 2750      // If the operand has sub-operands, they may be provided by distinct2751      // child patterns, so attempt to match each sub-operand separately.2752      if (OperandNode->isSubClassOf("Operand")) {2753        const DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo");2754        if (unsigned NumArgs = MIOpInfo->getNumArgs()) {2755          // But don't do that if the whole operand is being provided by2756          // a single ComplexPattern-related Operand.2757 2758          if (Child->getNumMIResults(CDP) < NumArgs) {2759            // Match first sub-operand against the child we already have.2760            const Record *SubRec = cast<DefInit>(MIOpInfo->getArg(0))->getDef();2761            MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP);2762 2763            // And the remaining sub-operands against subsequent children.2764            for (unsigned Arg = 1; Arg < NumArgs; ++Arg) {2765              if (ChildNo >= getNumChildren()) {2766                emitTooFewOperandsError(TP, getOperator()->getName(),2767                                        getNumChildren());2768                return false;2769              }2770              Child = &getChild(ChildNo++);2771 2772              SubRec = cast<DefInit>(MIOpInfo->getArg(Arg))->getDef();2773              MadeChange |=2774                  Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP);2775            }2776            continue;2777          }2778        }2779      }2780 2781      // If we didn't match by pieces above, attempt to match the whole2782      // operand now.2783      MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP);2784    }2785 2786    if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) {2787      emitTooManyOperandsError(TP, getOperator()->getName(), ChildNo,2788                               getNumChildren());2789      return false;2790    }2791 2792    for (TreePatternNode &Child : children())2793      MadeChange |= Child.ApplyTypeConstraints(TP, NotRegisters);2794    return MadeChange;2795  }2796 2797  if (getOperator()->isSubClassOf("ComplexPattern")) {2798    bool MadeChange = false;2799 2800    if (!NotRegisters) {2801      assert(Types.size() == 1 && "ComplexPatterns only produce one result!");2802      const Record *T = CDP.getComplexPattern(getOperator()).getValueType();2803      const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes();2804      const ValueTypeByHwMode VVT = getValueTypeByHwMode(T, CGH);2805      // TODO: AArch64 and AMDGPU use ComplexPattern<untyped, ...> and then2806      // exclusively use those as non-leaf nodes with explicit type casts, so2807      // for backwards compatibility we do no inference in that case. This is2808      // not supported when the ComplexPattern is used as a leaf value,2809      // however; this inconsistency should be resolved, either by adding this2810      // case there or by altering the backends to not do this (e.g. using Any2811      // instead may work).2812      if (!VVT.isSimple() || VVT.getSimple() != MVT::Untyped)2813        MadeChange |= UpdateNodeType(0, VVT, TP);2814    }2815 2816    for (TreePatternNode &Child : children())2817      MadeChange |= Child.ApplyTypeConstraints(TP, NotRegisters);2818 2819    return MadeChange;2820  }2821 2822  if (!getOperator()->isSubClassOf("SDNodeXForm")) {2823    TP.error("unknown node type '" + getOperator()->getName() +2824             "' in input pattern");2825    return false;2826  }2827 2828  // Node transforms always take one operand.2829  if (getNumChildren() != 1) {2830    TP.error("Node transform '" + getOperator()->getName() +2831             "' requires one operand!");2832    return false;2833  }2834 2835  bool MadeChange = getChild(0).ApplyTypeConstraints(TP, NotRegisters);2836  return MadeChange;2837}2838 2839/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the2840/// RHS of a commutative operation, not the on LHS.2841static bool OnlyOnRHSOfCommutative(const TreePatternNode &N) {2842  if (!N.isLeaf() && N.getOperator()->getName() == "imm")2843    return true;2844  if (N.isLeaf() && isa<IntInit>(N.getLeafValue()))2845    return true;2846  if (isImmAllOnesAllZerosMatch(N))2847    return true;2848  return false;2849}2850 2851/// canPatternMatch - If it is impossible for this pattern to match on this2852/// target, fill in Reason and return false.  Otherwise, return true.  This is2853/// used as a sanity check for .td files (to prevent people from writing stuff2854/// that can never possibly work), and to prevent the pattern permuter from2855/// generating stuff that is useless.2856bool TreePatternNode::canPatternMatch(std::string &Reason,2857                                      const CodeGenDAGPatterns &CDP) const {2858  if (isLeaf())2859    return true;2860 2861  for (const TreePatternNode &Child : children())2862    if (!Child.canPatternMatch(Reason, CDP))2863      return false;2864 2865  // If this is an intrinsic, handle cases that would make it not match.  For2866  // example, if an operand is required to be an immediate.2867  if (getOperator()->isSubClassOf("Intrinsic")) {2868    // TODO:2869    return true;2870  }2871 2872  if (getOperator()->isSubClassOf("ComplexPattern"))2873    return true;2874 2875  // If this node is a commutative operator, check that the LHS isn't an2876  // immediate.2877  const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator());2878  bool isCommIntrinsic = isCommutativeIntrinsic(CDP);2879  if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {2880    // Scan all of the operands of the node and make sure that only the last one2881    // is a constant node, unless the RHS also is.2882    if (!OnlyOnRHSOfCommutative(getChild(getNumChildren() - 1))) {2883      unsigned Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id.2884      for (unsigned i = Skip, e = getNumChildren() - 1; i != e; ++i)2885        if (OnlyOnRHSOfCommutative(getChild(i))) {2886          Reason =2887              "Immediate value must be on the RHS of commutative operators!";2888          return false;2889        }2890    }2891  }2892 2893  return true;2894}2895 2896//===----------------------------------------------------------------------===//2897// TreePattern implementation2898//2899 2900TreePattern::TreePattern(const Record *TheRec, const ListInit *RawPat,2901                         bool isInput, CodeGenDAGPatterns &cdp)2902    : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),2903      Infer(*this) {2904  for (const Init *I : RawPat->getElements())2905    Trees.push_back(ParseTreePattern(I, ""));2906}2907 2908TreePattern::TreePattern(const Record *TheRec, const DagInit *Pat, bool isInput,2909                         CodeGenDAGPatterns &cdp)2910    : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),2911      Infer(*this) {2912  Trees.push_back(ParseTreePattern(Pat, ""));2913}2914 2915TreePattern::TreePattern(const Record *TheRec, ArrayRef<const Init *> Args,2916                         ArrayRef<const StringInit *> ArgNames, bool isInput,2917                         CodeGenDAGPatterns &cdp)2918    : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),2919      Infer(*this) {2920  Trees.push_back(ParseRootlessTreePattern(Args, ArgNames));2921}2922 2923TreePattern::TreePattern(const Record *TheRec, TreePatternNodePtr Pat,2924                         bool isInput, CodeGenDAGPatterns &cdp)2925    : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),2926      Infer(*this) {2927  Trees.push_back(Pat);2928}2929 2930void TreePattern::error(const Twine &Msg) {2931  if (HasError)2932    return;2933  dump();2934  PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg);2935  HasError = true;2936}2937 2938void TreePattern::ComputeNamedNodes() {2939  for (TreePatternNodePtr &Tree : Trees)2940    ComputeNamedNodes(*Tree);2941}2942 2943void TreePattern::ComputeNamedNodes(TreePatternNode &N) {2944  if (!N.getName().empty())2945    NamedNodes[N.getName()].push_back(&N);2946 2947  for (TreePatternNode &Child : N.children())2948    ComputeNamedNodes(Child);2949}2950 2951TreePatternNodePtr2952TreePattern::ParseRootlessTreePattern(ArrayRef<const Init *> Args,2953                                      ArrayRef<const StringInit *> ArgNames) {2954  std::vector<TreePatternNodePtr> Children;2955 2956  for (auto [Arg, ArgName] : llvm::zip_equal(Args, ArgNames)) {2957    StringRef NameStr = ArgName ? ArgName->getValue() : "";2958    Children.push_back(ParseTreePattern(Arg, NameStr));2959  }2960 2961  return makeIntrusiveRefCnt<TreePatternNode>(nullptr, std::move(Children), 1);2962}2963 2964TreePatternNodePtr TreePattern::ParseTreePattern(const Init *TheInit,2965                                                 StringRef OpName) {2966  RecordKeeper &RK = TheInit->getRecordKeeper();2967  // Here, we are creating new records (BitsInit->InitInit), so const_cast2968  // TheInit back to non-const pointer.2969  if (const DefInit *DI = dyn_cast<DefInit>(TheInit)) {2970    const Record *R = DI->getDef();2971 2972    // Direct reference to a leaf DagNode or PatFrag?  Turn it into a2973    // TreePatternNode of its own.  For example:2974    ///   (foo GPR, imm) -> (foo GPR, (imm))2975    if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrags"))2976      return ParseTreePattern(DagInit::get(DI, {}), OpName);2977 2978    // Input argument?2979    TreePatternNodePtr Res = makeIntrusiveRefCnt<TreePatternNode>(DI, 1);2980    if (R->getName() == "node" && !OpName.empty()) {2981      if (OpName.empty())2982        error("'node' argument requires a name to match with operand list");2983      Args.push_back(OpName.str());2984    }2985 2986    Res->setName(OpName);2987    return Res;2988  }2989 2990  // ?:$name or just $name.2991  if (isa<UnsetInit>(TheInit)) {2992    if (OpName.empty())2993      error("'?' argument requires a name to match with operand list");2994    TreePatternNodePtr Res = makeIntrusiveRefCnt<TreePatternNode>(TheInit, 1);2995    Args.push_back(OpName.str());2996    Res->setName(OpName);2997    return Res;2998  }2999 3000  if (isa<IntInit>(TheInit) || isa<BitInit>(TheInit)) {3001    if (!OpName.empty())3002      error("Constant int or bit argument should not have a name!");3003    if (isa<BitInit>(TheInit))3004      TheInit = TheInit->convertInitializerTo(IntRecTy::get(RK));3005    return makeIntrusiveRefCnt<TreePatternNode>(TheInit, 1);3006  }3007 3008  if (const BitsInit *BI = dyn_cast<BitsInit>(TheInit)) {3009    // Turn this into an IntInit.3010    const Init *II = BI->convertInitializerTo(IntRecTy::get(RK));3011    if (!II || !isa<IntInit>(II))3012      error("Bits value must be constants!");3013    return II ? ParseTreePattern(II, OpName) : nullptr;3014  }3015 3016  const DagInit *Dag = dyn_cast<DagInit>(TheInit);3017  if (!Dag) {3018    TheInit->print(errs());3019    error("Pattern has unexpected init kind!");3020    return nullptr;3021  }3022 3023  auto ParseCastOperand = [this](const DagInit *Dag, StringRef OpName) {3024    if (Dag->getNumArgs() != 1)3025      error("Type cast only takes one operand!");3026 3027    if (!OpName.empty())3028      error("Type cast should not have a name!");3029 3030    return ParseTreePattern(Dag->getArg(0), Dag->getArgNameStr(0));3031  };3032 3033  if (const ListInit *LI = dyn_cast<ListInit>(Dag->getOperator())) {3034    // If the operator is a list (of value types), then this must be "type cast"3035    // of a leaf node with multiple results.3036    TreePatternNodePtr New = ParseCastOperand(Dag, OpName);3037 3038    size_t NumTypes = New->getNumTypes();3039    if (LI->empty() || LI->size() != NumTypes)3040      error("Invalid number of type casts!");3041 3042    // Apply the type casts.3043    const CodeGenHwModes &CGH = getDAGPatterns().getTargetInfo().getHwModes();3044    for (unsigned i = 0; i < std::min(NumTypes, LI->size()); ++i)3045      New->UpdateNodeType(3046          i, getValueTypeByHwMode(LI->getElementAsRecord(i), CGH), *this);3047 3048    return New;3049  }3050 3051  const DefInit *OpDef = dyn_cast<DefInit>(Dag->getOperator());3052  if (!OpDef) {3053    error("Pattern has unexpected operator type!");3054    return nullptr;3055  }3056  const Record *Operator = OpDef->getDef();3057 3058  if (Operator->isSubClassOf("ValueType")) {3059    // If the operator is a ValueType, then this must be "type cast" of a leaf3060    // node.3061    TreePatternNodePtr New = ParseCastOperand(Dag, OpName);3062 3063    if (New->getNumTypes() != 1)3064      error("ValueType cast can only have one type!");3065 3066    // Apply the type cast.3067    const CodeGenHwModes &CGH = getDAGPatterns().getTargetInfo().getHwModes();3068    New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this);3069 3070    return New;3071  }3072 3073  // Verify that this is something that makes sense for an operator.3074  if (!Operator->isSubClassOf("PatFrags") &&3075      !Operator->isSubClassOf("SDNode") &&3076      !Operator->isSubClassOf("Instruction") &&3077      !Operator->isSubClassOf("SDNodeXForm") &&3078      !Operator->isSubClassOf("Intrinsic") &&3079      !Operator->isSubClassOf("ComplexPattern") && Operator->getName() != "set")3080    error("Unrecognized node '" + Operator->getName() + "'!");3081 3082  //  Check to see if this is something that is illegal in an input pattern.3083  if (isInputPattern) {3084    if (Operator->isSubClassOf("Instruction") ||3085        Operator->isSubClassOf("SDNodeXForm"))3086      error("Cannot use '" + Operator->getName() + "' in an input pattern!");3087  } else {3088    if (Operator->isSubClassOf("Intrinsic"))3089      error("Cannot use '" + Operator->getName() + "' in an output pattern!");3090 3091    if (Operator->isSubClassOf("SDNode") && Operator->getName() != "imm" &&3092        Operator->getName() != "timm" && Operator->getName() != "fpimm" &&3093        Operator->getName() != "tglobaltlsaddr" &&3094        Operator->getName() != "tconstpool" &&3095        Operator->getName() != "tjumptable" &&3096        Operator->getName() != "tframeindex" &&3097        Operator->getName() != "texternalsym" &&3098        Operator->getName() != "tblockaddress" &&3099        Operator->getName() != "tglobaladdr" && Operator->getName() != "bb" &&3100        Operator->getName() != "vt" && Operator->getName() != "mcsym")3101      error("Cannot use '" + Operator->getName() + "' in an output pattern!");3102  }3103 3104  std::vector<TreePatternNodePtr> Children;3105 3106  // Parse all the operands.3107  for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i)3108    Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgNameStr(i)));3109 3110  // Get the actual number of results before Operator is converted to an3111  // intrinsic node (which is hard-coded to have either zero or one result).3112  unsigned NumResults = GetNumNodeResults(Operator, CDP);3113 3114  // If the operator is an intrinsic, then this is just syntactic sugar for3115  // (intrinsic_* <number>, ..children..).  Pick the right intrinsic node, and3116  // convert the intrinsic name to a number.3117  if (Operator->isSubClassOf("Intrinsic")) {3118    const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator);3119    unsigned IID = getDAGPatterns().getIntrinsicID(Operator) + 1;3120 3121    // If this intrinsic returns void, it must have side-effects and thus a3122    // chain.3123    if (Int.IS.RetTys.empty())3124      Operator = getDAGPatterns().get_intrinsic_void_sdnode();3125    else if (!Int.ME.doesNotAccessMemory() || Int.hasSideEffects)3126      // Has side-effects, requires chain.3127      Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode();3128    else // Otherwise, no chain.3129      Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode();3130 3131    Children.insert(Children.begin(), makeIntrusiveRefCnt<TreePatternNode>(3132                                          IntInit::get(RK, IID), 1));3133  }3134 3135  if (Operator->isSubClassOf("ComplexPattern")) {3136    for (unsigned i = 0; i < Children.size(); ++i) {3137      TreePatternNodePtr Child = Children[i];3138 3139      if (Child->getName().empty())3140        error("All arguments to a ComplexPattern must be named");3141 3142      // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)"3143      // and "(MY_PAT $b, $a)" should not be allowed in the same pattern;3144      // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)".3145      auto OperandId = std::pair(Operator, i);3146      auto [PrevOp, Inserted] =3147          ComplexPatternOperands.try_emplace(Child->getName(), OperandId);3148      if (!Inserted && PrevOp->getValue() != OperandId) {3149        error("All ComplexPattern operands must appear consistently: "3150              "in the same order in just one ComplexPattern instance.");3151      }3152    }3153  }3154 3155  TreePatternNodePtr Result = makeIntrusiveRefCnt<TreePatternNode>(3156      Operator, std::move(Children), NumResults);3157  Result->setName(OpName);3158 3159  if (Dag->getName()) {3160    assert(Result->getName().empty());3161    Result->setName(Dag->getNameStr());3162  }3163  return Result;3164}3165 3166/// SimplifyTree - See if we can simplify this tree to eliminate something that3167/// will never match in favor of something obvious that will.  This is here3168/// strictly as a convenience to target authors because it allows them to write3169/// more type generic things and have useless type casts fold away.3170///3171/// This returns true if any change is made.3172static bool SimplifyTree(TreePatternNodePtr &N) {3173  if (N->isLeaf())3174    return false;3175 3176  // If we have a bitconvert with a resolved type and if the source and3177  // destination types are the same, then the bitconvert is useless, remove it.3178  //3179  // We make an exception if the types are completely empty. This can come up3180  // when the pattern being simplified is in the Fragments list of a PatFrags,3181  // so that the operand is just an untyped "node". In that situation we leave3182  // bitconverts unsimplified, and simplify them later once the fragment is3183  // expanded into its true context.3184  if (N->getOperator()->getName() == "bitconvert" &&3185      N->getExtType(0).isValueTypeByHwMode(false) &&3186      !N->getExtType(0).empty() &&3187      N->getExtType(0) == N->getChild(0).getExtType(0) &&3188      N->getName().empty()) {3189    if (!N->getPredicateCalls().empty()) {3190      std::string Str;3191      raw_string_ostream OS(Str);3192      OS << *N3193         << "\n trivial bitconvert node should not have predicate calls\n";3194      PrintFatalError(Str);3195      return false;3196    }3197    N = N->getChildShared(0);3198    SimplifyTree(N);3199    return true;3200  }3201 3202  // Walk all children.3203  bool MadeChange = false;3204  for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)3205    MadeChange |= SimplifyTree(N->getChildSharedPtr(i));3206 3207  return MadeChange;3208}3209 3210/// InferAllTypes - Infer/propagate as many types throughout the expression3211/// patterns as possible.  Return true if all types are inferred, false3212/// otherwise.  Flags an error if a type contradiction is found.3213bool TreePattern::InferAllTypes(3214    const StringMap<SmallVector<TreePatternNode *, 1>> *InNamedTypes) {3215  if (NamedNodes.empty())3216    ComputeNamedNodes();3217 3218  bool MadeChange = true;3219  while (MadeChange) {3220    MadeChange = false;3221    for (TreePatternNodePtr &Tree : Trees) {3222      MadeChange |= Tree->ApplyTypeConstraints(*this, false);3223      MadeChange |= SimplifyTree(Tree);3224    }3225 3226    // If there are constraints on our named nodes, apply them.3227    for (auto &Entry : NamedNodes) {3228      SmallVectorImpl<TreePatternNode *> &Nodes = Entry.second;3229 3230      // If we have input named node types, propagate their types to the named3231      // values here.3232      if (InNamedTypes) {3233        auto InIter = InNamedTypes->find(Entry.getKey());3234        if (InIter == InNamedTypes->end()) {3235          error("Node '" + Entry.getKey().str() +3236                "' in output pattern but not input pattern");3237          return true;3238        }3239 3240        ArrayRef<TreePatternNode *> InNodes = InIter->second;3241 3242        // The input types should be fully resolved by now.3243        for (TreePatternNode *Node : Nodes) {3244          // If this node is a register class, and it is the root of the pattern3245          // then we're mapping something onto an input register.  We allow3246          // changing the type of the input register in this case.  This allows3247          // us to match things like:3248          //  def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>;3249          if (Node == Trees[0].get() && Node->isLeaf()) {3250            const DefInit *DI = dyn_cast<DefInit>(Node->getLeafValue());3251            if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||3252                       DI->getDef()->isSubClassOf("RegisterOperand")))3253              continue;3254          }3255 3256          assert(Node->getNumTypes() == 1 && InNodes[0]->getNumTypes() == 1 &&3257                 "FIXME: cannot name multiple result nodes yet");3258          MadeChange |=3259              Node->UpdateNodeType(0, InNodes[0]->getExtType(0), *this);3260        }3261      }3262 3263      // If there are multiple nodes with the same name, they must all have the3264      // same type.3265      if (Entry.second.size() > 1) {3266        for (unsigned i = 0, e = Nodes.size() - 1; i != e; ++i) {3267          TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i + 1];3268          assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 &&3269                 "FIXME: cannot name multiple result nodes yet");3270 3271          MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this);3272          MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this);3273        }3274      }3275    }3276  }3277 3278  bool HasUnresolvedTypes = false;3279  for (const TreePatternNodePtr &Tree : Trees)3280    HasUnresolvedTypes |= Tree->ContainsUnresolvedType(*this);3281  return !HasUnresolvedTypes;3282}3283 3284void TreePattern::print(raw_ostream &OS) const {3285  OS << getRecord()->getName();3286  if (!Args.empty())3287    OS << '(' << llvm::interleaved(Args) << ')';3288  OS << ": ";3289 3290  if (Trees.size() > 1)3291    OS << "[\n";3292  for (const TreePatternNodePtr &Tree : Trees) {3293    OS << "\t";3294    Tree->print(OS);3295    OS << "\n";3296  }3297 3298  if (Trees.size() > 1)3299    OS << "]\n";3300}3301 3302void TreePattern::dump() const { print(errs()); }3303 3304//===----------------------------------------------------------------------===//3305// CodeGenDAGPatterns implementation3306//3307 3308CodeGenDAGPatterns::CodeGenDAGPatterns(const RecordKeeper &R,3309                                       PatternRewriterFn PatternRewriter)3310    : Records(R), Target(R), Intrinsics(R),3311      LegalVTS(Target.getLegalValueTypes()),3312      LegalPtrVTS(ComputeLegalPtrTypes()),3313      PatternRewriter(std::move(PatternRewriter)) {3314  ParseNodeInfo();3315  ParseNodeTransforms();3316  ParseComplexPatterns();3317  ParsePatternFragments();3318  ParseDefaultOperands();3319  ParseInstructions();3320  ParsePatternFragments(/*OutFrags*/ true);3321  ParsePatterns();3322 3323  // Generate variants.  For example, commutative patterns can match3324  // multiple ways.  Add them to PatternsToMatch as well.3325  GenerateVariants();3326 3327  // Break patterns with parameterized types into a series of patterns,3328  // where each one has a fixed type and is predicated on the conditions3329  // of the associated HW mode.3330  ExpandHwModeBasedTypes();3331 3332  // Infer instruction flags.  For example, we can detect loads,3333  // stores, and side effects in many cases by examining an3334  // instruction's pattern.3335  InferInstructionFlags();3336 3337  // Verify that instruction flags match the patterns.3338  VerifyInstructionFlags();3339}3340 3341const Record *CodeGenDAGPatterns::getSDNodeNamed(StringRef Name) const {3342  const Record *N = Records.getDef(Name);3343  if (!N || !N->isSubClassOf("SDNode"))3344    PrintFatalError("Error getting SDNode '" + Name + "'!");3345  return N;3346}3347 3348// Compute the subset of iPTR and cPTR legal for each mode, coalescing into the3349// default mode where possible to avoid predicate explosion.3350TypeSetByHwMode CodeGenDAGPatterns::ComputeLegalPtrTypes() const {3351  auto LegalPtrsForSet = [](const MachineValueTypeSet &In) {3352    MachineValueTypeSet Out;3353    Out.insert(MVT::iPTR);3354    for (MVT T : MVT::cheri_capability_valuetypes()) {3355      if (In.count(T)) {3356        Out.insert(MVT::cPTR);3357        break;3358      }3359    }3360    return Out;3361  };3362 3363  const TypeSetByHwMode &LegalTypes = getLegalTypes();3364  MachineValueTypeSet LegalPtrsDefault =3365      LegalPtrsForSet(LegalTypes.get(DefaultMode));3366 3367  TypeSetByHwMode LegalPtrTypes;3368  for (const auto &I : LegalTypes) {3369    MachineValueTypeSet S = LegalPtrsForSet(I.second);3370    if (I.first != DefaultMode && S == LegalPtrsDefault)3371      continue;3372    LegalPtrTypes.getOrCreate(I.first).insert(S);3373  }3374 3375  return LegalPtrTypes;3376}3377 3378// Parse all of the SDNode definitions for the target, populating SDNodes.3379void CodeGenDAGPatterns::ParseNodeInfo() {3380  const CodeGenHwModes &CGH = getTargetInfo().getHwModes();3381 3382  for (const Record *R : reverse(Records.getAllDerivedDefinitions("SDNode")))3383    SDNodes.try_emplace(R, SDNodeInfo(R, CGH));3384 3385  // Get the builtin intrinsic nodes.3386  intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void");3387  intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain");3388  intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain");3389}3390 3391/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms3392/// map, and emit them to the file as functions.3393void CodeGenDAGPatterns::ParseNodeTransforms() {3394  for (const Record *XFormNode :3395       reverse(Records.getAllDerivedDefinitions("SDNodeXForm"))) {3396    const Record *SDNode = XFormNode->getValueAsDef("Opcode");3397    StringRef Code = XFormNode->getValueAsString("XFormFunction");3398    SDNodeXForms.try_emplace(XFormNode, NodeXForm(SDNode, Code.str()));3399  }3400}3401 3402void CodeGenDAGPatterns::ParseComplexPatterns() {3403  for (const Record *R :3404       reverse(Records.getAllDerivedDefinitions("ComplexPattern")))3405    ComplexPatterns.try_emplace(R, R);3406}3407 3408/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td3409/// file, building up the PatternFragments map.  After we've collected them all,3410/// inline fragments together as necessary, so that there are no references left3411/// inside a pattern fragment to a pattern fragment.3412///3413void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {3414  // First step, parse all of the fragments.3415  ArrayRef<const Record *> Fragments =3416      Records.getAllDerivedDefinitions("PatFrags");3417  for (const Record *Frag : Fragments) {3418    if (OutFrags != Frag->isSubClassOf("OutPatFrag"))3419      continue;3420 3421    const ListInit *LI = Frag->getValueAsListInit("Fragments");3422    TreePattern *P = (PatternFragments[Frag] = std::make_unique<TreePattern>(3423                          Frag, LI, !Frag->isSubClassOf("OutPatFrag"), *this))3424                         .get();3425 3426    // Validate the argument list, converting it to set, to discard duplicates.3427    std::vector<std::string> &Args = P->getArgList();3428    // Copy the args so we can take StringRefs to them.3429    auto ArgsCopy = Args;3430    SmallDenseSet<StringRef, 4> OperandsSet(llvm::from_range, ArgsCopy);3431 3432    if (OperandsSet.contains(""))3433      P->error("Cannot have unnamed 'node' values in pattern fragment!");3434 3435    // Parse the operands list.3436    const DagInit *OpsList = Frag->getValueAsDag("Operands");3437    const DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator());3438    // Special cases: ops == outs == ins. Different names are used to3439    // improve readability.3440    if (!OpsOp || (OpsOp->getDef()->getName() != "ops" &&3441                   OpsOp->getDef()->getName() != "outs" &&3442                   OpsOp->getDef()->getName() != "ins"))3443      P->error("Operands list should start with '(ops ... '!");3444 3445    // Copy over the arguments.3446    Args.clear();3447    for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) {3448      if (!isa<DefInit>(OpsList->getArg(j)) ||3449          cast<DefInit>(OpsList->getArg(j))->getDef()->getName() != "node")3450        P->error("Operands list should all be 'node' values.");3451      if (!OpsList->getArgName(j))3452        P->error("Operands list should have names for each operand!");3453      StringRef ArgNameStr = OpsList->getArgNameStr(j);3454      if (!OperandsSet.erase(ArgNameStr))3455        P->error("'" + ArgNameStr +3456                 "' does not occur in pattern or was multiply specified!");3457      Args.push_back(ArgNameStr.str());3458    }3459 3460    if (!OperandsSet.empty())3461      P->error("Operands list does not contain an entry for operand '" +3462               *OperandsSet.begin() + "'!");3463 3464    // If there is a node transformation corresponding to this, keep track of3465    // it.3466    const Record *Transform = Frag->getValueAsDef("OperandTransform");3467    if (!getSDNodeTransform(Transform).second.empty()) // not noop xform?3468      for (const auto &T : P->getTrees())3469        T->setTransformFn(Transform);3470  }3471 3472  // Now that we've parsed all of the tree fragments, do a closure on them so3473  // that there are not references to PatFrags left inside of them.3474  for (const Record *Frag : Fragments) {3475    if (OutFrags != Frag->isSubClassOf("OutPatFrag"))3476      continue;3477 3478    TreePattern &ThePat = *PatternFragments[Frag];3479    ThePat.InlinePatternFragments();3480 3481    // Infer as many types as possible.  Don't worry about it if we don't infer3482    // all of them, some may depend on the inputs of the pattern.  Also, don't3483    // validate type sets; validation may cause spurious failures e.g. if a3484    // fragment needs floating-point types but the current target does not have3485    // any (this is only an error if that fragment is ever used!).3486    {3487      TypeInfer::SuppressValidation SV(ThePat.getInfer());3488      ThePat.InferAllTypes();3489      ThePat.resetError();3490    }3491 3492    // If debugging, print out the pattern fragment result.3493    LLVM_DEBUG(ThePat.dump());3494  }3495}3496 3497void CodeGenDAGPatterns::ParseDefaultOperands() {3498  ArrayRef<const Record *> DefaultOps =3499      Records.getAllDerivedDefinitions("OperandWithDefaultOps");3500 3501  for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) {3502    const DagInit *DefaultInfo = DefaultOps[i]->getValueAsDag("DefaultOps");3503 3504    // Create a TreePattern to parse this.3505    TreePattern P(DefaultOps[i], DefaultInfo->getArgs(),3506                  DefaultInfo->getArgNames(), false, *this);3507    assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!");3508 3509    // Copy the operands over into a DAGDefaultOperand.3510    DAGDefaultOperand DefaultOpInfo;3511 3512    const TreePatternNodePtr &T = P.getTree(0);3513    for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) {3514      TreePatternNodePtr TPN = T->getChildShared(op);3515      while (TPN->ApplyTypeConstraints(P, false))3516        /* Resolve all types */;3517 3518      if (TPN->ContainsUnresolvedType(P)) {3519        PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" +3520                        DefaultOps[i]->getName() +3521                        "' doesn't have a concrete type!");3522      }3523      DefaultOpInfo.DefaultOps.push_back(std::move(TPN));3524    }3525 3526    // Insert it into the DefaultOperands map so we can find it later.3527    DefaultOperands[DefaultOps[i]] = DefaultOpInfo;3528  }3529}3530 3531/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an3532/// instruction input.  Return true if this is a real use.3533static bool HandleUse(TreePattern &I, TreePatternNodePtr Pat,3534                      std::map<StringRef, TreePatternNodePtr> &InstInputs) {3535  // No name -> not interesting.3536  if (Pat->getName().empty()) {3537    if (Pat->isLeaf()) {3538      const DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());3539      if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||3540                 DI->getDef()->isSubClassOf("RegisterOperand")))3541        I.error("Input " + DI->getDef()->getName() + " must be named!");3542    }3543    return false;3544  }3545 3546  const Record *Rec;3547  if (Pat->isLeaf()) {3548    const DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());3549    if (!DI)3550      I.error("Input $" + Pat->getName() + " must be an identifier!");3551    Rec = DI->getDef();3552  } else {3553    Rec = Pat->getOperator();3554  }3555 3556  // SRCVALUE nodes are ignored.3557  if (Rec->getName() == "srcvalue")3558    return false;3559 3560  TreePatternNodePtr &Slot = InstInputs[Pat->getName()];3561  if (!Slot) {3562    Slot = Pat;3563    return true;3564  }3565  const Record *SlotRec;3566  if (Slot->isLeaf()) {3567    SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef();3568  } else {3569    assert(Slot->getNumChildren() == 0 && "can't be a use with children!");3570    SlotRec = Slot->getOperator();3571  }3572 3573  // Ensure that the inputs agree if we've already seen this input.3574  if (Rec != SlotRec)3575    I.error("All $" + Pat->getName() + " inputs must agree with each other");3576  // Ensure that the types can agree as well.3577  Slot->UpdateNodeType(0, Pat->getExtType(0), I);3578  Pat->UpdateNodeType(0, Slot->getExtType(0), I);3579  if (Slot->getExtTypes() != Pat->getExtTypes())3580    I.error("All $" + Pat->getName() + " inputs must agree with each other");3581  return true;3582}3583 3584/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is3585/// part of "I", the instruction), computing the set of inputs and outputs of3586/// the pattern.  Report errors if we see anything naughty.3587void CodeGenDAGPatterns::FindPatternInputsAndOutputs(3588    TreePattern &I, TreePatternNodePtr Pat, InstInputsTy &InstInputs,3589    InstResultsTy &InstResults, std::vector<const Record *> &InstImpResults) {3590  // The instruction pattern still has unresolved fragments.  For *named*3591  // nodes we must resolve those here.  This may not result in multiple3592  // alternatives.3593  if (!Pat->getName().empty()) {3594    TreePattern SrcPattern(I.getRecord(), Pat, true, *this);3595    SrcPattern.InlinePatternFragments();3596    SrcPattern.InferAllTypes();3597    Pat = SrcPattern.getOnlyTree();3598  }3599 3600  if (Pat->isLeaf()) {3601    bool isUse = HandleUse(I, Pat, InstInputs);3602    if (!isUse && Pat->getTransformFn())3603      I.error("Cannot specify a transform function for a non-input value!");3604    return;3605  }3606 3607  if (Pat->getOperator()->getName() != "set") {3608    // If this is not a set, verify that the children nodes are not void typed,3609    // and recurse.3610    for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {3611      if (Pat->getChild(i).getNumTypes() == 0)3612        I.error("Cannot have void nodes inside of patterns!");3613      FindPatternInputsAndOutputs(I, Pat->getChildShared(i), InstInputs,3614                                  InstResults, InstImpResults);3615    }3616 3617    // If this is a non-leaf node with no children, treat it basically as if3618    // it were a leaf.  This handles nodes like (imm).3619    bool isUse = HandleUse(I, Pat, InstInputs);3620 3621    if (!isUse && Pat->getTransformFn())3622      I.error("Cannot specify a transform function for a non-input value!");3623    return;3624  }3625 3626  // Otherwise, this is a set, validate and collect instruction results.3627  if (Pat->getNumChildren() == 0)3628    I.error("set requires operands!");3629 3630  if (Pat->getTransformFn())3631    I.error("Cannot specify a transform function on a set node!");3632 3633  // Check the set destinations.3634  unsigned NumDests = Pat->getNumChildren() - 1;3635  for (unsigned i = 0; i != NumDests; ++i) {3636    TreePatternNodePtr Dest = Pat->getChildShared(i);3637    // For set destinations we also must resolve fragments here.3638    TreePattern DestPattern(I.getRecord(), Dest, false, *this);3639    DestPattern.InlinePatternFragments();3640    DestPattern.InferAllTypes();3641    Dest = DestPattern.getOnlyTree();3642 3643    if (!Dest->isLeaf())3644      I.error("set destination should be a register!");3645 3646    const DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());3647    if (!Val) {3648      I.error("set destination should be a register!");3649      continue;3650    }3651 3652    if (Val->getDef()->isSubClassOf("RegisterClassLike") ||3653        Val->getDef()->isSubClassOf("ValueType") ||3654        Val->getDef()->isSubClassOf("RegisterOperand")) {3655      if (Dest->getName().empty())3656        I.error("set destination must have a name!");3657      if (!InstResults.insert_or_assign(Dest->getName(), Dest).second)3658        I.error("cannot set '" + Dest->getName() + "' multiple times");3659    } else if (Val->getDef()->isSubClassOf("Register")) {3660      InstImpResults.push_back(Val->getDef());3661    } else {3662      I.error("set destination should be a register!");3663    }3664  }3665 3666  // Verify and collect info from the computation.3667  FindPatternInputsAndOutputs(I, Pat->getChildShared(NumDests), InstInputs,3668                              InstResults, InstImpResults);3669}3670 3671//===----------------------------------------------------------------------===//3672// Instruction Analysis3673//===----------------------------------------------------------------------===//3674 3675class InstAnalyzer {3676  const CodeGenDAGPatterns &CDP;3677 3678public:3679  bool hasSideEffects = false;3680  bool mayStore = false;3681  bool mayLoad = false;3682  bool isBitcast = false;3683  bool isVariadic = false;3684  bool hasChain = false;3685 3686  InstAnalyzer(const CodeGenDAGPatterns &cdp) : CDP(cdp) {}3687 3688  void Analyze(const PatternToMatch &Pat) {3689    const TreePatternNode &N = Pat.getSrcPattern();3690    AnalyzeNode(N);3691    // These properties are detected only on the root node.3692    isBitcast = IsNodeBitcast(N);3693  }3694 3695private:3696  bool IsNodeBitcast(const TreePatternNode &N) const {3697    if (hasSideEffects || mayLoad || mayStore || isVariadic)3698      return false;3699 3700    if (N.isLeaf())3701      return false;3702    if (N.getNumChildren() != 1 || !N.getChild(0).isLeaf())3703      return false;3704 3705    if (N.getOperator()->isSubClassOf("ComplexPattern"))3706      return false;3707 3708    const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N.getOperator());3709    if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1)3710      return false;3711    return OpInfo.getEnumName() == "ISD::BITCAST";3712  }3713 3714public:3715  void AnalyzeNode(const TreePatternNode &N) {3716    if (N.isLeaf()) {3717      if (const DefInit *DI = dyn_cast<DefInit>(N.getLeafValue())) {3718        const Record *LeafRec = DI->getDef();3719        // Handle ComplexPattern leaves.3720        if (LeafRec->isSubClassOf("ComplexPattern")) {3721          const ComplexPattern &CP = CDP.getComplexPattern(LeafRec);3722          if (CP.hasProperty(SDNPMayStore))3723            mayStore = true;3724          if (CP.hasProperty(SDNPMayLoad))3725            mayLoad = true;3726          if (CP.hasProperty(SDNPSideEffect))3727            hasSideEffects = true;3728        }3729      }3730      return;3731    }3732 3733    // Analyze children.3734    for (const TreePatternNode &Child : N.children())3735      AnalyzeNode(Child);3736 3737    // Notice properties of the node.3738    if (N.NodeHasProperty(SDNPMayStore, CDP))3739      mayStore = true;3740    if (N.NodeHasProperty(SDNPMayLoad, CDP))3741      mayLoad = true;3742    if (N.NodeHasProperty(SDNPSideEffect, CDP))3743      hasSideEffects = true;3744    if (N.NodeHasProperty(SDNPVariadic, CDP))3745      isVariadic = true;3746    if (N.NodeHasProperty(SDNPHasChain, CDP))3747      hasChain = true;3748 3749    if (const CodeGenIntrinsic *IntInfo = N.getIntrinsicInfo(CDP)) {3750      ModRefInfo MR = IntInfo->ME.getModRef();3751      // If this is an intrinsic, analyze it.3752      if (isRefSet(MR))3753        mayLoad = true; // These may load memory.3754 3755      if (isModSet(MR))3756        mayStore = true; // Intrinsics that can write to memory are 'mayStore'.3757 3758      // Consider intrinsics that don't specify any restrictions on memory3759      // effects as having a side-effect.3760      if (IntInfo->ME == MemoryEffects::unknown() || IntInfo->hasSideEffects)3761        hasSideEffects = true;3762    }3763  }3764};3765 3766static bool InferFromPattern(CodeGenInstruction &InstInfo,3767                             const InstAnalyzer &PatInfo,3768                             const Record *PatDef) {3769  bool Error = false;3770 3771  // Remember where InstInfo got its flags.3772  if (InstInfo.hasUndefFlags())3773    InstInfo.InferredFrom = PatDef;3774 3775  // Check explicitly set flags for consistency.3776  if (InstInfo.hasSideEffects != PatInfo.hasSideEffects &&3777      !InstInfo.hasSideEffects_Unset) {3778    // Allow explicitly setting hasSideEffects = 1 on instructions, even when3779    // the pattern has no side effects. That could be useful for div/rem3780    // instructions that may trap.3781    if (!InstInfo.hasSideEffects) {3782      Error = true;3783      PrintError(PatDef->getLoc(), "Pattern doesn't match hasSideEffects = " +3784                                       Twine(InstInfo.hasSideEffects));3785    }3786  }3787 3788  if (InstInfo.mayStore != PatInfo.mayStore && !InstInfo.mayStore_Unset) {3789    Error = true;3790    PrintError(PatDef->getLoc(),3791               "Pattern doesn't match mayStore = " + Twine(InstInfo.mayStore));3792  }3793 3794  if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) {3795    // Allow explicitly setting mayLoad = 1, even when the pattern has no loads.3796    // Some targets translate immediates to loads.3797    if (!InstInfo.mayLoad) {3798      Error = true;3799      PrintError(PatDef->getLoc(),3800                 "Pattern doesn't match mayLoad = " + Twine(InstInfo.mayLoad));3801    }3802  }3803 3804  // Transfer inferred flags.3805  InstInfo.hasSideEffects |= PatInfo.hasSideEffects;3806  InstInfo.mayStore |= PatInfo.mayStore;3807  InstInfo.mayLoad |= PatInfo.mayLoad;3808 3809  // These flags are silently added without any verification.3810  // FIXME: To match historical behavior of TableGen, for now add those flags3811  // only when we're inferring from the primary instruction pattern.3812  if (PatDef->isSubClassOf("Instruction")) {3813    InstInfo.isBitcast |= PatInfo.isBitcast;3814    InstInfo.hasChain |= PatInfo.hasChain;3815    InstInfo.hasChain_Inferred = true;3816  }3817 3818  // Don't infer isVariadic. This flag means something different on SDNodes and3819  // instructions. For example, a CALL SDNode is variadic because it has the3820  // call arguments as operands, but a CALL instruction is not variadic - it3821  // has argument registers as implicit, not explicit uses.3822 3823  return Error;3824}3825 3826/// hasNullFragReference - Return true if the DAG has any reference to the3827/// null_frag operator.3828static bool hasNullFragReference(const DagInit *DI) {3829  const DefInit *OpDef = dyn_cast<DefInit>(DI->getOperator());3830  if (!OpDef)3831    return false;3832  const Record *Operator = OpDef->getDef();3833 3834  // If this is the null fragment, return true.3835  if (Operator->getName() == "null_frag")3836    return true;3837  // If any of the arguments reference the null fragment, return true.3838  for (unsigned i = 0, e = DI->getNumArgs(); i != e; ++i) {3839    if (auto Arg = dyn_cast<DefInit>(DI->getArg(i)))3840      if (Arg->getDef()->getName() == "null_frag")3841        return true;3842    const DagInit *Arg = dyn_cast<DagInit>(DI->getArg(i));3843    if (Arg && hasNullFragReference(Arg))3844      return true;3845  }3846 3847  return false;3848}3849 3850/// hasNullFragReference - Return true if any DAG in the list references3851/// the null_frag operator.3852static bool hasNullFragReference(const ListInit *LI) {3853  for (const Init *I : LI->getElements()) {3854    const DagInit *DI = dyn_cast<DagInit>(I);3855    assert(DI && "non-dag in an instruction Pattern list?!");3856    if (hasNullFragReference(DI))3857      return true;3858  }3859  return false;3860}3861 3862/// Get all the instructions in a tree.3863static void getInstructionsInTree(TreePatternNode &Tree,3864                                  SmallVectorImpl<const Record *> &Instrs) {3865  if (Tree.isLeaf())3866    return;3867  if (Tree.getOperator()->isSubClassOf("Instruction"))3868    Instrs.push_back(Tree.getOperator());3869  for (TreePatternNode &Child : Tree.children())3870    getInstructionsInTree(Child, Instrs);3871}3872 3873/// Check the class of a pattern leaf node against the instruction operand it3874/// represents.3875static bool checkOperandClass(const CGIOperandList::OperandInfo &OI,3876                              const Record *Leaf) {3877  if (OI.Rec == Leaf)3878    return true;3879 3880  // Allow direct value types to be used in instruction set patterns.3881  // The type will be checked later.3882  if (Leaf->isSubClassOf("ValueType"))3883    return true;3884 3885  // Patterns can also be ComplexPattern instances.3886  if (Leaf->isSubClassOf("ComplexPattern"))3887    return true;3888 3889  return false;3890}3891 3892void CodeGenDAGPatterns::parseInstructionPattern(const CodeGenInstruction &CGI,3893                                                 const ListInit *Pat,3894                                                 DAGInstMap &DAGInsts) {3895 3896  assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!");3897 3898  // Parse the instruction.3899  TreePattern I(CGI.TheDef, Pat, true, *this);3900 3901  // InstInputs - Keep track of all of the inputs of the instruction, along3902  // with the record they are declared as.3903  std::map<StringRef, TreePatternNodePtr> InstInputs;3904 3905  // InstResults - Keep track of all the virtual registers that are 'set'3906  // in the instruction, including what reg class they are.3907  MapVector<StringRef, TreePatternNodePtr, std::map<StringRef, unsigned>>3908      InstResults;3909 3910  std::vector<const Record *> InstImpResults;3911 3912  // Verify that the top-level forms in the instruction are of void type, and3913  // fill in the InstResults map.3914  SmallString<32> TypesString;3915  for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) {3916    TypesString.clear();3917    TreePatternNodePtr Pat = I.getTree(j);3918    if (Pat->getNumTypes() != 0) {3919      raw_svector_ostream OS(TypesString);3920      ListSeparator LS;3921      for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {3922        OS << LS;3923        Pat->getExtType(k).writeToStream(OS);3924      }3925      I.error("Top-level forms in instruction pattern should have"3926              " void types, has types " +3927              OS.str());3928    }3929 3930    // Find inputs and outputs, and verify the structure of the uses/defs.3931    FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,3932                                InstImpResults);3933  }3934 3935  // Now that we have inputs and outputs of the pattern, inspect the operands3936  // list for the instruction.  This determines the order that operands are3937  // added to the machine instruction the node corresponds to.3938  unsigned NumResults = InstResults.size();3939 3940  // Parse the operands list from the (ops) list, validating it.3941  assert(I.getArgList().empty() && "Args list should still be empty here!");3942 3943  // Check that all of the results occur first in the list.3944  std::vector<const Record *> Results;3945  std::vector<unsigned> ResultIndices;3946  SmallVector<TreePatternNodePtr, 2> ResNodes;3947  for (unsigned i = 0; i != NumResults; ++i) {3948    if (i == CGI.Operands.size()) {3949      StringRef OpName =3950          llvm::find_if(InstResults,3951                        [](const std::pair<StringRef, TreePatternNodePtr> &P) {3952                          return P.second;3953                        })3954              ->first;3955 3956      I.error("'" + OpName + "' set but does not appear in operand list!");3957    }3958 3959    StringRef OpName = CGI.Operands[i].Name;3960 3961    // Check that it exists in InstResults.3962    auto InstResultIter = InstResults.find(OpName);3963    if (InstResultIter == InstResults.end() || !InstResultIter->second)3964      I.error("Operand $" + OpName + " does not exist in operand list!");3965 3966    TreePatternNodePtr RNode = InstResultIter->second;3967    const Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();3968    ResNodes.push_back(std::move(RNode));3969    if (!R)3970      I.error("Operand $" + OpName +3971              " should be a set destination: all "3972              "outputs must occur before inputs in operand list!");3973 3974    if (!checkOperandClass(CGI.Operands[i], R))3975      I.error("Operand $" + OpName + " class mismatch!");3976 3977    // Remember the return type.3978    Results.push_back(CGI.Operands[i].Rec);3979 3980    // Remember the result index.3981    ResultIndices.push_back(std::distance(InstResults.begin(), InstResultIter));3982 3983    // Okay, this one checks out.3984    InstResultIter->second = nullptr;3985  }3986 3987  // Loop over the inputs next.3988  std::vector<TreePatternNodePtr> ResultNodeOperands;3989  std::vector<const Record *> Operands;3990  for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {3991    const CGIOperandList::OperandInfo &Op = CGI.Operands[i];3992    StringRef OpName = Op.Name;3993    if (OpName.empty()) {3994      I.error("Operand #" + Twine(i) + " in operands list has no name!");3995      continue;3996    }3997 3998    auto InIter = InstInputs.find(OpName);3999    if (InIter == InstInputs.end()) {4000      // If this is an operand with a DefaultOps set filled in, we can ignore4001      // this.  When we codegen it, we will do so as always executed.4002      if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {4003        // Does it have a non-empty DefaultOps field?  If so, ignore this4004        // operand.4005        if (!getDefaultOperand(Op.Rec).DefaultOps.empty())4006          continue;4007      }4008      I.error("Operand $" + OpName +4009              " does not appear in the instruction pattern");4010      continue;4011    }4012    TreePatternNodePtr InVal = InIter->second;4013    InstInputs.erase(InIter); // It occurred, remove from map.4014 4015    if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {4016      const Record *InRec = cast<DefInit>(InVal->getLeafValue())->getDef();4017      if (!checkOperandClass(Op, InRec)) {4018        I.error("Operand $" + OpName +4019                "'s register class disagrees"4020                " between the operand and pattern");4021        continue;4022      }4023    }4024    Operands.push_back(Op.Rec);4025 4026    // Construct the result for the dest-pattern operand list.4027    TreePatternNodePtr OpNode = InVal->clone();4028 4029    // No predicate is useful on the result.4030    OpNode->clearPredicateCalls();4031 4032    // Promote the xform function to be an explicit node if set.4033    if (const Record *Xform = OpNode->getTransformFn()) {4034      OpNode->setTransformFn(nullptr);4035      std::vector<TreePatternNodePtr> Children;4036      Children.push_back(OpNode);4037      OpNode = makeIntrusiveRefCnt<TreePatternNode>(Xform, std::move(Children),4038                                                    OpNode->getNumTypes());4039    }4040 4041    ResultNodeOperands.push_back(std::move(OpNode));4042  }4043 4044  if (!InstInputs.empty())4045    I.error("Input operand $" + InstInputs.begin()->first +4046            " occurs in pattern but not in operands list!");4047 4048  TreePatternNodePtr ResultPattern = makeIntrusiveRefCnt<TreePatternNode>(4049      I.getRecord(), std::move(ResultNodeOperands),4050      GetNumNodeResults(I.getRecord(), *this));4051  // Copy fully inferred output node types to instruction result pattern.4052  for (unsigned i = 0; i != NumResults; ++i) {4053    assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled");4054    ResultPattern->setType(i, ResNodes[i]->getExtType(0));4055    ResultPattern->setResultIndex(i, ResultIndices[i]);4056  }4057 4058  // FIXME: Assume only the first tree is the pattern. The others are clobber4059  // nodes.4060  TreePatternNodePtr Pattern = I.getTree(0);4061  TreePatternNodePtr SrcPattern;4062  if (Pattern->getOperator()->getName() == "set") {4063    SrcPattern = Pattern->getChild(Pattern->getNumChildren() - 1).clone();4064  } else {4065    // Not a set (store or something?)4066    SrcPattern = Pattern;4067  }4068 4069  // Create and insert the instruction.4070  // FIXME: InstImpResults should not be part of DAGInstruction.4071  DAGInsts.try_emplace(I.getRecord(), std::move(Results), std::move(Operands),4072                       std::move(InstImpResults), SrcPattern, ResultPattern);4073 4074  LLVM_DEBUG(I.dump());4075}4076 4077/// ParseInstructions - Parse all of the instructions, inlining and resolving4078/// any fragments involved.  This populates the Instructions list with fully4079/// resolved instructions.4080void CodeGenDAGPatterns::ParseInstructions() {4081  for (const Record *Instr : Records.getAllDerivedDefinitions("Instruction")) {4082    const ListInit *LI = nullptr;4083 4084    if (isa<ListInit>(Instr->getValueInit("Pattern")))4085      LI = Instr->getValueAsListInit("Pattern");4086 4087    // If there is no pattern, only collect minimal information about the4088    // instruction for its operand list.  We have to assume that there is one4089    // result, as we have no detailed info. A pattern which references the4090    // null_frag operator is as-if no pattern were specified. Normally this4091    // is from a multiclass expansion w/ a SDPatternOperator passed in as4092    // null_frag.4093    if (!LI || LI->empty() || hasNullFragReference(LI)) {4094      std::vector<const Record *> Results;4095      std::vector<const Record *> Operands;4096 4097      const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);4098 4099      if (InstInfo.Operands.size() != 0) {4100        for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j)4101          Results.push_back(InstInfo.Operands[j].Rec);4102 4103        // The rest are inputs.4104        for (unsigned j = InstInfo.Operands.NumDefs,4105                      e = InstInfo.Operands.size();4106             j < e; ++j)4107          Operands.push_back(InstInfo.Operands[j].Rec);4108      }4109 4110      // Create and insert the instruction.4111      Instructions.try_emplace(Instr, std::move(Results), std::move(Operands),4112                               std::vector<const Record *>());4113      continue; // no pattern.4114    }4115 4116    const CodeGenInstruction &CGI = Target.getInstruction(Instr);4117    parseInstructionPattern(CGI, LI, Instructions);4118  }4119 4120  // If we can, convert the instructions to be patterns that are matched!4121  for (const auto &[Instr, TheInst] : Instructions) {4122    TreePatternNodePtr SrcPattern = TheInst.getSrcPattern();4123    TreePatternNodePtr ResultPattern = TheInst.getResultPattern();4124 4125    if (SrcPattern && ResultPattern) {4126      TreePattern Pattern(Instr, SrcPattern, true, *this);4127      TreePattern Result(Instr, ResultPattern, false, *this);4128      ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults());4129    }4130  }4131}4132 4133using NameRecord = std::pair<TreePatternNode *, unsigned>;4134 4135static void FindNames(TreePatternNode &P,4136                      std::map<StringRef, NameRecord> &Names,4137                      TreePattern *PatternTop) {4138  if (!P.getName().empty()) {4139    NameRecord &Rec = Names[P.getName()];4140    // If this is the first instance of the name, remember the node.4141    if (Rec.second++ == 0)4142      Rec.first = &P;4143    else if (Rec.first->getExtTypes() != P.getExtTypes())4144      PatternTop->error("repetition of value: $" + P.getName() +4145                        " where different uses have different types!");4146  }4147 4148  if (!P.isLeaf()) {4149    for (TreePatternNode &Child : P.children())4150      FindNames(Child, Names, PatternTop);4151  }4152}4153 4154void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,4155                                           PatternToMatch &&PTM) {4156  // Do some sanity checking on the pattern we're about to match.4157  std::string Reason;4158  if (!PTM.getSrcPattern().canPatternMatch(Reason, *this)) {4159    PrintWarning(Pattern->getRecord()->getLoc(),4160                 Twine("Pattern can never match: ") + Reason);4161    return;4162  }4163 4164  // If the source pattern's root is a complex pattern, that complex pattern4165  // must specify the nodes it can potentially match.4166  if (const ComplexPattern *CP =4167          PTM.getSrcPattern().getComplexPatternInfo(*this))4168    if (CP->getRootNodes().empty())4169      Pattern->error("ComplexPattern at root must specify list of opcodes it"4170                     " could match");4171 4172  // Find all of the named values in the input and output, ensure they have the4173  // same type.4174  std::map<StringRef, NameRecord> SrcNames, DstNames;4175  FindNames(PTM.getSrcPattern(), SrcNames, Pattern);4176  FindNames(PTM.getDstPattern(), DstNames, Pattern);4177 4178  // Scan all of the named values in the destination pattern, rejecting them if4179  // they don't exist in the input pattern.4180  for (const auto &Entry : DstNames) {4181    if (SrcNames[Entry.first].first == nullptr)4182      Pattern->error("Pattern has input without matching name in output: $" +4183                     Entry.first);4184  }4185 4186  // Scan all of the named values in the source pattern, rejecting them if the4187  // name isn't used in the dest, and isn't used to tie two values together.4188  for (const auto &Entry : SrcNames)4189    if (DstNames[Entry.first].first == nullptr &&4190        SrcNames[Entry.first].second == 1)4191      Pattern->error("Pattern has dead named input: $" + Entry.first);4192 4193  PatternsToMatch.push_back(std::move(PTM));4194}4195 4196void CodeGenDAGPatterns::InferInstructionFlags() {4197  ArrayRef<const CodeGenInstruction *> Instructions = Target.getInstructions();4198 4199  unsigned Errors = 0;4200 4201  // Try to infer flags from all patterns in PatternToMatch.  These include4202  // both the primary instruction patterns (which always come first) and4203  // patterns defined outside the instruction.4204  for (const PatternToMatch &PTM : ptms()) {4205    // We can only infer from single-instruction patterns, otherwise we won't4206    // know which instruction should get the flags.4207    SmallVector<const Record *, 8> PatInstrs;4208    getInstructionsInTree(PTM.getDstPattern(), PatInstrs);4209    if (PatInstrs.size() != 1)4210      continue;4211 4212    // Get the single instruction.4213    CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());4214 4215    // Only infer properties from the first pattern. We'll verify the others.4216    if (InstInfo.InferredFrom)4217      continue;4218 4219    InstAnalyzer PatInfo(*this);4220    PatInfo.Analyze(PTM);4221    Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord());4222  }4223 4224  if (Errors)4225    PrintFatalError("pattern conflicts");4226 4227  // If requested by the target, guess any undefined properties.4228  if (Target.guessInstructionProperties()) {4229    for (const CodeGenInstruction *InstInfo : Instructions) {4230      if (InstInfo->InferredFrom)4231        continue;4232      // The mayLoad and mayStore flags default to false.4233      // Conservatively assume hasSideEffects if it wasn't explicit.4234      if (InstInfo->hasSideEffects_Unset)4235        const_cast<CodeGenInstruction *>(InstInfo)->hasSideEffects = true;4236    }4237    return;4238  }4239 4240  // Complain about any flags that are still undefined.4241  for (const CodeGenInstruction *InstInfo : Instructions) {4242    if (InstInfo->InferredFrom)4243      continue;4244    if (InstInfo->hasSideEffects_Unset)4245      PrintError(InstInfo->TheDef->getLoc(),4246                 "Can't infer hasSideEffects from patterns");4247    if (InstInfo->mayStore_Unset)4248      PrintError(InstInfo->TheDef->getLoc(),4249                 "Can't infer mayStore from patterns");4250    if (InstInfo->mayLoad_Unset)4251      PrintError(InstInfo->TheDef->getLoc(),4252                 "Can't infer mayLoad from patterns");4253  }4254}4255 4256/// Verify instruction flags against pattern node properties.4257void CodeGenDAGPatterns::VerifyInstructionFlags() {4258  unsigned Errors = 0;4259  for (const PatternToMatch &PTM : ptms()) {4260    SmallVector<const Record *, 8> Instrs;4261    getInstructionsInTree(PTM.getDstPattern(), Instrs);4262    if (Instrs.empty())4263      continue;4264 4265    // Count the number of instructions with each flag set.4266    unsigned NumSideEffects = 0;4267    unsigned NumStores = 0;4268    unsigned NumLoads = 0;4269    for (const Record *Instr : Instrs) {4270      const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);4271      NumSideEffects += InstInfo.hasSideEffects;4272      NumStores += InstInfo.mayStore;4273      NumLoads += InstInfo.mayLoad;4274    }4275 4276    // Analyze the source pattern.4277    InstAnalyzer PatInfo(*this);4278    PatInfo.Analyze(PTM);4279 4280    // Collect error messages.4281    SmallVector<std::string, 4> Msgs;4282 4283    // Check for missing flags in the output.4284    // Permit extra flags for now at least.4285    if (PatInfo.hasSideEffects && !NumSideEffects)4286      Msgs.push_back("pattern has side effects, but hasSideEffects isn't set");4287 4288    // Don't verify store flags on instructions with side effects. At least for4289    // intrinsics, side effects implies mayStore.4290    if (!PatInfo.hasSideEffects && PatInfo.mayStore && !NumStores)4291      Msgs.push_back("pattern may store, but mayStore isn't set");4292 4293    // Similarly, mayStore implies mayLoad on intrinsics.4294    if (!PatInfo.mayStore && PatInfo.mayLoad && !NumLoads)4295      Msgs.push_back("pattern may load, but mayLoad isn't set");4296 4297    // Print error messages.4298    if (Msgs.empty())4299      continue;4300    ++Errors;4301 4302    for (const std::string &Msg : Msgs)4303      PrintError(4304          PTM.getSrcRecord()->getLoc(),4305          Twine(Msg) + " on the " +4306              (Instrs.size() == 1 ? "instruction" : "output instructions"));4307    // Provide the location of the relevant instruction definitions.4308    for (const Record *Instr : Instrs) {4309      if (Instr != PTM.getSrcRecord())4310        PrintError(Instr->getLoc(), "defined here");4311      const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);4312      if (InstInfo.InferredFrom && InstInfo.InferredFrom != InstInfo.TheDef &&4313          InstInfo.InferredFrom != PTM.getSrcRecord())4314        PrintError(InstInfo.InferredFrom->getLoc(), "inferred from pattern");4315    }4316  }4317  if (Errors)4318    PrintFatalError("Errors in DAG patterns");4319}4320 4321/// Given a pattern result with an unresolved type, see if we can find one4322/// instruction with an unresolved result type.  Force this result type to an4323/// arbitrary element if it's possible types to converge results.4324static bool ForceArbitraryInstResultType(TreePatternNode &N, TreePattern &TP) {4325  if (N.isLeaf())4326    return false;4327 4328  // Analyze children.4329  for (TreePatternNode &Child : N.children())4330    if (ForceArbitraryInstResultType(Child, TP))4331      return true;4332 4333  if (!N.getOperator()->isSubClassOf("Instruction"))4334    return false;4335 4336  // If this type is already concrete or completely unknown we can't do4337  // anything.4338  TypeInfer &TI = TP.getInfer();4339  for (unsigned i = 0, e = N.getNumTypes(); i != e; ++i) {4340    if (N.getExtType(i).empty() || TI.isConcrete(N.getExtType(i), false))4341      continue;4342 4343    // Otherwise, force its type to an arbitrary choice.4344    if (TI.forceArbitrary(N.getExtType(i)))4345      return true;4346  }4347 4348  return false;4349}4350 4351// Promote xform function to be an explicit node wherever set.4352static TreePatternNodePtr PromoteXForms(TreePatternNodePtr N) {4353  if (const Record *Xform = N->getTransformFn()) {4354    N->setTransformFn(nullptr);4355    std::vector<TreePatternNodePtr> Children;4356    Children.push_back(PromoteXForms(N));4357    return makeIntrusiveRefCnt<TreePatternNode>(Xform, std::move(Children),4358                                                N->getNumTypes());4359  }4360 4361  if (!N->isLeaf())4362    for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {4363      TreePatternNodePtr Child = N->getChildShared(i);4364      N->setChild(i, PromoteXForms(Child));4365    }4366  return N;4367}4368 4369void CodeGenDAGPatterns::ParseOnePattern(4370    const Record *TheDef, TreePattern &Pattern, TreePattern &Result,4371    ArrayRef<const Record *> InstImpResults, bool ShouldIgnore) {4372  // Inline pattern fragments and expand multiple alternatives.4373  Pattern.InlinePatternFragments();4374  Result.InlinePatternFragments();4375 4376  if (Result.getNumTrees() != 1) {4377    Result.error("Cannot use multi-alternative fragments in result pattern!");4378    return;4379  }4380 4381  // Infer types.4382  bool IterateInference;4383  bool InferredAllPatternTypes, InferredAllResultTypes;4384  do {4385    // Infer as many types as possible.  If we cannot infer all of them, we4386    // can never do anything with this pattern: report it to the user.4387    InferredAllPatternTypes =4388        Pattern.InferAllTypes(&Pattern.getNamedNodesMap());4389 4390    // Infer as many types as possible.  If we cannot infer all of them, we4391    // can never do anything with this pattern: report it to the user.4392    InferredAllResultTypes = Result.InferAllTypes(&Pattern.getNamedNodesMap());4393 4394    IterateInference = false;4395 4396    // Apply the type of the result to the source pattern.  This helps us4397    // resolve cases where the input type is known to be a pointer type (which4398    // is considered resolved), but the result knows it needs to be 32- or4399    // 64-bits.  Infer the other way for good measure.4400    for (const auto &T : Pattern.getTrees())4401      for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(),4402                                        T->getNumTypes());4403           i != e; ++i) {4404        IterateInference |=4405            T->UpdateNodeType(i, Result.getOnlyTree()->getExtType(i), Result);4406        IterateInference |=4407            Result.getOnlyTree()->UpdateNodeType(i, T->getExtType(i), Result);4408      }4409 4410    // If our iteration has converged and the input pattern's types are fully4411    // resolved but the result pattern is not fully resolved, we may have a4412    // situation where we have two instructions in the result pattern and4413    // the instructions require a common register class, but don't care about4414    // what actual MVT is used.  This is actually a bug in our modelling:4415    // output patterns should have register classes, not MVTs.4416    //4417    // In any case, to handle this, we just go through and disambiguate some4418    // arbitrary types to the result pattern's nodes.4419    if (!IterateInference && InferredAllPatternTypes && !InferredAllResultTypes)4420      IterateInference =4421          ForceArbitraryInstResultType(*Result.getTree(0), Result);4422  } while (IterateInference);4423 4424  // Verify that we inferred enough types that we can do something with the4425  // pattern and result.  If these fire the user has to add type casts.4426  if (!InferredAllPatternTypes)4427    Pattern.error("Could not infer all types in pattern!");4428  if (!InferredAllResultTypes) {4429    Pattern.dump();4430    Result.error("Could not infer all types in pattern result!");4431  }4432 4433  // Promote xform function to be an explicit node wherever set.4434  TreePatternNodePtr DstShared = PromoteXForms(Result.getOnlyTree());4435 4436  TreePattern Temp(Result.getRecord(), DstShared, false, *this);4437  Temp.InferAllTypes();4438 4439  const ListInit *Preds = TheDef->getValueAsListInit("Predicates");4440  int Complexity = TheDef->getValueAsInt("AddedComplexity");4441 4442  if (PatternRewriter)4443    PatternRewriter(&Pattern);4444 4445  // A pattern may end up with an "impossible" type, i.e. a situation4446  // where all types have been eliminated for some node in this pattern.4447  // This could occur for intrinsics that only make sense for a specific4448  // value type, and use a specific register class. If, for some mode,4449  // that register class does not accept that type, the type inference4450  // will lead to a contradiction, which is not an error however, but4451  // a sign that this pattern will simply never match.4452  if (Temp.getOnlyTree()->hasPossibleType()) {4453    for (const auto &T : Pattern.getTrees()) {4454      if (T->hasPossibleType())4455        AddPatternToMatch(&Pattern,4456                          PatternToMatch(TheDef, Preds, T, Temp.getOnlyTree(),4457                                         InstImpResults, Complexity,4458                                         TheDef->getID(), ShouldIgnore));4459    }4460  } else {4461    // Show a message about a dropped pattern with some info to make it4462    // easier to identify it in the .td files.4463    LLVM_DEBUG({4464      dbgs() << "Dropping: ";4465      Pattern.dump();4466      Temp.getOnlyTree()->dump();4467      dbgs() << "\n";4468    });4469  }4470}4471 4472void CodeGenDAGPatterns::ParsePatterns() {4473  for (const Record *CurPattern : Records.getAllDerivedDefinitions("Pattern")) {4474    const DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");4475 4476    // If the pattern references the null_frag, there's nothing to do.4477    if (hasNullFragReference(Tree))4478      continue;4479 4480    TreePattern Pattern(CurPattern, Tree, true, *this);4481 4482    const ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");4483    if (LI->empty())4484      continue; // no pattern.4485 4486    // Parse the instruction.4487    TreePattern Result(CurPattern, LI, false, *this);4488 4489    if (Result.getNumTrees() != 1)4490      Result.error("Cannot handle instructions producing instructions "4491                   "with temporaries yet!");4492 4493    // Validate that the input pattern is correct.4494    InstInputsTy InstInputs;4495    InstResultsTy InstResults;4496    std::vector<const Record *> InstImpResults;4497    for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)4498      FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,4499                                  InstResults, InstImpResults);4500 4501    ParseOnePattern(CurPattern, Pattern, Result, InstImpResults,4502                    CurPattern->getValueAsBit("GISelShouldIgnore"));4503  }4504}4505 4506static void collectModes(std::set<unsigned> &Modes, const TreePatternNode &N) {4507  for (const TypeSetByHwMode &VTS : N.getExtTypes())4508    for (const auto &I : VTS)4509      Modes.insert(I.first);4510 4511  for (const TreePatternNode &Child : N.children())4512    collectModes(Modes, Child);4513}4514 4515void CodeGenDAGPatterns::ExpandHwModeBasedTypes() {4516  const CodeGenHwModes &CGH = getTargetInfo().getHwModes();4517  if (CGH.getNumModeIds() == 1)4518    return;4519 4520  std::vector<PatternToMatch> Copy;4521  PatternsToMatch.swap(Copy);4522 4523  auto AppendPattern = [this](PatternToMatch &P, unsigned Mode,4524                              StringRef Check) {4525    TreePatternNodePtr NewSrc = P.getSrcPattern().clone();4526    TreePatternNodePtr NewDst = P.getDstPattern().clone();4527    if (!NewSrc->setDefaultMode(Mode) || !NewDst->setDefaultMode(Mode)) {4528      return;4529    }4530 4531    PatternsToMatch.emplace_back(P.getSrcRecord(), P.getPredicates(),4532                                 std::move(NewSrc), std::move(NewDst),4533                                 P.getDstRegs(), P.getAddedComplexity(),4534                                 getNewUID(), P.getGISelShouldIgnore(), Check);4535  };4536 4537  for (PatternToMatch &P : Copy) {4538    const TreePatternNode *SrcP = nullptr, *DstP = nullptr;4539    if (P.getSrcPattern().hasProperTypeByHwMode())4540      SrcP = &P.getSrcPattern();4541    if (P.getDstPattern().hasProperTypeByHwMode())4542      DstP = &P.getDstPattern();4543    if (!SrcP && !DstP) {4544      PatternsToMatch.push_back(P);4545      continue;4546    }4547 4548    std::set<unsigned> Modes;4549    if (SrcP)4550      collectModes(Modes, *SrcP);4551    if (DstP)4552      collectModes(Modes, *DstP);4553 4554    // The predicate for the default mode needs to be constructed for each4555    // pattern separately.4556    // Since not all modes must be present in each pattern, if a mode m is4557    // absent, then there is no point in constructing a check for m. If such4558    // a check was created, it would be equivalent to checking the default4559    // mode, except not all modes' predicates would be a part of the checking4560    // code. The subsequently generated check for the default mode would then4561    // have the exact same patterns, but a different predicate code. To avoid4562    // duplicated patterns with different predicate checks, construct the4563    // default check as a negation of all predicates that are actually present4564    // in the source/destination patterns.4565    SmallString<128> DefaultCheck;4566 4567    for (unsigned M : Modes) {4568      if (M == DefaultMode)4569        continue;4570 4571      // Fill the map entry for this mode.4572      const HwMode &HM = CGH.getMode(M);4573 4574      SmallString<128> PredicateCheck;4575      raw_svector_ostream PS(PredicateCheck);4576      SubtargetFeatureInfo::emitPredicateCheck(PS, HM.Predicates);4577      AppendPattern(P, M, PredicateCheck);4578 4579      // Add negations of the HM's predicates to the default predicate.4580      if (!DefaultCheck.empty())4581        DefaultCheck += " && ";4582      DefaultCheck += "!(";4583      DefaultCheck.append(PredicateCheck);4584      DefaultCheck += ")";4585    }4586 4587    bool HasDefault = Modes.count(DefaultMode);4588    if (HasDefault)4589      AppendPattern(P, DefaultMode, DefaultCheck);4590  }4591}4592 4593/// Dependent variable map for CodeGenDAGPattern variant generation4594using DepVarMap = StringMap<int>;4595 4596static void FindDepVarsOf(TreePatternNode &N, DepVarMap &DepMap) {4597  if (N.isLeaf()) {4598    if (N.hasName() && isa<DefInit>(N.getLeafValue()))4599      DepMap[N.getName()]++;4600  } else {4601    for (TreePatternNode &Child : N.children())4602      FindDepVarsOf(Child, DepMap);4603  }4604}4605 4606/// Find dependent variables within child patterns4607static void FindDepVars(TreePatternNode &N, MultipleUseVarSet &DepVars) {4608  DepVarMap depcounts;4609  FindDepVarsOf(N, depcounts);4610  for (const auto &Pair : depcounts) {4611    if (Pair.getValue() > 1)4612      DepVars.insert(Pair.getKey());4613  }4614}4615 4616#ifndef NDEBUG4617/// Dump the dependent variable set:4618static void DumpDepVars(MultipleUseVarSet &DepVars) {4619  if (DepVars.empty()) {4620    LLVM_DEBUG(errs() << "<empty set>");4621  } else {4622    LLVM_DEBUG(errs() << "[ ");4623    for (const auto &DepVar : DepVars) {4624      LLVM_DEBUG(errs() << DepVar.getKey() << " ");4625    }4626    LLVM_DEBUG(errs() << "]");4627  }4628}4629#endif4630 4631/// CombineChildVariants - Given a bunch of permutations of each child of the4632/// 'operator' node, put them together in all possible ways.4633static void CombineChildVariants(4634    TreePatternNodePtr Orig,4635    const std::vector<std::vector<TreePatternNodePtr>> &ChildVariants,4636    std::vector<TreePatternNodePtr> &OutVariants, CodeGenDAGPatterns &CDP,4637    const MultipleUseVarSet &DepVars) {4638  // Make sure that each operand has at least one variant to choose from.4639  for (const auto &Variants : ChildVariants)4640    if (Variants.empty())4641      return;4642 4643  // The end result is an all-pairs construction of the resultant pattern.4644  std::vector<unsigned> Idxs(ChildVariants.size());4645  bool NotDone;4646  do {4647#ifndef NDEBUG4648    LLVM_DEBUG(if (!Idxs.empty()) {4649      errs() << Orig->getOperator()->getName() << ": Idxs = [ ";4650      for (unsigned Idx : Idxs) {4651        errs() << Idx << " ";4652      }4653      errs() << "]\n";4654    });4655#endif4656    // Create the variant and add it to the output list.4657    std::vector<TreePatternNodePtr> NewChildren;4658    NewChildren.reserve(ChildVariants.size());4659    for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)4660      NewChildren.push_back(ChildVariants[i][Idxs[i]]);4661    TreePatternNodePtr R = makeIntrusiveRefCnt<TreePatternNode>(4662        Orig->getOperator(), std::move(NewChildren), Orig->getNumTypes());4663 4664    // Copy over properties.4665    R->setName(Orig->getName());4666    R->setNamesAsPredicateArg(Orig->getNamesAsPredicateArg());4667    R->setPredicateCalls(Orig->getPredicateCalls());4668    R->setGISelFlagsRecord(Orig->getGISelFlagsRecord());4669    R->setTransformFn(Orig->getTransformFn());4670    for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i)4671      R->setType(i, Orig->getExtType(i));4672 4673    // If this pattern cannot match, do not include it as a variant.4674    std::string ErrString;4675    // Scan to see if this pattern has already been emitted.  We can get4676    // duplication due to things like commuting:4677    //   (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a)4678    // which are the same pattern.  Ignore the dups.4679    if (R->canPatternMatch(ErrString, CDP) &&4680        none_of(OutVariants, [&](TreePatternNodePtr Variant) {4681          return R->isIsomorphicTo(*Variant, DepVars);4682        }))4683      OutVariants.push_back(R);4684 4685    // Increment indices to the next permutation by incrementing the4686    // indices from last index backward, e.g., generate the sequence4687    // [0, 0], [0, 1], [1, 0], [1, 1].4688    int IdxsIdx;4689    for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {4690      if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size())4691        Idxs[IdxsIdx] = 0;4692      else4693        break;4694    }4695    NotDone = (IdxsIdx >= 0);4696  } while (NotDone);4697}4698 4699/// CombineChildVariants - A helper function for binary operators.4700///4701static void CombineChildVariants(TreePatternNodePtr Orig,4702                                 const std::vector<TreePatternNodePtr> &LHS,4703                                 const std::vector<TreePatternNodePtr> &RHS,4704                                 std::vector<TreePatternNodePtr> &OutVariants,4705                                 CodeGenDAGPatterns &CDP,4706                                 const MultipleUseVarSet &DepVars) {4707  std::vector<std::vector<TreePatternNodePtr>> ChildVariants;4708  ChildVariants.push_back(LHS);4709  ChildVariants.push_back(RHS);4710  CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars);4711}4712 4713static void4714GatherChildrenOfAssociativeOpcode(TreePatternNodePtr N,4715                                  std::vector<TreePatternNodePtr> &Children) {4716  assert(N->getNumChildren() == 2 &&4717         "Associative but doesn't have 2 children!");4718  const Record *Operator = N->getOperator();4719 4720  // Only permit raw nodes.4721  if (!N->getName().empty() || !N->getPredicateCalls().empty() ||4722      N->getTransformFn()) {4723    Children.push_back(N);4724    return;4725  }4726 4727  if (N->getChild(0).isLeaf() || N->getChild(0).getOperator() != Operator)4728    Children.push_back(N->getChildShared(0));4729  else4730    GatherChildrenOfAssociativeOpcode(N->getChildShared(0), Children);4731 4732  if (N->getChild(1).isLeaf() || N->getChild(1).getOperator() != Operator)4733    Children.push_back(N->getChildShared(1));4734  else4735    GatherChildrenOfAssociativeOpcode(N->getChildShared(1), Children);4736}4737 4738/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of4739/// the (potentially recursive) pattern by using algebraic laws.4740///4741static void GenerateVariantsOf(TreePatternNodePtr N,4742                               std::vector<TreePatternNodePtr> &OutVariants,4743                               CodeGenDAGPatterns &CDP,4744                               const MultipleUseVarSet &DepVars) {4745  // We cannot permute leaves or ComplexPattern uses.4746  if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) {4747    OutVariants.push_back(N);4748    return;4749  }4750 4751  // Look up interesting info about the node.4752  const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator());4753 4754  // If this node is associative, re-associate.4755  if (NodeInfo.hasProperty(SDNPAssociative)) {4756    // Re-associate by pulling together all of the linked operators4757    std::vector<TreePatternNodePtr> MaximalChildren;4758    GatherChildrenOfAssociativeOpcode(N, MaximalChildren);4759 4760    // Only handle child sizes of 3.  Otherwise we'll end up trying too many4761    // permutations.4762    if (MaximalChildren.size() == 3) {4763      // Find the variants of all of our maximal children.4764      std::vector<TreePatternNodePtr> AVariants, BVariants, CVariants;4765      GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars);4766      GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars);4767      GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars);4768 4769      // There are only two ways we can permute the tree:4770      //   (A op B) op C    and    A op (B op C)4771      // Within these forms, we can also permute A/B/C.4772 4773      // Generate legal pair permutations of A/B/C.4774      std::vector<TreePatternNodePtr> ABVariants;4775      std::vector<TreePatternNodePtr> BAVariants;4776      std::vector<TreePatternNodePtr> ACVariants;4777      std::vector<TreePatternNodePtr> CAVariants;4778      std::vector<TreePatternNodePtr> BCVariants;4779      std::vector<TreePatternNodePtr> CBVariants;4780      CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars);4781      CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars);4782      CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars);4783      CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars);4784      CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars);4785      CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars);4786 4787      // Combine those into the result: (x op x) op x4788      CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars);4789      CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars);4790      CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars);4791      CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars);4792      CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars);4793      CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars);4794 4795      // Combine those into the result: x op (x op x)4796      CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars);4797      CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars);4798      CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars);4799      CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars);4800      CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars);4801      CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars);4802      return;4803    }4804  }4805 4806  // Compute permutations of all children.4807  std::vector<std::vector<TreePatternNodePtr>> ChildVariants(4808      N->getNumChildren());4809  for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)4810    GenerateVariantsOf(N->getChildShared(i), ChildVariants[i], CDP, DepVars);4811 4812  // Build all permutations based on how the children were formed.4813  CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars);4814 4815  // If this node is commutative, consider the commuted order.4816  bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP);4817  if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {4818    unsigned Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id.4819    assert(N->getNumChildren() >= (2 + Skip) &&4820           "Commutative but doesn't have 2 children!");4821    // Don't allow commuting children which are actually register references.4822    bool NoRegisters = true;4823    unsigned i = 0 + Skip;4824    unsigned e = 2 + Skip;4825    for (; i != e; ++i) {4826      TreePatternNode &Child = N->getChild(i);4827      if (Child.isLeaf())4828        if (const DefInit *DI = dyn_cast<DefInit>(Child.getLeafValue())) {4829          const Record *RR = DI->getDef();4830          if (RR->isSubClassOf("Register"))4831            NoRegisters = false;4832        }4833    }4834    // Consider the commuted order.4835    if (NoRegisters) {4836      // Swap the first two operands after the intrinsic id, if present.4837      unsigned i = isCommIntrinsic ? 1 : 0;4838      std::swap(ChildVariants[i], ChildVariants[i + 1]);4839      CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars);4840    }4841  }4842}4843 4844// GenerateVariants - Generate variants.  For example, commutative patterns can4845// match multiple ways.  Add them to PatternsToMatch as well.4846void CodeGenDAGPatterns::GenerateVariants() {4847  LLVM_DEBUG(errs() << "Generating instruction variants.\n");4848 4849  // Loop over all of the patterns we've collected, checking to see if we can4850  // generate variants of the instruction, through the exploitation of4851  // identities.  This permits the target to provide aggressive matching without4852  // the .td file having to contain tons of variants of instructions.4853  //4854  // Note that this loop adds new patterns to the PatternsToMatch list, but we4855  // intentionally do not reconsider these.  Any variants of added patterns have4856  // already been added.4857  //4858  for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {4859    MultipleUseVarSet DepVars;4860    std::vector<TreePatternNodePtr> Variants;4861    FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars);4862    LLVM_DEBUG(errs() << "Dependent/multiply used variables: ");4863    LLVM_DEBUG(DumpDepVars(DepVars));4864    LLVM_DEBUG(errs() << "\n");4865    GenerateVariantsOf(PatternsToMatch[i].getSrcPatternShared(), Variants,4866                       *this, DepVars);4867 4868    assert(PatternsToMatch[i].getHwModeFeatures().empty() &&4869           "HwModes should not have been expanded yet!");4870 4871    assert(!Variants.empty() && "Must create at least original variant!");4872    if (Variants.size() == 1) // No additional variants for this pattern.4873      continue;4874 4875    LLVM_DEBUG(errs() << "FOUND VARIANTS OF: ";4876               PatternsToMatch[i].getSrcPattern().dump(); errs() << "\n");4877 4878    for (unsigned v = 0, e = Variants.size(); v != e; ++v) {4879      TreePatternNodePtr Variant = Variants[v];4880 4881      LLVM_DEBUG(errs() << "  VAR#" << v << ": "; Variant->dump();4882                 errs() << "\n");4883 4884      // Scan to see if an instruction or explicit pattern already matches this.4885      bool AlreadyExists = false;4886      for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {4887        // Skip if the top level predicates do not match.4888        if ((i != p) && (PatternsToMatch[i].getPredicates() !=4889                         PatternsToMatch[p].getPredicates()))4890          continue;4891        // Check to see if this variant already exists.4892        if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(),4893                                    DepVars)) {4894          LLVM_DEBUG(errs() << "  *** ALREADY EXISTS, ignoring variant.\n");4895          AlreadyExists = true;4896          break;4897        }4898      }4899      // If we already have it, ignore the variant.4900      if (AlreadyExists)4901        continue;4902 4903      // Otherwise, add it to the list of patterns we have.4904      PatternsToMatch.emplace_back(4905          PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(),4906          Variant, PatternsToMatch[i].getDstPatternShared(),4907          PatternsToMatch[i].getDstRegs(),4908          PatternsToMatch[i].getAddedComplexity(), getNewUID(),4909          PatternsToMatch[i].getGISelShouldIgnore(),4910          PatternsToMatch[i].getHwModeFeatures());4911    }4912 4913    LLVM_DEBUG(errs() << "\n");4914  }4915}4916 4917unsigned CodeGenDAGPatterns::getNewUID() {4918  RecordKeeper &MutableRC = const_cast<RecordKeeper &>(Records);4919  return Record::getNewUID(MutableRC);4920}4921