print the complexity of the pattern being matched in the

comment in the generated table.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99794 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 76 insertions, 59 deletions

diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp
index 84a041b194..d2c0195c6d 100644
--- a/utils/TableGen/CodeGenDAGPatterns.cpp
+++ b/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -491,6 +491,59 @@ void DumpDepVars(MultipleUseVarSet &DepVars) {
 // PatternToMatch implementation
 //
 
+
+/// getPatternSize - Return the 'size' of this pattern.  We want to match large
+/// patterns before small ones.  This is used to determine the size of a
+/// pattern.
+static unsigned getPatternSize(const TreePatternNode *P,
+                               const CodeGenDAGPatterns &CGP) {
+  unsigned Size = 3;  // The node itself.
+  // If the root node is a ConstantSDNode, increases its size.
+  // e.g. (set R32:$dst, 0).
+  if (P->isLeaf() && dynamic_cast<IntInit*>(P->getLeafValue()))
+    Size += 2;
+  
+  // FIXME: This is a hack to statically increase the priority of patterns
+  // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD.
+  // Later we can allow complexity / cost for each pattern to be (optionally)
+  // specified. To get best possible pattern match we'll need to dynamically
+  // calculate the complexity of all patterns a dag can potentially map to.
+  const ComplexPattern *AM = P->getComplexPatternInfo(CGP);
+  if (AM)
+    Size += AM->getNumOperands() * 3;
+  
+  // If this node has some predicate function that must match, it adds to the
+  // complexity of this node.
+  if (!P->getPredicateFns().empty())
+    ++Size;
+  
+  // Count children in the count if they are also nodes.
+  for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
+    TreePatternNode *Child = P->getChild(i);
+    if (!Child->isLeaf() && Child->getNumTypes() &&
+        Child->getType(0) != MVT::Other)
+      Size += getPatternSize(Child, CGP);
+    else if (Child->isLeaf()) {
+      if (dynamic_cast<IntInit*>(Child->getLeafValue())) 
+        Size += 5;  // Matches a ConstantSDNode (+3) and a specific value (+2).
+      else if (Child->getComplexPatternInfo(CGP))
+        Size += getPatternSize(Child, CGP);
+      else if (!Child->getPredicateFns().empty())
+        ++Size;
+    }
+  }
+  
+  return Size;
+}
+
+/// Compute the complexity metric for the input pattern.  This roughly
+/// corresponds to the number of nodes that are covered.
+unsigned PatternToMatch::
+getPatternComplexity(const CodeGenDAGPatterns &CGP) const {
+  return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity();
+}
+
+
 /// getPredicateCheck - Return a single string containing all of this
 /// pattern's predicates concatenated with "&&" operators.
 ///
diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h
index 0960647300..548051300d 100644
--- a/utils/TableGen/CodeGenDAGPatterns.h
+++ b/utils/TableGen/CodeGenDAGPatterns.h
@@ -598,6 +598,10 @@ public:
   unsigned         getAddedComplexity() const { return AddedComplexity; }
 
   std::string getPredicateCheck() const;
+  
+  /// Compute the complexity metric for the input pattern.  This roughly
+  /// corresponds to the number of nodes that are covered.
+  unsigned getPatternComplexity(const CodeGenDAGPatterns &CGP) const;
 };
 
 // Deterministic comparison of Record*.
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index 044086add5..f4a287c6c6 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -21,49 +21,6 @@ using namespace llvm;
 // DAGISelEmitter Helper methods
 //
 
-/// getPatternSize - Return the 'size' of this pattern.  We want to match large
-/// patterns before small ones.  This is used to determine the size of a
-/// pattern.
-static unsigned getPatternSize(TreePatternNode *P, CodeGenDAGPatterns &CGP) {
-  unsigned Size = 3;  // The node itself.
-  // If the root node is a ConstantSDNode, increases its size.
-  // e.g. (set R32:$dst, 0).
-  if (P->isLeaf() && dynamic_cast<IntInit*>(P->getLeafValue()))
-    Size += 2;
-
-  // FIXME: This is a hack to statically increase the priority of patterns
-  // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD.
-  // Later we can allow complexity / cost for each pattern to be (optionally)
-  // specified. To get best possible pattern match we'll need to dynamically
-  // calculate the complexity of all patterns a dag can potentially map to.
-  const ComplexPattern *AM = P->getComplexPatternInfo(CGP);
-  if (AM)
-    Size += AM->getNumOperands() * 3;
-
-  // If this node has some predicate function that must match, it adds to the
-  // complexity of this node.
-  if (!P->getPredicateFns().empty())
-    ++Size;
-  
-  // Count children in the count if they are also nodes.
-  for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
-    TreePatternNode *Child = P->getChild(i);
-    if (!Child->isLeaf() && Child->getNumTypes() &&
-        Child->getType(0) != MVT::Other)
-      Size += getPatternSize(Child, CGP);
-    else if (Child->isLeaf()) {
-      if (dynamic_cast<IntInit*>(Child->getLeafValue())) 
-        Size += 5;  // Matches a ConstantSDNode (+3) and a specific value (+2).
-      else if (Child->getComplexPatternInfo(CGP))
-        Size += getPatternSize(Child, CGP);
-      else if (!Child->getPredicateFns().empty())
-        ++Size;
-    }
-  }
-  
-  return Size;
-}
-
 /// getResultPatternCost - Compute the number of instructions for this pattern.
 /// This is a temporary hack.  We should really include the instruction
 /// latencies in this calculation.
