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