[llvm-bugs] [Bug 50223] New: Bad time complexity in Straight Line Strength Reduce ?

[via llvm-bugs]

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

            Bug ID: 50223
           Summary: Bad time complexity in Straight Line Strength Reduce ?
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: mikael.holmen at ericsson.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 24826
  --> https://bugs.llvm.org/attachment.cgi?id=24826&action=edit
bbi-55824.ll reproducer

It looks like something in slsr has bad time complexity, where increasing the
size of a basic block with 6 instructions makes the execution time increase
with a factor 4.

Reproducer:
 opt -slsr -o /dev/null bbi-55824.ll

The reproducer above seems too hang, but perhaps it finishes at some point.

However, in the input file I've made a few comments:
; 3s
; 12s
; 45s
; 3m
; 12m

If commenting out all instructions (except the ending "rets") after the "3s"
comment, execution time is roughly 3 seconds on my machine. If instead
commenting out everything after "12s" it takes 12 seconds etc.

So it looks like every 6 new instructions makes the execution time increase
with a factor 4.

-- 
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/20210505/1a1b1ea4/attachment.html>