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