1 //===- DAGISelMatcher.h - Representation of DAG pattern matcher -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef TBLGEN_DAGISELMATCHER_H
11 #define TBLGEN_DAGISELMATCHER_H
13 #include "llvm/CodeGen/ValueTypes.h"
14 #include "llvm/ADT/OwningPtr.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/Support/Casting.h"
20 class CodeGenDAGPatterns;
27 Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,
28 const CodeGenDAGPatterns &CGP);
29 Matcher *OptimizeMatcher(Matcher *Matcher);
30 void EmitMatcherTable(const Matcher *Matcher, raw_ostream &OS);
33 /// Matcher - Base class for all the the DAG ISel Matcher representation
36 // The next matcher node that is executed after this one. Null if this is the
37 // last stage of a match.
38 OwningPtr<Matcher> Next;
41 // Matcher state manipulation.
42 Scope, // Push a checking scope.
43 RecordNode, // Record the current node.
44 RecordChild, // Record a child of the current node.
45 RecordMemRef, // Record the memref in the current node.
46 CaptureFlagInput, // If the current node has an input flag, save it.
47 MoveChild, // Move current node to specified child.
48 MoveParent, // Move current node to parent.
50 // Predicate checking.
51 CheckSame, // Fail if not same as prev match.
52 CheckPatternPredicate,
53 CheckPredicate, // Fail if node predicate fails.
54 CheckOpcode, // Fail if not opcode.
55 CheckMultiOpcode, // Fail if not in opcode list.
56 CheckType, // Fail if not correct type.
57 CheckChildType, // Fail if child has wrong type.
58 CheckInteger, // Fail if wrong val.
59 CheckCondCode, // Fail if not condcode.
64 CheckFoldableChainNode,
67 // Node creation/emisssion.
68 EmitInteger, // Create a TargetConstant
69 EmitStringInteger, // Create a TargetConstant from a string.
70 EmitRegister, // Create a register.
71 EmitConvertToTarget, // Convert a imm/fpimm to target imm/fpimm
72 EmitMergeInputChains, // Merge together a chains for an input.
73 EmitCopyToReg, // Emit a copytoreg into a physreg.
74 EmitNode, // Create a DAG node
75 EmitNodeXForm, // Run a SDNodeXForm
76 MarkFlagResults, // Indicate which interior nodes have flag results.
77 CompleteMatch // Finish a match and update the results.
82 Matcher(KindTy K) : Kind(K) {}
86 KindTy getKind() const { return Kind; }
88 Matcher *getNext() { return Next.get(); }
89 const Matcher *getNext() const { return Next.get(); }
90 void setNext(Matcher *C) { Next.reset(C); }
91 Matcher *takeNext() { return Next.take(); }
93 OwningPtr<Matcher> &getNextPtr() { return Next; }
95 static inline bool classof(const Matcher *) { return true; }
97 virtual void print(raw_ostream &OS, unsigned indent = 0) const = 0;
100 void printNext(raw_ostream &OS, unsigned indent) const;
103 /// ScopeMatcher - This pushes a failure scope on the stack and evaluates
104 /// 'Check'. If 'Check' fails to match, it pops its scope and continues on to
106 class ScopeMatcher : public Matcher {
107 OwningPtr<Matcher> Check;
109 ScopeMatcher(Matcher *check = 0, Matcher *next = 0)
110 : Matcher(Scope), Check(check) {
114 Matcher *getCheck() { return Check.get(); }
115 const Matcher *getCheck() const { return Check.get(); }
116 void setCheck(Matcher *N) { Check.reset(N); }
117 OwningPtr<Matcher> &getCheckPtr() { return Check; }
119 static inline bool classof(const Matcher *N) {
120 return N->getKind() == Scope;
123 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
126 /// RecordMatcher - Save the current node in the operand list.
127 class RecordMatcher : public Matcher {
128 /// WhatFor - This is a string indicating why we're recording this. This
129 /// should only be used for comment generation not anything semantic.
132 RecordMatcher(const std::string &whatfor)
133 : Matcher(RecordNode), WhatFor(whatfor) {}
135 const std::string &getWhatFor() const { return WhatFor; }
137 static inline bool classof(const Matcher *N) {
138 return N->getKind() == RecordNode;
141 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
144 /// RecordChildMatcher - Save a numbered child of the current node, or fail
145 /// the match if it doesn't exist. This is logically equivalent to:
146 /// MoveChild N + RecordNode + MoveParent.
147 class RecordChildMatcher : public Matcher {
150 /// WhatFor - This is a string indicating why we're recording this. This
151 /// should only be used for comment generation not anything semantic.
154 RecordChildMatcher(unsigned childno, const std::string &whatfor)
155 : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor) {}
157 unsigned getChildNo() const { return ChildNo; }
158 const std::string &getWhatFor() const { return WhatFor; }
160 static inline bool classof(const Matcher *N) {
161 return N->getKind() == RecordChild;
164 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
167 /// RecordMemRefMatcher - Save the current node's memref.
168 class RecordMemRefMatcher : public Matcher {
170 RecordMemRefMatcher() : Matcher(RecordMemRef) {}
172 static inline bool classof(const Matcher *N) {
173 return N->getKind() == RecordMemRef;
176 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
180 /// CaptureFlagInputMatcher - If the current record has a flag input, record
181 /// it so that it is used as an input to the generated code.
182 class CaptureFlagInputMatcher : public Matcher {
184 CaptureFlagInputMatcher() : Matcher(CaptureFlagInput) {}
186 static inline bool classof(const Matcher *N) {
187 return N->getKind() == CaptureFlagInput;
190 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
193 /// MoveChildMatcher - This tells the interpreter to move into the
194 /// specified child node.
195 class MoveChildMatcher : public Matcher {
198 MoveChildMatcher(unsigned childNo) : Matcher(MoveChild), ChildNo(childNo) {}
200 unsigned getChildNo() const { return ChildNo; }
202 static inline bool classof(const Matcher *N) {
203 return N->getKind() == MoveChild;
206 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
209 /// MoveParentMatcher - This tells the interpreter to move to the parent
210 /// of the current node.
211 class MoveParentMatcher : public Matcher {
213 MoveParentMatcher() : Matcher(MoveParent) {}
215 static inline bool classof(const Matcher *N) {
216 return N->getKind() == MoveParent;
219 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
222 /// CheckSameMatcher - This checks to see if this node is exactly the same
223 /// node as the specified match that was recorded with 'Record'. This is used
224 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
225 class CheckSameMatcher : public Matcher {
226 unsigned MatchNumber;
228 CheckSameMatcher(unsigned matchnumber)
229 : Matcher(CheckSame), MatchNumber(matchnumber) {}
231 unsigned getMatchNumber() const { return MatchNumber; }
233 static inline bool classof(const Matcher *N) {
234 return N->getKind() == CheckSame;
237 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
240 /// CheckPatternPredicateMatcher - This checks the target-specific predicate
241 /// to see if the entire pattern is capable of matching. This predicate does
242 /// not take a node as input. This is used for subtarget feature checks etc.
243 class CheckPatternPredicateMatcher : public Matcher {
244 std::string Predicate;
246 CheckPatternPredicateMatcher(StringRef predicate)
247 : Matcher(CheckPatternPredicate), Predicate(predicate) {}
249 StringRef getPredicate() const { return Predicate; }
251 static inline bool classof(const Matcher *N) {
252 return N->getKind() == CheckPatternPredicate;
255 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
258 /// CheckPredicateMatcher - This checks the target-specific predicate to
259 /// see if the node is acceptable.
260 class CheckPredicateMatcher : public Matcher {
263 CheckPredicateMatcher(StringRef predname)
264 : Matcher(CheckPredicate), PredName(predname) {}
266 StringRef getPredicateName() const { return PredName; }
268 static inline bool classof(const Matcher *N) {
269 return N->getKind() == CheckPredicate;
272 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
276 /// CheckOpcodeMatcher - This checks to see if the current node has the
277 /// specified opcode, if not it fails to match.
278 class CheckOpcodeMatcher : public Matcher {
279 StringRef OpcodeName;
281 CheckOpcodeMatcher(StringRef opcodename)
282 : Matcher(CheckOpcode), OpcodeName(opcodename) {}
284 StringRef getOpcodeName() const { return OpcodeName; }
286 static inline bool classof(const Matcher *N) {
287 return N->getKind() == CheckOpcode;
290 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
293 /// CheckMultiOpcodeMatcher - This checks to see if the current node has one
294 /// of the specified opcode, if not it fails to match.
295 class CheckMultiOpcodeMatcher : public Matcher {
296 SmallVector<StringRef, 4> OpcodeNames;
298 CheckMultiOpcodeMatcher(const StringRef *opcodes, unsigned numops)
299 : Matcher(CheckMultiOpcode), OpcodeNames(opcodes, opcodes+numops) {}
301 unsigned getNumOpcodeNames() const { return OpcodeNames.size(); }
302 StringRef getOpcodeName(unsigned i) const { return OpcodeNames[i]; }
304 static inline bool classof(const Matcher *N) {
305 return N->getKind() == CheckMultiOpcode;
308 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
313 /// CheckTypeMatcher - This checks to see if the current node has the
314 /// specified type, if not it fails to match.
315 class CheckTypeMatcher : public Matcher {
316 MVT::SimpleValueType Type;
318 CheckTypeMatcher(MVT::SimpleValueType type)
319 : Matcher(CheckType), Type(type) {}
321 MVT::SimpleValueType getType() const { return Type; }
323 static inline bool classof(const Matcher *N) {
324 return N->getKind() == CheckType;
327 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
330 /// CheckChildTypeMatcher - This checks to see if a child node has the
331 /// specified type, if not it fails to match.
332 class CheckChildTypeMatcher : public Matcher {
334 MVT::SimpleValueType Type;
336 CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type)
337 : Matcher(CheckChildType), ChildNo(childno), Type(type) {}
339 unsigned getChildNo() const { return ChildNo; }
340 MVT::SimpleValueType getType() const { return Type; }
342 static inline bool classof(const Matcher *N) {
343 return N->getKind() == CheckChildType;
346 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
350 /// CheckIntegerMatcher - This checks to see if the current node is a
351 /// ConstantSDNode with the specified integer value, if not it fails to match.
352 class CheckIntegerMatcher : public Matcher {
355 CheckIntegerMatcher(int64_t value)
356 : Matcher(CheckInteger), Value(value) {}
358 int64_t getValue() const { return Value; }
360 static inline bool classof(const Matcher *N) {
361 return N->getKind() == CheckInteger;
364 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
367 /// CheckCondCodeMatcher - This checks to see if the current node is a
368 /// CondCodeSDNode with the specified condition, if not it fails to match.
369 class CheckCondCodeMatcher : public Matcher {
370 StringRef CondCodeName;
372 CheckCondCodeMatcher(StringRef condcodename)
373 : Matcher(CheckCondCode), CondCodeName(condcodename) {}
375 StringRef getCondCodeName() const { return CondCodeName; }
377 static inline bool classof(const Matcher *N) {
378 return N->getKind() == CheckCondCode;
381 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
384 /// CheckValueTypeMatcher - This checks to see if the current node is a
385 /// VTSDNode with the specified type, if not it fails to match.
386 class CheckValueTypeMatcher : public Matcher {
389 CheckValueTypeMatcher(StringRef type_name)
390 : Matcher(CheckValueType), TypeName(type_name) {}
392 StringRef getTypeName() const { return TypeName; }
394 static inline bool classof(const Matcher *N) {
395 return N->getKind() == CheckValueType;
398 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
403 /// CheckComplexPatMatcher - This node runs the specified ComplexPattern on
404 /// the current node.
405 class CheckComplexPatMatcher : public Matcher {
406 const ComplexPattern &Pattern;
408 CheckComplexPatMatcher(const ComplexPattern &pattern)
409 : Matcher(CheckComplexPat), Pattern(pattern) {}
411 const ComplexPattern &getPattern() const { return Pattern; }
413 static inline bool classof(const Matcher *N) {
414 return N->getKind() == CheckComplexPat;
417 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
420 /// CheckAndImmMatcher - This checks to see if the current node is an 'and'
421 /// with something equivalent to the specified immediate.
422 class CheckAndImmMatcher : public Matcher {
425 CheckAndImmMatcher(int64_t value)
426 : Matcher(CheckAndImm), Value(value) {}
428 int64_t getValue() const { return Value; }
430 static inline bool classof(const Matcher *N) {
431 return N->getKind() == CheckAndImm;
434 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
437 /// CheckOrImmMatcher - This checks to see if the current node is an 'and'
438 /// with something equivalent to the specified immediate.
439 class CheckOrImmMatcher : public Matcher {
442 CheckOrImmMatcher(int64_t value)
443 : Matcher(CheckOrImm), Value(value) {}
445 int64_t getValue() const { return Value; }
447 static inline bool classof(const Matcher *N) {
448 return N->getKind() == CheckOrImm;
451 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
454 /// CheckFoldableChainNodeMatcher - This checks to see if the current node
455 /// (which defines a chain operand) is safe to fold into a larger pattern.
456 class CheckFoldableChainNodeMatcher : public Matcher {
458 CheckFoldableChainNodeMatcher()
459 : Matcher(CheckFoldableChainNode) {}
461 static inline bool classof(const Matcher *N) {
462 return N->getKind() == CheckFoldableChainNode;
465 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
468 /// CheckChainCompatibleMatcher - Verify that the current node's chain
469 /// operand is 'compatible' with the specified recorded node's.
470 class CheckChainCompatibleMatcher : public Matcher {
473 CheckChainCompatibleMatcher(unsigned previousop)
474 : Matcher(CheckChainCompatible), PreviousOp(previousop) {}
476 unsigned getPreviousOp() const { return PreviousOp; }
478 static inline bool classof(const Matcher *N) {
479 return N->getKind() == CheckChainCompatible;
482 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
485 /// EmitIntegerMatcher - This creates a new TargetConstant.
486 class EmitIntegerMatcher : public Matcher {
488 MVT::SimpleValueType VT;
490 EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
491 : Matcher(EmitInteger), Val(val), VT(vt) {}
493 int64_t getValue() const { return Val; }
494 MVT::SimpleValueType getVT() const { return VT; }
496 static inline bool classof(const Matcher *N) {
497 return N->getKind() == EmitInteger;
500 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
503 /// EmitStringIntegerMatcher - A target constant whose value is represented
505 class EmitStringIntegerMatcher : public Matcher {
507 MVT::SimpleValueType VT;
509 EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
510 : Matcher(EmitStringInteger), Val(val), VT(vt) {}
512 const std::string &getValue() const { return Val; }
513 MVT::SimpleValueType getVT() const { return VT; }
515 static inline bool classof(const Matcher *N) {
516 return N->getKind() == EmitStringInteger;
519 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
522 /// EmitRegisterMatcher - This creates a new TargetConstant.
523 class EmitRegisterMatcher : public Matcher {
524 /// Reg - The def for the register that we're emitting. If this is null, then
525 /// this is a reference to zero_reg.
527 MVT::SimpleValueType VT;
529 EmitRegisterMatcher(Record *reg, MVT::SimpleValueType vt)
530 : Matcher(EmitRegister), Reg(reg), VT(vt) {}
532 Record *getReg() const { return Reg; }
533 MVT::SimpleValueType getVT() const { return VT; }
535 static inline bool classof(const Matcher *N) {
536 return N->getKind() == EmitRegister;
539 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
542 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified
543 /// recorded node and converts it from being a ISD::Constant to
544 /// ISD::TargetConstant, likewise for ConstantFP.
545 class EmitConvertToTargetMatcher : public Matcher {
548 EmitConvertToTargetMatcher(unsigned slot)
549 : Matcher(EmitConvertToTarget), Slot(slot) {}
551 unsigned getSlot() const { return Slot; }
553 static inline bool classof(const Matcher *N) {
554 return N->getKind() == EmitConvertToTarget;
557 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
560 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
561 /// chains together with a token factor. The list of nodes are the nodes in the
562 /// matched pattern that have chain input/outputs. This node adds all input
563 /// chains of these nodes if they are not themselves a node in the pattern.
564 class EmitMergeInputChainsMatcher : public Matcher {
565 SmallVector<unsigned, 3> ChainNodes;
567 EmitMergeInputChainsMatcher(const unsigned *nodes, unsigned NumNodes)
568 : Matcher(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
570 unsigned getNumNodes() const { return ChainNodes.size(); }
572 unsigned getNode(unsigned i) const {
573 assert(i < ChainNodes.size());
574 return ChainNodes[i];
577 static inline bool classof(const Matcher *N) {
578 return N->getKind() == EmitMergeInputChains;
581 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
584 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
585 /// pushing the chain and flag results.
587 class EmitCopyToRegMatcher : public Matcher {
588 unsigned SrcSlot; // Value to copy into the physreg.
591 EmitCopyToRegMatcher(unsigned srcSlot, Record *destPhysReg)
592 : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
594 unsigned getSrcSlot() const { return SrcSlot; }
595 Record *getDestPhysReg() const { return DestPhysReg; }
597 static inline bool classof(const Matcher *N) {
598 return N->getKind() == EmitCopyToReg;
601 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
606 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
607 /// recorded node and records the result.
608 class EmitNodeXFormMatcher : public Matcher {
612 EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
613 : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
615 unsigned getSlot() const { return Slot; }
616 Record *getNodeXForm() const { return NodeXForm; }
618 static inline bool classof(const Matcher *N) {
619 return N->getKind() == EmitNodeXForm;
622 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
625 /// EmitNodeMatcher - This signals a successful match and generates a node.
626 class EmitNodeMatcher : public Matcher {
627 std::string OpcodeName;
628 const SmallVector<MVT::SimpleValueType, 3> VTs;
629 const SmallVector<unsigned, 6> Operands;
630 bool HasChain, HasFlag, HasMemRefs;
632 /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
633 /// If this is a varidic node, this is set to the number of fixed arity
634 /// operands in the root of the pattern. The rest are appended to this node.
635 int NumFixedArityOperands;
637 EmitNodeMatcher(const std::string &opcodeName,
638 const MVT::SimpleValueType *vts, unsigned numvts,
639 const unsigned *operands, unsigned numops,
640 bool hasChain, bool hasFlag, bool hasmemrefs,
641 int numfixedarityoperands)
642 : Matcher(EmitNode), OpcodeName(opcodeName),
643 VTs(vts, vts+numvts), Operands(operands, operands+numops),
644 HasChain(hasChain), HasFlag(hasFlag), HasMemRefs(hasmemrefs),
645 NumFixedArityOperands(numfixedarityoperands) {}
647 const std::string &getOpcodeName() const { return OpcodeName; }
649 unsigned getNumVTs() const { return VTs.size(); }
650 MVT::SimpleValueType getVT(unsigned i) const {
651 assert(i < VTs.size());
655 unsigned getNumOperands() const { return Operands.size(); }
656 unsigned getOperand(unsigned i) const {
657 assert(i < Operands.size());
661 bool hasChain() const { return HasChain; }
662 bool hasFlag() const { return HasFlag; }
663 bool hasMemRefs() const { return HasMemRefs; }
664 int getNumFixedArityOperands() const { return NumFixedArityOperands; }
666 static inline bool classof(const Matcher *N) {
667 return N->getKind() == EmitNode;
670 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
673 /// MarkFlagResultsMatcher - This node indicates which non-root nodes in the
674 /// pattern produce flags. This allows CompleteMatchMatcher to update them
675 /// with the output flag of the resultant code.
676 class MarkFlagResultsMatcher : public Matcher {
677 SmallVector<unsigned, 3> FlagResultNodes;
679 MarkFlagResultsMatcher(const unsigned *nodes, unsigned NumNodes)
680 : Matcher(MarkFlagResults), FlagResultNodes(nodes, nodes+NumNodes) {}
682 unsigned getNumNodes() const { return FlagResultNodes.size(); }
684 unsigned getNode(unsigned i) const {
685 assert(i < FlagResultNodes.size());
686 return FlagResultNodes[i];
689 static inline bool classof(const Matcher *N) {
690 return N->getKind() == MarkFlagResults;
693 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
696 /// CompleteMatchMatcher - Complete a match by replacing the results of the
697 /// pattern with the newly generated nodes. This also prints a comment
698 /// indicating the source and dest patterns.
699 class CompleteMatchMatcher : public Matcher {
700 SmallVector<unsigned, 2> Results;
701 const PatternToMatch &Pattern;
703 CompleteMatchMatcher(const unsigned *results, unsigned numresults,
704 const PatternToMatch &pattern)
705 : Matcher(CompleteMatch), Results(results, results+numresults),
708 unsigned getNumResults() const { return Results.size(); }
709 unsigned getResult(unsigned R) const { return Results[R]; }
710 const PatternToMatch &getPattern() const { return Pattern; }
712 static inline bool classof(const Matcher *N) {
713 return N->getKind() == CompleteMatch;
716 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
720 } // end namespace llvm