Page MenuHomePhabricator

[IDF] Enforce the returned blocks to be sorted.

Authored by mzolotukhin on May 9 2018, 9:40 AM.



Currently the order of blocks returned by IDF::calculate can be
non-deterministic. This was discovered in several attempts to enable
SSAUpdaterBulk for JumpThreading (which led to miscompare in bootstrap between
stage 3 and stage4). Originally, the blocks were put into a priority queue with
a depth level as their key, and this patch adds a DFSIn number as a second key
to specify a deterministic order across blocks from one level.

The solution was suggested by Daniel Berlin.

Diff Detail


Event Timeline

mzolotukhin created this revision.May 9 2018, 9:40 AM
dberlin accepted this revision.May 11 2018, 5:44 PM

Looks good to me. You may want to make a unit test for this.
It should only require three blocks.

This revision is now accepted and ready to land.May 11 2018, 5:44 PM
This revision was automatically updated to reflect the committed changes.