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_DAGISELMATCHER_H
10#define LLVM_UTILS_TABLEGEN_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, unsigned indent = 0) const;
189 void printOne(raw_ostream &OS) const;
190 void dump() const;
191
192protected:
193 virtual void printImpl(raw_ostream &OS, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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 const SmallVectorImpl<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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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 StringRef TypeName;
688
689public:
690 CheckValueTypeMatcher(StringRef type_name)
691 : Matcher(CheckValueType), TypeName(type_name) {}
692
693 StringRef getTypeName() const { return TypeName; }
694
695 static bool classof(const Matcher *N) {
696 return N->getKind() == CheckValueType;
697 }
698
699private:
700 void printImpl(raw_ostream &OS, unsigned indent) const override;
701 bool isEqualImpl(const Matcher *M) const override {
702 return cast<CheckValueTypeMatcher>(Val: M)->TypeName == TypeName;
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 std::string 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 const std::string &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 std::string 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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
837public:
838 EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
839 : Matcher(EmitInteger), Val(val), VT(vt) {}
840
841 int64_t getValue() const { return Val; }
842 MVT::SimpleValueType getVT() const { return VT; }
843
844 static bool classof(const Matcher *N) { return N->getKind() == EmitInteger; }
845
846private:
847 void printImpl(raw_ostream &OS, unsigned indent) const override;
848 bool isEqualImpl(const Matcher *M) const override {
849 return cast<EmitIntegerMatcher>(Val: M)->Val == Val &&
850 cast<EmitIntegerMatcher>(Val: M)->VT == VT;
851 }
852};
853
854/// EmitStringIntegerMatcher - A target constant whose value is represented
855/// by a string.
856class EmitStringIntegerMatcher : public Matcher {
857 std::string Val;
858 MVT::SimpleValueType VT;
859
860public:
861 EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
862 : Matcher(EmitStringInteger), Val(val), VT(vt) {}
863
864 const std::string &getValue() const { return Val; }
865 MVT::SimpleValueType getVT() const { return VT; }
866
867 static bool classof(const Matcher *N) {
868 return N->getKind() == EmitStringInteger;
869 }
870
871private:
872 void printImpl(raw_ostream &OS, unsigned indent) const override;
873 bool isEqualImpl(const Matcher *M) const override {
874 return cast<EmitStringIntegerMatcher>(Val: M)->Val == Val &&
875 cast<EmitStringIntegerMatcher>(Val: M)->VT == VT;
876 }
877};
878
879/// EmitRegisterMatcher - This creates a new TargetConstant.
880class EmitRegisterMatcher : public Matcher {
881 /// Reg - The def for the register that we're emitting. If this is null, then
882 /// this is a reference to zero_reg.
883 const CodeGenRegister *Reg;
884 MVT::SimpleValueType VT;
885
886public:
887 EmitRegisterMatcher(const CodeGenRegister *reg, MVT::SimpleValueType vt)
888 : Matcher(EmitRegister), Reg(reg), VT(vt) {}
889
890 const CodeGenRegister *getReg() const { return Reg; }
891 MVT::SimpleValueType getVT() const { return VT; }
892
893 static bool classof(const Matcher *N) { return N->getKind() == EmitRegister; }
894
895private:
896 void printImpl(raw_ostream &OS, unsigned indent) const override;
897 bool isEqualImpl(const Matcher *M) const override {
898 return cast<EmitRegisterMatcher>(Val: M)->Reg == Reg &&
899 cast<EmitRegisterMatcher>(Val: M)->VT == VT;
900 }
901};
902
903/// EmitConvertToTargetMatcher - Emit an operation that reads a specified
904/// recorded node and converts it from being a ISD::Constant to
905/// ISD::TargetConstant, likewise for ConstantFP.
906class EmitConvertToTargetMatcher : public Matcher {
907 unsigned Slot;
908
909public:
910 EmitConvertToTargetMatcher(unsigned slot)
911 : Matcher(EmitConvertToTarget), Slot(slot) {}
912
913 unsigned getSlot() const { return Slot; }
914
915 static bool classof(const Matcher *N) {
916 return N->getKind() == EmitConvertToTarget;
917 }
918
919private:
920 void printImpl(raw_ostream &OS, unsigned indent) const override;
921 bool isEqualImpl(const Matcher *M) const override {
922 return cast<EmitConvertToTargetMatcher>(Val: M)->Slot == Slot;
923 }
924};
925
926/// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
927/// chains together with a token factor. The list of nodes are the nodes in the
928/// matched pattern that have chain input/outputs. This node adds all input
929/// chains of these nodes if they are not themselves a node in the pattern.
930class EmitMergeInputChainsMatcher : public Matcher {
931 SmallVector<unsigned, 3> ChainNodes;
932
933public:
934 EmitMergeInputChainsMatcher(ArrayRef<unsigned> nodes)
935 : Matcher(EmitMergeInputChains), ChainNodes(nodes.begin(), nodes.end()) {}
936
937 unsigned getNumNodes() const { return ChainNodes.size(); }
938
939 unsigned getNode(unsigned i) const {
940 assert(i < ChainNodes.size());
941 return ChainNodes[i];
942 }
943
944 static bool classof(const Matcher *N) {
945 return N->getKind() == EmitMergeInputChains;
946 }
947
948private:
949 void printImpl(raw_ostream &OS, unsigned indent) const override;
950 bool isEqualImpl(const Matcher *M) const override {
951 return cast<EmitMergeInputChainsMatcher>(Val: M)->ChainNodes == ChainNodes;
952 }
953};
954
955/// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
956/// pushing the chain and glue results.
957///
958class EmitCopyToRegMatcher : public Matcher {
959 unsigned SrcSlot; // Value to copy into the physreg.
960 const CodeGenRegister *DestPhysReg;
961
962public:
963 EmitCopyToRegMatcher(unsigned srcSlot, const CodeGenRegister *destPhysReg)
964 : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
965
966 unsigned getSrcSlot() const { return SrcSlot; }
967 const CodeGenRegister *getDestPhysReg() const { return DestPhysReg; }
968
969 static bool classof(const Matcher *N) {
970 return N->getKind() == EmitCopyToReg;
971 }
972
973private:
974 void printImpl(raw_ostream &OS, unsigned indent) const override;
975 bool isEqualImpl(const Matcher *M) const override {
976 return cast<EmitCopyToRegMatcher>(Val: M)->SrcSlot == SrcSlot &&
977 cast<EmitCopyToRegMatcher>(Val: M)->DestPhysReg == DestPhysReg;
978 }
979};
980
981/// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
982/// recorded node and records the result.
983class EmitNodeXFormMatcher : public Matcher {
984 unsigned Slot;
985 Record *NodeXForm;
986
987public:
988 EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
989 : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
990
991 unsigned getSlot() const { return Slot; }
992 Record *getNodeXForm() const { return NodeXForm; }
993
994 static bool classof(const Matcher *N) {
995 return N->getKind() == EmitNodeXForm;
996 }
997
998private:
999 void printImpl(raw_ostream &OS, unsigned indent) const override;
1000 bool isEqualImpl(const Matcher *M) const override {
1001 return cast<EmitNodeXFormMatcher>(Val: M)->Slot == Slot &&
1002 cast<EmitNodeXFormMatcher>(Val: M)->NodeXForm == NodeXForm;
1003 }
1004};
1005
1006/// EmitNodeMatcherCommon - Common class shared between EmitNode and
1007/// MorphNodeTo.
1008class EmitNodeMatcherCommon : public Matcher {
1009 const CodeGenInstruction &CGI;
1010 const SmallVector<MVT::SimpleValueType, 3> VTs;
1011 const SmallVector<unsigned, 6> Operands;
1012 bool HasChain, HasInGlue, HasOutGlue, HasMemRefs;
1013
1014 /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
1015 /// If this is a varidic node, this is set to the number of fixed arity
1016 /// operands in the root of the pattern. The rest are appended to this node.
1017 int NumFixedArityOperands;
1018
1019public:
1020 EmitNodeMatcherCommon(const CodeGenInstruction &cgi,
1021 ArrayRef<MVT::SimpleValueType> vts,
1022 ArrayRef<unsigned> operands, bool hasChain,
1023 bool hasInGlue, bool hasOutGlue, bool hasmemrefs,
1024 int numfixedarityoperands, bool isMorphNodeTo)
1025 : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), CGI(cgi),
1026 VTs(vts.begin(), vts.end()), Operands(operands.begin(), operands.end()),
1027 HasChain(hasChain), HasInGlue(hasInGlue), HasOutGlue(hasOutGlue),
1028 HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
1029
1030 const CodeGenInstruction &getInstruction() const { return CGI; }
1031
1032 unsigned getNumVTs() const { return VTs.size(); }
1033 MVT::SimpleValueType getVT(unsigned i) const {
1034 assert(i < VTs.size());
1035 return VTs[i];
1036 }
1037
1038 unsigned getNumOperands() const { return Operands.size(); }
1039 unsigned getOperand(unsigned i) const {
1040 assert(i < Operands.size());
1041 return Operands[i];
1042 }
1043
1044 const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
1045 const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
1046
1047 bool hasChain() const { return HasChain; }
1048 bool hasInGlue() const { return HasInGlue; }
1049 bool hasOutGlue() const { return HasOutGlue; }
1050 bool hasMemRefs() const { return HasMemRefs; }
1051 int getNumFixedArityOperands() const { return NumFixedArityOperands; }
1052
1053 static bool classof(const Matcher *N) {
1054 return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
1055 }
1056
1057private:
1058 void printImpl(raw_ostream &OS, unsigned indent) const override;
1059 bool isEqualImpl(const Matcher *M) const override;
1060};
1061
1062/// EmitNodeMatcher - This signals a successful match and generates a node.
1063class EmitNodeMatcher : public EmitNodeMatcherCommon {
1064 void anchor() override;
1065 unsigned FirstResultSlot;
1066
1067public:
1068 EmitNodeMatcher(const CodeGenInstruction &cgi,
1069 ArrayRef<MVT::SimpleValueType> vts,
1070 ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue,
1071 bool hasOutGlue, bool hasmemrefs, int numfixedarityoperands,
1072 unsigned firstresultslot)
1073 : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue,
1074 hasOutGlue, hasmemrefs, numfixedarityoperands,
1075 false),
1076 FirstResultSlot(firstresultslot) {}
1077
1078 unsigned getFirstResultSlot() const { return FirstResultSlot; }
1079
1080 static bool classof(const Matcher *N) { return N->getKind() == EmitNode; }
1081};
1082
1083class MorphNodeToMatcher : public EmitNodeMatcherCommon {
1084 void anchor() override;
1085 const PatternToMatch &Pattern;
1086
1087public:
1088 MorphNodeToMatcher(const CodeGenInstruction &cgi,
1089 ArrayRef<MVT::SimpleValueType> vts,
1090 ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue,
1091 bool hasOutGlue, bool hasmemrefs,
1092 int numfixedarityoperands, const PatternToMatch &pattern)
1093 : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue,
1094 hasOutGlue, hasmemrefs, numfixedarityoperands,
1095 true),
1096 Pattern(pattern) {}
1097
1098 const PatternToMatch &getPattern() const { return Pattern; }
1099
1100 static bool classof(const Matcher *N) { return N->getKind() == MorphNodeTo; }
1101};
1102
1103/// CompleteMatchMatcher - Complete a match by replacing the results of the
1104/// pattern with the newly generated nodes. This also prints a comment
1105/// indicating the source and dest patterns.
1106class CompleteMatchMatcher : public Matcher {
1107 SmallVector<unsigned, 2> Results;
1108 const PatternToMatch &Pattern;
1109
1110public:
1111 CompleteMatchMatcher(ArrayRef<unsigned> results,
1112 const PatternToMatch &pattern)
1113 : Matcher(CompleteMatch), Results(results.begin(), results.end()),
1114 Pattern(pattern) {}
1115
1116 unsigned getNumResults() const { return Results.size(); }
1117 unsigned getResult(unsigned R) const { return Results[R]; }
1118 const PatternToMatch &getPattern() const { return Pattern; }
1119
1120 static bool classof(const Matcher *N) {
1121 return N->getKind() == CompleteMatch;
1122 }
1123
1124private:
1125 void printImpl(raw_ostream &OS, unsigned indent) const override;
1126 bool isEqualImpl(const Matcher *M) const override {
1127 return cast<CompleteMatchMatcher>(Val: M)->Results == Results &&
1128 &cast<CompleteMatchMatcher>(Val: M)->Pattern == &Pattern;
1129 }
1130};
1131
1132} // end namespace llvm
1133
1134#endif
1135

source code of llvm/utils/TableGen/Common/DAGISelMatcher.h