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