[DAG] Enforce stricter NodeId invariant during Instruction selection
ClosedPublic

Authored by niravd on Feb 12 2018, 9:35 AM.

Details

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

Diff Detail

Repository
rL LLVM
niravd created this revision.Feb 12 2018, 9:35 AM
niravd updated this revision to Diff 133885.Feb 12 2018, 9:38 AM
niravd edited the summary of this revision. (Show Details)

Fix PR number in test and commit message.

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

niravd updated this revision to Diff 134083.Feb 13 2018, 10:43 AM

Remove unrelated format changes.

niravd updated this revision to Diff 135273.Feb 21 2018, 9:13 AM
niravd edited the summary of this revision. (Show Details)

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

niravd updated this revision to Diff 135967.Feb 26 2018, 1:55 PM
niravd added a reviewer: jyknight.

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

Ping.

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

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)

  1. 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.
  2. Need to figure out how to check this property in a way that'll catch future errors.

Hopefully the above is correct. =)

niravd updated this revision to Diff 136830.Mar 2 2018, 12:48 PM
niravd retitled this revision from [X86] Fix Topological NodeId Ordering violation in Load-Op-Store fusion. to [DAG] Enforce stricter NodeId invariant during Instruction selection.
niravd edited the summary of this revision. (Show Details)

Change to a global fix for all NodeId ordering violation.

niravd updated this revision to Diff 137763.Mar 9 2018, 9:01 AM
niravd edited the summary of this revision. (Show Details)

Cleanup by folding EnforceNodeIdInvariant into ISel's replace functions

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 marked an inline comment as done.Mar 9 2018, 11:47 AM

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 updated this revision to Diff 137811.Mar 9 2018, 12:05 PM
niravd marked an inline comment as done.

Tweak negation as suggested by James.

jyknight accepted this revision.Mar 9 2018, 12:12 PM

OK, seems reasonable.

This revision is now accepted and ready to land.Mar 9 2018, 12:12 PM
This revision was automatically updated to reflect the committed changes.