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/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;
+}
+
+
+