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