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