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