HomePhabricator

[IDF] Enforce the returned blocks to be sorted.

Description

[IDF] Enforce the returned blocks to be sorted.

Summary:
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.

Reviewers: dberlin, davide

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D46646

Details

Committed
mzolotukhinMay 11 2018, 6:44 PM
Differential Revision
D46646: [IDF] Enforce the returned blocks to be sorted.
Parents
rL332166: [AMDGPU] Fix amdgpu-waves-per-eu accounting in scheduler
Branches
Unknown
Tags
Unknown