[DTU] DomTreeUpdater's Eager strategy fails to update DomTree, Lazy strategy works OK; need to fix or clarify the documentation

[llvmbot]

Bugzilla Link	40528
Resolution	FIXED
Resolved on	Feb 22, 2019 21:16
Version	trunk
OS	Windows NT
Reporter	LLVM Bugzilla Contributor
CC	@kuhar
Fixed by commit(s)	r354437

Extended Description

I wrote a unit test https://reviews.llvm.org/D57448 which demonstrates that DTU with Eager strategy fails to update the DomTree properly. Apply the patch and run unit tests. The failure looks like:

1 FAILED TEST DominatorTree is different than a freshly computed one! Current: =============================-------------------------------- Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries. [1] %BB {4294967295,4294967295} [0] [2] %BB1 {4294967295,4294967295} [1] [3] %BB17 {4294967295,4294967295} [2] [3] %BB2 {4294967295,4294967295} [2] [4] %Split {4294967295,4294967295} [3] [5] %BB3 {4294967295,4294967295} [4] [6] %BB4 {4294967295,4294967295} [5] [7] %BB5 {4294967295,4294967295} [6] [8] %BB16 {4294967295,4294967295} [7] [8] %BB15 {4294967295,4294967295} [7] [8] %BB14 {4294967295,4294967295} [7] [8] %BB13 {4294967295,4294967295} [7] [8] %BB12 {4294967295,4294967295} [7] [8] %BB11 {4294967295,4294967295} [7] [8] %BB8 {4294967295,4294967295} [7] [9] %BB28 {4294967295,4294967295} [8] [9] %BB27 {4294967295,4294967295} [8] [9] %BB26 {4294967295,4294967295} [8] [9] %BB23 {4294967295,4294967295} [8] [9] %BB24 {4294967295,4294967295} [8] [9] %BB25 {4294967295,4294967295} [8] [9] %BB29 {4294967295,4294967295} [8] [9] %BB22 {4294967295,4294967295} [8] [9] %BB20 {4294967295,4294967295} [8] [9] %BB21 {4294967295,4294967295} [8] [8] %BB10 {4294967295,4294967295} [7] [8] %BB9 {4294967295,4294967295} [7] [8] %BB7 {4294967295,4294967295} [7] [4] %BB19 {4294967295,4294967295} [3]

    Freshly computed tree:

=============================-------------------------------- Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries. [1] %BB {4294967295,4294967295} [0] [2] %BB1 {4294967295,4294967295} [1] [3] %BB17 {4294967295,4294967295} [2] [3] %BB2 {4294967295,4294967295} [2] [4] %Split {4294967295,4294967295} [3] [5] %BB3 {4294967295,4294967295} [4] [6] %BB4 {4294967295,4294967295} [5] [7] %BB5 {4294967295,4294967295} [6] [8] %BB16 {4294967295,4294967295} [7] [8] %BB15 {4294967295,4294967295} [7] [8] %BB14 {4294967295,4294967295} [7] [8] %BB13 {4294967295,4294967295} [7] [8] %BB12 {4294967295,4294967295} [7] [8] %BB11 {4294967295,4294967295} [7] [8] %BB8 {4294967295,4294967295} [7] [9] %BB28 {4294967295,4294967295} [8] [9] %BB27 {4294967295,4294967295} [8] [9] %BB26 {4294967295,4294967295} [8] [9] %BB23 {4294967295,4294967295} [8] [9] %BB24 {4294967295,4294967295} [8] [9] %BB25 {4294967295,4294967295} [8] [9] %BB29 {4294967295,4294967295} [8] [10] %BB6 {4294967295,4294967295} [9] [9] %BB22 {4294967295,4294967295} [8] [9] %BB20 {4294967295,4294967295} [8] [9] %BB21 {4294967295,4294967295} [8] [8] %BB10 {4294967295,4294967295} [7] [8] %BB9 {4294967295,4294967295} [7] [8] %BB7 {4294967295,4294967295} [7] [4] %BB19 {4294967295,4294967295} [3]

If we use Lazy update strategy instead of Eager, the very same tests passes.

I stepped over it while working on improving LoopSimplifyCFG. I worked this bug around by patch https://reviews.llvm.org/D57316. But it seems that it is a very fundamental problem that compromises the DomTree updater.

[llvmbot]

The Eager update strategy of DTU is only a bare wrapper of relevant functions of the underlying DominatorTree class. And the insertEdge()/deleteEdge() function of the DominatorTree class cannot handle multiple updates safely.

There are also relevant issues on DominatorTree involving this before: https://reviews.llvm.org/rL338184 "It's generally not possible to safely call insert/deleteEdge multiple times" https://reviews.llvm.org/D49925 "AFAIU, for multiple CFG changes, DT should be updated using batch updates, vs consecutive addEdge and removeEdge calls."

I'll create a patch to clarify this issue in the document. Thanks for the report!

[llvmbot]

I.e. the comment for deleteEdge says

"Notify all available trees on an edge deletion.

If both DT and PDT are nullptrs, this function discards the update. Under either Strategy, self-dominance update will be removed. The Eager Strategy applies the update immediately while the Lazy Strategy queues the update. It is recommended to only use this method when you have exactly one deletion (and no insertions). It is recommended to use applyUpdates() in all other cases. This function has to be called after making the update on the actual CFG. An internal functions checks if the edge doesn't exist in the CFG in DEBUG mode."

If it's not a bug, then the phrase "It is recommended to only use this method when you have exactly one deletion" should be replaced with something more obliging, like "It is only legal to use this method to..."

[llvmbot]

Let's keep it open then. If you think it's not a bug, feel free to close as invalid and update the doc. Otherwise, please close it when it is fixed.

[kuhar]

Will try to take a look later this week. Thanks for the unit test.

[llvmbot]

assigned to @kuhar