Check in the first big step of rewriting DAGISelEmitter to
produce a table based matcher instead of gobs of C++ Code.
Though it's not done yet, the shrinkage seems promising,
the table for the X86 ISel is 75K and still has a lot of
optimization to come (compare to the ~1.5M of .o generated
the old way, much of which will go away).
The code is currently disabled by default (the #if 0 in
DAGISelEmitter.cpp). When enabled it generates a dead
SelectCode2 function in the DAGISel Header which will
eventually replace SelectCode.
There is still a lot of stuff left to do, which are
documented with a trail of FIXMEs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96215 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/utils/TableGen/CMakeLists.txt b/utils/TableGen/CMakeLists.txt
index f344b28..a2678a2 100644
--- a/utils/TableGen/CMakeLists.txt
+++ b/utils/TableGen/CMakeLists.txt
@@ -9,6 +9,9 @@
CodeGenInstruction.cpp
CodeGenTarget.cpp
DAGISelEmitter.cpp
+ DAGISelMatcherEmitter.cpp
+ DAGISelMatcherGen.cpp
+ DAGISelMatcher.cpp
DisassemblerEmitter.cpp
EDEmitter.cpp
FastISelEmitter.cpp
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index e8aa164..0eb06bb 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -12,6 +12,7 @@
//===----------------------------------------------------------------------===//
#include "DAGISelEmitter.h"
+#include "DAGISelMatcher.h"
#include "Record.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CommandLine.h"
@@ -1609,7 +1610,7 @@
void DAGISelEmitter::EmitInstructionSelector(raw_ostream &OS) {
const CodeGenTarget &Target = CGP.getTargetInfo();
-
+
// Get the namespace to insert instructions into.
std::string InstNS = Target.getInstNamespace();
if (!InstNS.empty()) InstNS += "::";
@@ -1621,7 +1622,6 @@
for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
E = CGP.ptm_end(); I != E; ++I) {
const PatternToMatch &Pattern = *I;
-
TreePatternNode *Node = Pattern.getSrcPattern();
if (!Node->isLeaf()) {
PatternsByOpcode[getOpcodeName(Node->getOperator(), CGP)].
@@ -2011,4 +2011,26 @@
// definitions. Emit the resultant instruction selector.
EmitInstructionSelector(OS);
+#if 0
+ MatcherNode *Matcher = 0;
+ // Walk the patterns backwards, building a matcher for each and adding it to
+ // the matcher for the whole target.
+ for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
+ E = CGP.ptm_end(); I != E;) {
+ const PatternToMatch &Pattern = *--E;
+ MatcherNode *N = ConvertPatternToMatcher(Pattern, CGP);
+
+ if (Matcher == 0)
+ Matcher = N;
+ else
+ Matcher = new PushMatcherNode(N, Matcher);
+ }
+
+
+ EmitMatcherTable(Matcher, OS);
+
+
+ //Matcher->dump();
+ delete Matcher;
+#endif
}
diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp
new file mode 100644
index 0000000..1363aa3
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcher.cpp
@@ -0,0 +1,108 @@
+//===- DAGISelMatcher.cpp - Representation of DAG pattern matcher ---------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DAGISelMatcher.h"
+#include "CodeGenDAGPatterns.h"
+#include "CodeGenTarget.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+void MatcherNode::dump() const {
+ print(errs());
+}
+
+void EmitNodeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "EmitNode: Src = " << *Pattern.getSrcPattern() << "\n";
+ OS.indent(indent) << "EmitNode: Dst = " << *Pattern.getDstPattern() << "\n";
+}
+
+void MatcherNodeWithChild::printChild(raw_ostream &OS, unsigned indent) const {
+ if (Child)
+ return Child->print(OS, indent);
+ OS.indent(indent) << "<null child>\n";
+}
+
+
+void PushMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "Push\n";
+ printChild(OS, indent+2);
+ Failure->print(OS, indent);
+}
+
+void RecordMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "Record\n";
+ printChild(OS, indent);
+}
+
+void MoveChildMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "MoveChild " << ChildNo << '\n';
+ printChild(OS, indent);
+}
+
+void MoveParentMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "MoveParent\n";
+ printChild(OS, indent);
+}
+
+void CheckSameMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckSame " << MatchNumber << '\n';
+ printChild(OS, indent);
+}
+
+void CheckPatternPredicateMatcherNode::
+print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n';
+ printChild(OS, indent);
+}
+
+void CheckPredicateMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckPredicate " << PredName << '\n';
+ printChild(OS, indent);
+}
+
+void CheckOpcodeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckOpcode " << OpcodeName << '\n';
+ printChild(OS, indent);
+}
+
+void CheckTypeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckType " << getEnumName(Type) << '\n';
+ printChild(OS, indent);
+}
+
+void CheckIntegerMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckInteger " << Value << '\n';
+ printChild(OS, indent);
+}
+
+void CheckCondCodeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n';
+ printChild(OS, indent);
+}
+
+void CheckValueTypeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n';
+ printChild(OS, indent);
+}
+
+void CheckComplexPatMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';
+ printChild(OS, indent);
+}
+
+void CheckAndImmMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckAndImm " << Value << '\n';
+ printChild(OS, indent);
+}
+
+void CheckOrImmMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+ OS.indent(indent) << "CheckOrImm " << Value << '\n';
+ printChild(OS, indent);
+}
+
diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h
new file mode 100644
index 0000000..72bdb7b
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcher.h
@@ -0,0 +1,362 @@
+//===- DAGISelMatcher.h - Representation of DAG pattern matcher -----------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TBLGEN_DAGISELMATCHER_H
+#define TBLGEN_DAGISELMATCHER_H
+
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/ValueTypes.h"
+
+namespace llvm {
+ class CodeGenDAGPatterns;
+ class MatcherNode;
+ class PatternToMatch;
+ class raw_ostream;
+ class ComplexPattern;
+
+MatcherNode *ConvertPatternToMatcher(const PatternToMatch &Pattern,
+ const CodeGenDAGPatterns &CGP);
+
+void EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &OS);
+
+
+/// MatcherNode - Base class for all the the DAG ISel Matcher representation
+/// nodes.
+class MatcherNode {
+public:
+ enum KindTy {
+ EmitNode,
+ Push, // [Push, Dest0, Dest1, Dest2, Dest3]
+ Record, // [Record]
+ MoveChild, // [MoveChild, Child#]
+ MoveParent, // [MoveParent]
+
+ CheckSame, // [CheckSame, N] Fail if not same as prev match.
+ CheckPatternPredicate,
+ CheckPredicate, // [CheckPredicate, P] Fail if predicate fails.
+ CheckOpcode, // [CheckOpcode, Opcode] Fail if not opcode.
+ CheckType, // [CheckType, MVT] Fail if not correct type.
+ CheckInteger, // [CheckInteger, int0,int1,int2,...int7] Fail if wrong val.
+ CheckCondCode, // [CheckCondCode, CondCode] Fail if not condcode.
+ CheckValueType,
+ CheckComplexPat,
+ CheckAndImm,
+ CheckOrImm
+ };
+ const KindTy Kind;
+
+protected:
+ MatcherNode(KindTy K) : Kind(K) {}
+public:
+ virtual ~MatcherNode() {}
+
+ KindTy getKind() const { return Kind; }
+
+
+ static inline bool classof(const MatcherNode *) { return true; }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const = 0;
+ void dump() const;
+};
+
+/// EmitNodeMatcherNode - This signals a successful match and generates a node.
+class EmitNodeMatcherNode : public MatcherNode {
+ const PatternToMatch &Pattern;
+public:
+ EmitNodeMatcherNode(const PatternToMatch &pattern)
+ : MatcherNode(EmitNode), Pattern(pattern) {}
+
+ const PatternToMatch &getPattern() const { return Pattern; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == EmitNode;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// MatcherNodeWithChild - Every node accept the final accept state has a child
+/// that is executed after the node runs. This class captures this commonality.
+class MatcherNodeWithChild : public MatcherNode {
+ OwningPtr<MatcherNode> Child;
+public:
+ MatcherNodeWithChild(KindTy K) : MatcherNode(K) {}
+
+ MatcherNode *getChild() { return Child.get(); }
+ const MatcherNode *getChild() const { return Child.get(); }
+ void setChild(MatcherNode *C) { Child.reset(C); }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() != EmitNode;
+ }
+
+protected:
+ void printChild(raw_ostream &OS, unsigned indent) const;
+};
+
+/// PushMatcherNode - This pushes a failure scope on the stack and evaluates
+/// 'child'. If 'child' fails to match, it pops its scope and attempts to
+/// match 'Failure'.
+class PushMatcherNode : public MatcherNodeWithChild {
+ OwningPtr<MatcherNode> Failure;
+public:
+ PushMatcherNode(MatcherNode *child = 0, MatcherNode *failure = 0)
+ : MatcherNodeWithChild(Push), Failure(failure) {
+ setChild(child);
+ }
+
+ MatcherNode *getFailure() { return Failure.get(); }
+ const MatcherNode *getFailure() const { return Failure.get(); }
+ void setFailure(MatcherNode *N) { Failure.reset(N); }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == Push;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// RecordMatcherNode - Save the current node in the operand list.
+class RecordMatcherNode : public MatcherNodeWithChild {
+public:
+ RecordMatcherNode() : MatcherNodeWithChild(Record) {}
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == Record;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// MoveChildMatcherNode - This tells the interpreter to move into the
+/// specified child node.
+class MoveChildMatcherNode : public MatcherNodeWithChild {
+ unsigned ChildNo;
+public:
+ MoveChildMatcherNode(unsigned childNo)
+ : MatcherNodeWithChild(MoveChild), ChildNo(childNo) {}
+
+ unsigned getChildNo() const { return ChildNo; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == MoveChild;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// MoveParentMatcherNode - This tells the interpreter to move to the parent
+/// of the current node.
+class MoveParentMatcherNode : public MatcherNodeWithChild {
+public:
+ MoveParentMatcherNode()
+ : MatcherNodeWithChild(MoveParent) {}
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == MoveParent;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckSameMatcherNode - This checks to see if this node is exactly the same
+/// node as the specified match that was recorded with 'Record'. This is used
+/// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
+class CheckSameMatcherNode : public MatcherNodeWithChild {
+ unsigned MatchNumber;
+public:
+ CheckSameMatcherNode(unsigned matchnumber)
+ : MatcherNodeWithChild(CheckSame), MatchNumber(matchnumber) {}
+
+ unsigned getMatchNumber() const { return MatchNumber; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckSame;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckPatternPredicateMatcherNode - This checks the target-specific predicate
+/// to see if the entire pattern is capable of matching. This predicate does
+/// not take a node as input. This is used for subtarget feature checks etc.
+class CheckPatternPredicateMatcherNode : public MatcherNodeWithChild {
+ std::string Predicate;
+public:
+ CheckPatternPredicateMatcherNode(StringRef predicate)
+ : MatcherNodeWithChild(CheckPatternPredicate), Predicate(predicate) {}
+
+ StringRef getPredicate() const { return Predicate; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckPatternPredicate;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckPredicateMatcherNode - This checks the target-specific predicate to
+/// see if the node is acceptable.
+class CheckPredicateMatcherNode : public MatcherNodeWithChild {
+ StringRef PredName;
+public:
+ CheckPredicateMatcherNode(StringRef predname)
+ : MatcherNodeWithChild(CheckPredicate), PredName(predname) {}
+
+ StringRef getPredicateName() const { return PredName; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckPredicate;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+
+/// CheckOpcodeMatcherNode - This checks to see if the current node has the
+/// specified opcode, if not it fails to match.
+class CheckOpcodeMatcherNode : public MatcherNodeWithChild {
+ StringRef OpcodeName;
+public:
+ CheckOpcodeMatcherNode(StringRef opcodename)
+ : MatcherNodeWithChild(CheckOpcode), OpcodeName(opcodename) {}
+
+ StringRef getOpcodeName() const { return OpcodeName; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckOpcode;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckTypeMatcherNode - This checks to see if the current node has the
+/// specified type, if not it fails to match.
+class CheckTypeMatcherNode : public MatcherNodeWithChild {
+ MVT::SimpleValueType Type;
+public:
+ CheckTypeMatcherNode(MVT::SimpleValueType type)
+ : MatcherNodeWithChild(CheckType), Type(type) {}
+
+ MVT::SimpleValueType getType() const { return Type; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckType;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckIntegerMatcherNode - This checks to see if the current node is a
+/// ConstantSDNode with the specified integer value, if not it fails to match.
+class CheckIntegerMatcherNode : public MatcherNodeWithChild {
+ int64_t Value;
+public:
+ CheckIntegerMatcherNode(int64_t value)
+ : MatcherNodeWithChild(CheckInteger), Value(value) {}
+
+ int64_t getValue() const { return Value; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckInteger;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckCondCodeMatcherNode - This checks to see if the current node is a
+/// CondCodeSDNode with the specified condition, if not it fails to match.
+class CheckCondCodeMatcherNode : public MatcherNodeWithChild {
+ StringRef CondCodeName;
+public:
+ CheckCondCodeMatcherNode(StringRef condcodename)
+ : MatcherNodeWithChild(CheckCondCode), CondCodeName(condcodename) {}
+
+ StringRef getCondCodeName() const { return CondCodeName; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckCondCode;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckValueTypeMatcherNode - This checks to see if the current node is a
+/// VTSDNode with the specified type, if not it fails to match.
+class CheckValueTypeMatcherNode : public MatcherNodeWithChild {
+ StringRef TypeName;
+public:
+ CheckValueTypeMatcherNode(StringRef type_name)
+ : MatcherNodeWithChild(CheckValueType), TypeName(type_name) {}
+
+ StringRef getTypeName() const { return TypeName; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckValueType;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+
+
+/// CheckComplexPatMatcherNode - This node runs the specified ComplexPattern on
+/// the current node.
+class CheckComplexPatMatcherNode : public MatcherNodeWithChild {
+ const ComplexPattern &Pattern;
+public:
+ CheckComplexPatMatcherNode(const ComplexPattern &pattern)
+ : MatcherNodeWithChild(CheckComplexPat), Pattern(pattern) {}
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckComplexPat;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckAndImmMatcherNode - This checks to see if the current node is an 'and'
+/// with something equivalent to the specified immediate.
+class CheckAndImmMatcherNode : public MatcherNodeWithChild {
+ int64_t Value;
+public:
+ CheckAndImmMatcherNode(int64_t value)
+ : MatcherNodeWithChild(CheckAndImm), Value(value) {}
+
+ int64_t getValue() const { return Value; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckAndImm;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckOrImmMatcherNode - This checks to see if the current node is an 'and'
+/// with something equivalent to the specified immediate.
+class CheckOrImmMatcherNode : public MatcherNodeWithChild {
+ int64_t Value;
+public:
+ CheckOrImmMatcherNode(int64_t value)
+ : MatcherNodeWithChild(CheckOrImm), Value(value) {}
+
+ int64_t getValue() const { return Value; }
+
+ static inline bool classof(const MatcherNode *N) {
+ return N->getKind() == CheckOrImm;
+ }
+
+ virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+
+} // end namespace llvm
+
+#endif
diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp
new file mode 100644
index 0000000..1a41713
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -0,0 +1,217 @@
+//===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains code to generate C++ code a matcher.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DAGISelMatcher.h"
+#include "CodeGenDAGPatterns.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/FormattedStream.h"
+using namespace llvm;
+
+namespace {
+enum {
+ CommentIndent = 25
+};
+}
+
+static unsigned EmitMatcherAndChildren(const MatcherNode *N,
+ formatted_raw_ostream &FOS,
+ unsigned Indent);
+
+/// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this
+/// fits in 1, 2, 4, or 8 sign extended bytes.
+static char ClassifyInt(int64_t Val) {
+ if (Val == int8_t(Val)) return '1';
+ if (Val == int16_t(Val)) return '2';
+ if (Val == int32_t(Val)) return '4';
+ return '8';
+}
+
+/// EmitInt - Emit the specified integer, returning the number of bytes emitted.
+static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) {
+ unsigned BytesEmitted = 1;
+ OS << (int)(unsigned char)Val << ", ";
+ if (Val == int8_t(Val)) {
+ OS << "\n";
+ return BytesEmitted;
+ }
+
+ OS << (int)(unsigned char)(Val >> 8) << ", ";
+ ++BytesEmitted;
+
+ if (Val != int16_t(Val)) {
+ OS << (int)(unsigned char)(Val >> 16) << ','
+ << (int)(unsigned char)(Val >> 24) << ',';
+ BytesEmitted += 2;
+
+ if (Val != int32_t(Val)) {
+ OS << (int)(unsigned char)(Val >> 32) << ','
+ << (int)(unsigned char)(Val >> 40) << ','
+ << (int)(unsigned char)(Val >> 48) << ','
+ << (int)(unsigned char)(Val >> 56) << ',';
+ BytesEmitted += 4;
+ }
+ }
+
+ OS.PadToColumn(CommentIndent) << "// " << Val << '\n';
+ return BytesEmitted;
+}
+
+/// EmitMatcherOpcodes - Emit bytes for the specified matcher and return
+/// the number of bytes emitted.
+static unsigned EmitMatcher(const MatcherNode *N, formatted_raw_ostream &OS,
+ unsigned Indent) {
+ OS.PadToColumn(Indent*2);
+
+ switch (N->getKind()) {
+ case MatcherNode::Push: assert(0 && "Should be handled by caller");
+ case MatcherNode::EmitNode:
+ OS << "OPC_Emit, /*XXX*/";
+ OS.PadToColumn(CommentIndent) << "// Src: "
+ << *cast<EmitNodeMatcherNode>(N)->getPattern().getSrcPattern() << '\n';
+ OS.PadToColumn(CommentIndent) << "// Dst: "
+ << *cast<EmitNodeMatcherNode>(N)->getPattern().getDstPattern() << '\n';
+ return 1;
+ case MatcherNode::Record:
+ OS << "OPC_Record,\n";
+ return 1;
+ case MatcherNode::MoveChild:
+ OS << "OPC_MoveChild, "
+ << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n";
+ return 2;
+
+ case MatcherNode::MoveParent:
+ OS << "OPC_MoveParent,\n";
+ return 1;
+
+ case MatcherNode::CheckSame:
+ OS << "OPC_CheckSame, "
+ << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n";
+ return 2;
+
+ case MatcherNode::CheckPatternPredicate:
+ OS << "OPC_CheckPatternPredicate, /*XXX*/0,";
+ OS.PadToColumn(CommentIndent) << "// "
+ << cast<CheckPatternPredicateMatcherNode>(N)->getPredicate() << '\n';
+ return 2;
+
+ case MatcherNode::CheckPredicate:
+ OS << "OPC_CheckPredicate, /*XXX*/0,";
+ OS.PadToColumn(CommentIndent) << "// "
+ << cast<CheckPredicateMatcherNode>(N)->getPredicateName() << '\n';
+ return 2;
+
+ case MatcherNode::CheckOpcode:
+ OS << "OPC_CheckOpcode, "
+ << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n";
+ return 2;
+
+ case MatcherNode::CheckType:
+ OS << "OPC_CheckType, "
+ << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n";
+ return 2;
+
+ case MatcherNode::CheckInteger: {
+ int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue();
+ OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", ";
+ return EmitInt(Val, OS)+1;
+ }
+ case MatcherNode::CheckCondCode:
+ OS << "OPC_CheckCondCode, ISD::"
+ << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n";
+ return 2;
+
+ case MatcherNode::CheckValueType:
+ OS << "OPC_CheckValueType, MVT::"
+ << cast<CheckValueTypeMatcherNode>(N)->getTypeName() << ",\n";
+ return 2;
+
+ case MatcherNode::CheckComplexPat:
+ OS << "OPC_CheckComplexPat, 0/*XXX*/,\n";
+ return 2;
+
+ case MatcherNode::CheckAndImm: {
+ int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue();
+ OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", ";
+ return EmitInt(Val, OS)+1;
+ }
+
+ case MatcherNode::CheckOrImm: {
+ int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue();
+ OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", ";
+ return EmitInt(Val, OS)+1;
+ }
+ }
+ assert(0 && "Unreachable");
+ return 0;
+}
+
+/// EmitMatcherAndChildren - Emit the bytes for the specified matcher subtree.
+static unsigned EmitMatcherAndChildren(const MatcherNode *N,
+ formatted_raw_ostream &OS,
+ unsigned Indent) {
+ unsigned Size = 0;
+ while (1) {
+ // Push is a special case since it is binary.
+ if (const PushMatcherNode *PMN = dyn_cast<PushMatcherNode>(N)) {
+ // We need to encode the child and the offset of the failure code before
+ // emitting either of them. Handle this by buffering the output into a
+ // string while we get the size.
+ SmallString<128> TmpBuf;
+ unsigned ChildSize;
+ {
+ raw_svector_ostream OS(TmpBuf);
+ formatted_raw_ostream FOS(OS);
+ ChildSize =
+ EmitMatcherAndChildren(cast<PushMatcherNode>(N)->getChild(), FOS,
+ Indent+1);
+ }
+
+ if (ChildSize > 255) {
+ errs() <<
+ "Tblgen internal error: can't handle predicate this complex yet\n";
+ exit(1);
+ }
+
+ OS.PadToColumn(Indent*2);
+ OS << "OPC_Push, " << ChildSize << ",\n";
+ OS << TmpBuf.str();
+
+ Size += 2 + ChildSize;
+
+ N = PMN->getFailure();
+ continue;
+ }
+
+ Size += EmitMatcher(N, OS, Indent);
+
+ // If there are children of this node, iterate to them, otherwise we're
+ // done.
+ if (const MatcherNodeWithChild *MNWC = dyn_cast<MatcherNodeWithChild>(N))
+ N = MNWC->getChild();
+ else
+ return Size;
+ }
+}
+
+void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) {
+ formatted_raw_ostream OS(O);
+
+ OS << "// The main instruction selector code.\n";
+ OS << "SDNode *SelectCode2(SDNode *N) {\n";
+
+ OS << " static const unsigned char MatcherTable[] = {\n";
+ unsigned TotalSize = EmitMatcherAndChildren(Matcher, OS, 2);
+ OS << " 0\n }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
+ OS << " return SelectCodeCommon(N, MatcherTable, sizeof(MatcherTable));\n}\n";
+}
diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp
new file mode 100644
index 0000000..afa2587
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcherGen.cpp
@@ -0,0 +1,287 @@
+//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DAGISelMatcher.h"
+#include "CodeGenDAGPatterns.h"
+#include "Record.h"
+#include "llvm/ADT/StringMap.h"
+using namespace llvm;
+
+namespace {
+ class MatcherGen {
+ const PatternToMatch &Pattern;
+ const CodeGenDAGPatterns &CGP;
+
+ /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
+ /// out with all of the types removed. This allows us to insert type checks
+ /// as we scan the tree.
+ TreePatternNode *PatWithNoTypes;
+
+ /// VariableMap - A map from variable names ('$dst') to the recorded operand
+ /// number that they were captured as. These are biased by 1 to make
+ /// insertion easier.
+ StringMap<unsigned> VariableMap;
+ unsigned NextRecordedOperandNo;
+
+ MatcherNodeWithChild *Matcher;
+ MatcherNodeWithChild *CurPredicate;
+ public:
+ MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);
+
+ ~MatcherGen() {
+ delete PatWithNoTypes;
+ }
+
+ void EmitMatcherCode();
+
+ MatcherNodeWithChild *GetMatcher() const { return Matcher; }
+ MatcherNodeWithChild *GetCurPredicate() const { return CurPredicate; }
+ private:
+ void AddMatcherNode(MatcherNodeWithChild *NewNode);
+ void InferPossibleTypes();
+ void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes);
+ void EmitLeafMatchCode(const TreePatternNode *N);
+ void EmitOperatorMatchCode(const TreePatternNode *N,
+ TreePatternNode *NodeNoTypes);
+ };
+
+} // end anon namespace.
+
+MatcherGen::MatcherGen(const PatternToMatch &pattern,
+ const CodeGenDAGPatterns &cgp)
+: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0),
+ Matcher(0), CurPredicate(0) {
+ // We need to produce the matcher tree for the patterns source pattern. To do
+ // this we need to match the structure as well as the types. To do the type
+ // matching, we want to figure out the fewest number of type checks we need to
+ // emit. For example, if there is only one integer type supported by a
+ // target, there should be no type comparisons at all for integer patterns!
+ //
+ // To figure out the fewest number of type checks needed, clone the pattern,
+ // remove the types, then perform type inference on the pattern as a whole.
+ // If there are unresolved types, emit an explicit check for those types,
+ // apply the type to the tree, then rerun type inference. Iterate until all
+ // types are resolved.
+ //
+ PatWithNoTypes = Pattern.getSrcPattern()->clone();
+ PatWithNoTypes->RemoveAllTypes();
+
+ // If there are types that are manifestly known, infer them.
+ InferPossibleTypes();
+}
+
+/// InferPossibleTypes - As we emit the pattern, we end up generating type
+/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we
+/// want to propagate implied types as far throughout the tree as possible so
+/// that we avoid doing redundant type checks. This does the type propagation.
+void MatcherGen::InferPossibleTypes() {
+ // TP - Get *SOME* tree pattern, we don't care which. It is only used for
+ // diagnostics, which we know are impossible at this point.
+ TreePattern &TP = *CGP.pf_begin()->second;
+
+ try {
+ bool MadeChange = true;
+ while (MadeChange)
+ MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP,
+ true/*Ignore reg constraints*/);
+ } catch (...) {
+ errs() << "Type constraint application shouldn't fail!";
+ abort();
+ }
+}
+
+
+/// AddMatcherNode - Add a matcher node to the current graph we're building.
+void MatcherGen::AddMatcherNode(MatcherNodeWithChild *NewNode) {
+ if (CurPredicate != 0)
+ CurPredicate->setChild(NewNode);
+ else
+ Matcher = NewNode;
+ CurPredicate = NewNode;
+}
+
+
+
+/// EmitLeafMatchCode - Generate matching code for leaf nodes.
+void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) {
+ assert(N->isLeaf() && "Not a leaf?");
+ // Direct match against an integer constant.
+ if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue()))
+ return AddMatcherNode(new CheckIntegerMatcherNode(II->getValue()));
+
+ DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue());
+ if (DI == 0) {
+ errs() << "Unknown leaf kind: " << *DI << "\n";
+ abort();
+ }
+
+ Record *LeafRec = DI->getDef();
+ if (// Handle register references. Nothing to do here, they always match.
+ LeafRec->isSubClassOf("RegisterClass") ||
+ LeafRec->isSubClassOf("PointerLikeRegClass") ||
+ LeafRec->isSubClassOf("Register") ||
+ // Place holder for SRCVALUE nodes. Nothing to do here.
+ LeafRec->getName() == "srcvalue")
+ return;
+
+ if (LeafRec->isSubClassOf("ValueType"))
+ return AddMatcherNode(new CheckValueTypeMatcherNode(LeafRec->getName()));
+
+ if (LeafRec->isSubClassOf("CondCode"))
+ return AddMatcherNode(new CheckCondCodeMatcherNode(LeafRec->getName()));
+
+ if (LeafRec->isSubClassOf("ComplexPattern")) {
+ // Handle complex pattern.
+ const ComplexPattern &CP = CGP.getComplexPattern(LeafRec);
+ return AddMatcherNode(new CheckComplexPatMatcherNode(CP));
+ }
+
+ errs() << "Unknown leaf kind: " << *N << "\n";
+ abort();
+}
+
+void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
+ TreePatternNode *NodeNoTypes) {
+ assert(!N->isLeaf() && "Not an operator?");
+ const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator());
+
+ // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
+ // a constant without a predicate fn that has more that one bit set, handle
+ // this as a special case. This is usually for targets that have special
+ // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
+ // handling stuff). Using these instructions is often far more efficient
+ // than materializing the constant. Unfortunately, both the instcombiner
+ // and the dag combiner can often infer that bits are dead, and thus drop
+ // them from the mask in the dag. For example, it might turn 'AND X, 255'
+ // into 'AND X, 254' if it knows the low bit is set. Emit code that checks
+ // to handle this.
+ if ((N->getOperator()->getName() == "and" ||
+ N->getOperator()->getName() == "or") &&
+ N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty()) {
+ if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) {
+ if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits.
+ if (N->getOperator()->getName() == "and")
+ AddMatcherNode(new CheckAndImmMatcherNode(II->getValue()));
+ else
+ AddMatcherNode(new CheckOrImmMatcherNode(II->getValue()));
+
+ // Match the LHS of the AND as appropriate.
+ AddMatcherNode(new MoveChildMatcherNode(0));
+ EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0));
+ AddMatcherNode(new MoveParentMatcherNode());
+ return;
+ }
+ }
+ }
+
+ // Check that the current opcode lines up.
+ AddMatcherNode(new CheckOpcodeMatcherNode(CInfo.getEnumName()));
+
+ // If this node has a chain, then the chain is operand #0 is the SDNode, and
+ // the child numbers of the node are all offset by one.
+ unsigned OpNo = 0;
+ if (N->NodeHasProperty(SDNPHasChain, CGP))
+ OpNo = 1;
+
+ if (N->TreeHasProperty(SDNPHasChain, CGP)) {
+ // FIXME: Handle Chains with multiple uses etc.
+ // [ld]
+ // ^ ^
+ // | |
+ // / \---
+ // / [YY]
+ // | ^
+ // [XX]-------|
+ }
+
+ // FIXME: Handle Flags & .hasOneUse()
+
+ for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
+ // Get the code suitable for matching this child. Move to the child, check
+ // it then move back to the parent.
+ AddMatcherNode(new MoveChildMatcherNode(i));
+ EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i));
+ AddMatcherNode(new MoveParentMatcherNode());
+ }
+}
+
+
+void MatcherGen::EmitMatchCode(const TreePatternNode *N,
+ TreePatternNode *NodeNoTypes) {
+ // If N and NodeNoTypes don't agree on a type, then this is a case where we
+ // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and
+ // reinfer any correlated types.
+ if (NodeNoTypes->getExtTypes() != N->getExtTypes()) {
+ AddMatcherNode(new CheckTypeMatcherNode(N->getTypeNum(0)));
+ NodeNoTypes->setTypes(N->getExtTypes());
+ InferPossibleTypes();
+ }
+
+
+ // If this node has a name associated with it, capture it in VariableMap. If
+ // we already saw this in the pattern, emit code to verify dagness.
+ if (!N->getName().empty()) {
+ unsigned &VarMapEntry = VariableMap[N->getName()];
+ if (VarMapEntry == 0) {
+ VarMapEntry = ++NextRecordedOperandNo;
+ AddMatcherNode(new RecordMatcherNode());
+ } else {
+ // If we get here, this is a second reference to a specific name. Since
+ // we already have checked that the first reference is valid, we don't
+ // have to recursively match it, just check that it's the same as the
+ // previously named thing.
+ AddMatcherNode(new CheckSameMatcherNode(VarMapEntry-1));
+ return;
+ }
+ }
+
+ // If there are node predicates for this node, generate their checks.
+ for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i)
+ AddMatcherNode(new CheckPredicateMatcherNode(N->getPredicateFns()[i]));
+
+ if (N->isLeaf())
+ EmitLeafMatchCode(N);
+ else
+ EmitOperatorMatchCode(N, NodeNoTypes);
+}
+
+void MatcherGen::EmitMatcherCode() {
+ // If the pattern has a predicate on it (e.g. only enabled when a subtarget
+ // feature is around, do the check).
+ if (!Pattern.getPredicateCheck().empty())
+ AddMatcherNode(new
+ CheckPatternPredicateMatcherNode(Pattern.getPredicateCheck()));
+
+ // Emit the matcher for the pattern structure and types.
+ EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes);
+}
+
+
+MatcherNode *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern,
+ const CodeGenDAGPatterns &CGP) {
+ MatcherGen Gen(Pattern, CGP);
+
+ // Generate the code for the matcher.
+ Gen.EmitMatcherCode();
+
+ // If the match succeeds, then we generate Pattern.
+ EmitNodeMatcherNode *Result = new EmitNodeMatcherNode(Pattern);
+
+ // Link it into the pattern.
+ if (MatcherNodeWithChild *Pred = Gen.GetCurPredicate()) {
+ Pred->setChild(Result);
+ return Gen.GetMatcher();
+ }
+
+ // Unconditional match.
+ return Result;
+}
+
+
+