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 CompleteMatch // Finish a match and update the results.
79 MatcherNode(KindTy K) : Kind(K) {}
81 virtual ~MatcherNode() {}
83 KindTy getKind() const { return Kind; }
85 MatcherNode *getNext() { return Next.get(); }
86 const MatcherNode *getNext() const { return Next.get(); }
87 void setNext(MatcherNode *C) { Next.reset(C); }
89 static inline bool classof(const MatcherNode *) { return true; }
91 virtual void print(raw_ostream &OS, unsigned indent = 0) const = 0;
94 void printNext(raw_ostream &OS, unsigned indent) const;
97 /// PushMatcherNode - This pushes a failure scope on the stack and evaluates
98 /// 'Next'. If 'Next' fails to match, it pops its scope and attempts to
100 class PushMatcherNode : public MatcherNode {
101 OwningPtr<MatcherNode> Failure;
103 PushMatcherNode(MatcherNode *next = 0, MatcherNode *failure = 0)
104 : MatcherNode(Push), Failure(failure) {
108 MatcherNode *getFailure() { return Failure.get(); }
109 const MatcherNode *getFailure() const { return Failure.get(); }
110 void setFailure(MatcherNode *N) { Failure.reset(N); }
112 static inline bool classof(const MatcherNode *N) {
113 return N->getKind() == Push;
116 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
119 /// RecordMatcherNode - Save the current node in the operand list.
120 class RecordMatcherNode : public MatcherNode {
121 /// WhatFor - This is a string indicating why we're recording this. This
122 /// should only be used for comment generation not anything semantic.
125 RecordMatcherNode(const std::string &whatfor)
126 : MatcherNode(RecordNode), WhatFor(whatfor) {}
128 const std::string &getWhatFor() const { return WhatFor; }
130 static inline bool classof(const MatcherNode *N) {
131 return N->getKind() == RecordNode;
134 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
137 /// RecordMemRefMatcherNode - Save the current node's memref.
138 class RecordMemRefMatcherNode : public MatcherNode {
140 RecordMemRefMatcherNode() : MatcherNode(RecordMemRef) {}
142 static inline bool classof(const MatcherNode *N) {
143 return N->getKind() == RecordMemRef;
146 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
150 /// CaptureFlagInputMatcherNode - If the current record has a flag input, record
151 /// it so that it is used as an input to the generated code.
152 class CaptureFlagInputMatcherNode : public MatcherNode {
154 CaptureFlagInputMatcherNode()
155 : MatcherNode(CaptureFlagInput) {}
157 static inline bool classof(const MatcherNode *N) {
158 return N->getKind() == CaptureFlagInput;
161 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
164 /// MoveChildMatcherNode - This tells the interpreter to move into the
165 /// specified child node.
166 class MoveChildMatcherNode : public MatcherNode {
169 MoveChildMatcherNode(unsigned childNo)
170 : MatcherNode(MoveChild), ChildNo(childNo) {}
172 unsigned getChildNo() const { return ChildNo; }
174 static inline bool classof(const MatcherNode *N) {
175 return N->getKind() == MoveChild;
178 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
181 /// MoveParentMatcherNode - This tells the interpreter to move to the parent
182 /// of the current node.
183 class MoveParentMatcherNode : public MatcherNode {
185 MoveParentMatcherNode()
186 : MatcherNode(MoveParent) {}
188 static inline bool classof(const MatcherNode *N) {
189 return N->getKind() == MoveParent;
192 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
195 /// CheckSameMatcherNode - This checks to see if this node is exactly the same
196 /// node as the specified match that was recorded with 'Record'. This is used
197 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
198 class CheckSameMatcherNode : public MatcherNode {
199 unsigned MatchNumber;
201 CheckSameMatcherNode(unsigned matchnumber)
202 : MatcherNode(CheckSame), MatchNumber(matchnumber) {}
204 unsigned getMatchNumber() const { return MatchNumber; }
206 static inline bool classof(const MatcherNode *N) {
207 return N->getKind() == CheckSame;
210 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
213 /// CheckPatternPredicateMatcherNode - This checks the target-specific predicate
214 /// to see if the entire pattern is capable of matching. This predicate does
215 /// not take a node as input. This is used for subtarget feature checks etc.
216 class CheckPatternPredicateMatcherNode : public MatcherNode {
217 std::string Predicate;
219 CheckPatternPredicateMatcherNode(StringRef predicate)
220 : MatcherNode(CheckPatternPredicate), Predicate(predicate) {}
222 StringRef getPredicate() const { return Predicate; }
224 static inline bool classof(const MatcherNode *N) {
225 return N->getKind() == CheckPatternPredicate;
228 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
231 /// CheckPredicateMatcherNode - This checks the target-specific predicate to
232 /// see if the node is acceptable.
233 class CheckPredicateMatcherNode : public MatcherNode {
236 CheckPredicateMatcherNode(StringRef predname)
237 : MatcherNode(CheckPredicate), PredName(predname) {}
239 StringRef getPredicateName() const { return PredName; }
241 static inline bool classof(const MatcherNode *N) {
242 return N->getKind() == CheckPredicate;
245 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
249 /// CheckOpcodeMatcherNode - This checks to see if the current node has the
250 /// specified opcode, if not it fails to match.
251 class CheckOpcodeMatcherNode : public MatcherNode {
252 StringRef OpcodeName;
254 CheckOpcodeMatcherNode(StringRef opcodename)
255 : MatcherNode(CheckOpcode), OpcodeName(opcodename) {}
257 StringRef getOpcodeName() const { return OpcodeName; }
259 static inline bool classof(const MatcherNode *N) {
260 return N->getKind() == CheckOpcode;
263 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
266 /// CheckMultiOpcodeMatcherNode - This checks to see if the current node has one
267 /// of the specified opcode, if not it fails to match.
268 class CheckMultiOpcodeMatcherNode : public MatcherNode {
269 SmallVector<StringRef, 4> OpcodeNames;
271 CheckMultiOpcodeMatcherNode(const StringRef *opcodes, unsigned numops)
272 : MatcherNode(CheckMultiOpcode), OpcodeNames(opcodes, opcodes+numops) {}
274 unsigned getNumOpcodeNames() const { return OpcodeNames.size(); }
275 StringRef getOpcodeName(unsigned i) const { return OpcodeNames[i]; }
277 static inline bool classof(const MatcherNode *N) {
278 return N->getKind() == CheckMultiOpcode;
281 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
286 /// CheckTypeMatcherNode - This checks to see if the current node has the
287 /// specified type, if not it fails to match.
288 class CheckTypeMatcherNode : public MatcherNode {
289 MVT::SimpleValueType Type;
291 CheckTypeMatcherNode(MVT::SimpleValueType type)
292 : MatcherNode(CheckType), Type(type) {}
294 MVT::SimpleValueType getType() const { return Type; }
296 static inline bool classof(const MatcherNode *N) {
297 return N->getKind() == CheckType;
300 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
303 /// CheckIntegerMatcherNode - This checks to see if the current node is a
304 /// ConstantSDNode with the specified integer value, if not it fails to match.
305 class CheckIntegerMatcherNode : public MatcherNode {
308 CheckIntegerMatcherNode(int64_t value)
309 : MatcherNode(CheckInteger), Value(value) {}
311 int64_t getValue() const { return Value; }
313 static inline bool classof(const MatcherNode *N) {
314 return N->getKind() == CheckInteger;
317 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
320 /// CheckCondCodeMatcherNode - This checks to see if the current node is a
321 /// CondCodeSDNode with the specified condition, if not it fails to match.
322 class CheckCondCodeMatcherNode : public MatcherNode {
323 StringRef CondCodeName;
325 CheckCondCodeMatcherNode(StringRef condcodename)
326 : MatcherNode(CheckCondCode), CondCodeName(condcodename) {}
328 StringRef getCondCodeName() const { return CondCodeName; }
330 static inline bool classof(const MatcherNode *N) {
331 return N->getKind() == CheckCondCode;
334 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
337 /// CheckValueTypeMatcherNode - This checks to see if the current node is a
338 /// VTSDNode with the specified type, if not it fails to match.
339 class CheckValueTypeMatcherNode : public MatcherNode {
342 CheckValueTypeMatcherNode(StringRef type_name)
343 : MatcherNode(CheckValueType), TypeName(type_name) {}
345 StringRef getTypeName() const { return TypeName; }
347 static inline bool classof(const MatcherNode *N) {
348 return N->getKind() == CheckValueType;
351 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
356 /// CheckComplexPatMatcherNode - This node runs the specified ComplexPattern on
357 /// the current node.
358 class CheckComplexPatMatcherNode : public MatcherNode {
359 const ComplexPattern &Pattern;
361 CheckComplexPatMatcherNode(const ComplexPattern &pattern)
362 : MatcherNode(CheckComplexPat), Pattern(pattern) {}
364 const ComplexPattern &getPattern() const { return Pattern; }
366 static inline bool classof(const MatcherNode *N) {
367 return N->getKind() == CheckComplexPat;
370 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
373 /// CheckAndImmMatcherNode - This checks to see if the current node is an 'and'
374 /// with something equivalent to the specified immediate.
375 class CheckAndImmMatcherNode : public MatcherNode {
378 CheckAndImmMatcherNode(int64_t value)
379 : MatcherNode(CheckAndImm), Value(value) {}
381 int64_t getValue() const { return Value; }
383 static inline bool classof(const MatcherNode *N) {
384 return N->getKind() == CheckAndImm;
387 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
390 /// CheckOrImmMatcherNode - This checks to see if the current node is an 'and'
391 /// with something equivalent to the specified immediate.
392 class CheckOrImmMatcherNode : public MatcherNode {
395 CheckOrImmMatcherNode(int64_t value)
396 : MatcherNode(CheckOrImm), Value(value) {}
398 int64_t getValue() const { return Value; }
400 static inline bool classof(const MatcherNode *N) {
401 return N->getKind() == CheckOrImm;
404 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
407 /// CheckFoldableChainNodeMatcherNode - This checks to see if the current node
408 /// (which defines a chain operand) is safe to fold into a larger pattern.
409 class CheckFoldableChainNodeMatcherNode : public MatcherNode {
411 CheckFoldableChainNodeMatcherNode()
412 : MatcherNode(CheckFoldableChainNode) {}
414 static inline bool classof(const MatcherNode *N) {
415 return N->getKind() == CheckFoldableChainNode;
418 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
421 /// CheckChainCompatibleMatcherNode - Verify that the current node's chain
422 /// operand is 'compatible' with the specified recorded node's.
423 class CheckChainCompatibleMatcherNode : public MatcherNode {
426 CheckChainCompatibleMatcherNode(unsigned previousop)
427 : MatcherNode(CheckChainCompatible), PreviousOp(previousop) {}
429 unsigned getPreviousOp() const { return PreviousOp; }
431 static inline bool classof(const MatcherNode *N) {
432 return N->getKind() == CheckChainCompatible;
435 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
438 /// EmitIntegerMatcherNode - This creates a new TargetConstant.
439 class EmitIntegerMatcherNode : public MatcherNode {
441 MVT::SimpleValueType VT;
443 EmitIntegerMatcherNode(int64_t val, MVT::SimpleValueType vt)
444 : MatcherNode(EmitInteger), Val(val), VT(vt) {}
446 int64_t getValue() const { return Val; }
447 MVT::SimpleValueType getVT() const { return VT; }
449 static inline bool classof(const MatcherNode *N) {
450 return N->getKind() == EmitInteger;
453 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
456 /// EmitStringIntegerMatcherNode - A target constant whose value is represented
458 class EmitStringIntegerMatcherNode : public MatcherNode {
460 MVT::SimpleValueType VT;
462 EmitStringIntegerMatcherNode(const std::string &val, MVT::SimpleValueType vt)
463 : MatcherNode(EmitStringInteger), Val(val), VT(vt) {}
465 const std::string &getValue() const { return Val; }
466 MVT::SimpleValueType getVT() const { return VT; }
468 static inline bool classof(const MatcherNode *N) {
469 return N->getKind() == EmitStringInteger;
472 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
475 /// EmitRegisterMatcherNode - This creates a new TargetConstant.
476 class EmitRegisterMatcherNode : public MatcherNode {
477 /// Reg - The def for the register that we're emitting. If this is null, then
478 /// this is a reference to zero_reg.
480 MVT::SimpleValueType VT;
482 EmitRegisterMatcherNode(Record *reg, MVT::SimpleValueType vt)
483 : MatcherNode(EmitRegister), Reg(reg), VT(vt) {}
485 Record *getReg() const { return Reg; }
486 MVT::SimpleValueType getVT() const { return VT; }
488 static inline bool classof(const MatcherNode *N) {
489 return N->getKind() == EmitRegister;
492 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
495 /// EmitConvertToTargetMatcherNode - Emit an operation that reads a specified
496 /// recorded node and converts it from being a ISD::Constant to
497 /// ISD::TargetConstant, likewise for ConstantFP.
498 class EmitConvertToTargetMatcherNode : public MatcherNode {
501 EmitConvertToTargetMatcherNode(unsigned slot)
502 : MatcherNode(EmitConvertToTarget), Slot(slot) {}
504 unsigned getSlot() const { return Slot; }
506 static inline bool classof(const MatcherNode *N) {
507 return N->getKind() == EmitConvertToTarget;
510 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
513 /// EmitMergeInputChainsMatcherNode - Emit a node that merges a list of input
514 /// chains together with a token factor. The list of nodes are the nodes in the
515 /// matched pattern that have chain input/outputs. This node adds all input
516 /// chains of these nodes if they are not themselves a node in the pattern.
517 class EmitMergeInputChainsMatcherNode : public MatcherNode {
518 SmallVector<unsigned, 3> ChainNodes;
520 EmitMergeInputChainsMatcherNode(const unsigned *nodes, unsigned NumNodes)
521 : MatcherNode(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
523 unsigned getNumNodes() const { return ChainNodes.size(); }
525 unsigned getNode(unsigned i) const {
526 assert(i < ChainNodes.size());
527 return ChainNodes[i];
530 static inline bool classof(const MatcherNode *N) {
531 return N->getKind() == EmitMergeInputChains;
534 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
537 /// EmitCopyToRegMatcherNode - Emit a CopyToReg node from a value to a physreg,
538 /// pushing the chain and flag results.
540 class EmitCopyToRegMatcherNode : public MatcherNode {
541 unsigned SrcSlot; // Value to copy into the physreg.
544 EmitCopyToRegMatcherNode(unsigned srcSlot, Record *destPhysReg)
545 : MatcherNode(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
547 unsigned getSrcSlot() const { return SrcSlot; }
548 Record *getDestPhysReg() const { return DestPhysReg; }
550 static inline bool classof(const MatcherNode *N) {
551 return N->getKind() == EmitCopyToReg;
554 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
559 /// EmitNodeXFormMatcherNode - Emit an operation that runs an SDNodeXForm on a
560 /// recorded node and records the result.
561 class EmitNodeXFormMatcherNode : public MatcherNode {
565 EmitNodeXFormMatcherNode(unsigned slot, Record *nodeXForm)
566 : MatcherNode(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
568 unsigned getSlot() const { return Slot; }
569 Record *getNodeXForm() const { return NodeXForm; }
571 static inline bool classof(const MatcherNode *N) {
572 return N->getKind() == EmitNodeXForm;
575 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
578 /// EmitNodeMatcherNode - This signals a successful match and generates a node.
579 class EmitNodeMatcherNode : public MatcherNode {
580 std::string OpcodeName;
581 const SmallVector<MVT::SimpleValueType, 3> VTs;
582 const SmallVector<unsigned, 6> Operands;
583 bool HasChain, HasFlag, HasMemRefs;
585 /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
586 /// If this is a varidic node, this is set to the number of fixed arity
587 /// operands in the root of the pattern. The rest are appended to this node.
588 int NumFixedArityOperands;
590 EmitNodeMatcherNode(const std::string &opcodeName,
591 const MVT::SimpleValueType *vts, unsigned numvts,
592 const unsigned *operands, unsigned numops,
593 bool hasChain, bool hasFlag, bool hasmemrefs,
594 int numfixedarityoperands)
595 : MatcherNode(EmitNode), OpcodeName(opcodeName),
596 VTs(vts, vts+numvts), Operands(operands, operands+numops),
597 HasChain(hasChain), HasFlag(hasFlag), HasMemRefs(hasmemrefs),
598 NumFixedArityOperands(numfixedarityoperands) {}
600 const std::string &getOpcodeName() const { return OpcodeName; }
602 unsigned getNumVTs() const { return VTs.size(); }
603 MVT::SimpleValueType getVT(unsigned i) const {
604 assert(i < VTs.size());
608 unsigned getNumOperands() const { return Operands.size(); }
609 unsigned getOperand(unsigned i) const {
610 assert(i < Operands.size());
614 bool hasChain() const { return HasChain; }
615 bool hasFlag() const { return HasFlag; }
616 bool hasMemRefs() const { return HasMemRefs; }
617 int getNumFixedArityOperands() const { return NumFixedArityOperands; }
619 static inline bool classof(const MatcherNode *N) {
620 return N->getKind() == EmitNode;
623 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
626 /// CompleteMatchMatcherNode - Complete a match by replacing the results of the
627 /// pattern with the newly generated nodes. This also prints a comment
628 /// indicating the source and dest patterns.
629 class CompleteMatchMatcherNode : public MatcherNode {
630 SmallVector<unsigned, 2> Results;
631 const PatternToMatch &Pattern;
633 CompleteMatchMatcherNode(const unsigned *results, unsigned numresults,
634 const PatternToMatch &pattern)
635 : MatcherNode(CompleteMatch), Results(results, results+numresults),
638 unsigned getNumResults() const { return Results.size(); }
639 unsigned getResult(unsigned R) const { return Results[R]; }
640 const PatternToMatch &getPattern() const { return Pattern; }
642 static inline bool classof(const MatcherNode *N) {
643 return N->getKind() == CompleteMatch;
646 virtual void print(raw_ostream &OS, unsigned indent = 0) const;
650 } // end namespace llvm