add support for the new isel matcher to generate

(isprofitable|islegal)tofold checks.


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

7 files changed, 123 insertions, 12 deletions

diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h
index f9490a7..831475d 100644
--- a/include/llvm/CodeGen/DAGISelHeader.h
+++ b/include/llvm/CodeGen/DAGISelHeader.h
@@ -202,7 +202,9 @@ enum BuiltinOpcodes {
   OPC_CheckValueType,
   OPC_CheckComplexPat,
   OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
-  OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8
+  OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8,
+  OPC_IsProfitableToFold,
+  OPC_IsLegalToFold
 };
 
 struct MatchScope {
@@ -379,6 +381,19 @@ SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
     case OPC_CheckOrImm8:
       if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
       continue;
+        
+    case OPC_IsProfitableToFold:
+      assert(!NodeStack.size() == 1 && "No parent node");
+      if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
+                              NodeToMatch))
+        break;
+      continue;
+    case OPC_IsLegalToFold:
+      assert(!NodeStack.size() == 1 && "No parent node");
+      if (!IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
+                         NodeToMatch))
+        break;
+      continue;
     }
     
     // If the code reached this point, then the match failed pop out to the next
diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h
index 5eef9e1..f1f7bca 100644
--- a/utils/TableGen/CodeGenDAGPatterns.h
+++ b/utils/TableGen/CodeGenDAGPatterns.h
@@ -216,6 +216,13 @@ public:
   void setChild(unsigned i, TreePatternNode *N) {
     Children[i] = N;
   }
+  
+  /// hasChild - Return true if N is any of our children.
+  bool hasChild(const TreePatternNode *N) const {
+    for (unsigned i = 0, e = Children.size(); i != e; ++i)
+      if (Children[i] == N) return true;
+    return false;
+  }
 
   const std::vector<std::string> &getPredicateFns() const {return PredicateFns;}
   void clearPredicateFns() { PredicateFns.clear(); }
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index d2e260e..243700f 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -586,6 +586,8 @@ void PatternCodeEmitter::EmitMatchCode(TreePatternNode *N, TreePatternNode *P,
         //      /        [YY]
         //      |         ^
         //     [XX]-------|
+        
+        // We know we need the check if N's parent is not the root.
         bool NeedCheck = P != Pattern;
         if (!NeedCheck) {
           const SDNodeInfo &PInfo = CGP.getSDNodeInfo(P->getOperator());
diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp
index 1363aa3..3f75558 100644
--- a/utils/TableGen/DAGISelMatcher.cpp
+++ b/utils/TableGen/DAGISelMatcher.cpp
@@ -106,3 +106,13 @@ void CheckOrImmMatcherNode::print(raw_ostream &OS, unsigned indent) const {
   printChild(OS, indent);
 }
 
+void CheckProfitableToFoldMatcherNode::print(raw_ostream &OS,
+                                             unsigned indent) const {
+  OS.indent(indent) << "CheckProfitableToFold\n";
+  printChild(OS, indent);
+}
+
+void CheckLegalToFoldMatcherNode::print(raw_ostream &OS, unsigned indent) const{
+  OS.indent(indent) << "CheckLegalToFold\n";
+  printChild(OS, indent);
+}
diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h
index 72bdb7b..8699d51 100644
--- a/utils/TableGen/DAGISelMatcher.h
+++ b/utils/TableGen/DAGISelMatcher.h
@@ -48,7 +48,9 @@ public:
     CheckValueType,
     CheckComplexPat,
     CheckAndImm,
-    CheckOrImm
+    CheckOrImm,
+    CheckProfitableToFold,
+    CheckLegalToFold
   };
   const KindTy Kind;
   
@@ -355,8 +357,34 @@ public:
   
   virtual void print(raw_ostream &OS, unsigned indent = 0) const;
 };
