[DAG] Enforce stricter NodeId invariant during Instruction selection

[niravd]

Summary

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

[niravd]

Fix PR number in test and commit message.

[craig.topper]

There appears to be several unrelated formatting changes in here. Can you remove them or commit them separately?

[niravd]

Remove unrelated format changes.

[niravd]

Rephrase comments to be more clear and use less conservative node id. The comments now reference pictoral comments from D43154.

[niravd]

As verifying topological order is preserved is not practical, add EXPENSIVE_CHECK checking that pruning doesn't cause use to miss finding a predecessor.

[niravd]

Ping.

This is the last patch preventing the relanding of https://reviews.llvm.org/D41293.

[jyknight]

After discussion with Nirav --

We now think this is not sufficient to ensure the correct ordering in all cases, because this sort of situation can _probably_ come up in other places too where nodes are merged.

The property that hasPredecessorHelper requires (when Topological Sort is enabled) is that all predecessors have a nodeId less than the nodeId of all successors, recursively. But, this can be violated any time two nodes are merged where the earlier node in the merge pattern has successors outside of the pattern, which have not yet been selected, and the latter node in the pattern has another predecessor.

To make the property sound, any such additional successor nodes would need to have their nodeIds invalidated. (Invalidated means nodeId == -1)

This can only be an issue when there are successors of interior nodes in a merge pattern -- and should only happen where the caller has checked for cycles before doing the merge with hasPredecessor*. When it happens, nodeIds between the min and max in the pattern may need to be invalidated. The typical caller to hasPredecessor is through IsLegalToFold, so callers to that need to be examined too.

The change in this review does try to check the above, but:

1. Only for the X86 special case. The generic case can have the same happen, although generally only via chain outputs from the interior nodes.
2. The invalidation function here stops upon seeing a -1, but it's possible (afaict) for a node with a nodeId -1 to have a successor which has a valid nodeid.

So:
1a. Need to call the invalidation from the generic code in SelectionDAGIsel when merging input chains.
1b. Look at the other callers of IsLegalToFold to make sure they're okay too (some may already be covered by 1a)

2. Need to iterate over the node list, invalidating all nodes between the minimal id and the maximal id in the pattern that are successors to an already-selected node.
3. Need to figure out how to check this property in a way that'll catch future errors.

Hopefully the above is correct. =)

[niravd]

Change to a global fix for all NodeId ordering violation.

[niravd]

Cleanup by folding EnforceNodeIdInvariant into ISel's replace functions

[jyknight]

Looks overall reasonable. Is there any performance impact of EnforceNodeIdInvariant?

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

985 ↗

(On Diff #137763)

Don't want to conflict with existing usage of -1, right? How about (-UId) -1?

3028 ↗

(On Diff #137763)

Why not ReplaceNode?

[niravd]

Looks overall reasonable. Is there any performance impact of EnforceNodeIdInvariant?

We have to make a flood fill pass of the furrow between selected nodes which is potentially large if we select nodes wildly out of order. But that requires some target-specific munging which doesn't seem likely; I have not observed a depth of more than 2.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

985 ↗

(On Diff #137763)

Okay

3028 ↗

(On Diff #137763)

We can't because there is no guarantee that NodeToMatch->getOperand(0) has only 1 value.

[niravd]

Tweak negation as suggested by James.

[jyknight]

OK, seems reasonable.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

while (!Worklist.empty()) {
       if (MaxSteps != 0 && Visited.size() >= MaxSteps)
         break;
     }
     // Push deferred nodes back on worklist.
     Worklist.append(DeferredNodes.begin(), DeferredNodes.end());
     // If we bailed early, conservatively return found.
     if (MaxSteps != 0 && Visited.size() >= MaxSteps)
         return true;
+    #ifdef EXPENSIVE_CHECKS
+    // If we've we failed to find the node verify that topological pruning
+    // was correct by checking through deferred nodes. 
+    if (TopologicalPrune && !Found) {
+      SmallPtrSet<const SDNode *, 32> VisitedCheck(Visited.begin(), Visited.end());
+      SmallVector<const SDNode *, 16> WorklistCheck(Worklist.begin(),Worklist.end());
+      //Do not give up.
+      bool Check = hasPredecessorHelper(N, VisitedCheck, WorklistCheck, 0, false);
+      assert(!Check && "Topological pruning erroneously caused us to miss finding node");
+    }
+    #endif
     return Found;
   }
 
   /// Return true if all the users of N are contained in Nodes.
   /// NOTE: Requires at least one match, but doesn't require them all.
   static bool areOnlyUsersOf(ArrayRef<const SDNode *> Nodes, const SDNode *N);
 
   /// Return the number of values used by this operation.

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

for (SDNode::use_iterator FlagUI = UI->use_begin(), FlagUE = UI->use_end();
       default:
         return false;
       }
     }
   }
   return true;
 }
 
