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

[Quuxplusone]

Bugzilla Link	PR40528
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Max Kazantsev (max.kazantsev@azul.com)
Reported on	2019-01-30 06:09:03 -0800
Last modified on	2019-02-22 21:16:43 -0800
Version	trunk
Hardware	PC Windows NT
CC	htmldeveloper@gmail.com, kubakuderski@gmail.com, llvm-bugs@lists.llvm.org, simachijun@gmail.com
Fixed by commit(s)	rL354437
Attachments
Blocks
Blocked by
See also

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.

[Quuxplusone]

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

[Quuxplusone]

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.

[Quuxplusone]

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..."

[Quuxplusone]

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!