[LLVMbugs] [Bug 3944] New: mem2reg quadratic in number of in-edges to block receiving a new phi node

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: mem2reg quadratic in number of in-edges to block
                    receiving a new phi node
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: minor
          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=2784)
 --> (http://llvm.org/bugs/attachment.cgi?id=2784)
Script to make mem2reg quadratic

The attached script generates LLVM asm that triggers quadratic behavior in
mem2reg. The code looks like:

$ ./mem2reg_test.py 1
declare i1 @test()

define i32 @foo() {
entry:
  %retval_addr = alloca i32
  store i32 1, i32* %retval_addr
  %cond = call i1 @test()
  br i1 %cond, label %return_block, label %block0

block0:
  store i32 0, i32* %retval_addr
  %cond0 = call i1 @test()
  br i1 %cond0, label %return_block, label %block1

block1: br label %return_block
return_block:
  %retval = load i32* %retval_addr
  ret i32 %retval
}


After mem2reg, that's:

$ ./mem2reg_test.py 1|$LLVM/llvm-as|$LLVM/opt -mem2reg|$LLVM/llvm-dis
; ModuleID = '<stdin>'

declare i1 @test()

define i32 @foo() {
entry:
        %cond = call i1 @test()         ; <i1> [#uses=1]
        br i1 %cond, label %return_block, label %block0

block0:         ; preds = %entry
        %cond0 = call i1 @test()                ; <i1> [#uses=1]
        br i1 %cond0, label %return_block, label %block1

block1:         ; preds = %block0
        br label %return_block

return_block:           ; preds = %block1, %block0, %entry
        %retval_addr.0 = phi i32 [ 0, %block1 ], [ 0, %block0 ], [ 1, %entry ] 
        ; <i32> [#uses=1]
        ret i32 %retval_addr.0
}


mem2reg is quadratic in the number of arguments to the %retval_addr.0 phi node,
I believe because of the loop at the top of PromoteMem2Reg::RenamePass() that
starts with "for (unsigned i = 0, e = APN->getNumIncomingValues(); i != e;
++i)"

$ for N in 5000 10000 15000 20000 25000 30000; do ./mem2reg_test.py
$N|$LLVM/llvm-as|time $LLVM/opt -mem2reg > /dev/null; done
        1.09 real         0.66 user         0.01 sys
        2.83 real         1.96 user         0.03 sys
        5.38 real         3.97 user         0.05 sys
        8.54 real         6.62 user         0.08 sys
       12.22 real         9.92 user         0.11 sys
       16.67 real        13.90 user         0.11 sys

For comparison, llvm-as takes 0.33s for the 5000-block case, and goes up
linearly from there.

I'm marking this as "minor" because I only ran into it in the context of return
blocks, and I can work around it by manipulating the phi node myself.


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