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