[LLVMbugs] [Bug 5150] New: instcombine quadratic in GEP+Phi chain length

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: instcombine quadratic in GEP+Phi 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=3624)
 --> (http://llvm.org/bugs/attachment.cgi?id=3624)
Script to generate quadratic assembly

The attached script, when passed an integer argument N, generates an LLVM
assembly file containing a chain of O(N) Phi instructions separated by GEPs:

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

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

  br i1 undef, label %l1a, label %l1b

l1a:
  %A1 = getelementptr i32* %C0, i64 1
  br label %l1c

l1b:
  %B1 = getelementptr i32* %C0, i64 1
  br label %l1c

l1c:
  %C1 = phi i32* [%A1, %l1a], [%B1, %l1b]
  call void @use(i32* %C1)

  br i1 undef, label %l2a, label %l2b

l2a:
  %A2 = getelementptr i32* %C1, i64 1
  br label %l2c

l2b:
  %B2 = getelementptr i32* %C1, i64 1
  br label %l2c

l2c:
  %C2 = phi i32* [%A2, %l2a], [%B2, %l2b]
  call void @use(i32* %C2)

  ret i32* %C2
}

It's significant here that the phi node inputs are equivalent. The instcombine
pass is quadratic when trying to optimize the chain:

$ for n in 100 200 300 400 500 600; do ./instcombine_test.py
$n|$LLVM/llvm-as|time $LLVM/opt -instcombine >/dev/null;done
        0.18 real         0.13 user         0.00 sys
        0.51 real         0.44 user         0.00 sys
        1.05 real         0.95 user         0.01 sys
        1.81 real         1.66 user         0.01 sys
        2.70 real         2.53 user         0.01 sys
        3.82 real         3.61 user         0.02 sys


Thanks to Nick for helping me find the important chain.


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