1//===- DAGISelMatcher.h - Representation of DAG pattern matcher -*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_UTILS_TABLEGEN_COMMON_DAGISELMATCHER_H
10#define LLVM_UTILS_TABLEGEN_COMMON_DAGISELMATCHER_H
11
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 representation
45/// nodes.
46class Matcher {
47 // The next matcher node that is executed after this one. Null if this is
48 // 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 TargetConstant
89 EmitStringInteger, // Create a TargetConstant from a string.
90 EmitRegister, // Create a register.
91 EmitConvertToTarget, // Convert a imm/fpimm to target imm/fpimm
92 EmitMergeInputChains, // Merge together a chains for an input.
93 EmitCopyToReg, // Emit a copytoreg into a physreg.
94 EmitNode, // Create a DAG node
95 EmitNodeXForm, // Run a SDNodeXForm
96 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 = MorphNodeTo
101 };
102 const KindTy Kind;
103
104protected:
105 Matcher(KindTy K) : Kind(K) {}
106
107public:
108 virtual ~Matcher() {}
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(p: 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 that
128 /// operates on the node or its children without potential side effects or a
129 /// 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 or
156 /// 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 unlink
164 /// 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 if
168 /// we can move this matcher past all of the nodes in-between Other and this
169 /// 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 current
173 /// matcher across the specified one.
174 bool canMoveBeforeNode(const Matcher *Other) const;
175
176 /// isContradictory - Return true of these two matchers could never match on
177 /// the same node.
178 bool isContradictory(const Matcher *Other) const {
179 // Since this predicate is reflexive, we canonicalize the ordering so that
180 // we always match a node against nodes with kinds that are greater or
181 // equal to them. For example, we'll pass in a CheckType node as an
182 // argument to the CheckOpcode method, not the other way around.
183 if (getKind() < Other->getKind())
184 return isContradictoryImpl(M: Other);
185 return Other->isContradictoryImpl(M: 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 first
199/// 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(N: 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. This
244 /// 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 fail
266/// 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. This
272 /// 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>(Val: 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, record
311/// 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 the
326/// 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>(Val: M)->getChildNo() == getChildNo();
341 }
342};
343
344/// MoveSiblingMatcher - This tells the interpreter to move into the
345/// 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>(Val: M)->getSiblingNo() == getSiblingNo();
361 }
362};
363
364/// MoveParentMatcher - This tells the interpreter to move to the parent
365/// 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 same
378/// node as the specified match that was recorded with 'Record'. This is used
379/// 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>(Val: M)->getMatchNumber() == getMatchNumber();
395 }
396};
397
398/// CheckChildSameMatcher - This checks to see if child node is exactly the same
399/// node as the specified match that was recorded with 'Record'. This is used
400/// 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>(Val: M)->ChildNo == ChildNo &&
420 cast<CheckChildSameMatcher>(Val: M)->MatchNumber == MatchNumber;
421 }
422};
423
424/// CheckPatternPredicateMatcher - This checks the target-specific predicate
425/// to see if the entire pattern is capable of matching. This predicate does
426/// 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>(Val: M)->getPredicate() == Predicate;
444 }
445};
446
447/// CheckPredicateMatcher - This checks the target-specific predicate to
448/// 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>(Val: M)->Pred == Pred;
469 }
470};
471
472/// CheckOpcodeMatcher - This checks to see if the current node has the
473/// 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, dispatching
492/// 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 where
494/// 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 the
518/// specified type at the specified result, if not it fails to match.
519class CheckTypeMatcher : public Matcher {
520 MVT::SimpleValueType Type;
521 unsigned ResNo;
522
523public:
524 CheckTypeMatcher(MVT::SimpleValueType type, unsigned resno)
525 : Matcher(CheckType), Type(type), ResNo(resno) {}
526
527 MVT::SimpleValueType 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>(Val: M)->Type == Type;
536 }
537 bool isContradictoryImpl(const Matcher *M) const override;
538};
539
540/// SwitchTypeMatcher - Switch based on the current node's type, dispatching
541/// 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 where
543/// every child does a CheckType, but is much faster.
544class SwitchTypeMatcher : public Matcher {
545 SmallVector<std::pair<MVT::SimpleValueType, Matcher *>, 8> Cases;
546
547public:
548 SwitchTypeMatcher(
549 SmallVectorImpl<std::pair<MVT::SimpleValueType, Matcher *>> &&cases)
550 : Matcher(SwitchType), Cases(std::move(cases)) {}
551 ~SwitchTypeMatcher() override;
552
553 static bool classof(const Matcher *N) { return N->getKind() == SwitchType; }
554
555 unsigned getNumCases() const { return Cases.size(); }
556
557 MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; }
558 Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
559 const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
560
561private:
562 void printImpl(raw_ostream &OS, indent Indent) const override;
563 bool isEqualImpl(const Matcher *M) const override { return false; }
564};
565
566/// CheckChildTypeMatcher - This checks to see if a child node has the
567/// specified type, if not it fails to match.
568class CheckChildTypeMatcher : public Matcher {
569 unsigned ChildNo;
570 MVT::SimpleValueType Type;
571
572public:
573 CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type)
574 : Matcher(CheckChildType), ChildNo(childno), Type(type) {}
575
576 unsigned getChildNo() const { return ChildNo; }
577 MVT::SimpleValueType getType() const { return Type; }
578
579 static bool classof(const Matcher *N) {
580 return N->getKind() == CheckChildType;
581 }
582
583private:
584 void printImpl(raw_ostream &OS, indent Indent) const override;
585 bool isEqualImpl(const Matcher *M) const override {
586 return cast<CheckChildTypeMatcher>(Val: M)->ChildNo == ChildNo &&
587 cast<CheckChildTypeMatcher>(Val: M)->Type == Type;
588 }
589 bool isContradictoryImpl(const Matcher *M) const override;
590};
591
592/// CheckIntegerMatcher - This checks to see if the current node is a
593/// ConstantSDNode with the specified integer value, if not it fails to match.
594class CheckIntegerMatcher : public Matcher {
595 int64_t Value;
596
597public:
598 CheckIntegerMatcher(int64_t value) : Matcher(CheckInteger), Value(value) {}
599
600 int64_t getValue() const { return Value; }
601
602 static bool classof(const Matcher *N) { return N->getKind() == CheckInteger; }
603
604private:
605 void printImpl(raw_ostream &OS, indent Indent) const override;
606 bool isEqualImpl(const Matcher *M) const override {
607 return cast<CheckIntegerMatcher>(Val: M)->Value == Value;
608 }
609 bool isContradictoryImpl(const Matcher *M) const override;
610};
611
612/// CheckChildIntegerMatcher - This checks to see if the child node is a
613/// ConstantSDNode with a specified integer value, if not it fails to match.
614class CheckChildIntegerMatcher : public Matcher {
615 unsigned ChildNo;
616 int64_t Value;
617
618public:
619 CheckChildIntegerMatcher(unsigned childno, int64_t value)
620 : Matcher(CheckChildInteger), ChildNo(childno), Value(value) {}
621
622 unsigned getChildNo() const { return ChildNo; }
623 int64_t getValue() const { return Value; }
624
625 static bool classof(const Matcher *N) {
626 return N->getKind() == CheckChildInteger;
627 }
628
629private:
630 void printImpl(raw_ostream &OS, indent Indent) const override;
631 bool isEqualImpl(const Matcher *M) const override {
632 return cast<CheckChildIntegerMatcher>(Val: M)->ChildNo == ChildNo &&
633 cast<CheckChildIntegerMatcher>(Val: M)->Value == Value;
634 }
635 bool isContradictoryImpl(const Matcher *M) const override;
636};
637
638/// CheckCondCodeMatcher - This checks to see if the current node is a
639/// CondCodeSDNode with the specified condition, if not it fails to match.
640class CheckCondCodeMatcher : public Matcher {
641 StringRef CondCodeName;
642
643public:
644 CheckCondCodeMatcher(StringRef condcodename)
645 : Matcher(CheckCondCode), CondCodeName(condcodename) {}
646
647 StringRef getCondCodeName() const { return CondCodeName; }
648
649 static bool classof(const Matcher *N) {
650 return N->getKind() == CheckCondCode;
651 }
652
653private:
654 void printImpl(raw_ostream &OS, indent Indent) const override;
655 bool isEqualImpl(const Matcher *M) const override {
656 return cast<CheckCondCodeMatcher>(Val: M)->CondCodeName == CondCodeName;
657 }
658 bool isContradictoryImpl(const Matcher *M) const override;
659};
660
661/// CheckChild2CondCodeMatcher - This checks to see if child 2 node is a
662/// CondCodeSDNode with the specified condition, if not it fails to match.
663class CheckChild2CondCodeMatcher : public Matcher {
664 StringRef CondCodeName;
665
666public:
667 CheckChild2CondCodeMatcher(StringRef condcodename)
668 : Matcher(CheckChild2CondCode), CondCodeName(condcodename) {}
669
670 StringRef getCondCodeName() const { return CondCodeName; }
671
672 static bool classof(const Matcher *N) {
673 return N->getKind() == CheckChild2CondCode;
674 }
675
676private:
677 void printImpl(raw_ostream &OS, indent Indent) const override;
678 bool isEqualImpl(const Matcher *M) const override {
679 return cast<CheckChild2CondCodeMatcher>(Val: M)->CondCodeName == CondCodeName;
680 }
681 bool isContradictoryImpl(const Matcher *M) const override;
682};
683
684/// CheckValueTypeMatcher - This checks to see if the current node is a
685/// VTSDNode with the specified type, if not it fails to match.
686class CheckValueTypeMatcher : public Matcher {
687 MVT::SimpleValueType VT;
688
689public:
690 CheckValueTypeMatcher(MVT::SimpleValueType SimpleVT)
691 : Matcher(CheckValueType), VT(SimpleVT) {}
692
693 MVT::SimpleValueType getVT() const { return VT; }
694
695 static bool classof(const Matcher *N) {
696 return N->getKind() == CheckValueType;
697 }
698
699private:
700 void printImpl(raw_ostream &OS, indent Indent) const override;
701 bool isEqualImpl(const Matcher *M) const override {
702 return cast<CheckValueTypeMatcher>(Val: M)->VT == VT;
703 }
704 bool isContradictoryImpl(const Matcher *M) const override;
705};
706
707/// CheckComplexPatMatcher - This node runs the specified ComplexPattern on
708/// the current node.
709class CheckComplexPatMatcher : public Matcher {
710 const ComplexPattern &Pattern;
711
712 /// MatchNumber - This is the recorded nodes slot that contains the node we
713 /// want to match against.
714 unsigned MatchNumber;
715
716 /// Name - The name of the node we're matching, for comment emission.
717 StringRef Name;
718
719 /// FirstResult - This is the first slot in the RecordedNodes list that the
720 /// result of the match populates.
721 unsigned FirstResult;
722
723public:
724 CheckComplexPatMatcher(const ComplexPattern &pattern, unsigned matchnumber,
725 StringRef name, unsigned firstresult)
726 : Matcher(CheckComplexPat), Pattern(pattern), MatchNumber(matchnumber),
727 Name(name), FirstResult(firstresult) {}
728
729 const ComplexPattern &getPattern() const { return Pattern; }
730 unsigned getMatchNumber() const { return MatchNumber; }
731
732 StringRef getName() const { return Name; }
733 unsigned getFirstResult() const { return FirstResult; }
734
735 static bool classof(const Matcher *N) {
736 return N->getKind() == CheckComplexPat;
737 }
738
739private:
740 void printImpl(raw_ostream &OS, indent Indent) const override;
741 bool isEqualImpl(const Matcher *M) const override {
742 return &cast<CheckComplexPatMatcher>(Val: M)->Pattern == &Pattern &&
743 cast<CheckComplexPatMatcher>(Val: M)->MatchNumber == MatchNumber;
744 }
745};
746
747/// CheckAndImmMatcher - This checks to see if the current node is an 'and'
748/// with something equivalent to the specified immediate.
749class CheckAndImmMatcher : public Matcher {
750 int64_t Value;
751
752public:
753 CheckAndImmMatcher(int64_t value) : Matcher(CheckAndImm), Value(value) {}
754
755 int64_t getValue() const { return Value; }
756
757 static bool classof(const Matcher *N) { return N->getKind() == CheckAndImm; }
758
759private:
760 void printImpl(raw_ostream &OS, indent Indent) const override;
761 bool isEqualImpl(const Matcher *M) const override {
762 return cast<CheckAndImmMatcher>(Val: M)->Value == Value;
763 }
764};
765
766/// CheckOrImmMatcher - This checks to see if the current node is an 'and'
767/// with something equivalent to the specified immediate.
768class CheckOrImmMatcher : public Matcher {
769 int64_t Value;
770
771public:
772 CheckOrImmMatcher(int64_t value) : Matcher(CheckOrImm), Value(value) {}
773
774 int64_t getValue() const { return Value; }
775
776 static bool classof(const Matcher *N) { return N->getKind() == CheckOrImm; }
777
778private:
779 void printImpl(raw_ostream &OS, indent Indent) const override;
780 bool isEqualImpl(const Matcher *M) const override {
781 return cast<CheckOrImmMatcher>(Val: M)->Value == Value;
782 }
783};
784
785/// CheckImmAllOnesVMatcher - This checks if the current node is a build_vector
786/// or splat_vector of all ones.
787class CheckImmAllOnesVMatcher : public Matcher {
788public:
789 CheckImmAllOnesVMatcher() : Matcher(CheckImmAllOnesV) {}
790
791 static bool classof(const Matcher *N) {
792 return N->getKind() == CheckImmAllOnesV;
793 }
794
795private:
796 void printImpl(raw_ostream &OS, indent Indent) const override;
797 bool isEqualImpl(const Matcher *M) const override { return true; }
798 bool isContradictoryImpl(const Matcher *M) const override;
799};
800
801/// CheckImmAllZerosVMatcher - This checks if the current node is a
802/// build_vector or splat_vector of all zeros.
803class CheckImmAllZerosVMatcher : public Matcher {
804public:
805 CheckImmAllZerosVMatcher() : Matcher(CheckImmAllZerosV) {}
806
807 static bool classof(const Matcher *N) {
808 return N->getKind() == CheckImmAllZerosV;
809 }
810
811private:
812 void printImpl(raw_ostream &OS, indent Indent) const override;
813 bool isEqualImpl(const Matcher *M) const override { return true; }
814 bool isContradictoryImpl(const Matcher *M) const override;
815};
816
817/// CheckFoldableChainNodeMatcher - This checks to see if the current node
818/// (which defines a chain operand) is safe to fold into a larger pattern.
819class CheckFoldableChainNodeMatcher : public Matcher {
820public:
821 CheckFoldableChainNodeMatcher() : Matcher(CheckFoldableChainNode) {}
822
823 static bool classof(const Matcher *N) {
824 return N->getKind() == CheckFoldableChainNode;
825 }
826
827private:
828 void printImpl(raw_ostream &OS, indent Indent) const override;
829 bool isEqualImpl(const Matcher *M) const override { return true; }
830};
831
832/// EmitIntegerMatcher - This creates a new TargetConstant.
833class EmitIntegerMatcher : public Matcher {
834 int64_t Val;
835 MVT::SimpleValueType VT;
836
837 unsigned ResultNo;
838
839public:
840 EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt, unsigned resultNo)
841 : Matcher(EmitInteger), Val(SignExtend64(X: val, B: MVT(vt).getSizeInBits())),
842 VT(vt), ResultNo(resultNo) {}
843
844 int64_t getValue() const { return Val; }
845 MVT::SimpleValueType getVT() const { return VT; }
846 unsigned getResultNo() const { return ResultNo; }
847
848 static bool classof(const Matcher *N) { return N->getKind() == EmitInteger; }
849
850private:
851 void printImpl(raw_ostream &OS, indent Indent) const override;
852 bool isEqualImpl(const Matcher *M) const override {
853 return cast<EmitIntegerMatcher>(Val: M)->Val == Val &&
854 cast<EmitIntegerMatcher>(Val: M)->VT == VT;
855 }
856};
857
858/// EmitStringIntegerMatcher - A target constant whose value is represented
859/// by a string.
860class EmitStringIntegerMatcher : public Matcher {
861 std::string Val;
862 MVT::SimpleValueType VT;
863
864 unsigned ResultNo;
865
866public:
867 EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt,
868 unsigned resultNo)
869 : Matcher(EmitStringInteger), Val(val), VT(vt), ResultNo(resultNo) {}
870
871 const std::string &getValue() const { return Val; }
872 MVT::SimpleValueType getVT() const { return VT; }
873 unsigned getResultNo() const { return ResultNo; }
874
875 static bool classof(const Matcher *N) {
876 return N->getKind() == EmitStringInteger;
877 }
878
879private:
880 void printImpl(raw_ostream &OS, indent Indent) const override;
881 bool isEqualImpl(const Matcher *M) const override {
882 return cast<EmitStringIntegerMatcher>(Val: M)->Val == Val &&
883 cast<EmitStringIntegerMatcher>(Val: M)->VT == VT;
884 }
885};
886
887/// EmitRegisterMatcher - This creates a new TargetConstant.
888class EmitRegisterMatcher : public Matcher {
889 /// Reg - The def for the register that we're emitting. If this is null, then
890 /// this is a reference to zero_reg.
891 const CodeGenRegister *Reg;
892 MVT::SimpleValueType VT;
893
894 unsigned ResultNo;
895
896public:
897 EmitRegisterMatcher(const CodeGenRegister *reg, MVT::SimpleValueType vt,
898 unsigned resultNo)
899 : Matcher(EmitRegister), Reg(reg), VT(vt), ResultNo(resultNo) {}
900
901 const CodeGenRegister *getReg() const { return Reg; }
902 MVT::SimpleValueType getVT() const { return VT; }
903 unsigned getResultNo() const { return ResultNo; }
904
905 static bool classof(const Matcher *N) { return N->getKind() == EmitRegister; }
906
907private:
908 void printImpl(raw_ostream &OS, indent Indent) const override;
909 bool isEqualImpl(const Matcher *M) const override {
910 return cast<EmitRegisterMatcher>(Val: M)->Reg == Reg &&
911 cast<EmitRegisterMatcher>(Val: M)->VT == VT;
912 }
913};
914
915/// EmitConvertToTargetMatcher - Emit an operation that reads a specified
916/// recorded node and converts it from being a ISD::Constant to
917/// ISD::TargetConstant, likewise for ConstantFP.
918class EmitConvertToTargetMatcher : public Matcher {
919 unsigned Slot;
920
921 unsigned ResultNo;
922
923public:
924 EmitConvertToTargetMatcher(unsigned slot, unsigned resultNo)
925 : Matcher(EmitConvertToTarget), Slot(slot), ResultNo(resultNo) {}
926
927 unsigned getSlot() const { return Slot; }
928 unsigned getResultNo() const { return ResultNo; }
929
930 static bool classof(const Matcher *N) {
931 return N->getKind() == EmitConvertToTarget;
932 }
933
934private:
935 void printImpl(raw_ostream &OS, indent Indent) const override;
936 bool isEqualImpl(const Matcher *M) const override {
937 return cast<EmitConvertToTargetMatcher>(Val: M)->Slot == Slot;
938 }
939};
940
941/// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
942/// chains together with a token factor. The list of nodes are the nodes in the
943/// matched pattern that have chain input/outputs. This node adds all input
944/// chains of these nodes if they are not themselves a node in the pattern.
945class EmitMergeInputChainsMatcher : public Matcher {
946 SmallVector<unsigned, 3> ChainNodes;
947
948public:
949 EmitMergeInputChainsMatcher(ArrayRef<unsigned> nodes)
950 : Matcher(EmitMergeInputChains), ChainNodes(nodes) {}
951
952 unsigned getNumNodes() const { return ChainNodes.size(); }
953
954 unsigned getNode(unsigned i) const {
955 assert(i < ChainNodes.size());
956 return ChainNodes[i];
957 }
958
959 static bool classof(const Matcher *N) {
960 return N->getKind() == EmitMergeInputChains;
961 }
962
963private:
964 void printImpl(raw_ostream &OS, indent Indent) const override;
965 bool isEqualImpl(const Matcher *M) const override {
966 return cast<EmitMergeInputChainsMatcher>(Val: M)->ChainNodes == ChainNodes;
967 }
968};
969
970/// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
971/// pushing the chain and glue results.
972///
973class EmitCopyToRegMatcher : public Matcher {
974 unsigned SrcSlot; // Value to copy into the physreg.
975 const CodeGenRegister *DestPhysReg;
976
977public:
978 EmitCopyToRegMatcher(unsigned srcSlot, const CodeGenRegister *destPhysReg)
979 : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
980
981 unsigned getSrcSlot() const { return SrcSlot; }
982 const CodeGenRegister *getDestPhysReg() const { return DestPhysReg; }
983
984 static bool classof(const Matcher *N) {
985 return N->getKind() == EmitCopyToReg;
986 }
987
988private:
989 void printImpl(raw_ostream &OS, indent Indent) const override;
990 bool isEqualImpl(const Matcher *M) const override {
991 return cast<EmitCopyToRegMatcher>(Val: M)->SrcSlot == SrcSlot &&
992 cast<EmitCopyToRegMatcher>(Val: M)->DestPhysReg == DestPhysReg;
993 }
994};
995
996/// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
997/// recorded node and records the result.
998class EmitNodeXFormMatcher : public Matcher {
999 unsigned Slot;
1000 const Record *NodeXForm;
1001
1002 unsigned ResultNo;
1003
1004public:
1005 EmitNodeXFormMatcher(unsigned slot, const Record *nodeXForm,
1006 unsigned resultNo)
1007 : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm),
1008 ResultNo(resultNo) {}
1009
1010 unsigned getSlot() const { return Slot; }
1011 const Record *getNodeXForm() const { return NodeXForm; }
1012 unsigned getResultNo() const { return ResultNo; }
1013
1014 static bool classof(const Matcher *N) {
1015 return N->getKind() == EmitNodeXForm;
1016 }
1017
1018private:
1019 void printImpl(raw_ostream &OS, indent Indent) const override;
1020 bool isEqualImpl(const Matcher *M) const override {
1021 return cast<EmitNodeXFormMatcher>(Val: M)->Slot == Slot &&
1022 cast<EmitNodeXFormMatcher>(Val: M)->NodeXForm == NodeXForm;
1023 }
1024};
1025
1026/// EmitNodeMatcherCommon - Common class shared between EmitNode and
1027/// MorphNodeTo.
1028class EmitNodeMatcherCommon : public Matcher {
1029 const CodeGenInstruction &CGI;
1030 const SmallVector<MVT::SimpleValueType, 3> VTs;
1031 const SmallVector<unsigned, 6> Operands;
1032 bool HasChain, HasInGlue, HasOutGlue, HasMemRefs;
1033
1034 /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
1035 /// If this is a varidic node, this is set to the number of fixed arity
1036 /// operands in the root of the pattern. The rest are appended to this node.
1037 int NumFixedArityOperands;
1038
1039public:
1040 EmitNodeMatcherCommon(const CodeGenInstruction &cgi,
1041 ArrayRef<MVT::SimpleValueType> vts,
1042 ArrayRef<unsigned> operands, bool hasChain,
1043 bool hasInGlue, bool hasOutGlue, bool hasmemrefs,
1044 int numfixedarityoperands, bool isMorphNodeTo)
1045 : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), CGI(cgi), VTs(vts),
1046 Operands(operands), HasChain(hasChain), HasInGlue(hasInGlue),
1047 HasOutGlue(hasOutGlue), HasMemRefs(hasmemrefs),
1048 NumFixedArityOperands(numfixedarityoperands) {}
1049
1050 const CodeGenInstruction &getInstruction() const { return CGI; }
1051
1052 unsigned getNumVTs() const { return VTs.size(); }
1053 MVT::SimpleValueType getVT(unsigned i) const {
1054 assert(i < VTs.size());
1055 return VTs[i];
1056 }
1057
1058 unsigned getNumOperands() const { return Operands.size(); }
1059 unsigned getOperand(unsigned i) const {
1060 assert(i < Operands.size());
1061 return Operands[i];
1062 }
1063
1064 const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
1065 const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
1066
1067 bool hasChain() const { return HasChain; }
1068 bool hasInGlue() const { return HasInGlue; }
1069 bool hasOutGlue() const { return HasOutGlue; }
1070 bool hasMemRefs() const { return HasMemRefs; }
1071 int getNumFixedArityOperands() const { return NumFixedArityOperands; }
1072
1073 static bool classof(const Matcher *N) {
1074 return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
1075 }
1076
1077private:
1078 void printImpl(raw_ostream &OS, indent Indent) const override;
1079 bool isEqualImpl(const Matcher *M) const override;
1080};
1081
1082/// EmitNodeMatcher - This signals a successful match and generates a node.
1083class EmitNodeMatcher : public EmitNodeMatcherCommon {
1084 void anchor() override;
1085 unsigned FirstResultSlot;
1086
1087public:
1088 EmitNodeMatcher(const CodeGenInstruction &cgi,
1089 ArrayRef<MVT::SimpleValueType> vts,
1090 ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue,
1091 bool hasOutGlue, bool hasmemrefs, int numfixedarityoperands,
1092 unsigned firstresultslot)
1093 : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue,
1094 hasOutGlue, hasmemrefs, numfixedarityoperands,
1095 false),
1096 FirstResultSlot(firstresultslot) {}
1097
1098 unsigned getFirstResultSlot() const { return FirstResultSlot; }
1099
1100 static bool classof(const Matcher *N) { return N->getKind() == EmitNode; }
1101};
1102
1103class MorphNodeToMatcher : public EmitNodeMatcherCommon {
1104 void anchor() override;
1105 const PatternToMatch &Pattern;
1106
1107public:
1108 MorphNodeToMatcher(const CodeGenInstruction &cgi,
1109 ArrayRef<MVT::SimpleValueType> vts,
1110 ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue,
1111 bool hasOutGlue, bool hasmemrefs,
1112 int numfixedarityoperands, const PatternToMatch &pattern)
1113 : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue,
1114 hasOutGlue, hasmemrefs, numfixedarityoperands,
1115 true),
1116 Pattern(pattern) {}
1117
1118 const PatternToMatch &getPattern() const { return Pattern; }
1119
1120 static bool classof(const Matcher *N) { return N->getKind() == MorphNodeTo; }
1121};
1122
1123/// CompleteMatchMatcher - Complete a match by replacing the results of the
1124/// pattern with the newly generated nodes. This also prints a comment
1125/// indicating the source and dest patterns.
1126class CompleteMatchMatcher : public Matcher {
1127 SmallVector<unsigned, 2> Results;
1128 const PatternToMatch &Pattern;
1129
1130public:
1131 CompleteMatchMatcher(ArrayRef<unsigned> results,
1132 const PatternToMatch &pattern)
1133 : Matcher(CompleteMatch), Results(results), Pattern(pattern) {}
1134
1135 unsigned getNumResults() const { return Results.size(); }
1136 unsigned getResult(unsigned R) const { return Results[R]; }
1137 const PatternToMatch &getPattern() const { return Pattern; }
1138
1139 static bool classof(const Matcher *N) {
1140 return N->getKind() == CompleteMatch;
1141 }
1142
1143private:
1144 void printImpl(raw_ostream &OS, indent Indent) const override;
1145 bool isEqualImpl(const Matcher *M) const override {
1146 return cast<CompleteMatchMatcher>(Val: M)->Results == Results &&
1147 &cast<CompleteMatchMatcher>(Val: M)->Pattern == &Pattern;
1148 }
1149};
1150
1151} // end namespace llvm
1152
1153#endif // LLVM_UTILS_TABLEGEN_COMMON_DAGISELMATCHER_H
1154