[LLVMbugs] [Bug 3953] New: Instcombine quadratic in add chain length

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=3953

           Summary: Instcombine quadratic in add chain length
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Scalar Optimizations
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: jyasskin at google.com
                CC: llvmbugs at cs.uiuc.edu, nlewycky at google.com


Created an attachment (id=2799)
 --> (http://llvm.org/bugs/attachment.cgi?id=2799)
Generator for add chains that make instcombine quadratic

The attached script generates .ll files of the form:

$  ./instcombine_test3.py 3
declare void @use(i32)

define void @foo(i32 %B0) {

  %A1 = add i32 %B0, 1
  %B1 = add i32 %A1, -1
  call void @use(i32 %B1)

  %A2 = add i32 %B1, 1
  %B2 = add i32 %A2, -1
  call void @use(i32 %B2)

  ret void
}

instcombine takes approximately quadratic time to simplify these chains.

$ for N in 500 1000 1500 2000 2500; do ./instcombine_test3.py
$N|$LLVM/llvm-as|time $LLVM/opt -instcombine >/dev/null; done
        0.62 real         0.56 user         0.00 sys
        2.28 real         2.16 user         0.01 sys
        4.86 real         4.69 user         0.02 sys
        8.70 real         8.38 user         0.04 sys
       13.46 real        12.99 user         0.08 sys

This prevents me from applying the obvious workaround to bug 3936.

A time profile doesn't show an obvious culprit, spending 38% in
isInstructionTriviallyDead, 25% in visitCall, and 11% in visitAdd.


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.