Revert: r327172 "Correct load-op-store cycle detection analysis"

        r327171 "Improve Dependency analysis when doing multi-node Instruction Selection"
        r328170 "[DAG] Enforce stricter NodeId invariant during Instruction selection"

Reverting patch as NodeId invariant change is causing pathological
increases in compile time on PPC

llvm-svn: 327197

1 files changed, 227 insertions, 168 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 414b3be77e1..067690af636 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -960,59 +960,6 @@ public:
 
 } // end anonymous namespace
 
-// This function is used to enforce the topological node id property
-// property leveraged during Instruction selection. Before selection all
-// nodes are given a non-negative id such that all nodes have a larger id than
-// their operands. As this holds transitively we can prune checks that a node N
-// is a predecessor of M another by not recursively checking through M's
-// operands if N's ID is larger than M's ID. This is significantly improves
-// performance of for various legality checks (e.g. IsLegalToFold /
-// UpdateChains).
-
-// However, when we fuse multiple nodes into a single node
-// during selection we may induce a predecessor relationship between inputs and
-// outputs of distinct nodes being merged violating the topological property.
-// Should a fused node have a successor which has yet to be selected, our
-// legality checks would be incorrect. To avoid this we mark all unselected
-// sucessor nodes, i.e. id != -1 as invalid for pruning by bit-negating (x =>
-// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
-// We use bit-negation to more clearly enforce that node id -1 can only be
-// achieved by selected nodes). As the conversion is reversable the original Id,
-// topological pruning can still be leveraged when looking for unselected nodes.
-// This method is call internally in all ISel replacement calls.
-void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
-  SmallVector<SDNode *, 4> OpNodes;
-  SmallVector<SDNode *, 4> Nodes;
-  SmallPtrSet<const SDNode *, 32> Visited;
-  OpNodes.push_back(Node);
-
-  while (!OpNodes.empty()) {
-    SDNode *N = OpNodes.pop_back_val();
-    for (const SDValue &Op : N->op_values()) {
-      if (Op->getNodeId() == -1 && Visited.insert(Op.getNode()).second)
-        OpNodes.push_back(Op.getNode());
-    }
-    Nodes.push_back(N);
-  }
-
-  Visited.clear();
-  while (!Nodes.empty()) {
-    SDNode *N = Nodes.pop_back_val();
-
-    // Don't repeat work.
-    if (!Visited.insert(N).second)
-      continue;
-    for (auto *U : N->uses()) {
-      auto UId = U->getNodeId();
-      if (UId > 0) {
-        int InvalidatedUId = -UId + 1;
-        U->setNodeId(InvalidatedUId);
-        Nodes.push_back(U);
-      }
-    }
-  }
-}
-
 void SelectionDAGISel::DoInstructionSelection() {
   DEBUG(dbgs() << "===== Instruction selection begins: "
                << printMBBReference(*FuncInfo->MBB) << " '"
@@ -1048,33 +995,6 @@ void SelectionDAGISel::DoInstructionSelection() {
       if (Node->use_empty())
         continue;
 
-#ifndef NDEBUG
-      SmallVector<SDNode *, 4> Nodes;
-      Nodes.push_back(Node);
-
-      while (!Nodes.empty()) {
-        auto N = Nodes.pop_back_val();
-        if (Node->getOpcode() == ISD::TokenFactor || Node->getNodeId() < 0)
-          continue;
-        for (const SDValue &Op : N->op_values()) {
-          if (Op->getOpcode() == ISD::TokenFactor)
-            Nodes.push_back(Op.getNode());
-          else {
-            // We rely on topological ordering of node ids for checking for
-            // cycles when fusing nodes during selection. All unselected nodes
-            // successors of an already selected node should have a negative id.
-            // This assertion will catch such cases. If this assertion triggers
-            // it is likely you using DAG-level Value/Node replacement functions
-            // (versus equivalent ISEL replacement) in backend-specific
-            // selections. See comment in EnforceNodeIdInvariant for more
-            // details.
-            assert(Op->getNodeId() != -1 &&
-                   "Node has already selected predecessor node");
-          }
-        }
-      }
-#endif
-
       // When we are using non-default rounding modes or FP exception behavior
       // FP operations are represented by StrictFP pseudo-operations.  They
       // need to be simplified here so that the target-specific instruction
@@ -2242,44 +2162,54 @@ static SDNode *findGlueUse(SDNode *N) {
   return nullptr;
 }
 
-/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
-/// beyond "ImmedUse".  We may ignore chains as they are checked separately.
-static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
+/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
+/// This function iteratively traverses up the operand chain, ignoring
+/// certain nodes.
+static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
+                          SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited,
                           bool IgnoreChains) {
-  SmallPtrSet<const SDNode *, 16> Visited;
-  SmallVector<const SDNode *, 16> WorkList;
-  // Only check if we have non-immediate uses of Def.
-  if (ImmedUse->isOnlyUserOf(Def))
-    return false;
-
-  // We don't care about paths to Def that go through ImmedUse so mark it
-  // visited and mark non-def operands as used.
-  Visited.insert(ImmedUse);
-  for (const SDValue &Op : ImmedUse->op_values()) {
-    SDNode *N = Op.getNode();
-    // Ignore chain deps (they are validated by
-    // HandleMergeInputChains) and immediate uses
-    if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
+  // The NodeID's are given uniques ID's where a node ID is guaranteed to be
+  // greater than all of its (recursive) operands.  If we scan to a point where
+  // 'use' is smaller than the node we're scanning for, then we know we will
+  // never find it.
+  //
+  // The Use may be -1 (unassigned) if it is a newly allocated node.  This can
+  // happen because we scan down to newly selected nodes in the case of glue
+  // uses.
+  std::vector<SDNode *> WorkList;
+  WorkList.push_back(Use);
+
+  while (!WorkList.empty()) {
+    Use = WorkList.back();
+    WorkList.pop_back();
+    // NodeId topological order of TokenFactors is not guaranteed. Do not skip.
+    if (Use->getOpcode() != ISD::TokenFactor &&
+        Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)
       continue;
-    if (!Visited.insert(N).second)
+
+    // Don't revisit nodes if we already scanned it and didn't fail, we know we
+    // won't fail if we scan it again.
+    if (!Visited.insert(Use).second)
       continue;
-    WorkList.push_back(N);
-  }
 
-  // Initialize worklist to operands of Root.
-  if (Root != ImmedUse) {
-    for (const SDValue &Op : Root->op_values()) {
-      SDNode *N = Op.getNode();
-      // Ignore chains (they are validated by HandleMergeInputChains)
-      if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
-        continue;
-      if (!Visited.insert(N).second)
+    for (const SDValue &Op : Use->op_values()) {
+      // Ignore chain uses, they are validated by HandleMergeInputChains.
+      if (Op.getValueType() == MVT::Other && IgnoreChains)
         continue;
+
+      SDNode *N = Op.getNode();
+      if (N == Def) {
+        if (Use == ImmedUse || Use == Root)
+          continue;  // We are not looking for immediate use.
+        assert(N != Root);
+        return true;
+      }
+
+      // Traverse up the operand chain.
       WorkList.push_back(N);
     }
   }
-
-  return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
+  return false;
 }
 
 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
@@ -2351,12 +2281,13 @@ bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
 
     // If our query node has a glue result with a use, we've walked up it.  If
     // the user (which has already been selected) has a chain or indirectly uses
-    // the chain, HandleMergeInputChains will not consider it.  Because of
+    // the chain, our WalkChainUsers predicate will not consider it.  Because of
     // this, we cannot ignore chains in this predicate.
     IgnoreChains = false;
   }
 
-  return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
+  SmallPtrSet<SDNode*, 16> Visited;
+  return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
 }
 
 void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
@@ -2460,7 +2391,7 @@ void SelectionDAGISel::UpdateChains(
                          static_cast<SDNode *>(nullptr));
           });
       if (ChainNode->getOpcode() != ISD::TokenFactor)
