http://llvm.org/bugs/show_bug.cgi?id=3953
Summary: Instcombine quadratic in add 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=2799)
--> (http://llvm.org/bugs/attachment.cgi?id=2799)
Generator for add chains that make instcombine quadratic
The attached script generates .ll files of the form:
$ ./instcombine_test3.py 3
declare void @use(i32)
define void @foo(i32 %B0) {
%A1 = add i32 %B0, 1
%B1 = add i32 %A1, -1
call void @use(i32 %B1)
%A2 = add i32 %B1, 1
%B2 = add i32 %A2, -1
call void @use(i32 %B2)
ret void
}
instcombine takes approximately quadratic time to simplify these chains.
$ for N in 500 1000 1500 2000 2500; do ./instcombine_test3.py
$N|$LLVM/llvm-as|time $LLVM/opt -instcombine >/dev/null; done
0.62 real 0.56 user 0.00 sys
2.28 real 2.16 user 0.01 sys
4.86 real 4.69 user 0.02 sys
8.70 real 8.38 user 0.04 sys
13.46 real 12.99 user 0.08 sys
This prevents me from applying the obvious workaround to bug 3936.
A time profile doesn't show an obvious culprit, spending 38% in
isInstructionTriviallyDead, 25% in visitCall, and 11% in visitAdd.
--
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
