[DAG] Enforce stricter NodeId invariant during Instruction selection

Instruction Selection makes use of the topological ordering of nodes
by node id (a node's operands have smaller node id than it) when doing
cycle detection.  During selection we may violate this property as a
selection of multiple nodes may induce a use dependence (and thus a
node id restriction) between two unrelated nodes. If a selected node
has an unselected successor this may allow us to miss a cycle in
detection an invalid selection.

This patch fixes this by marking all unselected successors of a
selected node have negated node id.  We avoid pruning on such negative
ids but still can reconstruct the original id for pruning.

In-tree targets have been updated to replace DAG-level replacements
with ISel-level ones which enforce this property.

This preemptively fixes PR36312 before triggering commit r324359 relands

Reviewers: craig.topper, bogner, jyknight

Subscribers: arsenm, nhaehnle, javed.absar, llvm-commits, hiraditya

Differential Revision: https://reviews.llvm.org/D43198

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

1 files changed, 9 insertions, 6 deletions

diff --git a/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp b/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
index 9bf2474915c..6e2130828bb 100644
--- a/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
+++ b/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
@@ -596,7 +596,13 @@ static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
   if (N.getNode()->getNodeId() == -1 ||
       N.getNode()->getNodeId() > Pos->getNodeId()) {
     DAG->RepositionNode(Pos->getIterator(), N.getNode());
-    N.getNode()->setNodeId(Pos->getNodeId());
+    // Mark Node as invalid for pruning as after this it may be a successor to a
+    // selected node but otherwise be in the same position of Pos.
+    // Conservatively mark it with the same -abs(Id) to assure node id
+    // invariant is preserved.
+    int PId = Pos->getNodeId();
+    int InvalidatedPId = -(PId + 1);
+    N->setNodeId((PId > 0) ? InvalidatedPId : PId);
   }
 }
 
@@ -1027,8 +1033,7 @@ bool SystemZDAGToDAGISel::tryRISBGZero(SDNode *N) {
   };
   SDValue New = convertTo(
       DL, VT, SDValue(CurDAG->getMachineNode(Opcode, DL, OpcodeVT, Ops), 0));
-  ReplaceUses(N, New.getNode());
-  CurDAG->RemoveDeadNode(N);
+  ReplaceNode(N, New.getNode());
   return true;
 }
 
@@ -1119,8 +1124,7 @@ void SystemZDAGToDAGISel::splitLargeImmediate(unsigned Opcode, SDNode *Node,
   SDValue Lower = CurDAG->getConstant(LowerVal, DL, VT);
   SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower);
 
-  ReplaceUses(Node, Or.getNode());
-  CurDAG->RemoveDeadNode(Node);
+  ReplaceNode(Node, Or.getNode());
 
   SelectCode(Or.getNode());
 }
@@ -1618,4 +1622,3 @@ void SystemZDAGToDAGISel::PreprocessISelDAG() {
   if (MadeChange)
     CurDAG->RemoveDeadNodes();
 }
-