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

1 files changed, 287 insertions, 0 deletions

diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp
new file mode 100644
index 0000000000..afa258718f
--- /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;
+}
+
+
+