[LLVMbugs] [Bug 10604] New: llc takes a long time in 'Induction Variable Users'

[bugzilla-daemon at llvm.org]

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

           Summary: llc takes a long time in 'Induction Variable Users'
           Product: new-bugs
           Version: 2.9
          Platform: Other
        OS/Version: FreeBSD
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: cperciva at freebsd.org
                CC: llvmbugs at cs.uiuc.edu


Created an attachment (id=7032)
 --> (http://llvm.org/bugs/attachment.cgi?id=7032)
Test case (as minimal as I can make it -- any simplifications make the problem
go away).

Background:

Users of Tarsnap (http://www.tarsnap.com/) have been complaining that builds
"hang" on OS X Lion on one particular source file (chunkify.c) if -O2 is
enabled; using gcc instead of llvm-gcc makes the problem go away.  I don't have
an OS X Lion box, but I've installed llvm-gcc4 on a FreeBSD system and while
the build doesn't *hang* it does seem that something odd is happening with this
file.

Environment:

# uname -a
FreeBSD ip-10-242-186-3 8.2-RELEASE FreeBSD 8.2-RELEASE #0: Fri Jul  8 00:54:56
UTC 2011     root at ip-10-17-33-248:/usr/obj/usr/src/sys/XENHVM  amd64
# llvm-gcc --version
llvm-gcc (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build)

llvm-gcc was installed from the FreeBSD ports tree, which claims that this is
version 2.9.

Problem:

Moving between -O1 and -O2 causes a ~200x slowdown in compilation and a ~50x
increase in object file size for the attached C source code:

# /usr/bin/time -h llvm-gcc -O1 -c foo.c ; ls -l foo.o
        0.05s real              0.04s user              0.01s sys
-rw-r--r--  1 root  wheel  1904 Aug  7 18:04 foo.o

# /usr/bin/time -h llvm-gcc -O2 -c foo.c ; ls -l foo.o
        9.11s real              8.98s user              0.12s sys
-rw-r--r--  1 root  wheel  111784 Aug  7 18:04 foo.o

Generating llvm intermediate output from llvm-gcc -O2 and then compiling it
with llc -O=0 and llc -O=1 shows an even more obvious difference between the
produced assembly code:

# llvm-gcc -emit-llvm -o foo.bc -O2 -c foo.c

# /usr/bin/time -h llc -O=0 foo.bc ; ls -l foo.s
        0.01s real              0.00s user              0.00s sys
-rw-r--r--  1 root  wheel  6085 Aug  7 18:13 foo.s

# /usr/bin/time -h llc -O=1 foo.bc ; ls -l foo.s
        8.92s real              8.83s user              0.09s sys
-rw-r--r--  1 root  wheel  678772 Aug  7 18:13 foo.s

It seems that llc is spending a long time in 'Induction Variable Users':

# llc --time-passes -O=1 foo.bc 2>&1 | grep Induction
   5.0308 ( 56.7%)   0.0000 (  0.0%)   5.0308 ( 56.3%)   5.0308 ( 56.3%) 
Induction Variable Users

So I conclude that something in this pass is exploding (in both time and size)
and is almost certainly at fault.

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