Page MenuHomePhabricator

SCC: Allow ReplaceNode to safely support insertion
ClosedPublic

Authored by wristow on Thu, Jan 9, 11:22 AM.

Details

Summary

If scc_iterator::ReplaceNode is inserting a new entry in the map,
rather than replacing an existing entry, the possibility of growing
the map could cause a failure. This change safely implements the
insertion.

Explanation/justification for this change:

This is a simple change of splitting the assignment in the following code:

  void ReplaceNode(NodeRef Old, NodeRef New) {
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];  // Split this assignment.
    nodeVisitNumbers.erase(Old);
}

into two steps:

auto tempVal = nodeVisitNumbers[Old];
nodeVisitNumbers[New] = tempVal;

so that the evaluation of the original RHS is guaranteed to be completed before we evaluate the LHS (since the assignment operator isn't a sequence-point). The problem is that if New is not in the map, then the evaluation of the original LHS may grow the map, which if the original RHS has been partially evaluated, may invalidate values computed during that partial evaluation. By splitting this into two statements, the original RHS is guaranteed to be safely evaluated before the possibility of growing the map while evaluating the original LHS "has a chance to invalidate" that computation.

We encountered this in a very large test-case, that resisted attempts at reducing it. So I'm proposing this without a test-case for it.

As an aside, in running tests, it seems that New is very rarely in the map. That is, this is almost always an insertion of New (followed by a removal of Old), rather than a replacement of a pre-existing New entry. Specifically, adding an assert verifying that New is not already in the map virtually never fails (it only triggered one time in the Unit and LIT tests, and it never triggered at all in my large test-case that exposed the bug being addressed here). So it seems that it is nearly always inserting (rather than replacing), and so often runs the risk of growing the map. That said, even when the map does grow, if the host compiler happens to generate code that wraps-up the evaluation of original RHS before the growth, or if the growth doesn't invalidate the old data of the pre-growth-map, the compilation will succeed. (FTR, we encountered this where the hosting environment used to build Clang was Microsoft Visual Studio 2017.)

Diff Detail

Event Timeline

wristow created this revision.Thu, Jan 9, 11:22 AM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Jan 9, 11:22 AM
probinson accepted this revision.Tue, Jan 14, 7:24 AM
probinson added a subscriber: probinson.

Seems to me we've needed to do this sort of tweak before, so LGTM.
Because it depends on the memory-management behavior of the map, it would be tricky to test with IR input. Would it be feasible to do something in llvm/unittests/ADT/SCCIteratorTest.cpp that could trigger this reliably? Can be done as a follow-up, as I know the branch is coming soon.

This revision is now accepted and ready to land.Tue, Jan 14, 7:24 AM
This revision was automatically updated to reflect the committed changes.

Seems to me we've needed to do this sort of tweak before, so LGTM.
Because it depends on the memory-management behavior of the map, it would be tricky to test with IR input. Would it be feasible to do something in llvm/unittests/ADT/SCCIteratorTest.cpp that could trigger this reliably? Can be done as a follow-up, as I know the branch is coming soon.

Thanks for that @probinson. I'll look into the unittest approach.