SCC: Allow ReplaceNode to safely support insertion

[wristow]

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.)

[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.

[wristow]

In D72469#1819623, @probinson wrote:

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.

llvm/include/llvm/ADT/SCCIterator.h

public:
   /// If the SCC has more than one node, this is trivially true.  If not, it may
   /// still contain a loop if the node has an edge back to itself.
   bool hasLoop() const;
 
   /// This informs the \c scc_iterator that the specified \c Old node
   /// has been deleted, and \c New is to be used in its place.
   void ReplaceNode(NodeRef Old, NodeRef New) {
     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
-    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
+    // Do the assignment in two steps, in case 'New' is not yet in the map, and
+    // inserting it causes the map to grow.
+    auto tempVal = nodeVisitNumbers[Old];
+    nodeVisitNumbers[New] = tempVal;
     nodeVisitNumbers.erase(Old);
   }
 };
 
 template <class GraphT, class GT>
 void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
   ++visitNum;
   nodeVisitNumbers[N] = visitNum;