CodeGenDAGPatterns.cpp revision 288943
1//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the CodeGenDAGPatterns class, which is used to read and 11// represent the patterns present in a .td file for instructions. 12// 13//===----------------------------------------------------------------------===// 14 15#include "CodeGenDAGPatterns.h" 16#include "llvm/ADT/STLExtras.h" 17#include "llvm/ADT/StringExtras.h" 18#include "llvm/ADT/Twine.h" 19#include "llvm/Support/Debug.h" 20#include "llvm/Support/ErrorHandling.h" 21#include "llvm/TableGen/Error.h" 22#include "llvm/TableGen/Record.h" 23#include <algorithm> 24#include <cstdio> 25#include <set> 26using namespace llvm; 27 28#define DEBUG_TYPE "dag-patterns" 29 30//===----------------------------------------------------------------------===// 31// EEVT::TypeSet Implementation 32//===----------------------------------------------------------------------===// 33 34static inline bool isInteger(MVT::SimpleValueType VT) { 35 return MVT(VT).isInteger(); 36} 37static inline bool isFloatingPoint(MVT::SimpleValueType VT) { 38 return MVT(VT).isFloatingPoint(); 39} 40static inline bool isVector(MVT::SimpleValueType VT) { 41 return MVT(VT).isVector(); 42} 43static inline bool isScalar(MVT::SimpleValueType VT) { 44 return !MVT(VT).isVector(); 45} 46 47EEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) { 48 if (VT == MVT::iAny) 49 EnforceInteger(TP); 50 else if (VT == MVT::fAny) 51 EnforceFloatingPoint(TP); 52 else if (VT == MVT::vAny) 53 EnforceVector(TP); 54 else { 55 assert((VT < MVT::LAST_VALUETYPE || VT == MVT::iPTR || 56 VT == MVT::iPTRAny || VT == MVT::Any) && "Not a concrete type!"); 57 TypeVec.push_back(VT); 58 } 59} 60 61 62EEVT::TypeSet::TypeSet(ArrayRef<MVT::SimpleValueType> VTList) { 63 assert(!VTList.empty() && "empty list?"); 64 TypeVec.append(VTList.begin(), VTList.end()); 65 66 if (!VTList.empty()) 67 assert(VTList[0] != MVT::iAny && VTList[0] != MVT::vAny && 68 VTList[0] != MVT::fAny); 69 70 // Verify no duplicates. 71 array_pod_sort(TypeVec.begin(), TypeVec.end()); 72 assert(std::unique(TypeVec.begin(), TypeVec.end()) == TypeVec.end()); 73} 74 75/// FillWithPossibleTypes - Set to all legal types and return true, only valid 76/// on completely unknown type sets. 77bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP, 78 bool (*Pred)(MVT::SimpleValueType), 79 const char *PredicateName) { 80 assert(isCompletelyUnknown()); 81 ArrayRef<MVT::SimpleValueType> LegalTypes = 82 TP.getDAGPatterns().getTargetInfo().getLegalValueTypes(); 83 84 if (TP.hasError()) 85 return false; 86 87 for (unsigned i = 0, e = LegalTypes.size(); i != e; ++i) 88 if (!Pred || Pred(LegalTypes[i])) 89 TypeVec.push_back(LegalTypes[i]); 90 91 // If we have nothing that matches the predicate, bail out. 92 if (TypeVec.empty()) { 93 TP.error("Type inference contradiction found, no " + 94 std::string(PredicateName) + " types found"); 95 return false; 96 } 97 // No need to sort with one element. 98 if (TypeVec.size() == 1) return true; 99 100 // Remove duplicates. 101 array_pod_sort(TypeVec.begin(), TypeVec.end()); 102 TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end()); 103 104 return true; 105} 106 107/// hasIntegerTypes - Return true if this TypeSet contains iAny or an 108/// integer value type. 109bool EEVT::TypeSet::hasIntegerTypes() const { 110 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 111 if (isInteger(TypeVec[i])) 112 return true; 113 return false; 114} 115 116/// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or 117/// a floating point value type. 118bool EEVT::TypeSet::hasFloatingPointTypes() const { 119 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 120 if (isFloatingPoint(TypeVec[i])) 121 return true; 122 return false; 123} 124 125/// hasScalarTypes - Return true if this TypeSet contains a scalar value type. 126bool EEVT::TypeSet::hasScalarTypes() const { 127 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 128 if (isScalar(TypeVec[i])) 129 return true; 130 return false; 131} 132 133/// hasVectorTypes - Return true if this TypeSet contains a vAny or a vector 134/// value type. 135bool EEVT::TypeSet::hasVectorTypes() const { 136 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 137 if (isVector(TypeVec[i])) 138 return true; 139 return false; 140} 141 142 143std::string EEVT::TypeSet::getName() const { 144 if (TypeVec.empty()) return "<empty>"; 145 146 std::string Result; 147 148 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) { 149 std::string VTName = llvm::getEnumName(TypeVec[i]); 150 // Strip off MVT:: prefix if present. 151 if (VTName.substr(0,5) == "MVT::") 152 VTName = VTName.substr(5); 153 if (i) Result += ':'; 154 Result += VTName; 155 } 156 157 if (TypeVec.size() == 1) 158 return Result; 159 return "{" + Result + "}"; 160} 161 162/// MergeInTypeInfo - This merges in type information from the specified 163/// argument. If 'this' changes, it returns true. If the two types are 164/// contradictory (e.g. merge f32 into i32) then this flags an error. 165bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ 166 if (InVT.isCompletelyUnknown() || *this == InVT || TP.hasError()) 167 return false; 168 169 if (isCompletelyUnknown()) { 170 *this = InVT; 171 return true; 172 } 173 174 assert(TypeVec.size() >= 1 && InVT.TypeVec.size() >= 1 && "No unknowns"); 175 176 // Handle the abstract cases, seeing if we can resolve them better. 177 switch (TypeVec[0]) { 178 default: break; 179 case MVT::iPTR: 180 case MVT::iPTRAny: 181 if (InVT.hasIntegerTypes()) { 182 EEVT::TypeSet InCopy(InVT); 183 InCopy.EnforceInteger(TP); 184 InCopy.EnforceScalar(TP); 185 186 if (InCopy.isConcrete()) { 187 // If the RHS has one integer type, upgrade iPTR to i32. 188 TypeVec[0] = InVT.TypeVec[0]; 189 return true; 190 } 191 192 // If the input has multiple scalar integers, this doesn't add any info. 193 if (!InCopy.isCompletelyUnknown()) 194 return false; 195 } 196 break; 197 } 198 199 // If the input constraint is iAny/iPTR and this is an integer type list, 200 // remove non-integer types from the list. 201 if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && 202 hasIntegerTypes()) { 203 bool MadeChange = EnforceInteger(TP); 204 205 // If we're merging in iPTR/iPTRAny and the node currently has a list of 206 // multiple different integer types, replace them with a single iPTR. 207 if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && 208 TypeVec.size() != 1) { 209 TypeVec.resize(1); 210 TypeVec[0] = InVT.TypeVec[0]; 211 MadeChange = true; 212 } 213 214 return MadeChange; 215 } 216 217 // If this is a type list and the RHS is a typelist as well, eliminate entries 218 // from this list that aren't in the other one. 219 bool MadeChange = false; 220 TypeSet InputSet(*this); 221 222 for (unsigned i = 0; i != TypeVec.size(); ++i) { 223 bool InInVT = false; 224 for (unsigned j = 0, e = InVT.TypeVec.size(); j != e; ++j) 225 if (TypeVec[i] == InVT.TypeVec[j]) { 226 InInVT = true; 227 break; 228 } 229 230 if (InInVT) continue; 231 TypeVec.erase(TypeVec.begin()+i--); 232 MadeChange = true; 233 } 234 235 // If we removed all of our types, we have a type contradiction. 236 if (!TypeVec.empty()) 237 return MadeChange; 238 239 // FIXME: Really want an SMLoc here! 240 TP.error("Type inference contradiction found, merging '" + 241 InVT.getName() + "' into '" + InputSet.getName() + "'"); 242 return false; 243} 244 245/// EnforceInteger - Remove all non-integer types from this set. 246bool EEVT::TypeSet::EnforceInteger(TreePattern &TP) { 247 if (TP.hasError()) 248 return false; 249 // If we know nothing, then get the full set. 250 if (TypeVec.empty()) 251 return FillWithPossibleTypes(TP, isInteger, "integer"); 252 if (!hasFloatingPointTypes()) 253 return false; 254 255 TypeSet InputSet(*this); 256 257 // Filter out all the fp types. 258 for (unsigned i = 0; i != TypeVec.size(); ++i) 259 if (!isInteger(TypeVec[i])) 260 TypeVec.erase(TypeVec.begin()+i--); 261 262 if (TypeVec.empty()) { 263 TP.error("Type inference contradiction found, '" + 264 InputSet.getName() + "' needs to be integer"); 265 return false; 266 } 267 return true; 268} 269 270/// EnforceFloatingPoint - Remove all integer types from this set. 271bool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) { 272 if (TP.hasError()) 273 return false; 274 // If we know nothing, then get the full set. 275 if (TypeVec.empty()) 276 return FillWithPossibleTypes(TP, isFloatingPoint, "floating point"); 277 278 if (!hasIntegerTypes()) 279 return false; 280 281 TypeSet InputSet(*this); 282 283 // Filter out all the fp types. 284 for (unsigned i = 0; i != TypeVec.size(); ++i) 285 if (!isFloatingPoint(TypeVec[i])) 286 TypeVec.erase(TypeVec.begin()+i--); 287 288 if (TypeVec.empty()) { 289 TP.error("Type inference contradiction found, '" + 290 InputSet.getName() + "' needs to be floating point"); 291 return false; 292 } 293 return true; 294} 295 296/// EnforceScalar - Remove all vector types from this. 297bool EEVT::TypeSet::EnforceScalar(TreePattern &TP) { 298 if (TP.hasError()) 299 return false; 300 301 // If we know nothing, then get the full set. 302 if (TypeVec.empty()) 303 return FillWithPossibleTypes(TP, isScalar, "scalar"); 304 305 if (!hasVectorTypes()) 306 return false; 307 308 TypeSet InputSet(*this); 309 310 // Filter out all the vector types. 311 for (unsigned i = 0; i != TypeVec.size(); ++i) 312 if (!isScalar(TypeVec[i])) 313 TypeVec.erase(TypeVec.begin()+i--); 314 315 if (TypeVec.empty()) { 316 TP.error("Type inference contradiction found, '" + 317 InputSet.getName() + "' needs to be scalar"); 318 return false; 319 } 320 return true; 321} 322 323/// EnforceVector - Remove all vector types from this. 324bool EEVT::TypeSet::EnforceVector(TreePattern &TP) { 325 if (TP.hasError()) 326 return false; 327 328 // If we know nothing, then get the full set. 329 if (TypeVec.empty()) 330 return FillWithPossibleTypes(TP, isVector, "vector"); 331 332 TypeSet InputSet(*this); 333 bool MadeChange = false; 334 335 // Filter out all the scalar types. 336 for (unsigned i = 0; i != TypeVec.size(); ++i) 337 if (!isVector(TypeVec[i])) { 338 TypeVec.erase(TypeVec.begin()+i--); 339 MadeChange = true; 340 } 341 342 if (TypeVec.empty()) { 343 TP.error("Type inference contradiction found, '" + 344 InputSet.getName() + "' needs to be a vector"); 345 return false; 346 } 347 return MadeChange; 348} 349 350 351 352/// EnforceSmallerThan - 'this' must be a smaller VT than Other. For vectors 353/// this shoud be based on the element type. Update this and other based on 354/// this information. 355bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { 356 if (TP.hasError()) 357 return false; 358 359 // Both operands must be integer or FP, but we don't care which. 360 bool MadeChange = false; 361 362 if (isCompletelyUnknown()) 363 MadeChange = FillWithPossibleTypes(TP); 364 365 if (Other.isCompletelyUnknown()) 366 MadeChange = Other.FillWithPossibleTypes(TP); 367 368 // If one side is known to be integer or known to be FP but the other side has 369 // no information, get at least the type integrality info in there. 370 if (!hasFloatingPointTypes()) 371 MadeChange |= Other.EnforceInteger(TP); 372 else if (!hasIntegerTypes()) 373 MadeChange |= Other.EnforceFloatingPoint(TP); 374 if (!Other.hasFloatingPointTypes()) 375 MadeChange |= EnforceInteger(TP); 376 else if (!Other.hasIntegerTypes()) 377 MadeChange |= EnforceFloatingPoint(TP); 378 379 assert(!isCompletelyUnknown() && !Other.isCompletelyUnknown() && 380 "Should have a type list now"); 381 382 // If one contains vectors but the other doesn't pull vectors out. 383 if (!hasVectorTypes()) 384 MadeChange |= Other.EnforceScalar(TP); 385 else if (!hasScalarTypes()) 386 MadeChange |= Other.EnforceVector(TP); 387 if (!Other.hasVectorTypes()) 388 MadeChange |= EnforceScalar(TP); 389 else if (!Other.hasScalarTypes()) 390 MadeChange |= EnforceVector(TP); 391 392 // This code does not currently handle nodes which have multiple types, 393 // where some types are integer, and some are fp. Assert that this is not 394 // the case. 395 assert(!(hasIntegerTypes() && hasFloatingPointTypes()) && 396 !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) && 397 "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); 398 399 if (TP.hasError()) 400 return false; 401 402 // Okay, find the smallest type from current set and remove anything the 403 // same or smaller from the other set. We need to ensure that the scalar 404 // type size is smaller than the scalar size of the smallest type. For 405 // vectors, we also need to make sure that the total size is no larger than 406 // the size of the smallest type. 407 TypeSet InputSet(Other); 408 MVT Smallest = TypeVec[0]; 409 for (unsigned i = 0; i != Other.TypeVec.size(); ++i) { 410 MVT OtherVT = Other.TypeVec[i]; 411 // Don't compare vector and non-vector types. 412 if (OtherVT.isVector() != Smallest.isVector()) 413 continue; 414 // The getSizeInBits() check here is only needed for vectors, but is 415 // a subset of the scalar check for scalars so no need to qualify. 416 if (OtherVT.getScalarSizeInBits() <= Smallest.getScalarSizeInBits() || 417 OtherVT.getSizeInBits() < Smallest.getSizeInBits()) { 418 Other.TypeVec.erase(Other.TypeVec.begin()+i--); 419 MadeChange = true; 420 } 421 } 422 423 if (Other.TypeVec.empty()) { 424 TP.error("Type inference contradiction found, '" + InputSet.getName() + 425 "' has nothing larger than '" + getName() +"'!"); 426 return false; 427 } 428 429 // Okay, find the largest type from the other set and remove anything the 430 // same or smaller from the current set. We need to ensure that the scalar 431 // type size is larger than the scalar size of the largest type. For 432 // vectors, we also need to make sure that the total size is no smaller than 433 // the size of the largest type. 434 InputSet = TypeSet(*this); 435 MVT Largest = Other.TypeVec[Other.TypeVec.size()-1]; 436 for (unsigned i = 0; i != TypeVec.size(); ++i) { 437 MVT OtherVT = TypeVec[i]; 438 // Don't compare vector and non-vector types. 439 if (OtherVT.isVector() != Largest.isVector()) 440 continue; 441 // The getSizeInBits() check here is only needed for vectors, but is 442 // a subset of the scalar check for scalars so no need to qualify. 443 if (OtherVT.getScalarSizeInBits() >= Largest.getScalarSizeInBits() || 444 OtherVT.getSizeInBits() > Largest.getSizeInBits()) { 445 TypeVec.erase(TypeVec.begin()+i--); 446 MadeChange = true; 447 } 448 } 449 450 if (TypeVec.empty()) { 451 TP.error("Type inference contradiction found, '" + InputSet.getName() + 452 "' has nothing smaller than '" + Other.getName() +"'!"); 453 return false; 454 } 455 456 return MadeChange; 457} 458 459/// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 460/// whose element is specified by VTOperand. 461bool EEVT::TypeSet::EnforceVectorEltTypeIs(MVT::SimpleValueType VT, 462 TreePattern &TP) { 463 bool MadeChange = false; 464 465 MadeChange |= EnforceVector(TP); 466 467 TypeSet InputSet(*this); 468 469 // Filter out all the types which don't have the right element type. 470 for (unsigned i = 0; i != TypeVec.size(); ++i) { 471 assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); 472 if (MVT(TypeVec[i]).getVectorElementType().SimpleTy != VT) { 473 TypeVec.erase(TypeVec.begin()+i--); 474 MadeChange = true; 475 } 476 } 477 478 if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! 479 TP.error("Type inference contradiction found, forcing '" + 480 InputSet.getName() + "' to have a vector element"); 481 return false; 482 } 483 484 return MadeChange; 485} 486 487/// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 488/// whose element is specified by VTOperand. 489bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand, 490 TreePattern &TP) { 491 if (TP.hasError()) 492 return false; 493 494 // "This" must be a vector and "VTOperand" must be a scalar. 495 bool MadeChange = false; 496 MadeChange |= EnforceVector(TP); 497 MadeChange |= VTOperand.EnforceScalar(TP); 498 499 // If we know the vector type, it forces the scalar to agree. 500 if (isConcrete()) { 501 MVT IVT = getConcrete(); 502 IVT = IVT.getVectorElementType(); 503 return MadeChange | 504 VTOperand.MergeInTypeInfo(IVT.SimpleTy, TP); 505 } 506 507 // If the scalar type is known, filter out vector types whose element types 508 // disagree. 509 if (!VTOperand.isConcrete()) 510 return MadeChange; 511 512 MVT::SimpleValueType VT = VTOperand.getConcrete(); 513 514 TypeSet InputSet(*this); 515 516 // Filter out all the types which don't have the right element type. 517 for (unsigned i = 0; i != TypeVec.size(); ++i) { 518 assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); 519 if (MVT(TypeVec[i]).getVectorElementType().SimpleTy != VT) { 520 TypeVec.erase(TypeVec.begin()+i--); 521 MadeChange = true; 522 } 523 } 524 525 if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! 526 TP.error("Type inference contradiction found, forcing '" + 527 InputSet.getName() + "' to have a vector element"); 528 return false; 529 } 530 return MadeChange; 531} 532 533/// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to be a 534/// vector type specified by VTOperand. 535bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, 536 TreePattern &TP) { 537 if (TP.hasError()) 538 return false; 539 540 // "This" must be a vector and "VTOperand" must be a vector. 541 bool MadeChange = false; 542 MadeChange |= EnforceVector(TP); 543 MadeChange |= VTOperand.EnforceVector(TP); 544 545 // If one side is known to be integer or known to be FP but the other side has 546 // no information, get at least the type integrality info in there. 547 if (!hasFloatingPointTypes()) 548 MadeChange |= VTOperand.EnforceInteger(TP); 549 else if (!hasIntegerTypes()) 550 MadeChange |= VTOperand.EnforceFloatingPoint(TP); 551 if (!VTOperand.hasFloatingPointTypes()) 552 MadeChange |= EnforceInteger(TP); 553 else if (!VTOperand.hasIntegerTypes()) 554 MadeChange |= EnforceFloatingPoint(TP); 555 556 assert(!isCompletelyUnknown() && !VTOperand.isCompletelyUnknown() && 557 "Should have a type list now"); 558 559 // If we know the vector type, it forces the scalar types to agree. 560 // Also force one vector to have more elements than the other. 561 if (isConcrete()) { 562 MVT IVT = getConcrete(); 563 unsigned NumElems = IVT.getVectorNumElements(); 564 IVT = IVT.getVectorElementType(); 565 566 EEVT::TypeSet EltTypeSet(IVT.SimpleTy, TP); 567 MadeChange |= VTOperand.EnforceVectorEltTypeIs(EltTypeSet, TP); 568 569 // Only keep types that have less elements than VTOperand. 570 TypeSet InputSet(VTOperand); 571 572 for (unsigned i = 0; i != VTOperand.TypeVec.size(); ++i) { 573 assert(isVector(VTOperand.TypeVec[i]) && "EnforceVector didn't work"); 574 if (MVT(VTOperand.TypeVec[i]).getVectorNumElements() >= NumElems) { 575 VTOperand.TypeVec.erase(VTOperand.TypeVec.begin()+i--); 576 MadeChange = true; 577 } 578 } 579 if (VTOperand.TypeVec.empty()) { // FIXME: Really want an SMLoc here! 580 TP.error("Type inference contradiction found, forcing '" + 581 InputSet.getName() + "' to have less vector elements than '" + 582 getName() + "'"); 583 return false; 584 } 585 } else if (VTOperand.isConcrete()) { 586 MVT IVT = VTOperand.getConcrete(); 587 unsigned NumElems = IVT.getVectorNumElements(); 588 IVT = IVT.getVectorElementType(); 589 590 EEVT::TypeSet EltTypeSet(IVT.SimpleTy, TP); 591 MadeChange |= EnforceVectorEltTypeIs(EltTypeSet, TP); 592 593 // Only keep types that have more elements than 'this'. 594 TypeSet InputSet(*this); 595 596 for (unsigned i = 0; i != TypeVec.size(); ++i) { 597 assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); 598 if (MVT(TypeVec[i]).getVectorNumElements() <= NumElems) { 599 TypeVec.erase(TypeVec.begin()+i--); 600 MadeChange = true; 601 } 602 } 603 if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! 604 TP.error("Type inference contradiction found, forcing '" + 605 InputSet.getName() + "' to have more vector elements than '" + 606 VTOperand.getName() + "'"); 607 return false; 608 } 609 } 610 611 return MadeChange; 612} 613 614/// EnforceVectorSameNumElts - 'this' is now constrainted to 615/// be a vector with same num elements as VTOperand. 616bool EEVT::TypeSet::EnforceVectorSameNumElts(EEVT::TypeSet &VTOperand, 617 TreePattern &TP) { 618 if (TP.hasError()) 619 return false; 620 621 // "This" must be a vector and "VTOperand" must be a vector. 622 bool MadeChange = false; 623 MadeChange |= EnforceVector(TP); 624 MadeChange |= VTOperand.EnforceVector(TP); 625 626 // If we know one of the vector types, it forces the other type to agree. 627 if (isConcrete()) { 628 MVT IVT = getConcrete(); 629 unsigned NumElems = IVT.getVectorNumElements(); 630 631 // Only keep types that have same elements as VTOperand. 632 TypeSet InputSet(VTOperand); 633 634 for (unsigned i = 0; i != VTOperand.TypeVec.size(); ++i) { 635 assert(isVector(VTOperand.TypeVec[i]) && "EnforceVector didn't work"); 636 if (MVT(VTOperand.TypeVec[i]).getVectorNumElements() != NumElems) { 637 VTOperand.TypeVec.erase(VTOperand.TypeVec.begin()+i--); 638 MadeChange = true; 639 } 640 } 641 if (VTOperand.TypeVec.empty()) { // FIXME: Really want an SMLoc here! 642 TP.error("Type inference contradiction found, forcing '" + 643 InputSet.getName() + "' to have same number elements as '" + 644 getName() + "'"); 645 return false; 646 } 647 } else if (VTOperand.isConcrete()) { 648 MVT IVT = VTOperand.getConcrete(); 649 unsigned NumElems = IVT.getVectorNumElements(); 650 651 // Only keep types that have same elements as 'this'. 652 TypeSet InputSet(*this); 653 654 for (unsigned i = 0; i != TypeVec.size(); ++i) { 655 assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); 656 if (MVT(TypeVec[i]).getVectorNumElements() != NumElems) { 657 TypeVec.erase(TypeVec.begin()+i--); 658 MadeChange = true; 659 } 660 } 661 if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! 662 TP.error("Type inference contradiction found, forcing '" + 663 InputSet.getName() + "' to have same number elements than '" + 664 VTOperand.getName() + "'"); 665 return false; 666 } 667 } 668 669 return MadeChange; 670} 671 672//===----------------------------------------------------------------------===// 673// Helpers for working with extended types. 674 675/// Dependent variable map for CodeGenDAGPattern variant generation 676typedef std::map<std::string, int> DepVarMap; 677 678/// Const iterator shorthand for DepVarMap 679typedef DepVarMap::const_iterator DepVarMap_citer; 680 681static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 682 if (N->isLeaf()) { 683 if (isa<DefInit>(N->getLeafValue())) 684 DepMap[N->getName()]++; 685 } else { 686 for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 687 FindDepVarsOf(N->getChild(i), DepMap); 688 } 689} 690 691/// Find dependent variables within child patterns 692static void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 693 DepVarMap depcounts; 694 FindDepVarsOf(N, depcounts); 695 for (DepVarMap_citer i = depcounts.begin(); i != depcounts.end(); ++i) { 696 if (i->second > 1) // std::pair<std::string, int> 697 DepVars.insert(i->first); 698 } 699} 700 701#ifndef NDEBUG 702/// Dump the dependent variable set: 703static void DumpDepVars(MultipleUseVarSet &DepVars) { 704 if (DepVars.empty()) { 705 DEBUG(errs() << "<empty set>"); 706 } else { 707 DEBUG(errs() << "[ "); 708 for (MultipleUseVarSet::const_iterator i = DepVars.begin(), 709 e = DepVars.end(); i != e; ++i) { 710 DEBUG(errs() << (*i) << " "); 711 } 712 DEBUG(errs() << "]"); 713 } 714} 715#endif 716 717 718//===----------------------------------------------------------------------===// 719// TreePredicateFn Implementation 720//===----------------------------------------------------------------------===// 721 722/// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 723TreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) { 724 assert((getPredCode().empty() || getImmCode().empty()) && 725 ".td file corrupt: can't have a node predicate *and* an imm predicate"); 726} 727 728std::string TreePredicateFn::getPredCode() const { 729 return PatFragRec->getRecord()->getValueAsString("PredicateCode"); 730} 731 732std::string TreePredicateFn::getImmCode() const { 733 return PatFragRec->getRecord()->getValueAsString("ImmediateCode"); 734} 735 736 737/// isAlwaysTrue - Return true if this is a noop predicate. 738bool TreePredicateFn::isAlwaysTrue() const { 739 return getPredCode().empty() && getImmCode().empty(); 740} 741 742/// Return the name to use in the generated code to reference this, this is 743/// "Predicate_foo" if from a pattern fragment "foo". 744std::string TreePredicateFn::getFnName() const { 745 return "Predicate_" + PatFragRec->getRecord()->getName(); 746} 747 748/// getCodeToRunOnSDNode - Return the code for the function body that 749/// evaluates this predicate. The argument is expected to be in "Node", 750/// not N. This handles casting and conversion to a concrete node type as 751/// appropriate. 752std::string TreePredicateFn::getCodeToRunOnSDNode() const { 753 // Handle immediate predicates first. 754 std::string ImmCode = getImmCode(); 755 if (!ImmCode.empty()) { 756 std::string Result = 757 " int64_t Imm = cast<ConstantSDNode>(Node)->getSExtValue();\n"; 758 return Result + ImmCode; 759 } 760 761 // Handle arbitrary node predicates. 762 assert(!getPredCode().empty() && "Don't have any predicate code!"); 763 std::string ClassName; 764 if (PatFragRec->getOnlyTree()->isLeaf()) 765 ClassName = "SDNode"; 766 else { 767 Record *Op = PatFragRec->getOnlyTree()->getOperator(); 768 ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName(); 769 } 770 std::string Result; 771 if (ClassName == "SDNode") 772 Result = " SDNode *N = Node;\n"; 773 else 774 Result = " " + ClassName + "*N = cast<" + ClassName + ">(Node);\n"; 775 776 return Result + getPredCode(); 777} 778 779//===----------------------------------------------------------------------===// 780// PatternToMatch implementation 781// 782 783 784/// getPatternSize - Return the 'size' of this pattern. We want to match large 785/// patterns before small ones. This is used to determine the size of a 786/// pattern. 787static unsigned getPatternSize(const TreePatternNode *P, 788 const CodeGenDAGPatterns &CGP) { 789 unsigned Size = 3; // The node itself. 790 // If the root node is a ConstantSDNode, increases its size. 791 // e.g. (set R32:$dst, 0). 792 if (P->isLeaf() && isa<IntInit>(P->getLeafValue())) 793 Size += 2; 794 795 // FIXME: This is a hack to statically increase the priority of patterns 796 // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD. 797 // Later we can allow complexity / cost for each pattern to be (optionally) 798 // specified. To get best possible pattern match we'll need to dynamically 799 // calculate the complexity of all patterns a dag can potentially map to. 800 const ComplexPattern *AM = P->getComplexPatternInfo(CGP); 801 if (AM) { 802 Size += AM->getNumOperands() * 3; 803 804 // We don't want to count any children twice, so return early. 805 return Size; 806 } 807 808 // If this node has some predicate function that must match, it adds to the 809 // complexity of this node. 810 if (!P->getPredicateFns().empty()) 811 ++Size; 812 813 // Count children in the count if they are also nodes. 814 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { 815 TreePatternNode *Child = P->getChild(i); 816 if (!Child->isLeaf() && Child->getNumTypes() && 817 Child->getType(0) != MVT::Other) 818 Size += getPatternSize(Child, CGP); 819 else if (Child->isLeaf()) { 820 if (isa<IntInit>(Child->getLeafValue())) 821 Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). 822 else if (Child->getComplexPatternInfo(CGP)) 823 Size += getPatternSize(Child, CGP); 824 else if (!Child->getPredicateFns().empty()) 825 ++Size; 826 } 827 } 828 829 return Size; 830} 831 832/// Compute the complexity metric for the input pattern. This roughly 833/// corresponds to the number of nodes that are covered. 834int PatternToMatch:: 835getPatternComplexity(const CodeGenDAGPatterns &CGP) const { 836 return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity(); 837} 838 839 840/// getPredicateCheck - Return a single string containing all of this 841/// pattern's predicates concatenated with "&&" operators. 842/// 843std::string PatternToMatch::getPredicateCheck() const { 844 std::string PredicateCheck; 845 for (Init *I : Predicates->getValues()) { 846 if (DefInit *Pred = dyn_cast<DefInit>(I)) { 847 Record *Def = Pred->getDef(); 848 if (!Def->isSubClassOf("Predicate")) { 849#ifndef NDEBUG 850 Def->dump(); 851#endif 852 llvm_unreachable("Unknown predicate type!"); 853 } 854 if (!PredicateCheck.empty()) 855 PredicateCheck += " && "; 856 PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; 857 } 858 } 859 860 return PredicateCheck; 861} 862 863//===----------------------------------------------------------------------===// 864// SDTypeConstraint implementation 865// 866 867SDTypeConstraint::SDTypeConstraint(Record *R) { 868 OperandNo = R->getValueAsInt("OperandNum"); 869 870 if (R->isSubClassOf("SDTCisVT")) { 871 ConstraintType = SDTCisVT; 872 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 873 if (x.SDTCisVT_Info.VT == MVT::isVoid) 874 PrintFatalError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT"); 875 876 } else if (R->isSubClassOf("SDTCisPtrTy")) { 877 ConstraintType = SDTCisPtrTy; 878 } else if (R->isSubClassOf("SDTCisInt")) { 879 ConstraintType = SDTCisInt; 880 } else if (R->isSubClassOf("SDTCisFP")) { 881 ConstraintType = SDTCisFP; 882 } else if (R->isSubClassOf("SDTCisVec")) { 883 ConstraintType = SDTCisVec; 884 } else if (R->isSubClassOf("SDTCisSameAs")) { 885 ConstraintType = SDTCisSameAs; 886 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 887 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 888 ConstraintType = SDTCisVTSmallerThanOp; 889 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 890 R->getValueAsInt("OtherOperandNum"); 891 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 892 ConstraintType = SDTCisOpSmallerThanOp; 893 x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 894 R->getValueAsInt("BigOperandNum"); 895 } else if (R->isSubClassOf("SDTCisEltOfVec")) { 896 ConstraintType = SDTCisEltOfVec; 897 x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); 898 } else if (R->isSubClassOf("SDTCisSubVecOfVec")) { 899 ConstraintType = SDTCisSubVecOfVec; 900 x.SDTCisSubVecOfVec_Info.OtherOperandNum = 901 R->getValueAsInt("OtherOpNum"); 902 } else if (R->isSubClassOf("SDTCVecEltisVT")) { 903 ConstraintType = SDTCVecEltisVT; 904 x.SDTCVecEltisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 905 if (MVT(x.SDTCVecEltisVT_Info.VT).isVector()) 906 PrintFatalError(R->getLoc(), "Cannot use vector type as SDTCVecEltisVT"); 907 if (!MVT(x.SDTCVecEltisVT_Info.VT).isInteger() && 908 !MVT(x.SDTCVecEltisVT_Info.VT).isFloatingPoint()) 909 PrintFatalError(R->getLoc(), "Must use integer or floating point type " 910 "as SDTCVecEltisVT"); 911 } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) { 912 ConstraintType = SDTCisSameNumEltsAs; 913 x.SDTCisSameNumEltsAs_Info.OtherOperandNum = 914 R->getValueAsInt("OtherOperandNum"); 915 } else { 916 PrintFatalError("Unrecognized SDTypeConstraint '" + R->getName() + "'!\n"); 917 } 918} 919 920/// getOperandNum - Return the node corresponding to operand #OpNo in tree 921/// N, and the result number in ResNo. 922static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, 923 const SDNodeInfo &NodeInfo, 924 unsigned &ResNo) { 925 unsigned NumResults = NodeInfo.getNumResults(); 926 if (OpNo < NumResults) { 927 ResNo = OpNo; 928 return N; 929 } 930 931 OpNo -= NumResults; 932 933 if (OpNo >= N->getNumChildren()) { 934 std::string S; 935 raw_string_ostream OS(S); 936 OS << "Invalid operand number in type constraint " 937 << (OpNo+NumResults) << " "; 938 N->print(OS); 939 PrintFatalError(OS.str()); 940 } 941 942 return N->getChild(OpNo); 943} 944 945/// ApplyTypeConstraint - Given a node in a pattern, apply this type 946/// constraint to the nodes operands. This returns true if it makes a 947/// change, false otherwise. If a type contradiction is found, flag an error. 948bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 949 const SDNodeInfo &NodeInfo, 950 TreePattern &TP) const { 951 if (TP.hasError()) 952 return false; 953 954 unsigned ResNo = 0; // The result number being referenced. 955 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo); 956 957 switch (ConstraintType) { 958 case SDTCisVT: 959 // Operand must be a particular type. 960 return NodeToApply->UpdateNodeType(ResNo, x.SDTCisVT_Info.VT, TP); 961 case SDTCisPtrTy: 962 // Operand must be same as target pointer type. 963 return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP); 964 case SDTCisInt: 965 // Require it to be one of the legal integer VTs. 966 return NodeToApply->getExtType(ResNo).EnforceInteger(TP); 967 case SDTCisFP: 968 // Require it to be one of the legal fp VTs. 969 return NodeToApply->getExtType(ResNo).EnforceFloatingPoint(TP); 970 case SDTCisVec: 971 // Require it to be one of the legal vector VTs. 972 return NodeToApply->getExtType(ResNo).EnforceVector(TP); 973 case SDTCisSameAs: { 974 unsigned OResNo = 0; 975 TreePatternNode *OtherNode = 976 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); 977 return NodeToApply->UpdateNodeType(ResNo, OtherNode->getExtType(OResNo),TP)| 978 OtherNode->UpdateNodeType(OResNo,NodeToApply->getExtType(ResNo),TP); 979 } 980 case SDTCisVTSmallerThanOp: { 981 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 982 // have an integer type that is smaller than the VT. 983 if (!NodeToApply->isLeaf() || 984 !isa<DefInit>(NodeToApply->getLeafValue()) || 985 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 986 ->isSubClassOf("ValueType")) { 987 TP.error(N->getOperator()->getName() + " expects a VT operand!"); 988 return false; 989 } 990 MVT::SimpleValueType VT = 991 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()); 992 993 EEVT::TypeSet TypeListTmp(VT, TP); 994 995 unsigned OResNo = 0; 996 TreePatternNode *OtherNode = 997 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo, 998 OResNo); 999 1000 return TypeListTmp.EnforceSmallerThan(OtherNode->getExtType(OResNo), TP); 1001 } 1002 case SDTCisOpSmallerThanOp: { 1003 unsigned BResNo = 0; 1004 TreePatternNode *BigOperand = 1005 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo, 1006 BResNo); 1007 return NodeToApply->getExtType(ResNo). 1008 EnforceSmallerThan(BigOperand->getExtType(BResNo), TP); 1009 } 1010 case SDTCisEltOfVec: { 1011 unsigned VResNo = 0; 1012 TreePatternNode *VecOperand = 1013 getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo, 1014 VResNo); 1015 1016 // Filter vector types out of VecOperand that don't have the right element 1017 // type. 1018 return VecOperand->getExtType(VResNo). 1019 EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), TP); 1020 } 1021 case SDTCisSubVecOfVec: { 1022 unsigned VResNo = 0; 1023 TreePatternNode *BigVecOperand = 1024 getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo, 1025 VResNo); 1026 1027 // Filter vector types out of BigVecOperand that don't have the 1028 // right subvector type. 1029 return BigVecOperand->getExtType(VResNo). 1030 EnforceVectorSubVectorTypeIs(NodeToApply->getExtType(ResNo), TP); 1031 } 1032 case SDTCVecEltisVT: { 1033 return NodeToApply->getExtType(ResNo). 1034 EnforceVectorEltTypeIs(x.SDTCVecEltisVT_Info.VT, TP); 1035 } 1036 case SDTCisSameNumEltsAs: { 1037 unsigned OResNo = 0; 1038 TreePatternNode *OtherNode = 1039 getOperandNum(x.SDTCisSameNumEltsAs_Info.OtherOperandNum, 1040 N, NodeInfo, OResNo); 1041 return OtherNode->getExtType(OResNo). 1042 EnforceVectorSameNumElts(NodeToApply->getExtType(ResNo), TP); 1043 } 1044 } 1045 llvm_unreachable("Invalid ConstraintType!"); 1046} 1047 1048// Update the node type to match an instruction operand or result as specified 1049// in the ins or outs lists on the instruction definition. Return true if the 1050// type was actually changed. 1051bool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo, 1052 Record *Operand, 1053 TreePattern &TP) { 1054 // The 'unknown' operand indicates that types should be inferred from the 1055 // context. 1056 if (Operand->isSubClassOf("unknown_class")) 1057 return false; 1058 1059 // The Operand class specifies a type directly. 1060 if (Operand->isSubClassOf("Operand")) 1061 return UpdateNodeType(ResNo, getValueType(Operand->getValueAsDef("Type")), 1062 TP); 1063 1064 // PointerLikeRegClass has a type that is determined at runtime. 1065 if (Operand->isSubClassOf("PointerLikeRegClass")) 1066 return UpdateNodeType(ResNo, MVT::iPTR, TP); 1067 1068 // Both RegisterClass and RegisterOperand operands derive their types from a 1069 // register class def. 1070 Record *RC = nullptr; 1071 if (Operand->isSubClassOf("RegisterClass")) 1072 RC = Operand; 1073 else if (Operand->isSubClassOf("RegisterOperand")) 1074 RC = Operand->getValueAsDef("RegClass"); 1075 1076 assert(RC && "Unknown operand type"); 1077 CodeGenTarget &Tgt = TP.getDAGPatterns().getTargetInfo(); 1078 return UpdateNodeType(ResNo, Tgt.getRegisterClass(RC).getValueTypes(), TP); 1079} 1080 1081 1082//===----------------------------------------------------------------------===// 1083// SDNodeInfo implementation 1084// 1085SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { 1086 EnumName = R->getValueAsString("Opcode"); 1087 SDClassName = R->getValueAsString("SDClass"); 1088 Record *TypeProfile = R->getValueAsDef("TypeProfile"); 1089 NumResults = TypeProfile->getValueAsInt("NumResults"); 1090 NumOperands = TypeProfile->getValueAsInt("NumOperands"); 1091 1092 // Parse the properties. 1093 Properties = 0; 1094 std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties"); 1095 for (unsigned i = 0, e = PropList.size(); i != e; ++i) { 1096 if (PropList[i]->getName() == "SDNPCommutative") { 1097 Properties |= 1 << SDNPCommutative; 1098 } else if (PropList[i]->getName() == "SDNPAssociative") { 1099 Properties |= 1 << SDNPAssociative; 1100 } else if (PropList[i]->getName() == "SDNPHasChain") { 1101 Properties |= 1 << SDNPHasChain; 1102 } else if (PropList[i]->getName() == "SDNPOutGlue") { 1103 Properties |= 1 << SDNPOutGlue; 1104 } else if (PropList[i]->getName() == "SDNPInGlue") { 1105 Properties |= 1 << SDNPInGlue; 1106 } else if (PropList[i]->getName() == "SDNPOptInGlue") { 1107 Properties |= 1 << SDNPOptInGlue; 1108 } else if (PropList[i]->getName() == "SDNPMayStore") { 1109 Properties |= 1 << SDNPMayStore; 1110 } else if (PropList[i]->getName() == "SDNPMayLoad") { 1111 Properties |= 1 << SDNPMayLoad; 1112 } else if (PropList[i]->getName() == "SDNPSideEffect") { 1113 Properties |= 1 << SDNPSideEffect; 1114 } else if (PropList[i]->getName() == "SDNPMemOperand") { 1115 Properties |= 1 << SDNPMemOperand; 1116 } else if (PropList[i]->getName() == "SDNPVariadic") { 1117 Properties |= 1 << SDNPVariadic; 1118 } else { 1119 PrintFatalError("Unknown SD Node property '" + 1120 PropList[i]->getName() + "' on node '" + 1121 R->getName() + "'!"); 1122 } 1123 } 1124 1125 1126 // Parse the type constraints. 1127 std::vector<Record*> ConstraintList = 1128 TypeProfile->getValueAsListOfDefs("Constraints"); 1129 TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); 1130} 1131 1132/// getKnownType - If the type constraints on this node imply a fixed type 1133/// (e.g. all stores return void, etc), then return it as an 1134/// MVT::SimpleValueType. Otherwise, return EEVT::Other. 1135MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { 1136 unsigned NumResults = getNumResults(); 1137 assert(NumResults <= 1 && 1138 "We only work with nodes with zero or one result so far!"); 1139 assert(ResNo == 0 && "Only handles single result nodes so far"); 1140 1141 for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) { 1142 // Make sure that this applies to the correct node result. 1143 if (TypeConstraints[i].OperandNo >= NumResults) // FIXME: need value # 1144 continue; 1145 1146 switch (TypeConstraints[i].ConstraintType) { 1147 default: break; 1148 case SDTypeConstraint::SDTCisVT: 1149 return TypeConstraints[i].x.SDTCisVT_Info.VT; 1150 case SDTypeConstraint::SDTCisPtrTy: 1151 return MVT::iPTR; 1152 } 1153 } 1154 return MVT::Other; 1155} 1156 1157//===----------------------------------------------------------------------===// 1158// TreePatternNode implementation 1159// 1160 1161TreePatternNode::~TreePatternNode() { 1162#if 0 // FIXME: implement refcounted tree nodes! 1163 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1164 delete getChild(i); 1165#endif 1166} 1167 1168static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { 1169 if (Operator->getName() == "set" || 1170 Operator->getName() == "implicit") 1171 return 0; // All return nothing. 1172 1173 if (Operator->isSubClassOf("Intrinsic")) 1174 return CDP.getIntrinsic(Operator).IS.RetVTs.size(); 1175 1176 if (Operator->isSubClassOf("SDNode")) 1177 return CDP.getSDNodeInfo(Operator).getNumResults(); 1178 1179 if (Operator->isSubClassOf("PatFrag")) { 1180 // If we've already parsed this pattern fragment, get it. Otherwise, handle 1181 // the forward reference case where one pattern fragment references another 1182 // before it is processed. 1183 if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) 1184 return PFRec->getOnlyTree()->getNumTypes(); 1185 1186 // Get the result tree. 1187 DagInit *Tree = Operator->getValueAsDag("Fragment"); 1188 Record *Op = nullptr; 1189 if (Tree) 1190 if (DefInit *DI = dyn_cast<DefInit>(Tree->getOperator())) 1191 Op = DI->getDef(); 1192 assert(Op && "Invalid Fragment"); 1193 return GetNumNodeResults(Op, CDP); 1194 } 1195 1196 if (Operator->isSubClassOf("Instruction")) { 1197 CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator); 1198 1199 unsigned NumDefsToAdd = InstInfo.Operands.NumDefs; 1200 1201 // Subtract any defaulted outputs. 1202 for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) { 1203 Record *OperandNode = InstInfo.Operands[i].Rec; 1204 1205 if (OperandNode->isSubClassOf("OperandWithDefaultOps") && 1206 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 1207 --NumDefsToAdd; 1208 } 1209 1210 // Add on one implicit def if it has a resolvable type. 1211 if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other) 1212 ++NumDefsToAdd; 1213 return NumDefsToAdd; 1214 } 1215 1216 if (Operator->isSubClassOf("SDNodeXForm")) 1217 return 1; // FIXME: Generalize SDNodeXForm 1218 1219 if (Operator->isSubClassOf("ValueType")) 1220 return 1; // A type-cast of one result. 1221 1222 if (Operator->isSubClassOf("ComplexPattern")) 1223 return 1; 1224 1225 Operator->dump(); 1226 PrintFatalError("Unhandled node in GetNumNodeResults"); 1227} 1228 1229void TreePatternNode::print(raw_ostream &OS) const { 1230 if (isLeaf()) 1231 OS << *getLeafValue(); 1232 else 1233 OS << '(' << getOperator()->getName(); 1234 1235 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1236 OS << ':' << getExtType(i).getName(); 1237 1238 if (!isLeaf()) { 1239 if (getNumChildren() != 0) { 1240 OS << " "; 1241 getChild(0)->print(OS); 1242 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 1243 OS << ", "; 1244 getChild(i)->print(OS); 1245 } 1246 } 1247 OS << ")"; 1248 } 1249 1250 for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i) 1251 OS << "<<P:" << PredicateFns[i].getFnName() << ">>"; 1252 if (TransformFn) 1253 OS << "<<X:" << TransformFn->getName() << ">>"; 1254 if (!getName().empty()) 1255 OS << ":$" << getName(); 1256 1257} 1258void TreePatternNode::dump() const { 1259 print(errs()); 1260} 1261 1262/// isIsomorphicTo - Return true if this node is recursively 1263/// isomorphic to the specified node. For this comparison, the node's 1264/// entire state is considered. The assigned name is ignored, since 1265/// nodes with differing names are considered isomorphic. However, if 1266/// the assigned name is present in the dependent variable set, then 1267/// the assigned name is considered significant and the node is 1268/// isomorphic if the names match. 1269bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 1270 const MultipleUseVarSet &DepVars) const { 1271 if (N == this) return true; 1272 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 1273 getPredicateFns() != N->getPredicateFns() || 1274 getTransformFn() != N->getTransformFn()) 1275 return false; 1276 1277 if (isLeaf()) { 1278 if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) { 1279 if (DefInit *NDI = dyn_cast<DefInit>(N->getLeafValue())) { 1280 return ((DI->getDef() == NDI->getDef()) 1281 && (DepVars.find(getName()) == DepVars.end() 1282 || getName() == N->getName())); 1283 } 1284 } 1285 return getLeafValue() == N->getLeafValue(); 1286 } 1287 1288 if (N->getOperator() != getOperator() || 1289 N->getNumChildren() != getNumChildren()) return false; 1290 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1291 if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 1292 return false; 1293 return true; 1294} 1295 1296/// clone - Make a copy of this tree and all of its children. 1297/// 1298TreePatternNode *TreePatternNode::clone() const { 1299 TreePatternNode *New; 1300 if (isLeaf()) { 1301 New = new TreePatternNode(getLeafValue(), getNumTypes()); 1302 } else { 1303 std::vector<TreePatternNode*> CChildren; 1304 CChildren.reserve(Children.size()); 1305 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1306 CChildren.push_back(getChild(i)->clone()); 1307 New = new TreePatternNode(getOperator(), CChildren, getNumTypes()); 1308 } 1309 New->setName(getName()); 1310 New->Types = Types; 1311 New->setPredicateFns(getPredicateFns()); 1312 New->setTransformFn(getTransformFn()); 1313 return New; 1314} 1315 1316/// RemoveAllTypes - Recursively strip all the types of this tree. 1317void TreePatternNode::RemoveAllTypes() { 1318 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1319 Types[i] = EEVT::TypeSet(); // Reset to unknown type. 1320 if (isLeaf()) return; 1321 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1322 getChild(i)->RemoveAllTypes(); 1323} 1324 1325 1326/// SubstituteFormalArguments - Replace the formal arguments in this tree 1327/// with actual values specified by ArgMap. 1328void TreePatternNode:: 1329SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) { 1330 if (isLeaf()) return; 1331 1332 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1333 TreePatternNode *Child = getChild(i); 1334 if (Child->isLeaf()) { 1335 Init *Val = Child->getLeafValue(); 1336 // Note that, when substituting into an output pattern, Val might be an 1337 // UnsetInit. 1338 if (isa<UnsetInit>(Val) || (isa<DefInit>(Val) && 1339 cast<DefInit>(Val)->getDef()->getName() == "node")) { 1340 // We found a use of a formal argument, replace it with its value. 1341 TreePatternNode *NewChild = ArgMap[Child->getName()]; 1342 assert(NewChild && "Couldn't find formal argument!"); 1343 assert((Child->getPredicateFns().empty() || 1344 NewChild->getPredicateFns() == Child->getPredicateFns()) && 1345 "Non-empty child predicate clobbered!"); 1346 setChild(i, NewChild); 1347 } 1348 } else { 1349 getChild(i)->SubstituteFormalArguments(ArgMap); 1350 } 1351 } 1352} 1353 1354 1355/// InlinePatternFragments - If this pattern refers to any pattern 1356/// fragments, inline them into place, giving us a pattern without any 1357/// PatFrag references. 1358TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { 1359 if (TP.hasError()) 1360 return nullptr; 1361 1362 if (isLeaf()) 1363 return this; // nothing to do. 1364 Record *Op = getOperator(); 1365 1366 if (!Op->isSubClassOf("PatFrag")) { 1367 // Just recursively inline children nodes. 1368 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1369 TreePatternNode *Child = getChild(i); 1370 TreePatternNode *NewChild = Child->InlinePatternFragments(TP); 1371 1372 assert((Child->getPredicateFns().empty() || 1373 NewChild->getPredicateFns() == Child->getPredicateFns()) && 1374 "Non-empty child predicate clobbered!"); 1375 1376 setChild(i, NewChild); 1377 } 1378 return this; 1379 } 1380 1381 // Otherwise, we found a reference to a fragment. First, look up its 1382 // TreePattern record. 1383 TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 1384 1385 // Verify that we are passing the right number of operands. 1386 if (Frag->getNumArgs() != Children.size()) { 1387 TP.error("'" + Op->getName() + "' fragment requires " + 1388 utostr(Frag->getNumArgs()) + " operands!"); 1389 return nullptr; 1390 } 1391 1392 TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); 1393 1394 TreePredicateFn PredFn(Frag); 1395 if (!PredFn.isAlwaysTrue()) 1396 FragTree->addPredicateFn(PredFn); 1397 1398 // Resolve formal arguments to their actual value. 1399 if (Frag->getNumArgs()) { 1400 // Compute the map of formal to actual arguments. 1401 std::map<std::string, TreePatternNode*> ArgMap; 1402 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) 1403 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); 1404 1405 FragTree->SubstituteFormalArguments(ArgMap); 1406 } 1407 1408 FragTree->setName(getName()); 1409 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1410 FragTree->UpdateNodeType(i, getExtType(i), TP); 1411 1412 // Transfer in the old predicates. 1413 for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i) 1414 FragTree->addPredicateFn(getPredicateFns()[i]); 1415 1416 // Get a new copy of this fragment to stitch into here. 1417 //delete this; // FIXME: implement refcounting! 1418 1419 // The fragment we inlined could have recursive inlining that is needed. See 1420 // if there are any pattern fragments in it and inline them as needed. 1421 return FragTree->InlinePatternFragments(TP); 1422} 1423 1424/// getImplicitType - Check to see if the specified record has an implicit 1425/// type which should be applied to it. This will infer the type of register 1426/// references from the register file information, for example. 1427/// 1428/// When Unnamed is set, return the type of a DAG operand with no name, such as 1429/// the F8RC register class argument in: 1430/// 1431/// (COPY_TO_REGCLASS GPR:$src, F8RC) 1432/// 1433/// When Unnamed is false, return the type of a named DAG operand such as the 1434/// GPR:$src operand above. 1435/// 1436static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, 1437 bool NotRegisters, 1438 bool Unnamed, 1439 TreePattern &TP) { 1440 // Check to see if this is a register operand. 1441 if (R->isSubClassOf("RegisterOperand")) { 1442 assert(ResNo == 0 && "Regoperand ref only has one result!"); 1443 if (NotRegisters) 1444 return EEVT::TypeSet(); // Unknown. 1445 Record *RegClass = R->getValueAsDef("RegClass"); 1446 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1447 return EEVT::TypeSet(T.getRegisterClass(RegClass).getValueTypes()); 1448 } 1449 1450 // Check to see if this is a register or a register class. 1451 if (R->isSubClassOf("RegisterClass")) { 1452 assert(ResNo == 0 && "Regclass ref only has one result!"); 1453 // An unnamed register class represents itself as an i32 immediate, for 1454 // example on a COPY_TO_REGCLASS instruction. 1455 if (Unnamed) 1456 return EEVT::TypeSet(MVT::i32, TP); 1457 1458 // In a named operand, the register class provides the possible set of 1459 // types. 1460 if (NotRegisters) 1461 return EEVT::TypeSet(); // Unknown. 1462 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1463 return EEVT::TypeSet(T.getRegisterClass(R).getValueTypes()); 1464 } 1465 1466 if (R->isSubClassOf("PatFrag")) { 1467 assert(ResNo == 0 && "FIXME: PatFrag with multiple results?"); 1468 // Pattern fragment types will be resolved when they are inlined. 1469 return EEVT::TypeSet(); // Unknown. 1470 } 1471 1472 if (R->isSubClassOf("Register")) { 1473 assert(ResNo == 0 && "Registers only produce one result!"); 1474 if (NotRegisters) 1475 return EEVT::TypeSet(); // Unknown. 1476 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1477 return EEVT::TypeSet(T.getRegisterVTs(R)); 1478 } 1479 1480 if (R->isSubClassOf("SubRegIndex")) { 1481 assert(ResNo == 0 && "SubRegisterIndices only produce one result!"); 1482 return EEVT::TypeSet(MVT::i32, TP); 1483 } 1484 1485 if (R->isSubClassOf("ValueType")) { 1486 assert(ResNo == 0 && "This node only has one result!"); 1487 // An unnamed VTSDNode represents itself as an MVT::Other immediate. 1488 // 1489 // (sext_inreg GPR:$src, i16) 1490 // ~~~ 1491 if (Unnamed) 1492 return EEVT::TypeSet(MVT::Other, TP); 1493 // With a name, the ValueType simply provides the type of the named 1494 // variable. 1495 // 1496 // (sext_inreg i32:$src, i16) 1497 // ~~~~~~~~ 1498 if (NotRegisters) 1499 return EEVT::TypeSet(); // Unknown. 1500 return EEVT::TypeSet(getValueType(R), TP); 1501 } 1502 1503 if (R->isSubClassOf("CondCode")) { 1504 assert(ResNo == 0 && "This node only has one result!"); 1505 // Using a CondCodeSDNode. 1506 return EEVT::TypeSet(MVT::Other, TP); 1507 } 1508 1509 if (R->isSubClassOf("ComplexPattern")) { 1510 assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?"); 1511 if (NotRegisters) 1512 return EEVT::TypeSet(); // Unknown. 1513 return EEVT::TypeSet(TP.getDAGPatterns().getComplexPattern(R).getValueType(), 1514 TP); 1515 } 1516 if (R->isSubClassOf("PointerLikeRegClass")) { 1517 assert(ResNo == 0 && "Regclass can only have one result!"); 1518 return EEVT::TypeSet(MVT::iPTR, TP); 1519 } 1520 1521 if (R->getName() == "node" || R->getName() == "srcvalue" || 1522 R->getName() == "zero_reg") { 1523 // Placeholder. 1524 return EEVT::TypeSet(); // Unknown. 1525 } 1526 1527 if (R->isSubClassOf("Operand")) 1528 return EEVT::TypeSet(getValueType(R->getValueAsDef("Type"))); 1529 1530 TP.error("Unknown node flavor used in pattern: " + R->getName()); 1531 return EEVT::TypeSet(MVT::Other, TP); 1532} 1533 1534 1535/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 1536/// CodeGenIntrinsic information for it, otherwise return a null pointer. 1537const CodeGenIntrinsic *TreePatternNode:: 1538getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 1539 if (getOperator() != CDP.get_intrinsic_void_sdnode() && 1540 getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 1541 getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 1542 return nullptr; 1543 1544 unsigned IID = cast<IntInit>(getChild(0)->getLeafValue())->getValue(); 1545 return &CDP.getIntrinsicInfo(IID); 1546} 1547 1548/// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 1549/// return the ComplexPattern information, otherwise return null. 1550const ComplexPattern * 1551TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { 1552 Record *Rec; 1553 if (isLeaf()) { 1554 DefInit *DI = dyn_cast<DefInit>(getLeafValue()); 1555 if (!DI) 1556 return nullptr; 1557 Rec = DI->getDef(); 1558 } else 1559 Rec = getOperator(); 1560 1561 if (!Rec->isSubClassOf("ComplexPattern")) 1562 return nullptr; 1563 return &CGP.getComplexPattern(Rec); 1564} 1565 1566unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const { 1567 // A ComplexPattern specifically declares how many results it fills in. 1568 if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 1569 return CP->getNumOperands(); 1570 1571 // If MIOperandInfo is specified, that gives the count. 1572 if (isLeaf()) { 1573 DefInit *DI = dyn_cast<DefInit>(getLeafValue()); 1574 if (DI && DI->getDef()->isSubClassOf("Operand")) { 1575 DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo"); 1576 if (MIOps->getNumArgs()) 1577 return MIOps->getNumArgs(); 1578 } 1579 } 1580 1581 // Otherwise there is just one result. 1582 return 1; 1583} 1584 1585/// NodeHasProperty - Return true if this node has the specified property. 1586bool TreePatternNode::NodeHasProperty(SDNP Property, 1587 const CodeGenDAGPatterns &CGP) const { 1588 if (isLeaf()) { 1589 if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 1590 return CP->hasProperty(Property); 1591 return false; 1592 } 1593 1594 Record *Operator = getOperator(); 1595 if (!Operator->isSubClassOf("SDNode")) return false; 1596 1597 return CGP.getSDNodeInfo(Operator).hasProperty(Property); 1598} 1599 1600 1601 1602 1603/// TreeHasProperty - Return true if any node in this tree has the specified 1604/// property. 1605bool TreePatternNode::TreeHasProperty(SDNP Property, 1606 const CodeGenDAGPatterns &CGP) const { 1607 if (NodeHasProperty(Property, CGP)) 1608 return true; 1609 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1610 if (getChild(i)->TreeHasProperty(Property, CGP)) 1611 return true; 1612 return false; 1613} 1614 1615/// isCommutativeIntrinsic - Return true if the node corresponds to a 1616/// commutative intrinsic. 1617bool 1618TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { 1619 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) 1620 return Int->isCommutative; 1621 return false; 1622} 1623 1624static bool isOperandClass(const TreePatternNode *N, StringRef Class) { 1625 if (!N->isLeaf()) 1626 return N->getOperator()->isSubClassOf(Class); 1627 1628 DefInit *DI = dyn_cast<DefInit>(N->getLeafValue()); 1629 if (DI && DI->getDef()->isSubClassOf(Class)) 1630 return true; 1631 1632 return false; 1633} 1634 1635static void emitTooManyOperandsError(TreePattern &TP, 1636 StringRef InstName, 1637 unsigned Expected, 1638 unsigned Actual) { 1639 TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) + 1640 " operands but expected only " + Twine(Expected) + "!"); 1641} 1642 1643static void emitTooFewOperandsError(TreePattern &TP, 1644 StringRef InstName, 1645 unsigned Actual) { 1646 TP.error("Instruction '" + InstName + 1647 "' expects more than the provided " + Twine(Actual) + " operands!"); 1648} 1649 1650/// ApplyTypeConstraints - Apply all of the type constraints relevant to 1651/// this node and its children in the tree. This returns true if it makes a 1652/// change, false otherwise. If a type contradiction is found, flag an error. 1653bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 1654 if (TP.hasError()) 1655 return false; 1656 1657 CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 1658 if (isLeaf()) { 1659 if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) { 1660 // If it's a regclass or something else known, include the type. 1661 bool MadeChange = false; 1662 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1663 MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i, 1664 NotRegisters, 1665 !hasName(), TP), TP); 1666 return MadeChange; 1667 } 1668 1669 if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) { 1670 assert(Types.size() == 1 && "Invalid IntInit"); 1671 1672 // Int inits are always integers. :) 1673 bool MadeChange = Types[0].EnforceInteger(TP); 1674 1675 if (!Types[0].isConcrete()) 1676 return MadeChange; 1677 1678 MVT::SimpleValueType VT = getType(0); 1679 if (VT == MVT::iPTR || VT == MVT::iPTRAny) 1680 return MadeChange; 1681 1682 unsigned Size = MVT(VT).getSizeInBits(); 1683 // Make sure that the value is representable for this type. 1684 if (Size >= 32) return MadeChange; 1685 1686 // Check that the value doesn't use more bits than we have. It must either 1687 // be a sign- or zero-extended equivalent of the original. 1688 int64_t SignBitAndAbove = II->getValue() >> (Size - 1); 1689 if (SignBitAndAbove == -1 || SignBitAndAbove == 0 || SignBitAndAbove == 1) 1690 return MadeChange; 1691 1692 TP.error("Integer value '" + itostr(II->getValue()) + 1693 "' is out of range for type '" + getEnumName(getType(0)) + "'!"); 1694 return false; 1695 } 1696 return false; 1697 } 1698 1699 // special handling for set, which isn't really an SDNode. 1700 if (getOperator()->getName() == "set") { 1701 assert(getNumTypes() == 0 && "Set doesn't produce a value"); 1702 assert(getNumChildren() >= 2 && "Missing RHS of a set?"); 1703 unsigned NC = getNumChildren(); 1704 1705 TreePatternNode *SetVal = getChild(NC-1); 1706 bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters); 1707 1708 for (unsigned i = 0; i < NC-1; ++i) { 1709 TreePatternNode *Child = getChild(i); 1710 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 1711 1712 // Types of operands must match. 1713 MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP); 1714 MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP); 1715 } 1716 return MadeChange; 1717 } 1718 1719 if (getOperator()->getName() == "implicit") { 1720 assert(getNumTypes() == 0 && "Node doesn't produce a value"); 1721 1722 bool MadeChange = false; 1723 for (unsigned i = 0; i < getNumChildren(); ++i) 1724 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1725 return MadeChange; 1726 } 1727 1728 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 1729 bool MadeChange = false; 1730 1731 // Apply the result type to the node. 1732 unsigned NumRetVTs = Int->IS.RetVTs.size(); 1733 unsigned NumParamVTs = Int->IS.ParamVTs.size(); 1734 1735 for (unsigned i = 0, e = NumRetVTs; i != e; ++i) 1736 MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP); 1737 1738 if (getNumChildren() != NumParamVTs + 1) { 1739 TP.error("Intrinsic '" + Int->Name + "' expects " + 1740 utostr(NumParamVTs) + " operands, not " + 1741 utostr(getNumChildren() - 1) + " operands!"); 1742 return false; 1743 } 1744 1745 // Apply type info to the intrinsic ID. 1746 MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP); 1747 1748 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) { 1749 MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters); 1750 1751 MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i]; 1752 assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case"); 1753 MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP); 1754 } 1755 return MadeChange; 1756 } 1757 1758 if (getOperator()->isSubClassOf("SDNode")) { 1759 const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 1760 1761 // Check that the number of operands is sane. Negative operands -> varargs. 1762 if (NI.getNumOperands() >= 0 && 1763 getNumChildren() != (unsigned)NI.getNumOperands()) { 1764 TP.error(getOperator()->getName() + " node requires exactly " + 1765 itostr(NI.getNumOperands()) + " operands!"); 1766 return false; 1767 } 1768 1769 bool MadeChange = NI.ApplyTypeConstraints(this, TP); 1770 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1771 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1772 return MadeChange; 1773 } 1774 1775 if (getOperator()->isSubClassOf("Instruction")) { 1776 const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 1777 CodeGenInstruction &InstInfo = 1778 CDP.getTargetInfo().getInstruction(getOperator()); 1779 1780 bool MadeChange = false; 1781 1782 // Apply the result types to the node, these come from the things in the 1783 // (outs) list of the instruction. 1784 unsigned NumResultsToAdd = std::min(InstInfo.Operands.NumDefs, 1785 Inst.getNumResults()); 1786 for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo) 1787 MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP); 1788 1789 // If the instruction has implicit defs, we apply the first one as a result. 1790 // FIXME: This sucks, it should apply all implicit defs. 1791 if (!InstInfo.ImplicitDefs.empty()) { 1792 unsigned ResNo = NumResultsToAdd; 1793 1794 // FIXME: Generalize to multiple possible types and multiple possible 1795 // ImplicitDefs. 1796 MVT::SimpleValueType VT = 1797 InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()); 1798 1799 if (VT != MVT::Other) 1800 MadeChange |= UpdateNodeType(ResNo, VT, TP); 1801 } 1802 1803 // If this is an INSERT_SUBREG, constrain the source and destination VTs to 1804 // be the same. 1805 if (getOperator()->getName() == "INSERT_SUBREG") { 1806 assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); 1807 MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); 1808 MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); 1809 } else if (getOperator()->getName() == "REG_SEQUENCE") { 1810 // We need to do extra, custom typechecking for REG_SEQUENCE since it is 1811 // variadic. 1812 1813 unsigned NChild = getNumChildren(); 1814 if (NChild < 3) { 1815 TP.error("REG_SEQUENCE requires at least 3 operands!"); 1816 return false; 1817 } 1818 1819 if (NChild % 2 == 0) { 1820 TP.error("REG_SEQUENCE requires an odd number of operands!"); 1821 return false; 1822 } 1823 1824 if (!isOperandClass(getChild(0), "RegisterClass")) { 1825 TP.error("REG_SEQUENCE requires a RegisterClass for first operand!"); 1826 return false; 1827 } 1828 1829 for (unsigned I = 1; I < NChild; I += 2) { 1830 TreePatternNode *SubIdxChild = getChild(I + 1); 1831 if (!isOperandClass(SubIdxChild, "SubRegIndex")) { 1832 TP.error("REG_SEQUENCE requires a SubRegIndex for operand " + 1833 itostr(I + 1) + "!"); 1834 return false; 1835 } 1836 } 1837 } 1838 1839 unsigned ChildNo = 0; 1840 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 1841 Record *OperandNode = Inst.getOperand(i); 1842 1843 // If the instruction expects a predicate or optional def operand, we 1844 // codegen this by setting the operand to it's default value if it has a 1845 // non-empty DefaultOps field. 1846 if (OperandNode->isSubClassOf("OperandWithDefaultOps") && 1847 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 1848 continue; 1849 1850 // Verify that we didn't run out of provided operands. 1851 if (ChildNo >= getNumChildren()) { 1852 emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren()); 1853 return false; 1854 } 1855 1856 TreePatternNode *Child = getChild(ChildNo++); 1857 unsigned ChildResNo = 0; // Instructions always use res #0 of their op. 1858 1859 // If the operand has sub-operands, they may be provided by distinct 1860 // child patterns, so attempt to match each sub-operand separately. 1861 if (OperandNode->isSubClassOf("Operand")) { 1862 DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo"); 1863 if (unsigned NumArgs = MIOpInfo->getNumArgs()) { 1864 // But don't do that if the whole operand is being provided by 1865 // a single ComplexPattern-related Operand. 1866 1867 if (Child->getNumMIResults(CDP) < NumArgs) { 1868 // Match first sub-operand against the child we already have. 1869 Record *SubRec = cast<DefInit>(MIOpInfo->getArg(0))->getDef(); 1870 MadeChange |= 1871 Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP); 1872 1873 // And the remaining sub-operands against subsequent children. 1874 for (unsigned Arg = 1; Arg < NumArgs; ++Arg) { 1875 if (ChildNo >= getNumChildren()) { 1876 emitTooFewOperandsError(TP, getOperator()->getName(), 1877 getNumChildren()); 1878 return false; 1879 } 1880 Child = getChild(ChildNo++); 1881 1882 SubRec = cast<DefInit>(MIOpInfo->getArg(Arg))->getDef(); 1883 MadeChange |= 1884 Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP); 1885 } 1886 continue; 1887 } 1888 } 1889 } 1890 1891 // If we didn't match by pieces above, attempt to match the whole 1892 // operand now. 1893 MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP); 1894 } 1895 1896 if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) { 1897 emitTooManyOperandsError(TP, getOperator()->getName(), 1898 ChildNo, getNumChildren()); 1899 return false; 1900 } 1901 1902 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1903 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1904 return MadeChange; 1905 } 1906 1907 if (getOperator()->isSubClassOf("ComplexPattern")) { 1908 bool MadeChange = false; 1909 1910 for (unsigned i = 0; i < getNumChildren(); ++i) 1911 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1912 1913 return MadeChange; 1914 } 1915 1916 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 1917 1918 // Node transforms always take one operand. 1919 if (getNumChildren() != 1) { 1920 TP.error("Node transform '" + getOperator()->getName() + 1921 "' requires one operand!"); 1922 return false; 1923 } 1924 1925 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 1926 1927 1928 // If either the output or input of the xform does not have exact 1929 // type info. We assume they must be the same. Otherwise, it is perfectly 1930 // legal to transform from one type to a completely different type. 1931#if 0 1932 if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { 1933 bool MadeChange = UpdateNodeType(getChild(0)->getExtType(), TP); 1934 MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP); 1935 return MadeChange; 1936 } 1937#endif 1938 return MadeChange; 1939} 1940 1941/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 1942/// RHS of a commutative operation, not the on LHS. 1943static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 1944 if (!N->isLeaf() && N->getOperator()->getName() == "imm") 1945 return true; 1946 if (N->isLeaf() && isa<IntInit>(N->getLeafValue())) 1947 return true; 1948 return false; 1949} 1950 1951 1952/// canPatternMatch - If it is impossible for this pattern to match on this 1953/// target, fill in Reason and return false. Otherwise, return true. This is 1954/// used as a sanity check for .td files (to prevent people from writing stuff 1955/// that can never possibly work), and to prevent the pattern permuter from 1956/// generating stuff that is useless. 1957bool TreePatternNode::canPatternMatch(std::string &Reason, 1958 const CodeGenDAGPatterns &CDP) { 1959 if (isLeaf()) return true; 1960 1961 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1962 if (!getChild(i)->canPatternMatch(Reason, CDP)) 1963 return false; 1964 1965 // If this is an intrinsic, handle cases that would make it not match. For 1966 // example, if an operand is required to be an immediate. 1967 if (getOperator()->isSubClassOf("Intrinsic")) { 1968 // TODO: 1969 return true; 1970 } 1971 1972 if (getOperator()->isSubClassOf("ComplexPattern")) 1973 return true; 1974 1975 // If this node is a commutative operator, check that the LHS isn't an 1976 // immediate. 1977 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 1978 bool isCommIntrinsic = isCommutativeIntrinsic(CDP); 1979 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 1980 // Scan all of the operands of the node and make sure that only the last one 1981 // is a constant node, unless the RHS also is. 1982 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 1983 bool Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id. 1984 for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i) 1985 if (OnlyOnRHSOfCommutative(getChild(i))) { 1986 Reason="Immediate value must be on the RHS of commutative operators!"; 1987 return false; 1988 } 1989 } 1990 } 1991 1992 return true; 1993} 1994 1995//===----------------------------------------------------------------------===// 1996// TreePattern implementation 1997// 1998 1999TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 2000 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2001 isInputPattern(isInput), HasError(false) { 2002 for (Init *I : RawPat->getValues()) 2003 Trees.push_back(ParseTreePattern(I, "")); 2004} 2005 2006TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 2007 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2008 isInputPattern(isInput), HasError(false) { 2009 Trees.push_back(ParseTreePattern(Pat, "")); 2010} 2011 2012TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 2013 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), 2014 isInputPattern(isInput), HasError(false) { 2015 Trees.push_back(Pat); 2016} 2017 2018void TreePattern::error(const Twine &Msg) { 2019 if (HasError) 2020 return; 2021 dump(); 2022 PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); 2023 HasError = true; 2024} 2025 2026void TreePattern::ComputeNamedNodes() { 2027 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 2028 ComputeNamedNodes(Trees[i]); 2029} 2030 2031void TreePattern::ComputeNamedNodes(TreePatternNode *N) { 2032 if (!N->getName().empty()) 2033 NamedNodes[N->getName()].push_back(N); 2034 2035 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2036 ComputeNamedNodes(N->getChild(i)); 2037} 2038 2039 2040TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ 2041 if (DefInit *DI = dyn_cast<DefInit>(TheInit)) { 2042 Record *R = DI->getDef(); 2043 2044 // Direct reference to a leaf DagNode or PatFrag? Turn it into a 2045 // TreePatternNode of its own. For example: 2046 /// (foo GPR, imm) -> (foo GPR, (imm)) 2047 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) 2048 return ParseTreePattern( 2049 DagInit::get(DI, "", 2050 std::vector<std::pair<Init*, std::string> >()), 2051 OpName); 2052 2053 // Input argument? 2054 TreePatternNode *Res = new TreePatternNode(DI, 1); 2055 if (R->getName() == "node" && !OpName.empty()) { 2056 if (OpName.empty()) 2057 error("'node' argument requires a name to match with operand list"); 2058 Args.push_back(OpName); 2059 } 2060 2061 Res->setName(OpName); 2062 return Res; 2063 } 2064 2065 // ?:$name or just $name. 2066 if (isa<UnsetInit>(TheInit)) { 2067 if (OpName.empty()) 2068 error("'?' argument requires a name to match with operand list"); 2069 TreePatternNode *Res = new TreePatternNode(TheInit, 1); 2070 Args.push_back(OpName); 2071 Res->setName(OpName); 2072 return Res; 2073 } 2074 2075 if (IntInit *II = dyn_cast<IntInit>(TheInit)) { 2076 if (!OpName.empty()) 2077 error("Constant int argument should not have a name!"); 2078 return new TreePatternNode(II, 1); 2079 } 2080 2081 if (BitsInit *BI = dyn_cast<BitsInit>(TheInit)) { 2082 // Turn this into an IntInit. 2083 Init *II = BI->convertInitializerTo(IntRecTy::get()); 2084 if (!II || !isa<IntInit>(II)) 2085 error("Bits value must be constants!"); 2086 return ParseTreePattern(II, OpName); 2087 } 2088 2089 DagInit *Dag = dyn_cast<DagInit>(TheInit); 2090 if (!Dag) { 2091 TheInit->dump(); 2092 error("Pattern has unexpected init kind!"); 2093 } 2094 DefInit *OpDef = dyn_cast<DefInit>(Dag->getOperator()); 2095 if (!OpDef) error("Pattern has unexpected operator type!"); 2096 Record *Operator = OpDef->getDef(); 2097 2098 if (Operator->isSubClassOf("ValueType")) { 2099 // If the operator is a ValueType, then this must be "type cast" of a leaf 2100 // node. 2101 if (Dag->getNumArgs() != 1) 2102 error("Type cast only takes one operand!"); 2103 2104 TreePatternNode *New = ParseTreePattern(Dag->getArg(0), Dag->getArgName(0)); 2105 2106 // Apply the type cast. 2107 assert(New->getNumTypes() == 1 && "FIXME: Unhandled"); 2108 New->UpdateNodeType(0, getValueType(Operator), *this); 2109 2110 if (!OpName.empty()) 2111 error("ValueType cast should not have a name!"); 2112 return New; 2113 } 2114 2115 // Verify that this is something that makes sense for an operator. 2116 if (!Operator->isSubClassOf("PatFrag") && 2117 !Operator->isSubClassOf("SDNode") && 2118 !Operator->isSubClassOf("Instruction") && 2119 !Operator->isSubClassOf("SDNodeXForm") && 2120 !Operator->isSubClassOf("Intrinsic") && 2121 !Operator->isSubClassOf("ComplexPattern") && 2122 Operator->getName() != "set" && 2123 Operator->getName() != "implicit") 2124 error("Unrecognized node '" + Operator->getName() + "'!"); 2125 2126 // Check to see if this is something that is illegal in an input pattern. 2127 if (isInputPattern) { 2128 if (Operator->isSubClassOf("Instruction") || 2129 Operator->isSubClassOf("SDNodeXForm")) 2130 error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 2131 } else { 2132 if (Operator->isSubClassOf("Intrinsic")) 2133 error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 2134 2135 if (Operator->isSubClassOf("SDNode") && 2136 Operator->getName() != "imm" && 2137 Operator->getName() != "fpimm" && 2138 Operator->getName() != "tglobaltlsaddr" && 2139 Operator->getName() != "tconstpool" && 2140 Operator->getName() != "tjumptable" && 2141 Operator->getName() != "tframeindex" && 2142 Operator->getName() != "texternalsym" && 2143 Operator->getName() != "tblockaddress" && 2144 Operator->getName() != "tglobaladdr" && 2145 Operator->getName() != "bb" && 2146 Operator->getName() != "vt" && 2147 Operator->getName() != "mcsym") 2148 error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 2149 } 2150 2151 std::vector<TreePatternNode*> Children; 2152 2153 // Parse all the operands. 2154 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) 2155 Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgName(i))); 2156 2157 // If the operator is an intrinsic, then this is just syntactic sugar for for 2158 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 2159 // convert the intrinsic name to a number. 2160 if (Operator->isSubClassOf("Intrinsic")) { 2161 const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 2162 unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 2163 2164 // If this intrinsic returns void, it must have side-effects and thus a 2165 // chain. 2166 if (Int.IS.RetVTs.empty()) 2167 Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 2168 else if (Int.ModRef != CodeGenIntrinsic::NoMem) 2169 // Has side-effects, requires chain. 2170 Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 2171 else // Otherwise, no chain. 2172 Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 2173 2174 TreePatternNode *IIDNode = new TreePatternNode(IntInit::get(IID), 1); 2175 Children.insert(Children.begin(), IIDNode); 2176 } 2177 2178 if (Operator->isSubClassOf("ComplexPattern")) { 2179 for (unsigned i = 0; i < Children.size(); ++i) { 2180 TreePatternNode *Child = Children[i]; 2181 2182 if (Child->getName().empty()) 2183 error("All arguments to a ComplexPattern must be named"); 2184 2185 // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)" 2186 // and "(MY_PAT $b, $a)" should not be allowed in the same pattern; 2187 // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)". 2188 auto OperandId = std::make_pair(Operator, i); 2189 auto PrevOp = ComplexPatternOperands.find(Child->getName()); 2190 if (PrevOp != ComplexPatternOperands.end()) { 2191 if (PrevOp->getValue() != OperandId) 2192 error("All ComplexPattern operands must appear consistently: " 2193 "in the same order in just one ComplexPattern instance."); 2194 } else 2195 ComplexPatternOperands[Child->getName()] = OperandId; 2196 } 2197 } 2198 2199 unsigned NumResults = GetNumNodeResults(Operator, CDP); 2200 TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults); 2201 Result->setName(OpName); 2202 2203 if (!Dag->getName().empty()) { 2204 assert(Result->getName().empty()); 2205 Result->setName(Dag->getName()); 2206 } 2207 return Result; 2208} 2209 2210/// SimplifyTree - See if we can simplify this tree to eliminate something that 2211/// will never match in favor of something obvious that will. This is here 2212/// strictly as a convenience to target authors because it allows them to write 2213/// more type generic things and have useless type casts fold away. 2214/// 2215/// This returns true if any change is made. 2216static bool SimplifyTree(TreePatternNode *&N) { 2217 if (N->isLeaf()) 2218 return false; 2219 2220 // If we have a bitconvert with a resolved type and if the source and 2221 // destination types are the same, then the bitconvert is useless, remove it. 2222 if (N->getOperator()->getName() == "bitconvert" && 2223 N->getExtType(0).isConcrete() && 2224 N->getExtType(0) == N->getChild(0)->getExtType(0) && 2225 N->getName().empty()) { 2226 N = N->getChild(0); 2227 SimplifyTree(N); 2228 return true; 2229 } 2230 2231 // Walk all children. 2232 bool MadeChange = false; 2233 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2234 TreePatternNode *Child = N->getChild(i); 2235 MadeChange |= SimplifyTree(Child); 2236 N->setChild(i, Child); 2237 } 2238 return MadeChange; 2239} 2240 2241 2242 2243/// InferAllTypes - Infer/propagate as many types throughout the expression 2244/// patterns as possible. Return true if all types are inferred, false 2245/// otherwise. Flags an error if a type contradiction is found. 2246bool TreePattern:: 2247InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) { 2248 if (NamedNodes.empty()) 2249 ComputeNamedNodes(); 2250 2251 bool MadeChange = true; 2252 while (MadeChange) { 2253 MadeChange = false; 2254 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 2255 MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); 2256 MadeChange |= SimplifyTree(Trees[i]); 2257 } 2258 2259 // If there are constraints on our named nodes, apply them. 2260 for (StringMap<SmallVector<TreePatternNode*,1> >::iterator 2261 I = NamedNodes.begin(), E = NamedNodes.end(); I != E; ++I) { 2262 SmallVectorImpl<TreePatternNode*> &Nodes = I->second; 2263 2264 // If we have input named node types, propagate their types to the named 2265 // values here. 2266 if (InNamedTypes) { 2267 if (!InNamedTypes->count(I->getKey())) { 2268 error("Node '" + std::string(I->getKey()) + 2269 "' in output pattern but not input pattern"); 2270 return true; 2271 } 2272 2273 const SmallVectorImpl<TreePatternNode*> &InNodes = 2274 InNamedTypes->find(I->getKey())->second; 2275 2276 // The input types should be fully resolved by now. 2277 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 2278 // If this node is a register class, and it is the root of the pattern 2279 // then we're mapping something onto an input register. We allow 2280 // changing the type of the input register in this case. This allows 2281 // us to match things like: 2282 // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>; 2283 if (Nodes[i] == Trees[0] && Nodes[i]->isLeaf()) { 2284 DefInit *DI = dyn_cast<DefInit>(Nodes[i]->getLeafValue()); 2285 if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 2286 DI->getDef()->isSubClassOf("RegisterOperand"))) 2287 continue; 2288 } 2289 2290 assert(Nodes[i]->getNumTypes() == 1 && 2291 InNodes[0]->getNumTypes() == 1 && 2292 "FIXME: cannot name multiple result nodes yet"); 2293 MadeChange |= Nodes[i]->UpdateNodeType(0, InNodes[0]->getExtType(0), 2294 *this); 2295 } 2296 } 2297 2298 // If there are multiple nodes with the same name, they must all have the 2299 // same type. 2300 if (I->second.size() > 1) { 2301 for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) { 2302 TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1]; 2303 assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && 2304 "FIXME: cannot name multiple result nodes yet"); 2305 2306 MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this); 2307 MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this); 2308 } 2309 } 2310 } 2311 } 2312 2313 bool HasUnresolvedTypes = false; 2314 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 2315 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); 2316 return !HasUnresolvedTypes; 2317} 2318 2319void TreePattern::print(raw_ostream &OS) const { 2320 OS << getRecord()->getName(); 2321 if (!Args.empty()) { 2322 OS << "(" << Args[0]; 2323 for (unsigned i = 1, e = Args.size(); i != e; ++i) 2324 OS << ", " << Args[i]; 2325 OS << ")"; 2326 } 2327 OS << ": "; 2328 2329 if (Trees.size() > 1) 2330 OS << "[\n"; 2331 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 2332 OS << "\t"; 2333 Trees[i]->print(OS); 2334 OS << "\n"; 2335 } 2336 2337 if (Trees.size() > 1) 2338 OS << "]\n"; 2339} 2340 2341void TreePattern::dump() const { print(errs()); } 2342 2343//===----------------------------------------------------------------------===// 2344// CodeGenDAGPatterns implementation 2345// 2346 2347CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : 2348 Records(R), Target(R) { 2349 2350 Intrinsics = LoadIntrinsics(Records, false); 2351 TgtIntrinsics = LoadIntrinsics(Records, true); 2352 ParseNodeInfo(); 2353 ParseNodeTransforms(); 2354 ParseComplexPatterns(); 2355 ParsePatternFragments(); 2356 ParseDefaultOperands(); 2357 ParseInstructions(); 2358 ParsePatternFragments(/*OutFrags*/true); 2359 ParsePatterns(); 2360 2361 // Generate variants. For example, commutative patterns can match 2362 // multiple ways. Add them to PatternsToMatch as well. 2363 GenerateVariants(); 2364 2365 // Infer instruction flags. For example, we can detect loads, 2366 // stores, and side effects in many cases by examining an 2367 // instruction's pattern. 2368 InferInstructionFlags(); 2369 2370 // Verify that instruction flags match the patterns. 2371 VerifyInstructionFlags(); 2372} 2373 2374Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 2375 Record *N = Records.getDef(Name); 2376 if (!N || !N->isSubClassOf("SDNode")) 2377 PrintFatalError("Error getting SDNode '" + Name + "'!"); 2378 2379 return N; 2380} 2381 2382// Parse all of the SDNode definitions for the target, populating SDNodes. 2383void CodeGenDAGPatterns::ParseNodeInfo() { 2384 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 2385 while (!Nodes.empty()) { 2386 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back())); 2387 Nodes.pop_back(); 2388 } 2389 2390 // Get the builtin intrinsic nodes. 2391 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 2392 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 2393 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 2394} 2395 2396/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 2397/// map, and emit them to the file as functions. 2398void CodeGenDAGPatterns::ParseNodeTransforms() { 2399 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 2400 while (!Xforms.empty()) { 2401 Record *XFormNode = Xforms.back(); 2402 Record *SDNode = XFormNode->getValueAsDef("Opcode"); 2403 std::string Code = XFormNode->getValueAsString("XFormFunction"); 2404 SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 2405 2406 Xforms.pop_back(); 2407 } 2408} 2409 2410void CodeGenDAGPatterns::ParseComplexPatterns() { 2411 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 2412 while (!AMs.empty()) { 2413 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 2414 AMs.pop_back(); 2415 } 2416} 2417 2418 2419/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 2420/// file, building up the PatternFragments map. After we've collected them all, 2421/// inline fragments together as necessary, so that there are no references left 2422/// inside a pattern fragment to a pattern fragment. 2423/// 2424void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { 2425 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag"); 2426 2427 // First step, parse all of the fragments. 2428 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 2429 if (OutFrags != Fragments[i]->isSubClassOf("OutPatFrag")) 2430 continue; 2431 2432 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); 2433 TreePattern *P = 2434 (PatternFragments[Fragments[i]] = llvm::make_unique<TreePattern>( 2435 Fragments[i], Tree, !Fragments[i]->isSubClassOf("OutPatFrag"), 2436 *this)).get(); 2437 2438 // Validate the argument list, converting it to set, to discard duplicates. 2439 std::vector<std::string> &Args = P->getArgList(); 2440 std::set<std::string> OperandsSet(Args.begin(), Args.end()); 2441 2442 if (OperandsSet.count("")) 2443 P->error("Cannot have unnamed 'node' values in pattern fragment!"); 2444 2445 // Parse the operands list. 2446 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); 2447 DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator()); 2448 // Special cases: ops == outs == ins. Different names are used to 2449 // improve readability. 2450 if (!OpsOp || 2451 (OpsOp->getDef()->getName() != "ops" && 2452 OpsOp->getDef()->getName() != "outs" && 2453 OpsOp->getDef()->getName() != "ins")) 2454 P->error("Operands list should start with '(ops ... '!"); 2455 2456 // Copy over the arguments. 2457 Args.clear(); 2458 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 2459 if (!isa<DefInit>(OpsList->getArg(j)) || 2460 cast<DefInit>(OpsList->getArg(j))->getDef()->getName() != "node") 2461 P->error("Operands list should all be 'node' values."); 2462 if (OpsList->getArgName(j).empty()) 2463 P->error("Operands list should have names for each operand!"); 2464 if (!OperandsSet.count(OpsList->getArgName(j))) 2465 P->error("'" + OpsList->getArgName(j) + 2466 "' does not occur in pattern or was multiply specified!"); 2467 OperandsSet.erase(OpsList->getArgName(j)); 2468 Args.push_back(OpsList->getArgName(j)); 2469 } 2470 2471 if (!OperandsSet.empty()) 2472 P->error("Operands list does not contain an entry for operand '" + 2473 *OperandsSet.begin() + "'!"); 2474 2475 // If there is a code init for this fragment, keep track of the fact that 2476 // this fragment uses it. 2477 TreePredicateFn PredFn(P); 2478 if (!PredFn.isAlwaysTrue()) 2479 P->getOnlyTree()->addPredicateFn(PredFn); 2480 2481 // If there is a node transformation corresponding to this, keep track of 2482 // it. 2483 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); 2484 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 2485 P->getOnlyTree()->setTransformFn(Transform); 2486 } 2487 2488 // Now that we've parsed all of the tree fragments, do a closure on them so 2489 // that there are not references to PatFrags left inside of them. 2490 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 2491 if (OutFrags != Fragments[i]->isSubClassOf("OutPatFrag")) 2492 continue; 2493 2494 TreePattern &ThePat = *PatternFragments[Fragments[i]]; 2495 ThePat.InlinePatternFragments(); 2496 2497 // Infer as many types as possible. Don't worry about it if we don't infer 2498 // all of them, some may depend on the inputs of the pattern. 2499 ThePat.InferAllTypes(); 2500 ThePat.resetError(); 2501 2502 // If debugging, print out the pattern fragment result. 2503 DEBUG(ThePat.dump()); 2504 } 2505} 2506 2507void CodeGenDAGPatterns::ParseDefaultOperands() { 2508 std::vector<Record*> DefaultOps; 2509 DefaultOps = Records.getAllDerivedDefinitions("OperandWithDefaultOps"); 2510 2511 // Find some SDNode. 2512 assert(!SDNodes.empty() && "No SDNodes parsed?"); 2513 Init *SomeSDNode = DefInit::get(SDNodes.begin()->first); 2514 2515 for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) { 2516 DagInit *DefaultInfo = DefaultOps[i]->getValueAsDag("DefaultOps"); 2517 2518 // Clone the DefaultInfo dag node, changing the operator from 'ops' to 2519 // SomeSDnode so that we can parse this. 2520 std::vector<std::pair<Init*, std::string> > Ops; 2521 for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 2522 Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 2523 DefaultInfo->getArgName(op))); 2524 DagInit *DI = DagInit::get(SomeSDNode, "", Ops); 2525 2526 // Create a TreePattern to parse this. 2527 TreePattern P(DefaultOps[i], DI, false, *this); 2528 assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 2529 2530 // Copy the operands over into a DAGDefaultOperand. 2531 DAGDefaultOperand DefaultOpInfo; 2532 2533 TreePatternNode *T = P.getTree(0); 2534 for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 2535 TreePatternNode *TPN = T->getChild(op); 2536 while (TPN->ApplyTypeConstraints(P, false)) 2537 /* Resolve all types */; 2538 2539 if (TPN->ContainsUnresolvedType()) { 2540 PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" + 2541 DefaultOps[i]->getName() + 2542 "' doesn't have a concrete type!"); 2543 } 2544 DefaultOpInfo.DefaultOps.push_back(TPN); 2545 } 2546 2547 // Insert it into the DefaultOperands map so we can find it later. 2548 DefaultOperands[DefaultOps[i]] = DefaultOpInfo; 2549 } 2550} 2551 2552/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 2553/// instruction input. Return true if this is a real use. 2554static bool HandleUse(TreePattern *I, TreePatternNode *Pat, 2555 std::map<std::string, TreePatternNode*> &InstInputs) { 2556 // No name -> not interesting. 2557 if (Pat->getName().empty()) { 2558 if (Pat->isLeaf()) { 2559 DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue()); 2560 if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 2561 DI->getDef()->isSubClassOf("RegisterOperand"))) 2562 I->error("Input " + DI->getDef()->getName() + " must be named!"); 2563 } 2564 return false; 2565 } 2566 2567 Record *Rec; 2568 if (Pat->isLeaf()) { 2569 DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue()); 2570 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!"); 2571 Rec = DI->getDef(); 2572 } else { 2573 Rec = Pat->getOperator(); 2574 } 2575 2576 // SRCVALUE nodes are ignored. 2577 if (Rec->getName() == "srcvalue") 2578 return false; 2579 2580 TreePatternNode *&Slot = InstInputs[Pat->getName()]; 2581 if (!Slot) { 2582 Slot = Pat; 2583 return true; 2584 } 2585 Record *SlotRec; 2586 if (Slot->isLeaf()) { 2587 SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef(); 2588 } else { 2589 assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 2590 SlotRec = Slot->getOperator(); 2591 } 2592 2593 // Ensure that the inputs agree if we've already seen this input. 2594 if (Rec != SlotRec) 2595 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 2596 if (Slot->getExtTypes() != Pat->getExtTypes()) 2597 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 2598 return true; 2599} 2600 2601/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 2602/// part of "I", the instruction), computing the set of inputs and outputs of 2603/// the pattern. Report errors if we see anything naughty. 2604void CodeGenDAGPatterns:: 2605FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 2606 std::map<std::string, TreePatternNode*> &InstInputs, 2607 std::map<std::string, TreePatternNode*>&InstResults, 2608 std::vector<Record*> &InstImpResults) { 2609 if (Pat->isLeaf()) { 2610 bool isUse = HandleUse(I, Pat, InstInputs); 2611 if (!isUse && Pat->getTransformFn()) 2612 I->error("Cannot specify a transform function for a non-input value!"); 2613 return; 2614 } 2615 2616 if (Pat->getOperator()->getName() == "implicit") { 2617 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 2618 TreePatternNode *Dest = Pat->getChild(i); 2619 if (!Dest->isLeaf()) 2620 I->error("implicitly defined value should be a register!"); 2621 2622 DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue()); 2623 if (!Val || !Val->getDef()->isSubClassOf("Register")) 2624 I->error("implicitly defined value should be a register!"); 2625 InstImpResults.push_back(Val->getDef()); 2626 } 2627 return; 2628 } 2629 2630 if (Pat->getOperator()->getName() != "set") { 2631 // If this is not a set, verify that the children nodes are not void typed, 2632 // and recurse. 2633 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 2634 if (Pat->getChild(i)->getNumTypes() == 0) 2635 I->error("Cannot have void nodes inside of patterns!"); 2636 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, 2637 InstImpResults); 2638 } 2639 2640 // If this is a non-leaf node with no children, treat it basically as if 2641 // it were a leaf. This handles nodes like (imm). 2642 bool isUse = HandleUse(I, Pat, InstInputs); 2643 2644 if (!isUse && Pat->getTransformFn()) 2645 I->error("Cannot specify a transform function for a non-input value!"); 2646 return; 2647 } 2648 2649 // Otherwise, this is a set, validate and collect instruction results. 2650 if (Pat->getNumChildren() == 0) 2651 I->error("set requires operands!"); 2652 2653 if (Pat->getTransformFn()) 2654 I->error("Cannot specify a transform function on a set node!"); 2655 2656 // Check the set destinations. 2657 unsigned NumDests = Pat->getNumChildren()-1; 2658 for (unsigned i = 0; i != NumDests; ++i) { 2659 TreePatternNode *Dest = Pat->getChild(i); 2660 if (!Dest->isLeaf()) 2661 I->error("set destination should be a register!"); 2662 2663 DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue()); 2664 if (!Val) { 2665 I->error("set destination should be a register!"); 2666 continue; 2667 } 2668 2669 if (Val->getDef()->isSubClassOf("RegisterClass") || 2670 Val->getDef()->isSubClassOf("ValueType") || 2671 Val->getDef()->isSubClassOf("RegisterOperand") || 2672 Val->getDef()->isSubClassOf("PointerLikeRegClass")) { 2673 if (Dest->getName().empty()) 2674 I->error("set destination must have a name!"); 2675 if (InstResults.count(Dest->getName())) 2676 I->error("cannot set '" + Dest->getName() +"' multiple times"); 2677 InstResults[Dest->getName()] = Dest; 2678 } else if (Val->getDef()->isSubClassOf("Register")) { 2679 InstImpResults.push_back(Val->getDef()); 2680 } else { 2681 I->error("set destination should be a register!"); 2682 } 2683 } 2684 2685 // Verify and collect info from the computation. 2686 FindPatternInputsAndOutputs(I, Pat->getChild(NumDests), 2687 InstInputs, InstResults, InstImpResults); 2688} 2689 2690//===----------------------------------------------------------------------===// 2691// Instruction Analysis 2692//===----------------------------------------------------------------------===// 2693 2694class InstAnalyzer { 2695 const CodeGenDAGPatterns &CDP; 2696public: 2697 bool hasSideEffects; 2698 bool mayStore; 2699 bool mayLoad; 2700 bool isBitcast; 2701 bool isVariadic; 2702 2703 InstAnalyzer(const CodeGenDAGPatterns &cdp) 2704 : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false), 2705 isBitcast(false), isVariadic(false) {} 2706 2707 void Analyze(const TreePattern *Pat) { 2708 // Assume only the first tree is the pattern. The others are clobber nodes. 2709 AnalyzeNode(Pat->getTree(0)); 2710 } 2711 2712 void Analyze(const PatternToMatch *Pat) { 2713 AnalyzeNode(Pat->getSrcPattern()); 2714 } 2715 2716private: 2717 bool IsNodeBitcast(const TreePatternNode *N) const { 2718 if (hasSideEffects || mayLoad || mayStore || isVariadic) 2719 return false; 2720 2721 if (N->getNumChildren() != 2) 2722 return false; 2723 2724 const TreePatternNode *N0 = N->getChild(0); 2725 if (!N0->isLeaf() || !isa<DefInit>(N0->getLeafValue())) 2726 return false; 2727 2728 const TreePatternNode *N1 = N->getChild(1); 2729 if (N1->isLeaf()) 2730 return false; 2731 if (N1->getNumChildren() != 1 || !N1->getChild(0)->isLeaf()) 2732 return false; 2733 2734 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator()); 2735 if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1) 2736 return false; 2737 return OpInfo.getEnumName() == "ISD::BITCAST"; 2738 } 2739 2740public: 2741 void AnalyzeNode(const TreePatternNode *N) { 2742 if (N->isLeaf()) { 2743 if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) { 2744 Record *LeafRec = DI->getDef(); 2745 // Handle ComplexPattern leaves. 2746 if (LeafRec->isSubClassOf("ComplexPattern")) { 2747 const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 2748 if (CP.hasProperty(SDNPMayStore)) mayStore = true; 2749 if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 2750 if (CP.hasProperty(SDNPSideEffect)) hasSideEffects = true; 2751 } 2752 } 2753 return; 2754 } 2755 2756 // Analyze children. 2757 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2758 AnalyzeNode(N->getChild(i)); 2759 2760 // Ignore set nodes, which are not SDNodes. 2761 if (N->getOperator()->getName() == "set") { 2762 isBitcast = IsNodeBitcast(N); 2763 return; 2764 } 2765 2766 // Notice properties of the node. 2767 if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true; 2768 if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true; 2769 if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true; 2770 if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true; 2771 2772 if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 2773 // If this is an intrinsic, analyze it. 2774 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem) 2775 mayLoad = true;// These may load memory. 2776 2777 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteArgMem) 2778 mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 2779 2780 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem) 2781 // WriteMem intrinsics can have other strange effects. 2782 hasSideEffects = true; 2783 } 2784 } 2785 2786}; 2787 2788static bool InferFromPattern(CodeGenInstruction &InstInfo, 2789 const InstAnalyzer &PatInfo, 2790 Record *PatDef) { 2791 bool Error = false; 2792 2793 // Remember where InstInfo got its flags. 2794 if (InstInfo.hasUndefFlags()) 2795 InstInfo.InferredFrom = PatDef; 2796 2797 // Check explicitly set flags for consistency. 2798 if (InstInfo.hasSideEffects != PatInfo.hasSideEffects && 2799 !InstInfo.hasSideEffects_Unset) { 2800 // Allow explicitly setting hasSideEffects = 1 on instructions, even when 2801 // the pattern has no side effects. That could be useful for div/rem 2802 // instructions that may trap. 2803 if (!InstInfo.hasSideEffects) { 2804 Error = true; 2805 PrintError(PatDef->getLoc(), "Pattern doesn't match hasSideEffects = " + 2806 Twine(InstInfo.hasSideEffects)); 2807 } 2808 } 2809 2810 if (InstInfo.mayStore != PatInfo.mayStore && !InstInfo.mayStore_Unset) { 2811 Error = true; 2812 PrintError(PatDef->getLoc(), "Pattern doesn't match mayStore = " + 2813 Twine(InstInfo.mayStore)); 2814 } 2815 2816 if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) { 2817 // Allow explicitly setting mayLoad = 1, even when the pattern has no loads. 2818 // Some targets translate imediates to loads. 2819 if (!InstInfo.mayLoad) { 2820 Error = true; 2821 PrintError(PatDef->getLoc(), "Pattern doesn't match mayLoad = " + 2822 Twine(InstInfo.mayLoad)); 2823 } 2824 } 2825 2826 // Transfer inferred flags. 2827 InstInfo.hasSideEffects |= PatInfo.hasSideEffects; 2828 InstInfo.mayStore |= PatInfo.mayStore; 2829 InstInfo.mayLoad |= PatInfo.mayLoad; 2830 2831 // These flags are silently added without any verification. 2832 InstInfo.isBitcast |= PatInfo.isBitcast; 2833 2834 // Don't infer isVariadic. This flag means something different on SDNodes and 2835 // instructions. For example, a CALL SDNode is variadic because it has the 2836 // call arguments as operands, but a CALL instruction is not variadic - it 2837 // has argument registers as implicit, not explicit uses. 2838 2839 return Error; 2840} 2841 2842/// hasNullFragReference - Return true if the DAG has any reference to the 2843/// null_frag operator. 2844static bool hasNullFragReference(DagInit *DI) { 2845 DefInit *OpDef = dyn_cast<DefInit>(DI->getOperator()); 2846 if (!OpDef) return false; 2847 Record *Operator = OpDef->getDef(); 2848 2849 // If this is the null fragment, return true. 2850 if (Operator->getName() == "null_frag") return true; 2851 // If any of the arguments reference the null fragment, return true. 2852 for (unsigned i = 0, e = DI->getNumArgs(); i != e; ++i) { 2853 DagInit *Arg = dyn_cast<DagInit>(DI->getArg(i)); 2854 if (Arg && hasNullFragReference(Arg)) 2855 return true; 2856 } 2857 2858 return false; 2859} 2860 2861/// hasNullFragReference - Return true if any DAG in the list references 2862/// the null_frag operator. 2863static bool hasNullFragReference(ListInit *LI) { 2864 for (Init *I : LI->getValues()) { 2865 DagInit *DI = dyn_cast<DagInit>(I); 2866 assert(DI && "non-dag in an instruction Pattern list?!"); 2867 if (hasNullFragReference(DI)) 2868 return true; 2869 } 2870 return false; 2871} 2872 2873/// Get all the instructions in a tree. 2874static void 2875getInstructionsInTree(TreePatternNode *Tree, SmallVectorImpl<Record*> &Instrs) { 2876 if (Tree->isLeaf()) 2877 return; 2878 if (Tree->getOperator()->isSubClassOf("Instruction")) 2879 Instrs.push_back(Tree->getOperator()); 2880 for (unsigned i = 0, e = Tree->getNumChildren(); i != e; ++i) 2881 getInstructionsInTree(Tree->getChild(i), Instrs); 2882} 2883 2884/// Check the class of a pattern leaf node against the instruction operand it 2885/// represents. 2886static bool checkOperandClass(CGIOperandList::OperandInfo &OI, 2887 Record *Leaf) { 2888 if (OI.Rec == Leaf) 2889 return true; 2890 2891 // Allow direct value types to be used in instruction set patterns. 2892 // The type will be checked later. 2893 if (Leaf->isSubClassOf("ValueType")) 2894 return true; 2895 2896 // Patterns can also be ComplexPattern instances. 2897 if (Leaf->isSubClassOf("ComplexPattern")) 2898 return true; 2899 2900 return false; 2901} 2902 2903const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( 2904 CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) { 2905 2906 assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"); 2907 2908 // Parse the instruction. 2909 TreePattern *I = new TreePattern(CGI.TheDef, Pat, true, *this); 2910 // Inline pattern fragments into it. 2911 I->InlinePatternFragments(); 2912 2913 // Infer as many types as possible. If we cannot infer all of them, we can 2914 // never do anything with this instruction pattern: report it to the user. 2915 if (!I->InferAllTypes()) 2916 I->error("Could not infer all types in pattern!"); 2917 2918 // InstInputs - Keep track of all of the inputs of the instruction, along 2919 // with the record they are declared as. 2920 std::map<std::string, TreePatternNode*> InstInputs; 2921 2922 // InstResults - Keep track of all the virtual registers that are 'set' 2923 // in the instruction, including what reg class they are. 2924 std::map<std::string, TreePatternNode*> InstResults; 2925 2926 std::vector<Record*> InstImpResults; 2927 2928 // Verify that the top-level forms in the instruction are of void type, and 2929 // fill in the InstResults map. 2930 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { 2931 TreePatternNode *Pat = I->getTree(j); 2932 if (Pat->getNumTypes() != 0) 2933 I->error("Top-level forms in instruction pattern should have" 2934 " void types"); 2935 2936 // Find inputs and outputs, and verify the structure of the uses/defs. 2937 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 2938 InstImpResults); 2939 } 2940 2941 // Now that we have inputs and outputs of the pattern, inspect the operands 2942 // list for the instruction. This determines the order that operands are 2943 // added to the machine instruction the node corresponds to. 2944 unsigned NumResults = InstResults.size(); 2945 2946 // Parse the operands list from the (ops) list, validating it. 2947 assert(I->getArgList().empty() && "Args list should still be empty here!"); 2948 2949 // Check that all of the results occur first in the list. 2950 std::vector<Record*> Results; 2951 SmallVector<TreePatternNode *, 2> ResNodes; 2952 for (unsigned i = 0; i != NumResults; ++i) { 2953 if (i == CGI.Operands.size()) 2954 I->error("'" + InstResults.begin()->first + 2955 "' set but does not appear in operand list!"); 2956 const std::string &OpName = CGI.Operands[i].Name; 2957 2958 // Check that it exists in InstResults. 2959 TreePatternNode *RNode = InstResults[OpName]; 2960 if (!RNode) 2961 I->error("Operand $" + OpName + " does not exist in operand list!"); 2962 2963 ResNodes.push_back(RNode); 2964 2965 Record *R = cast<DefInit>(RNode->getLeafValue())->getDef(); 2966 if (!R) 2967 I->error("Operand $" + OpName + " should be a set destination: all " 2968 "outputs must occur before inputs in operand list!"); 2969 2970 if (!checkOperandClass(CGI.Operands[i], R)) 2971 I->error("Operand $" + OpName + " class mismatch!"); 2972 2973 // Remember the return type. 2974 Results.push_back(CGI.Operands[i].Rec); 2975 2976 // Okay, this one checks out. 2977 InstResults.erase(OpName); 2978 } 2979 2980 // Loop over the inputs next. Make a copy of InstInputs so we can destroy 2981 // the copy while we're checking the inputs. 2982 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs); 2983 2984 std::vector<TreePatternNode*> ResultNodeOperands; 2985 std::vector<Record*> Operands; 2986 for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) { 2987 CGIOperandList::OperandInfo &Op = CGI.Operands[i]; 2988 const std::string &OpName = Op.Name; 2989 if (OpName.empty()) 2990 I->error("Operand #" + utostr(i) + " in operands list has no name!"); 2991 2992 if (!InstInputsCheck.count(OpName)) { 2993 // If this is an operand with a DefaultOps set filled in, we can ignore 2994 // this. When we codegen it, we will do so as always executed. 2995 if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) { 2996 // Does it have a non-empty DefaultOps field? If so, ignore this 2997 // operand. 2998 if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 2999 continue; 3000 } 3001 I->error("Operand $" + OpName + 3002 " does not appear in the instruction pattern"); 3003 } 3004 TreePatternNode *InVal = InstInputsCheck[OpName]; 3005 InstInputsCheck.erase(OpName); // It occurred, remove from map. 3006 3007 if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) { 3008 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 3009 if (!checkOperandClass(Op, InRec)) 3010 I->error("Operand $" + OpName + "'s register class disagrees" 3011 " between the operand and pattern"); 3012 } 3013 Operands.push_back(Op.Rec); 3014 3015 // Construct the result for the dest-pattern operand list. 3016 TreePatternNode *OpNode = InVal->clone(); 3017 3018 // No predicate is useful on the result. 3019 OpNode->clearPredicateFns(); 3020 3021 // Promote the xform function to be an explicit node if set. 3022 if (Record *Xform = OpNode->getTransformFn()) { 3023 OpNode->setTransformFn(nullptr); 3024 std::vector<TreePatternNode*> Children; 3025 Children.push_back(OpNode); 3026 OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); 3027 } 3028 3029 ResultNodeOperands.push_back(OpNode); 3030 } 3031 3032 if (!InstInputsCheck.empty()) 3033 I->error("Input operand $" + InstInputsCheck.begin()->first + 3034 " occurs in pattern but not in operands list!"); 3035 3036 TreePatternNode *ResultPattern = 3037 new TreePatternNode(I->getRecord(), ResultNodeOperands, 3038 GetNumNodeResults(I->getRecord(), *this)); 3039 // Copy fully inferred output node types to instruction result pattern. 3040 for (unsigned i = 0; i != NumResults; ++i) { 3041 assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"); 3042 ResultPattern->setType(i, ResNodes[i]->getExtType(0)); 3043 } 3044 3045 // Create and insert the instruction. 3046 // FIXME: InstImpResults should not be part of DAGInstruction. 3047 DAGInstruction TheInst(I, Results, Operands, InstImpResults); 3048 DAGInsts.insert(std::make_pair(I->getRecord(), TheInst)); 3049 3050 // Use a temporary tree pattern to infer all types and make sure that the 3051 // constructed result is correct. This depends on the instruction already 3052 // being inserted into the DAGInsts map. 3053 TreePattern Temp(I->getRecord(), ResultPattern, false, *this); 3054 Temp.InferAllTypes(&I->getNamedNodesMap()); 3055 3056 DAGInstruction &TheInsertedInst = DAGInsts.find(I->getRecord())->second; 3057 TheInsertedInst.setResultPattern(Temp.getOnlyTree()); 3058 3059 return TheInsertedInst; 3060} 3061 3062/// ParseInstructions - Parse all of the instructions, inlining and resolving 3063/// any fragments involved. This populates the Instructions list with fully 3064/// resolved instructions. 3065void CodeGenDAGPatterns::ParseInstructions() { 3066 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 3067 3068 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 3069 ListInit *LI = nullptr; 3070 3071 if (isa<ListInit>(Instrs[i]->getValueInit("Pattern"))) 3072 LI = Instrs[i]->getValueAsListInit("Pattern"); 3073 3074 // If there is no pattern, only collect minimal information about the 3075 // instruction for its operand list. We have to assume that there is one 3076 // result, as we have no detailed info. A pattern which references the 3077 // null_frag operator is as-if no pattern were specified. Normally this 3078 // is from a multiclass expansion w/ a SDPatternOperator passed in as 3079 // null_frag. 3080 if (!LI || LI->empty() || hasNullFragReference(LI)) { 3081 std::vector<Record*> Results; 3082 std::vector<Record*> Operands; 3083 3084 CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); 3085 3086 if (InstInfo.Operands.size() != 0) { 3087 for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j) 3088 Results.push_back(InstInfo.Operands[j].Rec); 3089 3090 // The rest are inputs. 3091 for (unsigned j = InstInfo.Operands.NumDefs, 3092 e = InstInfo.Operands.size(); j < e; ++j) 3093 Operands.push_back(InstInfo.Operands[j].Rec); 3094 } 3095 3096 // Create and insert the instruction. 3097 std::vector<Record*> ImpResults; 3098 Instructions.insert(std::make_pair(Instrs[i], 3099 DAGInstruction(nullptr, Results, Operands, ImpResults))); 3100 continue; // no pattern. 3101 } 3102 3103 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]); 3104 const DAGInstruction &DI = parseInstructionPattern(CGI, LI, Instructions); 3105 3106 (void)DI; 3107 DEBUG(DI.getPattern()->dump()); 3108 } 3109 3110 // If we can, convert the instructions to be patterns that are matched! 3111 for (std::map<Record*, DAGInstruction, LessRecordByID>::iterator II = 3112 Instructions.begin(), 3113 E = Instructions.end(); II != E; ++II) { 3114 DAGInstruction &TheInst = II->second; 3115 TreePattern *I = TheInst.getPattern(); 3116 if (!I) continue; // No pattern. 3117 3118 // FIXME: Assume only the first tree is the pattern. The others are clobber 3119 // nodes. 3120 TreePatternNode *Pattern = I->getTree(0); 3121 TreePatternNode *SrcPattern; 3122 if (Pattern->getOperator()->getName() == "set") { 3123 SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 3124 } else{ 3125 // Not a set (store or something?) 3126 SrcPattern = Pattern; 3127 } 3128 3129 Record *Instr = II->first; 3130 AddPatternToMatch(I, 3131 PatternToMatch(Instr, 3132 Instr->getValueAsListInit("Predicates"), 3133 SrcPattern, 3134 TheInst.getResultPattern(), 3135 TheInst.getImpResults(), 3136 Instr->getValueAsInt("AddedComplexity"), 3137 Instr->getID())); 3138 } 3139} 3140 3141 3142typedef std::pair<const TreePatternNode*, unsigned> NameRecord; 3143 3144static void FindNames(const TreePatternNode *P, 3145 std::map<std::string, NameRecord> &Names, 3146 TreePattern *PatternTop) { 3147 if (!P->getName().empty()) { 3148 NameRecord &Rec = Names[P->getName()]; 3149 // If this is the first instance of the name, remember the node. 3150 if (Rec.second++ == 0) 3151 Rec.first = P; 3152 else if (Rec.first->getExtTypes() != P->getExtTypes()) 3153 PatternTop->error("repetition of value: $" + P->getName() + 3154 " where different uses have different types!"); 3155 } 3156 3157 if (!P->isLeaf()) { 3158 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 3159 FindNames(P->getChild(i), Names, PatternTop); 3160 } 3161} 3162 3163void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern, 3164 const PatternToMatch &PTM) { 3165 // Do some sanity checking on the pattern we're about to match. 3166 std::string Reason; 3167 if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) { 3168 PrintWarning(Pattern->getRecord()->getLoc(), 3169 Twine("Pattern can never match: ") + Reason); 3170 return; 3171 } 3172 3173 // If the source pattern's root is a complex pattern, that complex pattern 3174 // must specify the nodes it can potentially match. 3175 if (const ComplexPattern *CP = 3176 PTM.getSrcPattern()->getComplexPatternInfo(*this)) 3177 if (CP->getRootNodes().empty()) 3178 Pattern->error("ComplexPattern at root must specify list of opcodes it" 3179 " could match"); 3180 3181 3182 // Find all of the named values in the input and output, ensure they have the 3183 // same type. 3184 std::map<std::string, NameRecord> SrcNames, DstNames; 3185 FindNames(PTM.getSrcPattern(), SrcNames, Pattern); 3186 FindNames(PTM.getDstPattern(), DstNames, Pattern); 3187 3188 // Scan all of the named values in the destination pattern, rejecting them if 3189 // they don't exist in the input pattern. 3190 for (std::map<std::string, NameRecord>::iterator 3191 I = DstNames.begin(), E = DstNames.end(); I != E; ++I) { 3192 if (SrcNames[I->first].first == nullptr) 3193 Pattern->error("Pattern has input without matching name in output: $" + 3194 I->first); 3195 } 3196 3197 // Scan all of the named values in the source pattern, rejecting them if the 3198 // name isn't used in the dest, and isn't used to tie two values together. 3199 for (std::map<std::string, NameRecord>::iterator 3200 I = SrcNames.begin(), E = SrcNames.end(); I != E; ++I) 3201 if (DstNames[I->first].first == nullptr && SrcNames[I->first].second == 1) 3202 Pattern->error("Pattern has dead named input: $" + I->first); 3203 3204 PatternsToMatch.push_back(PTM); 3205} 3206 3207 3208 3209void CodeGenDAGPatterns::InferInstructionFlags() { 3210 const std::vector<const CodeGenInstruction*> &Instructions = 3211 Target.getInstructionsByEnumValue(); 3212 3213 // First try to infer flags from the primary instruction pattern, if any. 3214 SmallVector<CodeGenInstruction*, 8> Revisit; 3215 unsigned Errors = 0; 3216 for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 3217 CodeGenInstruction &InstInfo = 3218 const_cast<CodeGenInstruction &>(*Instructions[i]); 3219 3220 // Get the primary instruction pattern. 3221 const TreePattern *Pattern = getInstruction(InstInfo.TheDef).getPattern(); 3222 if (!Pattern) { 3223 if (InstInfo.hasUndefFlags()) 3224 Revisit.push_back(&InstInfo); 3225 continue; 3226 } 3227 InstAnalyzer PatInfo(*this); 3228 PatInfo.Analyze(Pattern); 3229 Errors += InferFromPattern(InstInfo, PatInfo, InstInfo.TheDef); 3230 } 3231 3232 // Second, look for single-instruction patterns defined outside the 3233 // instruction. 3234 for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) { 3235 const PatternToMatch &PTM = *I; 3236 3237 // We can only infer from single-instruction patterns, otherwise we won't 3238 // know which instruction should get the flags. 3239 SmallVector<Record*, 8> PatInstrs; 3240 getInstructionsInTree(PTM.getDstPattern(), PatInstrs); 3241 if (PatInstrs.size() != 1) 3242 continue; 3243 3244 // Get the single instruction. 3245 CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front()); 3246 3247 // Only infer properties from the first pattern. We'll verify the others. 3248 if (InstInfo.InferredFrom) 3249 continue; 3250 3251 InstAnalyzer PatInfo(*this); 3252 PatInfo.Analyze(&PTM); 3253 Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord()); 3254 } 3255 3256 if (Errors) 3257 PrintFatalError("pattern conflicts"); 3258 3259 // Revisit instructions with undefined flags and no pattern. 3260 if (Target.guessInstructionProperties()) { 3261 for (unsigned i = 0, e = Revisit.size(); i != e; ++i) { 3262 CodeGenInstruction &InstInfo = *Revisit[i]; 3263 if (InstInfo.InferredFrom) 3264 continue; 3265 // The mayLoad and mayStore flags default to false. 3266 // Conservatively assume hasSideEffects if it wasn't explicit. 3267 if (InstInfo.hasSideEffects_Unset) 3268 InstInfo.hasSideEffects = true; 3269 } 3270 return; 3271 } 3272 3273 // Complain about any flags that are still undefined. 3274 for (unsigned i = 0, e = Revisit.size(); i != e; ++i) { 3275 CodeGenInstruction &InstInfo = *Revisit[i]; 3276 if (InstInfo.InferredFrom) 3277 continue; 3278 if (InstInfo.hasSideEffects_Unset) 3279 PrintError(InstInfo.TheDef->getLoc(), 3280 "Can't infer hasSideEffects from patterns"); 3281 if (InstInfo.mayStore_Unset) 3282 PrintError(InstInfo.TheDef->getLoc(), 3283 "Can't infer mayStore from patterns"); 3284 if (InstInfo.mayLoad_Unset) 3285 PrintError(InstInfo.TheDef->getLoc(), 3286 "Can't infer mayLoad from patterns"); 3287 } 3288} 3289 3290 3291/// Verify instruction flags against pattern node properties. 3292void CodeGenDAGPatterns::VerifyInstructionFlags() { 3293 unsigned Errors = 0; 3294 for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) { 3295 const PatternToMatch &PTM = *I; 3296 SmallVector<Record*, 8> Instrs; 3297 getInstructionsInTree(PTM.getDstPattern(), Instrs); 3298 if (Instrs.empty()) 3299 continue; 3300 3301 // Count the number of instructions with each flag set. 3302 unsigned NumSideEffects = 0; 3303 unsigned NumStores = 0; 3304 unsigned NumLoads = 0; 3305 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 3306 const CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); 3307 NumSideEffects += InstInfo.hasSideEffects; 3308 NumStores += InstInfo.mayStore; 3309 NumLoads += InstInfo.mayLoad; 3310 } 3311 3312 // Analyze the source pattern. 3313 InstAnalyzer PatInfo(*this); 3314 PatInfo.Analyze(&PTM); 3315 3316 // Collect error messages. 3317 SmallVector<std::string, 4> Msgs; 3318 3319 // Check for missing flags in the output. 3320 // Permit extra flags for now at least. 3321 if (PatInfo.hasSideEffects && !NumSideEffects) 3322 Msgs.push_back("pattern has side effects, but hasSideEffects isn't set"); 3323 3324 // Don't verify store flags on instructions with side effects. At least for 3325 // intrinsics, side effects implies mayStore. 3326 if (!PatInfo.hasSideEffects && PatInfo.mayStore && !NumStores) 3327 Msgs.push_back("pattern may store, but mayStore isn't set"); 3328 3329 // Similarly, mayStore implies mayLoad on intrinsics. 3330 if (!PatInfo.mayStore && PatInfo.mayLoad && !NumLoads) 3331 Msgs.push_back("pattern may load, but mayLoad isn't set"); 3332 3333 // Print error messages. 3334 if (Msgs.empty()) 3335 continue; 3336 ++Errors; 3337 3338 for (unsigned i = 0, e = Msgs.size(); i != e; ++i) 3339 PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msgs[i]) + " on the " + 3340 (Instrs.size() == 1 ? 3341 "instruction" : "output instructions")); 3342 // Provide the location of the relevant instruction definitions. 3343 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 3344 if (Instrs[i] != PTM.getSrcRecord()) 3345 PrintError(Instrs[i]->getLoc(), "defined here"); 3346 const CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); 3347 if (InstInfo.InferredFrom && 3348 InstInfo.InferredFrom != InstInfo.TheDef && 3349 InstInfo.InferredFrom != PTM.getSrcRecord()) 3350 PrintError(InstInfo.InferredFrom->getLoc(), "inferred from patttern"); 3351 } 3352 } 3353 if (Errors) 3354 PrintFatalError("Errors in DAG patterns"); 3355} 3356 3357/// Given a pattern result with an unresolved type, see if we can find one 3358/// instruction with an unresolved result type. Force this result type to an 3359/// arbitrary element if it's possible types to converge results. 3360static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { 3361 if (N->isLeaf()) 3362 return false; 3363 3364 // Analyze children. 3365 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 3366 if (ForceArbitraryInstResultType(N->getChild(i), TP)) 3367 return true; 3368 3369 if (!N->getOperator()->isSubClassOf("Instruction")) 3370 return false; 3371 3372 // If this type is already concrete or completely unknown we can't do 3373 // anything. 3374 for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) { 3375 if (N->getExtType(i).isCompletelyUnknown() || N->getExtType(i).isConcrete()) 3376 continue; 3377 3378 // Otherwise, force its type to the first possibility (an arbitrary choice). 3379 if (N->getExtType(i).MergeInTypeInfo(N->getExtType(i).getTypeList()[0], TP)) 3380 return true; 3381 } 3382 3383 return false; 3384} 3385 3386void CodeGenDAGPatterns::ParsePatterns() { 3387 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 3388 3389 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 3390 Record *CurPattern = Patterns[i]; 3391 DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); 3392 3393 // If the pattern references the null_frag, there's nothing to do. 3394 if (hasNullFragReference(Tree)) 3395 continue; 3396 3397 TreePattern *Pattern = new TreePattern(CurPattern, Tree, true, *this); 3398 3399 // Inline pattern fragments into it. 3400 Pattern->InlinePatternFragments(); 3401 3402 ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); 3403 if (LI->empty()) continue; // no pattern. 3404 3405 // Parse the instruction. 3406 TreePattern Result(CurPattern, LI, false, *this); 3407 3408 // Inline pattern fragments into it. 3409 Result.InlinePatternFragments(); 3410 3411 if (Result.getNumTrees() != 1) 3412 Result.error("Cannot handle instructions producing instructions " 3413 "with temporaries yet!"); 3414 3415 bool IterateInference; 3416 bool InferredAllPatternTypes, InferredAllResultTypes; 3417 do { 3418 // Infer as many types as possible. If we cannot infer all of them, we 3419 // can never do anything with this pattern: report it to the user. 3420 InferredAllPatternTypes = 3421 Pattern->InferAllTypes(&Pattern->getNamedNodesMap()); 3422 3423 // Infer as many types as possible. If we cannot infer all of them, we 3424 // can never do anything with this pattern: report it to the user. 3425 InferredAllResultTypes = 3426 Result.InferAllTypes(&Pattern->getNamedNodesMap()); 3427 3428 IterateInference = false; 3429 3430 // Apply the type of the result to the source pattern. This helps us 3431 // resolve cases where the input type is known to be a pointer type (which 3432 // is considered resolved), but the result knows it needs to be 32- or 3433 // 64-bits. Infer the other way for good measure. 3434 for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(), 3435 Pattern->getTree(0)->getNumTypes()); 3436 i != e; ++i) { 3437 IterateInference = Pattern->getTree(0)->UpdateNodeType( 3438 i, Result.getTree(0)->getExtType(i), Result); 3439 IterateInference |= Result.getTree(0)->UpdateNodeType( 3440 i, Pattern->getTree(0)->getExtType(i), Result); 3441 } 3442 3443 // If our iteration has converged and the input pattern's types are fully 3444 // resolved but the result pattern is not fully resolved, we may have a 3445 // situation where we have two instructions in the result pattern and 3446 // the instructions require a common register class, but don't care about 3447 // what actual MVT is used. This is actually a bug in our modelling: 3448 // output patterns should have register classes, not MVTs. 3449 // 3450 // In any case, to handle this, we just go through and disambiguate some 3451 // arbitrary types to the result pattern's nodes. 3452 if (!IterateInference && InferredAllPatternTypes && 3453 !InferredAllResultTypes) 3454 IterateInference = 3455 ForceArbitraryInstResultType(Result.getTree(0), Result); 3456 } while (IterateInference); 3457 3458 // Verify that we inferred enough types that we can do something with the 3459 // pattern and result. If these fire the user has to add type casts. 3460 if (!InferredAllPatternTypes) 3461 Pattern->error("Could not infer all types in pattern!"); 3462 if (!InferredAllResultTypes) { 3463 Pattern->dump(); 3464 Result.error("Could not infer all types in pattern result!"); 3465 } 3466 3467 // Validate that the input pattern is correct. 3468 std::map<std::string, TreePatternNode*> InstInputs; 3469 std::map<std::string, TreePatternNode*> InstResults; 3470 std::vector<Record*> InstImpResults; 3471 for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j) 3472 FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j), 3473 InstInputs, InstResults, 3474 InstImpResults); 3475 3476 // Promote the xform function to be an explicit node if set. 3477 TreePatternNode *DstPattern = Result.getOnlyTree(); 3478 std::vector<TreePatternNode*> ResultNodeOperands; 3479 for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { 3480 TreePatternNode *OpNode = DstPattern->getChild(ii); 3481 if (Record *Xform = OpNode->getTransformFn()) { 3482 OpNode->setTransformFn(nullptr); 3483 std::vector<TreePatternNode*> Children; 3484 Children.push_back(OpNode); 3485 OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); 3486 } 3487 ResultNodeOperands.push_back(OpNode); 3488 } 3489 DstPattern = Result.getOnlyTree(); 3490 if (!DstPattern->isLeaf()) 3491 DstPattern = new TreePatternNode(DstPattern->getOperator(), 3492 ResultNodeOperands, 3493 DstPattern->getNumTypes()); 3494 3495 for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i) 3496 DstPattern->setType(i, Result.getOnlyTree()->getExtType(i)); 3497 3498 TreePattern Temp(Result.getRecord(), DstPattern, false, *this); 3499 Temp.InferAllTypes(); 3500 3501 3502 AddPatternToMatch(Pattern, 3503 PatternToMatch(CurPattern, 3504 CurPattern->getValueAsListInit("Predicates"), 3505 Pattern->getTree(0), 3506 Temp.getOnlyTree(), InstImpResults, 3507 CurPattern->getValueAsInt("AddedComplexity"), 3508 CurPattern->getID())); 3509 } 3510} 3511 3512/// CombineChildVariants - Given a bunch of permutations of each child of the 3513/// 'operator' node, put them together in all possible ways. 3514static void CombineChildVariants(TreePatternNode *Orig, 3515 const std::vector<std::vector<TreePatternNode*> > &ChildVariants, 3516 std::vector<TreePatternNode*> &OutVariants, 3517 CodeGenDAGPatterns &CDP, 3518 const MultipleUseVarSet &DepVars) { 3519 // Make sure that each operand has at least one variant to choose from. 3520 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 3521 if (ChildVariants[i].empty()) 3522 return; 3523 3524 // The end result is an all-pairs construction of the resultant pattern. 3525 std::vector<unsigned> Idxs; 3526 Idxs.resize(ChildVariants.size()); 3527 bool NotDone; 3528 do { 3529#ifndef NDEBUG 3530 DEBUG(if (!Idxs.empty()) { 3531 errs() << Orig->getOperator()->getName() << ": Idxs = [ "; 3532 for (unsigned i = 0; i < Idxs.size(); ++i) { 3533 errs() << Idxs[i] << " "; 3534 } 3535 errs() << "]\n"; 3536 }); 3537#endif 3538 // Create the variant and add it to the output list. 3539 std::vector<TreePatternNode*> NewChildren; 3540 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 3541 NewChildren.push_back(ChildVariants[i][Idxs[i]]); 3542 TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren, 3543 Orig->getNumTypes()); 3544 3545 // Copy over properties. 3546 R->setName(Orig->getName()); 3547 R->setPredicateFns(Orig->getPredicateFns()); 3548 R->setTransformFn(Orig->getTransformFn()); 3549 for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) 3550 R->setType(i, Orig->getExtType(i)); 3551 3552 // If this pattern cannot match, do not include it as a variant. 3553 std::string ErrString; 3554 if (!R->canPatternMatch(ErrString, CDP)) { 3555 delete R; 3556 } else { 3557 bool AlreadyExists = false; 3558 3559 // Scan to see if this pattern has already been emitted. We can get 3560 // duplication due to things like commuting: 3561 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 3562 // which are the same pattern. Ignore the dups. 3563 for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) 3564 if (R->isIsomorphicTo(OutVariants[i], DepVars)) { 3565 AlreadyExists = true; 3566 break; 3567 } 3568 3569 if (AlreadyExists) 3570 delete R; 3571 else 3572 OutVariants.push_back(R); 3573 } 3574 3575 // Increment indices to the next permutation by incrementing the 3576 // indicies from last index backward, e.g., generate the sequence 3577 // [0, 0], [0, 1], [1, 0], [1, 1]. 3578 int IdxsIdx; 3579 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 3580 if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 3581 Idxs[IdxsIdx] = 0; 3582 else 3583 break; 3584 } 3585 NotDone = (IdxsIdx >= 0); 3586 } while (NotDone); 3587} 3588 3589/// CombineChildVariants - A helper function for binary operators. 3590/// 3591static void CombineChildVariants(TreePatternNode *Orig, 3592 const std::vector<TreePatternNode*> &LHS, 3593 const std::vector<TreePatternNode*> &RHS, 3594 std::vector<TreePatternNode*> &OutVariants, 3595 CodeGenDAGPatterns &CDP, 3596 const MultipleUseVarSet &DepVars) { 3597 std::vector<std::vector<TreePatternNode*> > ChildVariants; 3598 ChildVariants.push_back(LHS); 3599 ChildVariants.push_back(RHS); 3600 CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 3601} 3602 3603 3604static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, 3605 std::vector<TreePatternNode *> &Children) { 3606 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 3607 Record *Operator = N->getOperator(); 3608 3609 // Only permit raw nodes. 3610 if (!N->getName().empty() || !N->getPredicateFns().empty() || 3611 N->getTransformFn()) { 3612 Children.push_back(N); 3613 return; 3614 } 3615 3616 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 3617 Children.push_back(N->getChild(0)); 3618 else 3619 GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); 3620 3621 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 3622 Children.push_back(N->getChild(1)); 3623 else 3624 GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); 3625} 3626 3627/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 3628/// the (potentially recursive) pattern by using algebraic laws. 3629/// 3630static void GenerateVariantsOf(TreePatternNode *N, 3631 std::vector<TreePatternNode*> &OutVariants, 3632 CodeGenDAGPatterns &CDP, 3633 const MultipleUseVarSet &DepVars) { 3634 // We cannot permute leaves or ComplexPattern uses. 3635 if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) { 3636 OutVariants.push_back(N); 3637 return; 3638 } 3639 3640 // Look up interesting info about the node. 3641 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 3642 3643 // If this node is associative, re-associate. 3644 if (NodeInfo.hasProperty(SDNPAssociative)) { 3645 // Re-associate by pulling together all of the linked operators 3646 std::vector<TreePatternNode*> MaximalChildren; 3647 GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 3648 3649 // Only handle child sizes of 3. Otherwise we'll end up trying too many 3650 // permutations. 3651 if (MaximalChildren.size() == 3) { 3652 // Find the variants of all of our maximal children. 3653 std::vector<TreePatternNode*> AVariants, BVariants, CVariants; 3654 GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 3655 GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 3656 GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 3657 3658 // There are only two ways we can permute the tree: 3659 // (A op B) op C and A op (B op C) 3660 // Within these forms, we can also permute A/B/C. 3661 3662 // Generate legal pair permutations of A/B/C. 3663 std::vector<TreePatternNode*> ABVariants; 3664 std::vector<TreePatternNode*> BAVariants; 3665 std::vector<TreePatternNode*> ACVariants; 3666 std::vector<TreePatternNode*> CAVariants; 3667 std::vector<TreePatternNode*> BCVariants; 3668 std::vector<TreePatternNode*> CBVariants; 3669 CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 3670 CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 3671 CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 3672 CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 3673 CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 3674 CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 3675 3676 // Combine those into the result: (x op x) op x 3677 CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 3678 CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 3679 CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 3680 CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 3681 CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 3682 CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 3683 3684 // Combine those into the result: x op (x op x) 3685 CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 3686 CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 3687 CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 3688 CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 3689 CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 3690 CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 3691 return; 3692 } 3693 } 3694 3695 // Compute permutations of all children. 3696 std::vector<std::vector<TreePatternNode*> > ChildVariants; 3697 ChildVariants.resize(N->getNumChildren()); 3698 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 3699 GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars); 3700 3701 // Build all permutations based on how the children were formed. 3702 CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 3703 3704 // If this node is commutative, consider the commuted order. 3705 bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP); 3706 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 3707 assert((N->getNumChildren()==2 || isCommIntrinsic) && 3708 "Commutative but doesn't have 2 children!"); 3709 // Don't count children which are actually register references. 3710 unsigned NC = 0; 3711 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 3712 TreePatternNode *Child = N->getChild(i); 3713 if (Child->isLeaf()) 3714 if (DefInit *DI = dyn_cast<DefInit>(Child->getLeafValue())) { 3715 Record *RR = DI->getDef(); 3716 if (RR->isSubClassOf("Register")) 3717 continue; 3718 } 3719 NC++; 3720 } 3721 // Consider the commuted order. 3722 if (isCommIntrinsic) { 3723 // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd 3724 // operands are the commutative operands, and there might be more operands 3725 // after those. 3726 assert(NC >= 3 && 3727 "Commutative intrinsic should have at least 3 childrean!"); 3728 std::vector<std::vector<TreePatternNode*> > Variants; 3729 Variants.push_back(ChildVariants[0]); // Intrinsic id. 3730 Variants.push_back(ChildVariants[2]); 3731 Variants.push_back(ChildVariants[1]); 3732 for (unsigned i = 3; i != NC; ++i) 3733 Variants.push_back(ChildVariants[i]); 3734 CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 3735 } else if (NC == 2) 3736 CombineChildVariants(N, ChildVariants[1], ChildVariants[0], 3737 OutVariants, CDP, DepVars); 3738 } 3739} 3740 3741 3742// GenerateVariants - Generate variants. For example, commutative patterns can 3743// match multiple ways. Add them to PatternsToMatch as well. 3744void CodeGenDAGPatterns::GenerateVariants() { 3745 DEBUG(errs() << "Generating instruction variants.\n"); 3746 3747 // Loop over all of the patterns we've collected, checking to see if we can 3748 // generate variants of the instruction, through the exploitation of 3749 // identities. This permits the target to provide aggressive matching without 3750 // the .td file having to contain tons of variants of instructions. 3751 // 3752 // Note that this loop adds new patterns to the PatternsToMatch list, but we 3753 // intentionally do not reconsider these. Any variants of added patterns have 3754 // already been added. 3755 // 3756 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 3757 MultipleUseVarSet DepVars; 3758 std::vector<TreePatternNode*> Variants; 3759 FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 3760 DEBUG(errs() << "Dependent/multiply used variables: "); 3761 DEBUG(DumpDepVars(DepVars)); 3762 DEBUG(errs() << "\n"); 3763 GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, 3764 DepVars); 3765 3766 assert(!Variants.empty() && "Must create at least original variant!"); 3767 Variants.erase(Variants.begin()); // Remove the original pattern. 3768 3769 if (Variants.empty()) // No variants for this pattern. 3770 continue; 3771 3772 DEBUG(errs() << "FOUND VARIANTS OF: "; 3773 PatternsToMatch[i].getSrcPattern()->dump(); 3774 errs() << "\n"); 3775 3776 for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 3777 TreePatternNode *Variant = Variants[v]; 3778 3779 DEBUG(errs() << " VAR#" << v << ": "; 3780 Variant->dump(); 3781 errs() << "\n"); 3782 3783 // Scan to see if an instruction or explicit pattern already matches this. 3784 bool AlreadyExists = false; 3785 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 3786 // Skip if the top level predicates do not match. 3787 if (PatternsToMatch[i].getPredicates() != 3788 PatternsToMatch[p].getPredicates()) 3789 continue; 3790 // Check to see if this variant already exists. 3791 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), 3792 DepVars)) { 3793 DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n"); 3794 AlreadyExists = true; 3795 break; 3796 } 3797 } 3798 // If we already have it, ignore the variant. 3799 if (AlreadyExists) continue; 3800 3801 // Otherwise, add it to the list of patterns we have. 3802 PatternsToMatch.emplace_back( 3803 PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(), 3804 Variant, PatternsToMatch[i].getDstPattern(), 3805 PatternsToMatch[i].getDstRegs(), 3806 PatternsToMatch[i].getAddedComplexity(), Record::getNewUID()); 3807 } 3808 3809 DEBUG(errs() << "\n"); 3810 } 3811} 3812