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: [email protected]
ReportedBy: [email protected]
CC: [email protected], [email protected]
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.
_______________________________________________
LLVMbugs mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/llvmbugs
