Rewrite chain handling validation and input TokenFactor handling

stuff now that we don't care about emulating the old broken 
behavior of the old isel.  This eliminates the 
'CheckChainCompatible' check (along with IsChainCompatible) which
did an incorrect and inefficient scan *up* the chain nodes which
happened as the pattern was being formed and does the validation
at the end in HandleMergeInputChains when it forms a structural 
pattern.  This scans "down" the graph, which means that it is
quickly bounded by nodes already selected.  This also handles
token factors that get "trapped" in the dag.

Removing the CheckChainCompatible nodes also shrinks the 
generated tables by about 6K for X86 (down to 83K).

There are two pieces remaining before I can nuke PreprocessRMW:
1. I xfailed a test because we're now producing worse code in a 
   case that has nothing to do with the change: it turns out that
   our use of MorphNodeTo will leave dead nodes in the graph
   which (depending on how the graph is walked) end up causing
   bogus uses of chains and blocking matches.  This is really 
   bad for other reasons, so I'll fix this in a follow-up patch.

2. CheckFoldableChainNode needs to be improved to handle the TF.



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

1 files changed, 158 insertions, 54 deletions

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index cb16d7a1f2..e62e5591b8 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -1455,30 +1455,6 @@ SDNode *SelectionDAGISel::Select_EH_LABEL(SDNode *N) {
                               MVT::Other, Tmp, Chain);
 }
 
-
-/// ChainNotReachable - Returns true if Chain does not reach Op.
-static bool ChainNotReachable(SDNode *Chain, SDNode *Op) {
-  if (Chain->getOpcode() == ISD::EntryToken)
-    return true;
-  if (Chain->getOpcode() == ISD::TokenFactor)
-    return false;
-  if (Chain->getNumOperands() > 0) {
-    SDValue C0 = Chain->getOperand(0);
-    if (C0.getValueType() == MVT::Other)
-      return C0.getNode() != Op && ChainNotReachable(C0.getNode(), Op);
-  }
-  return true;
-}
-
-/// IsChainCompatible - Returns true if Chain is Op or Chain does not reach Op.
-/// This is used to ensure that there are no nodes trapped between Chain, which
-/// is the first chain node discovered in a pattern and Op, a later node, that
-/// will not be selected into the pattern.
-static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
-  return Chain == Op || ChainNotReachable(Chain, Op);
-}
-
-
 /// GetVBR - decode a vbr encoding whose top bit is set.
 ALWAYS_INLINE static uint64_t
 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
@@ -1543,26 +1519,170 @@ static void UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain,
   DEBUG(errs() << "ISEL: Match complete!\n");
 }
 
+enum ChainResult {
+  CR_Simple,
+  CR_InducesCycle,
+  CR_LeadsToInteriorNode
+};
+
+/// WalkChainUsers - Walk down the users of the specified chained node that is
+/// part of the pattern we're matching, looking at all of the users we find.
+/// This determines whether something is an interior node, whether we have a
+/// non-pattern node in between two pattern nodes (which prevent folding because
+/// it would induce a cycle) and whether we have a TokenFactor node sandwiched
+/// between pattern nodes (in which case the TF becomes part of the pattern).
+///
+/// The walk we do here is guaranteed to be small because we quickly get down to
+/// already selected nodes "below" us.
+static ChainResult 
+WalkChainUsers(SDNode *ChainedNode,
+               SmallVectorImpl<SDNode*> &ChainedNodesInPattern,
+               SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
+  ChainResult Result = CR_Simple;
+  
+  for (SDNode::use_iterator UI = ChainedNode->use_begin(),
+         E = ChainedNode->use_end(); UI != E; ++UI) {
+    // Make sure the use is of the chain, not some other value we produce.
+    if (UI.getUse().getValueType() != MVT::Other) continue;
+    
+    SDNode *User = *UI;
+
+    // If we see an already-selected machine node, then we've gone beyond the
+    // pattern that we're selecting down into the already selected chunk of the
+    // DAG.
+    if (User->isMachineOpcode() ||
+        User->getOpcode() == ISD::CopyToReg ||
+        User->getOpcode() == ISD::CopyFromReg ||
+        User->getOpcode() == ISD::INLINEASM ||
+        User->getOpcode() == ISD::HANDLENODE)  // Root of the graph.
+      continue;
+
+    // If we have a TokenFactor, we handle it specially.
+    if (User->getOpcode() != ISD::TokenFactor) {
+      // If the node isn't a token factor and isn't part of our pattern, then it
+      // must be a random chained node in between two nodes we're selecting.
+      // This happens when we have something like:
+      //   x = load ptr
+      //   call
+      //   y = x+4
+      //   store y -> ptr
+      // Because we structurally match the load/store as a read/modify/write,
+      // but the call is chained between them.  We cannot fold in this case
+      // because it would induce a cycle in the graph.
+      if (!std::count(ChainedNodesInPattern.begin(),
+                      ChainedNodesInPattern.end(), User))
+        return CR_InducesCycle;
+      
+      // Otherwise we found a node that is part of our pattern.  For example in:
+      //   x = load ptr
+      //   y = x+4
+      //   store y -> ptr
+      // This would happen when we're scanning down from the load and see the
+      // store as a user.  Record that there is a use of ChainedNode that is
+      // part of the pattern and keep scanning uses.
+      Result = CR_LeadsToInteriorNode;
+      InteriorChainedNodes.push_back(User);
+      continue;
+    }
+    
+    // If we found a TokenFactor, there are two cases to consider: first if the
+    // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
+    // uses of the TF are in our pattern) we just want to ignore it.  Second,
+    // the TokenFactor can be sandwiched in between two chained nodes, like so:
+    //     [Load chain]
+    //         ^
+    //         |
+    //       [Load]
+    //       ^    ^
+    //       |    \                    DAG's like cheese
+    //      /       \                       do you?
+    //     /         |
+    // [TokenFactor] [Op]
+    //     ^          ^
+    //     |          |
+    //      \        /
+    //       \      /
+    //       [Store]
+    //
+    // In this case, the TokenFactor becomes part of our match and we rewrite it
+    // as a new TokenFactor.
+    //
+    // To distinguish these two cases, do a recursive walk down the uses.
+    switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
+    case CR_Simple:
+      // If the uses of the TokenFactor are just already-selected nodes, ignore
+      // it, it is "below" our pattern.
+      continue;
+    case CR_InducesCycle:
+      // If the uses of the TokenFactor lead to nodes that are not part of our
+      // pattern that are not selected, folding would turn this into a cycle,
+      // bail out now.
+      return CR_InducesCycle;
+    case CR_LeadsToInteriorNode:
+      break;  // Otherwise, keep processing.
+    }
+    
+    // Okay, we know we're in the interesting interior case.  The TokenFactor
+    // is now going to be considered part of the pattern so that we rewrite its
+    // uses (it may have uses that are not part of the pattern) with the
+    // ultimate chain result of the generated code.  We will also add its chain
+    // inputs as inputs to the ultimate TokenFactor we create.
+    Result = CR_LeadsToInteriorNode;
+    ChainedNodesInPattern.push_back(User);
+    InteriorChainedNodes.push_back(User);
+    continue;
+  }
+  
+  return Result;
+}
+
 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
