-O1 compilation uses all memory and fails on 32- and 64-bit Ubuntu 10.10 installs

[llvmbot]

Bugzilla Link	8679
Resolution	FIXED
Resolved on	Nov 30, 2010 14:23
Version	2.8
OS	Linux
Attachments	GPLed C99 code after clang -E, fails with -O1, Shortened C89 code, fails with -O1, Further shortened C89 code, fails with -O1
Reporter	LLVM Bugzilla Contributor
CC	@lattner

Extended Description

clang -c -o /dev/null naco_img_jitter_cpp.c

succeeds in about 0.3s. However,

clang -c -o /dev/null naco_img_jitter_cpp.c -O1

will run and allocate memory via brk() and later also mmap()
until mmap() returns ENOMEM and the compilation fails.

The problem also occurs with -O2.

The system runs 64-bit Ubuntu 10.10 with

$ clang --version
clang version 2.8 (branches/release_28)
Target: x86_64-pc-linux-gnu
Thread model: posix

The problem is also present on a 32-bit Ubuntu 10.10 with

$ clang --version
clang version 2.8 (branches/release_28)
Target: i386-pc-linux-gnu
Thread model: posix

The attached source code example has been generated with clang -E from GPL C99 source code that compiles and runs as expected with various versions of gcc.

[llvmbot]

A notable requirement for triggering the problem is 32 (or more) goto statements guarded by an if statement with a logical or of an integer expression and a call to some function.

The problem is triggered also without the -c option.

The bug also affects llvm-gcc-4.2 of Ubuntu 10.10 and clang 2.7 of Ubuntu 10.04.

[llvmbot]

On a 32-bit Ubuntu 10.10 installation the problem is also seen with dragonegg (v. 2.8), i.e. with this command:

/usr/bin/gcc-4.5 -fplugin=/usr/lib/gcc/i686-linux-gnu/4.5/plugin/dragonegg.so -c -o /dev/null naco_img_jitter_cpp.c -O1

This is not reproducible on a 64-bit Ubuntu 10.10 installation (and it is not reproducible without the -fplugin option).

[llvmbot]

It reproduces on darwin. It will terminate eventually if your machine has enough memory, it just hits an edge case of a slow algorithm.

Problem is the UsersOfOverdefinedPHIs logic in SCCP.cpp. markEdgeExecutable calls visitPHINode on each PHI. There are 2 PHIs, both Overdefined, feeding into a icmp which is not Overdefined; yet, the result of the icmp is constant because the incoming values from the PHIs match in all cases. There is extensive code to detect this case down in visitICmp, which records {PHI, icmp} pairs in UsersOfOverdefinedPHIs. Fair enough. Next edge, it runs through all the users in UsersOfOverdefinedPHIs, and does visitICmp again, resulting in another {PHI, icmp} pair for each. So, the number of elements doubles with each edge. It takes an unlikely input to set this off, but I think it's been there since original implementation in 2004.

Best fix isn't clear to me. Intuitively we want to check whether the pair is already there before adding another one, but that doesn't seem to be easy with a multimap. Perhaps a different data structure? but a multimap fits very well otherwise.

[llvmbot]

Intuitively we want to check whether the pair is
already there before adding another one

Thanks for looking into this.

I could not quite follow the reasoning behind the above suggestion, so I would just like to point out that my 3rd attachment to trigger the problem was the simplest/shortest possible example I could create, since I figured this would help investigate the problem.

However, while the shortened code has a number of identical if-statements, the
original code that triggers the problem has some variation in the logical expressions of the if-statements that guard the goto-statements.

So if the above-mentioned check is implemented, it may be a good idea to also validate it on my first attachment to this ticket, which is a cpp-processed version of the original code. It is the last function in the 1st attachment that also triggers the problem.

Thanks again.

[llvmbot]

It is the last function in the 1st attachment

Oops, no, it is the 6th last function in the (not-so-readable) 1st attachment

that also triggers the problem.

[llvmbot]

Fixed in 120457.