+
+/// CheckProfitableToFoldMatcherNode - This checks to see if the current node is
+/// worthwhile to try to fold into a large pattern.
+class CheckProfitableToFoldMatcherNode : public MatcherNodeWithChild {
+public:
+  CheckProfitableToFoldMatcherNode()
+  : MatcherNodeWithChild(CheckProfitableToFold) {}
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckProfitableToFold;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckLegalToFoldMatcherNode - This checks to see if the current node is
+/// legal to try to fold into a large pattern.
+class CheckLegalToFoldMatcherNode : public MatcherNodeWithChild {
+public:
+  CheckLegalToFoldMatcherNode()
+  : MatcherNodeWithChild(CheckLegalToFold) {}
   
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckLegalToFold;
+  }
   
+  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
index 1a41713..ee838d0 100644
--- a/utils/TableGen/DAGISelMatcherEmitter.cpp
+++ b/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -151,6 +151,12 @@ static unsigned EmitMatcher(const MatcherNode *N, formatted_raw_ostream &OS,
     OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", ";
     return EmitInt(Val, OS)+1;
   }
+  case MatcherNode::CheckProfitableToFold:
+    OS << "OPC_IsProfitableToFold,\n";
+    return 1;
+  case MatcherNode::CheckLegalToFold:
+    OS << "OPC_IsLegalToFold,\n";
+    return 1;
   }
   assert(0 && "Unreachable");
   return 0;
diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp
index afa2587..3ed076c 100644
--- a/utils/TableGen/DAGISelMatcherGen.cpp
+++ b/utils/TableGen/DAGISelMatcherGen.cpp
@@ -189,18 +189,61 @@ void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
   if (N->NodeHasProperty(SDNPHasChain, CGP))
     OpNo = 1;
 
-  if (N->TreeHasProperty(SDNPHasChain, CGP)) {
-    // FIXME: Handle Chains with multiple uses etc.
-    //         [ld]
-    //         ^  ^
-    //         |  |
-    //        /   \---
-    //      /        [YY]
-    //      |         ^
-    //     [XX]-------|
+  // If this node is not the root and the subtree underneath it produces a
+  // chain, then the result of matching the node is also produce a chain.
+  // Beyond that, this means that we're also folding (at least) the root node
+  // into the node that produce the chain (for example, matching
+  // "(add reg, (load ptr))" as a add_with_memory on X86).  This is problematic,
+  // if the 'reg' node also uses the load (say, its chain).  Graphically:
+  //
+  //         [LD]
+  //         ^  ^
+  //         |  \                              DAG's like cheese.
+  //        /    |
+  //       /    [YY]
+  //       |     ^
+  //      [XX]--/
+  //
+  // It would be invalid to fold XX and LD.  In this case, folding the two
+  // nodes together would induce a cycle in the DAG, making it a cyclic DAG (!).
+  // To prevent this, we emit a dynamic check for legality before allowing this
+  // to be folded.
+  //
+  const TreePatternNode *Root = Pattern.getSrcPattern();
+  if (N != Root &&                             // Not the root of the pattern.
+      N->TreeHasProperty(SDNPHasChain, CGP)) { // Has a chain somewhere in tree.
+    
+    AddMatcherNode(new CheckProfitableToFoldMatcherNode());
+    
+    // If this non-root node produces a chain, we may need to emit a validity
+    // check.
+    if (OpNo != 0) {
+      // If there is a node between the root and this node, then we definitely
+      // need to emit the check.
+      bool NeedCheck = !Root->hasChild(N);
+      
+      // If it *is* an immediate child of the root, we can still need a check if
+      // the root SDNode has multiple inputs.  For us, this means that it is an
+      // intrinsic, has multiple operands, or has other inputs like chain or
+      // flag).
+      if (!NeedCheck) {
+        const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator());
+        NeedCheck =
+          Root->getOperator() == CGP.get_intrinsic_void_sdnode() ||
+          Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() ||
+          Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() ||
+          PInfo.getNumOperands() > 1 ||
+          PInfo.hasProperty(SDNPHasChain) ||
+          PInfo.hasProperty(SDNPInFlag) ||
+          PInfo.hasProperty(SDNPOptInFlag);
+      }
+      
+      if (NeedCheck)
+        AddMatcherNode(new CheckLegalToFoldMatcherNode());
+    }
   }
       
-  // FIXME: Handle Flags & .hasOneUse()
+  // FIXME: Handle EmittedUseCheck & 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