-/// operation for when the pattern matched multiple nodes with chains.
+/// operation for when the pattern matched multiple nodes with chains.  The
+/// input vector contains a list of all of the chained nodes that we match.  We
+/// must determine if this is a valid thing to cover (i.e. matching it won't
+/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
+/// be used as the input node chain for the generated nodes.
 static SDValue
-HandleMergeInputChains(const SmallVectorImpl<SDNode*> &ChainNodesMatched,
+HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
                        SelectionDAG *CurDAG) {
   assert(ChainNodesMatched.size() > 1 && 
          "Should only happen for multi chain node case");
+
+  // Walk all of the chained nodes we've matched, recursively scanning down the
+  // users of the chain result. This adds any TokenFactor nodes that are caught
+  // in between chained nodes to the chained and interior nodes list.
+  SmallVector<SDNode*, 3> InteriorChainedNodes;
+  for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
+    if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
+                       InteriorChainedNodes) == CR_InducesCycle)
+      return SDValue(); // Would induce a cycle.
+  }
   
-  // Walk all the chained nodes, adding the input chains if they are not in
-  // ChainedNodes (and this, not in the matched pattern).  This is an N^2
-  // algorithm, but # chains is usually 2 here, at most 3 for MSP430.
+  // Okay, we have walked all the matched nodes and collected TokenFactor nodes
+  // that we are interested in.  Form our input TokenFactor node.
   SmallVector<SDValue, 3> InputChains;
   for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
-    SDValue InChain = ChainNodesMatched[i]->getOperand(0);
-    assert(InChain.getValueType() == MVT::Other && "Not a chain");
-    bool Invalid = false;
-    for (unsigned j = 0; j != e; ++j)
-      Invalid |= ChainNodesMatched[j] == InChain.getNode();
-    if (!Invalid)
+    // Add the input chain of this node to the InputChains list (which will be
+    // the operands of the generated TokenFactor) if it's not an interior node.
+    SDNode *N = ChainNodesMatched[i];
+    if (N->getOpcode() != ISD::TokenFactor) {
+      if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
+        continue;
+      
+      // Otherwise, add the input chain.
+      SDValue InChain = ChainNodesMatched[i]->getOperand(0);
+      assert(InChain.getValueType() == MVT::Other && "Not a chain");
       InputChains.push_back(InChain);
+      continue;
+    }
+    
+    // If we have a token factor, we want to add all inputs of the token factor
+    // that are not part of the pattern we're matching.
+    for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
+      if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
+                      N->getOperand(i).getNode()))
+        InputChains.push_back(N->getOperand(i));
+    }
   }
   
   SDValue Res;
@@ -1916,25 +2036,6 @@ SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
       
       continue;
     }
-    case OPC_CheckChainCompatible: {
-      unsigned PrevNode = MatcherTable[MatcherIndex++];
-      assert(PrevNode < RecordedNodes.size() && "Invalid CheckChainCompatible");
-      SDValue PrevChainedNode = RecordedNodes[PrevNode];
-      SDValue ThisChainedNode = RecordedNodes.back();
-      
-      // We have two nodes with chains, verify that their input chains are good.
-      assert(PrevChainedNode.getOperand(0).getValueType() == MVT::Other &&
-             ThisChainedNode.getOperand(0).getValueType() == MVT::Other &&
-             "Invalid chained nodes");
-      
-      if (!IsChainCompatible(// Input chain of the previous node.
-                             PrevChainedNode.getOperand(0).getNode(),
-                             // Node with chain.
-                             ThisChainedNode.getNode()))
-        break;
-      continue;
-    }
-        
     case OPC_EmitInteger: {
       MVT::SimpleValueType VT =
         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
@@ -2157,6 +2258,9 @@ SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
         } else if (NodeToMatch->getValueType(NTMNumResults-1) == MVT::Other)
           OldChainResultNo = NTMNumResults-1;
         
+        // FIXME: If this matches multiple nodes it will just leave them here
+        // dead with noone to love them.  These dead nodes can block future
+        // matches (!).
         Res = CurDAG->MorphNodeTo(NodeToMatch, ~TargetOpc, VTList,
                                   Ops.data(), Ops.size());