+// Node fusions where some output edges come from a non-root node may result
+// in child nodes violating the topological ordering of node ids. This helper
+// invalidate the id (set to -1) a node (and any similarly recursively) if
+// they have a node id less than Id.
+static void InvalidateNodeIds(SDNode *Node, int Id) {
+  if (Id <= 0)
+    return;
+  SmallVector<SDNode *, 4> Nodes;
+  Nodes.push_back(Node);
+  while (!Nodes.empty()) {
+    SDNode *N = Nodes.pop_back_val();
+    int NId = N->getNodeId();
+    if (NId > 0 && NId < Id) {
+      N->setNodeId(-1);
+      for (auto *U : N->uses())
+        Nodes.push_back(U);
+    }
+  }
+}
+
 /// Check whether or not the chain ending in StoreNode is suitable for doing
 /// the {load; op; store} to modify transformation.
 static bool isFusableLoadOpStorePattern(StoreSDNode *StoreNode,
                                         SDValue StoredVal, SelectionDAG *CurDAG,
                                         LoadSDNode *&LoadNode,
                                         SDValue &InputChain) {
   // is the stored value result 0 of the load?
   if (StoredVal.getResNo() != 0) return false;
bool X86DAGToDAGISel::foldLoadStoreIntoMemOperand(SDNode *Node) {
   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(2);
   MemOp[0] = StoreNode->getMemOperand();
   MemOp[1] = LoadNode->getMemOperand();
   Result->setMemRefs(MemOp, MemOp + 2);
 
   // Update Load Chain uses as well.
   ReplaceUses(SDValue(LoadNode, 1), SDValue(Result, 1));
   ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
+
+  // As discussed in isFusableLoadOpStorePattern, We induce
+  // dependences between Xn and Zn. While we have verified the merge
+  // is safe, this induced dependence may violate the topological
+  // ordering of node ids (i.e. an Xn may have a id larger than Zn).
+  // This may cause us to erroneously curtail a topological cycle checking
+  // search. Relabeling nodes is not viable in general so we resolve this
+  // by replacing all violating successor nodes id's (Zns and their successors
+  // with an id less than the largest Xn with an invalid topological id.
+
+  // Calculate a lowerbound on the maximum Xn id. Check StoreNode's Chain's id.
+  // If it is invalid, find maximum of its operands.
+
+  std::function<int(const SDValue)> getId = [&](SDValue N) -> int {
+    auto NId = N->getNodeId();
+    if (!(NId > 0))
+      for (const SDValue &Op : N->op_values())
+        NId = std::max(NId, getId(Op));
+    return NId;
+  };
+
+  int EffectiveId = getId(StoreNode->getOperand(0));
+  for (auto UI = StoredVal->use_begin(), E = StoredVal->use_end(); UI != E;
+       ++UI) {
+    if (UI.getUse().getResNo() == 1)
+      InvalidateNodeIds(*UI, EffectiveId);
+  }
+
   ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
   CurDAG->RemoveDeadNode(Node);
   return true;
 }
 
 // See if this is an (X >> C1) & C2 that we can match to BEXTR/BEXTRI.
 bool X86DAGToDAGISel::matchBEXTRFromAnd(SDNode *Node) {
   MVT NVT = Node->getSimpleValueType(0);

llvm/test/CodeGen/X86/pr36312.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+
+%struct.anon = type { i32, i32 }
+
+@c = common  global %struct.anon zeroinitializer, align 4
+@d =  local_unnamed_addr global %struct.anon* @c, align 8
+@a = common  local_unnamed_addr global i32 0, align 4
+@b = common  local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: norecurse nounwind uwtable
+define  void @g() local_unnamed_addr #0 {
+; CHECK-LABEL: g:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movq {{.*}}(%rip), %rax
+; CHECK-NEXT:    movl 4(%rax), %eax
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    incl {{.*}}(%rip)
+; CHECK-NEXT:    setne %cl
+; CHECK-NEXT:    addl %eax, %ecx
+; CHECK-NEXT:    movl %ecx, {{.*}}(%rip)
+; CHECK-NEXT:    retq
+entry:
+  %0 = load %struct.anon*, %struct.anon** @d, align 8
+  %y = getelementptr inbounds %struct.anon, %struct.anon* %0, i64 0, i32 1
+  %1 = load i32, i32* %y, align 4
+  %2 = load i32, i32* @b, align 4
+  %inc = add nsw i32 %2, 1
+  store i32 %inc, i32* @b, align 4
+  %tobool = icmp ne i32 %inc, 0
+  %land.ext = zext i1 %tobool to i32
+  %add = add nsw i32 %1, %land.ext
+  store i32 %add, i32* @a, align 4
+  ret void
+}