[LLVMbugs] [Bug 5860] New: simplifycfg quadratic on sequence of br (load!=0) %end, %next blocks

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: simplifycfg quadratic on sequence of br (load!=0) %end,
                    %next blocks
           Product: libraries
           Version: trunk
          Platform: PC
        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=3972)
 --> (http://llvm.org/bugs/attachment.cgi?id=3972)
Script to generate assembly that shows quadratic behavior in simplifycfg

The attached script, when passed an integer argument N, generates an LLVM
assembly file containing O(N) basic blocks where each one does a load, a
compare and conditional jump either to the end of the function or to the next
basic block.  Example:

$ ./simplifycfg-test.py 3

@MyGlobal = global i32 0

define void @foo() {

L0:
  %a0 = load i32* @MyGlobal
  %b0 = icmp ne i32 %a0, 0
  br i1 %b0, label %end, label %L1

L1:
  %a1 = load i32* @MyGlobal
  %b1 = icmp ne i32 %a1, 0
  br i1 %b1, label %end, label %L2

L2:
  %a2 = load i32* @MyGlobal
  %b2 = icmp ne i32 %a2, 0
  br i1 %b2, label %end, label %L3

L3:
  br label %end

end:
  ret void
}

The simplifycfg pass is quadratic on this input:

$ for B in 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000; do
./simplifycfg-test.py $B | llvm-as | time -f "real %e" opt -simplifycfg -f >
/dev/null; done
real 0.35
real 1.17
real 2.48
real 4.39
real 6.71
real 9.75
real 13.03
real 17.07
real 21.60
real 26.71


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