[GVN] Fix accidental double storage of the function BasicBlock list in iterateOnFunction

[craig.topper]

Summary

iterateOnFunction creates a ReversePostOrderTraversal object which does a post order traversal in its constructor and stores the results in an internal vector. Iteration over it just reads from the internal vector in reverse order.

The GVN code seems to be unaware of this and iterates over ReversePostOrderTraversal object and makes a copy of the vector into a local vector. (I think at one point in time we used a DFS here instead which would have required the local vector).

The net affect of this is that we have two vectors containing the basic block list. As I didn't want to expose the implementation detail of ReversePostOrderTraversal's constructor to GVN, I've changed the code to do an explicit post order traversal storing into the local vector and then reverse iterate over that.

I've also removed the reserve(256) since the ReversePostOrderTraversal wasn't doing that. I can add it back if we thinks it important. Though it seemed weird that it wasn't based on the size of the function.

[• dberlin]

A few things:

1. It looks like you could just use RPOT and remove bbvect here, since it's wrong, the rpot will not be invalidated :)
2. The other traditional solution we use is to just allow the iterator to have an external set for the storage.

I would rather see us do that (which seems pretty trivial), or at best, a function to fill rpot into an array that is part of postorderiterator.h

But it seems simply changing this not to have bbvect will work just as well, so i'd say we do that?

[craig.topper]

I was afraid of making the assumption about how RPOT works in case someone made it behave differently in the future. But I can change it to use RPOT if that's what you'd prefer.

[craig.topper]

Just use RPOT and kill off the local vector

[• dberlin]

In D31084#703946, @craig.topper wrote:

I was afraid of making the assumption about how RPOT works in case someone made it behave differently in the future.

Honestly, I would just document (in the RPO description) that it's guaranteed not to invalidate when bb's go away, *but* it may contain erased based blocks, document that things are relying on this semantic (cite at least GVN), and declare victory.

I think it's more important that the invariant things are relying on is documented than worrying about someone wanting to change it.

[craig.topper]

Add comment to PostOrderIterator.h

include/llvm/ADT/PostOrderIterator.h

 //
 // This is used to visit basic blocks in a method in reverse post order.  This
 // class is awkward to use because I don't know a good incremental algorithm to
 // computer RPO from a graph.  Because of this, the construction of the
 // ReversePostOrderTraversal object is expensive (it must walk the entire graph
 // with a postorder iterator to build the data structures).  The moral of this
 // story is: Don't create more ReversePostOrderTraversal classes than necessary.
 //
+// Because it does the traversal in its constructor, it won't invalidate when
+// BasicBlocks are removed, *but* it may contain erased blocks. Some places
+// rely on this behavior (i.e. GVN).
+//
 // This class should be used like this:
 // {
 //   ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
 //      ...
 //   }
 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
 //      ...

lib/Transforms/Scalar/GVN.cpp

 }
 
 /// Executes one iteration of GVN
 bool GVN::iterateOnFunction(Function &F) {
   cleanupGlobalSets();
 
   // Top-down walk of the dominator tree
   bool Changed = false;
-  // Save the blocks this function have before transformation begins. GVN may
-  // split critical edge, and hence may invalidate the RPO/DT iterator.
-  //
-  std::vector<BasicBlock *> BBVect;
-  BBVect.reserve(256);
   // Needed for value numbering with phi construction to work.
+  // RPOT walks the graph in its constructor and will not be invalidated during
+  // processBlock.
   ReversePostOrderTraversal<Function *> RPOT(&F);
-  for (ReversePostOrderTraversal<Function *>::rpo_iterator RI = RPOT.begin(),
-                                                           RE = RPOT.end();
-       RI != RE; ++RI)
-    BBVect.push_back(*RI);
-
-  for (std::vector<BasicBlock *>::iterator I = BBVect.begin(), E = BBVect.end();
-       I != E; I++)
-    Changed |= processBlock(*I);
+  for (BasicBlock *BB : RPOT)
+    Changed |= processBlock(BB);
 
   return Changed;
 }
 
 void GVN::cleanupGlobalSets() {
   VN.clear();
   LeaderTable.clear();
   TableAllocator.Reset();