-        ReplaceUses(ChainVal, InputChain);
+        CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
 
       // If the node became dead and we haven't already seen it, delete it.
       if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
@@ -2475,6 +2406,143 @@ void SelectionDAGISel::UpdateChains(
   DEBUG(dbgs() << "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(const SDNode *ChainedNode,
+               SmallVectorImpl<SDNode *> &ChainedNodesInPattern,
+               DenseMap<const SDNode *, ChainResult> &TokenFactorResult,
+               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 (User->getOpcode() == ISD::HANDLENODE)  // Root of the graph.
+      continue;
+
+    // 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.
+    unsigned UserOpcode = User->getOpcode();
+    if (User->isMachineOpcode() ||
+        UserOpcode == ISD::CopyToReg ||
+        UserOpcode == ISD::CopyFromReg ||
+        UserOpcode == ISD::INLINEASM ||
+        UserOpcode == ISD::EH_LABEL ||
+        UserOpcode == ISD::LIFETIME_START ||
+        UserOpcode == ISD::LIFETIME_END) {
+      // If their node ID got reset to -1 then they've already been selected.
+      // Treat them like a MachineOpcode.
+      if (User->getNodeId() == -1)
+        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.
+    auto MemoizeResult = TokenFactorResult.find(User);
+    bool Visited = MemoizeResult != TokenFactorResult.end();
+    // Recursively walk chain users only if the result is not memoized.
+    if (!Visited) {
+      auto Res = WalkChainUsers(User, ChainedNodesInPattern, TokenFactorResult,
+                                InteriorChainedNodes);
+      MemoizeResult = TokenFactorResult.insert(std::make_pair(User, Res)).first;
+    }
+    switch (MemoizeResult->second) {
+    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;
+    if (!Visited) {
+      ChainedNodesInPattern.push_back(User);
+      InteriorChainedNodes.push_back(User);
+    }
+  }
+
+  return Result;
+}
+
 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
 /// operation for when the pattern matched at least one node with a chains.  The
 /// input vector contains a list of all of the chained nodes that we match.  We
@@ -2484,56 +2552,47 @@ void SelectionDAGISel::UpdateChains(
 static SDValue
 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
                        SelectionDAG *CurDAG) {
+  // Used for memoization. Without it WalkChainUsers could take exponential
+  // time to run.
+  DenseMap<const SDNode *, ChainResult> TokenFactorResult;
+  // 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,
+                       TokenFactorResult,
+                       InteriorChainedNodes) == CR_InducesCycle)
+      return SDValue(); // Would induce a cycle.
+  }
 
