1 //===- DAGISelMatcher.h - Representation of DAG pattern matcher -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_UTILS_TABLEGEN_DAGISELMATCHER_H 10 #define LLVM_UTILS_TABLEGEN_DAGISELMATCHER_H 11 12 #include "llvm/ADT/ArrayRef.h" 13 #include "llvm/ADT/SmallVector.h" 14 #include "llvm/ADT/StringRef.h" 15 #include "llvm/CodeGen/MachineValueType.h" 16 #include "llvm/Support/Casting.h" 17 #include <cassert> 18 #include <cstddef> 19 #include <memory> 20 #include <string> 21 #include <utility> 22 23 namespace llvm { 24 class CodeGenRegister; 25 class CodeGenDAGPatterns; 26 class CodeGenInstruction; 27 class Matcher; 28 class PatternToMatch; 29 class raw_ostream; 30 class ComplexPattern; 31 class Record; 32 class SDNodeInfo; 33 class TreePredicateFn; 34 class TreePattern; 35 36 Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,unsigned Variant, 37 const CodeGenDAGPatterns &CGP); 38 void OptimizeMatcher(std::unique_ptr<Matcher> &Matcher, 39 const CodeGenDAGPatterns &CGP); 40 void EmitMatcherTable(Matcher *Matcher, const CodeGenDAGPatterns &CGP, 41 raw_ostream &OS); 42 43 44 /// Matcher - Base class for all the DAG ISel Matcher representation 45 /// nodes. 46 class Matcher { 47 // The next matcher node that is executed after this one. Null if this is the 48 // last stage of a match. 49 std::unique_ptr<Matcher> Next; 50 size_t Size = 0; // Size in bytes of matcher and all its children (if any). 51 virtual void anchor(); 52 public: 53 enum KindTy { 54 // Matcher state manipulation. 55 Scope, // Push a checking scope. 56 RecordNode, // Record the current node. 57 RecordChild, // Record a child of the current node. 58 RecordMemRef, // Record the memref in the current node. 59 CaptureGlueInput, // If the current node has an input glue, save it. 60 MoveChild, // Move current node to specified child. 61 MoveParent, // Move current node to parent. 62 63 // Predicate checking. 64 CheckSame, // Fail if not same as prev match. 65 CheckChildSame, // Fail if child not same as prev match. 66 CheckPatternPredicate, 67 CheckPredicate, // Fail if node predicate fails. 68 CheckOpcode, // Fail if not opcode. 69 SwitchOpcode, // Dispatch based on opcode. 70 CheckType, // Fail if not correct type. 71 SwitchType, // Dispatch based on type. 72 CheckChildType, // Fail if child has wrong type. 73 CheckInteger, // Fail if wrong val. 74 CheckChildInteger, // Fail if child is wrong val. 75 CheckCondCode, // Fail if not condcode. 76 CheckChild2CondCode, // Fail if child is wrong condcode. 77 CheckValueType, 78 CheckComplexPat, 79 CheckAndImm, 80 CheckOrImm, 81 CheckImmAllOnesV, 82 CheckImmAllZerosV, 83 CheckFoldableChainNode, 84 85 // Node creation/emisssion. 86 EmitInteger, // Create a TargetConstant 87 EmitStringInteger, // Create a TargetConstant from a string. 88 EmitRegister, // Create a register. 89 EmitConvertToTarget, // Convert a imm/fpimm to target imm/fpimm 90 EmitMergeInputChains, // Merge together a chains for an input. 91 EmitCopyToReg, // Emit a copytoreg into a physreg. 92 EmitNode, // Create a DAG node 93 EmitNodeXForm, // Run a SDNodeXForm 94 CompleteMatch, // Finish a match and update the results. 95 MorphNodeTo, // Build a node, finish a match and update results. 96 97 // Highest enum value; watch out when adding more. 98 HighestKind = MorphNodeTo 99 }; 100 const KindTy Kind; 101 102 protected: 103 Matcher(KindTy K) : Kind(K) {} 104 public: 105 virtual ~Matcher() {} 106 107 unsigned getSize() const { return Size; } 108 void setSize(unsigned sz) { Size = sz; } 109 KindTy getKind() const { return Kind; } 110 111 Matcher *getNext() { return Next.get(); } 112 const Matcher *getNext() const { return Next.get(); } 113 void setNext(Matcher *C) { Next.reset(C); } 114 Matcher *takeNext() { return Next.release(); } 115 116 std::unique_ptr<Matcher> &getNextPtr() { return Next; } 117 118 bool isEqual(const Matcher *M) const { 119 if (getKind() != M->getKind()) return false; 120 return isEqualImpl(M); 121 } 122 123 /// isSimplePredicateNode - Return true if this is a simple predicate that 124 /// operates on the node or its children without potential side effects or a 125 /// change of the current node. 126 bool isSimplePredicateNode() const { 127 switch (getKind()) { 128 default: return false; 129 case CheckSame: 130 case CheckChildSame: 131 case CheckPatternPredicate: 132 case CheckPredicate: 133 case CheckOpcode: 134 case CheckType: 135 case CheckChildType: 136 case CheckInteger: 137 case CheckChildInteger: 138 case CheckCondCode: 139 case CheckChild2CondCode: 140 case CheckValueType: 141 case CheckAndImm: 142 case CheckOrImm: 143 case CheckImmAllOnesV: 144 case CheckImmAllZerosV: 145 case CheckFoldableChainNode: 146 return true; 147 } 148 } 149 150 /// isSimplePredicateOrRecordNode - Return true if this is a record node or 151 /// a simple predicate. 152 bool isSimplePredicateOrRecordNode() const { 153 return isSimplePredicateNode() || 154 getKind() == RecordNode || getKind() == RecordChild; 155 } 156 157 /// unlinkNode - Unlink the specified node from this chain. If Other == this, 158 /// we unlink the next pointer and return it. Otherwise we unlink Other from 159 /// the list and return this. 160 Matcher *unlinkNode(Matcher *Other); 161 162 /// canMoveBefore - Return true if this matcher is the same as Other, or if 163 /// we can move this matcher past all of the nodes in-between Other and this 164 /// node. Other must be equal to or before this. 165 bool canMoveBefore(const Matcher *Other) const; 166 167 /// canMoveBeforeNode - Return true if it is safe to move the current matcher 168 /// across the specified one. 169 bool canMoveBeforeNode(const Matcher *Other) const; 170 171 /// isContradictory - Return true of these two matchers could never match on 172 /// the same node. 173 bool isContradictory(const Matcher *Other) const { 174 // Since this predicate is reflexive, we canonicalize the ordering so that 175 // we always match a node against nodes with kinds that are greater or equal 176 // to them. For example, we'll pass in a CheckType node as an argument to 177 // the CheckOpcode method, not the other way around. 178 if (getKind() < Other->getKind()) 179 return isContradictoryImpl(Other); 180 return Other->isContradictoryImpl(this); 181 } 182 183 void print(raw_ostream &OS, unsigned indent = 0) const; 184 void printOne(raw_ostream &OS) const; 185 void dump() const; 186 protected: 187 virtual void printImpl(raw_ostream &OS, unsigned indent) const = 0; 188 virtual bool isEqualImpl(const Matcher *M) const = 0; 189 virtual bool isContradictoryImpl(const Matcher *M) const { return false; } 190 }; 191 192 /// ScopeMatcher - This attempts to match each of its children to find the first 193 /// one that successfully matches. If one child fails, it tries the next child. 194 /// If none of the children match then this check fails. It never has a 'next'. 195 class ScopeMatcher : public Matcher { 196 SmallVector<Matcher*, 4> Children; 197 public: 198 ScopeMatcher(SmallVectorImpl<Matcher *> &&children) 199 : Matcher(Scope), Children(std::move(children)) {} 200 ~ScopeMatcher() override; 201 202 unsigned getNumChildren() const { return Children.size(); } 203 204 Matcher *getChild(unsigned i) { return Children[i]; } 205 const Matcher *getChild(unsigned i) const { return Children[i]; } 206 207 void resetChild(unsigned i, Matcher *N) { 208 delete Children[i]; 209 Children[i] = N; 210 } 211 212 Matcher *takeChild(unsigned i) { 213 Matcher *Res = Children[i]; 214 Children[i] = nullptr; 215 return Res; 216 } 217 218 void setNumChildren(unsigned NC) { 219 if (NC < Children.size()) { 220 // delete any children we're about to lose pointers to. 221 for (unsigned i = NC, e = Children.size(); i != e; ++i) 222 delete Children[i]; 223 } 224 Children.resize(NC); 225 } 226 227 static bool classof(const Matcher *N) { 228 return N->getKind() == Scope; 229 } 230 231 private: 232 void printImpl(raw_ostream &OS, unsigned indent) const override; 233 bool isEqualImpl(const Matcher *M) const override { return false; } 234 }; 235 236 /// RecordMatcher - Save the current node in the operand list. 237 class RecordMatcher : public Matcher { 238 /// WhatFor - This is a string indicating why we're recording this. This 239 /// should only be used for comment generation not anything semantic. 240 std::string WhatFor; 241 242 /// ResultNo - The slot number in the RecordedNodes vector that this will be, 243 /// just printed as a comment. 244 unsigned ResultNo; 245 public: 246 RecordMatcher(const std::string &whatfor, unsigned resultNo) 247 : Matcher(RecordNode), WhatFor(whatfor), ResultNo(resultNo) {} 248 249 const std::string &getWhatFor() const { return WhatFor; } 250 unsigned getResultNo() const { return ResultNo; } 251 252 static bool classof(const Matcher *N) { 253 return N->getKind() == RecordNode; 254 } 255 256 private: 257 void printImpl(raw_ostream &OS, unsigned indent) const override; 258 bool isEqualImpl(const Matcher *M) const override { return true; } 259 }; 260 261 /// RecordChildMatcher - Save a numbered child of the current node, or fail 262 /// the match if it doesn't exist. This is logically equivalent to: 263 /// MoveChild N + RecordNode + MoveParent. 264 class RecordChildMatcher : public Matcher { 265 unsigned ChildNo; 266 267 /// WhatFor - This is a string indicating why we're recording this. This 268 /// should only be used for comment generation not anything semantic. 269 std::string WhatFor; 270 271 /// ResultNo - The slot number in the RecordedNodes vector that this will be, 272 /// just printed as a comment. 273 unsigned ResultNo; 274 public: 275 RecordChildMatcher(unsigned childno, const std::string &whatfor, 276 unsigned resultNo) 277 : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor), 278 ResultNo(resultNo) {} 279 280 unsigned getChildNo() const { return ChildNo; } 281 const std::string &getWhatFor() const { return WhatFor; } 282 unsigned getResultNo() const { return ResultNo; } 283 284 static bool classof(const Matcher *N) { 285 return N->getKind() == RecordChild; 286 } 287 288 private: 289 void printImpl(raw_ostream &OS, unsigned indent) const override; 290 bool isEqualImpl(const Matcher *M) const override { 291 return cast<RecordChildMatcher>(M)->getChildNo() == getChildNo(); 292 } 293 }; 294 295 /// RecordMemRefMatcher - Save the current node's memref. 296 class RecordMemRefMatcher : public Matcher { 297 public: 298 RecordMemRefMatcher() : Matcher(RecordMemRef) {} 299 300 static bool classof(const Matcher *N) { 301 return N->getKind() == RecordMemRef; 302 } 303 304 private: 305 void printImpl(raw_ostream &OS, unsigned indent) const override; 306 bool isEqualImpl(const Matcher *M) const override { return true; } 307 }; 308 309 310 /// CaptureGlueInputMatcher - If the current record has a glue input, record 311 /// it so that it is used as an input to the generated code. 312 class CaptureGlueInputMatcher : public Matcher { 313 public: 314 CaptureGlueInputMatcher() : Matcher(CaptureGlueInput) {} 315 316 static bool classof(const Matcher *N) { 317 return N->getKind() == CaptureGlueInput; 318 } 319 320 private: 321 void printImpl(raw_ostream &OS, unsigned indent) const override; 322 bool isEqualImpl(const Matcher *M) const override { return true; } 323 }; 324 325 /// MoveChildMatcher - This tells the interpreter to move into the 326 /// specified child node. 327 class MoveChildMatcher : public Matcher { 328 unsigned ChildNo; 329 public: 330 MoveChildMatcher(unsigned childNo) : Matcher(MoveChild), ChildNo(childNo) {} 331 332 unsigned getChildNo() const { return ChildNo; } 333 334 static bool classof(const Matcher *N) { 335 return N->getKind() == MoveChild; 336 } 337 338 private: 339 void printImpl(raw_ostream &OS, unsigned indent) const override; 340 bool isEqualImpl(const Matcher *M) const override { 341 return cast<MoveChildMatcher>(M)->getChildNo() == getChildNo(); 342 } 343 }; 344 345 /// MoveParentMatcher - This tells the interpreter to move to the parent 346 /// of the current node. 347 class MoveParentMatcher : public Matcher { 348 public: 349 MoveParentMatcher() : Matcher(MoveParent) {} 350 351 static bool classof(const Matcher *N) { 352 return N->getKind() == MoveParent; 353 } 354 355 private: 356 void printImpl(raw_ostream &OS, unsigned indent) const override; 357 bool isEqualImpl(const Matcher *M) const override { return true; } 358 }; 359 360 /// CheckSameMatcher - This checks to see if this node is exactly the same 361 /// node as the specified match that was recorded with 'Record'. This is used 362 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'. 363 class CheckSameMatcher : public Matcher { 364 unsigned MatchNumber; 365 public: 366 CheckSameMatcher(unsigned matchnumber) 367 : Matcher(CheckSame), MatchNumber(matchnumber) {} 368 369 unsigned getMatchNumber() const { return MatchNumber; } 370 371 static bool classof(const Matcher *N) { 372 return N->getKind() == CheckSame; 373 } 374 375 private: 376 void printImpl(raw_ostream &OS, unsigned indent) const override; 377 bool isEqualImpl(const Matcher *M) const override { 378 return cast<CheckSameMatcher>(M)->getMatchNumber() == getMatchNumber(); 379 } 380 }; 381 382 /// CheckChildSameMatcher - This checks to see if child node is exactly the same 383 /// node as the specified match that was recorded with 'Record'. This is used 384 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'. 385 class CheckChildSameMatcher : public Matcher { 386 unsigned ChildNo; 387 unsigned MatchNumber; 388 public: 389 CheckChildSameMatcher(unsigned childno, unsigned matchnumber) 390 : Matcher(CheckChildSame), ChildNo(childno), MatchNumber(matchnumber) {} 391 392 unsigned getChildNo() const { return ChildNo; } 393 unsigned getMatchNumber() const { return MatchNumber; } 394 395 static bool classof(const Matcher *N) { 396 return N->getKind() == CheckChildSame; 397 } 398 399 private: 400 void printImpl(raw_ostream &OS, unsigned indent) const override; 401 bool isEqualImpl(const Matcher *M) const override { 402 return cast<CheckChildSameMatcher>(M)->ChildNo == ChildNo && 403 cast<CheckChildSameMatcher>(M)->MatchNumber == MatchNumber; 404 } 405 }; 406 407 /// CheckPatternPredicateMatcher - This checks the target-specific predicate 408 /// to see if the entire pattern is capable of matching. This predicate does 409 /// not take a node as input. This is used for subtarget feature checks etc. 410 class CheckPatternPredicateMatcher : public Matcher { 411 std::string Predicate; 412 public: 413 CheckPatternPredicateMatcher(StringRef predicate) 414 : Matcher(CheckPatternPredicate), Predicate(predicate) {} 415 416 StringRef getPredicate() const { return Predicate; } 417 418 static bool classof(const Matcher *N) { 419 return N->getKind() == CheckPatternPredicate; 420 } 421 422 private: 423 void printImpl(raw_ostream &OS, unsigned indent) const override; 424 bool isEqualImpl(const Matcher *M) const override { 425 return cast<CheckPatternPredicateMatcher>(M)->getPredicate() == Predicate; 426 } 427 }; 428 429 /// CheckPredicateMatcher - This checks the target-specific predicate to 430 /// see if the node is acceptable. 431 class CheckPredicateMatcher : public Matcher { 432 TreePattern *Pred; 433 const SmallVector<unsigned, 4> Operands; 434 public: 435 CheckPredicateMatcher(const TreePredicateFn &pred, 436 const SmallVectorImpl<unsigned> &Operands); 437 438 TreePredicateFn getPredicate() const; 439 unsigned getNumOperands() const; 440 unsigned getOperandNo(unsigned i) const; 441 442 static bool classof(const Matcher *N) { 443 return N->getKind() == CheckPredicate; 444 } 445 446 private: 447 void printImpl(raw_ostream &OS, unsigned indent) const override; 448 bool isEqualImpl(const Matcher *M) const override { 449 return cast<CheckPredicateMatcher>(M)->Pred == Pred; 450 } 451 }; 452 453 454 /// CheckOpcodeMatcher - This checks to see if the current node has the 455 /// specified opcode, if not it fails to match. 456 class CheckOpcodeMatcher : public Matcher { 457 const SDNodeInfo &Opcode; 458 public: 459 CheckOpcodeMatcher(const SDNodeInfo &opcode) 460 : Matcher(CheckOpcode), Opcode(opcode) {} 461 462 const SDNodeInfo &getOpcode() const { return Opcode; } 463 464 static bool classof(const Matcher *N) { 465 return N->getKind() == CheckOpcode; 466 } 467 468 private: 469 void printImpl(raw_ostream &OS, unsigned indent) const override; 470 bool isEqualImpl(const Matcher *M) const override; 471 bool isContradictoryImpl(const Matcher *M) const override; 472 }; 473 474 /// SwitchOpcodeMatcher - Switch based on the current node's opcode, dispatching 475 /// to one matcher per opcode. If the opcode doesn't match any of the cases, 476 /// then the match fails. This is semantically equivalent to a Scope node where 477 /// every child does a CheckOpcode, but is much faster. 478 class SwitchOpcodeMatcher : public Matcher { 479 SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; 480 public: 481 SwitchOpcodeMatcher( 482 SmallVectorImpl<std::pair<const SDNodeInfo *, Matcher *>> &&cases) 483 : Matcher(SwitchOpcode), Cases(std::move(cases)) {} 484 ~SwitchOpcodeMatcher() override; 485 486 static bool classof(const Matcher *N) { 487 return N->getKind() == SwitchOpcode; 488 } 489 490 unsigned getNumCases() const { return Cases.size(); } 491 492 const SDNodeInfo &getCaseOpcode(unsigned i) const { return *Cases[i].first; } 493 Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; } 494 const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; } 495 496 private: 497 void printImpl(raw_ostream &OS, unsigned indent) const override; 498 bool isEqualImpl(const Matcher *M) const override { return false; } 499 }; 500 501 /// CheckTypeMatcher - This checks to see if the current node has the 502 /// specified type at the specified result, if not it fails to match. 503 class CheckTypeMatcher : public Matcher { 504 MVT::SimpleValueType Type; 505 unsigned ResNo; 506 public: 507 CheckTypeMatcher(MVT::SimpleValueType type, unsigned resno) 508 : Matcher(CheckType), Type(type), ResNo(resno) {} 509 510 MVT::SimpleValueType getType() const { return Type; } 511 unsigned getResNo() const { return ResNo; } 512 513 static bool classof(const Matcher *N) { 514 return N->getKind() == CheckType; 515 } 516 517 private: 518 void printImpl(raw_ostream &OS, unsigned indent) const override; 519 bool isEqualImpl(const Matcher *M) const override { 520 return cast<CheckTypeMatcher>(M)->Type == Type; 521 } 522 bool isContradictoryImpl(const Matcher *M) const override; 523 }; 524 525 /// SwitchTypeMatcher - Switch based on the current node's type, dispatching 526 /// to one matcher per case. If the type doesn't match any of the cases, 527 /// then the match fails. This is semantically equivalent to a Scope node where 528 /// every child does a CheckType, but is much faster. 529 class SwitchTypeMatcher : public Matcher { 530 SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; 531 public: 532 SwitchTypeMatcher( 533 SmallVectorImpl<std::pair<MVT::SimpleValueType, Matcher *>> &&cases) 534 : Matcher(SwitchType), Cases(std::move(cases)) {} 535 ~SwitchTypeMatcher() override; 536 537 static bool classof(const Matcher *N) { 538 return N->getKind() == SwitchType; 539 } 540 541 unsigned getNumCases() const { return Cases.size(); } 542 543 MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; } 544 Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; } 545 const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; } 546 547 private: 548 void printImpl(raw_ostream &OS, unsigned indent) const override; 549 bool isEqualImpl(const Matcher *M) const override { return false; } 550 }; 551 552 553 /// CheckChildTypeMatcher - This checks to see if a child node has the 554 /// specified type, if not it fails to match. 555 class CheckChildTypeMatcher : public Matcher { 556 unsigned ChildNo; 557 MVT::SimpleValueType Type; 558 public: 559 CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type) 560 : Matcher(CheckChildType), ChildNo(childno), Type(type) {} 561 562 unsigned getChildNo() const { return ChildNo; } 563 MVT::SimpleValueType getType() const { return Type; } 564 565 static bool classof(const Matcher *N) { 566 return N->getKind() == CheckChildType; 567 } 568 569 private: 570 void printImpl(raw_ostream &OS, unsigned indent) const override; 571 bool isEqualImpl(const Matcher *M) const override { 572 return cast<CheckChildTypeMatcher>(M)->ChildNo == ChildNo && 573 cast<CheckChildTypeMatcher>(M)->Type == Type; 574 } 575 bool isContradictoryImpl(const Matcher *M) const override; 576 }; 577 578 579 /// CheckIntegerMatcher - This checks to see if the current node is a 580 /// ConstantSDNode with the specified integer value, if not it fails to match. 581 class CheckIntegerMatcher : public Matcher { 582 int64_t Value; 583 public: 584 CheckIntegerMatcher(int64_t value) 585 : Matcher(CheckInteger), Value(value) {} 586 587 int64_t getValue() const { return Value; } 588 589 static bool classof(const Matcher *N) { 590 return N->getKind() == CheckInteger; 591 } 592 593 private: 594 void printImpl(raw_ostream &OS, unsigned indent) const override; 595 bool isEqualImpl(const Matcher *M) const override { 596 return cast<CheckIntegerMatcher>(M)->Value == Value; 597 } 598 bool isContradictoryImpl(const Matcher *M) const override; 599 }; 600 601 /// CheckChildIntegerMatcher - This checks to see if the child node is a 602 /// ConstantSDNode with a specified integer value, if not it fails to match. 603 class CheckChildIntegerMatcher : public Matcher { 604 unsigned ChildNo; 605 int64_t Value; 606 public: 607 CheckChildIntegerMatcher(unsigned childno, int64_t value) 608 : Matcher(CheckChildInteger), ChildNo(childno), Value(value) {} 609 610 unsigned getChildNo() const { return ChildNo; } 611 int64_t getValue() const { return Value; } 612 613 static bool classof(const Matcher *N) { 614 return N->getKind() == CheckChildInteger; 615 } 616 617 private: 618 void printImpl(raw_ostream &OS, unsigned indent) const override; 619 bool isEqualImpl(const Matcher *M) const override { 620 return cast<CheckChildIntegerMatcher>(M)->ChildNo == ChildNo && 621 cast<CheckChildIntegerMatcher>(M)->Value == Value; 622 } 623 bool isContradictoryImpl(const Matcher *M) const override; 624 }; 625 626 /// CheckCondCodeMatcher - This checks to see if the current node is a 627 /// CondCodeSDNode with the specified condition, if not it fails to match. 628 class CheckCondCodeMatcher : public Matcher { 629 StringRef CondCodeName; 630 public: 631 CheckCondCodeMatcher(StringRef condcodename) 632 : Matcher(CheckCondCode), CondCodeName(condcodename) {} 633 634 StringRef getCondCodeName() const { return CondCodeName; } 635 636 static bool classof(const Matcher *N) { 637 return N->getKind() == CheckCondCode; 638 } 639 640 private: 641 void printImpl(raw_ostream &OS, unsigned indent) const override; 642 bool isEqualImpl(const Matcher *M) const override { 643 return cast<CheckCondCodeMatcher>(M)->CondCodeName == CondCodeName; 644 } 645 bool isContradictoryImpl(const Matcher *M) const override; 646 }; 647 648 /// CheckChild2CondCodeMatcher - This checks to see if child 2 node is a 649 /// CondCodeSDNode with the specified condition, if not it fails to match. 650 class CheckChild2CondCodeMatcher : public Matcher { 651 StringRef CondCodeName; 652 public: 653 CheckChild2CondCodeMatcher(StringRef condcodename) 654 : Matcher(CheckChild2CondCode), CondCodeName(condcodename) {} 655 656 StringRef getCondCodeName() const { return CondCodeName; } 657 658 static bool classof(const Matcher *N) { 659 return N->getKind() == CheckChild2CondCode; 660 } 661 662 private: 663 void printImpl(raw_ostream &OS, unsigned indent) const override; 664 bool isEqualImpl(const Matcher *M) const override { 665 return cast<CheckChild2CondCodeMatcher>(M)->CondCodeName == CondCodeName; 666 } 667 bool isContradictoryImpl(const Matcher *M) const override; 668 }; 669 670 /// CheckValueTypeMatcher - This checks to see if the current node is a 671 /// VTSDNode with the specified type, if not it fails to match. 672 class CheckValueTypeMatcher : public Matcher { 673 StringRef TypeName; 674 public: 675 CheckValueTypeMatcher(StringRef type_name) 676 : Matcher(CheckValueType), TypeName(type_name) {} 677 678 StringRef getTypeName() const { return TypeName; } 679 680 static bool classof(const Matcher *N) { 681 return N->getKind() == CheckValueType; 682 } 683 684 private: 685 void printImpl(raw_ostream &OS, unsigned indent) const override; 686 bool isEqualImpl(const Matcher *M) const override { 687 return cast<CheckValueTypeMatcher>(M)->TypeName == TypeName; 688 } 689 bool isContradictoryImpl(const Matcher *M) const override; 690 }; 691 692 693 694 /// CheckComplexPatMatcher - This node runs the specified ComplexPattern on 695 /// the current node. 696 class CheckComplexPatMatcher : public Matcher { 697 const ComplexPattern &Pattern; 698 699 /// MatchNumber - This is the recorded nodes slot that contains the node we 700 /// want to match against. 701 unsigned MatchNumber; 702 703 /// Name - The name of the node we're matching, for comment emission. 704 std::string Name; 705 706 /// FirstResult - This is the first slot in the RecordedNodes list that the 707 /// result of the match populates. 708 unsigned FirstResult; 709 public: 710 CheckComplexPatMatcher(const ComplexPattern &pattern, unsigned matchnumber, 711 const std::string &name, unsigned firstresult) 712 : Matcher(CheckComplexPat), Pattern(pattern), MatchNumber(matchnumber), 713 Name(name), FirstResult(firstresult) {} 714 715 const ComplexPattern &getPattern() const { return Pattern; } 716 unsigned getMatchNumber() const { return MatchNumber; } 717 718 std::string getName() const { return Name; } 719 unsigned getFirstResult() const { return FirstResult; } 720 721 static bool classof(const Matcher *N) { 722 return N->getKind() == CheckComplexPat; 723 } 724 725 private: 726 void printImpl(raw_ostream &OS, unsigned indent) const override; 727 bool isEqualImpl(const Matcher *M) const override { 728 return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern && 729 cast<CheckComplexPatMatcher>(M)->MatchNumber == MatchNumber; 730 } 731 }; 732 733 /// CheckAndImmMatcher - This checks to see if the current node is an 'and' 734 /// with something equivalent to the specified immediate. 735 class CheckAndImmMatcher : public Matcher { 736 int64_t Value; 737 public: 738 CheckAndImmMatcher(int64_t value) 739 : Matcher(CheckAndImm), Value(value) {} 740 741 int64_t getValue() const { return Value; } 742 743 static bool classof(const Matcher *N) { 744 return N->getKind() == CheckAndImm; 745 } 746 747 private: 748 void printImpl(raw_ostream &OS, unsigned indent) const override; 749 bool isEqualImpl(const Matcher *M) const override { 750 return cast<CheckAndImmMatcher>(M)->Value == Value; 751 } 752 }; 753 754 /// CheckOrImmMatcher - This checks to see if the current node is an 'and' 755 /// with something equivalent to the specified immediate. 756 class CheckOrImmMatcher : public Matcher { 757 int64_t Value; 758 public: 759 CheckOrImmMatcher(int64_t value) 760 : Matcher(CheckOrImm), Value(value) {} 761 762 int64_t getValue() const { return Value; } 763 764 static bool classof(const Matcher *N) { 765 return N->getKind() == CheckOrImm; 766 } 767 768 private: 769 void printImpl(raw_ostream &OS, unsigned indent) const override; 770 bool isEqualImpl(const Matcher *M) const override { 771 return cast<CheckOrImmMatcher>(M)->Value == Value; 772 } 773 }; 774 775 /// CheckImmAllOnesVMatcher - This checks if the current node is a build_vector 776 /// or splat_vector of all ones. 777 class CheckImmAllOnesVMatcher : public Matcher { 778 public: 779 CheckImmAllOnesVMatcher() : Matcher(CheckImmAllOnesV) {} 780 781 static bool classof(const Matcher *N) { 782 return N->getKind() == CheckImmAllOnesV; 783 } 784 785 private: 786 void printImpl(raw_ostream &OS, unsigned indent) const override; 787 bool isEqualImpl(const Matcher *M) const override { return true; } 788 bool isContradictoryImpl(const Matcher *M) const override; 789 }; 790 791 /// CheckImmAllZerosVMatcher - This checks if the current node is a 792 /// build_vector or splat_vector of all zeros. 793 class CheckImmAllZerosVMatcher : public Matcher { 794 public: 795 CheckImmAllZerosVMatcher() : Matcher(CheckImmAllZerosV) {} 796 797 static bool classof(const Matcher *N) { 798 return N->getKind() == CheckImmAllZerosV; 799 } 800 801 private: 802 void printImpl(raw_ostream &OS, unsigned indent) const override; 803 bool isEqualImpl(const Matcher *M) const override { return true; } 804 bool isContradictoryImpl(const Matcher *M) const override; 805 }; 806 807 /// CheckFoldableChainNodeMatcher - This checks to see if the current node 808 /// (which defines a chain operand) is safe to fold into a larger pattern. 809 class CheckFoldableChainNodeMatcher : public Matcher { 810 public: 811 CheckFoldableChainNodeMatcher() 812 : Matcher(CheckFoldableChainNode) {} 813 814 static bool classof(const Matcher *N) { 815 return N->getKind() == CheckFoldableChainNode; 816 } 817 818 private: 819 void printImpl(raw_ostream &OS, unsigned indent) const override; 820 bool isEqualImpl(const Matcher *M) const override { return true; } 821 }; 822 823 /// EmitIntegerMatcher - This creates a new TargetConstant. 824 class EmitIntegerMatcher : public Matcher { 825 int64_t Val; 826 MVT::SimpleValueType VT; 827 public: 828 EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt) 829 : Matcher(EmitInteger), Val(val), VT(vt) {} 830 831 int64_t getValue() const { return Val; } 832 MVT::SimpleValueType getVT() const { return VT; } 833 834 static bool classof(const Matcher *N) { 835 return N->getKind() == EmitInteger; 836 } 837 838 private: 839 void printImpl(raw_ostream &OS, unsigned indent) const override; 840 bool isEqualImpl(const Matcher *M) const override { 841 return cast<EmitIntegerMatcher>(M)->Val == Val && 842 cast<EmitIntegerMatcher>(M)->VT == VT; 843 } 844 }; 845 846 /// EmitStringIntegerMatcher - A target constant whose value is represented 847 /// by a string. 848 class EmitStringIntegerMatcher : public Matcher { 849 std::string Val; 850 MVT::SimpleValueType VT; 851 public: 852 EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt) 853 : Matcher(EmitStringInteger), Val(val), VT(vt) {} 854 855 const std::string &getValue() const { return Val; } 856 MVT::SimpleValueType getVT() const { return VT; } 857 858 static bool classof(const Matcher *N) { 859 return N->getKind() == EmitStringInteger; 860 } 861 862 private: 863 void printImpl(raw_ostream &OS, unsigned indent) const override; 864 bool isEqualImpl(const Matcher *M) const override { 865 return cast<EmitStringIntegerMatcher>(M)->Val == Val && 866 cast<EmitStringIntegerMatcher>(M)->VT == VT; 867 } 868 }; 869 870 /// EmitRegisterMatcher - This creates a new TargetConstant. 871 class EmitRegisterMatcher : public Matcher { 872 /// Reg - The def for the register that we're emitting. If this is null, then 873 /// this is a reference to zero_reg. 874 const CodeGenRegister *Reg; 875 MVT::SimpleValueType VT; 876 public: 877 EmitRegisterMatcher(const CodeGenRegister *reg, MVT::SimpleValueType vt) 878 : Matcher(EmitRegister), Reg(reg), VT(vt) {} 879 880 const CodeGenRegister *getReg() const { return Reg; } 881 MVT::SimpleValueType getVT() const { return VT; } 882 883 static bool classof(const Matcher *N) { 884 return N->getKind() == EmitRegister; 885 } 886 887 private: 888 void printImpl(raw_ostream &OS, unsigned indent) const override; 889 bool isEqualImpl(const Matcher *M) const override { 890 return cast<EmitRegisterMatcher>(M)->Reg == Reg && 891 cast<EmitRegisterMatcher>(M)->VT == VT; 892 } 893 }; 894 895 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified 896 /// recorded node and converts it from being a ISD::Constant to 897 /// ISD::TargetConstant, likewise for ConstantFP. 898 class EmitConvertToTargetMatcher : public Matcher { 899 unsigned Slot; 900 public: 901 EmitConvertToTargetMatcher(unsigned slot) 902 : Matcher(EmitConvertToTarget), Slot(slot) {} 903 904 unsigned getSlot() const { return Slot; } 905 906 static bool classof(const Matcher *N) { 907 return N->getKind() == EmitConvertToTarget; 908 } 909 910 private: 911 void printImpl(raw_ostream &OS, unsigned indent) const override; 912 bool isEqualImpl(const Matcher *M) const override { 913 return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot; 914 } 915 }; 916 917 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input 918 /// chains together with a token factor. The list of nodes are the nodes in the 919 /// matched pattern that have chain input/outputs. This node adds all input 920 /// chains of these nodes if they are not themselves a node in the pattern. 921 class EmitMergeInputChainsMatcher : public Matcher { 922 SmallVector<unsigned, 3> ChainNodes; 923 public: 924 EmitMergeInputChainsMatcher(ArrayRef<unsigned> nodes) 925 : Matcher(EmitMergeInputChains), ChainNodes(nodes.begin(), nodes.end()) {} 926 927 unsigned getNumNodes() const { return ChainNodes.size(); } 928 929 unsigned getNode(unsigned i) const { 930 assert(i < ChainNodes.size()); 931 return ChainNodes[i]; 932 } 933 934 static bool classof(const Matcher *N) { 935 return N->getKind() == EmitMergeInputChains; 936 } 937 938 private: 939 void printImpl(raw_ostream &OS, unsigned indent) const override; 940 bool isEqualImpl(const Matcher *M) const override { 941 return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes; 942 } 943 }; 944 945 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg, 946 /// pushing the chain and glue results. 947 /// 948 class EmitCopyToRegMatcher : public Matcher { 949 unsigned SrcSlot; // Value to copy into the physreg. 950 const CodeGenRegister *DestPhysReg; 951 952 public: 953 EmitCopyToRegMatcher(unsigned srcSlot, 954 const CodeGenRegister *destPhysReg) 955 : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {} 956 957 unsigned getSrcSlot() const { return SrcSlot; } 958 const CodeGenRegister *getDestPhysReg() const { return DestPhysReg; } 959 960 static bool classof(const Matcher *N) { 961 return N->getKind() == EmitCopyToReg; 962 } 963 964 private: 965 void printImpl(raw_ostream &OS, unsigned indent) const override; 966 bool isEqualImpl(const Matcher *M) const override { 967 return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot && 968 cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg; 969 } 970 }; 971 972 973 974 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a 975 /// recorded node and records the result. 976 class EmitNodeXFormMatcher : public Matcher { 977 unsigned Slot; 978 Record *NodeXForm; 979 public: 980 EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm) 981 : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {} 982 983 unsigned getSlot() const { return Slot; } 984 Record *getNodeXForm() const { return NodeXForm; } 985 986 static bool classof(const Matcher *N) { 987 return N->getKind() == EmitNodeXForm; 988 } 989 990 private: 991 void printImpl(raw_ostream &OS, unsigned indent) const override; 992 bool isEqualImpl(const Matcher *M) const override { 993 return cast<EmitNodeXFormMatcher>(M)->Slot == Slot && 994 cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm; 995 } 996 }; 997 998 /// EmitNodeMatcherCommon - Common class shared between EmitNode and 999 /// MorphNodeTo. 1000 class EmitNodeMatcherCommon : public Matcher { 1001 const CodeGenInstruction &CGI; 1002 const SmallVector<MVT::SimpleValueType, 3> VTs; 1003 const SmallVector<unsigned, 6> Operands; 1004 bool HasChain, HasInGlue, HasOutGlue, HasMemRefs; 1005 1006 /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1. 1007 /// If this is a varidic node, this is set to the number of fixed arity 1008 /// operands in the root of the pattern. The rest are appended to this node. 1009 int NumFixedArityOperands; 1010 public: 1011 EmitNodeMatcherCommon(const CodeGenInstruction &cgi, 1012 ArrayRef<MVT::SimpleValueType> vts, 1013 ArrayRef<unsigned> operands, bool hasChain, 1014 bool hasInGlue, bool hasOutGlue, bool hasmemrefs, 1015 int numfixedarityoperands, bool isMorphNodeTo) 1016 : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), CGI(cgi), 1017 VTs(vts.begin(), vts.end()), Operands(operands.begin(), operands.end()), 1018 HasChain(hasChain), HasInGlue(hasInGlue), HasOutGlue(hasOutGlue), 1019 HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {} 1020 1021 const CodeGenInstruction &getInstruction() const { return CGI; } 1022 1023 unsigned getNumVTs() const { return VTs.size(); } 1024 MVT::SimpleValueType getVT(unsigned i) const { 1025 assert(i < VTs.size()); 1026 return VTs[i]; 1027 } 1028 1029 unsigned getNumOperands() const { return Operands.size(); } 1030 unsigned getOperand(unsigned i) const { 1031 assert(i < Operands.size()); 1032 return Operands[i]; 1033 } 1034 1035 const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; } 1036 const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; } 1037 1038 1039 bool hasChain() const { return HasChain; } 1040 bool hasInGlue() const { return HasInGlue; } 1041 bool hasOutGlue() const { return HasOutGlue; } 1042 bool hasMemRefs() const { return HasMemRefs; } 1043 int getNumFixedArityOperands() const { return NumFixedArityOperands; } 1044 1045 static bool classof(const Matcher *N) { 1046 return N->getKind() == EmitNode || N->getKind() == MorphNodeTo; 1047 } 1048 1049 private: 1050 void printImpl(raw_ostream &OS, unsigned indent) const override; 1051 bool isEqualImpl(const Matcher *M) const override; 1052 }; 1053 1054 /// EmitNodeMatcher - This signals a successful match and generates a node. 1055 class EmitNodeMatcher : public EmitNodeMatcherCommon { 1056 void anchor() override; 1057 unsigned FirstResultSlot; 1058 public: 1059 EmitNodeMatcher(const CodeGenInstruction &cgi, 1060 ArrayRef<MVT::SimpleValueType> vts, 1061 ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue, 1062 bool hasOutGlue, bool hasmemrefs, int numfixedarityoperands, 1063 unsigned firstresultslot) 1064 : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue, 1065 hasOutGlue, hasmemrefs, numfixedarityoperands, 1066 false), 1067 FirstResultSlot(firstresultslot) {} 1068 1069 unsigned getFirstResultSlot() const { return FirstResultSlot; } 1070 1071 static bool classof(const Matcher *N) { 1072 return N->getKind() == EmitNode; 1073 } 1074 1075 }; 1076 1077 class MorphNodeToMatcher : public EmitNodeMatcherCommon { 1078 void anchor() override; 1079 const PatternToMatch &Pattern; 1080 public: 1081 MorphNodeToMatcher(const CodeGenInstruction &cgi, 1082 ArrayRef<MVT::SimpleValueType> vts, 1083 ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue, 1084 bool hasOutGlue, bool hasmemrefs, 1085 int numfixedarityoperands, const PatternToMatch &pattern) 1086 : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue, 1087 hasOutGlue, hasmemrefs, numfixedarityoperands, 1088 true), 1089 Pattern(pattern) {} 1090 1091 const PatternToMatch &getPattern() const { return Pattern; } 1092 1093 static bool classof(const Matcher *N) { 1094 return N->getKind() == MorphNodeTo; 1095 } 1096 }; 1097 1098 /// CompleteMatchMatcher - Complete a match by replacing the results of the 1099 /// pattern with the newly generated nodes. This also prints a comment 1100 /// indicating the source and dest patterns. 1101 class CompleteMatchMatcher : public Matcher { 1102 SmallVector<unsigned, 2> Results; 1103 const PatternToMatch &Pattern; 1104 public: 1105 CompleteMatchMatcher(ArrayRef<unsigned> results, 1106 const PatternToMatch &pattern) 1107 : Matcher(CompleteMatch), Results(results.begin(), results.end()), 1108 Pattern(pattern) {} 1109 1110 unsigned getNumResults() const { return Results.size(); } 1111 unsigned getResult(unsigned R) const { return Results[R]; } 1112 const PatternToMatch &getPattern() const { return Pattern; } 1113 1114 static bool classof(const Matcher *N) { 1115 return N->getKind() == CompleteMatch; 1116 } 1117 1118 private: 1119 void printImpl(raw_ostream &OS, unsigned indent) const override; 1120 bool isEqualImpl(const Matcher *M) const override { 1121 return cast<CompleteMatchMatcher>(M)->Results == Results && 1122 &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern; 1123 } 1124 }; 1125 1126 } // end namespace llvm 1127 1128 #endif 1129