CodeGenDAGPatterns.cpp revision 344779
1193323Sed//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the CodeGenDAGPatterns class, which is used to read and 11193323Sed// represent the patterns present in a .td file for instructions. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "CodeGenDAGPatterns.h" 16344779Sdim#include "llvm/ADT/BitVector.h" 17327952Sdim#include "llvm/ADT/DenseSet.h" 18344779Sdim#include "llvm/ADT/MapVector.h" 19249423Sdim#include "llvm/ADT/STLExtras.h" 20327952Sdim#include "llvm/ADT/SmallSet.h" 21296417Sdim#include "llvm/ADT/SmallString.h" 22193323Sed#include "llvm/ADT/StringExtras.h" 23327952Sdim#include "llvm/ADT/StringMap.h" 24234982Sdim#include "llvm/ADT/Twine.h" 25193323Sed#include "llvm/Support/Debug.h" 26234353Sdim#include "llvm/Support/ErrorHandling.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) { 71327952Sdim for (const ValueTypeByHwMode &VVT : VTList) 72327952Sdim insert(VVT); 73327952Sdim} 74218893Sdim 75327952Sdimbool TypeSetByHwMode::isValueTypeByHwMode(bool AllowEmpty) const { 76327952Sdim for (const auto &I : *this) { 77327952Sdim if (I.second.size() > 1) 78327952Sdim return false; 79327952Sdim if (!AllowEmpty && I.second.empty()) 80327952Sdim return false; 81327952Sdim } 82327952Sdim return true; 83193323Sed} 84193323Sed 85327952SdimValueTypeByHwMode TypeSetByHwMode::getValueTypeByHwMode() const { 86327952Sdim assert(isValueTypeByHwMode(true) && 87327952Sdim "The type set has multiple types for at least one HW mode"); 88327952Sdim ValueTypeByHwMode VVT; 89327952Sdim for (const auto &I : *this) { 90327952Sdim MVT T = I.second.empty() ? MVT::Other : *I.second.begin(); 91327952Sdim VVT.getOrCreateTypeForMode(I.first, T); 92327952Sdim } 93327952Sdim return VVT; 94327952Sdim} 95218893Sdim 96327952Sdimbool TypeSetByHwMode::isPossible() const { 97327952Sdim for (const auto &I : *this) 98327952Sdim if (!I.second.empty()) 99327952Sdim return true; 100327952Sdim return false; 101327952Sdim} 102243830Sdim 103327952Sdimbool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) { 104327952Sdim bool Changed = false; 105344779Sdim bool ContainsDefault = false; 106344779Sdim MVT DT = MVT::Other; 107344779Sdim 108327952Sdim SmallDenseSet<unsigned, 4> Modes; 109327952Sdim for (const auto &P : VVT) { 110327952Sdim unsigned M = P.first; 111327952Sdim Modes.insert(M); 112327952Sdim // Make sure there exists a set for each specific mode from VVT. 113327952Sdim Changed |= getOrCreate(M).insert(P.second).second; 114344779Sdim // Cache VVT's default mode. 115344779Sdim if (DefaultMode == M) { 116344779Sdim ContainsDefault = true; 117344779Sdim DT = P.second; 118344779Sdim } 119327952Sdim } 120205218Srdivacky 121327952Sdim // If VVT has a default mode, add the corresponding type to all 122327952Sdim // modes in "this" that do not exist in VVT. 123344779Sdim if (ContainsDefault) 124327952Sdim for (auto &I : *this) 125327952Sdim if (!Modes.count(I.first)) 126327952Sdim Changed |= I.second.insert(DT).second; 127344779Sdim 128327952Sdim return Changed; 129327952Sdim} 130205407Srdivacky 131327952Sdim// Constrain the type set to be the intersection with VTS. 132327952Sdimbool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) { 133327952Sdim bool Changed = false; 134327952Sdim if (hasDefault()) { 135327952Sdim for (const auto &I : VTS) { 136327952Sdim unsigned M = I.first; 137327952Sdim if (M == DefaultMode || hasMode(M)) 138327952Sdim continue; 139327952Sdim Map.insert({M, Map.at(DefaultMode)}); 140327952Sdim Changed = true; 141327952Sdim } 142327952Sdim } 143218893Sdim 144327952Sdim for (auto &I : *this) { 145327952Sdim unsigned M = I.first; 146327952Sdim SetType &S = I.second; 147327952Sdim if (VTS.hasMode(M) || VTS.hasDefault()) { 148327952Sdim Changed |= intersect(I.second, VTS.get(M)); 149327952Sdim } else if (!S.empty()) { 150327952Sdim S.clear(); 151327952Sdim Changed = true; 152327952Sdim } 153327952Sdim } 154327952Sdim return Changed; 155205407Srdivacky} 156205407Srdivacky 157327952Sdimtemplate <typename Predicate> 158327952Sdimbool TypeSetByHwMode::constrain(Predicate P) { 159327952Sdim bool Changed = false; 160327952Sdim for (auto &I : *this) 161327952Sdim Changed |= berase_if(I.second, [&P](MVT VT) { return !P(VT); }); 162327952Sdim return Changed; 163218893Sdim} 164205218Srdivacky 165327952Sdimtemplate <typename Predicate> 166327952Sdimbool TypeSetByHwMode::assign_if(const TypeSetByHwMode &VTS, Predicate P) { 167327952Sdim assert(empty()); 168327952Sdim for (const auto &I : VTS) { 169327952Sdim SetType &S = getOrCreate(I.first); 170327952Sdim for (auto J : I.second) 171327952Sdim if (P(J)) 172327952Sdim S.insert(J); 173327952Sdim } 174327952Sdim return !empty(); 175218893Sdim} 176205218Srdivacky 177327952Sdimvoid TypeSetByHwMode::writeToStream(raw_ostream &OS) const { 178327952Sdim SmallVector<unsigned, 4> Modes; 179327952Sdim Modes.reserve(Map.size()); 180327952Sdim 181327952Sdim for (const auto &I : *this) 182327952Sdim Modes.push_back(I.first); 183327952Sdim if (Modes.empty()) { 184327952Sdim OS << "{}"; 185327952Sdim return; 186327952Sdim } 187327952Sdim array_pod_sort(Modes.begin(), Modes.end()); 188327952Sdim 189327952Sdim OS << '{'; 190327952Sdim for (unsigned M : Modes) { 191327952Sdim OS << ' ' << getModeName(M) << ':'; 192327952Sdim writeToStream(get(M), OS); 193327952Sdim } 194327952Sdim OS << " }"; 195276479Sdim} 196276479Sdim 197327952Sdimvoid TypeSetByHwMode::writeToStream(const SetType &S, raw_ostream &OS) { 198327952Sdim SmallVector<MVT, 4> Types(S.begin(), S.end()); 199327952Sdim array_pod_sort(Types.begin(), Types.end()); 200327952Sdim 201327952Sdim OS << '['; 202327952Sdim for (unsigned i = 0, e = Types.size(); i != e; ++i) { 203327952Sdim OS << ValueTypeByHwMode::getMVTName(Types[i]); 204327952Sdim if (i != e-1) 205327952Sdim OS << ' '; 206327952Sdim } 207327952Sdim OS << ']'; 208193323Sed} 209198090Srdivacky 210327952Sdimbool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const { 211344779Sdim // The isSimple call is much quicker than hasDefault - check this first. 212344779Sdim bool IsSimple = isSimple(); 213344779Sdim bool VTSIsSimple = VTS.isSimple(); 214344779Sdim if (IsSimple && VTSIsSimple) 215344779Sdim return *begin() == *VTS.begin(); 216205218Srdivacky 217344779Sdim // Speedup: We have a default if the set is simple. 218344779Sdim bool HaveDefault = IsSimple || hasDefault(); 219344779Sdim bool VTSHaveDefault = VTSIsSimple || VTS.hasDefault(); 220344779Sdim if (HaveDefault != VTSHaveDefault) 221327952Sdim return false; 222218893Sdim 223327952Sdim SmallDenseSet<unsigned, 4> Modes; 224327952Sdim for (auto &I : *this) 225327952Sdim Modes.insert(I.first); 226327952Sdim for (const auto &I : VTS) 227327952Sdim Modes.insert(I.first); 228218893Sdim 229327952Sdim if (HaveDefault) { 230327952Sdim // Both sets have default mode. 231327952Sdim for (unsigned M : Modes) { 232327952Sdim if (get(M) != VTS.get(M)) 233327952Sdim return false; 234327952Sdim } 235327952Sdim } else { 236327952Sdim // Neither set has default mode. 237327952Sdim for (unsigned M : Modes) { 238327952Sdim // If there is no default mode, an empty set is equivalent to not having 239327952Sdim // the corresponding mode. 240327952Sdim bool NoModeThis = !hasMode(M) || get(M).empty(); 241327952Sdim bool NoModeVTS = !VTS.hasMode(M) || VTS.get(M).empty(); 242327952Sdim if (NoModeThis != NoModeVTS) 243327952Sdim return false; 244327952Sdim if (!NoModeThis) 245327952Sdim if (get(M) != VTS.get(M)) 246327952Sdim return false; 247327952Sdim } 248205218Srdivacky } 249218893Sdim 250327952Sdim return true; 251198090Srdivacky} 252193323Sed 253327952Sdimnamespace llvm { 254327952Sdim raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T) { 255327952Sdim T.writeToStream(OS); 256327952Sdim return OS; 257205218Srdivacky } 258327952Sdim} 259218893Sdim 260327952SdimLLVM_DUMP_METHOD 261327952Sdimvoid TypeSetByHwMode::dump() const { 262327952Sdim dbgs() << *this << '\n'; 263327952Sdim} 264218893Sdim 265327952Sdimbool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) { 266327952Sdim bool OutP = Out.count(MVT::iPTR), InP = In.count(MVT::iPTR); 267327952Sdim auto Int = [&In](MVT T) -> bool { return !In.count(T); }; 268218893Sdim 269327952Sdim if (OutP == InP) 270327952Sdim return berase_if(Out, Int); 271218893Sdim 272327952Sdim // Compute the intersection of scalars separately to account for only 273327952Sdim // one set containing iPTR. 274327952Sdim // The itersection of iPTR with a set of integer scalar types that does not 275327952Sdim // include iPTR will result in the most specific scalar type: 276327952Sdim // - iPTR is more specific than any set with two elements or more 277327952Sdim // - iPTR is less specific than any single integer scalar type. 278327952Sdim // For example 279327952Sdim // { iPTR } * { i32 } -> { i32 } 280327952Sdim // { iPTR } * { i32 i64 } -> { iPTR } 281327952Sdim // and 282327952Sdim // { iPTR i32 } * { i32 } -> { i32 } 283327952Sdim // { iPTR i32 } * { i32 i64 } -> { i32 i64 } 284327952Sdim // { iPTR i32 } * { i32 i64 i128 } -> { iPTR i32 } 285327952Sdim 286327952Sdim // Compute the difference between the two sets in such a way that the 287327952Sdim // iPTR is in the set that is being subtracted. This is to see if there 288327952Sdim // are any extra scalars in the set without iPTR that are not in the 289327952Sdim // set containing iPTR. Then the iPTR could be considered a "wildcard" 290327952Sdim // matching these scalars. If there is only one such scalar, it would 291327952Sdim // replace the iPTR, if there are more, the iPTR would be retained. 292327952Sdim SetType Diff; 293327952Sdim if (InP) { 294327952Sdim Diff = Out; 295327952Sdim berase_if(Diff, [&In](MVT T) { return In.count(T); }); 296327952Sdim // Pre-remove these elements and rely only on InP/OutP to determine 297327952Sdim // whether a change has been made. 298327952Sdim berase_if(Out, [&Diff](MVT T) { return Diff.count(T); }); 299327952Sdim } else { 300327952Sdim Diff = In; 301327952Sdim berase_if(Diff, [&Out](MVT T) { return Out.count(T); }); 302327952Sdim Out.erase(MVT::iPTR); 303205218Srdivacky } 304218893Sdim 305327952Sdim // The actual intersection. 306327952Sdim bool Changed = berase_if(Out, Int); 307327952Sdim unsigned NumD = Diff.size(); 308327952Sdim if (NumD == 0) 309327952Sdim return Changed; 310218893Sdim 311327952Sdim if (NumD == 1) { 312327952Sdim Out.insert(*Diff.begin()); 313327952Sdim // This is a change only if Out was the one with iPTR (which is now 314327952Sdim // being replaced). 315327952Sdim Changed |= OutP; 316327952Sdim } else { 317327952Sdim // Multiple elements from Out are now replaced with iPTR. 318327952Sdim Out.insert(MVT::iPTR); 319327952Sdim Changed |= !OutP; 320205218Srdivacky } 321327952Sdim return Changed; 322327952Sdim} 323218893Sdim 324327952Sdimbool TypeSetByHwMode::validate() const { 325327952Sdim#ifndef NDEBUG 326327952Sdim if (empty()) 327327952Sdim return true; 328327952Sdim bool AllEmpty = true; 329327952Sdim for (const auto &I : *this) 330327952Sdim AllEmpty &= I.second.empty(); 331327952Sdim return !AllEmpty; 332327952Sdim#endif 333327952Sdim return true; 334327952Sdim} 335205218Srdivacky 336327952Sdim// --- TypeInfer 337218893Sdim 338327952Sdimbool TypeInfer::MergeInTypeInfo(TypeSetByHwMode &Out, 339327952Sdim const TypeSetByHwMode &In) { 340327952Sdim ValidateOnExit _1(Out, *this); 341327952Sdim In.validate(); 342327952Sdim if (In.empty() || Out == In || TP.hasError()) 343296417Sdim return false; 344327952Sdim if (Out.empty()) { 345327952Sdim Out = In; 346296417Sdim return true; 347327952Sdim } 348218893Sdim 349327952Sdim bool Changed = Out.constrain(In); 350327952Sdim if (Changed && Out.empty()) 351327952Sdim TP.error("Type contradiction"); 352327952Sdim 353327952Sdim return Changed; 354205218Srdivacky} 355205218Srdivacky 356327952Sdimbool TypeInfer::forceArbitrary(TypeSetByHwMode &Out) { 357327952Sdim ValidateOnExit _1(Out, *this); 358243830Sdim if (TP.hasError()) 359243830Sdim return false; 360327952Sdim assert(!Out.empty() && "cannot pick from an empty set"); 361296417Sdim 362327952Sdim bool Changed = false; 363327952Sdim for (auto &I : Out) { 364327952Sdim TypeSetByHwMode::SetType &S = I.second; 365327952Sdim if (S.size() <= 1) 366327952Sdim continue; 367327952Sdim MVT T = *S.begin(); // Pick the first element. 368327952Sdim S.clear(); 369327952Sdim S.insert(T); 370327952Sdim Changed = true; 371327952Sdim } 372327952Sdim return Changed; 373327952Sdim} 374327952Sdim 375327952Sdimbool TypeInfer::EnforceInteger(TypeSetByHwMode &Out) { 376327952Sdim ValidateOnExit _1(Out, *this); 377327952Sdim if (TP.hasError()) 378205407Srdivacky return false; 379327952Sdim if (!Out.empty()) 380327952Sdim return Out.constrain(isIntegerOrPtr); 381205407Srdivacky 382327952Sdim return Out.assign_if(getLegalTypes(), isIntegerOrPtr); 383327952Sdim} 384218893Sdim 385327952Sdimbool TypeInfer::EnforceFloatingPoint(TypeSetByHwMode &Out) { 386327952Sdim ValidateOnExit _1(Out, *this); 387327952Sdim if (TP.hasError()) 388327952Sdim return false; 389327952Sdim if (!Out.empty()) 390327952Sdim return Out.constrain(isFloatingPoint); 391218893Sdim 392327952Sdim return Out.assign_if(getLegalTypes(), isFloatingPoint); 393327952Sdim} 394327952Sdim 395327952Sdimbool TypeInfer::EnforceScalar(TypeSetByHwMode &Out) { 396327952Sdim ValidateOnExit _1(Out, *this); 397327952Sdim if (TP.hasError()) 398243830Sdim return false; 399327952Sdim if (!Out.empty()) 400327952Sdim return Out.constrain(isScalar); 401327952Sdim 402327952Sdim return Out.assign_if(getLegalTypes(), isScalar); 403205218Srdivacky} 404205218Srdivacky 405327952Sdimbool TypeInfer::EnforceVector(TypeSetByHwMode &Out) { 406327952Sdim ValidateOnExit _1(Out, *this); 407243830Sdim if (TP.hasError()) 408243830Sdim return false; 409327952Sdim if (!Out.empty()) 410327952Sdim return Out.constrain(isVector); 411205407Srdivacky 412327952Sdim return Out.assign_if(getLegalTypes(), isVector); 413327952Sdim} 414327952Sdim 415327952Sdimbool TypeInfer::EnforceAny(TypeSetByHwMode &Out) { 416327952Sdim ValidateOnExit _1(Out, *this); 417327952Sdim if (TP.hasError() || !Out.empty()) 418205407Srdivacky return false; 419205407Srdivacky 420327952Sdim Out = getLegalTypes(); 421327952Sdim return true; 422327952Sdim} 423218893Sdim 424327952Sdimtemplate <typename Iter, typename Pred, typename Less> 425327952Sdimstatic Iter min_if(Iter B, Iter E, Pred P, Less L) { 426327952Sdim if (B == E) 427327952Sdim return E; 428327952Sdim Iter Min = E; 429327952Sdim for (Iter I = B; I != E; ++I) { 430327952Sdim if (!P(*I)) 431327952Sdim continue; 432327952Sdim if (Min == E || L(*I, *Min)) 433327952Sdim Min = I; 434327952Sdim } 435327952Sdim return Min; 436327952Sdim} 437218893Sdim 438327952Sdimtemplate <typename Iter, typename Pred, typename Less> 439327952Sdimstatic Iter max_if(Iter B, Iter E, Pred P, Less L) { 440327952Sdim if (B == E) 441327952Sdim return E; 442327952Sdim Iter Max = E; 443327952Sdim for (Iter I = B; I != E; ++I) { 444327952Sdim if (!P(*I)) 445327952Sdim continue; 446327952Sdim if (Max == E || L(*Max, *I)) 447327952Sdim Max = I; 448243830Sdim } 449327952Sdim return Max; 450205218Srdivacky} 451205218Srdivacky 452327952Sdim/// Make sure that for each type in Small, there exists a larger type in Big. 453327952Sdimbool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small, 454327952Sdim TypeSetByHwMode &Big) { 455327952Sdim ValidateOnExit _1(Small, *this), _2(Big, *this); 456243830Sdim if (TP.hasError()) 457243830Sdim return false; 458327952Sdim bool Changed = false; 459243830Sdim 460327952Sdim if (Small.empty()) 461327952Sdim Changed |= EnforceAny(Small); 462327952Sdim if (Big.empty()) 463327952Sdim Changed |= EnforceAny(Big); 464205407Srdivacky 465327952Sdim assert(Small.hasDefault() && Big.hasDefault()); 466205407Srdivacky 467327952Sdim std::vector<unsigned> Modes = union_modes(Small, Big); 468218893Sdim 469327952Sdim // 1. Only allow integer or floating point types and make sure that 470327952Sdim // both sides are both integer or both floating point. 471327952Sdim // 2. Make sure that either both sides have vector types, or neither 472327952Sdim // of them does. 473327952Sdim for (unsigned M : Modes) { 474327952Sdim TypeSetByHwMode::SetType &S = Small.get(M); 475327952Sdim TypeSetByHwMode::SetType &B = Big.get(M); 476218893Sdim 477327952Sdim if (any_of(S, isIntegerOrPtr) && any_of(S, isIntegerOrPtr)) { 478327952Sdim auto NotInt = [](MVT VT) { return !isIntegerOrPtr(VT); }; 479327952Sdim Changed |= berase_if(S, NotInt) | 480327952Sdim berase_if(B, NotInt); 481327952Sdim } else if (any_of(S, isFloatingPoint) && any_of(B, isFloatingPoint)) { 482327952Sdim auto NotFP = [](MVT VT) { return !isFloatingPoint(VT); }; 483327952Sdim Changed |= berase_if(S, NotFP) | 484327952Sdim berase_if(B, NotFP); 485327952Sdim } else if (S.empty() || B.empty()) { 486327952Sdim Changed = !S.empty() || !B.empty(); 487327952Sdim S.clear(); 488327952Sdim B.clear(); 489327952Sdim } else { 490327952Sdim TP.error("Incompatible types"); 491327952Sdim return Changed; 492327952Sdim } 493327952Sdim 494327952Sdim if (none_of(S, isVector) || none_of(B, isVector)) { 495327952Sdim Changed |= berase_if(S, isVector) | 496327952Sdim berase_if(B, isVector); 497327952Sdim } 498243830Sdim } 499205218Srdivacky 500327952Sdim auto LT = [](MVT A, MVT B) -> bool { 501327952Sdim return A.getScalarSizeInBits() < B.getScalarSizeInBits() || 502327952Sdim (A.getScalarSizeInBits() == B.getScalarSizeInBits() && 503327952Sdim A.getSizeInBits() < B.getSizeInBits()); 504327952Sdim }; 505327952Sdim auto LE = [](MVT A, MVT B) -> bool { 506327952Sdim // This function is used when removing elements: when a vector is compared 507327952Sdim // to a non-vector, it should return false (to avoid removal). 508327952Sdim if (A.isVector() != B.isVector()) 509327952Sdim return false; 510243830Sdim 511327952Sdim // Note on the < comparison below: 512327952Sdim // X86 has patterns like 513327952Sdim // (set VR128X:$dst, (v16i8 (X86vtrunc (v4i32 VR128X:$src1)))), 514327952Sdim // where the truncated vector is given a type v16i8, while the source 515327952Sdim // vector has type v4i32. They both have the same size in bits. 516327952Sdim // The minimal type in the result is obviously v16i8, and when we remove 517327952Sdim // all types from the source that are smaller-or-equal than v8i16, the 518327952Sdim // only source type would also be removed (since it's equal in size). 519327952Sdim return A.getScalarSizeInBits() <= B.getScalarSizeInBits() || 520327952Sdim A.getSizeInBits() < B.getSizeInBits(); 521327952Sdim }; 522205407Srdivacky 523327952Sdim for (unsigned M : Modes) { 524327952Sdim TypeSetByHwMode::SetType &S = Small.get(M); 525327952Sdim TypeSetByHwMode::SetType &B = Big.get(M); 526327952Sdim // MinS = min scalar in Small, remove all scalars from Big that are 527327952Sdim // smaller-or-equal than MinS. 528327952Sdim auto MinS = min_if(S.begin(), S.end(), isScalar, LT); 529327952Sdim if (MinS != S.end()) 530327952Sdim Changed |= berase_if(B, std::bind(LE, std::placeholders::_1, *MinS)); 531218893Sdim 532327952Sdim // MaxS = max scalar in Big, remove all scalars from Small that are 533327952Sdim // larger than MaxS. 534327952Sdim auto MaxS = max_if(B.begin(), B.end(), isScalar, LT); 535327952Sdim if (MaxS != B.end()) 536327952Sdim Changed |= berase_if(S, std::bind(LE, *MaxS, std::placeholders::_1)); 537218893Sdim 538327952Sdim // MinV = min vector in Small, remove all vectors from Big that are 539327952Sdim // smaller-or-equal than MinV. 540327952Sdim auto MinV = min_if(S.begin(), S.end(), isVector, LT); 541327952Sdim if (MinV != S.end()) 542327952Sdim Changed |= berase_if(B, std::bind(LE, std::placeholders::_1, *MinV)); 543327952Sdim 544327952Sdim // MaxV = max vector in Big, remove all vectors from Small that are 545327952Sdim // larger than MaxV. 546327952Sdim auto MaxV = max_if(B.begin(), B.end(), isVector, LT); 547327952Sdim if (MaxV != B.end()) 548327952Sdim Changed |= berase_if(S, std::bind(LE, *MaxV, std::placeholders::_1)); 549243830Sdim } 550327952Sdim 551327952Sdim return Changed; 552205218Srdivacky} 553205218Srdivacky 554327952Sdim/// 1. Ensure that for each type T in Vec, T is a vector type, and that 555327952Sdim/// for each type U in Elem, U is a scalar type. 556327952Sdim/// 2. Ensure that for each (scalar) type U in Elem, there exists a (vector) 557327952Sdim/// type T in Vec, such that U is the element type of T. 558327952Sdimbool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, 559327952Sdim TypeSetByHwMode &Elem) { 560327952Sdim ValidateOnExit _1(Vec, *this), _2(Elem, *this); 561243830Sdim if (TP.hasError()) 562243830Sdim return false; 563327952Sdim bool Changed = false; 564243830Sdim 565327952Sdim if (Vec.empty()) 566327952Sdim Changed |= EnforceVector(Vec); 567327952Sdim if (Elem.empty()) 568327952Sdim Changed |= EnforceScalar(Elem); 569218893Sdim 570327952Sdim for (unsigned M : union_modes(Vec, Elem)) { 571327952Sdim TypeSetByHwMode::SetType &V = Vec.get(M); 572327952Sdim TypeSetByHwMode::SetType &E = Elem.get(M); 573205407Srdivacky 574327952Sdim Changed |= berase_if(V, isScalar); // Scalar = !vector 575327952Sdim Changed |= berase_if(E, isVector); // Vector = !scalar 576327952Sdim assert(!V.empty() && !E.empty()); 577218893Sdim 578327952Sdim SmallSet<MVT,4> VT, ST; 579327952Sdim // Collect element types from the "vector" set. 580327952Sdim for (MVT T : V) 581327952Sdim VT.insert(T.getVectorElementType()); 582327952Sdim // Collect scalar types from the "element" set. 583327952Sdim for (MVT T : E) 584327952Sdim ST.insert(T); 585218893Sdim 586327952Sdim // Remove from V all (vector) types whose element type is not in S. 587327952Sdim Changed |= berase_if(V, [&ST](MVT T) -> bool { 588327952Sdim return !ST.count(T.getVectorElementType()); 589327952Sdim }); 590327952Sdim // Remove from E all (scalar) types, for which there is no corresponding 591327952Sdim // type in V. 592327952Sdim Changed |= berase_if(E, [&VT](MVT T) -> bool { return !VT.count(T); }); 593327952Sdim } 594218893Sdim 595327952Sdim return Changed; 596327952Sdim} 597218893Sdim 598327952Sdimbool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, 599327952Sdim const ValueTypeByHwMode &VVT) { 600327952Sdim TypeSetByHwMode Tmp(VVT); 601327952Sdim ValidateOnExit _1(Vec, *this), _2(Tmp, *this); 602327952Sdim return EnforceVectorEltTypeIs(Vec, Tmp); 603327952Sdim} 604276479Sdim 605327952Sdim/// Ensure that for each type T in Sub, T is a vector type, and there 606327952Sdim/// exists a type U in Vec such that U is a vector type with the same 607327952Sdim/// element type as T and at least as many elements as T. 608327952Sdimbool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec, 609327952Sdim TypeSetByHwMode &Sub) { 610327952Sdim ValidateOnExit _1(Vec, *this), _2(Sub, *this); 611276479Sdim if (TP.hasError()) 612243830Sdim return false; 613218893Sdim 614327952Sdim /// Return true if B is a suB-vector of P, i.e. P is a suPer-vector of B. 615327952Sdim auto IsSubVec = [](MVT B, MVT P) -> bool { 616327952Sdim if (!B.isVector() || !P.isVector()) 617327952Sdim return false; 618327952Sdim // Logically a <4 x i32> is a valid subvector of <n x 4 x i32> 619327952Sdim // but until there are obvious use-cases for this, keep the 620327952Sdim // types separate. 621327952Sdim if (B.isScalableVector() != P.isScalableVector()) 622327952Sdim return false; 623327952Sdim if (B.getVectorElementType() != P.getVectorElementType()) 624327952Sdim return false; 625327952Sdim return B.getVectorNumElements() < P.getVectorNumElements(); 626327952Sdim }; 627296417Sdim 628327952Sdim /// Return true if S has no element (vector type) that T is a sub-vector of, 629327952Sdim /// i.e. has the same element type as T and more elements. 630327952Sdim auto NoSubV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool { 631327952Sdim for (const auto &I : S) 632327952Sdim if (IsSubVec(T, I)) 633314564Sdim return false; 634327952Sdim return true; 635327952Sdim }; 636296417Sdim 637327952Sdim /// Return true if S has no element (vector type) that T is a super-vector 638327952Sdim /// of, i.e. has the same element type as T and fewer elements. 639327952Sdim auto NoSupV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool { 640327952Sdim for (const auto &I : S) 641327952Sdim if (IsSubVec(I, T)) 642314564Sdim return false; 643327952Sdim return true; 644327952Sdim }; 645296417Sdim 646327952Sdim bool Changed = false; 647218893Sdim 648327952Sdim if (Vec.empty()) 649327952Sdim Changed |= EnforceVector(Vec); 650327952Sdim if (Sub.empty()) 651327952Sdim Changed |= EnforceVector(Sub); 652205218Srdivacky 653327952Sdim for (unsigned M : union_modes(Vec, Sub)) { 654327952Sdim TypeSetByHwMode::SetType &S = Sub.get(M); 655327952Sdim TypeSetByHwMode::SetType &V = Vec.get(M); 656288943Sdim 657327952Sdim Changed |= berase_if(S, isScalar); 658288943Sdim 659327952Sdim // Erase all types from S that are not sub-vectors of a type in V. 660327952Sdim Changed |= berase_if(S, std::bind(NoSubV, V, std::placeholders::_1)); 661288943Sdim 662327952Sdim // Erase all types from V that are not super-vectors of a type in S. 663327952Sdim Changed |= berase_if(V, std::bind(NoSupV, S, std::placeholders::_1)); 664288943Sdim } 665288943Sdim 666327952Sdim return Changed; 667288943Sdim} 668288943Sdim 669327952Sdim/// 1. Ensure that V has a scalar type iff W has a scalar type. 670327952Sdim/// 2. Ensure that for each vector type T in V, there exists a vector 671327952Sdim/// type U in W, such that T and U have the same number of elements. 672327952Sdim/// 3. Ensure that for each vector type U in W, there exists a vector 673327952Sdim/// type T in V, such that T and U have the same number of elements 674327952Sdim/// (reverse of 2). 675327952Sdimbool TypeInfer::EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W) { 676327952Sdim ValidateOnExit _1(V, *this), _2(W, *this); 677243830Sdim if (TP.hasError()) 678243830Sdim return false; 679243830Sdim 680327952Sdim bool Changed = false; 681327952Sdim if (V.empty()) 682327952Sdim Changed |= EnforceAny(V); 683327952Sdim if (W.empty()) 684327952Sdim Changed |= EnforceAny(W); 685206083Srdivacky 686327952Sdim // An actual vector type cannot have 0 elements, so we can treat scalars 687327952Sdim // as zero-length vectors. This way both vectors and scalars can be 688327952Sdim // processed identically. 689327952Sdim auto NoLength = [](const SmallSet<unsigned,2> &Lengths, MVT T) -> bool { 690327952Sdim return !Lengths.count(T.isVector() ? T.getVectorNumElements() : 0); 691327952Sdim }; 692206083Srdivacky 693327952Sdim for (unsigned M : union_modes(V, W)) { 694327952Sdim TypeSetByHwMode::SetType &VS = V.get(M); 695327952Sdim TypeSetByHwMode::SetType &WS = W.get(M); 696218893Sdim 697327952Sdim SmallSet<unsigned,2> VN, WN; 698327952Sdim for (MVT T : VS) 699327952Sdim VN.insert(T.isVector() ? T.getVectorNumElements() : 0); 700327952Sdim for (MVT T : WS) 701327952Sdim WN.insert(T.isVector() ? T.getVectorNumElements() : 0); 702218893Sdim 703327952Sdim Changed |= berase_if(VS, std::bind(NoLength, WN, std::placeholders::_1)); 704327952Sdim Changed |= berase_if(WS, std::bind(NoLength, VN, std::placeholders::_1)); 705327952Sdim } 706327952Sdim return Changed; 707205218Srdivacky} 708205218Srdivacky 709327952Sdim/// 1. Ensure that for each type T in A, there exists a type U in B, 710327952Sdim/// such that T and U have equal size in bits. 711327952Sdim/// 2. Ensure that for each type U in B, there exists a type T in A 712327952Sdim/// such that T and U have equal size in bits (reverse of 1). 713327952Sdimbool TypeInfer::EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B) { 714327952Sdim ValidateOnExit _1(A, *this), _2(B, *this); 715276479Sdim if (TP.hasError()) 716276479Sdim return false; 717327952Sdim bool Changed = false; 718327952Sdim if (A.empty()) 719327952Sdim Changed |= EnforceAny(A); 720327952Sdim if (B.empty()) 721327952Sdim Changed |= EnforceAny(B); 722276479Sdim 723327952Sdim auto NoSize = [](const SmallSet<unsigned,2> &Sizes, MVT T) -> bool { 724327952Sdim return !Sizes.count(T.getSizeInBits()); 725327952Sdim }; 726218893Sdim 727327952Sdim for (unsigned M : union_modes(A, B)) { 728327952Sdim TypeSetByHwMode::SetType &AS = A.get(M); 729327952Sdim TypeSetByHwMode::SetType &BS = B.get(M); 730327952Sdim SmallSet<unsigned,2> AN, BN; 731218893Sdim 732327952Sdim for (MVT T : AS) 733327952Sdim AN.insert(T.getSizeInBits()); 734327952Sdim for (MVT T : BS) 735327952Sdim BN.insert(T.getSizeInBits()); 736276479Sdim 737327952Sdim Changed |= berase_if(AS, std::bind(NoSize, BN, std::placeholders::_1)); 738327952Sdim Changed |= berase_if(BS, std::bind(NoSize, AN, std::placeholders::_1)); 739327952Sdim } 740218893Sdim 741327952Sdim return Changed; 742327952Sdim} 743276479Sdim 744327952Sdimvoid TypeInfer::expandOverloads(TypeSetByHwMode &VTS) { 745327952Sdim ValidateOnExit _1(VTS, *this); 746344779Sdim const TypeSetByHwMode &Legal = getLegalTypes(); 747344779Sdim assert(Legal.isDefaultOnly() && "Default-mode only expected"); 748344779Sdim const TypeSetByHwMode::SetType &LegalTypes = Legal.get(DefaultMode); 749276479Sdim 750344779Sdim for (auto &I : VTS) 751344779Sdim expandOverloads(I.second, LegalTypes); 752327952Sdim} 753218893Sdim 754327952Sdimvoid TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out, 755327952Sdim const TypeSetByHwMode::SetType &Legal) { 756327952Sdim std::set<MVT> Ovs; 757327952Sdim for (MVT T : Out) { 758327952Sdim if (!T.isOverloaded()) 759327952Sdim continue; 760276479Sdim 761327952Sdim Ovs.insert(T); 762327952Sdim // MachineValueTypeSet allows iteration and erasing. 763327952Sdim Out.erase(T); 764327952Sdim } 765276479Sdim 766327952Sdim for (MVT Ov : Ovs) { 767327952Sdim switch (Ov.SimpleTy) { 768327952Sdim case MVT::iPTRAny: 769327952Sdim Out.insert(MVT::iPTR); 770327952Sdim return; 771327952Sdim case MVT::iAny: 772327952Sdim for (MVT T : MVT::integer_valuetypes()) 773327952Sdim if (Legal.count(T)) 774327952Sdim Out.insert(T); 775327952Sdim for (MVT T : MVT::integer_vector_valuetypes()) 776327952Sdim if (Legal.count(T)) 777327952Sdim Out.insert(T); 778327952Sdim return; 779327952Sdim case MVT::fAny: 780327952Sdim for (MVT T : MVT::fp_valuetypes()) 781327952Sdim if (Legal.count(T)) 782327952Sdim Out.insert(T); 783327952Sdim for (MVT T : MVT::fp_vector_valuetypes()) 784327952Sdim if (Legal.count(T)) 785327952Sdim Out.insert(T); 786327952Sdim return; 787327952Sdim case MVT::vAny: 788327952Sdim for (MVT T : MVT::vector_valuetypes()) 789327952Sdim if (Legal.count(T)) 790327952Sdim Out.insert(T); 791327952Sdim return; 792327952Sdim case MVT::Any: 793327952Sdim for (MVT T : MVT::all_valuetypes()) 794327952Sdim if (Legal.count(T)) 795327952Sdim Out.insert(T); 796327952Sdim return; 797327952Sdim default: 798327952Sdim break; 799276479Sdim } 800218893Sdim } 801327952Sdim} 802218893Sdim 803344779Sdimconst TypeSetByHwMode &TypeInfer::getLegalTypes() { 804327952Sdim if (!LegalTypesCached) { 805344779Sdim TypeSetByHwMode::SetType &LegalTypes = LegalCache.getOrCreate(DefaultMode); 806327952Sdim // Stuff all types from all modes into the default mode. 807327952Sdim const TypeSetByHwMode <S = TP.getDAGPatterns().getLegalTypes(); 808327952Sdim for (const auto &I : LTS) 809344779Sdim LegalTypes.insert(I.second); 810327952Sdim LegalTypesCached = true; 811327952Sdim } 812344779Sdim assert(LegalCache.isDefaultOnly() && "Default-mode only expected"); 813344779Sdim return LegalCache; 814218893Sdim} 815218893Sdim 816327952Sdim#ifndef NDEBUG 817327952SdimTypeInfer::ValidateOnExit::~ValidateOnExit() { 818341825Sdim if (Infer.Validate && !VTS.validate()) { 819327952Sdim dbgs() << "Type set is empty for each HW mode:\n" 820327952Sdim "possible type contradiction in the pattern below " 821327952Sdim "(use -print-records with llvm-tblgen to see all " 822327952Sdim "expanded records).\n"; 823327952Sdim Infer.TP.dump(); 824327952Sdim llvm_unreachable(nullptr); 825327952Sdim } 826327952Sdim} 827327952Sdim#endif 828288943Sdim 829344779Sdim 830327952Sdim//===----------------------------------------------------------------------===// 831344779Sdim// ScopedName Implementation 832344779Sdim//===----------------------------------------------------------------------===// 833344779Sdim 834344779Sdimbool ScopedName::operator==(const ScopedName &o) const { 835344779Sdim return Scope == o.Scope && Identifier == o.Identifier; 836344779Sdim} 837344779Sdim 838344779Sdimbool ScopedName::operator!=(const ScopedName &o) const { 839344779Sdim return !(*this == o); 840344779Sdim} 841344779Sdim 842344779Sdim 843344779Sdim//===----------------------------------------------------------------------===// 844327952Sdim// TreePredicateFn Implementation 845327952Sdim//===----------------------------------------------------------------------===// 846288943Sdim 847327952Sdim/// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 848327952SdimTreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) { 849327952Sdim assert( 850327952Sdim (!hasPredCode() || !hasImmCode()) && 851327952Sdim ".td file corrupt: can't have a node predicate *and* an imm predicate"); 852327952Sdim} 853321369Sdim 854327952Sdimbool TreePredicateFn::hasPredCode() const { 855327952Sdim return isLoad() || isStore() || isAtomic() || 856327952Sdim !PatFragRec->getRecord()->getValueAsString("PredicateCode").empty(); 857327952Sdim} 858321369Sdim 859327952Sdimstd::string TreePredicateFn::getPredCode() const { 860327952Sdim std::string Code = ""; 861321369Sdim 862327952Sdim if (!isLoad() && !isStore() && !isAtomic()) { 863327952Sdim Record *MemoryVT = getMemoryVT(); 864288943Sdim 865327952Sdim if (MemoryVT) 866327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 867327952Sdim "MemoryVT requires IsLoad or IsStore"); 868327952Sdim } 869288943Sdim 870327952Sdim if (!isLoad() && !isStore()) { 871327952Sdim if (isUnindexed()) 872327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 873327952Sdim "IsUnindexed requires IsLoad or IsStore"); 874296417Sdim 875327952Sdim Record *ScalarMemoryVT = getScalarMemoryVT(); 876288943Sdim 877327952Sdim if (ScalarMemoryVT) 878327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 879327952Sdim "ScalarMemoryVT requires IsLoad or IsStore"); 880327952Sdim } 881288943Sdim 882327952Sdim if (isLoad() + isStore() + isAtomic() > 1) 883327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 884327952Sdim "IsLoad, IsStore, and IsAtomic are mutually exclusive"); 885296417Sdim 886327952Sdim if (isLoad()) { 887327952Sdim if (!isUnindexed() && !isNonExtLoad() && !isAnyExtLoad() && 888327952Sdim !isSignExtLoad() && !isZeroExtLoad() && getMemoryVT() == nullptr && 889327952Sdim getScalarMemoryVT() == nullptr) 890327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 891327952Sdim "IsLoad cannot be used by itself"); 892327952Sdim } else { 893327952Sdim if (isNonExtLoad()) 894327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 895327952Sdim "IsNonExtLoad requires IsLoad"); 896327952Sdim if (isAnyExtLoad()) 897327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 898327952Sdim "IsAnyExtLoad requires IsLoad"); 899327952Sdim if (isSignExtLoad()) 900327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 901327952Sdim "IsSignExtLoad requires IsLoad"); 902327952Sdim if (isZeroExtLoad()) 903327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 904327952Sdim "IsZeroExtLoad requires IsLoad"); 905288943Sdim } 906288943Sdim 907327952Sdim if (isStore()) { 908327952Sdim if (!isUnindexed() && !isTruncStore() && !isNonTruncStore() && 909327952Sdim getMemoryVT() == nullptr && getScalarMemoryVT() == nullptr) 910327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 911327952Sdim "IsStore cannot be used by itself"); 912327952Sdim } else { 913327952Sdim if (isNonTruncStore()) 914327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 915327952Sdim "IsNonTruncStore requires IsStore"); 916327952Sdim if (isTruncStore()) 917327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 918327952Sdim "IsTruncStore requires IsStore"); 919327952Sdim } 920288943Sdim 921327952Sdim if (isAtomic()) { 922327952Sdim if (getMemoryVT() == nullptr && !isAtomicOrderingMonotonic() && 923327952Sdim !isAtomicOrderingAcquire() && !isAtomicOrderingRelease() && 924327952Sdim !isAtomicOrderingAcquireRelease() && 925327952Sdim !isAtomicOrderingSequentiallyConsistent() && 926327952Sdim !isAtomicOrderingAcquireOrStronger() && 927327952Sdim !isAtomicOrderingReleaseOrStronger() && 928327952Sdim !isAtomicOrderingWeakerThanAcquire() && 929327952Sdim !isAtomicOrderingWeakerThanRelease()) 930327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 931327952Sdim "IsAtomic cannot be used by itself"); 932327952Sdim } else { 933327952Sdim if (isAtomicOrderingMonotonic()) 934327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 935327952Sdim "IsAtomicOrderingMonotonic requires IsAtomic"); 936327952Sdim if (isAtomicOrderingAcquire()) 937327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 938327952Sdim "IsAtomicOrderingAcquire requires IsAtomic"); 939327952Sdim if (isAtomicOrderingRelease()) 940327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 941327952Sdim "IsAtomicOrderingRelease requires IsAtomic"); 942327952Sdim if (isAtomicOrderingAcquireRelease()) 943327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 944327952Sdim "IsAtomicOrderingAcquireRelease requires IsAtomic"); 945327952Sdim if (isAtomicOrderingSequentiallyConsistent()) 946327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 947327952Sdim "IsAtomicOrderingSequentiallyConsistent requires IsAtomic"); 948327952Sdim if (isAtomicOrderingAcquireOrStronger()) 949327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 950327952Sdim "IsAtomicOrderingAcquireOrStronger requires IsAtomic"); 951327952Sdim if (isAtomicOrderingReleaseOrStronger()) 952327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 953327952Sdim "IsAtomicOrderingReleaseOrStronger requires IsAtomic"); 954327952Sdim if (isAtomicOrderingWeakerThanAcquire()) 955327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 956327952Sdim "IsAtomicOrderingWeakerThanAcquire requires IsAtomic"); 957327952Sdim } 958296417Sdim 959327952Sdim if (isLoad() || isStore() || isAtomic()) { 960327952Sdim StringRef SDNodeName = 961327952Sdim isLoad() ? "LoadSDNode" : isStore() ? "StoreSDNode" : "AtomicSDNode"; 962296417Sdim 963327952Sdim Record *MemoryVT = getMemoryVT(); 964321369Sdim 965327952Sdim if (MemoryVT) 966327952Sdim Code += ("if (cast<" + SDNodeName + ">(N)->getMemoryVT() != MVT::" + 967327952Sdim MemoryVT->getName() + ") return false;\n") 968327952Sdim .str(); 969327952Sdim } 970321369Sdim 971327952Sdim if (isAtomic() && isAtomicOrderingMonotonic()) 972327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 973327952Sdim "AtomicOrdering::Monotonic) return false;\n"; 974327952Sdim if (isAtomic() && isAtomicOrderingAcquire()) 975327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 976327952Sdim "AtomicOrdering::Acquire) return false;\n"; 977327952Sdim if (isAtomic() && isAtomicOrderingRelease()) 978327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 979327952Sdim "AtomicOrdering::Release) return false;\n"; 980327952Sdim if (isAtomic() && isAtomicOrderingAcquireRelease()) 981327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 982327952Sdim "AtomicOrdering::AcquireRelease) return false;\n"; 983327952Sdim if (isAtomic() && isAtomicOrderingSequentiallyConsistent()) 984327952Sdim Code += "if (cast<AtomicSDNode>(N)->getOrdering() != " 985327952Sdim "AtomicOrdering::SequentiallyConsistent) return false;\n"; 986296417Sdim 987327952Sdim if (isAtomic() && isAtomicOrderingAcquireOrStronger()) 988327952Sdim Code += "if (!isAcquireOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 989327952Sdim "return false;\n"; 990327952Sdim if (isAtomic() && isAtomicOrderingWeakerThanAcquire()) 991327952Sdim Code += "if (isAcquireOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 992327952Sdim "return false;\n"; 993296417Sdim 994327952Sdim if (isAtomic() && isAtomicOrderingReleaseOrStronger()) 995327952Sdim Code += "if (!isReleaseOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 996327952Sdim "return false;\n"; 997327952Sdim if (isAtomic() && isAtomicOrderingWeakerThanRelease()) 998327952Sdim Code += "if (isReleaseOrStronger(cast<AtomicSDNode>(N)->getOrdering())) " 999327952Sdim "return false;\n"; 1000296417Sdim 1001327952Sdim if (isLoad() || isStore()) { 1002327952Sdim StringRef SDNodeName = isLoad() ? "LoadSDNode" : "StoreSDNode"; 1003327952Sdim 1004327952Sdim if (isUnindexed()) 1005327952Sdim Code += ("if (cast<" + SDNodeName + 1006327952Sdim ">(N)->getAddressingMode() != ISD::UNINDEXED) " 1007327952Sdim "return false;\n") 1008327952Sdim .str(); 1009327952Sdim 1010327952Sdim if (isLoad()) { 1011327952Sdim if ((isNonExtLoad() + isAnyExtLoad() + isSignExtLoad() + 1012327952Sdim isZeroExtLoad()) > 1) 1013327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1014327952Sdim "IsNonExtLoad, IsAnyExtLoad, IsSignExtLoad, and " 1015327952Sdim "IsZeroExtLoad are mutually exclusive"); 1016327952Sdim if (isNonExtLoad()) 1017327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != " 1018327952Sdim "ISD::NON_EXTLOAD) return false;\n"; 1019327952Sdim if (isAnyExtLoad()) 1020327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::EXTLOAD) " 1021327952Sdim "return false;\n"; 1022327952Sdim if (isSignExtLoad()) 1023327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::SEXTLOAD) " 1024327952Sdim "return false;\n"; 1025327952Sdim if (isZeroExtLoad()) 1026327952Sdim Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::ZEXTLOAD) " 1027327952Sdim "return false;\n"; 1028327952Sdim } else { 1029327952Sdim if ((isNonTruncStore() + isTruncStore()) > 1) 1030327952Sdim PrintFatalError( 1031327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1032327952Sdim "IsNonTruncStore, and IsTruncStore are mutually exclusive"); 1033327952Sdim if (isNonTruncStore()) 1034327952Sdim Code += 1035327952Sdim " if (cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n"; 1036327952Sdim if (isTruncStore()) 1037327952Sdim Code += 1038327952Sdim " if (!cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n"; 1039296417Sdim } 1040296417Sdim 1041327952Sdim Record *ScalarMemoryVT = getScalarMemoryVT(); 1042296417Sdim 1043327952Sdim if (ScalarMemoryVT) 1044327952Sdim Code += ("if (cast<" + SDNodeName + 1045327952Sdim ">(N)->getMemoryVT().getScalarType() != MVT::" + 1046327952Sdim ScalarMemoryVT->getName() + ") return false;\n") 1047327952Sdim .str(); 1048296417Sdim } 1049296417Sdim 1050327952Sdim std::string PredicateCode = PatFragRec->getRecord()->getValueAsString("PredicateCode"); 1051296417Sdim 1052327952Sdim Code += PredicateCode; 1053205218Srdivacky 1054327952Sdim if (PredicateCode.empty() && !Code.empty()) 1055327952Sdim Code += "return true;\n"; 1056193323Sed 1057327952Sdim return Code; 1058193323Sed} 1059327952Sdim 1060327952Sdimbool TreePredicateFn::hasImmCode() const { 1061327952Sdim return !PatFragRec->getRecord()->getValueAsString("ImmediateCode").empty(); 1062193323Sed} 1063193323Sed 1064327952Sdimstd::string TreePredicateFn::getImmCode() const { 1065327952Sdim return PatFragRec->getRecord()->getValueAsString("ImmediateCode"); 1066193323Sed} 1067218893Sdim 1068327952Sdimbool TreePredicateFn::immCodeUsesAPInt() const { 1069327952Sdim return getOrigPatFragRecord()->getRecord()->getValueAsBit("IsAPInt"); 1070327952Sdim} 1071221345Sdim 1072327952Sdimbool TreePredicateFn::immCodeUsesAPFloat() const { 1073327952Sdim bool Unset; 1074327952Sdim // The return value will be false when IsAPFloat is unset. 1075327952Sdim return getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset("IsAPFloat", 1076327952Sdim Unset); 1077327952Sdim} 1078221345Sdim 1079327952Sdimbool TreePredicateFn::isPredefinedPredicateEqualTo(StringRef Field, 1080327952Sdim bool Value) const { 1081327952Sdim bool Unset; 1082327952Sdim bool Result = 1083327952Sdim getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset(Field, Unset); 1084327952Sdim if (Unset) 1085327952Sdim return false; 1086327952Sdim return Result == Value; 1087193323Sed} 1088344779Sdimbool TreePredicateFn::usesOperands() const { 1089344779Sdim return isPredefinedPredicateEqualTo("PredicateCodeUsesOperands", true); 1090344779Sdim} 1091327952Sdimbool TreePredicateFn::isLoad() const { 1092327952Sdim return isPredefinedPredicateEqualTo("IsLoad", true); 1093327952Sdim} 1094327952Sdimbool TreePredicateFn::isStore() const { 1095327952Sdim return isPredefinedPredicateEqualTo("IsStore", true); 1096327952Sdim} 1097327952Sdimbool TreePredicateFn::isAtomic() const { 1098327952Sdim return isPredefinedPredicateEqualTo("IsAtomic", true); 1099327952Sdim} 1100327952Sdimbool TreePredicateFn::isUnindexed() const { 1101327952Sdim return isPredefinedPredicateEqualTo("IsUnindexed", true); 1102327952Sdim} 1103327952Sdimbool TreePredicateFn::isNonExtLoad() const { 1104327952Sdim return isPredefinedPredicateEqualTo("IsNonExtLoad", true); 1105327952Sdim} 1106327952Sdimbool TreePredicateFn::isAnyExtLoad() const { 1107327952Sdim return isPredefinedPredicateEqualTo("IsAnyExtLoad", true); 1108327952Sdim} 1109327952Sdimbool TreePredicateFn::isSignExtLoad() const { 1110327952Sdim return isPredefinedPredicateEqualTo("IsSignExtLoad", true); 1111327952Sdim} 1112327952Sdimbool TreePredicateFn::isZeroExtLoad() const { 1113327952Sdim return isPredefinedPredicateEqualTo("IsZeroExtLoad", true); 1114327952Sdim} 1115327952Sdimbool TreePredicateFn::isNonTruncStore() const { 1116327952Sdim return isPredefinedPredicateEqualTo("IsTruncStore", false); 1117327952Sdim} 1118327952Sdimbool TreePredicateFn::isTruncStore() const { 1119327952Sdim return isPredefinedPredicateEqualTo("IsTruncStore", true); 1120327952Sdim} 1121327952Sdimbool TreePredicateFn::isAtomicOrderingMonotonic() const { 1122327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingMonotonic", true); 1123327952Sdim} 1124327952Sdimbool TreePredicateFn::isAtomicOrderingAcquire() const { 1125327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquire", true); 1126327952Sdim} 1127327952Sdimbool TreePredicateFn::isAtomicOrderingRelease() const { 1128327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingRelease", true); 1129327952Sdim} 1130327952Sdimbool TreePredicateFn::isAtomicOrderingAcquireRelease() const { 1131327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireRelease", true); 1132327952Sdim} 1133327952Sdimbool TreePredicateFn::isAtomicOrderingSequentiallyConsistent() const { 1134327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingSequentiallyConsistent", 1135327952Sdim true); 1136327952Sdim} 1137327952Sdimbool TreePredicateFn::isAtomicOrderingAcquireOrStronger() const { 1138327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger", true); 1139327952Sdim} 1140327952Sdimbool TreePredicateFn::isAtomicOrderingWeakerThanAcquire() const { 1141327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger", false); 1142327952Sdim} 1143327952Sdimbool TreePredicateFn::isAtomicOrderingReleaseOrStronger() const { 1144327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger", true); 1145327952Sdim} 1146327952Sdimbool TreePredicateFn::isAtomicOrderingWeakerThanRelease() const { 1147327952Sdim return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger", false); 1148327952Sdim} 1149327952SdimRecord *TreePredicateFn::getMemoryVT() const { 1150327952Sdim Record *R = getOrigPatFragRecord()->getRecord(); 1151327952Sdim if (R->isValueUnset("MemoryVT")) 1152327952Sdim return nullptr; 1153327952Sdim return R->getValueAsDef("MemoryVT"); 1154327952Sdim} 1155327952SdimRecord *TreePredicateFn::getScalarMemoryVT() const { 1156327952Sdim Record *R = getOrigPatFragRecord()->getRecord(); 1157327952Sdim if (R->isValueUnset("ScalarMemoryVT")) 1158327952Sdim return nullptr; 1159327952Sdim return R->getValueAsDef("ScalarMemoryVT"); 1160327952Sdim} 1161341825Sdimbool TreePredicateFn::hasGISelPredicateCode() const { 1162341825Sdim return !PatFragRec->getRecord() 1163341825Sdim ->getValueAsString("GISelPredicateCode") 1164341825Sdim .empty(); 1165341825Sdim} 1166341825Sdimstd::string TreePredicateFn::getGISelPredicateCode() const { 1167341825Sdim return PatFragRec->getRecord()->getValueAsString("GISelPredicateCode"); 1168341825Sdim} 1169193323Sed 1170327952SdimStringRef TreePredicateFn::getImmType() const { 1171327952Sdim if (immCodeUsesAPInt()) 1172327952Sdim return "const APInt &"; 1173327952Sdim if (immCodeUsesAPFloat()) 1174327952Sdim return "const APFloat &"; 1175327952Sdim return "int64_t"; 1176221345Sdim} 1177221345Sdim 1178327952SdimStringRef TreePredicateFn::getImmTypeIdentifier() const { 1179327952Sdim if (immCodeUsesAPInt()) 1180327952Sdim return "APInt"; 1181327952Sdim else if (immCodeUsesAPFloat()) 1182327952Sdim return "APFloat"; 1183327952Sdim return "I64"; 1184221345Sdim} 1185221345Sdim 1186221345Sdim/// isAlwaysTrue - Return true if this is a noop predicate. 1187221345Sdimbool TreePredicateFn::isAlwaysTrue() const { 1188327952Sdim return !hasPredCode() && !hasImmCode(); 1189221345Sdim} 1190221345Sdim 1191221345Sdim/// Return the name to use in the generated code to reference this, this is 1192221345Sdim/// "Predicate_foo" if from a pattern fragment "foo". 1193221345Sdimstd::string TreePredicateFn::getFnName() const { 1194314564Sdim return "Predicate_" + PatFragRec->getRecord()->getName().str(); 1195221345Sdim} 1196221345Sdim 1197221345Sdim/// getCodeToRunOnSDNode - Return the code for the function body that 1198221345Sdim/// evaluates this predicate. The argument is expected to be in "Node", 1199221345Sdim/// not N. This handles casting and conversion to a concrete node type as 1200221345Sdim/// appropriate. 1201221345Sdimstd::string TreePredicateFn::getCodeToRunOnSDNode() const { 1202221345Sdim // Handle immediate predicates first. 1203221345Sdim std::string ImmCode = getImmCode(); 1204221345Sdim if (!ImmCode.empty()) { 1205327952Sdim if (isLoad()) 1206327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1207327952Sdim "IsLoad cannot be used with ImmLeaf or its subclasses"); 1208327952Sdim if (isStore()) 1209327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1210327952Sdim "IsStore cannot be used with ImmLeaf or its subclasses"); 1211327952Sdim if (isUnindexed()) 1212327952Sdim PrintFatalError( 1213327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1214327952Sdim "IsUnindexed cannot be used with ImmLeaf or its subclasses"); 1215327952Sdim if (isNonExtLoad()) 1216327952Sdim PrintFatalError( 1217327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1218327952Sdim "IsNonExtLoad cannot be used with ImmLeaf or its subclasses"); 1219327952Sdim if (isAnyExtLoad()) 1220327952Sdim PrintFatalError( 1221327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1222327952Sdim "IsAnyExtLoad cannot be used with ImmLeaf or its subclasses"); 1223327952Sdim if (isSignExtLoad()) 1224327952Sdim PrintFatalError( 1225327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1226327952Sdim "IsSignExtLoad cannot be used with ImmLeaf or its subclasses"); 1227327952Sdim if (isZeroExtLoad()) 1228327952Sdim PrintFatalError( 1229327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1230327952Sdim "IsZeroExtLoad cannot be used with ImmLeaf or its subclasses"); 1231327952Sdim if (isNonTruncStore()) 1232327952Sdim PrintFatalError( 1233327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1234327952Sdim "IsNonTruncStore cannot be used with ImmLeaf or its subclasses"); 1235327952Sdim if (isTruncStore()) 1236327952Sdim PrintFatalError( 1237327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1238327952Sdim "IsTruncStore cannot be used with ImmLeaf or its subclasses"); 1239327952Sdim if (getMemoryVT()) 1240327952Sdim PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(), 1241327952Sdim "MemoryVT cannot be used with ImmLeaf or its subclasses"); 1242327952Sdim if (getScalarMemoryVT()) 1243327952Sdim PrintFatalError( 1244327952Sdim getOrigPatFragRecord()->getRecord()->getLoc(), 1245327952Sdim "ScalarMemoryVT cannot be used with ImmLeaf or its subclasses"); 1246327952Sdim 1247327952Sdim std::string Result = (" " + getImmType() + " Imm = ").str(); 1248327952Sdim if (immCodeUsesAPFloat()) 1249327952Sdim Result += "cast<ConstantFPSDNode>(Node)->getValueAPF();\n"; 1250327952Sdim else if (immCodeUsesAPInt()) 1251327952Sdim Result += "cast<ConstantSDNode>(Node)->getAPIntValue();\n"; 1252327952Sdim else 1253327952Sdim Result += "cast<ConstantSDNode>(Node)->getSExtValue();\n"; 1254221345Sdim return Result + ImmCode; 1255221345Sdim } 1256327952Sdim 1257221345Sdim // Handle arbitrary node predicates. 1258327952Sdim assert(hasPredCode() && "Don't have any predicate code!"); 1259327952Sdim StringRef ClassName; 1260221345Sdim if (PatFragRec->getOnlyTree()->isLeaf()) 1261221345Sdim ClassName = "SDNode"; 1262221345Sdim else { 1263221345Sdim Record *Op = PatFragRec->getOnlyTree()->getOperator(); 1264221345Sdim ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName(); 1265221345Sdim } 1266221345Sdim std::string Result; 1267221345Sdim if (ClassName == "SDNode") 1268221345Sdim Result = " SDNode *N = Node;\n"; 1269221345Sdim else 1270327952Sdim Result = " auto *N = cast<" + ClassName.str() + ">(Node);\n"; 1271327952Sdim 1272344779Sdim return (Twine(Result) + " (void)N;\n" + getPredCode()).str(); 1273221345Sdim} 1274221345Sdim 1275193323Sed//===----------------------------------------------------------------------===// 1276193323Sed// PatternToMatch implementation 1277193323Sed// 1278193323Sed 1279206083Srdivacky/// getPatternSize - Return the 'size' of this pattern. We want to match large 1280206083Srdivacky/// patterns before small ones. This is used to determine the size of a 1281206083Srdivacky/// pattern. 1282206083Srdivackystatic unsigned getPatternSize(const TreePatternNode *P, 1283206083Srdivacky const CodeGenDAGPatterns &CGP) { 1284206083Srdivacky unsigned Size = 3; // The node itself. 1285206083Srdivacky // If the root node is a ConstantSDNode, increases its size. 1286206083Srdivacky // e.g. (set R32:$dst, 0). 1287243830Sdim if (P->isLeaf() && isa<IntInit>(P->getLeafValue())) 1288206083Srdivacky Size += 2; 1289218893Sdim 1290327952Sdim if (const ComplexPattern *AM = P->getComplexPatternInfo(CGP)) { 1291314564Sdim Size += AM->getComplexity(); 1292276479Sdim // We don't want to count any children twice, so return early. 1293276479Sdim return Size; 1294276479Sdim } 1295276479Sdim 1296206083Srdivacky // If this node has some predicate function that must match, it adds to the 1297206083Srdivacky // complexity of this node. 1298344779Sdim if (!P->getPredicateCalls().empty()) 1299206083Srdivacky ++Size; 1300218893Sdim 1301206083Srdivacky // Count children in the count if they are also nodes. 1302206083Srdivacky for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { 1303327952Sdim const TreePatternNode *Child = P->getChild(i); 1304327952Sdim if (!Child->isLeaf() && Child->getNumTypes()) { 1305344779Sdim const TypeSetByHwMode &T0 = Child->getExtType(0); 1306327952Sdim // At this point, all variable type sets should be simple, i.e. only 1307327952Sdim // have a default mode. 1308327952Sdim if (T0.getMachineValueType() != MVT::Other) { 1309327952Sdim Size += getPatternSize(Child, CGP); 1310327952Sdim continue; 1311327952Sdim } 1312327952Sdim } 1313327952Sdim if (Child->isLeaf()) { 1314243830Sdim if (isa<IntInit>(Child->getLeafValue())) 1315206083Srdivacky Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). 1316206083Srdivacky else if (Child->getComplexPatternInfo(CGP)) 1317206083Srdivacky Size += getPatternSize(Child, CGP); 1318344779Sdim else if (!Child->getPredicateCalls().empty()) 1319206083Srdivacky ++Size; 1320206083Srdivacky } 1321206083Srdivacky } 1322218893Sdim 1323206083Srdivacky return Size; 1324206083Srdivacky} 1325206083Srdivacky 1326206083Srdivacky/// Compute the complexity metric for the input pattern. This roughly 1327206083Srdivacky/// corresponds to the number of nodes that are covered. 1328280031Sdimint PatternToMatch:: 1329206083SrdivackygetPatternComplexity(const CodeGenDAGPatterns &CGP) const { 1330206083Srdivacky return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity(); 1331206083Srdivacky} 1332206083Srdivacky 1333193323Sed/// getPredicateCheck - Return a single string containing all of this 1334193323Sed/// pattern's predicates concatenated with "&&" operators. 1335193323Sed/// 1336193323Sedstd::string PatternToMatch::getPredicateCheck() const { 1337327952Sdim SmallVector<const Predicate*,4> PredList; 1338327952Sdim for (const Predicate &P : Predicates) 1339327952Sdim PredList.push_back(&P); 1340344779Sdim llvm::sort(PredList, deref<llvm::less>()); 1341193323Sed 1342327952Sdim std::string Check; 1343327952Sdim for (unsigned i = 0, e = PredList.size(); i != e; ++i) { 1344327952Sdim if (i != 0) 1345327952Sdim Check += " && "; 1346327952Sdim Check += '(' + PredList[i]->getCondString() + ')'; 1347296417Sdim } 1348327952Sdim return Check; 1349193323Sed} 1350193323Sed 1351193323Sed//===----------------------------------------------------------------------===// 1352193323Sed// SDTypeConstraint implementation 1353193323Sed// 1354193323Sed 1355327952SdimSDTypeConstraint::SDTypeConstraint(Record *R, const CodeGenHwModes &CGH) { 1356193323Sed OperandNo = R->getValueAsInt("OperandNum"); 1357218893Sdim 1358193323Sed if (R->isSubClassOf("SDTCisVT")) { 1359193323Sed ConstraintType = SDTCisVT; 1360327952Sdim VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH); 1361327952Sdim for (const auto &P : VVT) 1362327952Sdim if (P.second == MVT::isVoid) 1363327952Sdim PrintFatalError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT"); 1364193323Sed } else if (R->isSubClassOf("SDTCisPtrTy")) { 1365193323Sed ConstraintType = SDTCisPtrTy; 1366193323Sed } else if (R->isSubClassOf("SDTCisInt")) { 1367193323Sed ConstraintType = SDTCisInt; 1368193323Sed } else if (R->isSubClassOf("SDTCisFP")) { 1369193323Sed ConstraintType = SDTCisFP; 1370198090Srdivacky } else if (R->isSubClassOf("SDTCisVec")) { 1371198090Srdivacky ConstraintType = SDTCisVec; 1372193323Sed } else if (R->isSubClassOf("SDTCisSameAs")) { 1373193323Sed ConstraintType = SDTCisSameAs; 1374193323Sed x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 1375193323Sed } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 1376193323Sed ConstraintType = SDTCisVTSmallerThanOp; 1377218893Sdim x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 1378193323Sed R->getValueAsInt("OtherOperandNum"); 1379193323Sed } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 1380193323Sed ConstraintType = SDTCisOpSmallerThanOp; 1381218893Sdim x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 1382193323Sed R->getValueAsInt("BigOperandNum"); 1383193323Sed } else if (R->isSubClassOf("SDTCisEltOfVec")) { 1384193323Sed ConstraintType = SDTCisEltOfVec; 1385205218Srdivacky x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); 1386218893Sdim } else if (R->isSubClassOf("SDTCisSubVecOfVec")) { 1387218893Sdim ConstraintType = SDTCisSubVecOfVec; 1388218893Sdim x.SDTCisSubVecOfVec_Info.OtherOperandNum = 1389218893Sdim R->getValueAsInt("OtherOpNum"); 1390288943Sdim } else if (R->isSubClassOf("SDTCVecEltisVT")) { 1391288943Sdim ConstraintType = SDTCVecEltisVT; 1392327952Sdim VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH); 1393327952Sdim for (const auto &P : VVT) { 1394327952Sdim MVT T = P.second; 1395327952Sdim if (T.isVector()) 1396327952Sdim PrintFatalError(R->getLoc(), 1397327952Sdim "Cannot use vector type as SDTCVecEltisVT"); 1398327952Sdim if (!T.isInteger() && !T.isFloatingPoint()) 1399327952Sdim PrintFatalError(R->getLoc(), "Must use integer or floating point type " 1400327952Sdim "as SDTCVecEltisVT"); 1401327952Sdim } 1402288943Sdim } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) { 1403288943Sdim ConstraintType = SDTCisSameNumEltsAs; 1404288943Sdim x.SDTCisSameNumEltsAs_Info.OtherOperandNum = 1405288943Sdim R->getValueAsInt("OtherOperandNum"); 1406296417Sdim } else if (R->isSubClassOf("SDTCisSameSizeAs")) { 1407296417Sdim ConstraintType = SDTCisSameSizeAs; 1408296417Sdim x.SDTCisSameSizeAs_Info.OtherOperandNum = 1409296417Sdim R->getValueAsInt("OtherOperandNum"); 1410193323Sed } else { 1411288943Sdim PrintFatalError("Unrecognized SDTypeConstraint '" + R->getName() + "'!\n"); 1412193323Sed } 1413193323Sed} 1414193323Sed 1415193323Sed/// getOperandNum - Return the node corresponding to operand #OpNo in tree 1416205407Srdivacky/// N, and the result number in ResNo. 1417205407Srdivackystatic TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, 1418205407Srdivacky const SDNodeInfo &NodeInfo, 1419205407Srdivacky unsigned &ResNo) { 1420205407Srdivacky unsigned NumResults = NodeInfo.getNumResults(); 1421205407Srdivacky if (OpNo < NumResults) { 1422205407Srdivacky ResNo = OpNo; 1423205407Srdivacky return N; 1424205407Srdivacky } 1425218893Sdim 1426205407Srdivacky OpNo -= NumResults; 1427218893Sdim 1428205407Srdivacky if (OpNo >= N->getNumChildren()) { 1429288943Sdim std::string S; 1430288943Sdim raw_string_ostream OS(S); 1431288943Sdim OS << "Invalid operand number in type constraint " 1432205407Srdivacky << (OpNo+NumResults) << " "; 1433288943Sdim N->print(OS); 1434288943Sdim PrintFatalError(OS.str()); 1435193323Sed } 1436193323Sed 1437205407Srdivacky return N->getChild(OpNo); 1438193323Sed} 1439193323Sed 1440193323Sed/// ApplyTypeConstraint - Given a node in a pattern, apply this type 1441193323Sed/// constraint to the nodes operands. This returns true if it makes a 1442243830Sdim/// change, false otherwise. If a type contradiction is found, flag an error. 1443193323Sedbool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 1444193323Sed const SDNodeInfo &NodeInfo, 1445193323Sed TreePattern &TP) const { 1446243830Sdim if (TP.hasError()) 1447243830Sdim return false; 1448243830Sdim 1449205407Srdivacky unsigned ResNo = 0; // The result number being referenced. 1450205407Srdivacky TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo); 1451327952Sdim TypeInfer &TI = TP.getInfer(); 1452218893Sdim 1453193323Sed switch (ConstraintType) { 1454193323Sed case SDTCisVT: 1455193323Sed // Operand must be a particular type. 1456327952Sdim return NodeToApply->UpdateNodeType(ResNo, VVT, TP); 1457205218Srdivacky case SDTCisPtrTy: 1458193323Sed // Operand must be same as target pointer type. 1459205407Srdivacky return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP); 1460205218Srdivacky case SDTCisInt: 1461205218Srdivacky // Require it to be one of the legal integer VTs. 1462327952Sdim return TI.EnforceInteger(NodeToApply->getExtType(ResNo)); 1463205218Srdivacky case SDTCisFP: 1464205218Srdivacky // Require it to be one of the legal fp VTs. 1465327952Sdim return TI.EnforceFloatingPoint(NodeToApply->getExtType(ResNo)); 1466205218Srdivacky case SDTCisVec: 1467205218Srdivacky // Require it to be one of the legal vector VTs. 1468327952Sdim return TI.EnforceVector(NodeToApply->getExtType(ResNo)); 1469193323Sed case SDTCisSameAs: { 1470205407Srdivacky unsigned OResNo = 0; 1471193323Sed TreePatternNode *OtherNode = 1472205407Srdivacky getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); 1473288943Sdim return NodeToApply->UpdateNodeType(ResNo, OtherNode->getExtType(OResNo),TP)| 1474288943Sdim OtherNode->UpdateNodeType(OResNo,NodeToApply->getExtType(ResNo),TP); 1475193323Sed } 1476193323Sed case SDTCisVTSmallerThanOp: { 1477193323Sed // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 1478193323Sed // have an integer type that is smaller than the VT. 1479193323Sed if (!NodeToApply->isLeaf() || 1480243830Sdim !isa<DefInit>(NodeToApply->getLeafValue()) || 1481193323Sed !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 1482243830Sdim ->isSubClassOf("ValueType")) { 1483193323Sed TP.error(N->getOperator()->getName() + " expects a VT operand!"); 1484243830Sdim return false; 1485243830Sdim } 1486327952Sdim DefInit *DI = static_cast<DefInit*>(NodeToApply->getLeafValue()); 1487327952Sdim const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1488327952Sdim auto VVT = getValueTypeByHwMode(DI->getDef(), T.getHwModes()); 1489327952Sdim TypeSetByHwMode TypeListTmp(VVT); 1490218893Sdim 1491205407Srdivacky unsigned OResNo = 0; 1492193323Sed TreePatternNode *OtherNode = 1493205407Srdivacky getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo, 1494205407Srdivacky OResNo); 1495205218Srdivacky 1496327952Sdim return TI.EnforceSmallerThan(TypeListTmp, OtherNode->getExtType(OResNo)); 1497193323Sed } 1498193323Sed case SDTCisOpSmallerThanOp: { 1499205407Srdivacky unsigned BResNo = 0; 1500193323Sed TreePatternNode *BigOperand = 1501205407Srdivacky getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo, 1502205407Srdivacky BResNo); 1503327952Sdim return TI.EnforceSmallerThan(NodeToApply->getExtType(ResNo), 1504327952Sdim BigOperand->getExtType(BResNo)); 1505193323Sed } 1506193323Sed case SDTCisEltOfVec: { 1507205407Srdivacky unsigned VResNo = 0; 1508205218Srdivacky TreePatternNode *VecOperand = 1509205407Srdivacky getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo, 1510205407Srdivacky VResNo); 1511206083Srdivacky // Filter vector types out of VecOperand that don't have the right element 1512206083Srdivacky // type. 1513327952Sdim return TI.EnforceVectorEltTypeIs(VecOperand->getExtType(VResNo), 1514327952Sdim NodeToApply->getExtType(ResNo)); 1515193323Sed } 1516218893Sdim case SDTCisSubVecOfVec: { 1517218893Sdim unsigned VResNo = 0; 1518218893Sdim TreePatternNode *BigVecOperand = 1519218893Sdim getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo, 1520218893Sdim VResNo); 1521218893Sdim 1522218893Sdim // Filter vector types out of BigVecOperand that don't have the 1523218893Sdim // right subvector type. 1524327952Sdim return TI.EnforceVectorSubVectorTypeIs(BigVecOperand->getExtType(VResNo), 1525327952Sdim NodeToApply->getExtType(ResNo)); 1526218893Sdim } 1527288943Sdim case SDTCVecEltisVT: { 1528327952Sdim return TI.EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), VVT); 1529218893Sdim } 1530288943Sdim case SDTCisSameNumEltsAs: { 1531288943Sdim unsigned OResNo = 0; 1532288943Sdim TreePatternNode *OtherNode = 1533288943Sdim getOperandNum(x.SDTCisSameNumEltsAs_Info.OtherOperandNum, 1534288943Sdim N, NodeInfo, OResNo); 1535327952Sdim return TI.EnforceSameNumElts(OtherNode->getExtType(OResNo), 1536327952Sdim NodeToApply->getExtType(ResNo)); 1537288943Sdim } 1538296417Sdim case SDTCisSameSizeAs: { 1539296417Sdim unsigned OResNo = 0; 1540296417Sdim TreePatternNode *OtherNode = 1541296417Sdim getOperandNum(x.SDTCisSameSizeAs_Info.OtherOperandNum, 1542296417Sdim N, NodeInfo, OResNo); 1543327952Sdim return TI.EnforceSameSize(OtherNode->getExtType(OResNo), 1544327952Sdim NodeToApply->getExtType(ResNo)); 1545288943Sdim } 1546296417Sdim } 1547234353Sdim llvm_unreachable("Invalid ConstraintType!"); 1548193323Sed} 1549193323Sed 1550249423Sdim// Update the node type to match an instruction operand or result as specified 1551249423Sdim// in the ins or outs lists on the instruction definition. Return true if the 1552249423Sdim// type was actually changed. 1553249423Sdimbool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo, 1554249423Sdim Record *Operand, 1555249423Sdim TreePattern &TP) { 1556249423Sdim // The 'unknown' operand indicates that types should be inferred from the 1557249423Sdim // context. 1558249423Sdim if (Operand->isSubClassOf("unknown_class")) 1559249423Sdim return false; 1560249423Sdim 1561249423Sdim // The Operand class specifies a type directly. 1562327952Sdim if (Operand->isSubClassOf("Operand")) { 1563327952Sdim Record *R = Operand->getValueAsDef("Type"); 1564327952Sdim const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1565327952Sdim return UpdateNodeType(ResNo, getValueTypeByHwMode(R, T.getHwModes()), TP); 1566327952Sdim } 1567249423Sdim 1568249423Sdim // PointerLikeRegClass has a type that is determined at runtime. 1569249423Sdim if (Operand->isSubClassOf("PointerLikeRegClass")) 1570249423Sdim return UpdateNodeType(ResNo, MVT::iPTR, TP); 1571249423Sdim 1572249423Sdim // Both RegisterClass and RegisterOperand operands derive their types from a 1573249423Sdim // register class def. 1574276479Sdim Record *RC = nullptr; 1575249423Sdim if (Operand->isSubClassOf("RegisterClass")) 1576249423Sdim RC = Operand; 1577249423Sdim else if (Operand->isSubClassOf("RegisterOperand")) 1578249423Sdim RC = Operand->getValueAsDef("RegClass"); 1579249423Sdim 1580249423Sdim assert(RC && "Unknown operand type"); 1581249423Sdim CodeGenTarget &Tgt = TP.getDAGPatterns().getTargetInfo(); 1582249423Sdim return UpdateNodeType(ResNo, Tgt.getRegisterClass(RC).getValueTypes(), TP); 1583249423Sdim} 1584249423Sdim 1585327952Sdimbool TreePatternNode::ContainsUnresolvedType(TreePattern &TP) const { 1586327952Sdim for (unsigned i = 0, e = Types.size(); i != e; ++i) 1587327952Sdim if (!TP.getInfer().isConcrete(Types[i], true)) 1588327952Sdim return true; 1589327952Sdim for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1590327952Sdim if (getChild(i)->ContainsUnresolvedType(TP)) 1591327952Sdim return true; 1592327952Sdim return false; 1593327952Sdim} 1594249423Sdim 1595327952Sdimbool TreePatternNode::hasProperTypeByHwMode() const { 1596327952Sdim for (const TypeSetByHwMode &S : Types) 1597327952Sdim if (!S.isDefaultOnly()) 1598327952Sdim return true; 1599341825Sdim for (const TreePatternNodePtr &C : Children) 1600327952Sdim if (C->hasProperTypeByHwMode()) 1601327952Sdim return true; 1602327952Sdim return false; 1603327952Sdim} 1604327952Sdim 1605327952Sdimbool TreePatternNode::hasPossibleType() const { 1606327952Sdim for (const TypeSetByHwMode &S : Types) 1607327952Sdim if (!S.isPossible()) 1608327952Sdim return false; 1609341825Sdim for (const TreePatternNodePtr &C : Children) 1610327952Sdim if (!C->hasPossibleType()) 1611327952Sdim return false; 1612327952Sdim return true; 1613327952Sdim} 1614327952Sdim 1615327952Sdimbool TreePatternNode::setDefaultMode(unsigned Mode) { 1616327952Sdim for (TypeSetByHwMode &S : Types) { 1617327952Sdim S.makeSimple(Mode); 1618327952Sdim // Check if the selected mode had a type conflict. 1619327952Sdim if (S.get(DefaultMode).empty()) 1620327952Sdim return false; 1621327952Sdim } 1622341825Sdim for (const TreePatternNodePtr &C : Children) 1623327952Sdim if (!C->setDefaultMode(Mode)) 1624327952Sdim return false; 1625327952Sdim return true; 1626327952Sdim} 1627327952Sdim 1628193323Sed//===----------------------------------------------------------------------===// 1629193323Sed// SDNodeInfo implementation 1630193323Sed// 1631327952SdimSDNodeInfo::SDNodeInfo(Record *R, const CodeGenHwModes &CGH) : Def(R) { 1632193323Sed EnumName = R->getValueAsString("Opcode"); 1633193323Sed SDClassName = R->getValueAsString("SDClass"); 1634193323Sed Record *TypeProfile = R->getValueAsDef("TypeProfile"); 1635193323Sed NumResults = TypeProfile->getValueAsInt("NumResults"); 1636193323Sed NumOperands = TypeProfile->getValueAsInt("NumOperands"); 1637218893Sdim 1638193323Sed // Parse the properties. 1639327952Sdim Properties = parseSDPatternOperatorProperties(R); 1640218893Sdim 1641193323Sed // Parse the type constraints. 1642193323Sed std::vector<Record*> ConstraintList = 1643193323Sed TypeProfile->getValueAsListOfDefs("Constraints"); 1644327952Sdim for (Record *R : ConstraintList) 1645327952Sdim TypeConstraints.emplace_back(R, CGH); 1646193323Sed} 1647193323Sed 1648204642Srdivacky/// getKnownType - If the type constraints on this node imply a fixed type 1649204642Srdivacky/// (e.g. all stores return void, etc), then return it as an 1650205407Srdivacky/// MVT::SimpleValueType. Otherwise, return EEVT::Other. 1651206083SrdivackyMVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { 1652204642Srdivacky unsigned NumResults = getNumResults(); 1653204642Srdivacky assert(NumResults <= 1 && 1654204642Srdivacky "We only work with nodes with zero or one result so far!"); 1655206083Srdivacky assert(ResNo == 0 && "Only handles single result nodes so far"); 1656218893Sdim 1657296417Sdim for (const SDTypeConstraint &Constraint : TypeConstraints) { 1658204642Srdivacky // Make sure that this applies to the correct node result. 1659296417Sdim if (Constraint.OperandNo >= NumResults) // FIXME: need value # 1660204642Srdivacky continue; 1661218893Sdim 1662296417Sdim switch (Constraint.ConstraintType) { 1663204642Srdivacky default: break; 1664204642Srdivacky case SDTypeConstraint::SDTCisVT: 1665327952Sdim if (Constraint.VVT.isSimple()) 1666327952Sdim return Constraint.VVT.getSimple().SimpleTy; 1667327952Sdim break; 1668204642Srdivacky case SDTypeConstraint::SDTCisPtrTy: 1669204642Srdivacky return MVT::iPTR; 1670204642Srdivacky } 1671204642Srdivacky } 1672205407Srdivacky return MVT::Other; 1673204642Srdivacky} 1674204642Srdivacky 1675193323Sed//===----------------------------------------------------------------------===// 1676193323Sed// TreePatternNode implementation 1677193323Sed// 1678193323Sed 1679205407Srdivackystatic unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { 1680205407Srdivacky if (Operator->getName() == "set" || 1681206083Srdivacky Operator->getName() == "implicit") 1682205407Srdivacky return 0; // All return nothing. 1683218893Sdim 1684206083Srdivacky if (Operator->isSubClassOf("Intrinsic")) 1685206083Srdivacky return CDP.getIntrinsic(Operator).IS.RetVTs.size(); 1686218893Sdim 1687205407Srdivacky if (Operator->isSubClassOf("SDNode")) 1688205407Srdivacky return CDP.getSDNodeInfo(Operator).getNumResults(); 1689218893Sdim 1690341825Sdim if (Operator->isSubClassOf("PatFrags")) { 1691205407Srdivacky // If we've already parsed this pattern fragment, get it. Otherwise, handle 1692205407Srdivacky // the forward reference case where one pattern fragment references another 1693205407Srdivacky // before it is processed. 1694341825Sdim if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) { 1695341825Sdim // The number of results of a fragment with alternative records is the 1696341825Sdim // maximum number of results across all alternatives. 1697341825Sdim unsigned NumResults = 0; 1698341825Sdim for (auto T : PFRec->getTrees()) 1699341825Sdim NumResults = std::max(NumResults, T->getNumTypes()); 1700341825Sdim return NumResults; 1701341825Sdim } 1702218893Sdim 1703341825Sdim ListInit *LI = Operator->getValueAsListInit("Fragments"); 1704341825Sdim assert(LI && "Invalid Fragment"); 1705341825Sdim unsigned NumResults = 0; 1706341825Sdim for (Init *I : LI->getValues()) { 1707341825Sdim Record *Op = nullptr; 1708341825Sdim if (DagInit *Dag = dyn_cast<DagInit>(I)) 1709341825Sdim if (DefInit *DI = dyn_cast<DefInit>(Dag->getOperator())) 1710341825Sdim Op = DI->getDef(); 1711341825Sdim assert(Op && "Invalid Fragment"); 1712341825Sdim NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP)); 1713341825Sdim } 1714341825Sdim return NumResults; 1715205407Srdivacky } 1716218893Sdim 1717205407Srdivacky if (Operator->isSubClassOf("Instruction")) { 1718205407Srdivacky CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator); 1719206083Srdivacky 1720288943Sdim unsigned NumDefsToAdd = InstInfo.Operands.NumDefs; 1721218893Sdim 1722288943Sdim // Subtract any defaulted outputs. 1723288943Sdim for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) { 1724288943Sdim Record *OperandNode = InstInfo.Operands[i].Rec; 1725288943Sdim 1726288943Sdim if (OperandNode->isSubClassOf("OperandWithDefaultOps") && 1727288943Sdim !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 1728288943Sdim --NumDefsToAdd; 1729288943Sdim } 1730288943Sdim 1731206083Srdivacky // Add on one implicit def if it has a resolvable type. 1732206083Srdivacky if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other) 1733206083Srdivacky ++NumDefsToAdd; 1734206083Srdivacky return NumDefsToAdd; 1735205407Srdivacky } 1736218893Sdim 1737205407Srdivacky if (Operator->isSubClassOf("SDNodeXForm")) 1738205407Srdivacky return 1; // FIXME: Generalize SDNodeXForm 1739218893Sdim 1740276479Sdim if (Operator->isSubClassOf("ValueType")) 1741276479Sdim return 1; // A type-cast of one result. 1742276479Sdim 1743276479Sdim if (Operator->isSubClassOf("ComplexPattern")) 1744276479Sdim return 1; 1745276479Sdim 1746321369Sdim errs() << *Operator; 1747288943Sdim PrintFatalError("Unhandled node in GetNumNodeResults"); 1748205407Srdivacky} 1749193323Sed 1750195340Sedvoid TreePatternNode::print(raw_ostream &OS) const { 1751205407Srdivacky if (isLeaf()) 1752193323Sed OS << *getLeafValue(); 1753205407Srdivacky else 1754204642Srdivacky OS << '(' << getOperator()->getName(); 1755193323Sed 1756327952Sdim for (unsigned i = 0, e = Types.size(); i != e; ++i) { 1757327952Sdim OS << ':'; 1758327952Sdim getExtType(i).writeToStream(OS); 1759327952Sdim } 1760205407Srdivacky 1761193323Sed if (!isLeaf()) { 1762193323Sed if (getNumChildren() != 0) { 1763193323Sed OS << " "; 1764193323Sed getChild(0)->print(OS); 1765193323Sed for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 1766193323Sed OS << ", "; 1767193323Sed getChild(i)->print(OS); 1768193323Sed } 1769193323Sed } 1770193323Sed OS << ")"; 1771193323Sed } 1772218893Sdim 1773344779Sdim for (const TreePredicateCall &Pred : PredicateCalls) { 1774344779Sdim OS << "<<P:"; 1775344779Sdim if (Pred.Scope) 1776344779Sdim OS << Pred.Scope << ":"; 1777344779Sdim OS << Pred.Fn.getFnName() << ">>"; 1778344779Sdim } 1779193323Sed if (TransformFn) 1780193323Sed OS << "<<X:" << TransformFn->getName() << ">>"; 1781193323Sed if (!getName().empty()) 1782193323Sed OS << ":$" << getName(); 1783193323Sed 1784344779Sdim for (const ScopedName &Name : NamesAsPredicateArg) 1785344779Sdim OS << ":$pred:" << Name.getScope() << ":" << Name.getIdentifier(); 1786193323Sed} 1787193323Sedvoid TreePatternNode::dump() const { 1788195340Sed print(errs()); 1789193323Sed} 1790193323Sed 1791193323Sed/// isIsomorphicTo - Return true if this node is recursively 1792193323Sed/// isomorphic to the specified node. For this comparison, the node's 1793193323Sed/// entire state is considered. The assigned name is ignored, since 1794193323Sed/// nodes with differing names are considered isomorphic. However, if 1795193323Sed/// the assigned name is present in the dependent variable set, then 1796193323Sed/// the assigned name is considered significant and the node is 1797193323Sed/// isomorphic if the names match. 1798193323Sedbool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 1799193323Sed const MultipleUseVarSet &DepVars) const { 1800193323Sed if (N == this) return true; 1801205407Srdivacky if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 1802344779Sdim getPredicateCalls() != N->getPredicateCalls() || 1803193323Sed getTransformFn() != N->getTransformFn()) 1804193323Sed return false; 1805193323Sed 1806193323Sed if (isLeaf()) { 1807243830Sdim if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) { 1808243830Sdim if (DefInit *NDI = dyn_cast<DefInit>(N->getLeafValue())) { 1809193323Sed return ((DI->getDef() == NDI->getDef()) 1810193323Sed && (DepVars.find(getName()) == DepVars.end() 1811193323Sed || getName() == N->getName())); 1812193323Sed } 1813193323Sed } 1814193323Sed return getLeafValue() == N->getLeafValue(); 1815193323Sed } 1816218893Sdim 1817193323Sed if (N->getOperator() != getOperator() || 1818193323Sed N->getNumChildren() != getNumChildren()) return false; 1819193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1820193323Sed if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 1821193323Sed return false; 1822193323Sed return true; 1823193323Sed} 1824193323Sed 1825193323Sed/// clone - Make a copy of this tree and all of its children. 1826193323Sed/// 1827341825SdimTreePatternNodePtr TreePatternNode::clone() const { 1828341825Sdim TreePatternNodePtr New; 1829193323Sed if (isLeaf()) { 1830341825Sdim New = std::make_shared<TreePatternNode>(getLeafValue(), getNumTypes()); 1831193323Sed } else { 1832341825Sdim std::vector<TreePatternNodePtr> CChildren; 1833193323Sed CChildren.reserve(Children.size()); 1834193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1835193323Sed CChildren.push_back(getChild(i)->clone()); 1836341825Sdim New = std::make_shared<TreePatternNode>(getOperator(), std::move(CChildren), 1837341825Sdim getNumTypes()); 1838193323Sed } 1839193323Sed New->setName(getName()); 1840344779Sdim New->setNamesAsPredicateArg(getNamesAsPredicateArg()); 1841205407Srdivacky New->Types = Types; 1842344779Sdim New->setPredicateCalls(getPredicateCalls()); 1843193323Sed New->setTransformFn(getTransformFn()); 1844193323Sed return New; 1845193323Sed} 1846193323Sed 1847203954Srdivacky/// RemoveAllTypes - Recursively strip all the types of this tree. 1848203954Srdivackyvoid TreePatternNode::RemoveAllTypes() { 1849296417Sdim // Reset to unknown type. 1850327952Sdim std::fill(Types.begin(), Types.end(), TypeSetByHwMode()); 1851203954Srdivacky if (isLeaf()) return; 1852203954Srdivacky for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1853203954Srdivacky getChild(i)->RemoveAllTypes(); 1854203954Srdivacky} 1855203954Srdivacky 1856203954Srdivacky 1857193323Sed/// SubstituteFormalArguments - Replace the formal arguments in this tree 1858193323Sed/// with actual values specified by ArgMap. 1859341825Sdimvoid TreePatternNode::SubstituteFormalArguments( 1860341825Sdim std::map<std::string, TreePatternNodePtr> &ArgMap) { 1861193323Sed if (isLeaf()) return; 1862218893Sdim 1863193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1864193323Sed TreePatternNode *Child = getChild(i); 1865193323Sed if (Child->isLeaf()) { 1866193323Sed Init *Val = Child->getLeafValue(); 1867276479Sdim // Note that, when substituting into an output pattern, Val might be an 1868276479Sdim // UnsetInit. 1869276479Sdim if (isa<UnsetInit>(Val) || (isa<DefInit>(Val) && 1870276479Sdim cast<DefInit>(Val)->getDef()->getName() == "node")) { 1871193323Sed // We found a use of a formal argument, replace it with its value. 1872341825Sdim TreePatternNodePtr NewChild = ArgMap[Child->getName()]; 1873193323Sed assert(NewChild && "Couldn't find formal argument!"); 1874344779Sdim assert((Child->getPredicateCalls().empty() || 1875344779Sdim NewChild->getPredicateCalls() == Child->getPredicateCalls()) && 1876193323Sed "Non-empty child predicate clobbered!"); 1877341825Sdim setChild(i, std::move(NewChild)); 1878193323Sed } 1879193323Sed } else { 1880193323Sed getChild(i)->SubstituteFormalArguments(ArgMap); 1881193323Sed } 1882193323Sed } 1883193323Sed} 1884193323Sed 1885193323Sed 1886193323Sed/// InlinePatternFragments - If this pattern refers to any pattern 1887341825Sdim/// fragments, return the set of inlined versions (this can be more than 1888341825Sdim/// one if a PatFrags record has multiple alternatives). 1889341825Sdimvoid TreePatternNode::InlinePatternFragments( 1890341825Sdim TreePatternNodePtr T, TreePattern &TP, 1891341825Sdim std::vector<TreePatternNodePtr> &OutAlternatives) { 1892341825Sdim 1893243830Sdim if (TP.hasError()) 1894341825Sdim return; 1895243830Sdim 1896341825Sdim if (isLeaf()) { 1897341825Sdim OutAlternatives.push_back(T); // nothing to do. 1898341825Sdim return; 1899341825Sdim } 1900341825Sdim 1901193323Sed Record *Op = getOperator(); 1902218893Sdim 1903341825Sdim if (!Op->isSubClassOf("PatFrags")) { 1904341825Sdim if (getNumChildren() == 0) { 1905341825Sdim OutAlternatives.push_back(T); 1906341825Sdim return; 1907341825Sdim } 1908341825Sdim 1909341825Sdim // Recursively inline children nodes. 1910341825Sdim std::vector<std::vector<TreePatternNodePtr> > ChildAlternatives; 1911341825Sdim ChildAlternatives.resize(getNumChildren()); 1912193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1913341825Sdim TreePatternNodePtr Child = getChildShared(i); 1914341825Sdim Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]); 1915341825Sdim // If there are no alternatives for any child, there are no 1916341825Sdim // alternatives for this expression as whole. 1917341825Sdim if (ChildAlternatives[i].empty()) 1918341825Sdim return; 1919193323Sed 1920341825Sdim for (auto NewChild : ChildAlternatives[i]) 1921344779Sdim assert((Child->getPredicateCalls().empty() || 1922344779Sdim NewChild->getPredicateCalls() == Child->getPredicateCalls()) && 1923341825Sdim "Non-empty child predicate clobbered!"); 1924341825Sdim } 1925193323Sed 1926341825Sdim // The end result is an all-pairs construction of the resultant pattern. 1927341825Sdim std::vector<unsigned> Idxs; 1928341825Sdim Idxs.resize(ChildAlternatives.size()); 1929341825Sdim bool NotDone; 1930341825Sdim do { 1931341825Sdim // Create the variant and add it to the output list. 1932341825Sdim std::vector<TreePatternNodePtr> NewChildren; 1933341825Sdim for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i) 1934341825Sdim NewChildren.push_back(ChildAlternatives[i][Idxs[i]]); 1935341825Sdim TreePatternNodePtr R = std::make_shared<TreePatternNode>( 1936341825Sdim getOperator(), std::move(NewChildren), getNumTypes()); 1937341825Sdim 1938341825Sdim // Copy over properties. 1939341825Sdim R->setName(getName()); 1940344779Sdim R->setNamesAsPredicateArg(getNamesAsPredicateArg()); 1941344779Sdim R->setPredicateCalls(getPredicateCalls()); 1942341825Sdim R->setTransformFn(getTransformFn()); 1943341825Sdim for (unsigned i = 0, e = getNumTypes(); i != e; ++i) 1944341825Sdim R->setType(i, getExtType(i)); 1945344779Sdim for (unsigned i = 0, e = getNumResults(); i != e; ++i) 1946344779Sdim R->setResultIndex(i, getResultIndex(i)); 1947341825Sdim 1948341825Sdim // Register alternative. 1949341825Sdim OutAlternatives.push_back(R); 1950341825Sdim 1951341825Sdim // Increment indices to the next permutation by incrementing the 1952341825Sdim // indices from last index backward, e.g., generate the sequence 1953341825Sdim // [0, 0], [0, 1], [1, 0], [1, 1]. 1954341825Sdim int IdxsIdx; 1955341825Sdim for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 1956341825Sdim if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size()) 1957341825Sdim Idxs[IdxsIdx] = 0; 1958341825Sdim else 1959341825Sdim break; 1960341825Sdim } 1961341825Sdim NotDone = (IdxsIdx >= 0); 1962341825Sdim } while (NotDone); 1963341825Sdim 1964341825Sdim return; 1965193323Sed } 1966193323Sed 1967193323Sed // Otherwise, we found a reference to a fragment. First, look up its 1968193323Sed // TreePattern record. 1969193323Sed TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 1970218893Sdim 1971193323Sed // Verify that we are passing the right number of operands. 1972243830Sdim if (Frag->getNumArgs() != Children.size()) { 1973193323Sed TP.error("'" + Op->getName() + "' fragment requires " + 1974327952Sdim Twine(Frag->getNumArgs()) + " operands!"); 1975341825Sdim return; 1976243830Sdim } 1977193323Sed 1978344779Sdim TreePredicateFn PredFn(Frag); 1979344779Sdim unsigned Scope = 0; 1980344779Sdim if (TreePredicateFn(Frag).usesOperands()) 1981344779Sdim Scope = TP.getDAGPatterns().allocateScope(); 1982344779Sdim 1983341825Sdim // Compute the map of formal to actual arguments. 1984341825Sdim std::map<std::string, TreePatternNodePtr> ArgMap; 1985341825Sdim for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) { 1986344779Sdim TreePatternNodePtr Child = getChildShared(i); 1987344779Sdim if (Scope != 0) { 1988344779Sdim Child = Child->clone(); 1989344779Sdim Child->addNameAsPredicateArg(ScopedName(Scope, Frag->getArgName(i))); 1990344779Sdim } 1991341825Sdim ArgMap[Frag->getArgName(i)] = Child; 1992341825Sdim } 1993193323Sed 1994341825Sdim // Loop over all fragment alternatives. 1995341825Sdim for (auto Alternative : Frag->getTrees()) { 1996341825Sdim TreePatternNodePtr FragTree = Alternative->clone(); 1997193323Sed 1998341825Sdim if (!PredFn.isAlwaysTrue()) 1999344779Sdim FragTree->addPredicateCall(PredFn, Scope); 2000218893Sdim 2001341825Sdim // Resolve formal arguments to their actual value. 2002341825Sdim if (Frag->getNumArgs()) 2003341825Sdim FragTree->SubstituteFormalArguments(ArgMap); 2004218893Sdim 2005341825Sdim // Transfer types. Note that the resolved alternative may have fewer 2006341825Sdim // (but not more) results than the PatFrags node. 2007341825Sdim FragTree->setName(getName()); 2008341825Sdim for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i) 2009341825Sdim FragTree->UpdateNodeType(i, getExtType(i), TP); 2010193323Sed 2011341825Sdim // Transfer in the old predicates. 2012344779Sdim for (const TreePredicateCall &Pred : getPredicateCalls()) 2013344779Sdim FragTree->addPredicateCall(Pred); 2014193323Sed 2015341825Sdim // The fragment we inlined could have recursive inlining that is needed. See 2016341825Sdim // if there are any pattern fragments in it and inline them as needed. 2017341825Sdim FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives); 2018341825Sdim } 2019193323Sed} 2020193323Sed 2021193323Sed/// getImplicitType - Check to see if the specified record has an implicit 2022194612Sed/// type which should be applied to it. This will infer the type of register 2023193323Sed/// references from the register file information, for example. 2024193323Sed/// 2025249423Sdim/// When Unnamed is set, return the type of a DAG operand with no name, such as 2026249423Sdim/// the F8RC register class argument in: 2027249423Sdim/// 2028249423Sdim/// (COPY_TO_REGCLASS GPR:$src, F8RC) 2029249423Sdim/// 2030249423Sdim/// When Unnamed is false, return the type of a named DAG operand such as the 2031249423Sdim/// GPR:$src operand above. 2032249423Sdim/// 2033327952Sdimstatic TypeSetByHwMode getImplicitType(Record *R, unsigned ResNo, 2034327952Sdim bool NotRegisters, 2035327952Sdim bool Unnamed, 2036327952Sdim TreePattern &TP) { 2037327952Sdim CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 2038327952Sdim 2039224145Sdim // Check to see if this is a register operand. 2040224145Sdim if (R->isSubClassOf("RegisterOperand")) { 2041224145Sdim assert(ResNo == 0 && "Regoperand ref only has one result!"); 2042224145Sdim if (NotRegisters) 2043327952Sdim return TypeSetByHwMode(); // Unknown. 2044224145Sdim Record *RegClass = R->getValueAsDef("RegClass"); 2045224145Sdim const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 2046327952Sdim return TypeSetByHwMode(T.getRegisterClass(RegClass).getValueTypes()); 2047224145Sdim } 2048224145Sdim 2049205218Srdivacky // Check to see if this is a register or a register class. 2050193323Sed if (R->isSubClassOf("RegisterClass")) { 2051206083Srdivacky assert(ResNo == 0 && "Regclass ref only has one result!"); 2052249423Sdim // An unnamed register class represents itself as an i32 immediate, for 2053249423Sdim // example on a COPY_TO_REGCLASS instruction. 2054249423Sdim if (Unnamed) 2055327952Sdim return TypeSetByHwMode(MVT::i32); 2056249423Sdim 2057249423Sdim // In a named operand, the register class provides the possible set of 2058249423Sdim // types. 2059218893Sdim if (NotRegisters) 2060327952Sdim return TypeSetByHwMode(); // Unknown. 2061205218Srdivacky const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 2062327952Sdim return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes()); 2063206083Srdivacky } 2064218893Sdim 2065341825Sdim if (R->isSubClassOf("PatFrags")) { 2066206083Srdivacky assert(ResNo == 0 && "FIXME: PatFrag with multiple results?"); 2067193323Sed // Pattern fragment types will be resolved when they are inlined. 2068327952Sdim return TypeSetByHwMode(); // Unknown. 2069206083Srdivacky } 2070218893Sdim 2071206083Srdivacky if (R->isSubClassOf("Register")) { 2072206083Srdivacky assert(ResNo == 0 && "Registers only produce one result!"); 2073218893Sdim if (NotRegisters) 2074327952Sdim return TypeSetByHwMode(); // Unknown. 2075193323Sed const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 2076327952Sdim return TypeSetByHwMode(T.getRegisterVTs(R)); 2077206083Srdivacky } 2078208599Srdivacky 2079208599Srdivacky if (R->isSubClassOf("SubRegIndex")) { 2080208599Srdivacky assert(ResNo == 0 && "SubRegisterIndices only produce one result!"); 2081327952Sdim return TypeSetByHwMode(MVT::i32); 2082208599Srdivacky } 2083218893Sdim 2084249423Sdim if (R->isSubClassOf("ValueType")) { 2085206083Srdivacky assert(ResNo == 0 && "This node only has one result!"); 2086249423Sdim // An unnamed VTSDNode represents itself as an MVT::Other immediate. 2087249423Sdim // 2088249423Sdim // (sext_inreg GPR:$src, i16) 2089249423Sdim // ~~~ 2090249423Sdim if (Unnamed) 2091327952Sdim return TypeSetByHwMode(MVT::Other); 2092249423Sdim // With a name, the ValueType simply provides the type of the named 2093249423Sdim // variable. 2094249423Sdim // 2095249423Sdim // (sext_inreg i32:$src, i16) 2096249423Sdim // ~~~~~~~~ 2097249423Sdim if (NotRegisters) 2098327952Sdim return TypeSetByHwMode(); // Unknown. 2099327952Sdim const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes(); 2100327952Sdim return TypeSetByHwMode(getValueTypeByHwMode(R, CGH)); 2101249423Sdim } 2102249423Sdim 2103249423Sdim if (R->isSubClassOf("CondCode")) { 2104249423Sdim assert(ResNo == 0 && "This node only has one result!"); 2105249423Sdim // Using a CondCodeSDNode. 2106327952Sdim return TypeSetByHwMode(MVT::Other); 2107206083Srdivacky } 2108218893Sdim 2109206083Srdivacky if (R->isSubClassOf("ComplexPattern")) { 2110206083Srdivacky assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?"); 2111218893Sdim if (NotRegisters) 2112327952Sdim return TypeSetByHwMode(); // Unknown. 2113327952Sdim return TypeSetByHwMode(CDP.getComplexPattern(R).getValueType()); 2114206083Srdivacky } 2115206083Srdivacky if (R->isSubClassOf("PointerLikeRegClass")) { 2116206083Srdivacky assert(ResNo == 0 && "Regclass can only have one result!"); 2117327952Sdim TypeSetByHwMode VTS(MVT::iPTR); 2118327952Sdim TP.getInfer().expandOverloads(VTS); 2119327952Sdim return VTS; 2120206083Srdivacky } 2121218893Sdim 2122206083Srdivacky if (R->getName() == "node" || R->getName() == "srcvalue" || 2123206083Srdivacky R->getName() == "zero_reg") { 2124193323Sed // Placeholder. 2125327952Sdim return TypeSetByHwMode(); // Unknown. 2126193323Sed } 2127218893Sdim 2128327952Sdim if (R->isSubClassOf("Operand")) { 2129327952Sdim const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes(); 2130327952Sdim Record *T = R->getValueAsDef("Type"); 2131327952Sdim return TypeSetByHwMode(getValueTypeByHwMode(T, CGH)); 2132327952Sdim } 2133276479Sdim 2134193323Sed TP.error("Unknown node flavor used in pattern: " + R->getName()); 2135327952Sdim return TypeSetByHwMode(MVT::Other); 2136193323Sed} 2137193323Sed 2138193323Sed 2139193323Sed/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 2140193323Sed/// CodeGenIntrinsic information for it, otherwise return a null pointer. 2141193323Sedconst CodeGenIntrinsic *TreePatternNode:: 2142193323SedgetIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 2143193323Sed if (getOperator() != CDP.get_intrinsic_void_sdnode() && 2144193323Sed getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 2145193323Sed getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 2146276479Sdim return nullptr; 2147218893Sdim 2148243830Sdim unsigned IID = cast<IntInit>(getChild(0)->getLeafValue())->getValue(); 2149193323Sed return &CDP.getIntrinsicInfo(IID); 2150193323Sed} 2151193323Sed 2152203954Srdivacky/// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 2153203954Srdivacky/// return the ComplexPattern information, otherwise return null. 2154203954Srdivackyconst ComplexPattern * 2155203954SrdivackyTreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { 2156276479Sdim Record *Rec; 2157276479Sdim if (isLeaf()) { 2158276479Sdim DefInit *DI = dyn_cast<DefInit>(getLeafValue()); 2159276479Sdim if (!DI) 2160276479Sdim return nullptr; 2161276479Sdim Rec = DI->getDef(); 2162276479Sdim } else 2163276479Sdim Rec = getOperator(); 2164218893Sdim 2165276479Sdim if (!Rec->isSubClassOf("ComplexPattern")) 2166276479Sdim return nullptr; 2167276479Sdim return &CGP.getComplexPattern(Rec); 2168203954Srdivacky} 2169203954Srdivacky 2170276479Sdimunsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const { 2171276479Sdim // A ComplexPattern specifically declares how many results it fills in. 2172276479Sdim if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 2173276479Sdim return CP->getNumOperands(); 2174276479Sdim 2175276479Sdim // If MIOperandInfo is specified, that gives the count. 2176276479Sdim if (isLeaf()) { 2177276479Sdim DefInit *DI = dyn_cast<DefInit>(getLeafValue()); 2178276479Sdim if (DI && DI->getDef()->isSubClassOf("Operand")) { 2179276479Sdim DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo"); 2180276479Sdim if (MIOps->getNumArgs()) 2181276479Sdim return MIOps->getNumArgs(); 2182276479Sdim } 2183276479Sdim } 2184276479Sdim 2185276479Sdim // Otherwise there is just one result. 2186276479Sdim return 1; 2187276479Sdim} 2188276479Sdim 2189203954Srdivacky/// NodeHasProperty - Return true if this node has the specified property. 2190203954Srdivackybool TreePatternNode::NodeHasProperty(SDNP Property, 2191203954Srdivacky const CodeGenDAGPatterns &CGP) const { 2192203954Srdivacky if (isLeaf()) { 2193203954Srdivacky if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 2194203954Srdivacky return CP->hasProperty(Property); 2195327952Sdim 2196203954Srdivacky return false; 2197203954Srdivacky } 2198218893Sdim 2199327952Sdim if (Property != SDNPHasChain) { 2200327952Sdim // The chain proprety is already present on the different intrinsic node 2201327952Sdim // types (intrinsic_w_chain, intrinsic_void), and is not explicitly listed 2202327952Sdim // on the intrinsic. Anything else is specific to the individual intrinsic. 2203327952Sdim if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CGP)) 2204327952Sdim return Int->hasProperty(Property); 2205327952Sdim } 2206218893Sdim 2207327952Sdim if (!Operator->isSubClassOf("SDPatternOperator")) 2208327952Sdim return false; 2209327952Sdim 2210203954Srdivacky return CGP.getSDNodeInfo(Operator).hasProperty(Property); 2211203954Srdivacky} 2212203954Srdivacky 2213203954Srdivacky 2214203954Srdivacky 2215203954Srdivacky 2216203954Srdivacky/// TreeHasProperty - Return true if any node in this tree has the specified 2217203954Srdivacky/// property. 2218203954Srdivackybool TreePatternNode::TreeHasProperty(SDNP Property, 2219203954Srdivacky const CodeGenDAGPatterns &CGP) const { 2220203954Srdivacky if (NodeHasProperty(Property, CGP)) 2221203954Srdivacky return true; 2222203954Srdivacky for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2223203954Srdivacky if (getChild(i)->TreeHasProperty(Property, CGP)) 2224203954Srdivacky return true; 2225203954Srdivacky return false; 2226218893Sdim} 2227203954Srdivacky 2228193323Sed/// isCommutativeIntrinsic - Return true if the node corresponds to a 2229193323Sed/// commutative intrinsic. 2230193323Sedbool 2231193323SedTreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { 2232193323Sed if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) 2233193323Sed return Int->isCommutative; 2234193323Sed return false; 2235193323Sed} 2236193323Sed 2237280031Sdimstatic bool isOperandClass(const TreePatternNode *N, StringRef Class) { 2238280031Sdim if (!N->isLeaf()) 2239280031Sdim return N->getOperator()->isSubClassOf(Class); 2240193323Sed 2241280031Sdim DefInit *DI = dyn_cast<DefInit>(N->getLeafValue()); 2242280031Sdim if (DI && DI->getDef()->isSubClassOf(Class)) 2243280031Sdim return true; 2244280031Sdim 2245280031Sdim return false; 2246280031Sdim} 2247280031Sdim 2248280031Sdimstatic void emitTooManyOperandsError(TreePattern &TP, 2249280031Sdim StringRef InstName, 2250280031Sdim unsigned Expected, 2251280031Sdim unsigned Actual) { 2252280031Sdim TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) + 2253280031Sdim " operands but expected only " + Twine(Expected) + "!"); 2254280031Sdim} 2255280031Sdim 2256280031Sdimstatic void emitTooFewOperandsError(TreePattern &TP, 2257280031Sdim StringRef InstName, 2258280031Sdim unsigned Actual) { 2259280031Sdim TP.error("Instruction '" + InstName + 2260280031Sdim "' expects more than the provided " + Twine(Actual) + " operands!"); 2261280031Sdim} 2262280031Sdim 2263193323Sed/// ApplyTypeConstraints - Apply all of the type constraints relevant to 2264193323Sed/// this node and its children in the tree. This returns true if it makes a 2265243830Sdim/// change, false otherwise. If a type contradiction is found, flag an error. 2266193323Sedbool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 2267243830Sdim if (TP.hasError()) 2268243830Sdim return false; 2269243830Sdim 2270193323Sed CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 2271193323Sed if (isLeaf()) { 2272243830Sdim if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) { 2273193323Sed // If it's a regclass or something else known, include the type. 2274205407Srdivacky bool MadeChange = false; 2275205407Srdivacky for (unsigned i = 0, e = Types.size(); i != e; ++i) 2276205407Srdivacky MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i, 2277249423Sdim NotRegisters, 2278249423Sdim !hasName(), TP), TP); 2279205407Srdivacky return MadeChange; 2280203954Srdivacky } 2281218893Sdim 2282243830Sdim if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) { 2283205407Srdivacky assert(Types.size() == 1 && "Invalid IntInit"); 2284218893Sdim 2285193323Sed // Int inits are always integers. :) 2286327952Sdim bool MadeChange = TP.getInfer().EnforceInteger(Types[0]); 2287218893Sdim 2288327952Sdim if (!TP.getInfer().isConcrete(Types[0], false)) 2289205218Srdivacky return MadeChange; 2290218893Sdim 2291327952Sdim ValueTypeByHwMode VVT = TP.getInfer().getConcrete(Types[0], false); 2292327952Sdim for (auto &P : VVT) { 2293327952Sdim MVT::SimpleValueType VT = P.second.SimpleTy; 2294327952Sdim if (VT == MVT::iPTR || VT == MVT::iPTRAny) 2295327952Sdim continue; 2296327952Sdim unsigned Size = MVT(VT).getSizeInBits(); 2297327952Sdim // Make sure that the value is representable for this type. 2298327952Sdim if (Size >= 32) 2299327952Sdim continue; 2300327952Sdim // Check that the value doesn't use more bits than we have. It must 2301327952Sdim // either be a sign- or zero-extended equivalent of the original. 2302327952Sdim int64_t SignBitAndAbove = II->getValue() >> (Size - 1); 2303327952Sdim if (SignBitAndAbove == -1 || SignBitAndAbove == 0 || 2304327952Sdim SignBitAndAbove == 1) 2305327952Sdim continue; 2306218893Sdim 2307327952Sdim TP.error("Integer value '" + Twine(II->getValue()) + 2308327952Sdim "' is out of range for type '" + getEnumName(VT) + "'!"); 2309327952Sdim break; 2310327952Sdim } 2311327952Sdim return MadeChange; 2312327952Sdim } 2313218893Sdim 2314193323Sed return false; 2315193323Sed } 2316218893Sdim 2317204642Srdivacky if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 2318193323Sed bool MadeChange = false; 2319193323Sed 2320193323Sed // Apply the result type to the node. 2321193323Sed unsigned NumRetVTs = Int->IS.RetVTs.size(); 2322193323Sed unsigned NumParamVTs = Int->IS.ParamVTs.size(); 2323218893Sdim 2324193323Sed for (unsigned i = 0, e = NumRetVTs; i != e; ++i) 2325205407Srdivacky MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP); 2326193323Sed 2327243830Sdim if (getNumChildren() != NumParamVTs + 1) { 2328327952Sdim TP.error("Intrinsic '" + Int->Name + "' expects " + Twine(NumParamVTs) + 2329327952Sdim " operands, not " + Twine(getNumChildren() - 1) + " operands!"); 2330243830Sdim return false; 2331243830Sdim } 2332193323Sed 2333193323Sed // Apply type info to the intrinsic ID. 2334205407Srdivacky MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP); 2335218893Sdim 2336205407Srdivacky for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) { 2337205407Srdivacky MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters); 2338218893Sdim 2339205407Srdivacky MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i]; 2340205407Srdivacky assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case"); 2341205407Srdivacky MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP); 2342193323Sed } 2343193323Sed return MadeChange; 2344204642Srdivacky } 2345218893Sdim 2346204642Srdivacky if (getOperator()->isSubClassOf("SDNode")) { 2347193323Sed const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 2348218893Sdim 2349206083Srdivacky // Check that the number of operands is sane. Negative operands -> varargs. 2350206083Srdivacky if (NI.getNumOperands() >= 0 && 2351243830Sdim getNumChildren() != (unsigned)NI.getNumOperands()) { 2352206083Srdivacky TP.error(getOperator()->getName() + " node requires exactly " + 2353327952Sdim Twine(NI.getNumOperands()) + " operands!"); 2354243830Sdim return false; 2355243830Sdim } 2356218893Sdim 2357327952Sdim bool MadeChange = false; 2358193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2359193323Sed MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 2360327952Sdim MadeChange |= NI.ApplyTypeConstraints(this, TP); 2361205407Srdivacky return MadeChange; 2362204642Srdivacky } 2363218893Sdim 2364204642Srdivacky if (getOperator()->isSubClassOf("Instruction")) { 2365193323Sed const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 2366193323Sed CodeGenInstruction &InstInfo = 2367205407Srdivacky CDP.getTargetInfo().getInstruction(getOperator()); 2368218893Sdim 2369206083Srdivacky bool MadeChange = false; 2370206083Srdivacky 2371206083Srdivacky // Apply the result types to the node, these come from the things in the 2372206083Srdivacky // (outs) list of the instruction. 2373288943Sdim unsigned NumResultsToAdd = std::min(InstInfo.Operands.NumDefs, 2374288943Sdim Inst.getNumResults()); 2375249423Sdim for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo) 2376249423Sdim MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP); 2377218893Sdim 2378206083Srdivacky // If the instruction has implicit defs, we apply the first one as a result. 2379206083Srdivacky // FIXME: This sucks, it should apply all implicit defs. 2380206083Srdivacky if (!InstInfo.ImplicitDefs.empty()) { 2381206083Srdivacky unsigned ResNo = NumResultsToAdd; 2382218893Sdim 2383206083Srdivacky // FIXME: Generalize to multiple possible types and multiple possible 2384206083Srdivacky // ImplicitDefs. 2385206083Srdivacky MVT::SimpleValueType VT = 2386206083Srdivacky InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()); 2387218893Sdim 2388206083Srdivacky if (VT != MVT::Other) 2389206083Srdivacky MadeChange |= UpdateNodeType(ResNo, VT, TP); 2390206083Srdivacky } 2391218893Sdim 2392205218Srdivacky // If this is an INSERT_SUBREG, constrain the source and destination VTs to 2393205218Srdivacky // be the same. 2394205218Srdivacky if (getOperator()->getName() == "INSERT_SUBREG") { 2395205407Srdivacky assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); 2396205407Srdivacky MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); 2397205407Srdivacky MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); 2398280031Sdim } else if (getOperator()->getName() == "REG_SEQUENCE") { 2399280031Sdim // We need to do extra, custom typechecking for REG_SEQUENCE since it is 2400280031Sdim // variadic. 2401280031Sdim 2402280031Sdim unsigned NChild = getNumChildren(); 2403280031Sdim if (NChild < 3) { 2404280031Sdim TP.error("REG_SEQUENCE requires at least 3 operands!"); 2405280031Sdim return false; 2406280031Sdim } 2407280031Sdim 2408280031Sdim if (NChild % 2 == 0) { 2409280031Sdim TP.error("REG_SEQUENCE requires an odd number of operands!"); 2410280031Sdim return false; 2411280031Sdim } 2412280031Sdim 2413280031Sdim if (!isOperandClass(getChild(0), "RegisterClass")) { 2414280031Sdim TP.error("REG_SEQUENCE requires a RegisterClass for first operand!"); 2415280031Sdim return false; 2416280031Sdim } 2417280031Sdim 2418280031Sdim for (unsigned I = 1; I < NChild; I += 2) { 2419280031Sdim TreePatternNode *SubIdxChild = getChild(I + 1); 2420280031Sdim if (!isOperandClass(SubIdxChild, "SubRegIndex")) { 2421280031Sdim TP.error("REG_SEQUENCE requires a SubRegIndex for operand " + 2422327952Sdim Twine(I + 1) + "!"); 2423280031Sdim return false; 2424280031Sdim } 2425280031Sdim } 2426205218Srdivacky } 2427193323Sed 2428193323Sed unsigned ChildNo = 0; 2429193323Sed for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 2430193323Sed Record *OperandNode = Inst.getOperand(i); 2431218893Sdim 2432193323Sed // If the instruction expects a predicate or optional def operand, we 2433193323Sed // codegen this by setting the operand to it's default value if it has a 2434193323Sed // non-empty DefaultOps field. 2435243830Sdim if (OperandNode->isSubClassOf("OperandWithDefaultOps") && 2436193323Sed !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 2437193323Sed continue; 2438218893Sdim 2439193323Sed // Verify that we didn't run out of provided operands. 2440243830Sdim if (ChildNo >= getNumChildren()) { 2441280031Sdim emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren()); 2442243830Sdim return false; 2443243830Sdim } 2444218893Sdim 2445193323Sed TreePatternNode *Child = getChild(ChildNo++); 2446206083Srdivacky unsigned ChildResNo = 0; // Instructions always use res #0 of their op. 2447218893Sdim 2448249423Sdim // If the operand has sub-operands, they may be provided by distinct 2449249423Sdim // child patterns, so attempt to match each sub-operand separately. 2450249423Sdim if (OperandNode->isSubClassOf("Operand")) { 2451249423Sdim DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo"); 2452249423Sdim if (unsigned NumArgs = MIOpInfo->getNumArgs()) { 2453249423Sdim // But don't do that if the whole operand is being provided by 2454276479Sdim // a single ComplexPattern-related Operand. 2455276479Sdim 2456276479Sdim if (Child->getNumMIResults(CDP) < NumArgs) { 2457249423Sdim // Match first sub-operand against the child we already have. 2458249423Sdim Record *SubRec = cast<DefInit>(MIOpInfo->getArg(0))->getDef(); 2459249423Sdim MadeChange |= 2460249423Sdim Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP); 2461234353Sdim 2462249423Sdim // And the remaining sub-operands against subsequent children. 2463249423Sdim for (unsigned Arg = 1; Arg < NumArgs; ++Arg) { 2464249423Sdim if (ChildNo >= getNumChildren()) { 2465280031Sdim emitTooFewOperandsError(TP, getOperator()->getName(), 2466280031Sdim getNumChildren()); 2467249423Sdim return false; 2468249423Sdim } 2469249423Sdim Child = getChild(ChildNo++); 2470249423Sdim 2471249423Sdim SubRec = cast<DefInit>(MIOpInfo->getArg(Arg))->getDef(); 2472249423Sdim MadeChange |= 2473249423Sdim Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP); 2474249423Sdim } 2475249423Sdim continue; 2476249423Sdim } 2477249423Sdim } 2478249423Sdim } 2479249423Sdim 2480249423Sdim // If we didn't match by pieces above, attempt to match the whole 2481249423Sdim // operand now. 2482249423Sdim MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP); 2483193323Sed } 2484193323Sed 2485280031Sdim if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) { 2486280031Sdim emitTooManyOperandsError(TP, getOperator()->getName(), 2487280031Sdim ChildNo, getNumChildren()); 2488243830Sdim return false; 2489243830Sdim } 2490218893Sdim 2491249423Sdim for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2492249423Sdim MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 2493193323Sed return MadeChange; 2494204642Srdivacky } 2495218893Sdim 2496276479Sdim if (getOperator()->isSubClassOf("ComplexPattern")) { 2497276479Sdim bool MadeChange = false; 2498276479Sdim 2499276479Sdim for (unsigned i = 0; i < getNumChildren(); ++i) 2500276479Sdim MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 2501276479Sdim 2502276479Sdim return MadeChange; 2503276479Sdim } 2504276479Sdim 2505204642Srdivacky assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 2506218893Sdim 2507204642Srdivacky // Node transforms always take one operand. 2508243830Sdim if (getNumChildren() != 1) { 2509204642Srdivacky TP.error("Node transform '" + getOperator()->getName() + 2510204642Srdivacky "' requires one operand!"); 2511243830Sdim return false; 2512243830Sdim } 2513193323Sed 2514205218Srdivacky bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 2515205218Srdivacky return MadeChange; 2516193323Sed} 2517193323Sed 2518193323Sed/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 2519193323Sed/// RHS of a commutative operation, not the on LHS. 2520193323Sedstatic bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 2521193323Sed if (!N->isLeaf() && N->getOperator()->getName() == "imm") 2522193323Sed return true; 2523243830Sdim if (N->isLeaf() && isa<IntInit>(N->getLeafValue())) 2524193323Sed return true; 2525193323Sed return false; 2526193323Sed} 2527193323Sed 2528193323Sed 2529193323Sed/// canPatternMatch - If it is impossible for this pattern to match on this 2530193323Sed/// target, fill in Reason and return false. Otherwise, return true. This is 2531193323Sed/// used as a sanity check for .td files (to prevent people from writing stuff 2532193323Sed/// that can never possibly work), and to prevent the pattern permuter from 2533193323Sed/// generating stuff that is useless. 2534218893Sdimbool TreePatternNode::canPatternMatch(std::string &Reason, 2535193323Sed const CodeGenDAGPatterns &CDP) { 2536193323Sed if (isLeaf()) return true; 2537193323Sed 2538193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 2539193323Sed if (!getChild(i)->canPatternMatch(Reason, CDP)) 2540193323Sed return false; 2541193323Sed 2542193323Sed // If this is an intrinsic, handle cases that would make it not match. For 2543193323Sed // example, if an operand is required to be an immediate. 2544193323Sed if (getOperator()->isSubClassOf("Intrinsic")) { 2545193323Sed // TODO: 2546193323Sed return true; 2547193323Sed } 2548218893Sdim 2549276479Sdim if (getOperator()->isSubClassOf("ComplexPattern")) 2550276479Sdim return true; 2551276479Sdim 2552193323Sed // If this node is a commutative operator, check that the LHS isn't an 2553193323Sed // immediate. 2554193323Sed const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 2555193323Sed bool isCommIntrinsic = isCommutativeIntrinsic(CDP); 2556193323Sed if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 2557193323Sed // Scan all of the operands of the node and make sure that only the last one 2558193323Sed // is a constant node, unless the RHS also is. 2559193323Sed if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 2560314564Sdim unsigned Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id. 2561193323Sed for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i) 2562193323Sed if (OnlyOnRHSOfCommutative(getChild(i))) { 2563193323Sed Reason="Immediate value must be on the RHS of commutative operators!"; 2564193323Sed return false; 2565193323Sed } 2566193323Sed } 2567193323Sed } 2568218893Sdim 2569193323Sed return true; 2570193323Sed} 2571193323Sed 2572193323Sed//===----------------------------------------------------------------------===// 2573193323Sed// TreePattern implementation 2574193323Sed// 2575193323Sed 2576193323SedTreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 2577243830Sdim CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2578327952Sdim isInputPattern(isInput), HasError(false), 2579327952Sdim Infer(*this) { 2580288943Sdim for (Init *I : RawPat->getValues()) 2581288943Sdim Trees.push_back(ParseTreePattern(I, "")); 2582193323Sed} 2583193323Sed 2584193323SedTreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 2585243830Sdim CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2586327952Sdim isInputPattern(isInput), HasError(false), 2587327952Sdim Infer(*this) { 2588206083Srdivacky Trees.push_back(ParseTreePattern(Pat, "")); 2589193323Sed} 2590193323Sed 2591341825SdimTreePattern::TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput, 2592341825Sdim CodeGenDAGPatterns &cdp) 2593341825Sdim : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false), 2594341825Sdim Infer(*this) { 2595193323Sed Trees.push_back(Pat); 2596193323Sed} 2597193323Sed 2598280031Sdimvoid TreePattern::error(const Twine &Msg) { 2599243830Sdim if (HasError) 2600243830Sdim return; 2601193323Sed dump(); 2602243830Sdim PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); 2603243830Sdim HasError = true; 2604193323Sed} 2605193323Sed 2606205218Srdivackyvoid TreePattern::ComputeNamedNodes() { 2607341825Sdim for (TreePatternNodePtr &Tree : Trees) 2608341825Sdim ComputeNamedNodes(Tree.get()); 2609205218Srdivacky} 2610205218Srdivacky 2611205218Srdivackyvoid TreePattern::ComputeNamedNodes(TreePatternNode *N) { 2612205218Srdivacky if (!N->getName().empty()) 2613205218Srdivacky NamedNodes[N->getName()].push_back(N); 2614218893Sdim 2615205218Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2616205218Srdivacky ComputeNamedNodes(N->getChild(i)); 2617205218Srdivacky} 2618205218Srdivacky 2619341825SdimTreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit, 2620341825Sdim StringRef OpName) { 2621243830Sdim if (DefInit *DI = dyn_cast<DefInit>(TheInit)) { 2622206083Srdivacky Record *R = DI->getDef(); 2623218893Sdim 2624206083Srdivacky // Direct reference to a leaf DagNode or PatFrag? Turn it into a 2625224145Sdim // TreePatternNode of its own. For example: 2626206083Srdivacky /// (foo GPR, imm) -> (foo GPR, (imm)) 2627341825Sdim if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrags")) 2628226633Sdim return ParseTreePattern( 2629314564Sdim DagInit::get(DI, nullptr, 2630314564Sdim std::vector<std::pair<Init*, StringInit*> >()), 2631226633Sdim OpName); 2632218893Sdim 2633206083Srdivacky // Input argument? 2634341825Sdim TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1); 2635206083Srdivacky if (R->getName() == "node" && !OpName.empty()) { 2636206083Srdivacky if (OpName.empty()) 2637206083Srdivacky error("'node' argument requires a name to match with operand list"); 2638206083Srdivacky Args.push_back(OpName); 2639206083Srdivacky } 2640206083Srdivacky 2641206083Srdivacky Res->setName(OpName); 2642206083Srdivacky return Res; 2643206083Srdivacky } 2644218893Sdim 2645249423Sdim // ?:$name or just $name. 2646288943Sdim if (isa<UnsetInit>(TheInit)) { 2647249423Sdim if (OpName.empty()) 2648249423Sdim error("'?' argument requires a name to match with operand list"); 2649341825Sdim TreePatternNodePtr Res = std::make_shared<TreePatternNode>(TheInit, 1); 2650249423Sdim Args.push_back(OpName); 2651249423Sdim Res->setName(OpName); 2652249423Sdim return Res; 2653249423Sdim } 2654249423Sdim 2655341825Sdim if (isa<IntInit>(TheInit) || isa<BitInit>(TheInit)) { 2656206083Srdivacky if (!OpName.empty()) 2657341825Sdim error("Constant int or bit argument should not have a name!"); 2658341825Sdim if (isa<BitInit>(TheInit)) 2659341825Sdim TheInit = TheInit->convertInitializerTo(IntRecTy::get()); 2660341825Sdim return std::make_shared<TreePatternNode>(TheInit, 1); 2661206083Srdivacky } 2662218893Sdim 2663243830Sdim if (BitsInit *BI = dyn_cast<BitsInit>(TheInit)) { 2664206083Srdivacky // Turn this into an IntInit. 2665226633Sdim Init *II = BI->convertInitializerTo(IntRecTy::get()); 2666276479Sdim if (!II || !isa<IntInit>(II)) 2667206083Srdivacky error("Bits value must be constants!"); 2668206083Srdivacky return ParseTreePattern(II, OpName); 2669206083Srdivacky } 2670206083Srdivacky 2671243830Sdim DagInit *Dag = dyn_cast<DagInit>(TheInit); 2672206083Srdivacky if (!Dag) { 2673321369Sdim TheInit->print(errs()); 2674206083Srdivacky error("Pattern has unexpected init kind!"); 2675206083Srdivacky } 2676243830Sdim DefInit *OpDef = dyn_cast<DefInit>(Dag->getOperator()); 2677193323Sed if (!OpDef) error("Pattern has unexpected operator type!"); 2678193323Sed Record *Operator = OpDef->getDef(); 2679218893Sdim 2680193323Sed if (Operator->isSubClassOf("ValueType")) { 2681193323Sed // If the operator is a ValueType, then this must be "type cast" of a leaf 2682193323Sed // node. 2683193323Sed if (Dag->getNumArgs() != 1) 2684193323Sed error("Type cast only takes one operand!"); 2685218893Sdim 2686341825Sdim TreePatternNodePtr New = 2687341825Sdim ParseTreePattern(Dag->getArg(0), Dag->getArgNameStr(0)); 2688218893Sdim 2689193323Sed // Apply the type cast. 2690205407Srdivacky assert(New->getNumTypes() == 1 && "FIXME: Unhandled"); 2691327952Sdim const CodeGenHwModes &CGH = getDAGPatterns().getTargetInfo().getHwModes(); 2692327952Sdim New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this); 2693218893Sdim 2694206083Srdivacky if (!OpName.empty()) 2695206083Srdivacky error("ValueType cast should not have a name!"); 2696193323Sed return New; 2697193323Sed } 2698218893Sdim 2699193323Sed // Verify that this is something that makes sense for an operator. 2700341825Sdim if (!Operator->isSubClassOf("PatFrags") && 2701193323Sed !Operator->isSubClassOf("SDNode") && 2702218893Sdim !Operator->isSubClassOf("Instruction") && 2703193323Sed !Operator->isSubClassOf("SDNodeXForm") && 2704193323Sed !Operator->isSubClassOf("Intrinsic") && 2705276479Sdim !Operator->isSubClassOf("ComplexPattern") && 2706193323Sed Operator->getName() != "set" && 2707206083Srdivacky Operator->getName() != "implicit") 2708193323Sed error("Unrecognized node '" + Operator->getName() + "'!"); 2709218893Sdim 2710193323Sed // Check to see if this is something that is illegal in an input pattern. 2711206083Srdivacky if (isInputPattern) { 2712206083Srdivacky if (Operator->isSubClassOf("Instruction") || 2713206083Srdivacky Operator->isSubClassOf("SDNodeXForm")) 2714206083Srdivacky error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 2715206083Srdivacky } else { 2716206083Srdivacky if (Operator->isSubClassOf("Intrinsic")) 2717206083Srdivacky error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 2718218893Sdim 2719206083Srdivacky if (Operator->isSubClassOf("SDNode") && 2720206083Srdivacky Operator->getName() != "imm" && 2721206083Srdivacky Operator->getName() != "fpimm" && 2722206083Srdivacky Operator->getName() != "tglobaltlsaddr" && 2723206083Srdivacky Operator->getName() != "tconstpool" && 2724206083Srdivacky Operator->getName() != "tjumptable" && 2725206083Srdivacky Operator->getName() != "tframeindex" && 2726206083Srdivacky Operator->getName() != "texternalsym" && 2727206083Srdivacky Operator->getName() != "tblockaddress" && 2728206083Srdivacky Operator->getName() != "tglobaladdr" && 2729206083Srdivacky Operator->getName() != "bb" && 2730288943Sdim Operator->getName() != "vt" && 2731288943Sdim Operator->getName() != "mcsym") 2732206083Srdivacky error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 2733206083Srdivacky } 2734218893Sdim 2735341825Sdim std::vector<TreePatternNodePtr> Children; 2736206083Srdivacky 2737206083Srdivacky // Parse all the operands. 2738206083Srdivacky for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) 2739314564Sdim Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgNameStr(i))); 2740218893Sdim 2741327952Sdim // Get the actual number of results before Operator is converted to an intrinsic 2742327952Sdim // node (which is hard-coded to have either zero or one result). 2743327952Sdim unsigned NumResults = GetNumNodeResults(Operator, CDP); 2744327952Sdim 2745341825Sdim // If the operator is an intrinsic, then this is just syntactic sugar for 2746218893Sdim // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 2747193323Sed // convert the intrinsic name to a number. 2748193323Sed if (Operator->isSubClassOf("Intrinsic")) { 2749193323Sed const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 2750193323Sed unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 2751193323Sed 2752193323Sed // If this intrinsic returns void, it must have side-effects and thus a 2753193323Sed // chain. 2754206083Srdivacky if (Int.IS.RetVTs.empty()) 2755193323Sed Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 2756206083Srdivacky else if (Int.ModRef != CodeGenIntrinsic::NoMem) 2757193323Sed // Has side-effects, requires chain. 2758193323Sed Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 2759206083Srdivacky else // Otherwise, no chain. 2760193323Sed Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 2761218893Sdim 2762341825Sdim Children.insert(Children.begin(), 2763341825Sdim std::make_shared<TreePatternNode>(IntInit::get(IID), 1)); 2764193323Sed } 2765218893Sdim 2766276479Sdim if (Operator->isSubClassOf("ComplexPattern")) { 2767276479Sdim for (unsigned i = 0; i < Children.size(); ++i) { 2768341825Sdim TreePatternNodePtr Child = Children[i]; 2769276479Sdim 2770276479Sdim if (Child->getName().empty()) 2771276479Sdim error("All arguments to a ComplexPattern must be named"); 2772276479Sdim 2773276479Sdim // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)" 2774276479Sdim // and "(MY_PAT $b, $a)" should not be allowed in the same pattern; 2775276479Sdim // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)". 2776276479Sdim auto OperandId = std::make_pair(Operator, i); 2777276479Sdim auto PrevOp = ComplexPatternOperands.find(Child->getName()); 2778276479Sdim if (PrevOp != ComplexPatternOperands.end()) { 2779276479Sdim if (PrevOp->getValue() != OperandId) 2780276479Sdim error("All ComplexPattern operands must appear consistently: " 2781276479Sdim "in the same order in just one ComplexPattern instance."); 2782276479Sdim } else 2783276479Sdim ComplexPatternOperands[Child->getName()] = OperandId; 2784276479Sdim } 2785276479Sdim } 2786276479Sdim 2787341825Sdim TreePatternNodePtr Result = 2788341825Sdim std::make_shared<TreePatternNode>(Operator, std::move(Children), 2789341825Sdim NumResults); 2790206083Srdivacky Result->setName(OpName); 2791218893Sdim 2792314564Sdim if (Dag->getName()) { 2793206083Srdivacky assert(Result->getName().empty()); 2794314564Sdim Result->setName(Dag->getNameStr()); 2795206083Srdivacky } 2796193323Sed return Result; 2797193323Sed} 2798193323Sed 2799206083Srdivacky/// SimplifyTree - See if we can simplify this tree to eliminate something that 2800206083Srdivacky/// will never match in favor of something obvious that will. This is here 2801206083Srdivacky/// strictly as a convenience to target authors because it allows them to write 2802206083Srdivacky/// more type generic things and have useless type casts fold away. 2803206083Srdivacky/// 2804206083Srdivacky/// This returns true if any change is made. 2805341825Sdimstatic bool SimplifyTree(TreePatternNodePtr &N) { 2806206083Srdivacky if (N->isLeaf()) 2807206083Srdivacky return false; 2808206083Srdivacky 2809206083Srdivacky // If we have a bitconvert with a resolved type and if the source and 2810206083Srdivacky // destination types are the same, then the bitconvert is useless, remove it. 2811206083Srdivacky if (N->getOperator()->getName() == "bitconvert" && 2812327952Sdim N->getExtType(0).isValueTypeByHwMode(false) && 2813206083Srdivacky N->getExtType(0) == N->getChild(0)->getExtType(0) && 2814206083Srdivacky N->getName().empty()) { 2815341825Sdim N = N->getChildShared(0); 2816206083Srdivacky SimplifyTree(N); 2817206083Srdivacky return true; 2818206083Srdivacky } 2819206083Srdivacky 2820206083Srdivacky // Walk all children. 2821206083Srdivacky bool MadeChange = false; 2822206083Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2823341825Sdim TreePatternNodePtr Child = N->getChildShared(i); 2824206083Srdivacky MadeChange |= SimplifyTree(Child); 2825341825Sdim N->setChild(i, std::move(Child)); 2826206083Srdivacky } 2827206083Srdivacky return MadeChange; 2828206083Srdivacky} 2829206083Srdivacky 2830206083Srdivacky 2831206083Srdivacky 2832193323Sed/// InferAllTypes - Infer/propagate as many types throughout the expression 2833193323Sed/// patterns as possible. Return true if all types are inferred, false 2834243830Sdim/// otherwise. Flags an error if a type contradiction is found. 2835205218Srdivackybool TreePattern:: 2836205218SrdivackyInferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) { 2837205218Srdivacky if (NamedNodes.empty()) 2838205218Srdivacky ComputeNamedNodes(); 2839205218Srdivacky 2840193323Sed bool MadeChange = true; 2841193323Sed while (MadeChange) { 2842193323Sed MadeChange = false; 2843341825Sdim for (TreePatternNodePtr &Tree : Trees) { 2844296417Sdim MadeChange |= Tree->ApplyTypeConstraints(*this, false); 2845296417Sdim MadeChange |= SimplifyTree(Tree); 2846206083Srdivacky } 2847205218Srdivacky 2848205218Srdivacky // If there are constraints on our named nodes, apply them. 2849296417Sdim for (auto &Entry : NamedNodes) { 2850296417Sdim SmallVectorImpl<TreePatternNode*> &Nodes = Entry.second; 2851218893Sdim 2852205218Srdivacky // If we have input named node types, propagate their types to the named 2853205218Srdivacky // values here. 2854205218Srdivacky if (InNamedTypes) { 2855296417Sdim if (!InNamedTypes->count(Entry.getKey())) { 2856296417Sdim error("Node '" + std::string(Entry.getKey()) + 2857276479Sdim "' in output pattern but not input pattern"); 2858276479Sdim return true; 2859276479Sdim } 2860205218Srdivacky 2861205218Srdivacky const SmallVectorImpl<TreePatternNode*> &InNodes = 2862296417Sdim InNamedTypes->find(Entry.getKey())->second; 2863205218Srdivacky 2864205218Srdivacky // The input types should be fully resolved by now. 2865296417Sdim for (TreePatternNode *Node : Nodes) { 2866205218Srdivacky // If this node is a register class, and it is the root of the pattern 2867205218Srdivacky // then we're mapping something onto an input register. We allow 2868205218Srdivacky // changing the type of the input register in this case. This allows 2869205218Srdivacky // us to match things like: 2870205218Srdivacky // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>; 2871341825Sdim if (Node == Trees[0].get() && Node->isLeaf()) { 2872296417Sdim DefInit *DI = dyn_cast<DefInit>(Node->getLeafValue()); 2873224145Sdim if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 2874224145Sdim DI->getDef()->isSubClassOf("RegisterOperand"))) 2875205218Srdivacky continue; 2876205218Srdivacky } 2877218893Sdim 2878296417Sdim assert(Node->getNumTypes() == 1 && 2879205407Srdivacky InNodes[0]->getNumTypes() == 1 && 2880205407Srdivacky "FIXME: cannot name multiple result nodes yet"); 2881296417Sdim MadeChange |= Node->UpdateNodeType(0, InNodes[0]->getExtType(0), 2882296417Sdim *this); 2883205218Srdivacky } 2884205218Srdivacky } 2885218893Sdim 2886205218Srdivacky // If there are multiple nodes with the same name, they must all have the 2887205218Srdivacky // same type. 2888296417Sdim if (Entry.second.size() > 1) { 2889205218Srdivacky for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) { 2890205407Srdivacky TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1]; 2891205407Srdivacky assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && 2892205407Srdivacky "FIXME: cannot name multiple result nodes yet"); 2893218893Sdim 2894205407Srdivacky MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this); 2895205407Srdivacky MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this); 2896205218Srdivacky } 2897205218Srdivacky } 2898205218Srdivacky } 2899193323Sed } 2900218893Sdim 2901193323Sed bool HasUnresolvedTypes = false; 2902341825Sdim for (const TreePatternNodePtr &Tree : Trees) 2903327952Sdim HasUnresolvedTypes |= Tree->ContainsUnresolvedType(*this); 2904193323Sed return !HasUnresolvedTypes; 2905193323Sed} 2906193323Sed 2907195340Sedvoid TreePattern::print(raw_ostream &OS) const { 2908193323Sed OS << getRecord()->getName(); 2909193323Sed if (!Args.empty()) { 2910193323Sed OS << "(" << Args[0]; 2911193323Sed for (unsigned i = 1, e = Args.size(); i != e; ++i) 2912193323Sed OS << ", " << Args[i]; 2913193323Sed OS << ")"; 2914193323Sed } 2915193323Sed OS << ": "; 2916218893Sdim 2917193323Sed if (Trees.size() > 1) 2918193323Sed OS << "[\n"; 2919341825Sdim for (const TreePatternNodePtr &Tree : Trees) { 2920193323Sed OS << "\t"; 2921296417Sdim Tree->print(OS); 2922193323Sed OS << "\n"; 2923193323Sed } 2924193323Sed 2925193323Sed if (Trees.size() > 1) 2926193323Sed OS << "]\n"; 2927193323Sed} 2928193323Sed 2929195340Sedvoid TreePattern::dump() const { print(errs()); } 2930193323Sed 2931193323Sed//===----------------------------------------------------------------------===// 2932193323Sed// CodeGenDAGPatterns implementation 2933193323Sed// 2934193323Sed 2935327952SdimCodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R, 2936327952Sdim PatternRewriterFn PatternRewriter) 2937327952Sdim : Records(R), Target(R), LegalVTS(Target.getLegalValueTypes()), 2938327952Sdim PatternRewriter(PatternRewriter) { 2939218893Sdim 2940309124Sdim Intrinsics = CodeGenIntrinsicTable(Records, false); 2941309124Sdim TgtIntrinsics = CodeGenIntrinsicTable(Records, true); 2942193323Sed ParseNodeInfo(); 2943193323Sed ParseNodeTransforms(); 2944193323Sed ParseComplexPatterns(); 2945193323Sed ParsePatternFragments(); 2946193323Sed ParseDefaultOperands(); 2947193323Sed ParseInstructions(); 2948276479Sdim ParsePatternFragments(/*OutFrags*/true); 2949193323Sed ParsePatterns(); 2950218893Sdim 2951327952Sdim // Break patterns with parameterized types into a series of patterns, 2952327952Sdim // where each one has a fixed type and is predicated on the conditions 2953327952Sdim // of the associated HW mode. 2954327952Sdim ExpandHwModeBasedTypes(); 2955327952Sdim 2956193323Sed // Generate variants. For example, commutative patterns can match 2957193323Sed // multiple ways. Add them to PatternsToMatch as well. 2958193323Sed GenerateVariants(); 2959193323Sed 2960193323Sed // Infer instruction flags. For example, we can detect loads, 2961193323Sed // stores, and side effects in many cases by examining an 2962193323Sed // instruction's pattern. 2963193323Sed InferInstructionFlags(); 2964243830Sdim 2965243830Sdim // Verify that instruction flags match the patterns. 2966243830Sdim VerifyInstructionFlags(); 2967193323Sed} 2968193323Sed 2969193323SedRecord *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 2970193323Sed Record *N = Records.getDef(Name); 2971288943Sdim if (!N || !N->isSubClassOf("SDNode")) 2972288943Sdim PrintFatalError("Error getting SDNode '" + Name + "'!"); 2973288943Sdim 2974193323Sed return N; 2975193323Sed} 2976193323Sed 2977193323Sed// Parse all of the SDNode definitions for the target, populating SDNodes. 2978193323Sedvoid CodeGenDAGPatterns::ParseNodeInfo() { 2979193323Sed std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 2980327952Sdim const CodeGenHwModes &CGH = getTargetInfo().getHwModes(); 2981327952Sdim 2982193323Sed while (!Nodes.empty()) { 2983327952Sdim Record *R = Nodes.back(); 2984327952Sdim SDNodes.insert(std::make_pair(R, SDNodeInfo(R, CGH))); 2985193323Sed Nodes.pop_back(); 2986193323Sed } 2987193323Sed 2988193323Sed // Get the builtin intrinsic nodes. 2989193323Sed intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 2990193323Sed intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 2991193323Sed intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 2992193323Sed} 2993193323Sed 2994193323Sed/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 2995193323Sed/// map, and emit them to the file as functions. 2996193323Sedvoid CodeGenDAGPatterns::ParseNodeTransforms() { 2997193323Sed std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 2998193323Sed while (!Xforms.empty()) { 2999193323Sed Record *XFormNode = Xforms.back(); 3000193323Sed Record *SDNode = XFormNode->getValueAsDef("Opcode"); 3001321369Sdim StringRef Code = XFormNode->getValueAsString("XFormFunction"); 3002193323Sed SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 3003193323Sed 3004193323Sed Xforms.pop_back(); 3005193323Sed } 3006193323Sed} 3007193323Sed 3008193323Sedvoid CodeGenDAGPatterns::ParseComplexPatterns() { 3009193323Sed std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 3010193323Sed while (!AMs.empty()) { 3011193323Sed ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 3012193323Sed AMs.pop_back(); 3013193323Sed } 3014193323Sed} 3015193323Sed 3016193323Sed 3017193323Sed/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 3018193323Sed/// file, building up the PatternFragments map. After we've collected them all, 3019193323Sed/// inline fragments together as necessary, so that there are no references left 3020193323Sed/// inside a pattern fragment to a pattern fragment. 3021193323Sed/// 3022276479Sdimvoid CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { 3023341825Sdim std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrags"); 3024218893Sdim 3025193323Sed // First step, parse all of the fragments. 3026296417Sdim for (Record *Frag : Fragments) { 3027296417Sdim if (OutFrags != Frag->isSubClassOf("OutPatFrag")) 3028276479Sdim continue; 3029276479Sdim 3030341825Sdim ListInit *LI = Frag->getValueAsListInit("Fragments"); 3031276479Sdim TreePattern *P = 3032296417Sdim (PatternFragments[Frag] = llvm::make_unique<TreePattern>( 3033341825Sdim Frag, LI, !Frag->isSubClassOf("OutPatFrag"), 3034280031Sdim *this)).get(); 3035218893Sdim 3036193323Sed // Validate the argument list, converting it to set, to discard duplicates. 3037193323Sed std::vector<std::string> &Args = P->getArgList(); 3038327952Sdim // Copy the args so we can take StringRefs to them. 3039327952Sdim auto ArgsCopy = Args; 3040327952Sdim SmallDenseSet<StringRef, 4> OperandsSet; 3041327952Sdim OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end()); 3042218893Sdim 3043193323Sed if (OperandsSet.count("")) 3044193323Sed P->error("Cannot have unnamed 'node' values in pattern fragment!"); 3045218893Sdim 3046193323Sed // Parse the operands list. 3047296417Sdim DagInit *OpsList = Frag->getValueAsDag("Operands"); 3048243830Sdim DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator()); 3049193323Sed // Special cases: ops == outs == ins. Different names are used to 3050193323Sed // improve readability. 3051193323Sed if (!OpsOp || 3052193323Sed (OpsOp->getDef()->getName() != "ops" && 3053193323Sed OpsOp->getDef()->getName() != "outs" && 3054193323Sed OpsOp->getDef()->getName() != "ins")) 3055193323Sed P->error("Operands list should start with '(ops ... '!"); 3056218893Sdim 3057218893Sdim // Copy over the arguments. 3058193323Sed Args.clear(); 3059193323Sed for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 3060243830Sdim if (!isa<DefInit>(OpsList->getArg(j)) || 3061243830Sdim cast<DefInit>(OpsList->getArg(j))->getDef()->getName() != "node") 3062193323Sed P->error("Operands list should all be 'node' values."); 3063314564Sdim if (!OpsList->getArgName(j)) 3064193323Sed P->error("Operands list should have names for each operand!"); 3065314564Sdim StringRef ArgNameStr = OpsList->getArgNameStr(j); 3066314564Sdim if (!OperandsSet.count(ArgNameStr)) 3067314564Sdim P->error("'" + ArgNameStr + 3068193323Sed "' does not occur in pattern or was multiply specified!"); 3069314564Sdim OperandsSet.erase(ArgNameStr); 3070314564Sdim Args.push_back(ArgNameStr); 3071193323Sed } 3072218893Sdim 3073193323Sed if (!OperandsSet.empty()) 3074193323Sed P->error("Operands list does not contain an entry for operand '" + 3075193323Sed *OperandsSet.begin() + "'!"); 3076193323Sed 3077193323Sed // If there is a node transformation corresponding to this, keep track of 3078193323Sed // it. 3079296417Sdim Record *Transform = Frag->getValueAsDef("OperandTransform"); 3080193323Sed if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 3081341825Sdim for (auto T : P->getTrees()) 3082341825Sdim T->setTransformFn(Transform); 3083193323Sed } 3084218893Sdim 3085193323Sed // Now that we've parsed all of the tree fragments, do a closure on them so 3086193323Sed // that there are not references to PatFrags left inside of them. 3087296417Sdim for (Record *Frag : Fragments) { 3088296417Sdim if (OutFrags != Frag->isSubClassOf("OutPatFrag")) 3089276479Sdim continue; 3090276479Sdim 3091296417Sdim TreePattern &ThePat = *PatternFragments[Frag]; 3092280031Sdim ThePat.InlinePatternFragments(); 3093218893Sdim 3094193323Sed // Infer as many types as possible. Don't worry about it if we don't infer 3095341825Sdim // all of them, some may depend on the inputs of the pattern. Also, don't 3096341825Sdim // validate type sets; validation may cause spurious failures e.g. if a 3097341825Sdim // fragment needs floating-point types but the current target does not have 3098341825Sdim // any (this is only an error if that fragment is ever used!). 3099341825Sdim { 3100341825Sdim TypeInfer::SuppressValidation SV(ThePat.getInfer()); 3101341825Sdim ThePat.InferAllTypes(); 3102341825Sdim ThePat.resetError(); 3103341825Sdim } 3104218893Sdim 3105193323Sed // If debugging, print out the pattern fragment result. 3106341825Sdim LLVM_DEBUG(ThePat.dump()); 3107193323Sed } 3108193323Sed} 3109193323Sed 3110193323Sedvoid CodeGenDAGPatterns::ParseDefaultOperands() { 3111243830Sdim std::vector<Record*> DefaultOps; 3112243830Sdim DefaultOps = Records.getAllDerivedDefinitions("OperandWithDefaultOps"); 3113193323Sed 3114193323Sed // Find some SDNode. 3115193323Sed assert(!SDNodes.empty() && "No SDNodes parsed?"); 3116226633Sdim Init *SomeSDNode = DefInit::get(SDNodes.begin()->first); 3117218893Sdim 3118243830Sdim for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) { 3119243830Sdim DagInit *DefaultInfo = DefaultOps[i]->getValueAsDag("DefaultOps"); 3120218893Sdim 3121243830Sdim // Clone the DefaultInfo dag node, changing the operator from 'ops' to 3122243830Sdim // SomeSDnode so that we can parse this. 3123314564Sdim std::vector<std::pair<Init*, StringInit*> > Ops; 3124243830Sdim for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 3125243830Sdim Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 3126243830Sdim DefaultInfo->getArgName(op))); 3127314564Sdim DagInit *DI = DagInit::get(SomeSDNode, nullptr, Ops); 3128218893Sdim 3129243830Sdim // Create a TreePattern to parse this. 3130243830Sdim TreePattern P(DefaultOps[i], DI, false, *this); 3131243830Sdim assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 3132193323Sed 3133243830Sdim // Copy the operands over into a DAGDefaultOperand. 3134243830Sdim DAGDefaultOperand DefaultOpInfo; 3135218893Sdim 3136341825Sdim const TreePatternNodePtr &T = P.getTree(0); 3137243830Sdim for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 3138341825Sdim TreePatternNodePtr TPN = T->getChildShared(op); 3139243830Sdim while (TPN->ApplyTypeConstraints(P, false)) 3140243830Sdim /* Resolve all types */; 3141218893Sdim 3142327952Sdim if (TPN->ContainsUnresolvedType(P)) { 3143276479Sdim PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" + 3144276479Sdim DefaultOps[i]->getName() + 3145276479Sdim "' doesn't have a concrete type!"); 3146193323Sed } 3147341825Sdim DefaultOpInfo.DefaultOps.push_back(std::move(TPN)); 3148243830Sdim } 3149193323Sed 3150243830Sdim // Insert it into the DefaultOperands map so we can find it later. 3151243830Sdim DefaultOperands[DefaultOps[i]] = DefaultOpInfo; 3152193323Sed } 3153193323Sed} 3154193323Sed 3155193323Sed/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 3156193323Sed/// instruction input. Return true if this is a real use. 3157341825Sdimstatic bool HandleUse(TreePattern &I, TreePatternNodePtr Pat, 3158341825Sdim std::map<std::string, TreePatternNodePtr> &InstInputs) { 3159193323Sed // No name -> not interesting. 3160193323Sed if (Pat->getName().empty()) { 3161193323Sed if (Pat->isLeaf()) { 3162243830Sdim DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue()); 3163224145Sdim if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 3164224145Sdim DI->getDef()->isSubClassOf("RegisterOperand"))) 3165341825Sdim I.error("Input " + DI->getDef()->getName() + " must be named!"); 3166193323Sed } 3167193323Sed return false; 3168193323Sed } 3169193323Sed 3170193323Sed Record *Rec; 3171193323Sed if (Pat->isLeaf()) { 3172243830Sdim DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue()); 3173341825Sdim if (!DI) 3174341825Sdim I.error("Input $" + Pat->getName() + " must be an identifier!"); 3175193323Sed Rec = DI->getDef(); 3176193323Sed } else { 3177193323Sed Rec = Pat->getOperator(); 3178193323Sed } 3179193323Sed 3180193323Sed // SRCVALUE nodes are ignored. 3181193323Sed if (Rec->getName() == "srcvalue") 3182193323Sed return false; 3183193323Sed 3184341825Sdim TreePatternNodePtr &Slot = InstInputs[Pat->getName()]; 3185193323Sed if (!Slot) { 3186193323Sed Slot = Pat; 3187204642Srdivacky return true; 3188204642Srdivacky } 3189204642Srdivacky Record *SlotRec; 3190204642Srdivacky if (Slot->isLeaf()) { 3191243830Sdim SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef(); 3192193323Sed } else { 3193204642Srdivacky assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 3194204642Srdivacky SlotRec = Slot->getOperator(); 3195193323Sed } 3196218893Sdim 3197204642Srdivacky // Ensure that the inputs agree if we've already seen this input. 3198204642Srdivacky if (Rec != SlotRec) 3199341825Sdim I.error("All $" + Pat->getName() + " inputs must agree with each other"); 3200341825Sdim // Ensure that the types can agree as well. 3201341825Sdim Slot->UpdateNodeType(0, Pat->getExtType(0), I); 3202341825Sdim Pat->UpdateNodeType(0, Slot->getExtType(0), I); 3203205407Srdivacky if (Slot->getExtTypes() != Pat->getExtTypes()) 3204341825Sdim I.error("All $" + Pat->getName() + " inputs must agree with each other"); 3205193323Sed return true; 3206193323Sed} 3207193323Sed 3208193323Sed/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 3209193323Sed/// part of "I", the instruction), computing the set of inputs and outputs of 3210193323Sed/// the pattern. Report errors if we see anything naughty. 3211341825Sdimvoid CodeGenDAGPatterns::FindPatternInputsAndOutputs( 3212341825Sdim TreePattern &I, TreePatternNodePtr Pat, 3213341825Sdim std::map<std::string, TreePatternNodePtr> &InstInputs, 3214344779Sdim MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>> 3215344779Sdim &InstResults, 3216341825Sdim std::vector<Record *> &InstImpResults) { 3217341825Sdim 3218341825Sdim // The instruction pattern still has unresolved fragments. For *named* 3219341825Sdim // nodes we must resolve those here. This may not result in multiple 3220341825Sdim // alternatives. 3221341825Sdim if (!Pat->getName().empty()) { 3222341825Sdim TreePattern SrcPattern(I.getRecord(), Pat, true, *this); 3223341825Sdim SrcPattern.InlinePatternFragments(); 3224341825Sdim SrcPattern.InferAllTypes(); 3225341825Sdim Pat = SrcPattern.getOnlyTree(); 3226341825Sdim } 3227341825Sdim 3228193323Sed if (Pat->isLeaf()) { 3229207618Srdivacky bool isUse = HandleUse(I, Pat, InstInputs); 3230193323Sed if (!isUse && Pat->getTransformFn()) 3231341825Sdim I.error("Cannot specify a transform function for a non-input value!"); 3232193323Sed return; 3233204642Srdivacky } 3234218893Sdim 3235204642Srdivacky if (Pat->getOperator()->getName() == "implicit") { 3236193323Sed for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 3237193323Sed TreePatternNode *Dest = Pat->getChild(i); 3238193323Sed if (!Dest->isLeaf()) 3239341825Sdim I.error("implicitly defined value should be a register!"); 3240218893Sdim 3241243830Sdim DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue()); 3242193323Sed if (!Val || !Val->getDef()->isSubClassOf("Register")) 3243341825Sdim I.error("implicitly defined value should be a register!"); 3244193323Sed InstImpResults.push_back(Val->getDef()); 3245193323Sed } 3246193323Sed return; 3247204642Srdivacky } 3248218893Sdim 3249204642Srdivacky if (Pat->getOperator()->getName() != "set") { 3250193323Sed // If this is not a set, verify that the children nodes are not void typed, 3251193323Sed // and recurse. 3252193323Sed for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 3253205407Srdivacky if (Pat->getChild(i)->getNumTypes() == 0) 3254341825Sdim I.error("Cannot have void nodes inside of patterns!"); 3255341825Sdim FindPatternInputsAndOutputs(I, Pat->getChildShared(i), InstInputs, 3256341825Sdim InstResults, InstImpResults); 3257193323Sed } 3258218893Sdim 3259193323Sed // If this is a non-leaf node with no children, treat it basically as if 3260193323Sed // it were a leaf. This handles nodes like (imm). 3261207618Srdivacky bool isUse = HandleUse(I, Pat, InstInputs); 3262218893Sdim 3263193323Sed if (!isUse && Pat->getTransformFn()) 3264341825Sdim I.error("Cannot specify a transform function for a non-input value!"); 3265193323Sed return; 3266204642Srdivacky } 3267218893Sdim 3268193323Sed // Otherwise, this is a set, validate and collect instruction results. 3269193323Sed if (Pat->getNumChildren() == 0) 3270341825Sdim I.error("set requires operands!"); 3271218893Sdim 3272193323Sed if (Pat->getTransformFn()) 3273341825Sdim I.error("Cannot specify a transform function on a set node!"); 3274218893Sdim 3275193323Sed // Check the set destinations. 3276193323Sed unsigned NumDests = Pat->getNumChildren()-1; 3277193323Sed for (unsigned i = 0; i != NumDests; ++i) { 3278341825Sdim TreePatternNodePtr Dest = Pat->getChildShared(i); 3279341825Sdim // For set destinations we also must resolve fragments here. 3280341825Sdim TreePattern DestPattern(I.getRecord(), Dest, false, *this); 3281341825Sdim DestPattern.InlinePatternFragments(); 3282341825Sdim DestPattern.InferAllTypes(); 3283341825Sdim Dest = DestPattern.getOnlyTree(); 3284341825Sdim 3285193323Sed if (!Dest->isLeaf()) 3286341825Sdim I.error("set destination should be a register!"); 3287218893Sdim 3288243830Sdim DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue()); 3289280031Sdim if (!Val) { 3290341825Sdim I.error("set destination should be a register!"); 3291280031Sdim continue; 3292280031Sdim } 3293193323Sed 3294193323Sed if (Val->getDef()->isSubClassOf("RegisterClass") || 3295249423Sdim Val->getDef()->isSubClassOf("ValueType") || 3296224145Sdim Val->getDef()->isSubClassOf("RegisterOperand") || 3297198090Srdivacky Val->getDef()->isSubClassOf("PointerLikeRegClass")) { 3298193323Sed if (Dest->getName().empty()) 3299341825Sdim I.error("set destination must have a name!"); 3300193323Sed if (InstResults.count(Dest->getName())) 3301341825Sdim I.error("cannot set '" + Dest->getName() + "' multiple times"); 3302193323Sed InstResults[Dest->getName()] = Dest; 3303193323Sed } else if (Val->getDef()->isSubClassOf("Register")) { 3304193323Sed InstImpResults.push_back(Val->getDef()); 3305193323Sed } else { 3306341825Sdim I.error("set destination should be a register!"); 3307193323Sed } 3308193323Sed } 3309218893Sdim 3310193323Sed // Verify and collect info from the computation. 3311341825Sdim FindPatternInputsAndOutputs(I, Pat->getChildShared(NumDests), InstInputs, 3312341825Sdim InstResults, InstImpResults); 3313193323Sed} 3314193323Sed 3315193323Sed//===----------------------------------------------------------------------===// 3316193323Sed// Instruction Analysis 3317193323Sed//===----------------------------------------------------------------------===// 3318193323Sed 3319193323Sedclass InstAnalyzer { 3320193323Sed const CodeGenDAGPatterns &CDP; 3321193323Sedpublic: 3322243830Sdim bool hasSideEffects; 3323243830Sdim bool mayStore; 3324243830Sdim bool mayLoad; 3325243830Sdim bool isBitcast; 3326243830Sdim bool isVariadic; 3327341825Sdim bool hasChain; 3328193323Sed 3329243830Sdim InstAnalyzer(const CodeGenDAGPatterns &cdp) 3330243830Sdim : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false), 3331341825Sdim isBitcast(false), isVariadic(false), hasChain(false) {} 3332193323Sed 3333321369Sdim void Analyze(const PatternToMatch &Pat) { 3334341825Sdim const TreePatternNode *N = Pat.getSrcPattern(); 3335341825Sdim AnalyzeNode(N); 3336341825Sdim // These properties are detected only on the root node. 3337341825Sdim isBitcast = IsNodeBitcast(N); 3338243830Sdim } 3339243830Sdim 3340193323Sedprivate: 3341221345Sdim bool IsNodeBitcast(const TreePatternNode *N) const { 3342243830Sdim if (hasSideEffects || mayLoad || mayStore || isVariadic) 3343221345Sdim return false; 3344221345Sdim 3345341825Sdim if (N->isLeaf()) 3346221345Sdim return false; 3347341825Sdim if (N->getNumChildren() != 1 || !N->getChild(0)->isLeaf()) 3348221345Sdim return false; 3349221345Sdim 3350341825Sdim const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); 3351221345Sdim if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1) 3352221345Sdim return false; 3353221345Sdim return OpInfo.getEnumName() == "ISD::BITCAST"; 3354221345Sdim } 3355221345Sdim 3356243830Sdimpublic: 3357193323Sed void AnalyzeNode(const TreePatternNode *N) { 3358193323Sed if (N->isLeaf()) { 3359243830Sdim if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) { 3360193323Sed Record *LeafRec = DI->getDef(); 3361193323Sed // Handle ComplexPattern leaves. 3362193323Sed if (LeafRec->isSubClassOf("ComplexPattern")) { 3363193323Sed const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 3364193323Sed if (CP.hasProperty(SDNPMayStore)) mayStore = true; 3365193323Sed if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 3366243830Sdim if (CP.hasProperty(SDNPSideEffect)) hasSideEffects = true; 3367193323Sed } 3368193323Sed } 3369193323Sed return; 3370193323Sed } 3371193323Sed 3372193323Sed // Analyze children. 3373193323Sed for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 3374193323Sed AnalyzeNode(N->getChild(i)); 3375193323Sed 3376193323Sed // Notice properties of the node. 3377276479Sdim if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true; 3378276479Sdim if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true; 3379276479Sdim if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true; 3380276479Sdim if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true; 3381341825Sdim if (N->NodeHasProperty(SDNPHasChain, CDP)) hasChain = true; 3382193323Sed 3383193323Sed if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 3384193323Sed // If this is an intrinsic, analyze it. 3385309124Sdim if (IntInfo->ModRef & CodeGenIntrinsic::MR_Ref) 3386193323Sed mayLoad = true;// These may load memory. 3387193323Sed 3388309124Sdim if (IntInfo->ModRef & CodeGenIntrinsic::MR_Mod) 3389193323Sed mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 3390193323Sed 3391321369Sdim if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem || 3392321369Sdim IntInfo->hasSideEffects) 3393309124Sdim // ReadWriteMem intrinsics can have other strange effects. 3394243830Sdim hasSideEffects = true; 3395193323Sed } 3396193323Sed } 3397193323Sed 3398193323Sed}; 3399193323Sed 3400243830Sdimstatic bool InferFromPattern(CodeGenInstruction &InstInfo, 3401243830Sdim const InstAnalyzer &PatInfo, 3402243830Sdim Record *PatDef) { 3403243830Sdim bool Error = false; 3404193323Sed 3405243830Sdim // Remember where InstInfo got its flags. 3406243830Sdim if (InstInfo.hasUndefFlags()) 3407243830Sdim InstInfo.InferredFrom = PatDef; 3408193323Sed 3409243830Sdim // Check explicitly set flags for consistency. 3410243830Sdim if (InstInfo.hasSideEffects != PatInfo.hasSideEffects && 3411243830Sdim !InstInfo.hasSideEffects_Unset) { 3412243830Sdim // Allow explicitly setting hasSideEffects = 1 on instructions, even when 3413243830Sdim // the pattern has no side effects. That could be useful for div/rem 3414243830Sdim // instructions that may trap. 3415243830Sdim if (!InstInfo.hasSideEffects) { 3416243830Sdim Error = true; 3417243830Sdim PrintError(PatDef->getLoc(), "Pattern doesn't match hasSideEffects = " + 3418243830Sdim Twine(InstInfo.hasSideEffects)); 3419243830Sdim } 3420193323Sed } 3421193323Sed 3422243830Sdim if (InstInfo.mayStore != PatInfo.mayStore && !InstInfo.mayStore_Unset) { 3423243830Sdim Error = true; 3424243830Sdim PrintError(PatDef->getLoc(), "Pattern doesn't match mayStore = " + 3425243830Sdim Twine(InstInfo.mayStore)); 3426193323Sed } 3427193323Sed 3428243830Sdim if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) { 3429243830Sdim // Allow explicitly setting mayLoad = 1, even when the pattern has no loads. 3430296417Sdim // Some targets translate immediates to loads. 3431243830Sdim if (!InstInfo.mayLoad) { 3432243830Sdim Error = true; 3433243830Sdim PrintError(PatDef->getLoc(), "Pattern doesn't match mayLoad = " + 3434243830Sdim Twine(InstInfo.mayLoad)); 3435243830Sdim } 3436193323Sed } 3437193323Sed 3438243830Sdim // Transfer inferred flags. 3439243830Sdim InstInfo.hasSideEffects |= PatInfo.hasSideEffects; 3440243830Sdim InstInfo.mayStore |= PatInfo.mayStore; 3441243830Sdim InstInfo.mayLoad |= PatInfo.mayLoad; 3442218893Sdim 3443243830Sdim // These flags are silently added without any verification. 3444341825Sdim // FIXME: To match historical behavior of TableGen, for now add those flags 3445341825Sdim // only when we're inferring from the primary instruction pattern. 3446341825Sdim if (PatDef->isSubClassOf("Instruction")) { 3447341825Sdim InstInfo.isBitcast |= PatInfo.isBitcast; 3448341825Sdim InstInfo.hasChain |= PatInfo.hasChain; 3449341825Sdim InstInfo.hasChain_Inferred = true; 3450341825Sdim } 3451243830Sdim 3452243830Sdim // Don't infer isVariadic. This flag means something different on SDNodes and 3453243830Sdim // instructions. For example, a CALL SDNode is variadic because it has the 3454243830Sdim // call arguments as operands, but a CALL instruction is not variadic - it 3455243830Sdim // has argument registers as implicit, not explicit uses. 3456243830Sdim 3457243830Sdim return Error; 3458193323Sed} 3459193323Sed 3460239462Sdim/// hasNullFragReference - Return true if the DAG has any reference to the 3461239462Sdim/// null_frag operator. 3462239462Sdimstatic bool hasNullFragReference(DagInit *DI) { 3463243830Sdim DefInit *OpDef = dyn_cast<DefInit>(DI->getOperator()); 3464239462Sdim if (!OpDef) return false; 3465239462Sdim Record *Operator = OpDef->getDef(); 3466239462Sdim 3467239462Sdim // If this is the null fragment, return true. 3468239462Sdim if (Operator->getName() == "null_frag") return true; 3469239462Sdim // If any of the arguments reference the null fragment, return true. 3470239462Sdim for (unsigned i = 0, e = DI->getNumArgs(); i != e; ++i) { 3471243830Sdim DagInit *Arg = dyn_cast<DagInit>(DI->getArg(i)); 3472239462Sdim if (Arg && hasNullFragReference(Arg)) 3473239462Sdim return true; 3474239462Sdim } 3475239462Sdim 3476239462Sdim return false; 3477239462Sdim} 3478239462Sdim 3479239462Sdim/// hasNullFragReference - Return true if any DAG in the list references 3480239462Sdim/// the null_frag operator. 3481239462Sdimstatic bool hasNullFragReference(ListInit *LI) { 3482288943Sdim for (Init *I : LI->getValues()) { 3483288943Sdim DagInit *DI = dyn_cast<DagInit>(I); 3484239462Sdim assert(DI && "non-dag in an instruction Pattern list?!"); 3485239462Sdim if (hasNullFragReference(DI)) 3486239462Sdim return true; 3487239462Sdim } 3488239462Sdim return false; 3489239462Sdim} 3490239462Sdim 3491243830Sdim/// Get all the instructions in a tree. 3492243830Sdimstatic void 3493243830SdimgetInstructionsInTree(TreePatternNode *Tree, SmallVectorImpl<Record*> &Instrs) { 3494243830Sdim if (Tree->isLeaf()) 3495243830Sdim return; 3496243830Sdim if (Tree->getOperator()->isSubClassOf("Instruction")) 3497243830Sdim Instrs.push_back(Tree->getOperator()); 3498243830Sdim for (unsigned i = 0, e = Tree->getNumChildren(); i != e; ++i) 3499243830Sdim getInstructionsInTree(Tree->getChild(i), Instrs); 3500243830Sdim} 3501243830Sdim 3502249423Sdim/// Check the class of a pattern leaf node against the instruction operand it 3503249423Sdim/// represents. 3504249423Sdimstatic bool checkOperandClass(CGIOperandList::OperandInfo &OI, 3505249423Sdim Record *Leaf) { 3506249423Sdim if (OI.Rec == Leaf) 3507249423Sdim return true; 3508249423Sdim 3509249423Sdim // Allow direct value types to be used in instruction set patterns. 3510249423Sdim // The type will be checked later. 3511249423Sdim if (Leaf->isSubClassOf("ValueType")) 3512249423Sdim return true; 3513249423Sdim 3514249423Sdim // Patterns can also be ComplexPattern instances. 3515249423Sdim if (Leaf->isSubClassOf("ComplexPattern")) 3516249423Sdim return true; 3517249423Sdim 3518249423Sdim return false; 3519249423Sdim} 3520249423Sdim 3521341825Sdimvoid CodeGenDAGPatterns::parseInstructionPattern( 3522261991Sdim CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) { 3523218893Sdim 3524288943Sdim assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"); 3525218893Sdim 3526288943Sdim // Parse the instruction. 3527341825Sdim TreePattern I(CGI.TheDef, Pat, true, *this); 3528218893Sdim 3529288943Sdim // InstInputs - Keep track of all of the inputs of the instruction, along 3530288943Sdim // with the record they are declared as. 3531341825Sdim std::map<std::string, TreePatternNodePtr> InstInputs; 3532218893Sdim 3533288943Sdim // InstResults - Keep track of all the virtual registers that are 'set' 3534288943Sdim // in the instruction, including what reg class they are. 3535344779Sdim MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>> 3536344779Sdim InstResults; 3537193323Sed 3538288943Sdim std::vector<Record*> InstImpResults; 3539218893Sdim 3540288943Sdim // Verify that the top-level forms in the instruction are of void type, and 3541288943Sdim // fill in the InstResults map. 3542327952Sdim SmallString<32> TypesString; 3543341825Sdim for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) { 3544327952Sdim TypesString.clear(); 3545341825Sdim TreePatternNodePtr Pat = I.getTree(j); 3546309124Sdim if (Pat->getNumTypes() != 0) { 3547327952Sdim raw_svector_ostream OS(TypesString); 3548309124Sdim for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) { 3549309124Sdim if (k > 0) 3550327952Sdim OS << ", "; 3551327952Sdim Pat->getExtType(k).writeToStream(OS); 3552309124Sdim } 3553341825Sdim I.error("Top-level forms in instruction pattern should have" 3554327952Sdim " void types, has types " + 3555327952Sdim OS.str()); 3556309124Sdim } 3557193323Sed 3558288943Sdim // Find inputs and outputs, and verify the structure of the uses/defs. 3559288943Sdim FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 3560288943Sdim InstImpResults); 3561288943Sdim } 3562193323Sed 3563288943Sdim // Now that we have inputs and outputs of the pattern, inspect the operands 3564288943Sdim // list for the instruction. This determines the order that operands are 3565288943Sdim // added to the machine instruction the node corresponds to. 3566288943Sdim unsigned NumResults = InstResults.size(); 3567193323Sed 3568288943Sdim // Parse the operands list from the (ops) list, validating it. 3569341825Sdim assert(I.getArgList().empty() && "Args list should still be empty here!"); 3570193323Sed 3571288943Sdim // Check that all of the results occur first in the list. 3572288943Sdim std::vector<Record*> Results; 3573344779Sdim std::vector<unsigned> ResultIndices; 3574341825Sdim SmallVector<TreePatternNodePtr, 2> ResNodes; 3575288943Sdim for (unsigned i = 0; i != NumResults; ++i) { 3576344779Sdim if (i == CGI.Operands.size()) { 3577344779Sdim const std::string &OpName = 3578344779Sdim std::find_if(InstResults.begin(), InstResults.end(), 3579344779Sdim [](const std::pair<std::string, TreePatternNodePtr> &P) { 3580344779Sdim return P.second; 3581344779Sdim }) 3582344779Sdim ->first; 3583344779Sdim 3584344779Sdim I.error("'" + OpName + "' set but does not appear in operand list!"); 3585344779Sdim } 3586344779Sdim 3587288943Sdim const std::string &OpName = CGI.Operands[i].Name; 3588218893Sdim 3589288943Sdim // Check that it exists in InstResults. 3590344779Sdim auto InstResultIter = InstResults.find(OpName); 3591344779Sdim if (InstResultIter == InstResults.end() || !InstResultIter->second) 3592341825Sdim I.error("Operand $" + OpName + " does not exist in operand list!"); 3593218893Sdim 3594344779Sdim TreePatternNodePtr RNode = InstResultIter->second; 3595288943Sdim Record *R = cast<DefInit>(RNode->getLeafValue())->getDef(); 3596341825Sdim ResNodes.push_back(std::move(RNode)); 3597288943Sdim if (!R) 3598341825Sdim I.error("Operand $" + OpName + " should be a set destination: all " 3599288943Sdim "outputs must occur before inputs in operand list!"); 3600218893Sdim 3601288943Sdim if (!checkOperandClass(CGI.Operands[i], R)) 3602341825Sdim I.error("Operand $" + OpName + " class mismatch!"); 3603218893Sdim 3604288943Sdim // Remember the return type. 3605288943Sdim Results.push_back(CGI.Operands[i].Rec); 3606193323Sed 3607344779Sdim // Remember the result index. 3608344779Sdim ResultIndices.push_back(std::distance(InstResults.begin(), InstResultIter)); 3609344779Sdim 3610288943Sdim // Okay, this one checks out. 3611344779Sdim InstResultIter->second = nullptr; 3612288943Sdim } 3613193323Sed 3614341825Sdim // Loop over the inputs next. 3615341825Sdim std::vector<TreePatternNodePtr> ResultNodeOperands; 3616288943Sdim std::vector<Record*> Operands; 3617288943Sdim for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) { 3618288943Sdim CGIOperandList::OperandInfo &Op = CGI.Operands[i]; 3619288943Sdim const std::string &OpName = Op.Name; 3620288943Sdim if (OpName.empty()) 3621341825Sdim I.error("Operand #" + Twine(i) + " in operands list has no name!"); 3622218893Sdim 3623341825Sdim if (!InstInputs.count(OpName)) { 3624288943Sdim // If this is an operand with a DefaultOps set filled in, we can ignore 3625288943Sdim // this. When we codegen it, we will do so as always executed. 3626288943Sdim if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) { 3627288943Sdim // Does it have a non-empty DefaultOps field? If so, ignore this 3628288943Sdim // operand. 3629288943Sdim if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 3630288943Sdim continue; 3631193323Sed } 3632341825Sdim I.error("Operand $" + OpName + 3633288943Sdim " does not appear in the instruction pattern"); 3634288943Sdim } 3635341825Sdim TreePatternNodePtr InVal = InstInputs[OpName]; 3636341825Sdim InstInputs.erase(OpName); // It occurred, remove from map. 3637218893Sdim 3638288943Sdim if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) { 3639288943Sdim Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 3640288943Sdim if (!checkOperandClass(Op, InRec)) 3641341825Sdim I.error("Operand $" + OpName + "'s register class disagrees" 3642288943Sdim " between the operand and pattern"); 3643288943Sdim } 3644288943Sdim Operands.push_back(Op.Rec); 3645218893Sdim 3646288943Sdim // Construct the result for the dest-pattern operand list. 3647341825Sdim TreePatternNodePtr OpNode = InVal->clone(); 3648218893Sdim 3649288943Sdim // No predicate is useful on the result. 3650344779Sdim OpNode->clearPredicateCalls(); 3651218893Sdim 3652288943Sdim // Promote the xform function to be an explicit node if set. 3653288943Sdim if (Record *Xform = OpNode->getTransformFn()) { 3654288943Sdim OpNode->setTransformFn(nullptr); 3655341825Sdim std::vector<TreePatternNodePtr> Children; 3656288943Sdim Children.push_back(OpNode); 3657341825Sdim OpNode = std::make_shared<TreePatternNode>(Xform, std::move(Children), 3658341825Sdim OpNode->getNumTypes()); 3659193323Sed } 3660218893Sdim 3661341825Sdim ResultNodeOperands.push_back(std::move(OpNode)); 3662288943Sdim } 3663193323Sed 3664341825Sdim if (!InstInputs.empty()) 3665341825Sdim I.error("Input operand $" + InstInputs.begin()->first + 3666341825Sdim " occurs in pattern but not in operands list!"); 3667193323Sed 3668341825Sdim TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>( 3669341825Sdim I.getRecord(), std::move(ResultNodeOperands), 3670341825Sdim GetNumNodeResults(I.getRecord(), *this)); 3671288943Sdim // Copy fully inferred output node types to instruction result pattern. 3672288943Sdim for (unsigned i = 0; i != NumResults; ++i) { 3673288943Sdim assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"); 3674288943Sdim ResultPattern->setType(i, ResNodes[i]->getExtType(0)); 3675344779Sdim ResultPattern->setResultIndex(i, ResultIndices[i]); 3676288943Sdim } 3677193323Sed 3678341825Sdim // FIXME: Assume only the first tree is the pattern. The others are clobber 3679341825Sdim // nodes. 3680341825Sdim TreePatternNodePtr Pattern = I.getTree(0); 3681341825Sdim TreePatternNodePtr SrcPattern; 3682341825Sdim if (Pattern->getOperator()->getName() == "set") { 3683341825Sdim SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 3684341825Sdim } else{ 3685341825Sdim // Not a set (store or something?) 3686341825Sdim SrcPattern = Pattern; 3687341825Sdim } 3688341825Sdim 3689288943Sdim // Create and insert the instruction. 3690288943Sdim // FIXME: InstImpResults should not be part of DAGInstruction. 3691341825Sdim Record *R = I.getRecord(); 3692341825Sdim DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R), 3693341825Sdim std::forward_as_tuple(Results, Operands, InstImpResults, 3694341825Sdim SrcPattern, ResultPattern)); 3695193323Sed 3696341825Sdim LLVM_DEBUG(I.dump()); 3697288943Sdim} 3698288943Sdim 3699261991Sdim/// ParseInstructions - Parse all of the instructions, inlining and resolving 3700261991Sdim/// any fragments involved. This populates the Instructions list with fully 3701261991Sdim/// resolved instructions. 3702261991Sdimvoid CodeGenDAGPatterns::ParseInstructions() { 3703261991Sdim std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 3704261991Sdim 3705296417Sdim for (Record *Instr : Instrs) { 3706276479Sdim ListInit *LI = nullptr; 3707261991Sdim 3708296417Sdim if (isa<ListInit>(Instr->getValueInit("Pattern"))) 3709296417Sdim LI = Instr->getValueAsListInit("Pattern"); 3710261991Sdim 3711261991Sdim // If there is no pattern, only collect minimal information about the 3712261991Sdim // instruction for its operand list. We have to assume that there is one 3713261991Sdim // result, as we have no detailed info. A pattern which references the 3714261991Sdim // null_frag operator is as-if no pattern were specified. Normally this 3715261991Sdim // is from a multiclass expansion w/ a SDPatternOperator passed in as 3716261991Sdim // null_frag. 3717288943Sdim if (!LI || LI->empty() || hasNullFragReference(LI)) { 3718261991Sdim std::vector<Record*> Results; 3719261991Sdim std::vector<Record*> Operands; 3720261991Sdim 3721296417Sdim CodeGenInstruction &InstInfo = Target.getInstruction(Instr); 3722261991Sdim 3723261991Sdim if (InstInfo.Operands.size() != 0) { 3724288943Sdim for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j) 3725288943Sdim Results.push_back(InstInfo.Operands[j].Rec); 3726261991Sdim 3727288943Sdim // The rest are inputs. 3728288943Sdim for (unsigned j = InstInfo.Operands.NumDefs, 3729288943Sdim e = InstInfo.Operands.size(); j < e; ++j) 3730288943Sdim Operands.push_back(InstInfo.Operands[j].Rec); 3731261991Sdim } 3732261991Sdim 3733261991Sdim // Create and insert the instruction. 3734261991Sdim std::vector<Record*> ImpResults; 3735296417Sdim Instructions.insert(std::make_pair(Instr, 3736341825Sdim DAGInstruction(Results, Operands, ImpResults))); 3737261991Sdim continue; // no pattern. 3738261991Sdim } 3739261991Sdim 3740296417Sdim CodeGenInstruction &CGI = Target.getInstruction(Instr); 3741341825Sdim parseInstructionPattern(CGI, LI, Instructions); 3742261991Sdim } 3743261991Sdim 3744193323Sed // If we can, convert the instructions to be patterns that are matched! 3745296417Sdim for (auto &Entry : Instructions) { 3746341825Sdim Record *Instr = Entry.first; 3747296417Sdim DAGInstruction &TheInst = Entry.second; 3748341825Sdim TreePatternNodePtr SrcPattern = TheInst.getSrcPattern(); 3749341825Sdim TreePatternNodePtr ResultPattern = TheInst.getResultPattern(); 3750193323Sed 3751341825Sdim if (SrcPattern && ResultPattern) { 3752341825Sdim TreePattern Pattern(Instr, SrcPattern, true, *this); 3753341825Sdim TreePattern Result(Instr, ResultPattern, false, *this); 3754341825Sdim ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults()); 3755193323Sed } 3756193323Sed } 3757193323Sed} 3758193323Sed 3759341825Sdimtypedef std::pair<TreePatternNode *, unsigned> NameRecord; 3760193323Sed 3761341825Sdimstatic void FindNames(TreePatternNode *P, 3762204642Srdivacky std::map<std::string, NameRecord> &Names, 3763243830Sdim TreePattern *PatternTop) { 3764204642Srdivacky if (!P->getName().empty()) { 3765204642Srdivacky NameRecord &Rec = Names[P->getName()]; 3766204642Srdivacky // If this is the first instance of the name, remember the node. 3767204642Srdivacky if (Rec.second++ == 0) 3768204642Srdivacky Rec.first = P; 3769205407Srdivacky else if (Rec.first->getExtTypes() != P->getExtTypes()) 3770204642Srdivacky PatternTop->error("repetition of value: $" + P->getName() + 3771204642Srdivacky " where different uses have different types!"); 3772204642Srdivacky } 3773218893Sdim 3774204642Srdivacky if (!P->isLeaf()) { 3775204642Srdivacky for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 3776204642Srdivacky FindNames(P->getChild(i), Names, PatternTop); 3777204642Srdivacky } 3778204642Srdivacky} 3779204642Srdivacky 3780327952Sdimstd::vector<Predicate> CodeGenDAGPatterns::makePredList(ListInit *L) { 3781327952Sdim std::vector<Predicate> Preds; 3782327952Sdim for (Init *I : L->getValues()) { 3783327952Sdim if (DefInit *Pred = dyn_cast<DefInit>(I)) 3784327952Sdim Preds.push_back(Pred->getDef()); 3785327952Sdim else 3786327952Sdim llvm_unreachable("Non-def on the list"); 3787327952Sdim } 3788327952Sdim 3789327952Sdim // Sort so that different orders get canonicalized to the same string. 3790344779Sdim llvm::sort(Preds); 3791327952Sdim return Preds; 3792327952Sdim} 3793327952Sdim 3794243830Sdimvoid CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern, 3795321369Sdim PatternToMatch &&PTM) { 3796204642Srdivacky // Do some sanity checking on the pattern we're about to match. 3797204642Srdivacky std::string Reason; 3798243830Sdim if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) { 3799243830Sdim PrintWarning(Pattern->getRecord()->getLoc(), 3800243830Sdim Twine("Pattern can never match: ") + Reason); 3801243830Sdim return; 3802243830Sdim } 3803218893Sdim 3804204642Srdivacky // If the source pattern's root is a complex pattern, that complex pattern 3805204642Srdivacky // must specify the nodes it can potentially match. 3806204642Srdivacky if (const ComplexPattern *CP = 3807204642Srdivacky PTM.getSrcPattern()->getComplexPatternInfo(*this)) 3808204642Srdivacky if (CP->getRootNodes().empty()) 3809204642Srdivacky Pattern->error("ComplexPattern at root must specify list of opcodes it" 3810204642Srdivacky " could match"); 3811218893Sdim 3812218893Sdim 3813204642Srdivacky // Find all of the named values in the input and output, ensure they have the 3814204642Srdivacky // same type. 3815204642Srdivacky std::map<std::string, NameRecord> SrcNames, DstNames; 3816204642Srdivacky FindNames(PTM.getSrcPattern(), SrcNames, Pattern); 3817204642Srdivacky FindNames(PTM.getDstPattern(), DstNames, Pattern); 3818204642Srdivacky 3819204642Srdivacky // Scan all of the named values in the destination pattern, rejecting them if 3820204642Srdivacky // they don't exist in the input pattern. 3821296417Sdim for (const auto &Entry : DstNames) { 3822296417Sdim if (SrcNames[Entry.first].first == nullptr) 3823204642Srdivacky Pattern->error("Pattern has input without matching name in output: $" + 3824296417Sdim Entry.first); 3825204642Srdivacky } 3826218893Sdim 3827204642Srdivacky // Scan all of the named values in the source pattern, rejecting them if the 3828204642Srdivacky // name isn't used in the dest, and isn't used to tie two values together. 3829296417Sdim for (const auto &Entry : SrcNames) 3830296417Sdim if (DstNames[Entry.first].first == nullptr && 3831296417Sdim SrcNames[Entry.first].second == 1) 3832296417Sdim Pattern->error("Pattern has dead named input: $" + Entry.first); 3833218893Sdim 3834341825Sdim PatternsToMatch.push_back(PTM); 3835204642Srdivacky} 3836204642Srdivacky 3837193323Sedvoid CodeGenDAGPatterns::InferInstructionFlags() { 3838309124Sdim ArrayRef<const CodeGenInstruction*> Instructions = 3839205407Srdivacky Target.getInstructionsByEnumValue(); 3840243830Sdim 3841243830Sdim unsigned Errors = 0; 3842226633Sdim 3843341825Sdim // Try to infer flags from all patterns in PatternToMatch. These include 3844341825Sdim // both the primary instruction patterns (which always come first) and 3845341825Sdim // patterns defined outside the instruction. 3846321369Sdim for (const PatternToMatch &PTM : ptms()) { 3847243830Sdim // We can only infer from single-instruction patterns, otherwise we won't 3848243830Sdim // know which instruction should get the flags. 3849243830Sdim SmallVector<Record*, 8> PatInstrs; 3850243830Sdim getInstructionsInTree(PTM.getDstPattern(), PatInstrs); 3851243830Sdim if (PatInstrs.size() != 1) 3852243830Sdim continue; 3853243830Sdim 3854243830Sdim // Get the single instruction. 3855243830Sdim CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front()); 3856243830Sdim 3857243830Sdim // Only infer properties from the first pattern. We'll verify the others. 3858243830Sdim if (InstInfo.InferredFrom) 3859243830Sdim continue; 3860243830Sdim 3861243830Sdim InstAnalyzer PatInfo(*this); 3862321369Sdim PatInfo.Analyze(PTM); 3863243830Sdim Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord()); 3864243830Sdim } 3865243830Sdim 3866243830Sdim if (Errors) 3867243830Sdim PrintFatalError("pattern conflicts"); 3868243830Sdim 3869341825Sdim // If requested by the target, guess any undefined properties. 3870243830Sdim if (Target.guessInstructionProperties()) { 3871341825Sdim for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 3872341825Sdim CodeGenInstruction *InstInfo = 3873341825Sdim const_cast<CodeGenInstruction *>(Instructions[i]); 3874296417Sdim if (InstInfo->InferredFrom) 3875243830Sdim continue; 3876243830Sdim // The mayLoad and mayStore flags default to false. 3877243830Sdim // Conservatively assume hasSideEffects if it wasn't explicit. 3878296417Sdim if (InstInfo->hasSideEffects_Unset) 3879296417Sdim InstInfo->hasSideEffects = true; 3880243830Sdim } 3881243830Sdim return; 3882243830Sdim } 3883243830Sdim 3884243830Sdim // Complain about any flags that are still undefined. 3885341825Sdim for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 3886341825Sdim CodeGenInstruction *InstInfo = 3887341825Sdim const_cast<CodeGenInstruction *>(Instructions[i]); 3888296417Sdim if (InstInfo->InferredFrom) 3889243830Sdim continue; 3890296417Sdim if (InstInfo->hasSideEffects_Unset) 3891296417Sdim PrintError(InstInfo->TheDef->getLoc(), 3892243830Sdim "Can't infer hasSideEffects from patterns"); 3893296417Sdim if (InstInfo->mayStore_Unset) 3894296417Sdim PrintError(InstInfo->TheDef->getLoc(), 3895243830Sdim "Can't infer mayStore from patterns"); 3896296417Sdim if (InstInfo->mayLoad_Unset) 3897296417Sdim PrintError(InstInfo->TheDef->getLoc(), 3898243830Sdim "Can't infer mayLoad from patterns"); 3899243830Sdim } 3900193323Sed} 3901193323Sed 3902243830Sdim 3903243830Sdim/// Verify instruction flags against pattern node properties. 3904243830Sdimvoid CodeGenDAGPatterns::VerifyInstructionFlags() { 3905243830Sdim unsigned Errors = 0; 3906243830Sdim for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) { 3907243830Sdim const PatternToMatch &PTM = *I; 3908243830Sdim SmallVector<Record*, 8> Instrs; 3909243830Sdim getInstructionsInTree(PTM.getDstPattern(), Instrs); 3910243830Sdim if (Instrs.empty()) 3911243830Sdim continue; 3912243830Sdim 3913243830Sdim // Count the number of instructions with each flag set. 3914243830Sdim unsigned NumSideEffects = 0; 3915243830Sdim unsigned NumStores = 0; 3916243830Sdim unsigned NumLoads = 0; 3917296417Sdim for (const Record *Instr : Instrs) { 3918296417Sdim const CodeGenInstruction &InstInfo = Target.getInstruction(Instr); 3919243830Sdim NumSideEffects += InstInfo.hasSideEffects; 3920243830Sdim NumStores += InstInfo.mayStore; 3921243830Sdim NumLoads += InstInfo.mayLoad; 3922243830Sdim } 3923243830Sdim 3924243830Sdim // Analyze the source pattern. 3925243830Sdim InstAnalyzer PatInfo(*this); 3926321369Sdim PatInfo.Analyze(PTM); 3927243830Sdim 3928243830Sdim // Collect error messages. 3929243830Sdim SmallVector<std::string, 4> Msgs; 3930243830Sdim 3931243830Sdim // Check for missing flags in the output. 3932243830Sdim // Permit extra flags for now at least. 3933243830Sdim if (PatInfo.hasSideEffects && !NumSideEffects) 3934243830Sdim Msgs.push_back("pattern has side effects, but hasSideEffects isn't set"); 3935243830Sdim 3936243830Sdim // Don't verify store flags on instructions with side effects. At least for 3937243830Sdim // intrinsics, side effects implies mayStore. 3938243830Sdim if (!PatInfo.hasSideEffects && PatInfo.mayStore && !NumStores) 3939243830Sdim Msgs.push_back("pattern may store, but mayStore isn't set"); 3940243830Sdim 3941243830Sdim // Similarly, mayStore implies mayLoad on intrinsics. 3942243830Sdim if (!PatInfo.mayStore && PatInfo.mayLoad && !NumLoads) 3943243830Sdim Msgs.push_back("pattern may load, but mayLoad isn't set"); 3944243830Sdim 3945243830Sdim // Print error messages. 3946243830Sdim if (Msgs.empty()) 3947243830Sdim continue; 3948243830Sdim ++Errors; 3949243830Sdim 3950296417Sdim for (const std::string &Msg : Msgs) 3951296417Sdim PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msg) + " on the " + 3952243830Sdim (Instrs.size() == 1 ? 3953243830Sdim "instruction" : "output instructions")); 3954243830Sdim // Provide the location of the relevant instruction definitions. 3955296417Sdim for (const Record *Instr : Instrs) { 3956296417Sdim if (Instr != PTM.getSrcRecord()) 3957296417Sdim PrintError(Instr->getLoc(), "defined here"); 3958296417Sdim const CodeGenInstruction &InstInfo = Target.getInstruction(Instr); 3959243830Sdim if (InstInfo.InferredFrom && 3960243830Sdim InstInfo.InferredFrom != InstInfo.TheDef && 3961243830Sdim InstInfo.InferredFrom != PTM.getSrcRecord()) 3962296417Sdim PrintError(InstInfo.InferredFrom->getLoc(), "inferred from pattern"); 3963243830Sdim } 3964243830Sdim } 3965243830Sdim if (Errors) 3966243830Sdim PrintFatalError("Errors in DAG patterns"); 3967243830Sdim} 3968243830Sdim 3969205218Srdivacky/// Given a pattern result with an unresolved type, see if we can find one 3970205218Srdivacky/// instruction with an unresolved result type. Force this result type to an 3971205218Srdivacky/// arbitrary element if it's possible types to converge results. 3972205218Srdivackystatic bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { 3973205218Srdivacky if (N->isLeaf()) 3974205218Srdivacky return false; 3975218893Sdim 3976205218Srdivacky // Analyze children. 3977205218Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 3978205218Srdivacky if (ForceArbitraryInstResultType(N->getChild(i), TP)) 3979205218Srdivacky return true; 3980205218Srdivacky 3981205218Srdivacky if (!N->getOperator()->isSubClassOf("Instruction")) 3982205218Srdivacky return false; 3983205218Srdivacky 3984205218Srdivacky // If this type is already concrete or completely unknown we can't do 3985205218Srdivacky // anything. 3986327952Sdim TypeInfer &TI = TP.getInfer(); 3987205407Srdivacky for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) { 3988327952Sdim if (N->getExtType(i).empty() || TI.isConcrete(N->getExtType(i), false)) 3989205407Srdivacky continue; 3990218893Sdim 3991327952Sdim // Otherwise, force its type to an arbitrary choice. 3992327952Sdim if (TI.forceArbitrary(N->getExtType(i))) 3993205407Srdivacky return true; 3994205407Srdivacky } 3995218893Sdim 3996205407Srdivacky return false; 3997205218Srdivacky} 3998205218Srdivacky 3999341825Sdim// Promote xform function to be an explicit node wherever set. 4000341825Sdimstatic TreePatternNodePtr PromoteXForms(TreePatternNodePtr N) { 4001341825Sdim if (Record *Xform = N->getTransformFn()) { 4002341825Sdim N->setTransformFn(nullptr); 4003341825Sdim std::vector<TreePatternNodePtr> Children; 4004341825Sdim Children.push_back(PromoteXForms(N)); 4005341825Sdim return std::make_shared<TreePatternNode>(Xform, std::move(Children), 4006341825Sdim N->getNumTypes()); 4007341825Sdim } 4008341825Sdim 4009341825Sdim if (!N->isLeaf()) 4010341825Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 4011341825Sdim TreePatternNodePtr Child = N->getChildShared(i); 4012341825Sdim N->setChild(i, PromoteXForms(Child)); 4013341825Sdim } 4014341825Sdim return N; 4015341825Sdim} 4016341825Sdim 4017341825Sdimvoid CodeGenDAGPatterns::ParseOnePattern(Record *TheDef, 4018341825Sdim TreePattern &Pattern, TreePattern &Result, 4019341825Sdim const std::vector<Record *> &InstImpResults) { 4020341825Sdim 4021341825Sdim // Inline pattern fragments and expand multiple alternatives. 4022341825Sdim Pattern.InlinePatternFragments(); 4023341825Sdim Result.InlinePatternFragments(); 4024341825Sdim 4025341825Sdim if (Result.getNumTrees() != 1) 4026341825Sdim Result.error("Cannot use multi-alternative fragments in result pattern!"); 4027341825Sdim 4028341825Sdim // Infer types. 4029341825Sdim bool IterateInference; 4030341825Sdim bool InferredAllPatternTypes, InferredAllResultTypes; 4031341825Sdim do { 4032341825Sdim // Infer as many types as possible. If we cannot infer all of them, we 4033341825Sdim // can never do anything with this pattern: report it to the user. 4034341825Sdim InferredAllPatternTypes = 4035341825Sdim Pattern.InferAllTypes(&Pattern.getNamedNodesMap()); 4036341825Sdim 4037341825Sdim // Infer as many types as possible. If we cannot infer all of them, we 4038341825Sdim // can never do anything with this pattern: report it to the user. 4039341825Sdim InferredAllResultTypes = 4040341825Sdim Result.InferAllTypes(&Pattern.getNamedNodesMap()); 4041341825Sdim 4042341825Sdim IterateInference = false; 4043341825Sdim 4044341825Sdim // Apply the type of the result to the source pattern. This helps us 4045341825Sdim // resolve cases where the input type is known to be a pointer type (which 4046341825Sdim // is considered resolved), but the result knows it needs to be 32- or 4047341825Sdim // 64-bits. Infer the other way for good measure. 4048341825Sdim for (auto T : Pattern.getTrees()) 4049341825Sdim for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(), 4050341825Sdim T->getNumTypes()); 4051341825Sdim i != e; ++i) { 4052341825Sdim IterateInference |= T->UpdateNodeType( 4053341825Sdim i, Result.getOnlyTree()->getExtType(i), Result); 4054341825Sdim IterateInference |= Result.getOnlyTree()->UpdateNodeType( 4055341825Sdim i, T->getExtType(i), Result); 4056341825Sdim } 4057341825Sdim 4058341825Sdim // If our iteration has converged and the input pattern's types are fully 4059341825Sdim // resolved but the result pattern is not fully resolved, we may have a 4060341825Sdim // situation where we have two instructions in the result pattern and 4061341825Sdim // the instructions require a common register class, but don't care about 4062341825Sdim // what actual MVT is used. This is actually a bug in our modelling: 4063341825Sdim // output patterns should have register classes, not MVTs. 4064341825Sdim // 4065341825Sdim // In any case, to handle this, we just go through and disambiguate some 4066341825Sdim // arbitrary types to the result pattern's nodes. 4067341825Sdim if (!IterateInference && InferredAllPatternTypes && 4068341825Sdim !InferredAllResultTypes) 4069341825Sdim IterateInference = 4070341825Sdim ForceArbitraryInstResultType(Result.getTree(0).get(), Result); 4071341825Sdim } while (IterateInference); 4072341825Sdim 4073341825Sdim // Verify that we inferred enough types that we can do something with the 4074341825Sdim // pattern and result. If these fire the user has to add type casts. 4075341825Sdim if (!InferredAllPatternTypes) 4076341825Sdim Pattern.error("Could not infer all types in pattern!"); 4077341825Sdim if (!InferredAllResultTypes) { 4078341825Sdim Pattern.dump(); 4079341825Sdim Result.error("Could not infer all types in pattern result!"); 4080341825Sdim } 4081341825Sdim 4082341825Sdim // Promote xform function to be an explicit node wherever set. 4083341825Sdim TreePatternNodePtr DstShared = PromoteXForms(Result.getOnlyTree()); 4084341825Sdim 4085341825Sdim TreePattern Temp(Result.getRecord(), DstShared, false, *this); 4086341825Sdim Temp.InferAllTypes(); 4087341825Sdim 4088341825Sdim ListInit *Preds = TheDef->getValueAsListInit("Predicates"); 4089341825Sdim int Complexity = TheDef->getValueAsInt("AddedComplexity"); 4090341825Sdim 4091341825Sdim if (PatternRewriter) 4092341825Sdim PatternRewriter(&Pattern); 4093341825Sdim 4094341825Sdim // A pattern may end up with an "impossible" type, i.e. a situation 4095341825Sdim // where all types have been eliminated for some node in this pattern. 4096341825Sdim // This could occur for intrinsics that only make sense for a specific 4097341825Sdim // value type, and use a specific register class. If, for some mode, 4098341825Sdim // that register class does not accept that type, the type inference 4099341825Sdim // will lead to a contradiction, which is not an error however, but 4100341825Sdim // a sign that this pattern will simply never match. 4101341825Sdim if (Temp.getOnlyTree()->hasPossibleType()) 4102341825Sdim for (auto T : Pattern.getTrees()) 4103341825Sdim if (T->hasPossibleType()) 4104341825Sdim AddPatternToMatch(&Pattern, 4105341825Sdim PatternToMatch(TheDef, makePredList(Preds), 4106341825Sdim T, Temp.getOnlyTree(), 4107341825Sdim InstImpResults, Complexity, 4108341825Sdim TheDef->getID())); 4109341825Sdim} 4110341825Sdim 4111193323Sedvoid CodeGenDAGPatterns::ParsePatterns() { 4112193323Sed std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 4113193323Sed 4114296417Sdim for (Record *CurPattern : Patterns) { 4115205407Srdivacky DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); 4116239462Sdim 4117239462Sdim // If the pattern references the null_frag, there's nothing to do. 4118239462Sdim if (hasNullFragReference(Tree)) 4119239462Sdim continue; 4120239462Sdim 4121341825Sdim TreePattern Pattern(CurPattern, Tree, true, *this); 4122193323Sed 4123205407Srdivacky ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); 4124288943Sdim if (LI->empty()) continue; // no pattern. 4125218893Sdim 4126193323Sed // Parse the instruction. 4127280031Sdim TreePattern Result(CurPattern, LI, false, *this); 4128218893Sdim 4129280031Sdim if (Result.getNumTrees() != 1) 4130280031Sdim Result.error("Cannot handle instructions producing instructions " 4131280031Sdim "with temporaries yet!"); 4132218893Sdim 4133193323Sed // Validate that the input pattern is correct. 4134341825Sdim std::map<std::string, TreePatternNodePtr> InstInputs; 4135344779Sdim MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>> 4136344779Sdim InstResults; 4137193323Sed std::vector<Record*> InstImpResults; 4138341825Sdim for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j) 4139341825Sdim FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs, 4140341825Sdim InstResults, InstImpResults); 4141193323Sed 4142341825Sdim ParseOnePattern(CurPattern, Pattern, Result, InstImpResults); 4143193323Sed } 4144193323Sed} 4145193323Sed 4146327952Sdimstatic void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) { 4147327952Sdim for (const TypeSetByHwMode &VTS : N->getExtTypes()) 4148327952Sdim for (const auto &I : VTS) 4149327952Sdim Modes.insert(I.first); 4150327952Sdim 4151327952Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 4152327952Sdim collectModes(Modes, N->getChild(i)); 4153327952Sdim} 4154327952Sdim 4155327952Sdimvoid CodeGenDAGPatterns::ExpandHwModeBasedTypes() { 4156327952Sdim const CodeGenHwModes &CGH = getTargetInfo().getHwModes(); 4157327952Sdim std::map<unsigned,std::vector<Predicate>> ModeChecks; 4158327952Sdim std::vector<PatternToMatch> Copy = PatternsToMatch; 4159327952Sdim PatternsToMatch.clear(); 4160327952Sdim 4161341825Sdim auto AppendPattern = [this, &ModeChecks](PatternToMatch &P, unsigned Mode) { 4162341825Sdim TreePatternNodePtr NewSrc = P.SrcPattern->clone(); 4163341825Sdim TreePatternNodePtr NewDst = P.DstPattern->clone(); 4164327952Sdim if (!NewSrc->setDefaultMode(Mode) || !NewDst->setDefaultMode(Mode)) { 4165327952Sdim return; 4166327952Sdim } 4167327952Sdim 4168327952Sdim std::vector<Predicate> Preds = P.Predicates; 4169327952Sdim const std::vector<Predicate> &MC = ModeChecks[Mode]; 4170327952Sdim Preds.insert(Preds.end(), MC.begin(), MC.end()); 4171341825Sdim PatternsToMatch.emplace_back(P.getSrcRecord(), Preds, std::move(NewSrc), 4172341825Sdim std::move(NewDst), P.getDstRegs(), 4173341825Sdim P.getAddedComplexity(), Record::getNewUID(), 4174341825Sdim Mode); 4175327952Sdim }; 4176327952Sdim 4177327952Sdim for (PatternToMatch &P : Copy) { 4178341825Sdim TreePatternNodePtr SrcP = nullptr, DstP = nullptr; 4179327952Sdim if (P.SrcPattern->hasProperTypeByHwMode()) 4180327952Sdim SrcP = P.SrcPattern; 4181327952Sdim if (P.DstPattern->hasProperTypeByHwMode()) 4182327952Sdim DstP = P.DstPattern; 4183327952Sdim if (!SrcP && !DstP) { 4184327952Sdim PatternsToMatch.push_back(P); 4185327952Sdim continue; 4186327952Sdim } 4187327952Sdim 4188327952Sdim std::set<unsigned> Modes; 4189327952Sdim if (SrcP) 4190341825Sdim collectModes(Modes, SrcP.get()); 4191327952Sdim if (DstP) 4192341825Sdim collectModes(Modes, DstP.get()); 4193327952Sdim 4194327952Sdim // The predicate for the default mode needs to be constructed for each 4195327952Sdim // pattern separately. 4196327952Sdim // Since not all modes must be present in each pattern, if a mode m is 4197327952Sdim // absent, then there is no point in constructing a check for m. If such 4198327952Sdim // a check was created, it would be equivalent to checking the default 4199327952Sdim // mode, except not all modes' predicates would be a part of the checking 4200327952Sdim // code. The subsequently generated check for the default mode would then 4201327952Sdim // have the exact same patterns, but a different predicate code. To avoid 4202327952Sdim // duplicated patterns with different predicate checks, construct the 4203327952Sdim // default check as a negation of all predicates that are actually present 4204327952Sdim // in the source/destination patterns. 4205327952Sdim std::vector<Predicate> DefaultPred; 4206327952Sdim 4207327952Sdim for (unsigned M : Modes) { 4208327952Sdim if (M == DefaultMode) 4209327952Sdim continue; 4210327952Sdim if (ModeChecks.find(M) != ModeChecks.end()) 4211327952Sdim continue; 4212327952Sdim 4213327952Sdim // Fill the map entry for this mode. 4214327952Sdim const HwMode &HM = CGH.getMode(M); 4215327952Sdim ModeChecks[M].emplace_back(Predicate(HM.Features, true)); 4216327952Sdim 4217327952Sdim // Add negations of the HM's predicates to the default predicate. 4218327952Sdim DefaultPred.emplace_back(Predicate(HM.Features, false)); 4219327952Sdim } 4220327952Sdim 4221327952Sdim for (unsigned M : Modes) { 4222327952Sdim if (M == DefaultMode) 4223327952Sdim continue; 4224327952Sdim AppendPattern(P, M); 4225327952Sdim } 4226327952Sdim 4227327952Sdim bool HasDefault = Modes.count(DefaultMode); 4228327952Sdim if (HasDefault) 4229327952Sdim AppendPattern(P, DefaultMode); 4230327952Sdim } 4231327952Sdim} 4232327952Sdim 4233327952Sdim/// Dependent variable map for CodeGenDAGPattern variant generation 4234327952Sdimtypedef StringMap<int> DepVarMap; 4235327952Sdim 4236327952Sdimstatic void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 4237327952Sdim if (N->isLeaf()) { 4238327952Sdim if (N->hasName() && isa<DefInit>(N->getLeafValue())) 4239327952Sdim DepMap[N->getName()]++; 4240327952Sdim } else { 4241327952Sdim for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 4242327952Sdim FindDepVarsOf(N->getChild(i), DepMap); 4243327952Sdim } 4244327952Sdim} 4245327952Sdim 4246327952Sdim/// Find dependent variables within child patterns 4247327952Sdimstatic void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 4248327952Sdim DepVarMap depcounts; 4249327952Sdim FindDepVarsOf(N, depcounts); 4250327952Sdim for (const auto &Pair : depcounts) { 4251327952Sdim if (Pair.getValue() > 1) 4252327952Sdim DepVars.insert(Pair.getKey()); 4253327952Sdim } 4254327952Sdim} 4255327952Sdim 4256327952Sdim#ifndef NDEBUG 4257327952Sdim/// Dump the dependent variable set: 4258327952Sdimstatic void DumpDepVars(MultipleUseVarSet &DepVars) { 4259327952Sdim if (DepVars.empty()) { 4260341825Sdim LLVM_DEBUG(errs() << "<empty set>"); 4261327952Sdim } else { 4262341825Sdim LLVM_DEBUG(errs() << "[ "); 4263327952Sdim for (const auto &DepVar : DepVars) { 4264341825Sdim LLVM_DEBUG(errs() << DepVar.getKey() << " "); 4265327952Sdim } 4266341825Sdim LLVM_DEBUG(errs() << "]"); 4267327952Sdim } 4268327952Sdim} 4269327952Sdim#endif 4270327952Sdim 4271327952Sdim 4272193323Sed/// CombineChildVariants - Given a bunch of permutations of each child of the 4273193323Sed/// 'operator' node, put them together in all possible ways. 4274341825Sdimstatic void CombineChildVariants( 4275341825Sdim TreePatternNodePtr Orig, 4276341825Sdim const std::vector<std::vector<TreePatternNodePtr>> &ChildVariants, 4277341825Sdim std::vector<TreePatternNodePtr> &OutVariants, CodeGenDAGPatterns &CDP, 4278341825Sdim const MultipleUseVarSet &DepVars) { 4279193323Sed // Make sure that each operand has at least one variant to choose from. 4280296417Sdim for (const auto &Variants : ChildVariants) 4281296417Sdim if (Variants.empty()) 4282193323Sed return; 4283218893Sdim 4284193323Sed // The end result is an all-pairs construction of the resultant pattern. 4285193323Sed std::vector<unsigned> Idxs; 4286193323Sed Idxs.resize(ChildVariants.size()); 4287193323Sed bool NotDone; 4288193323Sed do { 4289193323Sed#ifndef NDEBUG 4290341825Sdim LLVM_DEBUG(if (!Idxs.empty()) { 4291341825Sdim errs() << Orig->getOperator()->getName() << ": Idxs = [ "; 4292341825Sdim for (unsigned Idx : Idxs) { 4293341825Sdim errs() << Idx << " "; 4294341825Sdim } 4295341825Sdim errs() << "]\n"; 4296341825Sdim }); 4297193323Sed#endif 4298193323Sed // Create the variant and add it to the output list. 4299341825Sdim std::vector<TreePatternNodePtr> NewChildren; 4300193323Sed for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 4301193323Sed NewChildren.push_back(ChildVariants[i][Idxs[i]]); 4302341825Sdim TreePatternNodePtr R = std::make_shared<TreePatternNode>( 4303341825Sdim Orig->getOperator(), std::move(NewChildren), Orig->getNumTypes()); 4304218893Sdim 4305193323Sed // Copy over properties. 4306193323Sed R->setName(Orig->getName()); 4307344779Sdim R->setNamesAsPredicateArg(Orig->getNamesAsPredicateArg()); 4308344779Sdim R->setPredicateCalls(Orig->getPredicateCalls()); 4309193323Sed R->setTransformFn(Orig->getTransformFn()); 4310205407Srdivacky for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) 4311205407Srdivacky R->setType(i, Orig->getExtType(i)); 4312218893Sdim 4313193323Sed // If this pattern cannot match, do not include it as a variant. 4314193323Sed std::string ErrString; 4315296417Sdim // Scan to see if this pattern has already been emitted. We can get 4316296417Sdim // duplication due to things like commuting: 4317296417Sdim // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 4318296417Sdim // which are the same pattern. Ignore the dups. 4319296417Sdim if (R->canPatternMatch(ErrString, CDP) && 4320341825Sdim none_of(OutVariants, [&](TreePatternNodePtr Variant) { 4321341825Sdim return R->isIsomorphicTo(Variant.get(), DepVars); 4322314564Sdim })) 4323341825Sdim OutVariants.push_back(R); 4324218893Sdim 4325193323Sed // Increment indices to the next permutation by incrementing the 4326296417Sdim // indices from last index backward, e.g., generate the sequence 4327193323Sed // [0, 0], [0, 1], [1, 0], [1, 1]. 4328193323Sed int IdxsIdx; 4329193323Sed for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 4330193323Sed if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 4331193323Sed Idxs[IdxsIdx] = 0; 4332193323Sed else 4333193323Sed break; 4334193323Sed } 4335193323Sed NotDone = (IdxsIdx >= 0); 4336193323Sed } while (NotDone); 4337193323Sed} 4338193323Sed 4339193323Sed/// CombineChildVariants - A helper function for binary operators. 4340193323Sed/// 4341341825Sdimstatic void CombineChildVariants(TreePatternNodePtr Orig, 4342341825Sdim const std::vector<TreePatternNodePtr> &LHS, 4343341825Sdim const std::vector<TreePatternNodePtr> &RHS, 4344341825Sdim std::vector<TreePatternNodePtr> &OutVariants, 4345193323Sed CodeGenDAGPatterns &CDP, 4346193323Sed const MultipleUseVarSet &DepVars) { 4347341825Sdim std::vector<std::vector<TreePatternNodePtr>> ChildVariants; 4348193323Sed ChildVariants.push_back(LHS); 4349193323Sed ChildVariants.push_back(RHS); 4350193323Sed CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 4351218893Sdim} 4352193323Sed 4353341825Sdimstatic void 4354341825SdimGatherChildrenOfAssociativeOpcode(TreePatternNodePtr N, 4355341825Sdim std::vector<TreePatternNodePtr> &Children) { 4356193323Sed assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 4357193323Sed Record *Operator = N->getOperator(); 4358218893Sdim 4359193323Sed // Only permit raw nodes. 4360344779Sdim if (!N->getName().empty() || !N->getPredicateCalls().empty() || 4361193323Sed N->getTransformFn()) { 4362193323Sed Children.push_back(N); 4363193323Sed return; 4364193323Sed } 4365193323Sed 4366193323Sed if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 4367341825Sdim Children.push_back(N->getChildShared(0)); 4368193323Sed else 4369341825Sdim GatherChildrenOfAssociativeOpcode(N->getChildShared(0), Children); 4370193323Sed 4371193323Sed if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 4372341825Sdim Children.push_back(N->getChildShared(1)); 4373193323Sed else 4374341825Sdim GatherChildrenOfAssociativeOpcode(N->getChildShared(1), Children); 4375193323Sed} 4376193323Sed 4377193323Sed/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 4378193323Sed/// the (potentially recursive) pattern by using algebraic laws. 4379193323Sed/// 4380341825Sdimstatic void GenerateVariantsOf(TreePatternNodePtr N, 4381341825Sdim std::vector<TreePatternNodePtr> &OutVariants, 4382193323Sed CodeGenDAGPatterns &CDP, 4383193323Sed const MultipleUseVarSet &DepVars) { 4384276479Sdim // We cannot permute leaves or ComplexPattern uses. 4385276479Sdim if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) { 4386193323Sed OutVariants.push_back(N); 4387193323Sed return; 4388193323Sed } 4389193323Sed 4390193323Sed // Look up interesting info about the node. 4391193323Sed const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 4392193323Sed 4393193323Sed // If this node is associative, re-associate. 4394193323Sed if (NodeInfo.hasProperty(SDNPAssociative)) { 4395218893Sdim // Re-associate by pulling together all of the linked operators 4396341825Sdim std::vector<TreePatternNodePtr> MaximalChildren; 4397193323Sed GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 4398193323Sed 4399193323Sed // Only handle child sizes of 3. Otherwise we'll end up trying too many 4400193323Sed // permutations. 4401193323Sed if (MaximalChildren.size() == 3) { 4402193323Sed // Find the variants of all of our maximal children. 4403341825Sdim std::vector<TreePatternNodePtr> AVariants, BVariants, CVariants; 4404193323Sed GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 4405193323Sed GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 4406193323Sed GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 4407218893Sdim 4408193323Sed // There are only two ways we can permute the tree: 4409193323Sed // (A op B) op C and A op (B op C) 4410193323Sed // Within these forms, we can also permute A/B/C. 4411218893Sdim 4412193323Sed // Generate legal pair permutations of A/B/C. 4413341825Sdim std::vector<TreePatternNodePtr> ABVariants; 4414341825Sdim std::vector<TreePatternNodePtr> BAVariants; 4415341825Sdim std::vector<TreePatternNodePtr> ACVariants; 4416341825Sdim std::vector<TreePatternNodePtr> CAVariants; 4417341825Sdim std::vector<TreePatternNodePtr> BCVariants; 4418341825Sdim std::vector<TreePatternNodePtr> CBVariants; 4419193323Sed CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 4420193323Sed CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 4421193323Sed CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 4422193323Sed CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 4423193323Sed CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 4424193323Sed CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 4425193323Sed 4426193323Sed // Combine those into the result: (x op x) op x 4427193323Sed CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 4428193323Sed CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 4429193323Sed CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 4430193323Sed CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 4431193323Sed CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 4432193323Sed CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 4433193323Sed 4434193323Sed // Combine those into the result: x op (x op x) 4435193323Sed CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 4436193323Sed CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 4437193323Sed CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 4438193323Sed CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 4439193323Sed CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 4440193323Sed CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 4441193323Sed return; 4442193323Sed } 4443193323Sed } 4444218893Sdim 4445193323Sed // Compute permutations of all children. 4446341825Sdim std::vector<std::vector<TreePatternNodePtr>> ChildVariants; 4447193323Sed ChildVariants.resize(N->getNumChildren()); 4448193323Sed for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 4449341825Sdim GenerateVariantsOf(N->getChildShared(i), ChildVariants[i], CDP, DepVars); 4450193323Sed 4451193323Sed // Build all permutations based on how the children were formed. 4452193323Sed CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 4453193323Sed 4454193323Sed // If this node is commutative, consider the commuted order. 4455193323Sed bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP); 4456193323Sed if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 4457327952Sdim assert((N->getNumChildren()>=2 || isCommIntrinsic) && 4458193323Sed "Commutative but doesn't have 2 children!"); 4459193323Sed // Don't count children which are actually register references. 4460193323Sed unsigned NC = 0; 4461193323Sed for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 4462193323Sed TreePatternNode *Child = N->getChild(i); 4463193323Sed if (Child->isLeaf()) 4464243830Sdim if (DefInit *DI = dyn_cast<DefInit>(Child->getLeafValue())) { 4465193323Sed Record *RR = DI->getDef(); 4466193323Sed if (RR->isSubClassOf("Register")) 4467193323Sed continue; 4468193323Sed } 4469193323Sed NC++; 4470193323Sed } 4471193323Sed // Consider the commuted order. 4472193323Sed if (isCommIntrinsic) { 4473193323Sed // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd 4474193323Sed // operands are the commutative operands, and there might be more operands 4475193323Sed // after those. 4476193323Sed assert(NC >= 3 && 4477296417Sdim "Commutative intrinsic should have at least 3 children!"); 4478341825Sdim std::vector<std::vector<TreePatternNodePtr>> Variants; 4479341825Sdim Variants.push_back(std::move(ChildVariants[0])); // Intrinsic id. 4480341825Sdim Variants.push_back(std::move(ChildVariants[2])); 4481341825Sdim Variants.push_back(std::move(ChildVariants[1])); 4482193323Sed for (unsigned i = 3; i != NC; ++i) 4483341825Sdim Variants.push_back(std::move(ChildVariants[i])); 4484193323Sed CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 4485327952Sdim } else if (NC == N->getNumChildren()) { 4486341825Sdim std::vector<std::vector<TreePatternNodePtr>> Variants; 4487341825Sdim Variants.push_back(std::move(ChildVariants[1])); 4488341825Sdim Variants.push_back(std::move(ChildVariants[0])); 4489327952Sdim for (unsigned i = 2; i != NC; ++i) 4490341825Sdim Variants.push_back(std::move(ChildVariants[i])); 4491327952Sdim CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 4492327952Sdim } 4493193323Sed } 4494193323Sed} 4495193323Sed 4496193323Sed 4497193323Sed// GenerateVariants - Generate variants. For example, commutative patterns can 4498193323Sed// match multiple ways. Add them to PatternsToMatch as well. 4499193323Sedvoid CodeGenDAGPatterns::GenerateVariants() { 4500341825Sdim LLVM_DEBUG(errs() << "Generating instruction variants.\n"); 4501218893Sdim 4502193323Sed // Loop over all of the patterns we've collected, checking to see if we can 4503193323Sed // generate variants of the instruction, through the exploitation of 4504193323Sed // identities. This permits the target to provide aggressive matching without 4505193323Sed // the .td file having to contain tons of variants of instructions. 4506193323Sed // 4507193323Sed // Note that this loop adds new patterns to the PatternsToMatch list, but we 4508193323Sed // intentionally do not reconsider these. Any variants of added patterns have 4509193323Sed // already been added. 4510193323Sed // 4511344779Sdim const unsigned NumOriginalPatterns = PatternsToMatch.size(); 4512344779Sdim BitVector MatchedPatterns(NumOriginalPatterns); 4513344779Sdim std::vector<BitVector> MatchedPredicates(NumOriginalPatterns, 4514344779Sdim BitVector(NumOriginalPatterns)); 4515344779Sdim 4516344779Sdim typedef std::pair<MultipleUseVarSet, std::vector<TreePatternNodePtr>> 4517344779Sdim DepsAndVariants; 4518344779Sdim std::map<unsigned, DepsAndVariants> PatternsWithVariants; 4519344779Sdim 4520344779Sdim // Collect patterns with more than one variant. 4521344779Sdim for (unsigned i = 0; i != NumOriginalPatterns; ++i) { 4522344779Sdim MultipleUseVarSet DepVars; 4523341825Sdim std::vector<TreePatternNodePtr> Variants; 4524193323Sed FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 4525341825Sdim LLVM_DEBUG(errs() << "Dependent/multiply used variables: "); 4526341825Sdim LLVM_DEBUG(DumpDepVars(DepVars)); 4527341825Sdim LLVM_DEBUG(errs() << "\n"); 4528341825Sdim GenerateVariantsOf(PatternsToMatch[i].getSrcPatternShared(), Variants, 4529341825Sdim *this, DepVars); 4530193323Sed 4531193323Sed assert(!Variants.empty() && "Must create at least original variant!"); 4532344779Sdim if (Variants.size() == 1) // No additional variants for this pattern. 4533193323Sed continue; 4534193323Sed 4535341825Sdim LLVM_DEBUG(errs() << "FOUND VARIANTS OF: "; 4536341825Sdim PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n"); 4537193323Sed 4538344779Sdim PatternsWithVariants[i] = std::make_pair(DepVars, Variants); 4539344779Sdim 4540344779Sdim // Cache matching predicates. 4541344779Sdim if (MatchedPatterns[i]) 4542344779Sdim continue; 4543344779Sdim 4544344779Sdim const std::vector<Predicate> &Predicates = 4545344779Sdim PatternsToMatch[i].getPredicates(); 4546344779Sdim 4547344779Sdim BitVector &Matches = MatchedPredicates[i]; 4548344779Sdim MatchedPatterns.set(i); 4549344779Sdim Matches.set(i); 4550344779Sdim 4551344779Sdim // Don't test patterns that have already been cached - it won't match. 4552344779Sdim for (unsigned p = 0; p != NumOriginalPatterns; ++p) 4553344779Sdim if (!MatchedPatterns[p]) 4554344779Sdim Matches[p] = (Predicates == PatternsToMatch[p].getPredicates()); 4555344779Sdim 4556344779Sdim // Copy this to all the matching patterns. 4557344779Sdim for (int p = Matches.find_first(); p != -1; p = Matches.find_next(p)) 4558344779Sdim if (p != (int)i) { 4559344779Sdim MatchedPatterns.set(p); 4560344779Sdim MatchedPredicates[p] = Matches; 4561344779Sdim } 4562344779Sdim } 4563344779Sdim 4564344779Sdim for (auto it : PatternsWithVariants) { 4565344779Sdim unsigned i = it.first; 4566344779Sdim const MultipleUseVarSet &DepVars = it.second.first; 4567344779Sdim const std::vector<TreePatternNodePtr> &Variants = it.second.second; 4568344779Sdim 4569193323Sed for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 4570341825Sdim TreePatternNodePtr Variant = Variants[v]; 4571344779Sdim BitVector &Matches = MatchedPredicates[i]; 4572193323Sed 4573341825Sdim LLVM_DEBUG(errs() << " VAR#" << v << ": "; Variant->dump(); 4574341825Sdim errs() << "\n"); 4575218893Sdim 4576193323Sed // Scan to see if an instruction or explicit pattern already matches this. 4577193323Sed bool AlreadyExists = false; 4578193323Sed for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 4579195098Sed // Skip if the top level predicates do not match. 4580344779Sdim if (!Matches[p]) 4581195098Sed continue; 4582193323Sed // Check to see if this variant already exists. 4583218893Sdim if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), 4584218893Sdim DepVars)) { 4585341825Sdim LLVM_DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n"); 4586193323Sed AlreadyExists = true; 4587193323Sed break; 4588193323Sed } 4589193323Sed } 4590193323Sed // If we already have it, ignore the variant. 4591193323Sed if (AlreadyExists) continue; 4592193323Sed 4593193323Sed // Otherwise, add it to the list of patterns we have. 4594321369Sdim PatternsToMatch.push_back(PatternToMatch( 4595288943Sdim PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(), 4596341825Sdim Variant, PatternsToMatch[i].getDstPatternShared(), 4597288943Sdim PatternsToMatch[i].getDstRegs(), 4598321369Sdim PatternsToMatch[i].getAddedComplexity(), Record::getNewUID())); 4599344779Sdim MatchedPredicates.push_back(Matches); 4600344779Sdim 4601344779Sdim // Add a new match the same as this pattern. 4602344779Sdim for (auto &P : MatchedPredicates) 4603344779Sdim P.push_back(P[i]); 4604193323Sed } 4605193323Sed 4606341825Sdim LLVM_DEBUG(errs() << "\n"); 4607193323Sed } 4608193323Sed} 4609