[llvm-bugs] [Bug 40528] New: [DTU] DomTreeUpdater's Eager strategy fails to update DomTree, Lazy strategy works OK

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=40528

            Bug ID: 40528
           Summary: [DTU] DomTreeUpdater's Eager strategy fails to update
                    DomTree, Lazy strategy works OK
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: max.kazantsev at azul.com
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190130/3791e55d/attachment-0001.html>