-  SmallPtrSet<const SDNode *, 16> Visited;
-  SmallVector<const SDNode *, 8> Worklist;
+  // 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;
-  unsigned int Max = 8192;
-
-  // Quick exit on trivial merge.
-  if (ChainNodesMatched.size() == 1)
-    return ChainNodesMatched[0]->getOperand(0);
+  for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
+    // 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;
 
-  // Add chains that aren't already added (internal). Peek through
-  // token factors.
-  std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
-    if (V.getValueType() != MVT::Other)
-      return;
-    if (V->getOpcode() == ISD::EntryToken)
-      return;
-    if (!Visited.insert(V.getNode()).second)
-      return;
-    if (V->getOpcode() == ISD::TokenFactor) {
-      for (const SDValue &Op : V->op_values())
-        AddChains(Op);
-    } else
-      InputChains.push_back(V);
-  };
+      // Otherwise, add the input chain.
+      SDValue InChain = ChainNodesMatched[i]->getOperand(0);
+      assert(InChain.getValueType() == MVT::Other && "Not a chain");
+      InputChains.push_back(InChain);
+      continue;
+    }
 
-  for (auto *N : ChainNodesMatched) {
-    Worklist.push_back(N);
-    Visited.insert(N);
+    // 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 (const SDValue &Op : N->op_values()) {
+      if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
+                      Op.getNode()))
+        InputChains.push_back(Op);
+    }
   }
 
-  while (!Worklist.empty())
-    AddChains(Worklist.pop_back_val()->getOperand(0));
-
-  // Skip the search if there are no chain dependencies.
-  if (InputChains.size() == 0)
-    return CurDAG->getEntryNode();
-
-  // If one of these chains is a successor of input, we must have a
-  // node that is both the predecessor and successor of the
-  // to-be-merged nodes. Fail.
-  Visited.clear();
-  for (SDValue V : InputChains)
-    Worklist.push_back(V.getNode());
-
-  for (auto *N : ChainNodesMatched)
-    if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
-      return SDValue();
-
-  // Return merged chain.
   if (InputChains.size() == 1)
     return InputChains[0];
   return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
@@ -2578,8 +2637,8 @@ MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
   // Move the glue if needed.
   if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
       (unsigned)OldGlueResultNo != ResNumResults-1)
-    ReplaceUses(SDValue(Node, OldGlueResultNo),
-                SDValue(Res, ResNumResults - 1));
+    CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
+                                      SDValue(Res, ResNumResults-1));
 
   if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
     --ResNumResults;
@@ -2587,15 +2646,14 @@ MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
   // Move the chain reference if needed.
   if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
       (unsigned)OldChainResultNo != ResNumResults-1)
-    ReplaceUses(SDValue(Node, OldChainResultNo),
-                SDValue(Res, ResNumResults - 1));
+    CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
+                                      SDValue(Res, ResNumResults-1));
 
   // Otherwise, no replacement happened because the node already exists. Replace
   // Uses of the old node with the new one.
   if (Res != Node) {
-    ReplaceNode(Node, Res);
-  } else {
-    EnforceNodeIdInvariant(Res);
+    CurDAG->ReplaceAllUsesWith(Node, Res);
+    CurDAG->RemoveDeadNode(Node);
   }
 
   return Res;
@@ -2912,7 +2970,8 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
     return;
   case ISD::AssertSext:
   case ISD::AssertZext:
-    ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
+    CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
+                                      NodeToMatch->getOperand(0));
     CurDAG->RemoveDeadNode(NodeToMatch);
     return;
   case ISD::INLINEASM:
@@ -3670,7 +3729,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
                 NodeToMatch->getValueType(i).getSizeInBits() ==
                     Res.getValueSizeInBits()) &&
                "invalid replacement");
-        ReplaceUses(SDValue(NodeToMatch, i), Res);
+        CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
       }
 
       // Update chain uses.
@@ -3683,8 +3742,8 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
       if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
               MVT::Glue &&
           InputGlue.getNode())
-        ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
-                    InputGlue);
+        CurDAG->ReplaceAllUsesOfValueWith(
+            SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), InputGlue);
 
       assert(NodeToMatch->use_empty() &&
              "Didn't replace all uses of the node?");