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