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