@@ -145,6 +102,7 @@ void DAGISelEmitter::EmitPredicateFunctions(raw_ostream &OS) {
   OS << "\n\n";
 }
 
+
 namespace {
 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
 // In particular, we want to match maximal patterns first and lowest cost within
@@ -153,12 +111,12 @@ struct PatternSortingPredicate {
   PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
   CodeGenDAGPatterns &CGP;
   
-  bool operator()(const PatternToMatch *LHS,
-                  const PatternToMatch *RHS) {
-    unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), CGP);
-    unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), CGP);
-    LHSSize += LHS->getAddedComplexity();
-    RHSSize += RHS->getAddedComplexity();
+  bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) {
+    // Otherwise, if the patterns might both match, sort based on complexity,
+    // which means that we prefer to match patterns that cover more nodes in the
+    // input over nodes that cover fewer.
+    unsigned LHSSize = LHS->getPatternComplexity(CGP);
+    unsigned RHSSize = RHS->getPatternComplexity(CGP);
     if (LHSSize > RHSSize) return true;   // LHS -> bigger -> less cost
     if (LHSSize < RHSSize) return false;
     
@@ -173,7 +131,8 @@ struct PatternSortingPredicate {
     if (LHSPatSize < RHSPatSize) return true;
     if (LHSPatSize > RHSPatSize) return false;
     
-    // Sort based on the UID of the pattern, giving us a deterministic ordering.
+    // Sort based on the UID of the pattern, giving us a deterministic ordering
+    // if all other sorting conditions fail.
     assert(LHS == RHS || LHS->ID != RHS->ID);
     return LHS->ID < RHS->ID;
   }
diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp
index 25b7a2f600..4473f0de96 100644
--- a/utils/TableGen/DAGISelMatcherEmitter.cpp
+++ b/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -32,6 +32,7 @@ OmitComments("omit-comments", cl::desc("Do not generate comments"),
 
 namespace {
 class MatcherTableEmitter {
+  const CodeGenDAGPatterns &CGP;
   StringMap<unsigned> NodePredicateMap, PatternPredicateMap;
   std::vector<std::string> NodePredicates, PatternPredicates;
 
@@ -43,13 +44,12 @@ class MatcherTableEmitter {
   std::vector<Record*> NodeXForms;
 
 public:
-  MatcherTableEmitter() {}
+  MatcherTableEmitter(const CodeGenDAGPatterns &cgp) : CGP(cgp) {}
 
   unsigned EmitMatcherList(const Matcher *N, unsigned Indent,
                            unsigned StartIdx, formatted_raw_ostream &OS);
   
-  void EmitPredicateFunctions(const CodeGenDAGPatterns &CGP,
-                              formatted_raw_ostream &OS);
+  void EmitPredicateFunctions(formatted_raw_ostream &OS);
   
   void EmitHistogram(const Matcher *N, formatted_raw_ostream &OS);
 private:
@@ -521,7 +521,8 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
 
       if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
         OS.PadToColumn(Indent*2) << "// Src: "
-          << *SNT->getPattern().getSrcPattern() << '\n';
+          << *SNT->getPattern().getSrcPattern() << " - Complexity = " 
+          << SNT->getPattern().getPatternComplexity(CGP) << '\n';
         OS.PadToColumn(Indent*2) << "// Dst: "
           << *SNT->getPattern().getDstPattern() << '\n';
       }
@@ -548,7 +549,8 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
     OS << '\n';
     if (!OmitComments) {
       OS.PadToColumn(Indent*2) << "// Src: "
-        << *CM->getPattern().getSrcPattern() << '\n';
+        << *CM->getPattern().getSrcPattern() << " - Complexity = " 
+        << CM->getPattern().getPatternComplexity(CGP) << '\n';
       OS.PadToColumn(Indent*2) << "// Dst: "
         << *CM->getPattern().getDstPattern();
     }
@@ -579,8 +581,7 @@ EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
   return Size;
 }
 
-void MatcherTableEmitter::EmitPredicateFunctions(const CodeGenDAGPatterns &CGP,
-                                                 formatted_raw_ostream &OS) {
+void MatcherTableEmitter::EmitPredicateFunctions(formatted_raw_ostream &OS) {
   // Emit pattern predicates.
   if (!PatternPredicates.empty()) {
     OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n";
@@ -774,7 +775,7 @@ void llvm::EmitMatcherTable(const Matcher *TheMatcher,
   OS << "// The main instruction selector code.\n";
   OS << "SDNode *SelectCode(SDNode *N) {\n";
 
-  MatcherTableEmitter MatcherEmitter;
+  MatcherTableEmitter MatcherEmitter(CGP);
 
   OS << "  // Opcodes are emitted as 2 bytes, TARGET_OPCODE handles this.\n";
   OS << "  #define TARGET_OPCODE(X) X & 255, unsigned(X) >> 8\n";
@@ -789,5 +790,5 @@ void llvm::EmitMatcherTable(const Matcher *TheMatcher,
   OS << '\n';
   
   // Next up, emit the function for node and pattern predicates:
-  MatcherEmitter.EmitPredicateFunctions(CGP, OS);
+  MatcherEmitter.EmitPredicateFunctions(OS);
 }