This is an archive of the discontinued LLVM Phabricator instance.

[RewriteStatepointsForGC] Make base pointer inference deterministic
ClosedPublic

Authored by reames on Sep 4 2015, 11:31 AM.

Details

Summary

Previously, the base pointer algorithm wasn't deterministic. The core fixed point was (of course), but we were inserting new nodes and optimizing them in an order which was unspecified and variable. We'd somewhat hacked around this for testing by sorting by value name, but that doesn't solve the general determinism problem.

Instead, we can use the order of traversal over the def/use graph to give us a single consistent ordering. Today, this is a DFS order, but the exact order doesn't mater provided it's deterministic for a given input.

(Q: It is safe to rely on a deterministic order of operands right?)

Note that this only fixes the determinism within a single inference step. The inference step is currently invoked many times in a non-deterministic order. That's the next change in the sequence. :)

Diff Detail

Repository
rL LLVM

Event Timeline

reames updated this revision to Diff 34051.Sep 4 2015, 11:31 AM
reames retitled this revision from to [RewriteStatepointsForGC] Make base pointer inference deterministic.
reames updated this object.
reames added a reviewer: sanjoy.
reames added a subscriber: llvm-commits.
sanjoy edited edge metadata.Sep 7 2015, 3:59 PM

I'm not a 100% sure about this, but I think we can just use a MapVector for the states variable and then not track the extra VisitOrder. If you've already considered using MapVector and it does not work for some reason then this change lgtm, otherwise please use MapVector.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
817 ↗(On Diff #34051)

Can we just typedef MapVector<Value *, BDVState> ConflictStateMapTy; instead, and then instead of maintaining an extra VisitOrder insert into states instead of VisitOrder.insert(Base)?

986 ↗(On Diff #34051)

The naming here is weird -- how about Instruction *I = ...? Fine to do as a follow up change.

987 ↗(On Diff #34051)

In that follow up change, I think state should be renamed to State in keeping with LLVM coding style.

reames updated this revision to Diff 34382.Sep 9 2015, 4:23 PM
reames edited edge metadata.

Update per Sanjoy's comments. Naming changes will follow in separate change.

sanjoy accepted this revision.Sep 9 2015, 4:25 PM
sanjoy edited edge metadata.

lgtm

This revision is now accepted and ready to land.Sep 9 2015, 4:25 PM
This revision was automatically updated to reflect the committed changes.