[llvm-bugs] [Bug 39544] New: simple-loop-unswitch is too aggressive in unswitching leading to compile-time issues

[via llvm-bugs]

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

            Bug ID: 39544
           Summary: simple-loop-unswitch is too aggressive in unswitching
                    leading to compile-time issues
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: fedor.v.sergeev at gmail.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 21075
  --> https://bugs.llvm.org/attachment.cgi?id=21075&action=edit
real testcase leading to excessive unswitch

On a relatively simple testcase simple-loop-unswitch goes unswitching too many
times, generating too many copies of loops and forcing compile-time to become
abnormally high.

] time ~/work/llvm-upstream/builds/linux-release/bin/opt
-enable-nontrivial-unswitch -licm -simple-loop-unswitch
after-reassociate-upstream.ll -disable-output  --stats                          

real    5m17.711s
user    4m33.670s
sys     0m0.188s
]

This testcase is a slightly simplified version of IR we generate on real java
code, so it is a very real practical issue for us.

Here is its loop structure (nothing really weird):
] ~/work/llvm-upstream/builds/linux-release/bin/opt -passes="print<loops>"
unswitch-compile-time.ll -disable-output 2>&1 | sed -n
's/\(Loop.at.depth.[0-9]*\).*/\1/p'
Loop at depth 1
Loop at depth 1
Loop at depth 1
Loop at depth 1
Loop at depth 1
Loop at depth 1
Loop at depth 1
    Loop at depth 2
    Loop at depth 2
        Loop at depth 3
            Loop at depth 4
                Loop at depth 5
                    Loop at depth 6
                        Loop at depth 7
                            Loop at depth 8
                                Loop at depth 9
                                    Loop at depth 10
                                        Loop at depth 11
                                            Loop at depth 12
                                                Loop at depth 13
                                                    Loop at depth 14
                                                    Loop at depth 14
                                                    Loop at depth 14
                                                    Loop at depth 14
]
It has ~2K lines and ~200 conditions:

] wc -l unswitch-compile-time.ll
2317 unswitch-compile-time.ll
] grep 'br i1 ' -c unswitch-compile-time.ll 
197
]

And it goes pretty fast with legacy unswitch:

] time ~/work/llvm-upstream/builds/linux-release/bin/opt
-enable-nontrivial-unswitch -licm -loop-unswitch unswitch-compile-time.ll
-disable-output

real    0m0.018s
user    0m0.018s
sys     0m0.000s
]

-- 
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/20181102/9d55b073/attachment.html>