[LLVMbugs] [Bug 5361] New: break-crit-edges quadratic in number of operands of Phi node

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: break-crit-edges quadratic in number of operands of Phi
                    node
           Product: libraries
           Version: trunk
          Platform: PC
               URL: http://spreadsheets.google.com/ccc?key=tFEKYR-
                    Xt4iIfZJXOat_y9g
        OS/Version: Windows XP
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Scalar Optimizations
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: abbeyj at gmail.com
                CC: llvmbugs at cs.uiuc.edu, nlewycky at google.com,
                    jyasskin at google.com


Created an attachment (id=3733)
 --> (http://llvm.org/bugs/attachment.cgi?id=3733)
Script to generate assembly that shows quadratic behavior in break-crit-edges

The attached script, when passed an integer argument N, generates an LLVM
assembly file containing O(N) basic blocks and one Phi with O(N) operands.

$ ./previter-test.py 3
define i32* @foo(i32* %stack) {

l0:
  %C0 = getelementptr i32* %stack, i32 0
  %x0 = load i32* %C0
  %y0 = icmp eq i32 %x0, 0
  br i1 %y0, label %end, label %l1

l1:
  %C1 = getelementptr i32* %stack, i32 1
  %x1 = load i32* %C1
  %y1 = icmp eq i32 %x1, 0
  br i1 %y1, label %end, label %l2

l2:
  %C2 = getelementptr i32* %stack, i32 2
  %x2 = load i32* %C2
  %y2 = icmp eq i32 %x2, 0
  br i1 %y2, label %end, label %l3

l3:
  %C3 = bitcast i32* null to i32*
  br label %end

end:
  %retval = phi i32* [%C0, %l0], [%C1, %l1], [%C2, %l2], [%C3, %l3]
  ret i32* %retval
}

The time to run
$ ./previter-test.py $x | llvm-as | opt -break-crit-edges > /dev/null
for various values of x is available at:
http://spreadsheets.google.com/ccc?key=tFEKYR-Xt4iIfZJXOat_y9g
Red is experimentally collected data.  Blue is an O(x^2) curve that I fit to
that data.


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