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 MatcherNode *ConvertPatternToMatcher(const PatternToMatch &Pattern,
28 const CodeGenDAGPatterns &CGP);
30 void EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &OS);
33 /// MatcherNode - 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<MatcherNode> Next;
41 // Matcher state manipulation.
42 Push, // Push a checking scope.
43 RecordNode, // Record the current node.
44 RecordMemRef, // Record the memref in the current node.
45 CaptureFlagInput, // If the current node has an input flag, save it.
46 MoveChild, // Move current node to specified child.
47 MoveParent, // Move current node to parent.
49 // Predicate checking.
50 CheckSame, // Fail if not same as prev match.
51 CheckPatternPredicate,
52 CheckPredicate, // Fail if node predicate fails.
53 CheckOpcode, // Fail if not opcode.
54 CheckMultiOpcode, // Fail if not in opcode list.
55 CheckType, // Fail if not correct type.
56 CheckInteger, // Fail if wrong val.
57 CheckCondCode, // Fail if not condcode.
62 CheckFoldableChainNode,
65 // Node creation/emisssion.
66 EmitInteger, // Create a TargetConstant
67 EmitStringInteger, // Create a TargetConstant from a string.
68 EmitRegister, // Create a register.
69 EmitConvertToTarget, // Convert a imm/fpimm to target imm/fpimm
70 EmitMergeInputChains, // Merge together a chains for an input.
71 EmitCopyToReg, // Emit a copytoreg into a physreg.
72 EmitNode, // Create a DAG node
73 EmitNodeXForm, // Run a SDNodeXForm
74 MarkFlagResults, // Indicate which interior nodes have flag results.
75 CompleteMatch // Finish a match and update the results.
80 MatcherNode(KindTy K) : Kind(K) {}
82 virtual ~MatcherNode() {}
84 KindTy getKind() const { return Kind; }
86 MatcherNode *getNext() { return Next.get(); }
87 const MatcherNode *getNext() const { return Next.get(); }
88 void setNext(MatcherNode *C) { Next.reset(C); }
90 static inline bool classof(const MatcherNode *) { return true; }
92 virtual void print(raw_ostream &OS, unsigned indent = 0) const = 0;
95 void printNext(raw_ostream &OS, unsigned indent) const;
98 /// PushMatcherNode - This pushes a failure scope on the stack and evaluates
99 /// 'Next'. If 'Next' fails to match, it pops its scope and attempts to
101 class PushMatcherNode : public MatcherNode {
102 OwningPtr<MatcherNode> Failure;
104 PushMatcherNode(MatcherNode *next = 0, MatcherNode *failure = 0)
105 : MatcherNode(Push), Failure(failure) {
109 MatcherNode *getFailure() { return Failure.get(); }
110 const MatcherNode *getFailure() const { return Failure.get(); }
111 void setFailure(MatcherNode *N) { Failure.reset(N); }
113 static inline bool classof(const MatcherNode *N) {
114 return N->getKind() == Push;
117 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
120 /// RecordMatcherNode - Save the current node in the operand list.
121 class RecordMatcherNode : public MatcherNode {
122 /// WhatFor - This is a string indicating why we're recording this. This
123 /// should only be used for comment generation not anything semantic.
126 RecordMatcherNode(const std::string &whatfor)
127 : MatcherNode(RecordNode), WhatFor(whatfor) {}
129 const std::string &getWhatFor() const { return WhatFor; }
131 static inline bool classof(const MatcherNode *N) {
132 return N->getKind() == RecordNode;
135 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
138 /// RecordMemRefMatcherNode - Save the current node's memref.
139 class RecordMemRefMatcherNode : public MatcherNode {
141 RecordMemRefMatcherNode() : MatcherNode(RecordMemRef) {}
143 static inline bool classof(const MatcherNode *N) {
144 return N->getKind() == RecordMemRef;
147 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
151 /// CaptureFlagInputMatcherNode - If the current record has a flag input, record
152 /// it so that it is used as an input to the generated code.
153 class CaptureFlagInputMatcherNode : public MatcherNode {
155 CaptureFlagInputMatcherNode()
156 : MatcherNode(CaptureFlagInput) {}
158 static inline bool classof(const MatcherNode *N) {
159 return N->getKind() == CaptureFlagInput;
162 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
165 /// MoveChildMatcherNode - This tells the interpreter to move into the
166 /// specified child node.
167 class MoveChildMatcherNode : public MatcherNode {
170 MoveChildMatcherNode(unsigned childNo)
171 : MatcherNode(MoveChild), ChildNo(childNo) {}
173 unsigned getChildNo() const { return ChildNo; }
175 static inline bool classof(const MatcherNode *N) {
176 return N->getKind() == MoveChild;
179 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
182 /// MoveParentMatcherNode - This tells the interpreter to move to the parent
183 /// of the current node.
184 class MoveParentMatcherNode : public MatcherNode {
186 MoveParentMatcherNode()
187 : MatcherNode(MoveParent) {}
189 static inline bool classof(const MatcherNode *N) {
190 return N->getKind() == MoveParent;
193 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
196 /// CheckSameMatcherNode - This checks to see if this node is exactly the same
197 /// node as the specified match that was recorded with 'Record'. This is used
198 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
199 class CheckSameMatcherNode : public MatcherNode {
200 unsigned MatchNumber;
202 CheckSameMatcherNode(unsigned matchnumber)
203 : MatcherNode(CheckSame), MatchNumber(matchnumber) {}
205 unsigned getMatchNumber() const { return MatchNumber; }
207 static inline bool classof(const MatcherNode *N) {
208 return N->getKind() == CheckSame;
211 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
214 /// CheckPatternPredicateMatcherNode - This checks the target-specific predicate
215 /// to see if the entire pattern is capable of matching. This predicate does
216 /// not take a node as input. This is used for subtarget feature checks etc.
217 class CheckPatternPredicateMatcherNode : public MatcherNode {
218 std::string Predicate;
220 CheckPatternPredicateMatcherNode(StringRef predicate)
221 : MatcherNode(CheckPatternPredicate), Predicate(predicate) {}
223 StringRef getPredicate() const { return Predicate; }
225 static inline bool classof(const MatcherNode *N) {
226 return N->getKind() == CheckPatternPredicate;
229 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
232 /// CheckPredicateMatcherNode - This checks the target-specific predicate to
233 /// see if the node is acceptable.
234 class CheckPredicateMatcherNode : public MatcherNode {
237 CheckPredicateMatcherNode(StringRef predname)
238 : MatcherNode(CheckPredicate), PredName(predname) {}
240 StringRef getPredicateName() const { return PredName; }
242 static inline bool classof(const MatcherNode *N) {
243 return N->getKind() == CheckPredicate;
246 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
250 /// CheckOpcodeMatcherNode - This checks to see if the current node has the
251 /// specified opcode, if not it fails to match.
252 class CheckOpcodeMatcherNode : public MatcherNode {
253 StringRef OpcodeName;
255 CheckOpcodeMatcherNode(StringRef opcodename)
256 : MatcherNode(CheckOpcode), OpcodeName(opcodename) {}
258 StringRef getOpcodeName() const { return OpcodeName; }
260 static inline bool classof(const MatcherNode *N) {
261 return N->getKind() == CheckOpcode;
264 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
267 /// CheckMultiOpcodeMatcherNode - This checks to see if the current node has one
268 /// of the specified opcode, if not it fails to match.
269 class CheckMultiOpcodeMatcherNode : public MatcherNode {
270 SmallVector<StringRef, 4> OpcodeNames;
272 CheckMultiOpcodeMatcherNode(const StringRef *opcodes, unsigned numops)
273 : MatcherNode(CheckMultiOpcode), OpcodeNames(opcodes, opcodes+numops) {}
275 unsigned getNumOpcodeNames() const { return OpcodeNames.size(); }
276 StringRef getOpcodeName(unsigned i) const { return OpcodeNames[i]; }
278 static inline bool classof(const MatcherNode *N) {
279 return N->getKind() == CheckMultiOpcode;
282 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
287 /// CheckTypeMatcherNode - This checks to see if the current node has the
288 /// specified type, if not it fails to match.
289 class CheckTypeMatcherNode : public MatcherNode {
290 MVT::SimpleValueType Type;
292 CheckTypeMatcherNode(MVT::SimpleValueType type)
293 : MatcherNode(CheckType), Type(type) {}
295 MVT::SimpleValueType getType() const { return Type; }
297 static inline bool classof(const MatcherNode *N) {
298 return N->getKind() == CheckType;
301 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
304 /// CheckIntegerMatcherNode - This checks to see if the current node is a
305 /// ConstantSDNode with the specified integer value, if not it fails to match.
306 class CheckIntegerMatcherNode : public MatcherNode {
309 CheckIntegerMatcherNode(int64_t value)
310 : MatcherNode(CheckInteger), Value(value) {}
312 int64_t getValue() const { return Value; }
314 static inline bool classof(const MatcherNode *N) {
315 return N->getKind() == CheckInteger;
318 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
321 /// CheckCondCodeMatcherNode - This checks to see if the current node is a
322 /// CondCodeSDNode with the specified condition, if not it fails to match.
323 class CheckCondCodeMatcherNode : public MatcherNode {
324 StringRef CondCodeName;
326 CheckCondCodeMatcherNode(StringRef condcodename)
327 : MatcherNode(CheckCondCode), CondCodeName(condcodename) {}
329 StringRef getCondCodeName() const { return CondCodeName; }
331 static inline bool classof(const MatcherNode *N) {
332 return N->getKind() == CheckCondCode;
335 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
338 /// CheckValueTypeMatcherNode - This checks to see if the current node is a
339 /// VTSDNode with the specified type, if not it fails to match.
340 class CheckValueTypeMatcherNode : public MatcherNode {
343 CheckValueTypeMatcherNode(StringRef type_name)
344 : MatcherNode(CheckValueType), TypeName(type_name) {}
346 StringRef getTypeName() const { return TypeName; }
348 static inline bool classof(const MatcherNode *N) {
349 return N->getKind() == CheckValueType;
352 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
357 /// CheckComplexPatMatcherNode - This node runs the specified ComplexPattern on
358 /// the current node.
359 class CheckComplexPatMatcherNode : public MatcherNode {
360 const ComplexPattern &Pattern;
362 CheckComplexPatMatcherNode(const ComplexPattern &pattern)
363 : MatcherNode(CheckComplexPat), Pattern(pattern) {}
365 const ComplexPattern &getPattern() const { return Pattern; }
367 static inline bool classof(const MatcherNode *N) {
368 return N->getKind() == CheckComplexPat;
371 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
374 /// CheckAndImmMatcherNode - This checks to see if the current node is an 'and'
375 /// with something equivalent to the specified immediate.
376 class CheckAndImmMatcherNode : public MatcherNode {
379 CheckAndImmMatcherNode(int64_t value)
380 : MatcherNode(CheckAndImm), Value(value) {}
382 int64_t getValue() const { return Value; }
384 static inline bool classof(const MatcherNode *N) {
385 return N->getKind() == CheckAndImm;
388 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
391 /// CheckOrImmMatcherNode - This checks to see if the current node is an 'and'
392 /// with something equivalent to the specified immediate.
393 class CheckOrImmMatcherNode : public MatcherNode {
396 CheckOrImmMatcherNode(int64_t value)
397 : MatcherNode(CheckOrImm), Value(value) {}
399 int64_t getValue() const { return Value; }
401 static inline bool classof(const MatcherNode *N) {
402 return N->getKind() == CheckOrImm;
405 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
408 /// CheckFoldableChainNodeMatcherNode - This checks to see if the current node
409 /// (which defines a chain operand) is safe to fold into a larger pattern.
410 class CheckFoldableChainNodeMatcherNode : public MatcherNode {
412 CheckFoldableChainNodeMatcherNode()
413 : MatcherNode(CheckFoldableChainNode) {}
415 static inline bool classof(const MatcherNode *N) {
416 return N->getKind() == CheckFoldableChainNode;
419 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
422 /// CheckChainCompatibleMatcherNode - Verify that the current node's chain
423 /// operand is 'compatible' with the specified recorded node's.
424 class CheckChainCompatibleMatcherNode : public MatcherNode {
427 CheckChainCompatibleMatcherNode(unsigned previousop)
428 : MatcherNode(CheckChainCompatible), PreviousOp(previousop) {}
430 unsigned getPreviousOp() const { return PreviousOp; }
432 static inline bool classof(const MatcherNode *N) {
433 return N->getKind() == CheckChainCompatible;
436 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
439 /// EmitIntegerMatcherNode - This creates a new TargetConstant.
440 class EmitIntegerMatcherNode : public MatcherNode {
442 MVT::SimpleValueType VT;
444 EmitIntegerMatcherNode(int64_t val, MVT::SimpleValueType vt)
445 : MatcherNode(EmitInteger), Val(val), VT(vt) {}
447 int64_t getValue() const { return Val; }
448 MVT::SimpleValueType getVT() const { return VT; }
450 static inline bool classof(const MatcherNode *N) {
451 return N->getKind() == EmitInteger;
454 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
457 /// EmitStringIntegerMatcherNode - A target constant whose value is represented
459 class EmitStringIntegerMatcherNode : public MatcherNode {
461 MVT::SimpleValueType VT;
463 EmitStringIntegerMatcherNode(const std::string &val, MVT::SimpleValueType vt)
464 : MatcherNode(EmitStringInteger), Val(val), VT(vt) {}
466 const std::string &getValue() const { return Val; }
467 MVT::SimpleValueType getVT() const { return VT; }
469 static inline bool classof(const MatcherNode *N) {
470 return N->getKind() == EmitStringInteger;
473 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
476 /// EmitRegisterMatcherNode - This creates a new TargetConstant.
477 class EmitRegisterMatcherNode : public MatcherNode {
478 /// Reg - The def for the register that we're emitting. If this is null, then
479 /// this is a reference to zero_reg.
481 MVT::SimpleValueType VT;
483 EmitRegisterMatcherNode(Record *reg, MVT::SimpleValueType vt)
484 : MatcherNode(EmitRegister), Reg(reg), VT(vt) {}
486 Record *getReg() const { return Reg; }
487 MVT::SimpleValueType getVT() const { return VT; }
489 static inline bool classof(const MatcherNode *N) {
490 return N->getKind() == EmitRegister;
493 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
496 /// EmitConvertToTargetMatcherNode - Emit an operation that reads a specified
497 /// recorded node and converts it from being a ISD::Constant to
498 /// ISD::TargetConstant, likewise for ConstantFP.
499 class EmitConvertToTargetMatcherNode : public MatcherNode {
502 EmitConvertToTargetMatcherNode(unsigned slot)
503 : MatcherNode(EmitConvertToTarget), Slot(slot) {}
505 unsigned getSlot() const { return Slot; }
507 static inline bool classof(const MatcherNode *N) {
508 return N->getKind() == EmitConvertToTarget;
511 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
514 /// EmitMergeInputChainsMatcherNode - Emit a node that merges a list of input
515 /// chains together with a token factor. The list of nodes are the nodes in the
516 /// matched pattern that have chain input/outputs. This node adds all input
517 /// chains of these nodes if they are not themselves a node in the pattern.
518 class EmitMergeInputChainsMatcherNode : public MatcherNode {
519 SmallVector<unsigned, 3> ChainNodes;
521 EmitMergeInputChainsMatcherNode(const unsigned *nodes, unsigned NumNodes)
522 : MatcherNode(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
524 unsigned getNumNodes() const { return ChainNodes.size(); }
526 unsigned getNode(unsigned i) const {
527 assert(i < ChainNodes.size());
528 return ChainNodes[i];
531 static inline bool classof(const MatcherNode *N) {
532 return N->getKind() == EmitMergeInputChains;
535 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
538 /// EmitCopyToRegMatcherNode - Emit a CopyToReg node from a value to a physreg,
539 /// pushing the chain and flag results.
541 class EmitCopyToRegMatcherNode : public MatcherNode {
542 unsigned SrcSlot; // Value to copy into the physreg.
545 EmitCopyToRegMatcherNode(unsigned srcSlot, Record *destPhysReg)
546 : MatcherNode(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
548 unsigned getSrcSlot() const { return SrcSlot; }
549 Record *getDestPhysReg() const { return DestPhysReg; }
551 static inline bool classof(const MatcherNode *N) {
552 return N->getKind() == EmitCopyToReg;
555 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
560 /// EmitNodeXFormMatcherNode - Emit an operation that runs an SDNodeXForm on a
561 /// recorded node and records the result.
562 class EmitNodeXFormMatcherNode : public MatcherNode {
566 EmitNodeXFormMatcherNode(unsigned slot, Record *nodeXForm)
567 : MatcherNode(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
569 unsigned getSlot() const { return Slot; }
570 Record *getNodeXForm() const { return NodeXForm; }
572 static inline bool classof(const MatcherNode *N) {
573 return N->getKind() == EmitNodeXForm;
576 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
579 /// EmitNodeMatcherNode - This signals a successful match and generates a node.
580 class EmitNodeMatcherNode : public MatcherNode {
581 std::string OpcodeName;
582 const SmallVector<MVT::SimpleValueType, 3> VTs;
583 const SmallVector<unsigned, 6> Operands;
584 bool HasChain, HasFlag, HasMemRefs;
586 /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
587 /// If this is a varidic node, this is set to the number of fixed arity
588 /// operands in the root of the pattern. The rest are appended to this node.
589 int NumFixedArityOperands;
591 EmitNodeMatcherNode(const std::string &opcodeName,
592 const MVT::SimpleValueType *vts, unsigned numvts,
593 const unsigned *operands, unsigned numops,
594 bool hasChain, bool hasFlag, bool hasmemrefs,
595 int numfixedarityoperands)
596 : MatcherNode(EmitNode), OpcodeName(opcodeName),
597 VTs(vts, vts+numvts), Operands(operands, operands+numops),
598 HasChain(hasChain), HasFlag(hasFlag), HasMemRefs(hasmemrefs),
599 NumFixedArityOperands(numfixedarityoperands) {}
601 const std::string &getOpcodeName() const { return OpcodeName; }
603 unsigned getNumVTs() const { return VTs.size(); }
604 MVT::SimpleValueType getVT(unsigned i) const {
605 assert(i < VTs.size());
609 unsigned getNumOperands() const { return Operands.size(); }
610 unsigned getOperand(unsigned i) const {
611 assert(i < Operands.size());
615 bool hasChain() const { return HasChain; }
616 bool hasFlag() const { return HasFlag; }
617 bool hasMemRefs() const { return HasMemRefs; }
618 int getNumFixedArityOperands() const { return NumFixedArityOperands; }
620 static inline bool classof(const MatcherNode *N) {
621 return N->getKind() == EmitNode;
624 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
627 /// MarkFlagResultsMatcherNode - This node indicates which non-root nodes in the
628 /// pattern produce flags. This allows CompleteMatchMatcherNode to update them
629 /// with the output flag of the resultant code.
630 class MarkFlagResultsMatcherNode : public MatcherNode {
631 SmallVector<unsigned, 3> FlagResultNodes;
633 MarkFlagResultsMatcherNode(const unsigned *nodes, unsigned NumNodes)
634 : MatcherNode(MarkFlagResults), FlagResultNodes(nodes, nodes+NumNodes) {}
636 unsigned getNumNodes() const { return FlagResultNodes.size(); }
638 unsigned getNode(unsigned i) const {
639 assert(i < FlagResultNodes.size());
640 return FlagResultNodes[i];
643 static inline bool classof(const MatcherNode *N) {
644 return N->getKind() == MarkFlagResults;
647 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
650 /// CompleteMatchMatcherNode - Complete a match by replacing the results of the
651 /// pattern with the newly generated nodes. This also prints a comment
652 /// indicating the source and dest patterns.
653 class CompleteMatchMatcherNode : public MatcherNode {
654 SmallVector<unsigned, 2> Results;
655 const PatternToMatch &Pattern;
657 CompleteMatchMatcherNode(const unsigned *results, unsigned numresults,
658 const PatternToMatch &pattern)
659 : MatcherNode(CompleteMatch), Results(results, results+numresults),
662 unsigned getNumResults() const { return Results.size(); }
663 unsigned getResult(unsigned R) const { return Results[R]; }
664 const PatternToMatch &getPattern() const { return Pattern; }
666 static inline bool classof(const MatcherNode *N) {
667 return N->getKind() == CompleteMatch;
670 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
674 } // end namespace llvm