1193323Sed//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements the CodeGenDAGPatterns class, which is used to read and 10193323Sed// represent the patterns present in a .td file for instructions. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#include "CodeGenDAGPatterns.h" 15344779Sdim#include "llvm/ADT/BitVector.h" 16327952Sdim#include "llvm/ADT/DenseSet.h" 17344779Sdim#include "llvm/ADT/MapVector.h" 18249423Sdim#include "llvm/ADT/STLExtras.h" 19327952Sdim#include "llvm/ADT/SmallSet.h" 20296417Sdim#include "llvm/ADT/SmallString.h" 21193323Sed#include "llvm/ADT/StringExtras.h" 22327952Sdim#include "llvm/ADT/StringMap.h" 23234982Sdim#include "llvm/ADT/Twine.h" 24193323Sed#include "llvm/Support/Debug.h" 25234353Sdim#include "llvm/Support/ErrorHandling.h" 26360784Sdim#include "llvm/Support/TypeSize.h" 27249423Sdim#include "llvm/TableGen/Error.h" 28249423Sdim#include "llvm/TableGen/Record.h" 29234353Sdim#include <algorithm> 30234353Sdim#include <cstdio> 31344779Sdim#include <iterator> 32193323Sed#include <set> 33193323Sedusing namespace llvm; 34193323Sed 35276479Sdim#define DEBUG_TYPE "dag-patterns" 36276479Sdim 37327952Sdimstatic inline bool isIntegerOrPtr(MVT VT) { 38327952Sdim return VT.isInteger() || VT == MVT::iPTR; 39193323Sed} 40327952Sdimstatic inline bool isFloatingPoint(MVT VT) { 41327952Sdim return VT.isFloatingPoint(); 42193323Sed} 43327952Sdimstatic inline bool isVector(MVT VT) { 44327952Sdim return VT.isVector(); 45193323Sed} 46327952Sdimstatic inline bool isScalar(MVT VT) { 47327952Sdim return !VT.isVector(); 48205407Srdivacky} 49193323Sed 50327952Sdimtemplate <typename Predicate> 51327952Sdimstatic bool berase_if(MachineValueTypeSet &S, Predicate P) { 52327952Sdim bool Erased = false; 53327952Sdim // It is ok to iterate over MachineValueTypeSet and remove elements from it 54327952Sdim // at the same time. 55327952Sdim for (MVT T : S) { 56327952Sdim if (!P(T)) 57327952Sdim continue; 58327952Sdim Erased = true; 59327952Sdim S.erase(T); 60205218Srdivacky } 61327952Sdim return Erased; 62193323Sed} 63193323Sed 64327952Sdim// --- TypeSetByHwMode 65205218Srdivacky 66327952Sdim// This is a parameterized type-set class. For each mode there is a list 67327952Sdim// of types that are currently possible for a given tree node. Type 68327952Sdim// inference will apply to each mode separately. 69218893Sdim 70327952SdimTypeSetByHwMode::TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList) { 71353358Sdim for (const ValueTypeByHwMode &VVT : VTList) { 72327952Sdim insert(VVT); 73353358Sdim AddrSpaces.push_back(VVT.PtrAddrSpace); 74353358Sdim } 75327952Sdim} 76218893Sdim 77327952Sdimbool TypeSetByHwMode::isValueTypeByHwMode(bool AllowEmpty) const { 78327952Sdim for (const auto &I : *this) { 79327952Sdim if (I.second.size() > 1) 80327952Sdim return false; 81327952Sdim if (!AllowEmpty && I.second.empty()) 82327952Sdim return false; 83327952Sdim } 84327952Sdim return true; 85193323Sed} 86193323Sed 87327952SdimValueTypeByHwMode TypeSetByHwMode::getValueTypeByHwMode() const { 88327952Sdim assert(isValueTypeByHwMode(true) && 89327952Sdim "The type set has multiple types for at least one HW mode"); 90327952Sdim ValueTypeByHwMode VVT; 91353358Sdim auto ASI = AddrSpaces.begin(); 92353358Sdim 93327952Sdim for (const auto &I : *this) { 94327952Sdim MVT T = I.second.empty() ? MVT::Other : *I.second.begin(); 95327952Sdim VVT.getOrCreateTypeForMode(I.first, T); 96353358Sdim if (ASI != AddrSpaces.end()) 97353358Sdim VVT.PtrAddrSpace = *ASI++; 98327952Sdim } 99327952Sdim return VVT; 100327952Sdim} 101218893Sdim 102327952Sdimbool TypeSetByHwMode::isPossible() const { 103327952Sdim for (const auto &I : *this) 104327952Sdim if (!I.second.empty()) 105327952Sdim return true; 106327952Sdim return false; 107327952Sdim} 108243830Sdim 109327952Sdimbool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) { 110327952Sdim bool Changed = false; 111344779Sdim bool ContainsDefault = false; 112344779Sdim MVT DT = MVT::Other; 113344779Sdim 114327952Sdim SmallDenseSet<unsigned, 4> Modes; 115327952Sdim for (const auto &P : VVT) { 116327952Sdim unsigned M = P.first; 117327952Sdim Modes.insert(M); 118327952Sdim // Make sure there exists a set for each specific mode from VVT. 119327952Sdim Changed |= getOrCreate(M).insert(P.second).second; 120344779Sdim // Cache VVT's default mode. 121344779Sdim if (DefaultMode == M) { 122344779Sdim ContainsDefault = true; 123344779Sdim DT = P.second; 124344779Sdim } 125327952Sdim } 126205218Srdivacky 127327952Sdim // If VVT has a default mode, add the corresponding type to all 128327952Sdim // modes in "this" that do not exist in VVT. 129344779Sdim if (ContainsDefault) 130327952Sdim for (auto &I : *this) 131327952Sdim if (!Modes.count(I.first)) 132327952Sdim Changed |= I.second.insert(DT).second; 133344779Sdim 134327952Sdim return Changed; 135327952Sdim} 136205407Srdivacky 137327952Sdim// Constrain the type set to be the intersection with VTS. 138327952Sdimbool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) { 139327952Sdim bool Changed = false; 140327952Sdim if (hasDefault()) { 141327952Sdim for (const auto &I : VTS) { 142327952Sdim unsigned M = I.first; 143327952Sdim if (M == DefaultMode || hasMode(M)) 144327952Sdim continue; 145327952Sdim Map.insert({M, Map.at(DefaultMode)}); 146327952Sdim Changed = true; 147327952Sdim } 148327952Sdim } 149218893Sdim 150327952Sdim for (auto &I : *this) { 151327952Sdim unsigned M = I.first; 152327952Sdim SetType &S = I.second; 153327952Sdim if (VTS.hasMode(M) || VTS.hasDefault()) { 154327952Sdim Changed |= intersect(I.second, VTS.get(M)); 155327952Sdim } else if (!S.empty()) { 156327952Sdim S.clear(); 157327952Sdim Changed = true; 158327952Sdim } 159327952Sdim } 160327952Sdim return Changed; 161205407Srdivacky} 162205407Srdivacky 163327952Sdimtemplate <typename Predicate> 164327952Sdimbool TypeSetByHwMode::constrain(Predicate P) { 165327952Sdim bool Changed = false; 166327952Sdim for (auto &I : *this) 167327952Sdim Changed |= berase_if(I.second, [&P](MVT VT) { return !P(VT); }); 168327952Sdim return Changed; 169218893Sdim} 170205218Srdivacky 171327952Sdimtemplate <typename Predicate> 172327952Sdimbool TypeSetByHwMode::assign_if(const TypeSetByHwMode &VTS, Predicate P) { 173327952Sdim assert(empty()); 174327952Sdim for (const auto &I : VTS) { 175327952Sdim SetType &S = getOrCreate(I.first); 176327952Sdim for (auto J : I.second) 177327952Sdim if (P(J)) 178327952Sdim S.insert(J); 179327952Sdim } 180327952Sdim return !empty(); 181218893Sdim} 182205218Srdivacky 183327952Sdimvoid TypeSetByHwMode::writeToStream(raw_ostream &OS) const { 184327952Sdim SmallVector<unsigned, 4> Modes; 185327952Sdim Modes.reserve(Map.size()); 186327952Sdim 187327952Sdim for (const auto &I : *this) 188327952Sdim Modes.push_back(I.first); 189327952Sdim if (Modes.empty()) { 190327952Sdim OS << "{}"; 191327952Sdim return; 192327952Sdim } 193327952Sdim array_pod_sort(Modes.begin(), Modes.end()); 194327952Sdim 195327952Sdim OS << '{'; 196327952Sdim for (unsigned M : Modes) { 197327952Sdim OS << ' ' << getModeName(M) << ':'; 198327952Sdim writeToStream(get(M), OS); 199327952Sdim } 200327952Sdim OS << " }"; 201276479Sdim} 202276479Sdim 203327952Sdimvoid TypeSetByHwMode::writeToStream(const SetType &S, raw_ostream &OS) { 204327952Sdim SmallVector<MVT, 4> Types(S.begin(), S.end()); 205327952Sdim array_pod_sort(Types.begin(), Types.end()); 206327952Sdim 207327952Sdim OS << '['; 208327952Sdim for (unsigned i = 0, e = Types.size(); i != e; ++i) { 209327952Sdim OS << ValueTypeByHwMode::getMVTName(Types[i]); 210327952Sdim if (i != e-1) 211327952Sdim OS << ' '; 212327952Sdim } 213327952Sdim OS << ']'; 214193323Sed} 215198090Srdivacky 216327952Sdimbool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const { 217344779Sdim // The isSimple call is much quicker than hasDefault - check this first. 218344779Sdim bool IsSimple = isSimple(); 219344779Sdim bool VTSIsSimple = VTS.isSimple(); 220344779Sdim if (IsSimple && VTSIsSimple) 221344779Sdim return *begin() == *VTS.begin(); 222205218Srdivacky 223344779Sdim // Speedup: We have a default if the set is simple. 224344779Sdim bool HaveDefault = IsSimple || hasDefault(); 225344779Sdim bool VTSHaveDefault = VTSIsSimple || VTS.hasDefault(); 226344779Sdim if (HaveDefault != VTSHaveDefault) 227327952Sdim return false; 228218893Sdim 229327952Sdim SmallDenseSet<unsigned, 4> Modes; 230327952Sdim for (auto &I : *this) 231327952Sdim Modes.insert(I.first); 232327952Sdim for (const auto &I : VTS) 233327952Sdim Modes.insert(I.first); 234218893Sdim 235327952Sdim if (HaveDefault) { 236327952Sdim // Both sets have default mode. 237327952Sdim for (unsigned M : Modes) { 238327952Sdim if (get(M) != VTS.get(M)) 239327952Sdim return false; 240327952Sdim } 241327952Sdim } else { 242327952Sdim // Neither set has default mode. 243327952Sdim for (unsigned M : Modes) { 244327952Sdim // If there is no default mode, an empty set is equivalent to not having 245327952Sdim // the corresponding mode. 246327952Sdim bool NoModeThis = !hasMode(M) || get(M).empty(); 247327952Sdim bool NoModeVTS = !VTS.hasMode(M) || VTS.get(M).empty(); 248327952Sdim if (NoModeThis != NoModeVTS) 249327952Sdim return false; 250327952Sdim if (!NoModeThis) 251327952Sdim if (get(M) != VTS.get(M)) 252327952Sdim return false; 253327952Sdim } 254205218Srdivacky } 255218893Sdim 256327952Sdim return true; 257198090Srdivacky} 258193323Sed 259327952Sdimnamespace llvm { 260327952Sdim raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T) { 261327952Sdim T.writeToStream(OS); 262327952Sdim return OS; 263205218Srdivacky } 264327952Sdim} 265218893Sdim 266327952SdimLLVM_DUMP_METHOD 267327952Sdimvoid TypeSetByHwMode::dump() const { 268327952Sdim dbgs() << *this << '\n'; 269327952Sdim} 270218893Sdim 271327952Sdimbool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) { 272327952Sdim bool OutP = Out.count(MVT::iPTR), InP = In.count(MVT::iPTR); 273327952Sdim auto Int = [&In](MVT T) -> bool { return !In.count(T); }; 274218893Sdim 275327952Sdim if (OutP == InP) 276327952Sdim return berase_if(Out, Int); 277218893Sdim 278327952Sdim // Compute the intersection of scalars separately to account for only 279327952Sdim // one set containing iPTR. 280327952Sdim // The itersection of iPTR with a set of integer scalar types that does not 281327952Sdim // include iPTR will result in the most specific scalar type: 282327952Sdim // - iPTR is more specific than any set with two elements or more 283327952Sdim // - iPTR is less specific than any single integer scalar type. 284327952Sdim // For example 285327952Sdim // { iPTR } * { i32 } -> { i32 } 286327952Sdim // { iPTR } * { i32 i64 } -> { iPTR } 287327952Sdim // and 288327952Sdim // { iPTR i32 } * { i32 } -> { i32 } 289327952Sdim // { iPTR i32 } * { i32 i64 } -> { i32 i64 } 290327952Sdim // { iPTR i32 } * { i32 i64 i128 } -> { iPTR i32 } 291327952Sdim 292327952Sdim // Compute the difference between the two sets in such a way that the 293327952Sdim // iPTR is in the set that is being subtracted. This is to see if there 294327952Sdim // are any extra scalars in the set without iPTR that are not in the 295327952Sdim // set containing iPTR. Then the iPTR could be considered a "wildcard" 296327952Sdim // matching these scalars. If there is only one such scalar, it would 297327952Sdim // replace the iPTR, if there are more, the iPTR would be retained. 298327952Sdim SetType Diff; 299327952Sdim if (InP) { 300327952Sdim Diff = Out; 301327952Sdim berase_if(Diff, [&In](MVT T) { return In.count(T); }); 302327952Sdim // Pre-remove these elements and rely only on InP/OutP to determine 303327952Sdim // whether a change has been made. 304327952Sdim berase_if(Out, [&Diff](MVT T) { return Diff.count(T); }); 305327952Sdim } else { 306327952Sdim Diff = In; 307327952Sdim berase_if(Diff, [&Out](MVT T) { return Out.count(T); }); 308327952Sdim Out.erase(MVT::iPTR); 309205218Srdivacky } 310218893Sdim 311327952Sdim // The actual intersection. 312327952Sdim bool Changed = berase_if(Out, Int); 313327952Sdim unsigned NumD = Diff.size(); 314327952Sdim if (NumD == 0) 315327952Sdim return Changed; 316218893Sdim 317327952Sdim if (NumD == 1) { 318327952Sdim Out.insert(*Diff.begin()); 319327952Sdim // This is a change only if Out was the one with iPTR (which is now 320327952Sdim // being replaced). 321327952Sdim Changed |= OutP; 322327952Sdim } else { 323327952Sdim // Multiple elements from Out are now replaced with iPTR. 324327952Sdim Out.insert(MVT::iPTR); 325327952Sdim Changed |= !OutP; 326205218Srdivacky } 327327952Sdim return Changed; 328327952Sdim} 329218893Sdim 330327952Sdimbool TypeSetByHwMode::validate() const { 331327952Sdim#ifndef NDEBUG 332327952Sdim if (empty()) 333327952Sdim return true; 334327952Sdim bool AllEmpty = true; 335327952Sdim for (const auto &I : *this) 336327952Sdim AllEmpty &= I.second.empty(); 337327952Sdim return !AllEmpty; 338327952Sdim#endif 339327952Sdim return true; 340327952Sdim} 341205218Srdivacky 342327952Sdim// --- TypeInfer 343218893Sdim 344327952Sdimbool TypeInfer::MergeInTypeInfo(TypeSetByHwMode &Out, 345327952Sdim const TypeSetByHwMode &In) { 346327952Sdim ValidateOnExit _1(Out, *this); 347327952Sdim In.validate(); 348327952Sdim if (In.empty() || Out == In || TP.hasError()) 349296417Sdim return false; 350327952Sdim if (Out.empty()) { 351327952Sdim Out = In; 352296417Sdim return true; 353327952Sdim } 354218893Sdim 355327952Sdim bool Changed = Out.constrain(In); 356327952Sdim if (Changed && Out.empty()) 357327952Sdim TP.error("Type contradiction"); 358327952Sdim 359327952Sdim return Changed; 360205218Srdivacky} 361205218Srdivacky 362327952Sdimbool TypeInfer::forceArbitrary(TypeSetByHwMode &Out) { 363327952Sdim ValidateOnExit _1(Out, *this); 364243830Sdim if (TP.hasError()) 365243830Sdim return false; 366327952Sdim assert(!Out.empty() && "cannot pick from an empty set"); 367296417Sdim 368327952Sdim bool Changed = false; 369327952Sdim for (auto &I : Out) { 370327952Sdim TypeSetByHwMode::SetType &S = I.second; 371327952Sdim if (S.size() <= 1) 372327952Sdim continue; 373327952Sdim MVT T = *S.begin(); // Pick the first element. 374327952Sdim S.clear(); 375327952Sdim S.insert(T); 376327952Sdim Changed = true; 377327952Sdim } 378327952Sdim return Changed; 379327952Sdim} 380327952Sdim 381327952Sdimbool TypeInfer::EnforceInteger(TypeSetByHwMode &Out) { 382327952Sdim ValidateOnExit _1(Out, *this); 383327952Sdim if (TP.hasError()) 384205407Srdivacky return false; 385327952Sdim if (!Out.empty()) 386327952Sdim return Out.constrain(isIntegerOrPtr); 387205407Srdivacky 388327952Sdim return Out.assign_if(getLegalTypes(), isIntegerOrPtr); 389327952Sdim} 390218893Sdim 391327952Sdimbool TypeInfer::EnforceFloatingPoint(TypeSetByHwMode &Out) { 392327952Sdim ValidateOnExit _1(Out, *this); 393327952Sdim if (TP.hasError()) 394327952Sdim return false; 395327952Sdim if (!Out.empty()) 396327952Sdim return Out.constrain(isFloatingPoint); 397218893Sdim 398327952Sdim return Out.assign_if(getLegalTypes(), isFloatingPoint); 399327952Sdim} 400327952Sdim 401327952Sdimbool TypeInfer::EnforceScalar(TypeSetByHwMode &Out) { 402327952Sdim ValidateOnExit _1(Out, *this); 403327952Sdim if (TP.hasError()) 404243830Sdim return false; 405327952Sdim if (!Out.empty()) 406327952Sdim return Out.constrain(isScalar); 407327952Sdim 408327952Sdim return Out.assign_if(getLegalTypes(), isScalar); 409205218Srdivacky} 410205218Srdivacky 411327952Sdimbool TypeInfer::EnforceVector(TypeSetByHwMode &Out) { 412327952Sdim ValidateOnExit _1(Out, *this); 413243830Sdim if (TP.hasError()) 414243830Sdim return false; 415327952Sdim if (!Out.empty()) 416327952Sdim return Out.constrain(isVector); 417205407Srdivacky 418327952Sdim return Out.assign_if(getLegalTypes(), isVector); 419327952Sdim} 420327952Sdim 421327952Sdimbool TypeInfer::EnforceAny(TypeSetByHwMode &Out) { 422327952Sdim ValidateOnExit _1(Out, *this); 423327952Sdim if (TP.hasError() || !Out.empty()) 424205407Srdivacky return false; 425205407Srdivacky 426327952Sdim Out = getLegalTypes(); 427327952Sdim return true; 428327952Sdim} 429218893Sdim 430327952Sdimtemplate <typename Iter, typename Pred, typename Less> 431327952Sdimstatic Iter min_if(Iter B, Iter E, Pred P, Less L) { 432327952Sdim if (B == E) 433327952Sdim return E; 434327952Sdim Iter Min = E; 435327952Sdim for (Iter I = B; I != E; ++I) { 436327952Sdim if (!P(*I)) 437327952Sdim continue; 438327952Sdim if (Min == E || L(*I, *Min)) 439327952Sdim Min = I; 440327952Sdim } 441327952Sdim return Min; 442327952Sdim} 443218893Sdim 444327952Sdimtemplate <typename Iter, typename Pred, typename Less> 445327952Sdimstatic Iter max_if(Iter B, Iter E, Pred P, Less L) { 446327952Sdim if (B == E) 447327952Sdim return E; 448327952Sdim Iter Max = E; 449327952Sdim for (Iter I = B; I != E; ++I) { 450327952Sdim if (!P(*I)) 451327952Sdim continue; 452327952Sdim if (Max == E || L(*Max, *I)) 453327952Sdim Max = I; 454243830Sdim } 455327952Sdim return Max; 456205218Srdivacky} 457205218Srdivacky 458327952Sdim/// Make sure that for each type in Small, there exists a larger type in Big. 459327952Sdimbool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small, 460327952Sdim TypeSetByHwMode &Big) { 461327952Sdim ValidateOnExit _1(Small, *this), _2(Big, *this); 462243830Sdim if (TP.hasError()) 463243830Sdim return false; 464327952Sdim bool Changed = false; 465243830Sdim 466327952Sdim if (Small.empty()) 467327952Sdim Changed |= EnforceAny(Small); 468327952Sdim if (Big.empty()) 469327952Sdim Changed |= EnforceAny(Big); 470205407Srdivacky 471327952Sdim assert(Small.hasDefault() && Big.hasDefault()); 472205407Srdivacky 473327952Sdim std::vector<unsigned> Modes = union_modes(Small, Big); 474218893Sdim 475327952Sdim // 1. Only allow integer or floating point types and make sure that 476327952Sdim // both sides are both integer or both floating point. 477327952Sdim // 2. Make sure that either both sides have vector types, or neither 478327952Sdim // of them does. 479327952Sdim for (unsigned M : Modes) { 480327952Sdim TypeSetByHwMode::SetType &S = Small.get(M); 481327952Sdim TypeSetByHwMode::SetType &B = Big.get(M); 482218893Sdim 483327952Sdim if (any_of(S, isIntegerOrPtr) && any_of(S, isIntegerOrPtr)) { 484327952Sdim auto NotInt = [](MVT VT) { return !isIntegerOrPtr(VT); }; 485360784Sdim Changed |= berase_if(S, NotInt); 486360784Sdim Changed |= berase_if(B, NotInt); 487327952Sdim } else if (any_of(S, isFloatingPoint) && any_of(B, isFloatingPoint)) { 488327952Sdim auto NotFP = [](MVT VT) { return !isFloatingPoint(VT); }; 489360784Sdim Changed |= berase_if(S, NotFP); 490360784Sdim Changed |= berase_if(B, NotFP); 491327952Sdim } else if (S.empty() || B.empty()) { 492327952Sdim Changed = !S.empty() || !B.empty(); 493327952Sdim S.clear(); 494327952Sdim B.clear(); 495327952Sdim } else { 496327952Sdim TP.error("Incompatible types"); 497327952Sdim return Changed; 498327952Sdim } 499327952Sdim 500327952Sdim if (none_of(S, isVector) || none_of(B, isVector)) { 501360784Sdim Changed |= berase_if(S, isVector); 502360784Sdim Changed |= berase_if(B, isVector); 503327952Sdim } 504243830Sdim } 505205218Srdivacky 506327952Sdim auto LT = [](MVT A, MVT B) -> bool { 507360784Sdim // Always treat non-scalable MVTs as smaller than scalable MVTs for the 508360784Sdim // purposes of ordering. 509360784Sdim auto ASize = std::make_tuple(A.isScalableVector(), A.getScalarSizeInBits(), 510360784Sdim A.getSizeInBits()); 511360784Sdim auto BSize = std::make_tuple(B.isScalableVector(), B.getScalarSizeInBits(), 512360784Sdim B.getSizeInBits()); 513360784Sdim return ASize < BSize; 514327952Sdim }; 515360784Sdim auto SameKindLE = [](MVT A, MVT B) -> bool { 516327952Sdim // This function is used when removing elements: when a vector is compared 517360784Sdim // to a non-vector or a scalable vector to any non-scalable MVT, it should 518360784Sdim // return false (to avoid removal). 519360784Sdim if (std::make_tuple(A.isVector(), A.isScalableVector()) != 520360784Sdim std::make_tuple(B.isVector(), B.isScalableVector())) 521327952Sdim return false; 522243830Sdim 523360784Sdim return std::make_tuple(A.getScalarSizeInBits(), A.getSizeInBits()) <= 524360784Sdim std::make_tuple(B.getScalarSizeInBits(), B.getSizeInBits()); 525327952Sdim }; 526205407Srdivacky 527327952Sdim for (unsigned M : Modes) { 528327952Sdim TypeSetByHwMode::SetType &S = Small.get(M); 529327952Sdim TypeSetByHwMode::SetType &B = Big.get(M); 530327952Sdim // MinS = min scalar in Small, remove all scalars from Big that are 531327952Sdim // smaller-or-equal than MinS. 532327952Sdim auto MinS = min_if(S.begin(), S.end(), isScalar, LT); 533327952Sdim if (MinS != S.end()) 534360784Sdim Changed |= berase_if(B, std::bind(SameKindLE, 535360784Sdim std::placeholders::_1, *MinS)); 536218893Sdim 537327952Sdim // MaxS = max scalar in Big, remove all scalars from Small that are 538327952Sdim // larger than MaxS. 539327952Sdim auto MaxS = max_if(B.begin(), B.end(), isScalar, LT); 540327952Sdim if (MaxS != B.end()) 541360784Sdim Changed |= berase_if(S, std::bind(SameKindLE, 542360784Sdim *MaxS, std::placeholders::_1)); 543218893Sdim 544327952Sdim // MinV = min vector in Small, remove all vectors from Big that are 545327952Sdim // smaller-or-equal than MinV. 546327952Sdim auto MinV = min_if(S.begin(), S.end(), isVector, LT); 547327952Sdim if (MinV != S.end()) 548360784Sdim Changed |= berase_if(B, std::bind(SameKindLE, 549360784Sdim std::placeholders::_1, *MinV)); 550327952Sdim 551327952Sdim // MaxV = max vector in Big, remove all vectors from Small that are 552327952Sdim // larger than MaxV. 553327952Sdim auto MaxV = max_if(B.begin(), B.end(), isVector, LT); 554327952Sdim if (MaxV != B.end()) 555360784Sdim Changed |= berase_if(S, std::bind(SameKindLE, 556360784Sdim *MaxV, std::placeholders::_1)); 557243830Sdim } 558327952Sdim 559327952Sdim return Changed; 560205218Srdivacky} 561205218Srdivacky 562327952Sdim/// 1. Ensure that for each type T in Vec, T is a vector type, and that 563327952Sdim/// for each type U in Elem, U is a scalar type. 564327952Sdim/// 2. Ensure that for each (scalar) type U in Elem, there exists a (vector) 565327952Sdim/// type T in Vec, such that U is the element type of T. 566327952Sdimbool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, 567327952Sdim TypeSetByHwMode &Elem) { 568327952Sdim ValidateOnExit _1(Vec, *this), _2(Elem, *this); 569243830Sdim if (TP.hasError()) 570243830Sdim return false; 571327952Sdim bool Changed = false; 572243830Sdim 573327952Sdim if (Vec.empty()) 574327952Sdim Changed |= EnforceVector(Vec); 575327952Sdim if (Elem.empty()) 576327952Sdim Changed |= EnforceScalar(Elem); 577218893Sdim 578327952Sdim for (unsigned M : union_modes(Vec, Elem)) { 579327952Sdim TypeSetByHwMode::SetType &V = Vec.get(M); 580327952Sdim TypeSetByHwMode::SetType &E = Elem.get(M); 581205407Srdivacky 582327952Sdim Changed |= berase_if(V, isScalar); // Scalar = !vector 583327952Sdim Changed |= berase_if(E, isVector); // Vector = !scalar 584327952Sdim assert(!V.empty() && !E.empty()); 585218893Sdim 586327952Sdim SmallSet<MVT,4> VT, ST; 587327952Sdim // Collect element types from the "vector" set. 588327952Sdim for (MVT T : V) 589327952Sdim VT.insert(T.getVectorElementType()); 590327952Sdim // Collect scalar types from the "element" set. 591327952Sdim for (MVT T : E) 592327952Sdim ST.insert(T); 593218893Sdim 594327952Sdim // Remove from V all (vector) types whose element type is not in S. 595327952Sdim Changed |= berase_if(V, [&ST](MVT T) -> bool { 596327952Sdim return !ST.count(T.getVectorElementType()); 597327952Sdim }); 598327952Sdim // Remove from E all (scalar) types, for which there is no corresponding 599327952Sdim // type in V. 600327952Sdim Changed |= berase_if(E, [&VT](MVT T) -> bool { return !VT.count(T); }); 601327952Sdim } 602218893Sdim 603327952Sdim return Changed; 604327952Sdim} 605218893Sdim 606327952Sdimbool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, 607327952Sdim const ValueTypeByHwMode &VVT) { 608327952Sdim TypeSetByHwMode Tmp(VVT); 609327952Sdim ValidateOnExit _1(Vec, *this), _2(Tmp, *this); 610327952Sdim return EnforceVectorEltTypeIs(Vec, Tmp); 611327952Sdim} 612276479Sdim 613327952Sdim/// Ensure that for each type T in Sub, T is a vector type, and there 614327952Sdim/// exists a type U in Vec such that U is a vector type with the same 615327952Sdim/// element type as T and at least as many elements as T. 616327952Sdimbool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec, 617327952Sdim TypeSetByHwMode &Sub) { 618327952Sdim ValidateOnExit _1(Vec, *this), _2(Sub, *this); 619276479Sdim if (TP.hasError()) 620243830Sdim return false; 621218893Sdim 622327952Sdim /// Return true if B is a suB-vector of P, i.e. P is a suPer-vector of B. 623327952Sdim auto IsSubVec = [](MVT B, MVT P) -> bool { 624327952Sdim if (!B.isVector() || !P.isVector()) 625327952Sdim return false; 626327952Sdim // Logically a <4 x i32> is a valid subvector of <n x 4 x i32> 627327952Sdim // but until there are obvious use-cases for this, keep the 628327952Sdim // types separate. 629327952Sdim if (B.isScalableVector() != P.isScalableVector()) 630327952Sdim return false; 631327952Sdim if (B.getVectorElementType() != P.getVectorElementType()) 632327952Sdim return false; 633327952Sdim return B.getVectorNumElements() < P.getVectorNumElements(); 634327952Sdim }; 635296417Sdim 636327952Sdim /// Return true if S has no element (vector type) that T is a sub-vector of, 637327952Sdim /// i.e. has the same element type as T and more elements. 638327952Sdim auto NoSubV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool { 639360784Sdim for (auto I : S) 640327952Sdim if (IsSubVec(T, I)) 641314564Sdim return false; 642327952Sdim return true; 643327952Sdim }; 644296417Sdim 645327952Sdim /// Return true if S has no element (vector type) that T is a super-vector 646327952Sdim /// of, i.e. has the same element type as T and fewer elements. 647327952Sdim auto NoSupV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool { 648360784Sdim for (auto I : S) 649327952Sdim if (IsSubVec(I, T)) 650314564Sdim return false; 651327952Sdim return true; 652327952Sdim }; 653296417Sdim 654327952Sdim bool Changed = false; 655218893Sdim 656327952Sdim if (Vec.empty()) 657327952Sdim Changed |= EnforceVector(Vec); 658327952Sdim if (Sub.empty()) 659327952Sdim Changed |= EnforceVector(Sub); 660205218Srdivacky 661327952Sdim for (unsigned M : union_modes(Vec, Sub)) { 662327952Sdim TypeSetByHwMode::SetType &S = Sub.get(M); 663327952Sdim TypeSetByHwMode::SetType &V = Vec.get(M); 664288943Sdim 665327952Sdim Changed |= berase_if(S, isScalar); 666288943Sdim 667327952Sdim // Erase all types from S that are not sub-vectors of a type in V. 668327952Sdim Changed |= berase_if(S, std::bind(NoSubV, V, std::placeholders::_1)); 669288943Sdim 670327952Sdim // Erase all types from V that are not super-vectors of a type in S. 671327952Sdim Changed |= berase_if(V, std::bind(NoSupV, S, std::placeholders::_1)); 672288943Sdim } 673288943Sdim 674327952Sdim return Changed; 675288943Sdim} 676288943Sdim 677327952Sdim/// 1. Ensure that V has a scalar type iff W has a scalar type. 678327952Sdim/// 2. Ensure that for each vector type T in V, there exists a vector 679327952Sdim/// type U in W, such that T and U have the same number of elements. 680327952Sdim/// 3. Ensure that for each vector type U in W, there exists a vector 681327952Sdim/// type T in V, such that T and U have the same number of elements 682327952Sdim/// (reverse of 2). 683327952Sdimbool TypeInfer::EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W) { 684327952Sdim ValidateOnExit _1(V, *this), _2(W, *this); 685243830Sdim if (TP.hasError()) 686243830Sdim return false; 687243830Sdim 688327952Sdim bool Changed = false; 689327952Sdim if (V.empty()) 690327952Sdim Changed |= EnforceAny(V); 691327952Sdim if (W.empty()) 692327952Sdim Changed |= EnforceAny(W); 693206083Srdivacky 694327952Sdim // An actual vector type cannot have 0 elements, so we can treat scalars 695327952Sdim // as zero-length vectors. This way both vectors and scalars can be 696327952Sdim // processed identically. 697327952Sdim auto NoLength = [](const SmallSet<unsigned,2> &Lengths, MVT T) -> bool { 698327952Sdim return !Lengths.count(T.isVector() ? T.getVectorNumElements() : 0); 699327952Sdim }; 700206083Srdivacky 701327952Sdim for (unsigned M : union_modes(V, W)) { 702327952Sdim TypeSetByHwMode::SetType &VS = V.get(M); 703327952Sdim TypeSetByHwMode::SetType &WS = W.get(M); 704218893Sdim 705327952Sdim SmallSet<unsigned,2> VN, WN; 706327952Sdim for (MVT T : VS) 707327952Sdim VN.insert(T.isVector() ? T.getVectorNumElements() : 0); 708327952Sdim for (MVT T : WS) 709327952Sdim WN.insert(T.isVector() ? T.getVectorNumElements() : 0); 710218893Sdim 711327952Sdim Changed |= berase_if(VS, std::bind(NoLength, WN, std::placeholders::_1)); 712327952Sdim Changed |= berase_if(WS, std::bind(NoLength, VN, std::placeholders::_1)); 713327952Sdim } 714327952Sdim return Changed; 715205218Srdivacky} 716205218Srdivacky 717327952Sdim/// 1. Ensure that for each type T in A, there exists a type U in B, 718327952Sdim/// such that T and U have equal size in bits. 719327952Sdim/// 2. Ensure that for each type U in B, there exists a type T in A 720327952Sdim/// such that T and U have equal size in bits (reverse of 1). 721327952Sdimbool TypeInfer::EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B) { 722327952Sdim ValidateOnExit _1(A, *this), _2(B, *this); 723276479Sdim if (TP.hasError()) 724276479Sdim return false; 725327952Sdim bool Changed = false; 726327952Sdim if (A.empty()) 727327952Sdim Changed |= EnforceAny(A); 728327952Sdim if (B.empty()) 729327952Sdim Changed |= EnforceAny(B); 730276479Sdim 731327952Sdim auto NoSize = [](const SmallSet<unsigned,2> &Sizes, MVT T) -> bool { 732327952Sdim return !Sizes.count(T.getSizeInBits()); 733327952Sdim }; 734218893Sdim 735327952Sdim for (unsigned M : union_modes(A, B)) { 736327952Sdim TypeSetByHwMode::SetType &AS = A.get(M); 737327952Sdim TypeSetByHwMode::SetType &BS = B.get(M); 738327952Sdim SmallSet<unsigned,2> AN, BN; 739218893Sdim 740327952Sdim for (MVT T : AS) 741327952Sdim AN.insert(T.getSizeInBits()); 742327952Sdim for (MVT T : BS) 743327952Sdim BN.insert(T.getSizeInBits()); 744276479Sdim 745327952Sdim Changed |= berase_if(AS, std::bind(NoSize, BN, std::placeholders::_1)); 746327952Sdim Changed |= berase_if(BS, std::bind(NoSize, AN, std::placeholders::_1)); 747327952Sdim } 748218893Sdim 749327952Sdim return Changed; 750327952Sdim} 751276479Sdim 752327952Sdimvoid TypeInfer::expandOverloads(TypeSetByHwMode &VTS) { 753327952Sdim ValidateOnExit _1(VTS, *this); 754344779Sdim const TypeSetByHwMode &Legal = getLegalTypes(); 755344779Sdim assert(Legal.isDefaultOnly() && "Default-mode only expected"); 756344779Sdim const TypeSetByHwMode::SetType &LegalTypes = Legal.get(DefaultMode); 757276479Sdim 758344779Sdim for (auto &I : VTS) 759344779Sdim expandOverloads(I.second, LegalTypes); 760327952Sdim} 761218893Sdim 762327952Sdimvoid TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out, 763327952Sdim const TypeSetByHwMode::SetType &Legal) { 764327952Sdim std::set<MVT> Ovs; 765327952Sdim for (MVT T : Out) { 766327952Sdim if (!T.isOverloaded()) 767327952Sdim continue; 768276479Sdim 769327952Sdim Ovs.insert(T); 770327952Sdim // MachineValueTypeSet allows iteration and erasing. 771327952Sdim Out.erase(T); 772327952Sdim } 773276479Sdim 774327952Sdim for (MVT Ov : Ovs) { 775327952Sdim switch (Ov.SimpleTy) { 776327952Sdim case MVT::iPTRAny: 777327952Sdim Out.insert(MVT::iPTR); 778327952Sdim return; 779327952Sdim case MVT::iAny: 780327952Sdim for (MVT T : MVT::integer_valuetypes()) 781327952Sdim if (Legal.count(T)) 782327952Sdim Out.insert(T); 783360784Sdim for (MVT T : MVT::integer_fixedlen_vector_valuetypes()) 784327952Sdim if (Legal.count(T)) 785327952Sdim Out.insert(T); 786360784Sdim for (MVT T : MVT::integer_scalable_vector_valuetypes()) 787360784Sdim if (Legal.count(T)) 788360784Sdim Out.insert(T); 789327952Sdim return; 790327952Sdim case MVT::fAny: 791327952Sdim for (MVT T : MVT::fp_valuetypes()) 792327952Sdim if (Legal.count(T)) 793327952Sdim Out.insert(T); 794360784Sdim for (MVT T : MVT::fp_fixedlen_vector_valuetypes()) 795327952Sdim if (Legal.count(T)) 796327952Sdim Out.insert(T); 797360784Sdim for (MVT T : MVT::fp_scalable_vector_valuetypes()) 798360784Sdim if (Legal.count(T)) 799360784Sdim Out.insert(T); 800327952Sdim return; 801327952Sdim case MVT::vAny: 802327952Sdim for (MVT T : MVT::vector_valuetypes()) 803327952Sdim if (Legal.count(T)) 804327952Sdim Out.insert(T); 805327952Sdim return; 806327952Sdim case MVT::Any: 807327952Sdim for (MVT T : MVT::all_valuetypes()) 808327952Sdim if (Legal.count(T)) 809327952Sdim Out.insert(T); 810327952Sdim return; 811327952Sdim default: 812327952Sdim break; 813276479Sdim } 814218893Sdim } 815327952Sdim} 816218893Sdim 817344779Sdimconst TypeSetByHwMode &TypeInfer::getLegalTypes() { 818327952Sdim if (!LegalTypesCached) { 819344779Sdim TypeSetByHwMode::SetType &LegalTypes = LegalCache.getOrCreate(DefaultMode); 820327952Sdim // Stuff all types from all modes into the default mode. 821327952Sdim const TypeSetByHwMode <S = TP.getDAGPatterns().getLegalTypes(); 822327952Sdim for (const auto &I : LTS) 823344779Sdim LegalTypes.insert(I.second); 824327952Sdim LegalTypesCached = true; 825327952Sdim } 826344779Sdim assert(LegalCache.isDefaultOnly() && "Default-mode only expected"); 827344779Sdim return LegalCache; 828218893Sdim} 829218893Sdim 830327952Sdim#ifndef NDEBUG 831327952SdimTypeInfer::ValidateOnExit::~ValidateOnExit() { 832341825Sdim if (Infer.Validate && !VTS.validate()) { 833327952Sdim dbgs() << "Type set is empty for each HW mode:\n" 834327952Sdim "possible type contradiction in the pattern below " 835327952Sdim "(use -print-records with llvm-tblgen to see all " 836327952Sdim "expanded records).\n"; 837327952Sdim Infer.TP.dump(); 838327952Sdim llvm_unreachable(nullptr); 839327952Sdim } 840327952Sdim} 841327952Sdim#endif 842288943Sdim 843344779Sdim 844327952Sdim//===----------------------------------------------------------------------===// 845344779Sdim// ScopedName Implementation 846344779Sdim//===----------------------------------------------------------------------===// 847344779Sdim 848344779Sdimbool ScopedName::operator==(const ScopedName &o) const { 849344779Sdim return Scope == o.Scope && Identifier == o.Identifier; 850344779Sdim} 851344779Sdim 852344779Sdimbool ScopedName::operator!=(const ScopedName &o) const { 853344779Sdim return !(*this == o); 854344779Sdim} 855344779Sdim 856344779Sdim 857344779Sdim//===----------------------------------------------------------------------===// 858327952Sdim// TreePredicateFn Implementation 859327952Sdim//===----------------------------------------------------------------------===// 860288943Sdim 861327952Sdim/// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 862327952SdimTreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) { 863327952Sdim assert( 864327952Sdim (!hasPredCode() || !hasImmCode()) && 865327952Sdim ".td file corrupt: can't have a node predicate *and* an imm predicate"); 866327952Sdim} 867321369Sdim 868327952Sdimbool TreePredicateFn::hasPredCode() const { 869327952Sdim return isLoad() || isStore() || isAtomic() || 870327952Sdim !PatFragRec->getRecord()->getValueAsString("PredicateCode").empty(); 871327952Sdim} 872321369Sdim 873327952Sdimstd::string TreePredicateFn::getPredCode() const { 874327952Sdim std::string Code = ""; 875321369Sdim 876327952Sdim if (!isLoad() && !isStore() && !isAtomic()) { 877327952Sdim Record *MemoryVT = getMemoryVT(); 878288943Sdim 879327952Sdim if (MemoryVT) 880327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 881327952Sdim "MemoryVT requires IsLoad or IsStore"); 882327952Sdim } 883288943Sdim 884327952Sdim if (!isLoad() && !isStore()) { 885327952Sdim if (isUnindexed()) 886327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 887327952Sdim "IsUnindexed requires IsLoad or IsStore"); 888296417Sdim 889327952Sdim Record *ScalarMemoryVT = getScalarMemoryVT(); 890288943Sdim 891327952Sdim if (ScalarMemoryVT) 892327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 893327952Sdim "ScalarMemoryVT requires IsLoad or IsStore"); 894327952Sdim } 895288943Sdim 896327952Sdim if (isLoad() + isStore() + isAtomic() > 1) 897327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 898327952Sdim "IsLoad, IsStore, and IsAtomic are mutually exclusive"); 899296417Sdim 900327952Sdim if (isLoad()) { 901327952Sdim if (!isUnindexed() && !isNonExtLoad() && !isAnyExtLoad() && 902327952Sdim !isSignExtLoad() && !isZeroExtLoad() && getMemoryVT() == nullptr && 903360784Sdim getScalarMemoryVT() == nullptr && getAddressSpaces() == nullptr && 904360784Sdim getMinAlignment() < 1) 905327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 906327952Sdim "IsLoad cannot be used by itself"); 907327952Sdim } else { 908327952Sdim if (isNonExtLoad()) 909327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 910327952Sdim "IsNonExtLoad requires IsLoad"); 911327952Sdim if (isAnyExtLoad()) 912327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 913327952Sdim "IsAnyExtLoad requires IsLoad"); 914327952Sdim if (isSignExtLoad()) 915327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 916327952Sdim "IsSignExtLoad requires IsLoad"); 917327952Sdim if (isZeroExtLoad()) 918327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 919327952Sdim "IsZeroExtLoad requires IsLoad"); 920288943Sdim } 921288943Sdim 922327952Sdim if (isStore()) { 923327952Sdim if (!isUnindexed() && !isTruncStore() && !isNonTruncStore() && 924360784Sdim getMemoryVT() == nullptr && getScalarMemoryVT() == nullptr && 925360784Sdim getAddressSpaces() == nullptr && getMinAlignment() < 1) 926327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 927327952Sdim "IsStore cannot be used by itself"); 928327952Sdim } else { 929327952Sdim if (isNonTruncStore()) 930327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 931327952Sdim "IsNonTruncStore requires IsStore"); 932327952Sdim if (isTruncStore()) 933327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 934327952Sdim "IsTruncStore requires IsStore"); 935327952Sdim } 936288943Sdim 937327952Sdim if (isAtomic()) { 938327952Sdim if (getMemoryVT() == nullptr && !isAtomicOrderingMonotonic() && 939360784Sdim getAddressSpaces() == nullptr && 940327952Sdim !isAtomicOrderingAcquire() && !isAtomicOrderingRelease() && 941327952Sdim !isAtomicOrderingAcquireRelease() && 942327952Sdim !isAtomicOrderingSequentiallyConsistent() && 943327952Sdim !isAtomicOrderingAcquireOrStronger() && 944327952Sdim !isAtomicOrderingReleaseOrStronger() && 945327952Sdim !isAtomicOrderingWeakerThanAcquire() && 946327952Sdim !isAtomicOrderingWeakerThanRelease()) 947327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 948327952Sdim "IsAtomic cannot be used by itself"); 949327952Sdim } else { 950327952Sdim if (isAtomicOrderingMonotonic()) 951327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 952327952Sdim "IsAtomicOrderingMonotonic requires IsAtomic"); 953327952Sdim if (isAtomicOrderingAcquire()) 954327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 955327952Sdim "IsAtomicOrderingAcquire requires IsAtomic"); 956327952Sdim if (isAtomicOrderingRelease()) 957327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 958327952Sdim "IsAtomicOrderingRelease requires IsAtomic"); 959327952Sdim if (isAtomicOrderingAcquireRelease()) 960327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 961327952Sdim "IsAtomicOrderingAcquireRelease requires IsAtomic"); 962327952Sdim if (isAtomicOrderingSequentiallyConsistent()) 963327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 964327952Sdim "IsAtomicOrderingSequentiallyConsistent requires IsAtomic"); 965327952Sdim if (isAtomicOrderingAcquireOrStronger()) 966327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 967327952Sdim "IsAtomicOrderingAcquireOrStronger requires IsAtomic"); 968327952Sdim if (isAtomicOrderingReleaseOrStronger()) 969327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 970327952Sdim "IsAtomicOrderingReleaseOrStronger requires IsAtomic"); 971327952Sdim if (isAtomicOrderingWeakerThanAcquire()) 972327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 973327952Sdim "IsAtomicOrderingWeakerThanAcquire requires IsAtomic"); 974327952Sdim } 975296417Sdim 976327952Sdim if (isLoad() || isStore() || isAtomic()) { 977353358Sdim if (ListInit *AddressSpaces = getAddressSpaces()) { 978353358Sdim Code += "unsigned AddrSpace = cast<MemSDNode>(N)->getAddressSpace();\n" 979353358Sdim " if ("; 980296417Sdim 981353358Sdim bool First = true; 982353358Sdim for (Init *Val : AddressSpaces->getValues()) { 983353358Sdim if (First) 984353358Sdim First = false; 985353358Sdim else 986353358Sdim Code += " && "; 987353358Sdim 988353358Sdim IntInit *IntVal = dyn_cast<IntInit>(Val); 989353358Sdim if (!IntVal) { 990353358Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 991353358Sdim "AddressSpaces element must be integer"); 992353358Sdim } 993353358Sdim 994353358Sdim Code += "AddrSpace != " + utostr(IntVal->getValue()); 995353358Sdim } 996353358Sdim 997353358Sdim Code += ")\nreturn false;\n"; 998353358Sdim } 999353358Sdim 1000360784Sdim int64_t MinAlign = getMinAlignment(); 1001360784Sdim if (MinAlign > 0) { 1002360784Sdim Code += "if (cast<MemSDNode>(N)->getAlignment() < "; 1003360784Sdim Code += utostr(MinAlign); 1004360784Sdim Code += ")\nreturn false;\n"; 1005360784Sdim } 1006360784Sdim 1007327952Sdim Record *MemoryVT = getMemoryVT(); 1008321369Sdim 1009327952Sdim if (MemoryVT) 1010353358Sdim Code += ("if (cast<MemSDNode>(N)->getMemoryVT() != MVT::" + 1011327952Sdim MemoryVT->getName() + ") return false;\n") 1012327952Sdim .str(); 1013327952Sdim } 1014321369Sdim 1015327952Sdim if (isAtomic() && isAtomicOrderingMonotonic()) 1016327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 1017327952Sdim "AtomicOrdering::Monotonic) return false;\n"; 1018327952Sdim if (isAtomic() && isAtomicOrderingAcquire()) 1019327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 1020327952Sdim "AtomicOrdering::Acquire) return false;\n"; 1021327952Sdim if (isAtomic() && isAtomicOrderingRelease()) 1022327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 1023327952Sdim "AtomicOrdering::Release) return false;\n"; 1024327952Sdim if (isAtomic() && isAtomicOrderingAcquireRelease()) 1025327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 1026327952Sdim "AtomicOrdering::AcquireRelease) return false;\n"; 1027327952Sdim if (isAtomic() && isAtomicOrderingSequentiallyConsistent()) 1028327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 1029327952Sdim "AtomicOrdering::SequentiallyConsistent) return false;\n"; 1030296417Sdim 1031327952Sdim if (isAtomic() && isAtomicOrderingAcquireOrStronger()) 1032327952Sdim Code += "if (!isAcquireOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 1033327952Sdim "return false;\n"; 1034327952Sdim if (isAtomic() && isAtomicOrderingWeakerThanAcquire()) 1035327952Sdim Code += "if (isAcquireOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 1036327952Sdim "return false;\n"; 1037296417Sdim 1038327952Sdim if (isAtomic() && isAtomicOrderingReleaseOrStronger()) 1039327952Sdim Code += "if (!isReleaseOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 1040327952Sdim "return false;\n"; 1041327952Sdim if (isAtomic() && isAtomicOrderingWeakerThanRelease()) 1042327952Sdim Code += "if (isReleaseOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 1043327952Sdim "return false;\n"; 1044296417Sdim 1045327952Sdim if (isLoad() || isStore()) { 1046327952Sdim StringRef SDNodeName = isLoad() ? "LoadSDNode" : "StoreSDNode"; 1047327952Sdim 1048327952Sdim if (isUnindexed()) 1049327952Sdim Code += ("if (cast<" + SDNodeName + 1050327952Sdim ">(N)->getAddressingMode() != ISD::UNINDEXED) " 1051327952Sdim "return false;\n") 1052327952Sdim .str(); 1053327952Sdim 1054327952Sdim if (isLoad()) { 1055327952Sdim if ((isNonExtLoad() + isAnyExtLoad() + isSignExtLoad() + 1056327952Sdim isZeroExtLoad()) > 1) 1057327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1058327952Sdim "IsNonExtLoad, IsAnyExtLoad, IsSignExtLoad, and " 1059327952Sdim "IsZeroExtLoad are mutually exclusive"); 1060327952Sdim if (isNonExtLoad()) 1061327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != " 1062327952Sdim "ISD::NON_EXTLOAD) return false;\n"; 1063327952Sdim if (isAnyExtLoad()) 1064327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::EXTLOAD) " 1065327952Sdim "return false;\n"; 1066327952Sdim if (isSignExtLoad()) 1067327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::SEXTLOAD) " 1068327952Sdim "return false;\n"; 1069327952Sdim if (isZeroExtLoad()) 1070327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::ZEXTLOAD) " 1071327952Sdim "return false;\n"; 1072327952Sdim } else { 1073327952Sdim if ((isNonTruncStore() + isTruncStore()) > 1) 1074327952Sdim PrintFatalError( 1075327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1076327952Sdim "IsNonTruncStore, and IsTruncStore are mutually exclusive"); 1077327952Sdim if (isNonTruncStore()) 1078327952Sdim Code += 1079327952Sdim " if (cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n"; 1080327952Sdim if (isTruncStore()) 1081327952Sdim Code += 1082327952Sdim " if (!cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n"; 1083296417Sdim } 1084296417Sdim 1085327952Sdim Record *ScalarMemoryVT = getScalarMemoryVT(); 1086296417Sdim 1087327952Sdim if (ScalarMemoryVT) 1088327952Sdim Code += ("if (cast<" + SDNodeName + 1089327952Sdim ">(N)->getMemoryVT().getScalarType() != MVT::" + 1090327952Sdim ScalarMemoryVT->getName() + ") return false;\n") 1091327952Sdim .str(); 1092296417Sdim } 1093296417Sdim 1094327952Sdim std::string PredicateCode = PatFragRec->getRecord()->getValueAsString("PredicateCode"); 1095296417Sdim 1096327952Sdim Code += PredicateCode; 1097205218Srdivacky 1098327952Sdim if (PredicateCode.empty() && !Code.empty()) 1099327952Sdim Code += "return true;\n"; 1100193323Sed 1101327952Sdim return Code; 1102193323Sed} 1103327952Sdim 1104327952Sdimbool TreePredicateFn::hasImmCode() const { 1105327952Sdim return !PatFragRec->getRecord()->getValueAsString("ImmediateCode").empty(); 1106193323Sed} 1107193323Sed 1108327952Sdimstd::string TreePredicateFn::getImmCode() const { 1109327952Sdim return PatFragRec->getRecord()->getValueAsString("ImmediateCode"); 1110193323Sed} 1111218893Sdim 1112327952Sdimbool TreePredicateFn::immCodeUsesAPInt() const { 1113327952Sdim return getOrigPatFragRecord()->getRecord()->getValueAsBit("IsAPInt"); 1114327952Sdim} 1115221345Sdim 1116327952Sdimbool TreePredicateFn::immCodeUsesAPFloat() const { 1117327952Sdim bool Unset; 1118327952Sdim // The return value will be false when IsAPFloat is unset. 1119327952Sdim return getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset("IsAPFloat", 1120327952Sdim Unset); 1121327952Sdim} 1122221345Sdim 1123327952Sdimbool TreePredicateFn::isPredefinedPredicateEqualTo(StringRef Field, 1124327952Sdim bool Value) const { 1125327952Sdim bool Unset; 1126327952Sdim bool Result = 1127327952Sdim getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset(Field, Unset); 1128327952Sdim if (Unset) 1129327952Sdim return false; 1130327952Sdim return Result == Value; 1131193323Sed} 1132344779Sdimbool TreePredicateFn::usesOperands() const { 1133344779Sdim return isPredefinedPredicateEqualTo("PredicateCodeUsesOperands", true); 1134344779Sdim} 1135327952Sdimbool TreePredicateFn::isLoad() const { 1136327952Sdim return isPredefinedPredicateEqualTo("IsLoad", true); 1137327952Sdim} 1138327952Sdimbool TreePredicateFn::isStore() const { 1139327952Sdim return isPredefinedPredicateEqualTo("IsStore", true); 1140327952Sdim} 1141327952Sdimbool TreePredicateFn::isAtomic() const { 1142327952Sdim return isPredefinedPredicateEqualTo("IsAtomic", true); 1143327952Sdim} 1144327952Sdimbool TreePredicateFn::isUnindexed() const { 1145327952Sdim return isPredefinedPredicateEqualTo("IsUnindexed", true); 1146327952Sdim} 1147327952Sdimbool TreePredicateFn::isNonExtLoad() const { 1148327952Sdim return isPredefinedPredicateEqualTo("IsNonExtLoad", true); 1149327952Sdim} 1150327952Sdimbool TreePredicateFn::isAnyExtLoad() const { 1151327952Sdim return isPredefinedPredicateEqualTo("IsAnyExtLoad", true); 1152327952Sdim} 1153327952Sdimbool TreePredicateFn::isSignExtLoad() const { 1154327952Sdim return isPredefinedPredicateEqualTo("IsSignExtLoad", true); 1155327952Sdim} 1156327952Sdimbool TreePredicateFn::isZeroExtLoad() const { 1157327952Sdim return isPredefinedPredicateEqualTo("IsZeroExtLoad", true); 1158327952Sdim} 1159327952Sdimbool TreePredicateFn::isNonTruncStore() const { 1160327952Sdim return isPredefinedPredicateEqualTo("IsTruncStore", false); 1161327952Sdim} 1162327952Sdimbool TreePredicateFn::isTruncStore() const { 1163327952Sdim return isPredefinedPredicateEqualTo("IsTruncStore", true); 1164327952Sdim} 1165327952Sdimbool TreePredicateFn::isAtomicOrderingMonotonic() const { 1166327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingMonotonic", true); 1167327952Sdim} 1168327952Sdimbool TreePredicateFn::isAtomicOrderingAcquire() const { 1169327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquire", true); 1170327952Sdim} 1171327952Sdimbool TreePredicateFn::isAtomicOrderingRelease() const { 1172327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingRelease", true); 1173327952Sdim} 1174327952Sdimbool TreePredicateFn::isAtomicOrderingAcquireRelease() const { 1175327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireRelease", true); 1176327952Sdim} 1177327952Sdimbool TreePredicateFn::isAtomicOrderingSequentiallyConsistent() const { 1178327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingSequentiallyConsistent", 1179327952Sdim true); 1180327952Sdim} 1181327952Sdimbool TreePredicateFn::isAtomicOrderingAcquireOrStronger() const { 1182327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger", true); 1183327952Sdim} 1184327952Sdimbool TreePredicateFn::isAtomicOrderingWeakerThanAcquire() const { 1185327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger", false); 1186327952Sdim} 1187327952Sdimbool TreePredicateFn::isAtomicOrderingReleaseOrStronger() const { 1188327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger", true); 1189327952Sdim} 1190327952Sdimbool TreePredicateFn::isAtomicOrderingWeakerThanRelease() const { 1191327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger", false); 1192327952Sdim} 1193327952SdimRecord *TreePredicateFn::getMemoryVT() const { 1194327952Sdim Record *R = getOrigPatFragRecord()->getRecord(); 1195327952Sdim if (R->isValueUnset("MemoryVT")) 1196327952Sdim return nullptr; 1197327952Sdim return R->getValueAsDef("MemoryVT"); 1198327952Sdim} 1199353358Sdim 1200353358SdimListInit *TreePredicateFn::getAddressSpaces() const { 1201353358Sdim Record *R = getOrigPatFragRecord()->getRecord(); 1202353358Sdim if (R->isValueUnset("AddressSpaces")) 1203353358Sdim return nullptr; 1204353358Sdim return R->getValueAsListInit("AddressSpaces"); 1205353358Sdim} 1206353358Sdim 1207360784Sdimint64_t TreePredicateFn::getMinAlignment() const { 1208360784Sdim Record *R = getOrigPatFragRecord()->getRecord(); 1209360784Sdim if (R->isValueUnset("MinAlignment")) 1210360784Sdim return 0; 1211360784Sdim return R->getValueAsInt("MinAlignment"); 1212360784Sdim} 1213360784Sdim 1214327952SdimRecord *TreePredicateFn::getScalarMemoryVT() const { 1215327952Sdim Record *R = getOrigPatFragRecord()->getRecord(); 1216327952Sdim if (R->isValueUnset("ScalarMemoryVT")) 1217327952Sdim return nullptr; 1218327952Sdim return R->getValueAsDef("ScalarMemoryVT"); 1219327952Sdim} 1220341825Sdimbool TreePredicateFn::hasGISelPredicateCode() const { 1221341825Sdim return !PatFragRec->getRecord() 1222341825Sdim ->getValueAsString("GISelPredicateCode") 1223341825Sdim .empty(); 1224341825Sdim} 1225341825Sdimstd::string TreePredicateFn::getGISelPredicateCode() const { 1226341825Sdim return PatFragRec->getRecord()->getValueAsString("GISelPredicateCode"); 1227341825Sdim} 1228193323Sed 1229327952SdimStringRef TreePredicateFn::getImmType() const { 1230327952Sdim if (immCodeUsesAPInt()) 1231327952Sdim return "const APInt &"; 1232327952Sdim if (immCodeUsesAPFloat()) 1233327952Sdim return "const APFloat &"; 1234327952Sdim return "int64_t"; 1235221345Sdim} 1236221345Sdim 1237327952SdimStringRef TreePredicateFn::getImmTypeIdentifier() const { 1238327952Sdim if (immCodeUsesAPInt()) 1239327952Sdim return "APInt"; 1240327952Sdim else if (immCodeUsesAPFloat()) 1241327952Sdim return "APFloat"; 1242327952Sdim return "I64"; 1243221345Sdim} 1244221345Sdim 1245221345Sdim/// isAlwaysTrue - Return true if this is a noop predicate. 1246221345Sdimbool TreePredicateFn::isAlwaysTrue() const { 1247327952Sdim return !hasPredCode() && !hasImmCode(); 1248221345Sdim} 1249221345Sdim 1250221345Sdim/// Return the name to use in the generated code to reference this, this is 1251221345Sdim/// "Predicate_foo" if from a pattern fragment "foo". 1252221345Sdimstd::string TreePredicateFn::getFnName() const { 1253314564Sdim return "Predicate_" + PatFragRec->getRecord()->getName().str(); 1254221345Sdim} 1255221345Sdim 1256221345Sdim/// getCodeToRunOnSDNode - Return the code for the function body that 1257221345Sdim/// evaluates this predicate. The argument is expected to be in "Node", 1258221345Sdim/// not N. This handles casting and conversion to a concrete node type as 1259221345Sdim/// appropriate. 1260221345Sdimstd::string TreePredicateFn::getCodeToRunOnSDNode() const { 1261221345Sdim // Handle immediate predicates first. 1262221345Sdim std::string ImmCode = getImmCode(); 1263221345Sdim if (!ImmCode.empty()) { 1264327952Sdim if (isLoad()) 1265327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1266327952Sdim "IsLoad cannot be used with ImmLeaf or its subclasses"); 1267327952Sdim if (isStore()) 1268327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1269327952Sdim "IsStore cannot be used with ImmLeaf or its subclasses"); 1270327952Sdim if (isUnindexed()) 1271327952Sdim PrintFatalError( 1272327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1273327952Sdim "IsUnindexed cannot be used with ImmLeaf or its subclasses"); 1274327952Sdim if (isNonExtLoad()) 1275327952Sdim PrintFatalError( 1276327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1277327952Sdim "IsNonExtLoad cannot be used with ImmLeaf or its subclasses"); 1278327952Sdim if (isAnyExtLoad()) 1279327952Sdim PrintFatalError( 1280327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1281327952Sdim "IsAnyExtLoad cannot be used with ImmLeaf or its subclasses"); 1282327952Sdim if (isSignExtLoad()) 1283327952Sdim PrintFatalError( 1284327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1285327952Sdim "IsSignExtLoad cannot be used with ImmLeaf or its subclasses"); 1286327952Sdim if (isZeroExtLoad()) 1287327952Sdim PrintFatalError( 1288327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1289327952Sdim "IsZeroExtLoad cannot be used with ImmLeaf or its subclasses"); 1290327952Sdim if (isNonTruncStore()) 1291327952Sdim PrintFatalError( 1292327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1293327952Sdim "IsNonTruncStore cannot be used with ImmLeaf or its subclasses"); 1294327952Sdim if (isTruncStore()) 1295327952Sdim PrintFatalError( 1296327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1297327952Sdim "IsTruncStore cannot be used with ImmLeaf or its subclasses"); 1298327952Sdim if (getMemoryVT()) 1299327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1300327952Sdim "MemoryVT cannot be used with ImmLeaf or its subclasses"); 1301327952Sdim if (getScalarMemoryVT()) 1302327952Sdim PrintFatalError( 1303327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1304327952Sdim "ScalarMemoryVT cannot be used with ImmLeaf or its subclasses"); 1305327952Sdim 1306327952Sdim std::string Result = (" " + getImmType() + " Imm = ").str(); 1307327952Sdim if (immCodeUsesAPFloat()) 1308327952Sdim Result += "cast<ConstantFPSDNode>(Node)->getValueAPF();\n"; 1309327952Sdim else if (immCodeUsesAPInt()) 1310327952Sdim Result += "cast<ConstantSDNode>(Node)->getAPIntValue();\n"; 1311327952Sdim else 1312327952Sdim Result += "cast<ConstantSDNode>(Node)->getSExtValue();\n"; 1313221345Sdim return Result + ImmCode; 1314221345Sdim } 1315327952Sdim 1316221345Sdim // Handle arbitrary node predicates. 1317327952Sdim assert(hasPredCode() && "Don't have any predicate code!"); 1318360784Sdim 1319360784Sdim // If this is using PatFrags, there are multiple trees to search. They should 1320360784Sdim // all have the same class. FIXME: Is there a way to find a common 1321360784Sdim // superclass? 1322327952Sdim StringRef ClassName; 1323360784Sdim for (const auto &Tree : PatFragRec->getTrees()) { 1324360784Sdim StringRef TreeClassName; 1325360784Sdim if (Tree->isLeaf()) 1326360784Sdim TreeClassName = "SDNode"; 1327360784Sdim else { 1328360784Sdim Record *Op = Tree->getOperator(); 1329360784Sdim const SDNodeInfo &Info = PatFragRec->getDAGPatterns().getSDNodeInfo(Op); 1330360784Sdim TreeClassName = Info.getSDClassName(); 1331360784Sdim } 1332360784Sdim 1333360784Sdim if (ClassName.empty()) 1334360784Sdim ClassName = TreeClassName; 1335360784Sdim else if (ClassName != TreeClassName) { 1336360784Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1337360784Sdim "PatFrags trees do not have consistent class"); 1338360784Sdim } 1339221345Sdim } 1340360784Sdim 1341221345Sdim std::string Result; 1342221345Sdim if (ClassName == "SDNode") 1343221345Sdim Result = " SDNode *N = Node;\n"; 1344221345Sdim else 1345327952Sdim Result = " auto *N = cast<" + ClassName.str() + ">(Node);\n"; 1346327952Sdim 1347344779Sdim return (Twine(Result) + " (void)N;\n" + getPredCode()).str(); 1348221345Sdim} 1349221345Sdim 1350193323Sed//===----------------------------------------------------------------------===// 1351193323Sed// PatternToMatch implementation 1352193323Sed// 1353193323Sed 1354353358Sdimstatic bool isImmAllOnesAllZerosMatch(const TreePatternNode *P) { 1355353358Sdim if (!P->isLeaf()) 1356353358Sdim return false; 1357353358Sdim DefInit *DI = dyn_cast<DefInit>(P->getLeafValue()); 1358353358Sdim if (!DI) 1359353358Sdim return false; 1360353358Sdim 1361353358Sdim Record *R = DI->getDef(); 1362353358Sdim return R->getName() == "immAllOnesV" || R->getName() == "immAllZerosV"; 1363353358Sdim} 1364353358Sdim 1365206083Srdivacky/// getPatternSize - Return the 'size' of this pattern. We want to match large 1366206083Srdivacky/// patterns before small ones. This is used to determine the size of a 1367206083Srdivacky/// pattern. 1368206083Srdivackystatic unsigned getPatternSize(const TreePatternNode *P, 1369206083Srdivacky const CodeGenDAGPatterns &CGP) { 1370206083Srdivacky unsigned Size = 3; // The node itself. 1371206083Srdivacky // If the root node is a ConstantSDNode, increases its size. 1372206083Srdivacky // e.g. (set R32:$dst, 0). 1373243830Sdim if (P->isLeaf() && isa<IntInit>(P->getLeafValue())) 1374206083Srdivacky Size += 2; 1375218893Sdim 1376327952Sdim if (const ComplexPattern *AM = P->getComplexPatternInfo(CGP)) { 1377314564Sdim Size += AM->getComplexity(); 1378276479Sdim // We don't want to count any children twice, so return early. 1379276479Sdim return Size; 1380276479Sdim } 1381276479Sdim 1382206083Srdivacky // If this node has some predicate function that must match, it adds to the 1383206083Srdivacky // complexity of this node. 1384344779Sdim if (!P->getPredicateCalls().empty()) 1385206083Srdivacky ++Size; 1386218893Sdim 1387206083Srdivacky // Count children in the count if they are also nodes. 1388206083Srdivacky for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { 1389327952Sdim const TreePatternNode *Child = P->getChild(i); 1390327952Sdim if (!Child->isLeaf() && Child->getNumTypes()) { 1391344779Sdim const TypeSetByHwMode &T0 = Child->getExtType(0); 1392327952Sdim // At this point, all variable type sets should be simple, i.e. only 1393327952Sdim // have a default mode. 1394327952Sdim if (T0.getMachineValueType() != MVT::Other) { 1395327952Sdim Size += getPatternSize(Child, CGP); 1396327952Sdim continue; 1397327952Sdim } 1398327952Sdim } 1399327952Sdim if (Child->isLeaf()) { 1400243830Sdim if (isa<IntInit>(Child->getLeafValue())) 1401206083Srdivacky Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). 1402206083Srdivacky else if (Child->getComplexPatternInfo(CGP)) 1403206083Srdivacky Size += getPatternSize(Child, CGP); 1404353358Sdim else if (isImmAllOnesAllZerosMatch(Child)) 1405353358Sdim Size += 4; // Matches a build_vector(+3) and a predicate (+1). 1406344779Sdim else if (!Child->getPredicateCalls().empty()) 1407206083Srdivacky ++Size; 1408206083Srdivacky } 1409206083Srdivacky } 1410218893Sdim 1411206083Srdivacky return Size; 1412206083Srdivacky} 1413206083Srdivacky 1414206083Srdivacky/// Compute the complexity metric for the input pattern. This roughly 1415206083Srdivacky/// corresponds to the number of nodes that are covered. 1416280031Sdimint PatternToMatch:: 1417206083SrdivackygetPatternComplexity(const CodeGenDAGPatterns &CGP) const { 1418206083Srdivacky return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity(); 1419206083Srdivacky} 1420206083Srdivacky 1421193323Sed/// getPredicateCheck - Return a single string containing all of this 1422193323Sed/// pattern's predicates concatenated with "&&" operators. 1423193323Sed/// 1424193323Sedstd::string PatternToMatch::getPredicateCheck() const { 1425327952Sdim SmallVector<const Predicate*,4> PredList; 1426360784Sdim for (const Predicate &P : Predicates) { 1427360784Sdim if (!P.getCondString().empty()) 1428360784Sdim PredList.push_back(&P); 1429360784Sdim } 1430360784Sdim llvm::sort(PredList, deref<std::less<>>()); 1431193323Sed 1432327952Sdim std::string Check; 1433327952Sdim for (unsigned i = 0, e = PredList.size(); i != e; ++i) { 1434327952Sdim if (i != 0) 1435327952Sdim Check += " && "; 1436327952Sdim Check += '(' + PredList[i]->getCondString() + ')'; 1437296417Sdim } 1438327952Sdim return Check; 1439193323Sed} 1440193323Sed 1441193323Sed//===----------------------------------------------------------------------===// 1442193323Sed// SDTypeConstraint implementation 1443193323Sed// 1444193323Sed 1445327952SdimSDTypeConstraint::SDTypeConstraint(Record *R, const CodeGenHwModes &CGH) { 1446193323Sed OperandNo = R->getValueAsInt("OperandNum"); 1447218893Sdim 1448193323Sed if (R->isSubClassOf("SDTCisVT")) { 1449193323Sed ConstraintType = SDTCisVT; 1450327952Sdim VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH); 1451327952Sdim for (const auto &P : VVT) 1452327952Sdim if (P.second == MVT::isVoid) 1453327952Sdim PrintFatalError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT"); 1454193323Sed } else if (R->isSubClassOf("SDTCisPtrTy")) { 1455193323Sed ConstraintType = SDTCisPtrTy; 1456193323Sed } else if (R->isSubClassOf("SDTCisInt")) { 1457193323Sed ConstraintType = SDTCisInt; 1458193323Sed } else if (R->isSubClassOf("SDTCisFP")) { 1459193323Sed ConstraintType = SDTCisFP; 1460198090Srdivacky } else if (R->isSubClassOf("SDTCisVec")) { 1461198090Srdivacky ConstraintType = SDTCisVec; 1462193323Sed } else if (R->isSubClassOf("SDTCisSameAs")) { 1463193323Sed ConstraintType = SDTCisSameAs; 1464193323Sed x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 1465193323Sed } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 1466193323Sed ConstraintType = SDTCisVTSmallerThanOp; 1467218893Sdim x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 1468193323Sed R->getValueAsInt("OtherOperandNum"); 1469193323Sed } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 1470193323Sed ConstraintType = SDTCisOpSmallerThanOp; 1471218893Sdim x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 1472193323Sed R->getValueAsInt("BigOperandNum"); 1473193323Sed } else if (R->isSubClassOf("SDTCisEltOfVec")) { 1474193323Sed ConstraintType = SDTCisEltOfVec; 1475205218Srdivacky x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); 1476218893Sdim } else if (R->isSubClassOf("SDTCisSubVecOfVec")) { 1477218893Sdim ConstraintType = SDTCisSubVecOfVec; 1478218893Sdim x.SDTCisSubVecOfVec_Info.OtherOperandNum = 1479218893Sdim R->getValueAsInt("OtherOpNum"); 1480288943Sdim } else if (R->isSubClassOf("SDTCVecEltisVT")) { 1481288943Sdim ConstraintType = SDTCVecEltisVT; 1482327952Sdim VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH); 1483327952Sdim for (const auto &P : VVT) { 1484327952Sdim MVT T = P.second; 1485327952Sdim if (T.isVector()) 1486327952Sdim PrintFatalError(R->getLoc(), 1487327952Sdim "Cannot use vector type as SDTCVecEltisVT"); 1488327952Sdim if (!T.isInteger() && !T.isFloatingPoint()) 1489327952Sdim PrintFatalError(R->getLoc(), "Must use integer or floating point type " 1490327952Sdim "as SDTCVecEltisVT"); 1491327952Sdim } 1492288943Sdim } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) { 1493288943Sdim ConstraintType = SDTCisSameNumEltsAs; 1494288943Sdim x.SDTCisSameNumEltsAs_Info.OtherOperandNum = 1495288943Sdim R->getValueAsInt("OtherOperandNum"); 1496296417Sdim } else if (R->isSubClassOf("SDTCisSameSizeAs")) { 1497296417Sdim ConstraintType = SDTCisSameSizeAs; 1498296417Sdim x.SDTCisSameSizeAs_Info.OtherOperandNum = 1499296417Sdim R->getValueAsInt("OtherOperandNum"); 1500193323Sed } else { 1501353358Sdim PrintFatalError(R->getLoc(), 1502353358Sdim "Unrecognized SDTypeConstraint '" + R->getName() + "'!\n"); 1503193323Sed } 1504193323Sed} 1505193323Sed 1506193323Sed/// getOperandNum - Return the node corresponding to operand #OpNo in tree 1507205407Srdivacky/// N, and the result number in ResNo. 1508205407Srdivackystatic TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, 1509205407Srdivacky const SDNodeInfo &NodeInfo, 1510205407Srdivacky unsigned &ResNo) { 1511205407Srdivacky unsigned NumResults = NodeInfo.getNumResults(); 1512205407Srdivacky if (OpNo < NumResults) { 1513205407Srdivacky ResNo = OpNo; 1514205407Srdivacky return N; 1515205407Srdivacky } 1516218893Sdim 1517205407Srdivacky OpNo -= NumResults; 1518218893Sdim 1519205407Srdivacky if (OpNo >= N->getNumChildren()) { 1520288943Sdim std::string S; 1521288943Sdim raw_string_ostream OS(S); 1522288943Sdim OS << "Invalid operand number in type constraint " 1523205407Srdivacky << (OpNo+NumResults) << " "; 1524288943Sdim N->print(OS); 1525288943Sdim PrintFatalError(OS.str()); 1526193323Sed } 1527193323Sed 1528205407Srdivacky return N->getChild(OpNo); 1529193323Sed} 1530193323Sed 1531193323Sed/// ApplyTypeConstraint - Given a node in a pattern, apply this type 1532193323Sed/// constraint to the nodes operands. This returns true if it makes a 1533243830Sdim/// change, false otherwise. If a type contradiction is found, flag an error. 1534193323Sedbool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 1535193323Sed const SDNodeInfo &NodeInfo, 1536193323Sed TreePattern &TP) const { 1537243830Sdim if (TP.hasError()) 1538243830Sdim return false; 1539243830Sdim 1540205407Srdivacky unsigned ResNo = 0; // The result number being referenced. 1541205407Srdivacky TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo); 1542327952Sdim TypeInfer &TI = TP.getInfer(); 1543218893Sdim 1544193323Sed switch (ConstraintType) { 1545193323Sed case SDTCisVT: 1546193323Sed // Operand must be a particular type. 1547327952Sdim return NodeToApply->UpdateNodeType(ResNo, VVT, TP); 1548205218Srdivacky case SDTCisPtrTy: 1549193323Sed // Operand must be same as target pointer type. 1550205407Srdivacky return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP); 1551205218Srdivacky case SDTCisInt: 1552205218Srdivacky // Require it to be one of the legal integer VTs. 1553327952Sdim return TI.EnforceInteger(NodeToApply->getExtType(ResNo)); 1554205218Srdivacky case SDTCisFP: 1555205218Srdivacky // Require it to be one of the legal fp VTs. 1556327952Sdim return TI.EnforceFloatingPoint(NodeToApply->getExtType(ResNo)); 1557205218Srdivacky case SDTCisVec: 1558205218Srdivacky // Require it to be one of the legal vector VTs. 1559327952Sdim return TI.EnforceVector(NodeToApply->getExtType(ResNo)); 1560193323Sed case SDTCisSameAs: { 1561205407Srdivacky unsigned OResNo = 0; 1562193323Sed TreePatternNode *OtherNode = 1563205407Srdivacky getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); 1564288943Sdim return NodeToApply->UpdateNodeType(ResNo, OtherNode->getExtType(OResNo),TP)| 1565288943Sdim OtherNode->UpdateNodeType(OResNo,NodeToApply->getExtType(ResNo),TP); 1566193323Sed } 1567193323Sed case SDTCisVTSmallerThanOp: { 1568193323Sed // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 1569193323Sed // have an integer type that is smaller than the VT. 1570193323Sed if (!NodeToApply->isLeaf() || 1571243830Sdim !isa<DefInit>(NodeToApply->getLeafValue()) || 1572193323Sed !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 1573243830Sdim ->isSubClassOf("ValueType")) { 1574193323Sed TP.error(N->getOperator()->getName() + " expects a VT operand!"); 1575243830Sdim return false; 1576243830Sdim } 1577327952Sdim DefInit *DI = static_cast<DefInit*>(NodeToApply->getLeafValue()); 1578327952Sdim const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1579327952Sdim auto VVT = getValueTypeByHwMode(DI->getDef(), T.getHwModes()); 1580327952Sdim TypeSetByHwMode TypeListTmp(VVT); 1581218893Sdim 1582205407Srdivacky unsigned OResNo = 0; 1583193323Sed TreePatternNode *OtherNode = 1584205407Srdivacky getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo, 1585205407Srdivacky OResNo); 1586205218Srdivacky 1587327952Sdim return TI.EnforceSmallerThan(TypeListTmp, OtherNode->getExtType(OResNo)); 1588193323Sed } 1589193323Sed case SDTCisOpSmallerThanOp: { 1590205407Srdivacky unsigned BResNo = 0; 1591193323Sed TreePatternNode *BigOperand = 1592205407Srdivacky getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo, 1593205407Srdivacky BResNo); 1594327952Sdim return TI.EnforceSmallerThan(NodeToApply->getExtType(ResNo), 1595327952Sdim BigOperand->getExtType(BResNo)); 1596193323Sed } 1597193323Sed case SDTCisEltOfVec: { 1598205407Srdivacky unsigned VResNo = 0; 1599205218Srdivacky TreePatternNode *VecOperand = 1600205407Srdivacky getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo, 1601205407Srdivacky VResNo); 1602206083Srdivacky // Filter vector types out of VecOperand that don't have the right element 1603206083Srdivacky // type. 1604327952Sdim return TI.EnforceVectorEltTypeIs(VecOperand->getExtType(VResNo), 1605327952Sdim NodeToApply->getExtType(ResNo)); 1606193323Sed } 1607218893Sdim case SDTCisSubVecOfVec: { 1608218893Sdim unsigned VResNo = 0; 1609218893Sdim TreePatternNode *BigVecOperand = 1610218893Sdim getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo, 1611218893Sdim VResNo); 1612218893Sdim 1613218893Sdim // Filter vector types out of BigVecOperand that don't have the 1614218893Sdim // right subvector type. 1615327952Sdim return TI.EnforceVectorSubVectorTypeIs(BigVecOperand->getExtType(VResNo), 1616327952Sdim NodeToApply->getExtType(ResNo)); 1617218893Sdim } 1618288943Sdim case SDTCVecEltisVT: { 1619327952Sdim return TI.EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), VVT); 1620218893Sdim } 1621288943Sdim case SDTCisSameNumEltsAs: { 1622288943Sdim unsigned OResNo = 0; 1623288943Sdim TreePatternNode *OtherNode = 1624288943Sdim getOperandNum(x.SDTCisSameNumEltsAs_Info.OtherOperandNum, 1625288943Sdim N, NodeInfo, OResNo); 1626327952Sdim return TI.EnforceSameNumElts(OtherNode->getExtType(OResNo), 1627327952Sdim NodeToApply->getExtType(ResNo)); 1628288943Sdim } 1629296417Sdim case SDTCisSameSizeAs: { 1630296417Sdim unsigned OResNo = 0; 1631296417Sdim TreePatternNode *OtherNode = 1632296417Sdim getOperandNum(x.SDTCisSameSizeAs_Info.OtherOperandNum, 1633296417Sdim N, NodeInfo, OResNo); 1634327952Sdim return TI.EnforceSameSize(OtherNode->getExtType(OResNo), 1635327952Sdim NodeToApply->getExtType(ResNo)); 1636288943Sdim } 1637296417Sdim } 1638234353Sdim llvm_unreachable("Invalid ConstraintType!"); 1639193323Sed} 1640193323Sed 1641249423Sdim// Update the node type to match an instruction operand or result as specified 1642249423Sdim// in the ins or outs lists on the instruction definition. Return true if the 1643249423Sdim// type was actually changed. 1644249423Sdimbool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo, 1645249423Sdim Record *Operand, 1646249423Sdim TreePattern &TP) { 1647249423Sdim // The 'unknown' operand indicates that types should be inferred from the 1648249423Sdim // context. 1649249423Sdim if (Operand->isSubClassOf("unknown_class")) 1650249423Sdim return false; 1651249423Sdim 1652249423Sdim // The Operand class specifies a type directly. 1653327952Sdim if (Operand->isSubClassOf("Operand")) { 1654327952Sdim Record *R = Operand->getValueAsDef("Type"); 1655327952Sdim const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1656327952Sdim return UpdateNodeType(ResNo, getValueTypeByHwMode(R, T.getHwModes()), TP); 1657327952Sdim } 1658249423Sdim 1659249423Sdim // PointerLikeRegClass has a type that is determined at runtime. 1660249423Sdim if (Operand->isSubClassOf("PointerLikeRegClass")) 1661249423Sdim return UpdateNodeType(ResNo, MVT::iPTR, TP); 1662249423Sdim 1663249423Sdim // Both RegisterClass and RegisterOperand operands derive their types from a 1664249423Sdim // register class def. 1665276479Sdim Record *RC = nullptr; 1666249423Sdim if (Operand->isSubClassOf("RegisterClass")) 1667249423Sdim RC = Operand; 1668249423Sdim else if (Operand->isSubClassOf("RegisterOperand")) 1669249423Sdim RC = Operand->getValueAsDef("RegClass"); 1670249423Sdim 1671249423Sdim assert(RC && "Unknown operand type"); 1672249423Sdim CodeGenTarget &Tgt = TP.getDAGPatterns().getTargetInfo(); 1673249423Sdim return UpdateNodeType(ResNo, Tgt.getRegisterClass(RC).getValueTypes(), TP); 1674249423Sdim} 1675249423Sdim 1676327952Sdimbool TreePatternNode::ContainsUnresolvedType(TreePattern &TP) const { 1677327952Sdim for (unsigned i = 0, e = Types.size(); i != e; ++i) 1678327952Sdim if (!TP.getInfer().isConcrete(Types[i], true)) 1679327952Sdim return true; 1680327952Sdim for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1681327952Sdim if (getChild(i)->ContainsUnresolvedType(TP)) 1682327952Sdim return true; 1683327952Sdim return false; 1684327952Sdim} 1685249423Sdim 1686327952Sdimbool TreePatternNode::hasProperTypeByHwMode() const { 1687327952Sdim for (const TypeSetByHwMode &S : Types) 1688327952Sdim if (!S.isDefaultOnly()) 1689327952Sdim return true; 1690341825Sdim for (const TreePatternNodePtr &C : Children) 1691327952Sdim if (C->hasProperTypeByHwMode()) 1692327952Sdim return true; 1693327952Sdim return false; 1694327952Sdim} 1695327952Sdim 1696327952Sdimbool TreePatternNode::hasPossibleType() const { 1697327952Sdim for (const TypeSetByHwMode &S : Types) 1698327952Sdim if (!S.isPossible()) 1699327952Sdim return false; 1700341825Sdim for (const TreePatternNodePtr &C : Children) 1701327952Sdim if (!C->hasPossibleType()) 1702327952Sdim return false; 1703327952Sdim return true; 1704327952Sdim} 1705327952Sdim 1706327952Sdimbool TreePatternNode::setDefaultMode(unsigned Mode) { 1707327952Sdim for (TypeSetByHwMode &S : Types) { 1708327952Sdim S.makeSimple(Mode); 1709327952Sdim // Check if the selected mode had a type conflict. 1710327952Sdim if (S.get(DefaultMode).empty()) 1711327952Sdim return false; 1712327952Sdim } 1713341825Sdim for (const TreePatternNodePtr &C : Children) 1714327952Sdim if (!C->setDefaultMode(Mode)) 1715327952Sdim return false; 1716327952Sdim return true; 1717327952Sdim} 1718327952Sdim 1719193323Sed//===----------------------------------------------------------------------===// 1720193323Sed// SDNodeInfo implementation 1721193323Sed// 1722327952SdimSDNodeInfo::SDNodeInfo(Record *R, const CodeGenHwModes &CGH) : Def(R) { 1723193323Sed EnumName = R->getValueAsString("Opcode"); 1724193323Sed SDClassName = R->getValueAsString("SDClass"); 1725193323Sed Record *TypeProfile = R->getValueAsDef("TypeProfile"); 1726193323Sed NumResults = TypeProfile->getValueAsInt("NumResults"); 1727193323Sed NumOperands = TypeProfile->getValueAsInt("NumOperands"); 1728218893Sdim 1729193323Sed // Parse the properties. 1730327952Sdim Properties = parseSDPatternOperatorProperties(R); 1731218893Sdim 1732193323Sed // Parse the type constraints. 1733193323Sed std::vector<Record*> ConstraintList = 1734193323Sed TypeProfile->getValueAsListOfDefs("Constraints"); 1735327952Sdim for (Record *R : ConstraintList) 1736327952Sdim TypeConstraints.emplace_back(R, CGH); 1737193323Sed} 1738193323Sed 1739204642Srdivacky/// getKnownType - If the type constraints on this node imply a fixed type 1740204642Srdivacky/// (e.g. all stores return void, etc), then return it as an 1741205407Srdivacky/// MVT::SimpleValueType. Otherwise, return EEVT::Other. 1742206083SrdivackyMVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { 1743204642Srdivacky unsigned NumResults = getNumResults(); 1744204642Srdivacky assert(NumResults <= 1 && 1745204642Srdivacky "We only work with nodes with zero or one result so far!"); 1746206083Srdivacky assert(ResNo == 0 && "Only handles single result nodes so far"); 1747218893Sdim 1748296417Sdim for (const SDTypeConstraint &Constraint : TypeConstraints) { 1749204642Srdivacky // Make sure that this applies to the correct node result. 1750296417Sdim if (Constraint.OperandNo >= NumResults) // FIXME: need value # 1751204642Srdivacky continue; 1752218893Sdim 1753296417Sdim switch (Constraint.ConstraintType) { 1754204642Srdivacky default: break; 1755204642Srdivacky case SDTypeConstraint::SDTCisVT: 1756327952Sdim if (Constraint.VVT.isSimple()) 1757327952Sdim return Constraint.VVT.getSimple().SimpleTy; 1758327952Sdim break; 1759204642Srdivacky case SDTypeConstraint::SDTCisPtrTy: 1760204642Srdivacky return MVT::iPTR; 1761204642Srdivacky } 1762204642Srdivacky } 1763205407Srdivacky return MVT::Other; 1764204642Srdivacky} 1765204642Srdivacky 1766193323Sed//===----------------------------------------------------------------------===// 1767193323Sed// TreePatternNode implementation 1768193323Sed// 1769193323Sed 1770205407Srdivackystatic unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { 1771205407Srdivacky if (Operator->getName() == "set" || 1772206083Srdivacky Operator->getName() == "implicit") 1773205407Srdivacky return 0; // All return nothing. 1774218893Sdim 1775206083Srdivacky if (Operator->isSubClassOf("Intrinsic")) 1776206083Srdivacky return CDP.getIntrinsic(Operator).IS.RetVTs.size(); 1777218893Sdim 1778205407Srdivacky if (Operator->isSubClassOf("SDNode")) 1779205407Srdivacky return CDP.getSDNodeInfo(Operator).getNumResults(); 1780218893Sdim 1781341825Sdim if (Operator->isSubClassOf("PatFrags")) { 1782205407Srdivacky // If we've already parsed this pattern fragment, get it. Otherwise, handle 1783205407Srdivacky // the forward reference case where one pattern fragment references another 1784205407Srdivacky // before it is processed. 1785341825Sdim if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) { 1786341825Sdim // The number of results of a fragment with alternative records is the 1787341825Sdim // maximum number of results across all alternatives. 1788341825Sdim unsigned NumResults = 0; 1789341825Sdim for (auto T : PFRec->getTrees()) 1790341825Sdim NumResults = std::max(NumResults, T->getNumTypes()); 1791341825Sdim return NumResults; 1792341825Sdim } 1793218893Sdim 1794341825Sdim ListInit *LI = Operator->getValueAsListInit("Fragments"); 1795341825Sdim assert(LI && "Invalid Fragment"); 1796341825Sdim unsigned NumResults = 0; 1797341825Sdim for (Init *I : LI->getValues()) { 1798341825Sdim Record *Op = nullptr; 1799341825Sdim if (DagInit *Dag = dyn_cast<DagInit>(I)) 1800341825Sdim if (DefInit *DI = dyn_cast<DefInit>(Dag->getOperator())) 1801341825Sdim Op = DI->getDef(); 1802341825Sdim assert(Op && "Invalid Fragment"); 1803341825Sdim NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP)); 1804341825Sdim } 1805341825Sdim return NumResults; 1806205407Srdivacky } 1807218893Sdim 1808205407Srdivacky if (Operator->isSubClassOf("Instruction")) { 1809205407Srdivacky CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator); 1810206083Srdivacky 1811288943Sdim unsigned NumDefsToAdd = InstInfo.Operands.NumDefs; 1812218893Sdim 1813288943Sdim // Subtract any defaulted outputs. 1814288943Sdim for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) { 1815288943Sdim Record *OperandNode = InstInfo.Operands[i].Rec; 1816288943Sdim 1817288943Sdim if (OperandNode->isSubClassOf("OperandWithDefaultOps") && 1818288943Sdim !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 1819288943Sdim --NumDefsToAdd; 1820288943Sdim } 1821288943Sdim 1822206083Srdivacky // Add on one implicit def if it has a resolvable type. 1823206083Srdivacky if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other) 1824206083Srdivacky ++NumDefsToAdd; 1825206083Srdivacky return NumDefsToAdd; 1826205407Srdivacky } 1827218893Sdim 1828205407Srdivacky if (Operator->isSubClassOf("SDNodeXForm")) 1829205407Srdivacky return 1; // FIXME: Generalize SDNodeXForm 1830218893Sdim 1831276479Sdim if (Operator->isSubClassOf("ValueType")) 1832276479Sdim return 1; // A type-cast of one result. 1833276479Sdim 1834276479Sdim if (Operator->isSubClassOf("ComplexPattern")) 1835276479Sdim return 1; 1836276479Sdim 1837321369Sdim errs() << *Operator; 1838288943Sdim PrintFatalError("Unhandled node in GetNumNodeResults"); 1839205407Srdivacky} 1840193323Sed 1841195340Sedvoid TreePatternNode::print(raw_ostream &OS) const { 1842205407Srdivacky if (isLeaf()) 1843193323Sed OS << *getLeafValue(); 1844205407Srdivacky else 1845204642Srdivacky OS << '(' << getOperator()->getName(); 1846193323Sed 1847327952Sdim for (unsigned i = 0, e = Types.size(); i != e; ++i) { 1848327952Sdim OS << ':'; 1849327952Sdim getExtType(i).writeToStream(OS); 1850327952Sdim } 1851205407Srdivacky 1852193323Sed if (!isLeaf()) { 1853193323Sed if (getNumChildren() != 0) { 1854193323Sed OS << " "; 1855193323Sed getChild(0)->print(OS); 1856193323Sed for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 1857193323Sed OS << ", "; 1858193323Sed getChild(i)->print(OS); 1859193323Sed } 1860193323Sed } 1861193323Sed OS << ")"; 1862193323Sed } 1863218893Sdim 1864344779Sdim for (const TreePredicateCall &Pred : PredicateCalls) { 1865344779Sdim OS << "<<P:"; 1866344779Sdim if (Pred.Scope) 1867344779Sdim OS << Pred.Scope << ":"; 1868344779Sdim OS << Pred.Fn.getFnName() << ">>"; 1869344779Sdim } 1870193323Sed if (TransformFn) 1871193323Sed OS << "<<X:" << TransformFn->getName() << ">>"; 1872193323Sed if (!getName().empty()) 1873193323Sed OS << ":$" << getName(); 1874193323Sed 1875344779Sdim for (const ScopedName &Name : NamesAsPredicateArg) 1876344779Sdim OS << ":$pred:" << Name.getScope() << ":" << Name.getIdentifier(); 1877193323Sed} 1878193323Sedvoid TreePatternNode::dump() const { 1879195340Sed print(errs()); 1880193323Sed} 1881193323Sed 1882193323Sed/// isIsomorphicTo - Return true if this node is recursively 1883193323Sed/// isomorphic to the specified node. For this comparison, the node's 1884193323Sed/// entire state is considered. The assigned name is ignored, since 1885193323Sed/// nodes with differing names are considered isomorphic. However, if 1886193323Sed/// the assigned name is present in the dependent variable set, then 1887193323Sed/// the assigned name is considered significant and the node is 1888193323Sed/// isomorphic if the names match. 1889193323Sedbool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 1890193323Sed const MultipleUseVarSet &DepVars) const { 1891193323Sed if (N == this) return true; 1892205407Srdivacky if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 1893344779Sdim getPredicateCalls() != N->getPredicateCalls() || 1894193323Sed getTransformFn() != N->getTransformFn()) 1895193323Sed return false; 1896193323Sed 1897193323Sed if (isLeaf()) { 1898243830Sdim if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) { 1899243830Sdim if (DefInit *NDI = dyn_cast<DefInit>(N->getLeafValue())) { 1900193323Sed return ((DI->getDef() == NDI->getDef()) 1901193323Sed && (DepVars.find(getName()) == DepVars.end() 1902193323Sed || getName() == N->getName())); 1903193323Sed } 1904193323Sed } 1905193323Sed return getLeafValue() == N->getLeafValue(); 1906193323Sed } 1907218893Sdim 1908193323Sed if (N->getOperator() != getOperator() || 1909193323Sed N->getNumChildren() != getNumChildren()) return false; 1910193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1911193323Sed if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 1912193323Sed return false; 1913193323Sed return true; 1914193323Sed} 1915193323Sed 1916193323Sed/// clone - Make a copy of this tree and all of its children. 1917193323Sed/// 1918341825SdimTreePatternNodePtr TreePatternNode::clone() const { 1919341825Sdim TreePatternNodePtr New; 1920193323Sed if (isLeaf()) { 1921341825Sdim New = std::make_shared<TreePatternNode>(getLeafValue(), getNumTypes()); 1922193323Sed } else { 1923341825Sdim std::vector<TreePatternNodePtr> CChildren; 1924193323Sed CChildren.reserve(Children.size()); 1925193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1926193323Sed CChildren.push_back(getChild(i)->clone()); 1927341825Sdim New = std::make_shared<TreePatternNode>(getOperator(), std::move(CChildren), 1928341825Sdim getNumTypes()); 1929193323Sed } 1930193323Sed New->setName(getName()); 1931344779Sdim New->setNamesAsPredicateArg(getNamesAsPredicateArg()); 1932205407Srdivacky New->Types = Types; 1933344779Sdim New->setPredicateCalls(getPredicateCalls()); 1934193323Sed New->setTransformFn(getTransformFn()); 1935193323Sed return New; 1936193323Sed} 1937193323Sed 1938203954Srdivacky/// RemoveAllTypes - Recursively strip all the types of this tree. 1939203954Srdivackyvoid TreePatternNode::RemoveAllTypes() { 1940296417Sdim // Reset to unknown type. 1941327952Sdim std::fill(Types.begin(), Types.end(), TypeSetByHwMode()); 1942203954Srdivacky if (isLeaf()) return; 1943203954Srdivacky for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1944203954Srdivacky getChild(i)->RemoveAllTypes(); 1945203954Srdivacky} 1946203954Srdivacky 1947203954Srdivacky 1948193323Sed/// SubstituteFormalArguments - Replace the formal arguments in this tree 1949193323Sed/// with actual values specified by ArgMap. 1950341825Sdimvoid TreePatternNode::SubstituteFormalArguments( 1951341825Sdim std::map<std::string, TreePatternNodePtr> &ArgMap) { 1952193323Sed if (isLeaf()) return; 1953218893Sdim 1954193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1955193323Sed TreePatternNode *Child = getChild(i); 1956193323Sed if (Child->isLeaf()) { 1957193323Sed Init *Val = Child->getLeafValue(); 1958276479Sdim // Note that, when substituting into an output pattern, Val might be an 1959276479Sdim // UnsetInit. 1960276479Sdim if (isa<UnsetInit>(Val) || (isa<DefInit>(Val) && 1961276479Sdim cast<DefInit>(Val)->getDef()->getName() == "node")) { 1962193323Sed // We found a use of a formal argument, replace it with its value. 1963341825Sdim TreePatternNodePtr NewChild = ArgMap[Child->getName()]; 1964193323Sed assert(NewChild && "Couldn't find formal argument!"); 1965344779Sdim assert((Child->getPredicateCalls().empty() || 1966344779Sdim NewChild->getPredicateCalls() == Child->getPredicateCalls()) && 1967193323Sed "Non-empty child predicate clobbered!"); 1968341825Sdim setChild(i, std::move(NewChild)); 1969193323Sed } 1970193323Sed } else { 1971193323Sed getChild(i)->SubstituteFormalArguments(ArgMap); 1972193323Sed } 1973193323Sed } 1974193323Sed} 1975193323Sed 1976193323Sed 1977193323Sed/// InlinePatternFragments - If this pattern refers to any pattern 1978341825Sdim/// fragments, return the set of inlined versions (this can be more than 1979341825Sdim/// one if a PatFrags record has multiple alternatives). 1980341825Sdimvoid TreePatternNode::InlinePatternFragments( 1981341825Sdim TreePatternNodePtr T, TreePattern &TP, 1982341825Sdim std::vector<TreePatternNodePtr> &OutAlternatives) { 1983341825Sdim 1984243830Sdim if (TP.hasError()) 1985341825Sdim return; 1986243830Sdim 1987341825Sdim if (isLeaf()) { 1988341825Sdim OutAlternatives.push_back(T); // nothing to do. 1989341825Sdim return; 1990341825Sdim } 1991341825Sdim 1992193323Sed Record *Op = getOperator(); 1993218893Sdim 1994341825Sdim if (!Op->isSubClassOf("PatFrags")) { 1995341825Sdim if (getNumChildren() == 0) { 1996341825Sdim OutAlternatives.push_back(T); 1997341825Sdim return; 1998341825Sdim } 1999341825Sdim 2000341825Sdim // Recursively inline children nodes. 2001341825Sdim std::vector<std::vector<TreePatternNodePtr> > ChildAlternatives; 2002341825Sdim ChildAlternatives.resize(getNumChildren()); 2003193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 2004341825Sdim TreePatternNodePtr Child = getChildShared(i); 2005341825Sdim Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]); 2006341825Sdim // If there are no alternatives for any child, there are no 2007341825Sdim // alternatives for this expression as whole. 2008341825Sdim if (ChildAlternatives[i].empty()) 2009341825Sdim return; 2010193323Sed 2011341825Sdim for (auto NewChild : ChildAlternatives[i]) 2012344779Sdim assert((Child->getPredicateCalls().empty() || 2013344779Sdim NewChild->getPredicateCalls() == Child->getPredicateCalls()) && 2014341825Sdim "Non-empty child predicate clobbered!"); 2015341825Sdim } 2016193323Sed 2017341825Sdim // The end result is an all-pairs construction of the resultant pattern. 2018341825Sdim std::vector<unsigned> Idxs; 2019341825Sdim Idxs.resize(ChildAlternatives.size()); 2020341825Sdim bool NotDone; 2021341825Sdim do { 2022341825Sdim // Create the variant and add it to the output list. 2023341825Sdim std::vector<TreePatternNodePtr> NewChildren; 2024341825Sdim for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i) 2025341825Sdim NewChildren.push_back(ChildAlternatives[i][Idxs[i]]); 2026341825Sdim TreePatternNodePtr R = std::make_shared<TreePatternNode>( 2027341825Sdim getOperator(), std::move(NewChildren), getNumTypes()); 2028341825Sdim 2029341825Sdim // Copy over properties. 2030341825Sdim R->setName(getName()); 2031344779Sdim R->setNamesAsPredicateArg(getNamesAsPredicateArg()); 2032344779Sdim R->setPredicateCalls(getPredicateCalls()); 2033341825Sdim R->setTransformFn(getTransformFn()); 2034341825Sdim for (unsigned i = 0, e = getNumTypes(); i != e; ++i) 2035341825Sdim R->setType(i, getExtType(i)); 2036344779Sdim for (unsigned i = 0, e = getNumResults(); i != e; ++i) 2037344779Sdim R->setResultIndex(i, getResultIndex(i)); 2038341825Sdim 2039341825Sdim // Register alternative. 2040341825Sdim OutAlternatives.push_back(R); 2041341825Sdim 2042341825Sdim // Increment indices to the next permutation by incrementing the 2043341825Sdim // indices from last index backward, e.g., generate the sequence 2044341825Sdim // [0, 0], [0, 1], [1, 0], [1, 1]. 2045341825Sdim int IdxsIdx; 2046341825Sdim for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 2047341825Sdim if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size()) 2048341825Sdim Idxs[IdxsIdx] = 0; 2049341825Sdim else 2050341825Sdim break; 2051341825Sdim } 2052341825Sdim NotDone = (IdxsIdx >= 0); 2053341825Sdim } while (NotDone); 2054341825Sdim 2055341825Sdim return; 2056193323Sed } 2057193323Sed 2058193323Sed // Otherwise, we found a reference to a fragment. First, look up its 2059193323Sed // TreePattern record. 2060193323Sed TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 2061218893Sdim 2062193323Sed // Verify that we are passing the right number of operands. 2063243830Sdim if (Frag->getNumArgs() != Children.size()) { 2064193323Sed TP.error("'" + Op->getName() + "' fragment requires " + 2065327952Sdim Twine(Frag->getNumArgs()) + " operands!"); 2066341825Sdim return; 2067243830Sdim } 2068193323Sed 2069344779Sdim TreePredicateFn PredFn(Frag); 2070344779Sdim unsigned Scope = 0; 2071344779Sdim if (TreePredicateFn(Frag).usesOperands()) 2072344779Sdim Scope = TP.getDAGPatterns().allocateScope(); 2073344779Sdim 2074341825Sdim // Compute the map of formal to actual arguments. 2075341825Sdim std::map<std::string, TreePatternNodePtr> ArgMap; 2076341825Sdim for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) { 2077344779Sdim TreePatternNodePtr Child = getChildShared(i); 2078344779Sdim if (Scope != 0) { 2079344779Sdim Child = Child->clone(); 2080344779Sdim Child->addNameAsPredicateArg(ScopedName(Scope, Frag->getArgName(i))); 2081344779Sdim } 2082341825Sdim ArgMap[Frag->getArgName(i)] = Child; 2083341825Sdim } 2084193323Sed 2085341825Sdim // Loop over all fragment alternatives. 2086341825Sdim for (auto Alternative : Frag->getTrees()) { 2087341825Sdim TreePatternNodePtr FragTree = Alternative->clone(); 2088193323Sed 2089341825Sdim if (!PredFn.isAlwaysTrue()) 2090344779Sdim FragTree->addPredicateCall(PredFn, Scope); 2091218893Sdim 2092341825Sdim // Resolve formal arguments to their actual value. 2093341825Sdim if (Frag->getNumArgs()) 2094341825Sdim FragTree->SubstituteFormalArguments(ArgMap); 2095218893Sdim 2096341825Sdim // Transfer types. Note that the resolved alternative may have fewer 2097341825Sdim // (but not more) results than the PatFrags node. 2098341825Sdim FragTree->setName(getName()); 2099341825Sdim for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i) 2100341825Sdim FragTree->UpdateNodeType(i, getExtType(i), TP); 2101193323Sed 2102341825Sdim // Transfer in the old predicates. 2103344779Sdim for (const TreePredicateCall &Pred : getPredicateCalls()) 2104344779Sdim FragTree->addPredicateCall(Pred); 2105193323Sed 2106341825Sdim // The fragment we inlined could have recursive inlining that is needed. See 2107341825Sdim // if there are any pattern fragments in it and inline them as needed. 2108341825Sdim FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives); 2109341825Sdim } 2110193323Sed} 2111193323Sed 2112193323Sed/// getImplicitType - Check to see if the specified record has an implicit 2113194612Sed/// type which should be applied to it. This will infer the type of register 2114193323Sed/// references from the register file information, for example. 2115193323Sed/// 2116249423Sdim/// When Unnamed is set, return the type of a DAG operand with no name, such as 2117249423Sdim/// the F8RC register class argument in: 2118249423Sdim/// 2119249423Sdim/// (COPY_TO_REGCLASS GPR:$src, F8RC) 2120249423Sdim/// 2121249423Sdim/// When Unnamed is false, return the type of a named DAG operand such as the 2122249423Sdim/// GPR:$src operand above. 2123249423Sdim/// 2124327952Sdimstatic TypeSetByHwMode getImplicitType(Record *R, unsigned ResNo, 2125327952Sdim bool NotRegisters, 2126327952Sdim bool Unnamed, 2127327952Sdim TreePattern &TP) { 2128327952Sdim CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 2129327952Sdim 2130224145Sdim // Check to see if this is a register operand. 2131224145Sdim if (R->isSubClassOf("RegisterOperand")) { 2132224145Sdim assert(ResNo == 0 && "Regoperand ref only has one result!"); 2133224145Sdim if (NotRegisters) 2134327952Sdim return TypeSetByHwMode(); // Unknown. 2135224145Sdim Record *RegClass = R->getValueAsDef("RegClass"); 2136224145Sdim const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 2137327952Sdim return TypeSetByHwMode(T.getRegisterClass(RegClass).getValueTypes()); 2138224145Sdim } 2139224145Sdim 2140205218Srdivacky // Check to see if this is a register or a register class. 2141193323Sed if (R->isSubClassOf("RegisterClass")) { 2142206083Srdivacky assert(ResNo == 0 && "Regclass ref only has one result!"); 2143249423Sdim // An unnamed register class represents itself as an i32 immediate, for 2144249423Sdim // example on a COPY_TO_REGCLASS instruction. 2145249423Sdim if (Unnamed) 2146327952Sdim return TypeSetByHwMode(MVT::i32); 2147249423Sdim 2148249423Sdim // In a named operand, the register class provides the possible set of 2149249423Sdim // types. 2150218893Sdim if (NotRegisters) 2151327952Sdim return TypeSetByHwMode(); // Unknown. 2152205218Srdivacky const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 2153327952Sdim return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes()); 2154206083Srdivacky } 2155218893Sdim 2156341825Sdim if (R->isSubClassOf("PatFrags")) { 2157206083Srdivacky assert(ResNo == 0 && "FIXME: PatFrag with multiple results?"); 2158193323Sed // Pattern fragment types will be resolved when they are inlined. 2159327952Sdim return TypeSetByHwMode(); // Unknown. 2160206083Srdivacky } 2161218893Sdim 2162206083Srdivacky if (R->isSubClassOf("Register")) { 2163206083Srdivacky assert(ResNo == 0 && "Registers only produce one result!"); 2164218893Sdim if (NotRegisters) 2165327952Sdim return TypeSetByHwMode(); // Unknown. 2166193323Sed const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 2167327952Sdim return TypeSetByHwMode(T.getRegisterVTs(R)); 2168206083Srdivacky } 2169208599Srdivacky 2170208599Srdivacky if (R->isSubClassOf("SubRegIndex")) { 2171208599Srdivacky assert(ResNo == 0 && "SubRegisterIndices only produce one result!"); 2172327952Sdim return TypeSetByHwMode(MVT::i32); 2173208599Srdivacky } 2174218893Sdim 2175249423Sdim if (R->isSubClassOf("ValueType")) { 2176206083Srdivacky assert(ResNo == 0 && "This node only has one result!"); 2177249423Sdim // An unnamed VTSDNode represents itself as an MVT::Other immediate. 2178249423Sdim // 2179249423Sdim // (sext_inreg GPR:$src, i16) 2180249423Sdim // ~~~ 2181249423Sdim if (Unnamed) 2182327952Sdim return TypeSetByHwMode(MVT::Other); 2183249423Sdim // With a name, the ValueType simply provides the type of the named 2184249423Sdim // variable. 2185249423Sdim // 2186249423Sdim // (sext_inreg i32:$src, i16) 2187249423Sdim // ~~~~~~~~ 2188249423Sdim if (NotRegisters) 2189327952Sdim return TypeSetByHwMode(); // Unknown. 2190327952Sdim const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes(); 2191327952Sdim return TypeSetByHwMode(getValueTypeByHwMode(R, CGH)); 2192249423Sdim } 2193249423Sdim 2194249423Sdim if (R->isSubClassOf("CondCode")) { 2195249423Sdim assert(ResNo == 0 && "This node only has one result!"); 2196249423Sdim // Using a CondCodeSDNode. 2197327952Sdim return TypeSetByHwMode(MVT::Other); 2198206083Srdivacky } 2199218893Sdim 2200206083Srdivacky if (R->isSubClassOf("ComplexPattern")) { 2201206083Srdivacky assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?"); 2202218893Sdim if (NotRegisters) 2203327952Sdim return TypeSetByHwMode(); // Unknown. 2204327952Sdim return TypeSetByHwMode(CDP.getComplexPattern(R).getValueType()); 2205206083Srdivacky } 2206206083Srdivacky if (R->isSubClassOf("PointerLikeRegClass")) { 2207206083Srdivacky assert(ResNo == 0 && "Regclass can only have one result!"); 2208327952Sdim TypeSetByHwMode VTS(MVT::iPTR); 2209327952Sdim TP.getInfer().expandOverloads(VTS); 2210327952Sdim return VTS; 2211206083Srdivacky } 2212218893Sdim 2213206083Srdivacky if (R->getName() == "node" || R->getName() == "srcvalue" || 2214353358Sdim R->getName() == "zero_reg" || R->getName() == "immAllOnesV" || 2215353358Sdim R->getName() == "immAllZerosV" || R->getName() == "undef_tied_input") { 2216193323Sed // Placeholder. 2217327952Sdim return TypeSetByHwMode(); // Unknown. 2218193323Sed } 2219218893Sdim 2220327952Sdim if (R->isSubClassOf("Operand")) { 2221327952Sdim const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes(); 2222327952Sdim Record *T = R->getValueAsDef("Type"); 2223327952Sdim return TypeSetByHwMode(getValueTypeByHwMode(T, CGH)); 2224327952Sdim } 2225276479Sdim 2226193323Sed TP.error("Unknown node flavor used in pattern: " + R->getName()); 2227327952Sdim return TypeSetByHwMode(MVT::Other); 2228193323Sed} 2229193323Sed 2230193323Sed 2231193323Sed/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 2232193323Sed/// CodeGenIntrinsic information for it, otherwise return a null pointer. 2233193323Sedconst CodeGenIntrinsic *TreePatternNode:: 2234193323SedgetIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 2235193323Sed if (getOperator() != CDP.get_intrinsic_void_sdnode() && 2236193323Sed getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 2237193323Sed getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 2238276479Sdim return nullptr; 2239218893Sdim 2240243830Sdim unsigned IID = cast<IntInit>(getChild(0)->getLeafValue())->getValue(); 2241193323Sed return &CDP.getIntrinsicInfo(IID); 2242193323Sed} 2243193323Sed 2244203954Srdivacky/// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 2245203954Srdivacky/// return the ComplexPattern information, otherwise return null. 2246203954Srdivackyconst ComplexPattern * 2247203954SrdivackyTreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { 2248276479Sdim Record *Rec; 2249276479Sdim if (isLeaf()) { 2250276479Sdim DefInit *DI = dyn_cast<DefInit>(getLeafValue()); 2251276479Sdim if (!DI) 2252276479Sdim return nullptr; 2253276479Sdim Rec = DI->getDef(); 2254276479Sdim } else 2255276479Sdim Rec = getOperator(); 2256218893Sdim 2257276479Sdim if (!Rec->isSubClassOf("ComplexPattern")) 2258276479Sdim return nullptr; 2259276479Sdim return &CGP.getComplexPattern(Rec); 2260203954Srdivacky} 2261203954Srdivacky 2262276479Sdimunsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const { 2263276479Sdim // A ComplexPattern specifically declares how many results it fills in. 2264276479Sdim if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 2265276479Sdim return CP->getNumOperands(); 2266276479Sdim 2267276479Sdim // If MIOperandInfo is specified, that gives the count. 2268276479Sdim if (isLeaf()) { 2269276479Sdim DefInit *DI = dyn_cast<DefInit>(getLeafValue()); 2270276479Sdim if (DI && DI->getDef()->isSubClassOf("Operand")) { 2271276479Sdim DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo"); 2272276479Sdim if (MIOps->getNumArgs()) 2273276479Sdim return MIOps->getNumArgs(); 2274276479Sdim } 2275276479Sdim } 2276276479Sdim 2277276479Sdim // Otherwise there is just one result. 2278276479Sdim return 1; 2279276479Sdim} 2280276479Sdim 2281203954Srdivacky/// NodeHasProperty - Return true if this node has the specified property. 2282203954Srdivackybool TreePatternNode::NodeHasProperty(SDNP Property, 2283203954Srdivacky const CodeGenDAGPatterns &CGP) const { 2284203954Srdivacky if (isLeaf()) { 2285203954Srdivacky if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 2286203954Srdivacky return CP->hasProperty(Property); 2287327952Sdim 2288203954Srdivacky return false; 2289203954Srdivacky } 2290218893Sdim 2291327952Sdim if (Property != SDNPHasChain) { 2292327952Sdim // The chain proprety is already present on the different intrinsic node 2293327952Sdim // types (intrinsic_w_chain, intrinsic_void), and is not explicitly listed 2294327952Sdim // on the intrinsic. Anything else is specific to the individual intrinsic. 2295327952Sdim if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CGP)) 2296327952Sdim return Int->hasProperty(Property); 2297327952Sdim } 2298218893Sdim 2299327952Sdim if (!Operator->isSubClassOf("SDPatternOperator")) 2300327952Sdim return false; 2301327952Sdim 2302203954Srdivacky return CGP.getSDNodeInfo(Operator).hasProperty(Property); 2303203954Srdivacky} 2304203954Srdivacky 2305203954Srdivacky 2306203954Srdivacky 2307203954Srdivacky 2308203954Srdivacky/// TreeHasProperty - Return true if any node in this tree has the specified 2309203954Srdivacky/// property. 2310203954Srdivackybool TreePatternNode::TreeHasProperty(SDNP Property, 2311203954Srdivacky const CodeGenDAGPatterns &CGP) const { 2312203954Srdivacky if (NodeHasProperty(Property, CGP)) 2313203954Srdivacky return true; 2314203954Srdivacky for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2315203954Srdivacky if (getChild(i)->TreeHasProperty(Property, CGP)) 2316203954Srdivacky return true; 2317203954Srdivacky return false; 2318218893Sdim} 2319203954Srdivacky 2320193323Sed/// isCommutativeIntrinsic - Return true if the node corresponds to a 2321193323Sed/// commutative intrinsic. 2322193323Sedbool 2323193323SedTreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { 2324193323Sed if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) 2325193323Sed return Int->isCommutative; 2326193323Sed return false; 2327193323Sed} 2328193323Sed 2329280031Sdimstatic bool isOperandClass(const TreePatternNode *N, StringRef Class) { 2330280031Sdim if (!N->isLeaf()) 2331280031Sdim return N->getOperator()->isSubClassOf(Class); 2332193323Sed 2333280031Sdim DefInit *DI = dyn_cast<DefInit>(N->getLeafValue()); 2334280031Sdim if (DI && DI->getDef()->isSubClassOf(Class)) 2335280031Sdim return true; 2336280031Sdim 2337280031Sdim return false; 2338280031Sdim} 2339280031Sdim 2340280031Sdimstatic void emitTooManyOperandsError(TreePattern &TP, 2341280031Sdim StringRef InstName, 2342280031Sdim unsigned Expected, 2343280031Sdim unsigned Actual) { 2344280031Sdim TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) + 2345280031Sdim " operands but expected only " + Twine(Expected) + "!"); 2346280031Sdim} 2347280031Sdim 2348280031Sdimstatic void emitTooFewOperandsError(TreePattern &TP, 2349280031Sdim StringRef InstName, 2350280031Sdim unsigned Actual) { 2351280031Sdim TP.error("Instruction '" + InstName + 2352280031Sdim "' expects more than the provided " + Twine(Actual) + " operands!"); 2353280031Sdim} 2354280031Sdim 2355193323Sed/// ApplyTypeConstraints - Apply all of the type constraints relevant to 2356193323Sed/// this node and its children in the tree. This returns true if it makes a 2357243830Sdim/// change, false otherwise. If a type contradiction is found, flag an error. 2358193323Sedbool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 2359243830Sdim if (TP.hasError()) 2360243830Sdim return false; 2361243830Sdim 2362193323Sed CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 2363193323Sed if (isLeaf()) { 2364243830Sdim if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) { 2365193323Sed // If it's a regclass or something else known, include the type. 2366205407Srdivacky bool MadeChange = false; 2367205407Srdivacky for (unsigned i = 0, e = Types.size(); i != e; ++i) 2368205407Srdivacky MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i, 2369249423Sdim NotRegisters, 2370249423Sdim !hasName(), TP), TP); 2371205407Srdivacky return MadeChange; 2372203954Srdivacky } 2373218893Sdim 2374243830Sdim if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) { 2375205407Srdivacky assert(Types.size() == 1 && "Invalid IntInit"); 2376218893Sdim 2377193323Sed // Int inits are always integers. :) 2378327952Sdim bool MadeChange = TP.getInfer().EnforceInteger(Types[0]); 2379218893Sdim 2380327952Sdim if (!TP.getInfer().isConcrete(Types[0], false)) 2381205218Srdivacky return MadeChange; 2382218893Sdim 2383327952Sdim ValueTypeByHwMode VVT = TP.getInfer().getConcrete(Types[0], false); 2384327952Sdim for (auto &P : VVT) { 2385327952Sdim MVT::SimpleValueType VT = P.second.SimpleTy; 2386327952Sdim if (VT == MVT::iPTR || VT == MVT::iPTRAny) 2387327952Sdim continue; 2388327952Sdim unsigned Size = MVT(VT).getSizeInBits(); 2389327952Sdim // Make sure that the value is representable for this type. 2390327952Sdim if (Size >= 32) 2391327952Sdim continue; 2392327952Sdim // Check that the value doesn't use more bits than we have. It must 2393327952Sdim // either be a sign- or zero-extended equivalent of the original. 2394327952Sdim int64_t SignBitAndAbove = II->getValue() >> (Size - 1); 2395327952Sdim if (SignBitAndAbove == -1 || SignBitAndAbove == 0 || 2396327952Sdim SignBitAndAbove == 1) 2397327952Sdim continue; 2398218893Sdim 2399327952Sdim TP.error("Integer value '" + Twine(II->getValue()) + 2400327952Sdim "' is out of range for type '" + getEnumName(VT) + "'!"); 2401327952Sdim break; 2402327952Sdim } 2403327952Sdim return MadeChange; 2404327952Sdim } 2405218893Sdim 2406193323Sed return false; 2407193323Sed } 2408218893Sdim 2409204642Srdivacky if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 2410193323Sed bool MadeChange = false; 2411193323Sed 2412193323Sed // Apply the result type to the node. 2413193323Sed unsigned NumRetVTs = Int->IS.RetVTs.size(); 2414193323Sed unsigned NumParamVTs = Int->IS.ParamVTs.size(); 2415218893Sdim 2416193323Sed for (unsigned i = 0, e = NumRetVTs; i != e; ++i) 2417205407Srdivacky MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP); 2418193323Sed 2419243830Sdim if (getNumChildren() != NumParamVTs + 1) { 2420327952Sdim TP.error("Intrinsic '" + Int->Name + "' expects " + Twine(NumParamVTs) + 2421327952Sdim " operands, not " + Twine(getNumChildren() - 1) + " operands!"); 2422243830Sdim return false; 2423243830Sdim } 2424193323Sed 2425193323Sed // Apply type info to the intrinsic ID. 2426205407Srdivacky MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP); 2427218893Sdim 2428205407Srdivacky for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) { 2429205407Srdivacky MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters); 2430218893Sdim 2431205407Srdivacky MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i]; 2432205407Srdivacky assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case"); 2433205407Srdivacky MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP); 2434193323Sed } 2435193323Sed return MadeChange; 2436204642Srdivacky } 2437218893Sdim 2438204642Srdivacky if (getOperator()->isSubClassOf("SDNode")) { 2439193323Sed const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 2440218893Sdim 2441206083Srdivacky // Check that the number of operands is sane. Negative operands -> varargs. 2442206083Srdivacky if (NI.getNumOperands() >= 0 && 2443243830Sdim getNumChildren() != (unsigned)NI.getNumOperands()) { 2444206083Srdivacky TP.error(getOperator()->getName() + " node requires exactly " + 2445327952Sdim Twine(NI.getNumOperands()) + " operands!"); 2446243830Sdim return false; 2447243830Sdim } 2448218893Sdim 2449327952Sdim bool MadeChange = false; 2450193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2451193323Sed MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 2452327952Sdim MadeChange |= NI.ApplyTypeConstraints(this, TP); 2453205407Srdivacky return MadeChange; 2454204642Srdivacky } 2455218893Sdim 2456204642Srdivacky if (getOperator()->isSubClassOf("Instruction")) { 2457193323Sed const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 2458193323Sed CodeGenInstruction &InstInfo = 2459205407Srdivacky CDP.getTargetInfo().getInstruction(getOperator()); 2460218893Sdim 2461206083Srdivacky bool MadeChange = false; 2462206083Srdivacky 2463206083Srdivacky // Apply the result types to the node, these come from the things in the 2464206083Srdivacky // (outs) list of the instruction. 2465288943Sdim unsigned NumResultsToAdd = std::min(InstInfo.Operands.NumDefs, 2466288943Sdim Inst.getNumResults()); 2467249423Sdim for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo) 2468249423Sdim MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP); 2469218893Sdim 2470206083Srdivacky // If the instruction has implicit defs, we apply the first one as a result. 2471206083Srdivacky // FIXME: This sucks, it should apply all implicit defs. 2472206083Srdivacky if (!InstInfo.ImplicitDefs.empty()) { 2473206083Srdivacky unsigned ResNo = NumResultsToAdd; 2474218893Sdim 2475206083Srdivacky // FIXME: Generalize to multiple possible types and multiple possible 2476206083Srdivacky // ImplicitDefs. 2477206083Srdivacky MVT::SimpleValueType VT = 2478206083Srdivacky InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()); 2479218893Sdim 2480206083Srdivacky if (VT != MVT::Other) 2481206083Srdivacky MadeChange |= UpdateNodeType(ResNo, VT, TP); 2482206083Srdivacky } 2483218893Sdim 2484205218Srdivacky // If this is an INSERT_SUBREG, constrain the source and destination VTs to 2485205218Srdivacky // be the same. 2486205218Srdivacky if (getOperator()->getName() == "INSERT_SUBREG") { 2487205407Srdivacky assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); 2488205407Srdivacky MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); 2489205407Srdivacky MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); 2490280031Sdim } else if (getOperator()->getName() == "REG_SEQUENCE") { 2491280031Sdim // We need to do extra, custom typechecking for REG_SEQUENCE since it is 2492280031Sdim // variadic. 2493280031Sdim 2494280031Sdim unsigned NChild = getNumChildren(); 2495280031Sdim if (NChild < 3) { 2496280031Sdim TP.error("REG_SEQUENCE requires at least 3 operands!"); 2497280031Sdim return false; 2498280031Sdim } 2499280031Sdim 2500280031Sdim if (NChild % 2 == 0) { 2501280031Sdim TP.error("REG_SEQUENCE requires an odd number of operands!"); 2502280031Sdim return false; 2503280031Sdim } 2504280031Sdim 2505280031Sdim if (!isOperandClass(getChild(0), "RegisterClass")) { 2506280031Sdim TP.error("REG_SEQUENCE requires a RegisterClass for first operand!"); 2507280031Sdim return false; 2508280031Sdim } 2509280031Sdim 2510280031Sdim for (unsigned I = 1; I < NChild; I += 2) { 2511280031Sdim TreePatternNode *SubIdxChild = getChild(I + 1); 2512280031Sdim if (!isOperandClass(SubIdxChild, "SubRegIndex")) { 2513280031Sdim TP.error("REG_SEQUENCE requires a SubRegIndex for operand " + 2514327952Sdim Twine(I + 1) + "!"); 2515280031Sdim return false; 2516280031Sdim } 2517280031Sdim } 2518205218Srdivacky } 2519193323Sed 2520353358Sdim // If one or more operands with a default value appear at the end of the 2521353358Sdim // formal operand list for an instruction, we allow them to be overridden 2522353358Sdim // by optional operands provided in the pattern. 2523353358Sdim // 2524353358Sdim // But if an operand B without a default appears at any point after an 2525353358Sdim // operand A with a default, then we don't allow A to be overridden, 2526353358Sdim // because there would be no way to specify whether the next operand in 2527353358Sdim // the pattern was intended to override A or skip it. 2528353358Sdim unsigned NonOverridableOperands = Inst.getNumOperands(); 2529353358Sdim while (NonOverridableOperands > 0 && 2530353358Sdim CDP.operandHasDefault(Inst.getOperand(NonOverridableOperands-1))) 2531353358Sdim --NonOverridableOperands; 2532353358Sdim 2533193323Sed unsigned ChildNo = 0; 2534193323Sed for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 2535193323Sed Record *OperandNode = Inst.getOperand(i); 2536218893Sdim 2537353358Sdim // If the operand has a default value, do we use it? We must use the 2538353358Sdim // default if we've run out of children of the pattern DAG to consume, 2539353358Sdim // or if the operand is followed by a non-defaulted one. 2540353358Sdim if (CDP.operandHasDefault(OperandNode) && 2541353358Sdim (i < NonOverridableOperands || ChildNo >= getNumChildren())) 2542193323Sed continue; 2543218893Sdim 2544353358Sdim // If we have run out of child nodes and there _isn't_ a default 2545353358Sdim // value we can use for the next operand, give an error. 2546243830Sdim if (ChildNo >= getNumChildren()) { 2547280031Sdim emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren()); 2548243830Sdim return false; 2549243830Sdim } 2550218893Sdim 2551193323Sed TreePatternNode *Child = getChild(ChildNo++); 2552206083Srdivacky unsigned ChildResNo = 0; // Instructions always use res #0 of their op. 2553218893Sdim 2554249423Sdim // If the operand has sub-operands, they may be provided by distinct 2555249423Sdim // child patterns, so attempt to match each sub-operand separately. 2556249423Sdim if (OperandNode->isSubClassOf("Operand")) { 2557249423Sdim DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo"); 2558249423Sdim if (unsigned NumArgs = MIOpInfo->getNumArgs()) { 2559249423Sdim // But don't do that if the whole operand is being provided by 2560276479Sdim // a single ComplexPattern-related Operand. 2561276479Sdim 2562276479Sdim if (Child->getNumMIResults(CDP) < NumArgs) { 2563249423Sdim // Match first sub-operand against the child we already have. 2564249423Sdim Record *SubRec = cast<DefInit>(MIOpInfo->getArg(0))->getDef(); 2565249423Sdim MadeChange |= 2566249423Sdim Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP); 2567234353Sdim 2568249423Sdim // And the remaining sub-operands against subsequent children. 2569249423Sdim for (unsigned Arg = 1; Arg < NumArgs; ++Arg) { 2570249423Sdim if (ChildNo >= getNumChildren()) { 2571280031Sdim emitTooFewOperandsError(TP, getOperator()->getName(), 2572280031Sdim getNumChildren()); 2573249423Sdim return false; 2574249423Sdim } 2575249423Sdim Child = getChild(ChildNo++); 2576249423Sdim 2577249423Sdim SubRec = cast<DefInit>(MIOpInfo->getArg(Arg))->getDef(); 2578249423Sdim MadeChange |= 2579249423Sdim Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP); 2580249423Sdim } 2581249423Sdim continue; 2582249423Sdim } 2583249423Sdim } 2584249423Sdim } 2585249423Sdim 2586249423Sdim // If we didn't match by pieces above, attempt to match the whole 2587249423Sdim // operand now. 2588249423Sdim MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP); 2589193323Sed } 2590193323Sed 2591280031Sdim if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) { 2592280031Sdim emitTooManyOperandsError(TP, getOperator()->getName(), 2593280031Sdim ChildNo, getNumChildren()); 2594243830Sdim return false; 2595243830Sdim } 2596218893Sdim 2597249423Sdim for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2598249423Sdim MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 2599193323Sed return MadeChange; 2600204642Srdivacky } 2601218893Sdim 2602276479Sdim if (getOperator()->isSubClassOf("ComplexPattern")) { 2603276479Sdim bool MadeChange = false; 2604276479Sdim 2605276479Sdim for (unsigned i = 0; i < getNumChildren(); ++i) 2606276479Sdim MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 2607276479Sdim 2608276479Sdim return MadeChange; 2609276479Sdim } 2610276479Sdim 2611204642Srdivacky assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 2612218893Sdim 2613204642Srdivacky // Node transforms always take one operand. 2614243830Sdim if (getNumChildren() != 1) { 2615204642Srdivacky TP.error("Node transform '" + getOperator()->getName() + 2616204642Srdivacky "' requires one operand!"); 2617243830Sdim return false; 2618243830Sdim } 2619193323Sed 2620205218Srdivacky bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 2621205218Srdivacky return MadeChange; 2622193323Sed} 2623193323Sed 2624193323Sed/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 2625193323Sed/// RHS of a commutative operation, not the on LHS. 2626193323Sedstatic bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 2627193323Sed if (!N->isLeaf() && N->getOperator()->getName() == "imm") 2628193323Sed return true; 2629243830Sdim if (N->isLeaf() && isa<IntInit>(N->getLeafValue())) 2630193323Sed return true; 2631193323Sed return false; 2632193323Sed} 2633193323Sed 2634193323Sed 2635193323Sed/// canPatternMatch - If it is impossible for this pattern to match on this 2636193323Sed/// target, fill in Reason and return false. Otherwise, return true. This is 2637193323Sed/// used as a sanity check for .td files (to prevent people from writing stuff 2638193323Sed/// that can never possibly work), and to prevent the pattern permuter from 2639193323Sed/// generating stuff that is useless. 2640218893Sdimbool TreePatternNode::canPatternMatch(std::string &Reason, 2641193323Sed const CodeGenDAGPatterns &CDP) { 2642193323Sed if (isLeaf()) return true; 2643193323Sed 2644193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2645193323Sed if (!getChild(i)->canPatternMatch(Reason, CDP)) 2646193323Sed return false; 2647193323Sed 2648193323Sed // If this is an intrinsic, handle cases that would make it not match. For 2649193323Sed // example, if an operand is required to be an immediate. 2650193323Sed if (getOperator()->isSubClassOf("Intrinsic")) { 2651193323Sed // TODO: 2652193323Sed return true; 2653193323Sed } 2654218893Sdim 2655276479Sdim if (getOperator()->isSubClassOf("ComplexPattern")) 2656276479Sdim return true; 2657276479Sdim 2658193323Sed // If this node is a commutative operator, check that the LHS isn't an 2659193323Sed // immediate. 2660193323Sed const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 2661193323Sed bool isCommIntrinsic = isCommutativeIntrinsic(CDP); 2662193323Sed if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 2663193323Sed // Scan all of the operands of the node and make sure that only the last one 2664193323Sed // is a constant node, unless the RHS also is. 2665193323Sed if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 2666314564Sdim unsigned Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id. 2667193323Sed for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i) 2668193323Sed if (OnlyOnRHSOfCommutative(getChild(i))) { 2669193323Sed Reason="Immediate value must be on the RHS of commutative operators!"; 2670193323Sed return false; 2671193323Sed } 2672193323Sed } 2673193323Sed } 2674218893Sdim 2675193323Sed return true; 2676193323Sed} 2677193323Sed 2678193323Sed//===----------------------------------------------------------------------===// 2679193323Sed// TreePattern implementation 2680193323Sed// 2681193323Sed 2682193323SedTreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 2683243830Sdim CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2684327952Sdim isInputPattern(isInput), HasError(false), 2685327952Sdim Infer(*this) { 2686288943Sdim for (Init *I : RawPat->getValues()) 2687288943Sdim Trees.push_back(ParseTreePattern(I, "")); 2688193323Sed} 2689193323Sed 2690193323SedTreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 2691243830Sdim CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2692327952Sdim isInputPattern(isInput), HasError(false), 2693327952Sdim Infer(*this) { 2694206083Srdivacky Trees.push_back(ParseTreePattern(Pat, "")); 2695193323Sed} 2696193323Sed 2697341825SdimTreePattern::TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput, 2698341825Sdim CodeGenDAGPatterns &cdp) 2699341825Sdim : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false), 2700341825Sdim Infer(*this) { 2701193323Sed Trees.push_back(Pat); 2702193323Sed} 2703193323Sed 2704280031Sdimvoid TreePattern::error(const Twine &Msg) { 2705243830Sdim if (HasError) 2706243830Sdim return; 2707193323Sed dump(); 2708243830Sdim PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); 2709243830Sdim HasError = true; 2710193323Sed} 2711193323Sed 2712205218Srdivackyvoid TreePattern::ComputeNamedNodes() { 2713341825Sdim for (TreePatternNodePtr &Tree : Trees) 2714341825Sdim ComputeNamedNodes(Tree.get()); 2715205218Srdivacky} 2716205218Srdivacky 2717205218Srdivackyvoid TreePattern::ComputeNamedNodes(TreePatternNode *N) { 2718205218Srdivacky if (!N->getName().empty()) 2719205218Srdivacky NamedNodes[N->getName()].push_back(N); 2720218893Sdim 2721205218Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2722205218Srdivacky ComputeNamedNodes(N->getChild(i)); 2723205218Srdivacky} 2724205218Srdivacky 2725341825SdimTreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit, 2726341825Sdim StringRef OpName) { 2727243830Sdim if (DefInit *DI = dyn_cast<DefInit>(TheInit)) { 2728206083Srdivacky Record *R = DI->getDef(); 2729218893Sdim 2730206083Srdivacky // Direct reference to a leaf DagNode or PatFrag? Turn it into a 2731224145Sdim // TreePatternNode of its own. For example: 2732206083Srdivacky /// (foo GPR, imm) -> (foo GPR, (imm)) 2733341825Sdim if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrags")) 2734226633Sdim return ParseTreePattern( 2735314564Sdim DagInit::get(DI, nullptr, 2736314564Sdim std::vector<std::pair<Init*, StringInit*> >()), 2737226633Sdim OpName); 2738218893Sdim 2739206083Srdivacky // Input argument? 2740341825Sdim TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1); 2741206083Srdivacky if (R->getName() == "node" && !OpName.empty()) { 2742206083Srdivacky if (OpName.empty()) 2743206083Srdivacky error("'node' argument requires a name to match with operand list"); 2744206083Srdivacky Args.push_back(OpName); 2745206083Srdivacky } 2746206083Srdivacky 2747206083Srdivacky Res->setName(OpName); 2748206083Srdivacky return Res; 2749206083Srdivacky } 2750218893Sdim 2751249423Sdim // ?:$name or just $name. 2752288943Sdim if (isa<UnsetInit>(TheInit)) { 2753249423Sdim if (OpName.empty()) 2754249423Sdim error("'?' argument requires a name to match with operand list"); 2755341825Sdim TreePatternNodePtr Res = std::make_shared<TreePatternNode>(TheInit, 1); 2756249423Sdim Args.push_back(OpName); 2757249423Sdim Res->setName(OpName); 2758249423Sdim return Res; 2759249423Sdim } 2760249423Sdim 2761341825Sdim if (isa<IntInit>(TheInit) || isa<BitInit>(TheInit)) { 2762206083Srdivacky if (!OpName.empty()) 2763341825Sdim error("Constant int or bit argument should not have a name!"); 2764341825Sdim if (isa<BitInit>(TheInit)) 2765341825Sdim TheInit = TheInit->convertInitializerTo(IntRecTy::get()); 2766341825Sdim return std::make_shared<TreePatternNode>(TheInit, 1); 2767206083Srdivacky } 2768218893Sdim 2769243830Sdim if (BitsInit *BI = dyn_cast<BitsInit>(TheInit)) { 2770206083Srdivacky // Turn this into an IntInit. 2771226633Sdim Init *II = BI->convertInitializerTo(IntRecTy::get()); 2772276479Sdim if (!II || !isa<IntInit>(II)) 2773206083Srdivacky error("Bits value must be constants!"); 2774206083Srdivacky return ParseTreePattern(II, OpName); 2775206083Srdivacky } 2776206083Srdivacky 2777243830Sdim DagInit *Dag = dyn_cast<DagInit>(TheInit); 2778206083Srdivacky if (!Dag) { 2779321369Sdim TheInit->print(errs()); 2780206083Srdivacky error("Pattern has unexpected init kind!"); 2781206083Srdivacky } 2782243830Sdim DefInit *OpDef = dyn_cast<DefInit>(Dag->getOperator()); 2783193323Sed if (!OpDef) error("Pattern has unexpected operator type!"); 2784193323Sed Record *Operator = OpDef->getDef(); 2785218893Sdim 2786193323Sed if (Operator->isSubClassOf("ValueType")) { 2787193323Sed // If the operator is a ValueType, then this must be "type cast" of a leaf 2788193323Sed // node. 2789193323Sed if (Dag->getNumArgs() != 1) 2790193323Sed error("Type cast only takes one operand!"); 2791218893Sdim 2792341825Sdim TreePatternNodePtr New = 2793341825Sdim ParseTreePattern(Dag->getArg(0), Dag->getArgNameStr(0)); 2794218893Sdim 2795193323Sed // Apply the type cast. 2796205407Srdivacky assert(New->getNumTypes() == 1 && "FIXME: Unhandled"); 2797327952Sdim const CodeGenHwModes &CGH = getDAGPatterns().getTargetInfo().getHwModes(); 2798327952Sdim New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this); 2799218893Sdim 2800206083Srdivacky if (!OpName.empty()) 2801206083Srdivacky error("ValueType cast should not have a name!"); 2802193323Sed return New; 2803193323Sed } 2804218893Sdim 2805193323Sed // Verify that this is something that makes sense for an operator. 2806341825Sdim if (!Operator->isSubClassOf("PatFrags") && 2807193323Sed !Operator->isSubClassOf("SDNode") && 2808218893Sdim !Operator->isSubClassOf("Instruction") && 2809193323Sed !Operator->isSubClassOf("SDNodeXForm") && 2810193323Sed !Operator->isSubClassOf("Intrinsic") && 2811276479Sdim !Operator->isSubClassOf("ComplexPattern") && 2812193323Sed Operator->getName() != "set" && 2813206083Srdivacky Operator->getName() != "implicit") 2814193323Sed error("Unrecognized node '" + Operator->getName() + "'!"); 2815218893Sdim 2816193323Sed // Check to see if this is something that is illegal in an input pattern. 2817206083Srdivacky if (isInputPattern) { 2818206083Srdivacky if (Operator->isSubClassOf("Instruction") || 2819206083Srdivacky Operator->isSubClassOf("SDNodeXForm")) 2820206083Srdivacky error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 2821206083Srdivacky } else { 2822206083Srdivacky if (Operator->isSubClassOf("Intrinsic")) 2823206083Srdivacky error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 2824218893Sdim 2825206083Srdivacky if (Operator->isSubClassOf("SDNode") && 2826206083Srdivacky Operator->getName() != "imm" && 2827360784Sdim Operator->getName() != "timm" && 2828206083Srdivacky Operator->getName() != "fpimm" && 2829206083Srdivacky Operator->getName() != "tglobaltlsaddr" && 2830206083Srdivacky Operator->getName() != "tconstpool" && 2831206083Srdivacky Operator->getName() != "tjumptable" && 2832206083Srdivacky Operator->getName() != "tframeindex" && 2833206083Srdivacky Operator->getName() != "texternalsym" && 2834206083Srdivacky Operator->getName() != "tblockaddress" && 2835206083Srdivacky Operator->getName() != "tglobaladdr" && 2836206083Srdivacky Operator->getName() != "bb" && 2837288943Sdim Operator->getName() != "vt" && 2838288943Sdim Operator->getName() != "mcsym") 2839206083Srdivacky error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 2840206083Srdivacky } 2841218893Sdim 2842341825Sdim std::vector<TreePatternNodePtr> Children; 2843206083Srdivacky 2844206083Srdivacky // Parse all the operands. 2845206083Srdivacky for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) 2846314564Sdim Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgNameStr(i))); 2847218893Sdim 2848327952Sdim // Get the actual number of results before Operator is converted to an intrinsic 2849327952Sdim // node (which is hard-coded to have either zero or one result). 2850327952Sdim unsigned NumResults = GetNumNodeResults(Operator, CDP); 2851327952Sdim 2852341825Sdim // If the operator is an intrinsic, then this is just syntactic sugar for 2853218893Sdim // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 2854193323Sed // convert the intrinsic name to a number. 2855193323Sed if (Operator->isSubClassOf("Intrinsic")) { 2856193323Sed const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 2857193323Sed unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 2858193323Sed 2859193323Sed // If this intrinsic returns void, it must have side-effects and thus a 2860193323Sed // chain. 2861206083Srdivacky if (Int.IS.RetVTs.empty()) 2862193323Sed Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 2863353358Sdim else if (Int.ModRef != CodeGenIntrinsic::NoMem || Int.hasSideEffects) 2864193323Sed // Has side-effects, requires chain. 2865193323Sed Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 2866206083Srdivacky else // Otherwise, no chain. 2867193323Sed Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 2868218893Sdim 2869341825Sdim Children.insert(Children.begin(), 2870341825Sdim std::make_shared<TreePatternNode>(IntInit::get(IID), 1)); 2871193323Sed } 2872218893Sdim 2873276479Sdim if (Operator->isSubClassOf("ComplexPattern")) { 2874276479Sdim for (unsigned i = 0; i < Children.size(); ++i) { 2875341825Sdim TreePatternNodePtr Child = Children[i]; 2876276479Sdim 2877276479Sdim if (Child->getName().empty()) 2878276479Sdim error("All arguments to a ComplexPattern must be named"); 2879276479Sdim 2880276479Sdim // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)" 2881276479Sdim // and "(MY_PAT $b, $a)" should not be allowed in the same pattern; 2882276479Sdim // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)". 2883276479Sdim auto OperandId = std::make_pair(Operator, i); 2884276479Sdim auto PrevOp = ComplexPatternOperands.find(Child->getName()); 2885276479Sdim if (PrevOp != ComplexPatternOperands.end()) { 2886276479Sdim if (PrevOp->getValue() != OperandId) 2887276479Sdim error("All ComplexPattern operands must appear consistently: " 2888276479Sdim "in the same order in just one ComplexPattern instance."); 2889276479Sdim } else 2890276479Sdim ComplexPatternOperands[Child->getName()] = OperandId; 2891276479Sdim } 2892276479Sdim } 2893276479Sdim 2894341825Sdim TreePatternNodePtr Result = 2895341825Sdim std::make_shared<TreePatternNode>(Operator, std::move(Children), 2896341825Sdim NumResults); 2897206083Srdivacky Result->setName(OpName); 2898218893Sdim 2899314564Sdim if (Dag->getName()) { 2900206083Srdivacky assert(Result->getName().empty()); 2901314564Sdim Result->setName(Dag->getNameStr()); 2902206083Srdivacky } 2903193323Sed return Result; 2904193323Sed} 2905193323Sed 2906206083Srdivacky/// SimplifyTree - See if we can simplify this tree to eliminate something that 2907206083Srdivacky/// will never match in favor of something obvious that will. This is here 2908206083Srdivacky/// strictly as a convenience to target authors because it allows them to write 2909206083Srdivacky/// more type generic things and have useless type casts fold away. 2910206083Srdivacky/// 2911206083Srdivacky/// This returns true if any change is made. 2912341825Sdimstatic bool SimplifyTree(TreePatternNodePtr &N) { 2913206083Srdivacky if (N->isLeaf()) 2914206083Srdivacky return false; 2915206083Srdivacky 2916206083Srdivacky // If we have a bitconvert with a resolved type and if the source and 2917206083Srdivacky // destination types are the same, then the bitconvert is useless, remove it. 2918206083Srdivacky if (N->getOperator()->getName() == "bitconvert" && 2919327952Sdim N->getExtType(0).isValueTypeByHwMode(false) && 2920206083Srdivacky N->getExtType(0) == N->getChild(0)->getExtType(0) && 2921206083Srdivacky N->getName().empty()) { 2922341825Sdim N = N->getChildShared(0); 2923206083Srdivacky SimplifyTree(N); 2924206083Srdivacky return true; 2925206083Srdivacky } 2926206083Srdivacky 2927206083Srdivacky // Walk all children. 2928206083Srdivacky bool MadeChange = false; 2929206083Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2930341825Sdim TreePatternNodePtr Child = N->getChildShared(i); 2931206083Srdivacky MadeChange |= SimplifyTree(Child); 2932341825Sdim N->setChild(i, std::move(Child)); 2933206083Srdivacky } 2934206083Srdivacky return MadeChange; 2935206083Srdivacky} 2936206083Srdivacky 2937206083Srdivacky 2938206083Srdivacky 2939193323Sed/// InferAllTypes - Infer/propagate as many types throughout the expression 2940193323Sed/// patterns as possible. Return true if all types are inferred, false 2941243830Sdim/// otherwise. Flags an error if a type contradiction is found. 2942205218Srdivackybool TreePattern:: 2943205218SrdivackyInferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) { 2944205218Srdivacky if (NamedNodes.empty()) 2945205218Srdivacky ComputeNamedNodes(); 2946205218Srdivacky 2947193323Sed bool MadeChange = true; 2948193323Sed while (MadeChange) { 2949193323Sed MadeChange = false; 2950341825Sdim for (TreePatternNodePtr &Tree : Trees) { 2951296417Sdim MadeChange |= Tree->ApplyTypeConstraints(*this, false); 2952296417Sdim MadeChange |= SimplifyTree(Tree); 2953206083Srdivacky } 2954205218Srdivacky 2955205218Srdivacky // If there are constraints on our named nodes, apply them. 2956296417Sdim for (auto &Entry : NamedNodes) { 2957296417Sdim SmallVectorImpl<TreePatternNode*> &Nodes = Entry.second; 2958218893Sdim 2959205218Srdivacky // If we have input named node types, propagate their types to the named 2960205218Srdivacky // values here. 2961205218Srdivacky if (InNamedTypes) { 2962296417Sdim if (!InNamedTypes->count(Entry.getKey())) { 2963296417Sdim error("Node '" + std::string(Entry.getKey()) + 2964276479Sdim "' in output pattern but not input pattern"); 2965276479Sdim return true; 2966276479Sdim } 2967205218Srdivacky 2968205218Srdivacky const SmallVectorImpl<TreePatternNode*> &InNodes = 2969296417Sdim InNamedTypes->find(Entry.getKey())->second; 2970205218Srdivacky 2971205218Srdivacky // The input types should be fully resolved by now. 2972296417Sdim for (TreePatternNode *Node : Nodes) { 2973205218Srdivacky // If this node is a register class, and it is the root of the pattern 2974205218Srdivacky // then we're mapping something onto an input register. We allow 2975205218Srdivacky // changing the type of the input register in this case. This allows 2976205218Srdivacky // us to match things like: 2977205218Srdivacky // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>; 2978341825Sdim if (Node == Trees[0].get() && Node->isLeaf()) { 2979296417Sdim DefInit *DI = dyn_cast<DefInit>(Node->getLeafValue()); 2980224145Sdim if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 2981224145Sdim DI->getDef()->isSubClassOf("RegisterOperand"))) 2982205218Srdivacky continue; 2983205218Srdivacky } 2984218893Sdim 2985296417Sdim assert(Node->getNumTypes() == 1 && 2986205407Srdivacky InNodes[0]->getNumTypes() == 1 && 2987205407Srdivacky "FIXME: cannot name multiple result nodes yet"); 2988296417Sdim MadeChange |= Node->UpdateNodeType(0, InNodes[0]->getExtType(0), 2989296417Sdim *this); 2990205218Srdivacky } 2991205218Srdivacky } 2992218893Sdim 2993205218Srdivacky // If there are multiple nodes with the same name, they must all have the 2994205218Srdivacky // same type. 2995296417Sdim if (Entry.second.size() > 1) { 2996205218Srdivacky for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) { 2997205407Srdivacky TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1]; 2998205407Srdivacky assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && 2999205407Srdivacky "FIXME: cannot name multiple result nodes yet"); 3000218893Sdim 3001205407Srdivacky MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this); 3002205407Srdivacky MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this); 3003205218Srdivacky } 3004205218Srdivacky } 3005205218Srdivacky } 3006193323Sed } 3007218893Sdim 3008193323Sed bool HasUnresolvedTypes = false; 3009341825Sdim for (const TreePatternNodePtr &Tree : Trees) 3010327952Sdim HasUnresolvedTypes |= Tree->ContainsUnresolvedType(*this); 3011193323Sed return !HasUnresolvedTypes; 3012193323Sed} 3013193323Sed 3014195340Sedvoid TreePattern::print(raw_ostream &OS) const { 3015193323Sed OS << getRecord()->getName(); 3016193323Sed if (!Args.empty()) { 3017193323Sed OS << "(" << Args[0]; 3018193323Sed for (unsigned i = 1, e = Args.size(); i != e; ++i) 3019193323Sed OS << ", " << Args[i]; 3020193323Sed OS << ")"; 3021193323Sed } 3022193323Sed OS << ": "; 3023218893Sdim 3024193323Sed if (Trees.size() > 1) 3025193323Sed OS << "[\n"; 3026341825Sdim for (const TreePatternNodePtr &Tree : Trees) { 3027193323Sed OS << "\t"; 3028296417Sdim Tree->print(OS); 3029193323Sed OS << "\n"; 3030193323Sed } 3031193323Sed 3032193323Sed if (Trees.size() > 1) 3033193323Sed OS << "]\n"; 3034193323Sed} 3035193323Sed 3036195340Sedvoid TreePattern::dump() const { print(errs()); } 3037193323Sed 3038193323Sed//===----------------------------------------------------------------------===// 3039193323Sed// CodeGenDAGPatterns implementation 3040193323Sed// 3041193323Sed 3042327952SdimCodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R, 3043327952Sdim PatternRewriterFn PatternRewriter) 3044327952Sdim : Records(R), Target(R), LegalVTS(Target.getLegalValueTypes()), 3045327952Sdim PatternRewriter(PatternRewriter) { 3046218893Sdim 3047360784Sdim Intrinsics = CodeGenIntrinsicTable(Records); 3048193323Sed ParseNodeInfo(); 3049193323Sed ParseNodeTransforms(); 3050193323Sed ParseComplexPatterns(); 3051193323Sed ParsePatternFragments(); 3052193323Sed ParseDefaultOperands(); 3053193323Sed ParseInstructions(); 3054276479Sdim ParsePatternFragments(/*OutFrags*/true); 3055193323Sed ParsePatterns(); 3056218893Sdim 3057327952Sdim // Break patterns with parameterized types into a series of patterns, 3058327952Sdim // where each one has a fixed type and is predicated on the conditions 3059327952Sdim // of the associated HW mode. 3060327952Sdim ExpandHwModeBasedTypes(); 3061327952Sdim 3062193323Sed // Generate variants. For example, commutative patterns can match 3063193323Sed // multiple ways. Add them to PatternsToMatch as well. 3064193323Sed GenerateVariants(); 3065193323Sed 3066193323Sed // Infer instruction flags. For example, we can detect loads, 3067193323Sed // stores, and side effects in many cases by examining an 3068193323Sed // instruction's pattern. 3069193323Sed InferInstructionFlags(); 3070243830Sdim 3071243830Sdim // Verify that instruction flags match the patterns. 3072243830Sdim VerifyInstructionFlags(); 3073193323Sed} 3074193323Sed 3075193323SedRecord *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 3076193323Sed Record *N = Records.getDef(Name); 3077288943Sdim if (!N || !N->isSubClassOf("SDNode")) 3078288943Sdim PrintFatalError("Error getting SDNode '" + Name + "'!"); 3079288943Sdim 3080193323Sed return N; 3081193323Sed} 3082193323Sed 3083193323Sed// Parse all of the SDNode definitions for the target, populating SDNodes. 3084193323Sedvoid CodeGenDAGPatterns::ParseNodeInfo() { 3085193323Sed std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 3086327952Sdim const CodeGenHwModes &CGH = getTargetInfo().getHwModes(); 3087327952Sdim 3088193323Sed while (!Nodes.empty()) { 3089327952Sdim Record *R = Nodes.back(); 3090327952Sdim SDNodes.insert(std::make_pair(R, SDNodeInfo(R, CGH))); 3091193323Sed Nodes.pop_back(); 3092193323Sed } 3093193323Sed 3094193323Sed // Get the builtin intrinsic nodes. 3095193323Sed intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 3096193323Sed intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 3097193323Sed intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 3098193323Sed} 3099193323Sed 3100193323Sed/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 3101193323Sed/// map, and emit them to the file as functions. 3102193323Sedvoid CodeGenDAGPatterns::ParseNodeTransforms() { 3103193323Sed std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 3104193323Sed while (!Xforms.empty()) { 3105193323Sed Record *XFormNode = Xforms.back(); 3106193323Sed Record *SDNode = XFormNode->getValueAsDef("Opcode"); 3107321369Sdim StringRef Code = XFormNode->getValueAsString("XFormFunction"); 3108193323Sed SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 3109193323Sed 3110193323Sed Xforms.pop_back(); 3111193323Sed } 3112193323Sed} 3113193323Sed 3114193323Sedvoid CodeGenDAGPatterns::ParseComplexPatterns() { 3115193323Sed std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 3116193323Sed while (!AMs.empty()) { 3117193323Sed ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 3118193323Sed AMs.pop_back(); 3119193323Sed } 3120193323Sed} 3121193323Sed 3122193323Sed 3123193323Sed/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 3124193323Sed/// file, building up the PatternFragments map. After we've collected them all, 3125193323Sed/// inline fragments together as necessary, so that there are no references left 3126193323Sed/// inside a pattern fragment to a pattern fragment. 3127193323Sed/// 3128276479Sdimvoid CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { 3129341825Sdim std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrags"); 3130218893Sdim 3131193323Sed // First step, parse all of the fragments. 3132296417Sdim for (Record *Frag : Fragments) { 3133296417Sdim if (OutFrags != Frag->isSubClassOf("OutPatFrag")) 3134276479Sdim continue; 3135276479Sdim 3136341825Sdim ListInit *LI = Frag->getValueAsListInit("Fragments"); 3137276479Sdim TreePattern *P = 3138360784Sdim (PatternFragments[Frag] = std::make_unique<TreePattern>( 3139341825Sdim Frag, LI, !Frag->isSubClassOf("OutPatFrag"), 3140280031Sdim *this)).get(); 3141218893Sdim 3142193323Sed // Validate the argument list, converting it to set, to discard duplicates. 3143193323Sed std::vector<std::string> &Args = P->getArgList(); 3144327952Sdim // Copy the args so we can take StringRefs to them. 3145327952Sdim auto ArgsCopy = Args; 3146327952Sdim SmallDenseSet<StringRef, 4> OperandsSet; 3147327952Sdim OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end()); 3148218893Sdim 3149193323Sed if (OperandsSet.count("")) 3150193323Sed P->error("Cannot have unnamed 'node' values in pattern fragment!"); 3151218893Sdim 3152193323Sed // Parse the operands list. 3153296417Sdim DagInit *OpsList = Frag->getValueAsDag("Operands"); 3154243830Sdim DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator()); 3155193323Sed // Special cases: ops == outs == ins. Different names are used to 3156193323Sed // improve readability. 3157193323Sed if (!OpsOp || 3158193323Sed (OpsOp->getDef()->getName() != "ops" && 3159193323Sed OpsOp->getDef()->getName() != "outs" && 3160193323Sed OpsOp->getDef()->getName() != "ins")) 3161193323Sed P->error("Operands list should start with '(ops ... '!"); 3162218893Sdim 3163218893Sdim // Copy over the arguments. 3164193323Sed Args.clear(); 3165193323Sed for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 3166243830Sdim if (!isa<DefInit>(OpsList->getArg(j)) || 3167243830Sdim cast<DefInit>(OpsList->getArg(j))->getDef()->getName() != "node") 3168193323Sed P->error("Operands list should all be 'node' values."); 3169314564Sdim if (!OpsList->getArgName(j)) 3170193323Sed P->error("Operands list should have names for each operand!"); 3171314564Sdim StringRef ArgNameStr = OpsList->getArgNameStr(j); 3172314564Sdim if (!OperandsSet.count(ArgNameStr)) 3173314564Sdim P->error("'" + ArgNameStr + 3174193323Sed "' does not occur in pattern or was multiply specified!"); 3175314564Sdim OperandsSet.erase(ArgNameStr); 3176314564Sdim Args.push_back(ArgNameStr); 3177193323Sed } 3178218893Sdim 3179193323Sed if (!OperandsSet.empty()) 3180193323Sed P->error("Operands list does not contain an entry for operand '" + 3181193323Sed *OperandsSet.begin() + "'!"); 3182193323Sed 3183193323Sed // If there is a node transformation corresponding to this, keep track of 3184193323Sed // it. 3185296417Sdim Record *Transform = Frag->getValueAsDef("OperandTransform"); 3186193323Sed if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 3187341825Sdim for (auto T : P->getTrees()) 3188341825Sdim T->setTransformFn(Transform); 3189193323Sed } 3190218893Sdim 3191193323Sed // Now that we've parsed all of the tree fragments, do a closure on them so 3192193323Sed // that there are not references to PatFrags left inside of them. 3193296417Sdim for (Record *Frag : Fragments) { 3194296417Sdim if (OutFrags != Frag->isSubClassOf("OutPatFrag")) 3195276479Sdim continue; 3196276479Sdim 3197296417Sdim TreePattern &ThePat = *PatternFragments[Frag]; 3198280031Sdim ThePat.InlinePatternFragments(); 3199218893Sdim 3200193323Sed // Infer as many types as possible. Don't worry about it if we don't infer 3201341825Sdim // all of them, some may depend on the inputs of the pattern. Also, don't 3202341825Sdim // validate type sets; validation may cause spurious failures e.g. if a 3203341825Sdim // fragment needs floating-point types but the current target does not have 3204341825Sdim // any (this is only an error if that fragment is ever used!). 3205341825Sdim { 3206341825Sdim TypeInfer::SuppressValidation SV(ThePat.getInfer()); 3207341825Sdim ThePat.InferAllTypes(); 3208341825Sdim ThePat.resetError(); 3209341825Sdim } 3210218893Sdim 3211193323Sed // If debugging, print out the pattern fragment result. 3212341825Sdim LLVM_DEBUG(ThePat.dump()); 3213193323Sed } 3214193323Sed} 3215193323Sed 3216193323Sedvoid CodeGenDAGPatterns::ParseDefaultOperands() { 3217243830Sdim std::vector<Record*> DefaultOps; 3218243830Sdim DefaultOps = Records.getAllDerivedDefinitions("OperandWithDefaultOps"); 3219193323Sed 3220193323Sed // Find some SDNode. 3221193323Sed assert(!SDNodes.empty() && "No SDNodes parsed?"); 3222226633Sdim Init *SomeSDNode = DefInit::get(SDNodes.begin()->first); 3223218893Sdim 3224243830Sdim for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) { 3225243830Sdim DagInit *DefaultInfo = DefaultOps[i]->getValueAsDag("DefaultOps"); 3226218893Sdim 3227243830Sdim // Clone the DefaultInfo dag node, changing the operator from 'ops' to 3228243830Sdim // SomeSDnode so that we can parse this. 3229314564Sdim std::vector<std::pair<Init*, StringInit*> > Ops; 3230243830Sdim for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 3231243830Sdim Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 3232243830Sdim DefaultInfo->getArgName(op))); 3233314564Sdim DagInit *DI = DagInit::get(SomeSDNode, nullptr, Ops); 3234218893Sdim 3235243830Sdim // Create a TreePattern to parse this. 3236243830Sdim TreePattern P(DefaultOps[i], DI, false, *this); 3237243830Sdim assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 3238193323Sed 3239243830Sdim // Copy the operands over into a DAGDefaultOperand. 3240243830Sdim DAGDefaultOperand DefaultOpInfo; 3241218893Sdim 3242341825Sdim const TreePatternNodePtr &T = P.getTree(0); 3243243830Sdim for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 3244341825Sdim TreePatternNodePtr TPN = T->getChildShared(op); 3245243830Sdim while (TPN->ApplyTypeConstraints(P, false)) 3246243830Sdim /* Resolve all types */; 3247218893Sdim 3248327952Sdim if (TPN->ContainsUnresolvedType(P)) { 3249276479Sdim PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" + 3250276479Sdim DefaultOps[i]->getName() + 3251276479Sdim "' doesn't have a concrete type!"); 3252193323Sed } 3253341825Sdim DefaultOpInfo.DefaultOps.push_back(std::move(TPN)); 3254243830Sdim } 3255193323Sed 3256243830Sdim // Insert it into the DefaultOperands map so we can find it later. 3257243830Sdim DefaultOperands[DefaultOps[i]] = DefaultOpInfo; 3258193323Sed } 3259193323Sed} 3260193323Sed 3261193323Sed/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 3262193323Sed/// instruction input. Return true if this is a real use. 3263341825Sdimstatic bool HandleUse(TreePattern &I, TreePatternNodePtr Pat, 3264341825Sdim std::map<std::string, TreePatternNodePtr> &InstInputs) { 3265193323Sed // No name -> not interesting. 3266193323Sed if (Pat->getName().empty()) { 3267193323Sed if (Pat->isLeaf()) { 3268243830Sdim DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue()); 3269224145Sdim if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 3270224145Sdim DI->getDef()->isSubClassOf("RegisterOperand"))) 3271341825Sdim I.error("Input " + DI->getDef()->getName() + " must be named!"); 3272193323Sed } 3273193323Sed return false; 3274193323Sed } 3275193323Sed 3276193323Sed Record *Rec; 3277193323Sed if (Pat->isLeaf()) { 3278243830Sdim DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue()); 3279341825Sdim if (!DI) 3280341825Sdim I.error("Input $" + Pat->getName() + " must be an identifier!"); 3281193323Sed Rec = DI->getDef(); 3282193323Sed } else { 3283193323Sed Rec = Pat->getOperator(); 3284193323Sed } 3285193323Sed 3286193323Sed // SRCVALUE nodes are ignored. 3287193323Sed if (Rec->getName() == "srcvalue") 3288193323Sed return false; 3289193323Sed 3290341825Sdim TreePatternNodePtr &Slot = InstInputs[Pat->getName()]; 3291193323Sed if (!Slot) { 3292193323Sed Slot = Pat; 3293204642Srdivacky return true; 3294204642Srdivacky } 3295204642Srdivacky Record *SlotRec; 3296204642Srdivacky if (Slot->isLeaf()) { 3297243830Sdim SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef(); 3298193323Sed } else { 3299204642Srdivacky assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 3300204642Srdivacky SlotRec = Slot->getOperator(); 3301193323Sed } 3302218893Sdim 3303204642Srdivacky // Ensure that the inputs agree if we've already seen this input. 3304204642Srdivacky if (Rec != SlotRec) 3305341825Sdim I.error("All $" + Pat->getName() + " inputs must agree with each other"); 3306341825Sdim // Ensure that the types can agree as well. 3307341825Sdim Slot->UpdateNodeType(0, Pat->getExtType(0), I); 3308341825Sdim Pat->UpdateNodeType(0, Slot->getExtType(0), I); 3309205407Srdivacky if (Slot->getExtTypes() != Pat->getExtTypes()) 3310341825Sdim I.error("All $" + Pat->getName() + " inputs must agree with each other"); 3311193323Sed return true; 3312193323Sed} 3313193323Sed 3314193323Sed/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 3315193323Sed/// part of "I", the instruction), computing the set of inputs and outputs of 3316193323Sed/// the pattern. Report errors if we see anything naughty. 3317341825Sdimvoid CodeGenDAGPatterns::FindPatternInputsAndOutputs( 3318341825Sdim TreePattern &I, TreePatternNodePtr Pat, 3319341825Sdim std::map<std::string, TreePatternNodePtr> &InstInputs, 3320344779Sdim MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>> 3321344779Sdim &InstResults, 3322341825Sdim std::vector<Record *> &InstImpResults) { 3323341825Sdim 3324341825Sdim // The instruction pattern still has unresolved fragments. For *named* 3325341825Sdim // nodes we must resolve those here. This may not result in multiple 3326341825Sdim // alternatives. 3327341825Sdim if (!Pat->getName().empty()) { 3328341825Sdim TreePattern SrcPattern(I.getRecord(), Pat, true, *this); 3329341825Sdim SrcPattern.InlinePatternFragments(); 3330341825Sdim SrcPattern.InferAllTypes(); 3331341825Sdim Pat = SrcPattern.getOnlyTree(); 3332341825Sdim } 3333341825Sdim 3334193323Sed if (Pat->isLeaf()) { 3335207618Srdivacky bool isUse = HandleUse(I, Pat, InstInputs); 3336193323Sed if (!isUse && Pat->getTransformFn()) 3337341825Sdim I.error("Cannot specify a transform function for a non-input value!"); 3338193323Sed return; 3339204642Srdivacky } 3340218893Sdim 3341204642Srdivacky if (Pat->getOperator()->getName() == "implicit") { 3342193323Sed for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 3343193323Sed TreePatternNode *Dest = Pat->getChild(i); 3344193323Sed if (!Dest->isLeaf()) 3345341825Sdim I.error("implicitly defined value should be a register!"); 3346218893Sdim 3347243830Sdim DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue()); 3348193323Sed if (!Val || !Val->getDef()->isSubClassOf("Register")) 3349341825Sdim I.error("implicitly defined value should be a register!"); 3350193323Sed InstImpResults.push_back(Val->getDef()); 3351193323Sed } 3352193323Sed return; 3353204642Srdivacky } 3354218893Sdim 3355204642Srdivacky if (Pat->getOperator()->getName() != "set") { 3356193323Sed // If this is not a set, verify that the children nodes are not void typed, 3357193323Sed // and recurse. 3358193323Sed for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 3359205407Srdivacky if (Pat->getChild(i)->getNumTypes() == 0) 3360341825Sdim I.error("Cannot have void nodes inside of patterns!"); 3361341825Sdim FindPatternInputsAndOutputs(I, Pat->getChildShared(i), InstInputs, 3362341825Sdim InstResults, InstImpResults); 3363193323Sed } 3364218893Sdim 3365193323Sed // If this is a non-leaf node with no children, treat it basically as if 3366193323Sed // it were a leaf. This handles nodes like (imm). 3367207618Srdivacky bool isUse = HandleUse(I, Pat, InstInputs); 3368218893Sdim 3369193323Sed if (!isUse && Pat->getTransformFn()) 3370341825Sdim I.error("Cannot specify a transform function for a non-input value!"); 3371193323Sed return; 3372204642Srdivacky } 3373218893Sdim 3374193323Sed // Otherwise, this is a set, validate and collect instruction results. 3375193323Sed if (Pat->getNumChildren() == 0) 3376341825Sdim I.error("set requires operands!"); 3377218893Sdim 3378193323Sed if (Pat->getTransformFn()) 3379341825Sdim I.error("Cannot specify a transform function on a set node!"); 3380218893Sdim 3381193323Sed // Check the set destinations. 3382193323Sed unsigned NumDests = Pat->getNumChildren()-1; 3383193323Sed for (unsigned i = 0; i != NumDests; ++i) { 3384341825Sdim TreePatternNodePtr Dest = Pat->getChildShared(i); 3385341825Sdim // For set destinations we also must resolve fragments here. 3386341825Sdim TreePattern DestPattern(I.getRecord(), Dest, false, *this); 3387341825Sdim DestPattern.InlinePatternFragments(); 3388341825Sdim DestPattern.InferAllTypes(); 3389341825Sdim Dest = DestPattern.getOnlyTree(); 3390341825Sdim 3391193323Sed if (!Dest->isLeaf()) 3392341825Sdim I.error("set destination should be a register!"); 3393218893Sdim 3394243830Sdim DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue()); 3395280031Sdim if (!Val) { 3396341825Sdim I.error("set destination should be a register!"); 3397280031Sdim continue; 3398280031Sdim } 3399193323Sed 3400193323Sed if (Val->getDef()->isSubClassOf("RegisterClass") || 3401249423Sdim Val->getDef()->isSubClassOf("ValueType") || 3402224145Sdim Val->getDef()->isSubClassOf("RegisterOperand") || 3403198090Srdivacky Val->getDef()->isSubClassOf("PointerLikeRegClass")) { 3404193323Sed if (Dest->getName().empty()) 3405341825Sdim I.error("set destination must have a name!"); 3406193323Sed if (InstResults.count(Dest->getName())) 3407341825Sdim I.error("cannot set '" + Dest->getName() + "' multiple times"); 3408193323Sed InstResults[Dest->getName()] = Dest; 3409193323Sed } else if (Val->getDef()->isSubClassOf("Register")) { 3410193323Sed InstImpResults.push_back(Val->getDef()); 3411193323Sed } else { 3412341825Sdim I.error("set destination should be a register!"); 3413193323Sed } 3414193323Sed } 3415218893Sdim 3416193323Sed // Verify and collect info from the computation. 3417341825Sdim FindPatternInputsAndOutputs(I, Pat->getChildShared(NumDests), InstInputs, 3418341825Sdim InstResults, InstImpResults); 3419193323Sed} 3420193323Sed 3421193323Sed//===----------------------------------------------------------------------===// 3422193323Sed// Instruction Analysis 3423193323Sed//===----------------------------------------------------------------------===// 3424193323Sed 3425193323Sedclass InstAnalyzer { 3426193323Sed const CodeGenDAGPatterns &CDP; 3427193323Sedpublic: 3428243830Sdim bool hasSideEffects; 3429243830Sdim bool mayStore; 3430243830Sdim bool mayLoad; 3431243830Sdim bool isBitcast; 3432243830Sdim bool isVariadic; 3433341825Sdim bool hasChain; 3434193323Sed 3435243830Sdim InstAnalyzer(const CodeGenDAGPatterns &cdp) 3436243830Sdim : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false), 3437341825Sdim isBitcast(false), isVariadic(false), hasChain(false) {} 3438193323Sed 3439321369Sdim void Analyze(const PatternToMatch &Pat) { 3440341825Sdim const TreePatternNode *N = Pat.getSrcPattern(); 3441341825Sdim AnalyzeNode(N); 3442341825Sdim // These properties are detected only on the root node. 3443341825Sdim isBitcast = IsNodeBitcast(N); 3444243830Sdim } 3445243830Sdim 3446193323Sedprivate: 3447221345Sdim bool IsNodeBitcast(const TreePatternNode *N) const { 3448243830Sdim if (hasSideEffects || mayLoad || mayStore || isVariadic) 3449221345Sdim return false; 3450221345Sdim 3451341825Sdim if (N->isLeaf()) 3452221345Sdim return false; 3453341825Sdim if (N->getNumChildren() != 1 || !N->getChild(0)->isLeaf()) 3454221345Sdim return false; 3455221345Sdim 3456341825Sdim const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); 3457221345Sdim if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1) 3458221345Sdim return false; 3459221345Sdim return OpInfo.getEnumName() == "ISD::BITCAST"; 3460221345Sdim } 3461221345Sdim 3462243830Sdimpublic: 3463193323Sed void AnalyzeNode(const TreePatternNode *N) { 3464193323Sed if (N->isLeaf()) { 3465243830Sdim if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) { 3466193323Sed Record *LeafRec = DI->getDef(); 3467193323Sed // Handle ComplexPattern leaves. 3468193323Sed if (LeafRec->isSubClassOf("ComplexPattern")) { 3469193323Sed const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 3470193323Sed if (CP.hasProperty(SDNPMayStore)) mayStore = true; 3471193323Sed if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 3472243830Sdim if (CP.hasProperty(SDNPSideEffect)) hasSideEffects = true; 3473193323Sed } 3474193323Sed } 3475193323Sed return; 3476193323Sed } 3477193323Sed 3478193323Sed // Analyze children. 3479193323Sed for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 3480193323Sed AnalyzeNode(N->getChild(i)); 3481193323Sed 3482193323Sed // Notice properties of the node. 3483276479Sdim if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true; 3484276479Sdim if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true; 3485276479Sdim if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true; 3486276479Sdim if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true; 3487341825Sdim if (N->NodeHasProperty(SDNPHasChain, CDP)) hasChain = true; 3488193323Sed 3489193323Sed if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 3490193323Sed // If this is an intrinsic, analyze it. 3491309124Sdim if (IntInfo->ModRef & CodeGenIntrinsic::MR_Ref) 3492193323Sed mayLoad = true;// These may load memory. 3493193323Sed 3494309124Sdim if (IntInfo->ModRef & CodeGenIntrinsic::MR_Mod) 3495193323Sed mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 3496193323Sed 3497321369Sdim if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem || 3498321369Sdim IntInfo->hasSideEffects) 3499309124Sdim // ReadWriteMem intrinsics can have other strange effects. 3500243830Sdim hasSideEffects = true; 3501193323Sed } 3502193323Sed } 3503193323Sed 3504193323Sed}; 3505193323Sed 3506243830Sdimstatic bool InferFromPattern(CodeGenInstruction &InstInfo, 3507243830Sdim const InstAnalyzer &PatInfo, 3508243830Sdim Record *PatDef) { 3509243830Sdim bool Error = false; 3510193323Sed 3511243830Sdim // Remember where InstInfo got its flags. 3512243830Sdim if (InstInfo.hasUndefFlags()) 3513243830Sdim InstInfo.InferredFrom = PatDef; 3514193323Sed 3515243830Sdim // Check explicitly set flags for consistency. 3516243830Sdim if (InstInfo.hasSideEffects != PatInfo.hasSideEffects && 3517243830Sdim !InstInfo.hasSideEffects_Unset) { 3518243830Sdim // Allow explicitly setting hasSideEffects = 1 on instructions, even when 3519243830Sdim // the pattern has no side effects. That could be useful for div/rem 3520243830Sdim // instructions that may trap. 3521243830Sdim if (!InstInfo.hasSideEffects) { 3522243830Sdim Error = true; 3523243830Sdim PrintError(PatDef->getLoc(), "Pattern doesn't match hasSideEffects = " + 3524243830Sdim Twine(InstInfo.hasSideEffects)); 3525243830Sdim } 3526193323Sed } 3527193323Sed 3528243830Sdim if (InstInfo.mayStore != PatInfo.mayStore && !InstInfo.mayStore_Unset) { 3529243830Sdim Error = true; 3530243830Sdim PrintError(PatDef->getLoc(), "Pattern doesn't match mayStore = " + 3531243830Sdim Twine(InstInfo.mayStore)); 3532193323Sed } 3533193323Sed 3534243830Sdim if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) { 3535243830Sdim // Allow explicitly setting mayLoad = 1, even when the pattern has no loads. 3536296417Sdim // Some targets translate immediates to loads. 3537243830Sdim if (!InstInfo.mayLoad) { 3538243830Sdim Error = true; 3539243830Sdim PrintError(PatDef->getLoc(), "Pattern doesn't match mayLoad = " + 3540243830Sdim Twine(InstInfo.mayLoad)); 3541243830Sdim } 3542193323Sed } 3543193323Sed 3544243830Sdim // Transfer inferred flags. 3545243830Sdim InstInfo.hasSideEffects |= PatInfo.hasSideEffects; 3546243830Sdim InstInfo.mayStore |= PatInfo.mayStore; 3547243830Sdim InstInfo.mayLoad |= PatInfo.mayLoad; 3548218893Sdim 3549243830Sdim // These flags are silently added without any verification. 3550341825Sdim // FIXME: To match historical behavior of TableGen, for now add those flags 3551341825Sdim // only when we're inferring from the primary instruction pattern. 3552341825Sdim if (PatDef->isSubClassOf("Instruction")) { 3553341825Sdim InstInfo.isBitcast |= PatInfo.isBitcast; 3554341825Sdim InstInfo.hasChain |= PatInfo.hasChain; 3555341825Sdim InstInfo.hasChain_Inferred = true; 3556341825Sdim } 3557243830Sdim 3558243830Sdim // Don't infer isVariadic. This flag means something different on SDNodes and 3559243830Sdim // instructions. For example, a CALL SDNode is variadic because it has the 3560243830Sdim // call arguments as operands, but a CALL instruction is not variadic - it 3561243830Sdim // has argument registers as implicit, not explicit uses. 3562243830Sdim 3563243830Sdim return Error; 3564193323Sed} 3565193323Sed 3566239462Sdim/// hasNullFragReference - Return true if the DAG has any reference to the 3567239462Sdim/// null_frag operator. 3568239462Sdimstatic bool hasNullFragReference(DagInit *DI) { 3569243830Sdim DefInit *OpDef = dyn_cast<DefInit>(DI->getOperator()); 3570239462Sdim if (!OpDef) return false; 3571239462Sdim Record *Operator = OpDef->getDef(); 3572239462Sdim 3573239462Sdim // If this is the null fragment, return true. 3574239462Sdim if (Operator->getName() == "null_frag") return true; 3575239462Sdim // If any of the arguments reference the null fragment, return true. 3576239462Sdim for (unsigned i = 0, e = DI->getNumArgs(); i != e; ++i) { 3577243830Sdim DagInit *Arg = dyn_cast<DagInit>(DI->getArg(i)); 3578239462Sdim if (Arg && hasNullFragReference(Arg)) 3579239462Sdim return true; 3580239462Sdim } 3581239462Sdim 3582239462Sdim return false; 3583239462Sdim} 3584239462Sdim 3585239462Sdim/// hasNullFragReference - Return true if any DAG in the list references 3586239462Sdim/// the null_frag operator. 3587239462Sdimstatic bool hasNullFragReference(ListInit *LI) { 3588288943Sdim for (Init *I : LI->getValues()) { 3589288943Sdim DagInit *DI = dyn_cast<DagInit>(I); 3590239462Sdim assert(DI && "non-dag in an instruction Pattern list?!"); 3591239462Sdim if (hasNullFragReference(DI)) 3592239462Sdim return true; 3593239462Sdim } 3594239462Sdim return false; 3595239462Sdim} 3596239462Sdim 3597243830Sdim/// Get all the instructions in a tree. 3598243830Sdimstatic void 3599243830SdimgetInstructionsInTree(TreePatternNode *Tree, SmallVectorImpl<Record*> &Instrs) { 3600243830Sdim if (Tree->isLeaf()) 3601243830Sdim return; 3602243830Sdim if (Tree->getOperator()->isSubClassOf("Instruction")) 3603243830Sdim Instrs.push_back(Tree->getOperator()); 3604243830Sdim for (unsigned i = 0, e = Tree->getNumChildren(); i != e; ++i) 3605243830Sdim getInstructionsInTree(Tree->getChild(i), Instrs); 3606243830Sdim} 3607243830Sdim 3608249423Sdim/// Check the class of a pattern leaf node against the instruction operand it 3609249423Sdim/// represents. 3610249423Sdimstatic bool checkOperandClass(CGIOperandList::OperandInfo &OI, 3611249423Sdim Record *Leaf) { 3612249423Sdim if (OI.Rec == Leaf) 3613249423Sdim return true; 3614249423Sdim 3615249423Sdim // Allow direct value types to be used in instruction set patterns. 3616249423Sdim // The type will be checked later. 3617249423Sdim if (Leaf->isSubClassOf("ValueType")) 3618249423Sdim return true; 3619249423Sdim 3620249423Sdim // Patterns can also be ComplexPattern instances. 3621249423Sdim if (Leaf->isSubClassOf("ComplexPattern")) 3622249423Sdim return true; 3623249423Sdim 3624249423Sdim return false; 3625249423Sdim} 3626249423Sdim 3627341825Sdimvoid CodeGenDAGPatterns::parseInstructionPattern( 3628261991Sdim CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) { 3629218893Sdim 3630288943Sdim assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"); 3631218893Sdim 3632288943Sdim // Parse the instruction. 3633341825Sdim TreePattern I(CGI.TheDef, Pat, true, *this); 3634218893Sdim 3635288943Sdim // InstInputs - Keep track of all of the inputs of the instruction, along 3636288943Sdim // with the record they are declared as. 3637341825Sdim std::map<std::string, TreePatternNodePtr> InstInputs; 3638218893Sdim 3639288943Sdim // InstResults - Keep track of all the virtual registers that are 'set' 3640288943Sdim // in the instruction, including what reg class they are. 3641344779Sdim MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>> 3642344779Sdim InstResults; 3643193323Sed 3644288943Sdim std::vector<Record*> InstImpResults; 3645218893Sdim 3646288943Sdim // Verify that the top-level forms in the instruction are of void type, and 3647288943Sdim // fill in the InstResults map. 3648327952Sdim SmallString<32> TypesString; 3649341825Sdim for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) { 3650327952Sdim TypesString.clear(); 3651341825Sdim TreePatternNodePtr Pat = I.getTree(j); 3652309124Sdim if (Pat->getNumTypes() != 0) { 3653327952Sdim raw_svector_ostream OS(TypesString); 3654309124Sdim for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) { 3655309124Sdim if (k > 0) 3656327952Sdim OS << ", "; 3657327952Sdim Pat->getExtType(k).writeToStream(OS); 3658309124Sdim } 3659341825Sdim I.error("Top-level forms in instruction pattern should have" 3660327952Sdim " void types, has types " + 3661327952Sdim OS.str()); 3662309124Sdim } 3663193323Sed 3664288943Sdim // Find inputs and outputs, and verify the structure of the uses/defs. 3665288943Sdim FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 3666288943Sdim InstImpResults); 3667288943Sdim } 3668193323Sed 3669288943Sdim // Now that we have inputs and outputs of the pattern, inspect the operands 3670288943Sdim // list for the instruction. This determines the order that operands are 3671288943Sdim // added to the machine instruction the node corresponds to. 3672288943Sdim unsigned NumResults = InstResults.size(); 3673193323Sed 3674288943Sdim // Parse the operands list from the (ops) list, validating it. 3675341825Sdim assert(I.getArgList().empty() && "Args list should still be empty here!"); 3676193323Sed 3677288943Sdim // Check that all of the results occur first in the list. 3678288943Sdim std::vector<Record*> Results; 3679344779Sdim std::vector<unsigned> ResultIndices; 3680341825Sdim SmallVector<TreePatternNodePtr, 2> ResNodes; 3681288943Sdim for (unsigned i = 0; i != NumResults; ++i) { 3682344779Sdim if (i == CGI.Operands.size()) { 3683344779Sdim const std::string &OpName = 3684344779Sdim std::find_if(InstResults.begin(), InstResults.end(), 3685344779Sdim [](const std::pair<std::string, TreePatternNodePtr> &P) { 3686344779Sdim return P.second; 3687344779Sdim }) 3688344779Sdim ->first; 3689344779Sdim 3690344779Sdim I.error("'" + OpName + "' set but does not appear in operand list!"); 3691344779Sdim } 3692344779Sdim 3693288943Sdim const std::string &OpName = CGI.Operands[i].Name; 3694218893Sdim 3695288943Sdim // Check that it exists in InstResults. 3696344779Sdim auto InstResultIter = InstResults.find(OpName); 3697344779Sdim if (InstResultIter == InstResults.end() || !InstResultIter->second) 3698341825Sdim I.error("Operand $" + OpName + " does not exist in operand list!"); 3699218893Sdim 3700344779Sdim TreePatternNodePtr RNode = InstResultIter->second; 3701288943Sdim Record *R = cast<DefInit>(RNode->getLeafValue())->getDef(); 3702341825Sdim ResNodes.push_back(std::move(RNode)); 3703288943Sdim if (!R) 3704341825Sdim I.error("Operand $" + OpName + " should be a set destination: all " 3705288943Sdim "outputs must occur before inputs in operand list!"); 3706218893Sdim 3707288943Sdim if (!checkOperandClass(CGI.Operands[i], R)) 3708341825Sdim I.error("Operand $" + OpName + " class mismatch!"); 3709218893Sdim 3710288943Sdim // Remember the return type. 3711288943Sdim Results.push_back(CGI.Operands[i].Rec); 3712193323Sed 3713344779Sdim // Remember the result index. 3714344779Sdim ResultIndices.push_back(std::distance(InstResults.begin(), InstResultIter)); 3715344779Sdim 3716288943Sdim // Okay, this one checks out. 3717344779Sdim InstResultIter->second = nullptr; 3718288943Sdim } 3719193323Sed 3720341825Sdim // Loop over the inputs next. 3721341825Sdim std::vector<TreePatternNodePtr> ResultNodeOperands; 3722288943Sdim std::vector<Record*> Operands; 3723288943Sdim for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) { 3724288943Sdim CGIOperandList::OperandInfo &Op = CGI.Operands[i]; 3725288943Sdim const std::string &OpName = Op.Name; 3726288943Sdim if (OpName.empty()) 3727341825Sdim I.error("Operand #" + Twine(i) + " in operands list has no name!"); 3728218893Sdim 3729341825Sdim if (!InstInputs.count(OpName)) { 3730288943Sdim // If this is an operand with a DefaultOps set filled in, we can ignore 3731288943Sdim // this. When we codegen it, we will do so as always executed. 3732288943Sdim if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) { 3733288943Sdim // Does it have a non-empty DefaultOps field? If so, ignore this 3734288943Sdim // operand. 3735288943Sdim if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 3736288943Sdim continue; 3737193323Sed } 3738341825Sdim I.error("Operand $" + OpName + 3739288943Sdim " does not appear in the instruction pattern"); 3740288943Sdim } 3741341825Sdim TreePatternNodePtr InVal = InstInputs[OpName]; 3742341825Sdim InstInputs.erase(OpName); // It occurred, remove from map. 3743218893Sdim 3744288943Sdim if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) { 3745288943Sdim Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 3746288943Sdim if (!checkOperandClass(Op, InRec)) 3747341825Sdim I.error("Operand $" + OpName + "'s register class disagrees" 3748288943Sdim " between the operand and pattern"); 3749288943Sdim } 3750288943Sdim Operands.push_back(Op.Rec); 3751218893Sdim 3752288943Sdim // Construct the result for the dest-pattern operand list. 3753341825Sdim TreePatternNodePtr OpNode = InVal->clone(); 3754218893Sdim 3755288943Sdim // No predicate is useful on the result. 3756344779Sdim OpNode->clearPredicateCalls(); 3757218893Sdim 3758288943Sdim // Promote the xform function to be an explicit node if set. 3759288943Sdim if (Record *Xform = OpNode->getTransformFn()) { 3760288943Sdim OpNode->setTransformFn(nullptr); 3761341825Sdim std::vector<TreePatternNodePtr> Children; 3762288943Sdim Children.push_back(OpNode); 3763341825Sdim OpNode = std::make_shared<TreePatternNode>(Xform, std::move(Children), 3764341825Sdim OpNode->getNumTypes()); 3765193323Sed } 3766218893Sdim 3767341825Sdim ResultNodeOperands.push_back(std::move(OpNode)); 3768288943Sdim } 3769193323Sed 3770341825Sdim if (!InstInputs.empty()) 3771341825Sdim I.error("Input operand $" + InstInputs.begin()->first + 3772341825Sdim " occurs in pattern but not in operands list!"); 3773193323Sed 3774341825Sdim TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>( 3775341825Sdim I.getRecord(), std::move(ResultNodeOperands), 3776341825Sdim GetNumNodeResults(I.getRecord(), *this)); 3777288943Sdim // Copy fully inferred output node types to instruction result pattern. 3778288943Sdim for (unsigned i = 0; i != NumResults; ++i) { 3779288943Sdim assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"); 3780288943Sdim ResultPattern->setType(i, ResNodes[i]->getExtType(0)); 3781344779Sdim ResultPattern->setResultIndex(i, ResultIndices[i]); 3782288943Sdim } 3783193323Sed 3784341825Sdim // FIXME: Assume only the first tree is the pattern. The others are clobber 3785341825Sdim // nodes. 3786341825Sdim TreePatternNodePtr Pattern = I.getTree(0); 3787341825Sdim TreePatternNodePtr SrcPattern; 3788341825Sdim if (Pattern->getOperator()->getName() == "set") { 3789341825Sdim SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 3790341825Sdim } else{ 3791341825Sdim // Not a set (store or something?) 3792341825Sdim SrcPattern = Pattern; 3793341825Sdim } 3794341825Sdim 3795288943Sdim // Create and insert the instruction. 3796288943Sdim // FIXME: InstImpResults should not be part of DAGInstruction. 3797341825Sdim Record *R = I.getRecord(); 3798341825Sdim DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R), 3799341825Sdim std::forward_as_tuple(Results, Operands, InstImpResults, 3800341825Sdim SrcPattern, ResultPattern)); 3801193323Sed 3802341825Sdim LLVM_DEBUG(I.dump()); 3803288943Sdim} 3804288943Sdim 3805261991Sdim/// ParseInstructions - Parse all of the instructions, inlining and resolving 3806261991Sdim/// any fragments involved. This populates the Instructions list with fully 3807261991Sdim/// resolved instructions. 3808261991Sdimvoid CodeGenDAGPatterns::ParseInstructions() { 3809261991Sdim std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 3810261991Sdim 3811296417Sdim for (Record *Instr : Instrs) { 3812276479Sdim ListInit *LI = nullptr; 3813261991Sdim 3814296417Sdim if (isa<ListInit>(Instr->getValueInit("Pattern"))) 3815296417Sdim LI = Instr->getValueAsListInit("Pattern"); 3816261991Sdim 3817261991Sdim // If there is no pattern, only collect minimal information about the 3818261991Sdim // instruction for its operand list. We have to assume that there is one 3819261991Sdim // result, as we have no detailed info. A pattern which references the 3820261991Sdim // null_frag operator is as-if no pattern were specified. Normally this 3821261991Sdim // is from a multiclass expansion w/ a SDPatternOperator passed in as 3822261991Sdim // null_frag. 3823288943Sdim if (!LI || LI->empty() || hasNullFragReference(LI)) { 3824261991Sdim std::vector<Record*> Results; 3825261991Sdim std::vector<Record*> Operands; 3826261991Sdim 3827296417Sdim CodeGenInstruction &InstInfo = Target.getInstruction(Instr); 3828261991Sdim 3829261991Sdim if (InstInfo.Operands.size() != 0) { 3830288943Sdim for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j) 3831288943Sdim Results.push_back(InstInfo.Operands[j].Rec); 3832261991Sdim 3833288943Sdim // The rest are inputs. 3834288943Sdim for (unsigned j = InstInfo.Operands.NumDefs, 3835288943Sdim e = InstInfo.Operands.size(); j < e; ++j) 3836288943Sdim Operands.push_back(InstInfo.Operands[j].Rec); 3837261991Sdim } 3838261991Sdim 3839261991Sdim // Create and insert the instruction. 3840261991Sdim std::vector<Record*> ImpResults; 3841296417Sdim Instructions.insert(std::make_pair(Instr, 3842341825Sdim DAGInstruction(Results, Operands, ImpResults))); 3843261991Sdim continue; // no pattern. 3844261991Sdim } 3845261991Sdim 3846296417Sdim CodeGenInstruction &CGI = Target.getInstruction(Instr); 3847341825Sdim parseInstructionPattern(CGI, LI, Instructions); 3848261991Sdim } 3849261991Sdim 3850193323Sed // If we can, convert the instructions to be patterns that are matched! 3851296417Sdim for (auto &Entry : Instructions) { 3852341825Sdim Record *Instr = Entry.first; 3853296417Sdim DAGInstruction &TheInst = Entry.second; 3854341825Sdim TreePatternNodePtr SrcPattern = TheInst.getSrcPattern(); 3855341825Sdim TreePatternNodePtr ResultPattern = TheInst.getResultPattern(); 3856193323Sed 3857341825Sdim if (SrcPattern && ResultPattern) { 3858341825Sdim TreePattern Pattern(Instr, SrcPattern, true, *this); 3859341825Sdim TreePattern Result(Instr, ResultPattern, false, *this); 3860341825Sdim ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults()); 3861193323Sed } 3862193323Sed } 3863193323Sed} 3864193323Sed 3865341825Sdimtypedef std::pair<TreePatternNode *, unsigned> NameRecord; 3866193323Sed 3867341825Sdimstatic void FindNames(TreePatternNode *P, 3868204642Srdivacky std::map<std::string, NameRecord> &Names, 3869243830Sdim TreePattern *PatternTop) { 3870204642Srdivacky if (!P->getName().empty()) { 3871204642Srdivacky NameRecord &Rec = Names[P->getName()]; 3872204642Srdivacky // If this is the first instance of the name, remember the node. 3873204642Srdivacky if (Rec.second++ == 0) 3874204642Srdivacky Rec.first = P; 3875205407Srdivacky else if (Rec.first->getExtTypes() != P->getExtTypes()) 3876204642Srdivacky PatternTop->error("repetition of value: $" + P->getName() + 3877204642Srdivacky " where different uses have different types!"); 3878204642Srdivacky } 3879218893Sdim 3880204642Srdivacky if (!P->isLeaf()) { 3881204642Srdivacky for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 3882204642Srdivacky FindNames(P->getChild(i), Names, PatternTop); 3883204642Srdivacky } 3884204642Srdivacky} 3885204642Srdivacky 3886327952Sdimstd::vector<Predicate> CodeGenDAGPatterns::makePredList(ListInit *L) { 3887327952Sdim std::vector<Predicate> Preds; 3888327952Sdim for (Init *I : L->getValues()) { 3889327952Sdim if (DefInit *Pred = dyn_cast<DefInit>(I)) 3890327952Sdim Preds.push_back(Pred->getDef()); 3891327952Sdim else 3892327952Sdim llvm_unreachable("Non-def on the list"); 3893327952Sdim } 3894327952Sdim 3895327952Sdim // Sort so that different orders get canonicalized to the same string. 3896344779Sdim llvm::sort(Preds); 3897327952Sdim return Preds; 3898327952Sdim} 3899327952Sdim 3900243830Sdimvoid CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern, 3901321369Sdim PatternToMatch &&PTM) { 3902204642Srdivacky // Do some sanity checking on the pattern we're about to match. 3903204642Srdivacky std::string Reason; 3904243830Sdim if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) { 3905243830Sdim PrintWarning(Pattern->getRecord()->getLoc(), 3906243830Sdim Twine("Pattern can never match: ") + Reason); 3907243830Sdim return; 3908243830Sdim } 3909218893Sdim 3910204642Srdivacky // If the source pattern's root is a complex pattern, that complex pattern 3911204642Srdivacky // must specify the nodes it can potentially match. 3912204642Srdivacky if (const ComplexPattern *CP = 3913204642Srdivacky PTM.getSrcPattern()->getComplexPatternInfo(*this)) 3914204642Srdivacky if (CP->getRootNodes().empty()) 3915204642Srdivacky Pattern->error("ComplexPattern at root must specify list of opcodes it" 3916204642Srdivacky " could match"); 3917218893Sdim 3918218893Sdim 3919204642Srdivacky // Find all of the named values in the input and output, ensure they have the 3920204642Srdivacky // same type. 3921204642Srdivacky std::map<std::string, NameRecord> SrcNames, DstNames; 3922204642Srdivacky FindNames(PTM.getSrcPattern(), SrcNames, Pattern); 3923204642Srdivacky FindNames(PTM.getDstPattern(), DstNames, Pattern); 3924204642Srdivacky 3925204642Srdivacky // Scan all of the named values in the destination pattern, rejecting them if 3926204642Srdivacky // they don't exist in the input pattern. 3927296417Sdim for (const auto &Entry : DstNames) { 3928296417Sdim if (SrcNames[Entry.first].first == nullptr) 3929204642Srdivacky Pattern->error("Pattern has input without matching name in output: $" + 3930296417Sdim Entry.first); 3931204642Srdivacky } 3932218893Sdim 3933204642Srdivacky // Scan all of the named values in the source pattern, rejecting them if the 3934204642Srdivacky // name isn't used in the dest, and isn't used to tie two values together. 3935296417Sdim for (const auto &Entry : SrcNames) 3936296417Sdim if (DstNames[Entry.first].first == nullptr && 3937296417Sdim SrcNames[Entry.first].second == 1) 3938296417Sdim Pattern->error("Pattern has dead named input: $" + Entry.first); 3939218893Sdim 3940341825Sdim PatternsToMatch.push_back(PTM); 3941204642Srdivacky} 3942204642Srdivacky 3943193323Sedvoid CodeGenDAGPatterns::InferInstructionFlags() { 3944309124Sdim ArrayRef<const CodeGenInstruction*> Instructions = 3945205407Srdivacky Target.getInstructionsByEnumValue(); 3946243830Sdim 3947243830Sdim unsigned Errors = 0; 3948226633Sdim 3949341825Sdim // Try to infer flags from all patterns in PatternToMatch. These include 3950341825Sdim // both the primary instruction patterns (which always come first) and 3951341825Sdim // patterns defined outside the instruction. 3952321369Sdim for (const PatternToMatch &PTM : ptms()) { 3953243830Sdim // We can only infer from single-instruction patterns, otherwise we won't 3954243830Sdim // know which instruction should get the flags. 3955243830Sdim SmallVector<Record*, 8> PatInstrs; 3956243830Sdim getInstructionsInTree(PTM.getDstPattern(), PatInstrs); 3957243830Sdim if (PatInstrs.size() != 1) 3958243830Sdim continue; 3959243830Sdim 3960243830Sdim // Get the single instruction. 3961243830Sdim CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front()); 3962243830Sdim 3963243830Sdim // Only infer properties from the first pattern. We'll verify the others. 3964243830Sdim if (InstInfo.InferredFrom) 3965243830Sdim continue; 3966243830Sdim 3967243830Sdim InstAnalyzer PatInfo(*this); 3968321369Sdim PatInfo.Analyze(PTM); 3969243830Sdim Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord()); 3970243830Sdim } 3971243830Sdim 3972243830Sdim if (Errors) 3973243830Sdim PrintFatalError("pattern conflicts"); 3974243830Sdim 3975341825Sdim // If requested by the target, guess any undefined properties. 3976243830Sdim if (Target.guessInstructionProperties()) { 3977341825Sdim for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 3978341825Sdim CodeGenInstruction *InstInfo = 3979341825Sdim const_cast<CodeGenInstruction *>(Instructions[i]); 3980296417Sdim if (InstInfo->InferredFrom) 3981243830Sdim continue; 3982243830Sdim // The mayLoad and mayStore flags default to false. 3983243830Sdim // Conservatively assume hasSideEffects if it wasn't explicit. 3984296417Sdim if (InstInfo->hasSideEffects_Unset) 3985296417Sdim InstInfo->hasSideEffects = true; 3986243830Sdim } 3987243830Sdim return; 3988243830Sdim } 3989243830Sdim 3990243830Sdim // Complain about any flags that are still undefined. 3991341825Sdim for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 3992341825Sdim CodeGenInstruction *InstInfo = 3993341825Sdim const_cast<CodeGenInstruction *>(Instructions[i]); 3994296417Sdim if (InstInfo->InferredFrom) 3995243830Sdim continue; 3996296417Sdim if (InstInfo->hasSideEffects_Unset) 3997296417Sdim PrintError(InstInfo->TheDef->getLoc(), 3998243830Sdim "Can't infer hasSideEffects from patterns"); 3999296417Sdim if (InstInfo->mayStore_Unset) 4000296417Sdim PrintError(InstInfo->TheDef->getLoc(), 4001243830Sdim "Can't infer mayStore from patterns"); 4002296417Sdim if (InstInfo->mayLoad_Unset) 4003296417Sdim PrintError(InstInfo->TheDef->getLoc(), 4004243830Sdim "Can't infer mayLoad from patterns"); 4005243830Sdim } 4006193323Sed} 4007193323Sed 4008243830Sdim 4009243830Sdim/// Verify instruction flags against pattern node properties. 4010243830Sdimvoid CodeGenDAGPatterns::VerifyInstructionFlags() { 4011243830Sdim unsigned Errors = 0; 4012243830Sdim for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) { 4013243830Sdim const PatternToMatch &PTM = *I; 4014243830Sdim SmallVector<Record*, 8> Instrs; 4015243830Sdim getInstructionsInTree(PTM.getDstPattern(), Instrs); 4016243830Sdim if (Instrs.empty()) 4017243830Sdim continue; 4018243830Sdim 4019243830Sdim // Count the number of instructions with each flag set. 4020243830Sdim unsigned NumSideEffects = 0; 4021243830Sdim unsigned NumStores = 0; 4022243830Sdim unsigned NumLoads = 0; 4023296417Sdim for (const Record *Instr : Instrs) { 4024296417Sdim const CodeGenInstruction &InstInfo = Target.getInstruction(Instr); 4025243830Sdim NumSideEffects += InstInfo.hasSideEffects; 4026243830Sdim NumStores += InstInfo.mayStore; 4027243830Sdim NumLoads += InstInfo.mayLoad; 4028243830Sdim } 4029243830Sdim 4030243830Sdim // Analyze the source pattern. 4031243830Sdim InstAnalyzer PatInfo(*this); 4032321369Sdim PatInfo.Analyze(PTM); 4033243830Sdim 4034243830Sdim // Collect error messages. 4035243830Sdim SmallVector<std::string, 4> Msgs; 4036243830Sdim 4037243830Sdim // Check for missing flags in the output. 4038243830Sdim // Permit extra flags for now at least. 4039243830Sdim if (PatInfo.hasSideEffects && !NumSideEffects) 4040243830Sdim Msgs.push_back("pattern has side effects, but hasSideEffects isn't set"); 4041243830Sdim 4042243830Sdim // Don't verify store flags on instructions with side effects. At least for 4043243830Sdim // intrinsics, side effects implies mayStore. 4044243830Sdim if (!PatInfo.hasSideEffects && PatInfo.mayStore && !NumStores) 4045243830Sdim Msgs.push_back("pattern may store, but mayStore isn't set"); 4046243830Sdim 4047243830Sdim // Similarly, mayStore implies mayLoad on intrinsics. 4048243830Sdim if (!PatInfo.mayStore && PatInfo.mayLoad && !NumLoads) 4049243830Sdim Msgs.push_back("pattern may load, but mayLoad isn't set"); 4050243830Sdim 4051243830Sdim // Print error messages. 4052243830Sdim if (Msgs.empty()) 4053243830Sdim continue; 4054243830Sdim ++Errors; 4055243830Sdim 4056296417Sdim for (const std::string &Msg : Msgs) 4057296417Sdim PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msg) + " on the " + 4058243830Sdim (Instrs.size() == 1 ? 4059243830Sdim "instruction" : "output instructions")); 4060243830Sdim // Provide the location of the relevant instruction definitions. 4061296417Sdim for (const Record *Instr : Instrs) { 4062296417Sdim if (Instr != PTM.getSrcRecord()) 4063296417Sdim PrintError(Instr->getLoc(), "defined here"); 4064296417Sdim const CodeGenInstruction &InstInfo = Target.getInstruction(Instr); 4065243830Sdim if (InstInfo.InferredFrom && 4066243830Sdim InstInfo.InferredFrom != InstInfo.TheDef && 4067243830Sdim InstInfo.InferredFrom != PTM.getSrcRecord()) 4068296417Sdim PrintError(InstInfo.InferredFrom->getLoc(), "inferred from pattern"); 4069243830Sdim } 4070243830Sdim } 4071243830Sdim if (Errors) 4072243830Sdim PrintFatalError("Errors in DAG patterns"); 4073243830Sdim} 4074243830Sdim 4075205218Srdivacky/// Given a pattern result with an unresolved type, see if we can find one 4076205218Srdivacky/// instruction with an unresolved result type. Force this result type to an 4077205218Srdivacky/// arbitrary element if it's possible types to converge results. 4078205218Srdivackystatic bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { 4079205218Srdivacky if (N->isLeaf()) 4080205218Srdivacky return false; 4081218893Sdim 4082205218Srdivacky // Analyze children. 4083205218Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 4084205218Srdivacky if (ForceArbitraryInstResultType(N->getChild(i), TP)) 4085205218Srdivacky return true; 4086205218Srdivacky 4087205218Srdivacky if (!N->getOperator()->isSubClassOf("Instruction")) 4088205218Srdivacky return false; 4089205218Srdivacky 4090205218Srdivacky // If this type is already concrete or completely unknown we can't do 4091205218Srdivacky // anything. 4092327952Sdim TypeInfer &TI = TP.getInfer(); 4093205407Srdivacky for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) { 4094327952Sdim if (N->getExtType(i).empty() || TI.isConcrete(N->getExtType(i), false)) 4095205407Srdivacky continue; 4096218893Sdim 4097327952Sdim // Otherwise, force its type to an arbitrary choice. 4098327952Sdim if (TI.forceArbitrary(N->getExtType(i))) 4099205407Srdivacky return true; 4100205407Srdivacky } 4101218893Sdim 4102205407Srdivacky return false; 4103205218Srdivacky} 4104205218Srdivacky 4105341825Sdim// Promote xform function to be an explicit node wherever set. 4106341825Sdimstatic TreePatternNodePtr PromoteXForms(TreePatternNodePtr N) { 4107341825Sdim if (Record *Xform = N->getTransformFn()) { 4108341825Sdim N->setTransformFn(nullptr); 4109341825Sdim std::vector<TreePatternNodePtr> Children; 4110341825Sdim Children.push_back(PromoteXForms(N)); 4111341825Sdim return std::make_shared<TreePatternNode>(Xform, std::move(Children), 4112341825Sdim N->getNumTypes()); 4113341825Sdim } 4114341825Sdim 4115341825Sdim if (!N->isLeaf()) 4116341825Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 4117341825Sdim TreePatternNodePtr Child = N->getChildShared(i); 4118341825Sdim N->setChild(i, PromoteXForms(Child)); 4119341825Sdim } 4120341825Sdim return N; 4121341825Sdim} 4122341825Sdim 4123341825Sdimvoid CodeGenDAGPatterns::ParseOnePattern(Record *TheDef, 4124341825Sdim TreePattern &Pattern, TreePattern &Result, 4125341825Sdim const std::vector<Record *> &InstImpResults) { 4126341825Sdim 4127341825Sdim // Inline pattern fragments and expand multiple alternatives. 4128341825Sdim Pattern.InlinePatternFragments(); 4129341825Sdim Result.InlinePatternFragments(); 4130341825Sdim 4131341825Sdim if (Result.getNumTrees() != 1) 4132341825Sdim Result.error("Cannot use multi-alternative fragments in result pattern!"); 4133341825Sdim 4134341825Sdim // Infer types. 4135341825Sdim bool IterateInference; 4136341825Sdim bool InferredAllPatternTypes, InferredAllResultTypes; 4137341825Sdim do { 4138341825Sdim // Infer as many types as possible. If we cannot infer all of them, we 4139341825Sdim // can never do anything with this pattern: report it to the user. 4140341825Sdim InferredAllPatternTypes = 4141341825Sdim Pattern.InferAllTypes(&Pattern.getNamedNodesMap()); 4142341825Sdim 4143341825Sdim // Infer as many types as possible. If we cannot infer all of them, we 4144341825Sdim // can never do anything with this pattern: report it to the user. 4145341825Sdim InferredAllResultTypes = 4146341825Sdim Result.InferAllTypes(&Pattern.getNamedNodesMap()); 4147341825Sdim 4148341825Sdim IterateInference = false; 4149341825Sdim 4150341825Sdim // Apply the type of the result to the source pattern. This helps us 4151341825Sdim // resolve cases where the input type is known to be a pointer type (which 4152341825Sdim // is considered resolved), but the result knows it needs to be 32- or 4153341825Sdim // 64-bits. Infer the other way for good measure. 4154341825Sdim for (auto T : Pattern.getTrees()) 4155341825Sdim for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(), 4156341825Sdim T->getNumTypes()); 4157341825Sdim i != e; ++i) { 4158341825Sdim IterateInference |= T->UpdateNodeType( 4159341825Sdim i, Result.getOnlyTree()->getExtType(i), Result); 4160341825Sdim IterateInference |= Result.getOnlyTree()->UpdateNodeType( 4161341825Sdim i, T->getExtType(i), Result); 4162341825Sdim } 4163341825Sdim 4164341825Sdim // If our iteration has converged and the input pattern's types are fully 4165341825Sdim // resolved but the result pattern is not fully resolved, we may have a 4166341825Sdim // situation where we have two instructions in the result pattern and 4167341825Sdim // the instructions require a common register class, but don't care about 4168341825Sdim // what actual MVT is used. This is actually a bug in our modelling: 4169341825Sdim // output patterns should have register classes, not MVTs. 4170341825Sdim // 4171341825Sdim // In any case, to handle this, we just go through and disambiguate some 4172341825Sdim // arbitrary types to the result pattern's nodes. 4173341825Sdim if (!IterateInference && InferredAllPatternTypes && 4174341825Sdim !InferredAllResultTypes) 4175341825Sdim IterateInference = 4176341825Sdim ForceArbitraryInstResultType(Result.getTree(0).get(), Result); 4177341825Sdim } while (IterateInference); 4178341825Sdim 4179341825Sdim // Verify that we inferred enough types that we can do something with the 4180341825Sdim // pattern and result. If these fire the user has to add type casts. 4181341825Sdim if (!InferredAllPatternTypes) 4182341825Sdim Pattern.error("Could not infer all types in pattern!"); 4183341825Sdim if (!InferredAllResultTypes) { 4184341825Sdim Pattern.dump(); 4185341825Sdim Result.error("Could not infer all types in pattern result!"); 4186341825Sdim } 4187341825Sdim 4188341825Sdim // Promote xform function to be an explicit node wherever set. 4189341825Sdim TreePatternNodePtr DstShared = PromoteXForms(Result.getOnlyTree()); 4190341825Sdim 4191341825Sdim TreePattern Temp(Result.getRecord(), DstShared, false, *this); 4192341825Sdim Temp.InferAllTypes(); 4193341825Sdim 4194341825Sdim ListInit *Preds = TheDef->getValueAsListInit("Predicates"); 4195341825Sdim int Complexity = TheDef->getValueAsInt("AddedComplexity"); 4196341825Sdim 4197341825Sdim if (PatternRewriter) 4198341825Sdim PatternRewriter(&Pattern); 4199341825Sdim 4200341825Sdim // A pattern may end up with an "impossible" type, i.e. a situation 4201341825Sdim // where all types have been eliminated for some node in this pattern. 4202341825Sdim // This could occur for intrinsics that only make sense for a specific 4203341825Sdim // value type, and use a specific register class. If, for some mode, 4204341825Sdim // that register class does not accept that type, the type inference 4205341825Sdim // will lead to a contradiction, which is not an error however, but 4206341825Sdim // a sign that this pattern will simply never match. 4207341825Sdim if (Temp.getOnlyTree()->hasPossibleType()) 4208341825Sdim for (auto T : Pattern.getTrees()) 4209341825Sdim if (T->hasPossibleType()) 4210341825Sdim AddPatternToMatch(&Pattern, 4211341825Sdim PatternToMatch(TheDef, makePredList(Preds), 4212341825Sdim T, Temp.getOnlyTree(), 4213341825Sdim InstImpResults, Complexity, 4214341825Sdim TheDef->getID())); 4215341825Sdim} 4216341825Sdim 4217193323Sedvoid CodeGenDAGPatterns::ParsePatterns() { 4218193323Sed std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 4219193323Sed 4220296417Sdim for (Record *CurPattern : Patterns) { 4221205407Srdivacky DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); 4222239462Sdim 4223239462Sdim // If the pattern references the null_frag, there's nothing to do. 4224239462Sdim if (hasNullFragReference(Tree)) 4225239462Sdim continue; 4226239462Sdim 4227341825Sdim TreePattern Pattern(CurPattern, Tree, true, *this); 4228193323Sed 4229205407Srdivacky ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); 4230288943Sdim if (LI->empty()) continue; // no pattern. 4231218893Sdim 4232193323Sed // Parse the instruction. 4233280031Sdim TreePattern Result(CurPattern, LI, false, *this); 4234218893Sdim 4235280031Sdim if (Result.getNumTrees() != 1) 4236280031Sdim Result.error("Cannot handle instructions producing instructions " 4237280031Sdim "with temporaries yet!"); 4238218893Sdim 4239193323Sed // Validate that the input pattern is correct. 4240341825Sdim std::map<std::string, TreePatternNodePtr> InstInputs; 4241344779Sdim MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>> 4242344779Sdim InstResults; 4243193323Sed std::vector<Record*> InstImpResults; 4244341825Sdim for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j) 4245341825Sdim FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs, 4246341825Sdim InstResults, InstImpResults); 4247193323Sed 4248341825Sdim ParseOnePattern(CurPattern, Pattern, Result, InstImpResults); 4249193323Sed } 4250193323Sed} 4251193323Sed 4252327952Sdimstatic void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) { 4253327952Sdim for (const TypeSetByHwMode &VTS : N->getExtTypes()) 4254327952Sdim for (const auto &I : VTS) 4255327952Sdim Modes.insert(I.first); 4256327952Sdim 4257327952Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 4258327952Sdim collectModes(Modes, N->getChild(i)); 4259327952Sdim} 4260327952Sdim 4261327952Sdimvoid CodeGenDAGPatterns::ExpandHwModeBasedTypes() { 4262327952Sdim const CodeGenHwModes &CGH = getTargetInfo().getHwModes(); 4263327952Sdim std::map<unsigned,std::vector<Predicate>> ModeChecks; 4264327952Sdim std::vector<PatternToMatch> Copy = PatternsToMatch; 4265327952Sdim PatternsToMatch.clear(); 4266327952Sdim 4267341825Sdim auto AppendPattern = [this, &ModeChecks](PatternToMatch &P, unsigned Mode) { 4268341825Sdim TreePatternNodePtr NewSrc = P.SrcPattern->clone(); 4269341825Sdim TreePatternNodePtr NewDst = P.DstPattern->clone(); 4270327952Sdim if (!NewSrc->setDefaultMode(Mode) || !NewDst->setDefaultMode(Mode)) { 4271327952Sdim return; 4272327952Sdim } 4273327952Sdim 4274327952Sdim std::vector<Predicate> Preds = P.Predicates; 4275327952Sdim const std::vector<Predicate> &MC = ModeChecks[Mode]; 4276327952Sdim Preds.insert(Preds.end(), MC.begin(), MC.end()); 4277341825Sdim PatternsToMatch.emplace_back(P.getSrcRecord(), Preds, std::move(NewSrc), 4278341825Sdim std::move(NewDst), P.getDstRegs(), 4279341825Sdim P.getAddedComplexity(), Record::getNewUID(), 4280341825Sdim Mode); 4281327952Sdim }; 4282327952Sdim 4283327952Sdim for (PatternToMatch &P : Copy) { 4284341825Sdim TreePatternNodePtr SrcP = nullptr, DstP = nullptr; 4285327952Sdim if (P.SrcPattern->hasProperTypeByHwMode()) 4286327952Sdim SrcP = P.SrcPattern; 4287327952Sdim if (P.DstPattern->hasProperTypeByHwMode()) 4288327952Sdim DstP = P.DstPattern; 4289327952Sdim if (!SrcP && !DstP) { 4290327952Sdim PatternsToMatch.push_back(P); 4291327952Sdim continue; 4292327952Sdim } 4293327952Sdim 4294327952Sdim std::set<unsigned> Modes; 4295327952Sdim if (SrcP) 4296341825Sdim collectModes(Modes, SrcP.get()); 4297327952Sdim if (DstP) 4298341825Sdim collectModes(Modes, DstP.get()); 4299327952Sdim 4300327952Sdim // The predicate for the default mode needs to be constructed for each 4301327952Sdim // pattern separately. 4302327952Sdim // Since not all modes must be present in each pattern, if a mode m is 4303327952Sdim // absent, then there is no point in constructing a check for m. If such 4304327952Sdim // a check was created, it would be equivalent to checking the default 4305327952Sdim // mode, except not all modes' predicates would be a part of the checking 4306327952Sdim // code. The subsequently generated check for the default mode would then 4307327952Sdim // have the exact same patterns, but a different predicate code. To avoid 4308327952Sdim // duplicated patterns with different predicate checks, construct the 4309327952Sdim // default check as a negation of all predicates that are actually present 4310327952Sdim // in the source/destination patterns. 4311327952Sdim std::vector<Predicate> DefaultPred; 4312327952Sdim 4313327952Sdim for (unsigned M : Modes) { 4314327952Sdim if (M == DefaultMode) 4315327952Sdim continue; 4316327952Sdim if (ModeChecks.find(M) != ModeChecks.end()) 4317327952Sdim continue; 4318327952Sdim 4319327952Sdim // Fill the map entry for this mode. 4320327952Sdim const HwMode &HM = CGH.getMode(M); 4321327952Sdim ModeChecks[M].emplace_back(Predicate(HM.Features, true)); 4322327952Sdim 4323327952Sdim // Add negations of the HM's predicates to the default predicate. 4324327952Sdim DefaultPred.emplace_back(Predicate(HM.Features, false)); 4325327952Sdim } 4326327952Sdim 4327327952Sdim for (unsigned M : Modes) { 4328327952Sdim if (M == DefaultMode) 4329327952Sdim continue; 4330327952Sdim AppendPattern(P, M); 4331327952Sdim } 4332327952Sdim 4333327952Sdim bool HasDefault = Modes.count(DefaultMode); 4334327952Sdim if (HasDefault) 4335327952Sdim AppendPattern(P, DefaultMode); 4336327952Sdim } 4337327952Sdim} 4338327952Sdim 4339327952Sdim/// Dependent variable map for CodeGenDAGPattern variant generation 4340327952Sdimtypedef StringMap<int> DepVarMap; 4341327952Sdim 4342327952Sdimstatic void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 4343327952Sdim if (N->isLeaf()) { 4344327952Sdim if (N->hasName() && isa<DefInit>(N->getLeafValue())) 4345327952Sdim DepMap[N->getName()]++; 4346327952Sdim } else { 4347327952Sdim for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 4348327952Sdim FindDepVarsOf(N->getChild(i), DepMap); 4349327952Sdim } 4350327952Sdim} 4351327952Sdim 4352327952Sdim/// Find dependent variables within child patterns 4353327952Sdimstatic void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 4354327952Sdim DepVarMap depcounts; 4355327952Sdim FindDepVarsOf(N, depcounts); 4356327952Sdim for (const auto &Pair : depcounts) { 4357327952Sdim if (Pair.getValue() > 1) 4358327952Sdim DepVars.insert(Pair.getKey()); 4359327952Sdim } 4360327952Sdim} 4361327952Sdim 4362327952Sdim#ifndef NDEBUG 4363327952Sdim/// Dump the dependent variable set: 4364327952Sdimstatic void DumpDepVars(MultipleUseVarSet &DepVars) { 4365327952Sdim if (DepVars.empty()) { 4366341825Sdim LLVM_DEBUG(errs() << "<empty set>"); 4367327952Sdim } else { 4368341825Sdim LLVM_DEBUG(errs() << "[ "); 4369327952Sdim for (const auto &DepVar : DepVars) { 4370341825Sdim LLVM_DEBUG(errs() << DepVar.getKey() << " "); 4371327952Sdim } 4372341825Sdim LLVM_DEBUG(errs() << "]"); 4373327952Sdim } 4374327952Sdim} 4375327952Sdim#endif 4376327952Sdim 4377327952Sdim 4378193323Sed/// CombineChildVariants - Given a bunch of permutations of each child of the 4379193323Sed/// 'operator' node, put them together in all possible ways. 4380341825Sdimstatic void CombineChildVariants( 4381341825Sdim TreePatternNodePtr Orig, 4382341825Sdim const std::vector<std::vector<TreePatternNodePtr>> &ChildVariants, 4383341825Sdim std::vector<TreePatternNodePtr> &OutVariants, CodeGenDAGPatterns &CDP, 4384341825Sdim const MultipleUseVarSet &DepVars) { 4385193323Sed // Make sure that each operand has at least one variant to choose from. 4386296417Sdim for (const auto &Variants : ChildVariants) 4387296417Sdim if (Variants.empty()) 4388193323Sed return; 4389218893Sdim 4390193323Sed // The end result is an all-pairs construction of the resultant pattern. 4391193323Sed std::vector<unsigned> Idxs; 4392193323Sed Idxs.resize(ChildVariants.size()); 4393193323Sed bool NotDone; 4394193323Sed do { 4395193323Sed#ifndef NDEBUG 4396341825Sdim LLVM_DEBUG(if (!Idxs.empty()) { 4397341825Sdim errs() << Orig->getOperator()->getName() << ": Idxs = [ "; 4398341825Sdim for (unsigned Idx : Idxs) { 4399341825Sdim errs() << Idx << " "; 4400341825Sdim } 4401341825Sdim errs() << "]\n"; 4402341825Sdim }); 4403193323Sed#endif 4404193323Sed // Create the variant and add it to the output list. 4405341825Sdim std::vector<TreePatternNodePtr> NewChildren; 4406193323Sed for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 4407193323Sed NewChildren.push_back(ChildVariants[i][Idxs[i]]); 4408341825Sdim TreePatternNodePtr R = std::make_shared<TreePatternNode>( 4409341825Sdim Orig->getOperator(), std::move(NewChildren), Orig->getNumTypes()); 4410218893Sdim 4411193323Sed // Copy over properties. 4412193323Sed R->setName(Orig->getName()); 4413344779Sdim R->setNamesAsPredicateArg(Orig->getNamesAsPredicateArg()); 4414344779Sdim R->setPredicateCalls(Orig->getPredicateCalls()); 4415193323Sed R->setTransformFn(Orig->getTransformFn()); 4416205407Srdivacky for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) 4417205407Srdivacky R->setType(i, Orig->getExtType(i)); 4418218893Sdim 4419193323Sed // If this pattern cannot match, do not include it as a variant. 4420193323Sed std::string ErrString; 4421296417Sdim // Scan to see if this pattern has already been emitted. We can get 4422296417Sdim // duplication due to things like commuting: 4423296417Sdim // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 4424296417Sdim // which are the same pattern. Ignore the dups. 4425296417Sdim if (R->canPatternMatch(ErrString, CDP) && 4426341825Sdim none_of(OutVariants, [&](TreePatternNodePtr Variant) { 4427341825Sdim return R->isIsomorphicTo(Variant.get(), DepVars); 4428314564Sdim })) 4429341825Sdim OutVariants.push_back(R); 4430218893Sdim 4431193323Sed // Increment indices to the next permutation by incrementing the 4432296417Sdim // indices from last index backward, e.g., generate the sequence 4433193323Sed // [0, 0], [0, 1], [1, 0], [1, 1]. 4434193323Sed int IdxsIdx; 4435193323Sed for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 4436193323Sed if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 4437193323Sed Idxs[IdxsIdx] = 0; 4438193323Sed else 4439193323Sed break; 4440193323Sed } 4441193323Sed NotDone = (IdxsIdx >= 0); 4442193323Sed } while (NotDone); 4443193323Sed} 4444193323Sed 4445193323Sed/// CombineChildVariants - A helper function for binary operators. 4446193323Sed/// 4447341825Sdimstatic void CombineChildVariants(TreePatternNodePtr Orig, 4448341825Sdim const std::vector<TreePatternNodePtr> &LHS, 4449341825Sdim const std::vector<TreePatternNodePtr> &RHS, 4450341825Sdim std::vector<TreePatternNodePtr> &OutVariants, 4451193323Sed CodeGenDAGPatterns &CDP, 4452193323Sed const MultipleUseVarSet &DepVars) { 4453341825Sdim std::vector<std::vector<TreePatternNodePtr>> ChildVariants; 4454193323Sed ChildVariants.push_back(LHS); 4455193323Sed ChildVariants.push_back(RHS); 4456193323Sed CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 4457218893Sdim} 4458193323Sed 4459341825Sdimstatic void 4460341825SdimGatherChildrenOfAssociativeOpcode(TreePatternNodePtr N, 4461341825Sdim std::vector<TreePatternNodePtr> &Children) { 4462193323Sed assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 4463193323Sed Record *Operator = N->getOperator(); 4464218893Sdim 4465193323Sed // Only permit raw nodes. 4466344779Sdim if (!N->getName().empty() || !N->getPredicateCalls().empty() || 4467193323Sed N->getTransformFn()) { 4468193323Sed Children.push_back(N); 4469193323Sed return; 4470193323Sed } 4471193323Sed 4472193323Sed if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 4473341825Sdim Children.push_back(N->getChildShared(0)); 4474193323Sed else 4475341825Sdim GatherChildrenOfAssociativeOpcode(N->getChildShared(0), Children); 4476193323Sed 4477193323Sed if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 4478341825Sdim Children.push_back(N->getChildShared(1)); 4479193323Sed else 4480341825Sdim GatherChildrenOfAssociativeOpcode(N->getChildShared(1), Children); 4481193323Sed} 4482193323Sed 4483193323Sed/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 4484193323Sed/// the (potentially recursive) pattern by using algebraic laws. 4485193323Sed/// 4486341825Sdimstatic void GenerateVariantsOf(TreePatternNodePtr N, 4487341825Sdim std::vector<TreePatternNodePtr> &OutVariants, 4488193323Sed CodeGenDAGPatterns &CDP, 4489193323Sed const MultipleUseVarSet &DepVars) { 4490276479Sdim // We cannot permute leaves or ComplexPattern uses. 4491276479Sdim if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) { 4492193323Sed OutVariants.push_back(N); 4493193323Sed return; 4494193323Sed } 4495193323Sed 4496193323Sed // Look up interesting info about the node. 4497193323Sed const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 4498193323Sed 4499193323Sed // If this node is associative, re-associate. 4500193323Sed if (NodeInfo.hasProperty(SDNPAssociative)) { 4501218893Sdim // Re-associate by pulling together all of the linked operators 4502341825Sdim std::vector<TreePatternNodePtr> MaximalChildren; 4503193323Sed GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 4504193323Sed 4505193323Sed // Only handle child sizes of 3. Otherwise we'll end up trying too many 4506193323Sed // permutations. 4507193323Sed if (MaximalChildren.size() == 3) { 4508193323Sed // Find the variants of all of our maximal children. 4509341825Sdim std::vector<TreePatternNodePtr> AVariants, BVariants, CVariants; 4510193323Sed GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 4511193323Sed GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 4512193323Sed GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 4513218893Sdim 4514193323Sed // There are only two ways we can permute the tree: 4515193323Sed // (A op B) op C and A op (B op C) 4516193323Sed // Within these forms, we can also permute A/B/C. 4517218893Sdim 4518193323Sed // Generate legal pair permutations of A/B/C. 4519341825Sdim std::vector<TreePatternNodePtr> ABVariants; 4520341825Sdim std::vector<TreePatternNodePtr> BAVariants; 4521341825Sdim std::vector<TreePatternNodePtr> ACVariants; 4522341825Sdim std::vector<TreePatternNodePtr> CAVariants; 4523341825Sdim std::vector<TreePatternNodePtr> BCVariants; 4524341825Sdim std::vector<TreePatternNodePtr> CBVariants; 4525193323Sed CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 4526193323Sed CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 4527193323Sed CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 4528193323Sed CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 4529193323Sed CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 4530193323Sed CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 4531193323Sed 4532193323Sed // Combine those into the result: (x op x) op x 4533193323Sed CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 4534193323Sed CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 4535193323Sed CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 4536193323Sed CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 4537193323Sed CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 4538193323Sed CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 4539193323Sed 4540193323Sed // Combine those into the result: x op (x op x) 4541193323Sed CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 4542193323Sed CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 4543193323Sed CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 4544193323Sed CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 4545193323Sed CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 4546193323Sed CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 4547193323Sed return; 4548193323Sed } 4549193323Sed } 4550218893Sdim 4551193323Sed // Compute permutations of all children. 4552341825Sdim std::vector<std::vector<TreePatternNodePtr>> ChildVariants; 4553193323Sed ChildVariants.resize(N->getNumChildren()); 4554193323Sed for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 4555341825Sdim GenerateVariantsOf(N->getChildShared(i), ChildVariants[i], CDP, DepVars); 4556193323Sed 4557193323Sed // Build all permutations based on how the children were formed. 4558193323Sed CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 4559193323Sed 4560193323Sed // If this node is commutative, consider the commuted order. 4561193323Sed bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP); 4562193323Sed if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 4563327952Sdim assert((N->getNumChildren()>=2 || isCommIntrinsic) && 4564193323Sed "Commutative but doesn't have 2 children!"); 4565193323Sed // Don't count children which are actually register references. 4566193323Sed unsigned NC = 0; 4567193323Sed for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 4568193323Sed TreePatternNode *Child = N->getChild(i); 4569193323Sed if (Child->isLeaf()) 4570243830Sdim if (DefInit *DI = dyn_cast<DefInit>(Child->getLeafValue())) { 4571193323Sed Record *RR = DI->getDef(); 4572193323Sed if (RR->isSubClassOf("Register")) 4573193323Sed continue; 4574193323Sed } 4575193323Sed NC++; 4576193323Sed } 4577193323Sed // Consider the commuted order. 4578193323Sed if (isCommIntrinsic) { 4579193323Sed // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd 4580193323Sed // operands are the commutative operands, and there might be more operands 4581193323Sed // after those. 4582193323Sed assert(NC >= 3 && 4583296417Sdim "Commutative intrinsic should have at least 3 children!"); 4584341825Sdim std::vector<std::vector<TreePatternNodePtr>> Variants; 4585341825Sdim Variants.push_back(std::move(ChildVariants[0])); // Intrinsic id. 4586341825Sdim Variants.push_back(std::move(ChildVariants[2])); 4587341825Sdim Variants.push_back(std::move(ChildVariants[1])); 4588193323Sed for (unsigned i = 3; i != NC; ++i) 4589341825Sdim Variants.push_back(std::move(ChildVariants[i])); 4590193323Sed CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 4591327952Sdim } else if (NC == N->getNumChildren()) { 4592341825Sdim std::vector<std::vector<TreePatternNodePtr>> Variants; 4593341825Sdim Variants.push_back(std::move(ChildVariants[1])); 4594341825Sdim Variants.push_back(std::move(ChildVariants[0])); 4595327952Sdim for (unsigned i = 2; i != NC; ++i) 4596341825Sdim Variants.push_back(std::move(ChildVariants[i])); 4597327952Sdim CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 4598327952Sdim } 4599193323Sed } 4600193323Sed} 4601193323Sed 4602193323Sed 4603193323Sed// GenerateVariants - Generate variants. For example, commutative patterns can 4604193323Sed// match multiple ways. Add them to PatternsToMatch as well. 4605193323Sedvoid CodeGenDAGPatterns::GenerateVariants() { 4606341825Sdim LLVM_DEBUG(errs() << "Generating instruction variants.\n"); 4607218893Sdim 4608193323Sed // Loop over all of the patterns we've collected, checking to see if we can 4609193323Sed // generate variants of the instruction, through the exploitation of 4610193323Sed // identities. This permits the target to provide aggressive matching without 4611193323Sed // the .td file having to contain tons of variants of instructions. 4612193323Sed // 4613193323Sed // Note that this loop adds new patterns to the PatternsToMatch list, but we 4614193323Sed // intentionally do not reconsider these. Any variants of added patterns have 4615193323Sed // already been added. 4616193323Sed // 4617344779Sdim const unsigned NumOriginalPatterns = PatternsToMatch.size(); 4618344779Sdim BitVector MatchedPatterns(NumOriginalPatterns); 4619344779Sdim std::vector<BitVector> MatchedPredicates(NumOriginalPatterns, 4620344779Sdim BitVector(NumOriginalPatterns)); 4621344779Sdim 4622344779Sdim typedef std::pair<MultipleUseVarSet, std::vector<TreePatternNodePtr>> 4623344779Sdim DepsAndVariants; 4624344779Sdim std::map<unsigned, DepsAndVariants> PatternsWithVariants; 4625344779Sdim 4626344779Sdim // Collect patterns with more than one variant. 4627344779Sdim for (unsigned i = 0; i != NumOriginalPatterns; ++i) { 4628344779Sdim MultipleUseVarSet DepVars; 4629341825Sdim std::vector<TreePatternNodePtr> Variants; 4630193323Sed FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 4631341825Sdim LLVM_DEBUG(errs() << "Dependent/multiply used variables: "); 4632341825Sdim LLVM_DEBUG(DumpDepVars(DepVars)); 4633341825Sdim LLVM_DEBUG(errs() << "\n"); 4634341825Sdim GenerateVariantsOf(PatternsToMatch[i].getSrcPatternShared(), Variants, 4635341825Sdim *this, DepVars); 4636193323Sed 4637193323Sed assert(!Variants.empty() && "Must create at least original variant!"); 4638344779Sdim if (Variants.size() == 1) // No additional variants for this pattern. 4639193323Sed continue; 4640193323Sed 4641341825Sdim LLVM_DEBUG(errs() << "FOUND VARIANTS OF: "; 4642341825Sdim PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n"); 4643193323Sed 4644344779Sdim PatternsWithVariants[i] = std::make_pair(DepVars, Variants); 4645344779Sdim 4646344779Sdim // Cache matching predicates. 4647344779Sdim if (MatchedPatterns[i]) 4648344779Sdim continue; 4649344779Sdim 4650344779Sdim const std::vector<Predicate> &Predicates = 4651344779Sdim PatternsToMatch[i].getPredicates(); 4652344779Sdim 4653344779Sdim BitVector &Matches = MatchedPredicates[i]; 4654344779Sdim MatchedPatterns.set(i); 4655344779Sdim Matches.set(i); 4656344779Sdim 4657344779Sdim // Don't test patterns that have already been cached - it won't match. 4658344779Sdim for (unsigned p = 0; p != NumOriginalPatterns; ++p) 4659344779Sdim if (!MatchedPatterns[p]) 4660344779Sdim Matches[p] = (Predicates == PatternsToMatch[p].getPredicates()); 4661344779Sdim 4662344779Sdim // Copy this to all the matching patterns. 4663344779Sdim for (int p = Matches.find_first(); p != -1; p = Matches.find_next(p)) 4664344779Sdim if (p != (int)i) { 4665344779Sdim MatchedPatterns.set(p); 4666344779Sdim MatchedPredicates[p] = Matches; 4667344779Sdim } 4668344779Sdim } 4669344779Sdim 4670344779Sdim for (auto it : PatternsWithVariants) { 4671344779Sdim unsigned i = it.first; 4672344779Sdim const MultipleUseVarSet &DepVars = it.second.first; 4673344779Sdim const std::vector<TreePatternNodePtr> &Variants = it.second.second; 4674344779Sdim 4675193323Sed for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 4676341825Sdim TreePatternNodePtr Variant = Variants[v]; 4677344779Sdim BitVector &Matches = MatchedPredicates[i]; 4678193323Sed 4679341825Sdim LLVM_DEBUG(errs() << " VAR#" << v << ": "; Variant->dump(); 4680341825Sdim errs() << "\n"); 4681218893Sdim 4682193323Sed // Scan to see if an instruction or explicit pattern already matches this. 4683193323Sed bool AlreadyExists = false; 4684193323Sed for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 4685195098Sed // Skip if the top level predicates do not match. 4686344779Sdim if (!Matches[p]) 4687195098Sed continue; 4688193323Sed // Check to see if this variant already exists. 4689218893Sdim if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), 4690218893Sdim DepVars)) { 4691341825Sdim LLVM_DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n"); 4692193323Sed AlreadyExists = true; 4693193323Sed break; 4694193323Sed } 4695193323Sed } 4696193323Sed // If we already have it, ignore the variant. 4697193323Sed if (AlreadyExists) continue; 4698193323Sed 4699193323Sed // Otherwise, add it to the list of patterns we have. 4700321369Sdim PatternsToMatch.push_back(PatternToMatch( 4701288943Sdim PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(), 4702341825Sdim Variant, PatternsToMatch[i].getDstPatternShared(), 4703288943Sdim PatternsToMatch[i].getDstRegs(), 4704321369Sdim PatternsToMatch[i].getAddedComplexity(), Record::getNewUID())); 4705344779Sdim MatchedPredicates.push_back(Matches); 4706344779Sdim 4707344779Sdim // Add a new match the same as this pattern. 4708344779Sdim for (auto &P : MatchedPredicates) 4709344779Sdim P.push_back(P[i]); 4710193323Sed } 4711193323Sed 4712341825Sdim LLVM_DEBUG(errs() << "\n"); 4713193323Sed } 4714193323Sed} 4715