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