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