[LLVMdev] qualitative comparison of correctness of llvm and gcc

[John Regehr]

Hi folks,

We recently generated some data that seemed interesting enough to share
here.  This is a comparison between compilers that ignores the
performance of the generated code and focuses only on compiler correctness.

                   volatile    checksum
                     errors      errors

avr-gcc-3.4         1.879%      0.378%
avr-gcc-4.1         0.037%      0.256%
avr-gcc-4.2         0.753%      0.225%
gcc-3.4             1.222%      0.004%
gcc-4.0             0.041%      0.026%
gcc-4.1             0.196%      0.024%
gcc-4.2             0.770%      0.004%
gcc-4.3             0.727%      0.003%
llvm-gcc-2.2       18.712%      0.110%
llvm-gcc-pre-2.4    0.000%      0.006%

Notes:

These numbers come from throwing 100,000 random C programs at the 
various compilers.  For each compiler, we compiled each test case at 
-O0, -O1, -O2, -Os, and -O3 and compared the results of these 
compilations.  Random programs that crashed a compiler, and executables 
that failed to terminate in a timely fashion, did not count towards the 
100,000.

Target is ia32 except for the top three compilers, which target AVR, an 
8-bit MCU.  Host is Ubuntu Feisty.

A "volatile error" indicates a case where a compiler failed to respect
the volatile invariant.  The volatile invariant is simply that changing
the optimization level of a strictly conforming C program must not
change the number of dynamic loads or stores to any variable that is
volatile-qualified in the compiler's input.  We check this with a hacked
valgrind (for x86) or a hacked simulator (for AVR).

A "checksum error" indicates a case where changing the optimization
level of a compiler changed the computation performed by its generated 
code in a way that is not correctness-preserving.  The checksum is taken 
over the global variables in the random program just before it terminates.

We believe that our random programs are free of unspecified and
undefined behavior (e.g. divide by zero, pointer misuse, uninitialized
variable use, dependency on order of evaluation, etc.).  Therefore,
every checksum or volatile error is the result of a real compiler bug.
We can't easily prove this.  However, whenever we look closely at an 
apparent error, it becomes possible to legitimately blame the compiler.

I don't have handy the exact svn rev of the pre-2.4 llvm that we tested
but it's from a few weeks ago.

The improvement in llvm between 2.2 and now is no doubt the result of
many factors.  I would argue that one of the most important factors was 
the llvm team's rapid fixing of 5 volatile bugs and 8 code generation 
bugs that we reported.  We didn't test 2.3 because some bugs that we 
reported were fixed before that release, some after.

Current llvm is also far harder to crash than 2.2, although we
lack statistics on this.

Since the snapshot a few weeks ago, the llvm team has fixed a few more 
bugs.  If this process continues it seems possible that within the 
foreseeable future, llvm will be effectively free of crashes, codegen 
errors, and volatile errors (for the class of random programs that we 
generate).

If anyone is curious about the kinds of bugs that are found through
random testing, a list follows.

Volatile:

   http://llvm.org/bugs/show_bug.cgi?id=2182
   http://llvm.org/bugs/show_bug.cgi?id=2234
   http://llvm.org/bugs/show_bug.cgi?id=2260
   http://llvm.org/bugs/show_bug.cgi?id=2262
   http://llvm.org/bugs/show_bug.cgi?id=2496

Codegen:

   http://llvm.org/bugs/show_bug.cgi?id=2271
   http://llvm.org/bugs/show_bug.cgi?id=2274
   http://llvm.org/bugs/show_bug.cgi?id=2276
   http://llvm.org/bugs/show_bug.cgi?id=2294
   http://llvm.org/bugs/show_bug.cgi?id=2364
   http://llvm.org/bugs/show_bug.cgi?id=2435
   http://llvm.org/bugs/show_bug.cgi?id=2479
   http://llvm.org/bugs/show_bug.cgi?id=2487
   http://llvm.org/bugs/show_bug.cgi?id=2568

Crash/hang:

   http://llvm.org/bugs/show_bug.cgi?id=2264
   http://llvm.org/bugs/show_bug.cgi?id=2323
   http://llvm.org/bugs/show_bug.cgi?id=2326
   http://llvm.org/bugs/show_bug.cgi?id=2234
   http://llvm.org/bugs/show_bug.cgi?id=2372
   http://llvm.org/bugs/show_bug.cgi?id=2422
   http://llvm.org/bugs/show_bug.cgi?id=2455
   http://llvm.org/bugs/show_bug.cgi?id=2497
   http://llvm.org/bugs/show_bug.cgi?id=2497
   http://llvm.org/bugs/show_bug.cgi?id=2513
   http://llvm.org/bugs/show_bug.cgi?id=2570

John Regehr