[LLVMbugs] [Bug 3936] New: Instcombine quadtratic in GEP chain length

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: Instcombine quadtratic in GEP 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: nicholas at mxc.ca, llvmbugs at cs.uiuc.edu


Created an attachment (id=2783)
 --> (http://llvm.org/bugs/attachment.cgi?id=2783)
Script to generate quadratic assembly

The attached script, when passed an integer argument N, generates an LLVM
assembly file containing a chain of 2N-1 GEP instructions:

$ ./instcombine_test.py 2
declare void @use(i32)

define void @foo(i32* %stack) {
  %B0 = getelementptr i32* %stack, i32 0

  %A1 = getelementptr i32* %B0, i32 1
  %B1 = getelementptr i32* %A1, i32 -1
  %C1 = load i32* %B1
  call void @use(i32 %C1)

  ret void
}

The instcombine pass is quadratic when trying to optimize the chain:

$ for n in 1000 2000 3000 4000 5000 6000; do ./instcombine_test.py
$n|$LLVM/llvm-as|time $LLVM/opt -instcombine >/dev/null;done
        1.03 real         0.85 user         0.01 sys
        3.22 real         2.89 user         0.03 sys
        6.55 real         5.94 user         0.05 sys
       11.40 real        10.47 user         0.10 sys
       17.82 real        16.52 user         0.16 sys
       24.73 real        23.02 user         0.21 sys


Shark reports that a very high percentage of the time is spent in
Value::getUnderlyingObject, resolving loads like %C1 down to %stack. It doesn't
appear to combine any GEPs before calling getUnderlyingObject on every load in
the function, causing quadratic work.

Thanks to Nick for the form of the testcase. I've seen the behavior in both 2.5
and trunk.


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