This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by craig.topper on Mar 17 2017, 9:54 AM.

Details

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.

Diff Detail

Event Timeline

craig.topper created this revision.Mar 17 2017, 9:54 AM
dberlin edited edge metadata.Mar 17 2017, 10:02 AM

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?

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.

Just use RPOT and kill off the local vector

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.

Add comment to PostOrderIterator.h

dberlin accepted this revision.Mar 18 2017, 5:08 AM
This revision is now accepted and ready to land.Mar 18 2017, 5:08 AM
This revision was automatically updated to reflect the committed changes.