R-1

SASIMI 2016 Proceedings

Detecting Missed Arithmetic Optimization in C Compilers
by Diﬀerential Random Testing
Mitsuyoshi Iwatsuji 1 Atsushi Hashimoto 2 Nagisa Ishiura 1
1Kwansei Gakuin University, Sanda, Hyogo, Japan
Nomura Research Institute, Ltd., Tokyo, Japan2

1: #include <stdio.h>
2: #define OK() printf("@OK@\n")
3: #define NG(fmt,val) printf("@NG@ (test="fmt")\n",val)
4: const signed int k8 = 144011145;
5: int main (void) {6:
signed short x1 = 6;
7:
static unsigned short x2 = 1U;
8:static signed long x4 = 4542636934L;
9:
volatile signed short x7 = -1;
10:
signed long t0 = -1261917469307207940L;
11:
signed long t1 = -42079927921L;
12:
t0 = (x2^(x4+((x7+k8)>>x2)));13:
t1 = ((x4<<(x4/t0))/x1);
14:
if (t0 == 4614642507L) {OK();} else {NG("%d", t0);}15:
if (t1 == 757106155L) {OK();} else {NG("%lld", t1);}
16:
return 0;
17: }Abstract— This paper presents a method of detecting missed optimization opportunities in C compilers by diﬀerential random testing. By compilingrandomly generated test programs by two diﬀerent
compilers, or diﬀerent versions of the same compiler,and comparing the resulting pairs of assembly codes,
lack of optimization is detected. Comparison is basedon the instruction count. An experimental test system has successfully detected under-optimization in
the latest versions of GCC and Clang/LLVM.

I. Introduction
Compilers must be highly reliable, for they are infrastructure tools for software development. In addition, theperformance of generated codes is also a critical issue.
Thus, compilers must be tested for their performance aswell as for their correctness.
There have been a few attempts to detect performancebugs. Nullstone [1] is a test suite for C compilers’ optimization consisting of about 6,500 test programs. As it
is a ﬁnite set of test cases, it is inevitable that its detection ability is limited. Randprog [2] tries to ﬁnd invalid deletion of memory accesses for volatile variables
by random testing. It detects over-optimization but notunder-optimization. [3] proposed a method of detecting
under-optimization in C compilers by random testing. A
pair of equivalent programs, one is unoptimized and theother is optimized in the C language level, are compiled
and assembly codes are compared. However, in principle
it can not ﬁnd lack of stronger optimization than that
performed in the C language level.
To address this issue, this paper presents yet anothermethod of detecting missed optimization opportunities in
C compilers by diﬀerential random testing [4]. Randomly
generated test programs are compiled by diﬀerent compilers and the resulting codes are compared to detect missedoptimization. A test system based on our method has detected several under-optimization in the latest versions ofGCC and Clang/LLVM.
II. Random testing of C compilers
After validation using test suites, compilers are often
tested by randomly generated programs to detect potential bugs. Csmith [5] and Orange [6] are examples of successful random test systems for C compilers.
In this paper, we employ Orange3 [6] as a random
test generator. Fig. 1 shows an example of a test program. It veriﬁes (in lines 14–15) the resulting values of
the arithmetic expressions (in lines 12–13). The expres-Fig. 1. Test program generated by Orange3.
generate
test1.cequivalent

compilercompiler1

compile & execute

result1

comparegenerate

test2.cresult2(a) Method in [3].

test.ccompile & execute

result1

compiler2
compile & executecompareresult2(b) Proposed method.

Fig. 2. Approaches for optimization test.

sions are constructed carefully not to yield undeﬁned behavior (such as zero division or signed overﬂow). The sizeof the programs can be adjusted to the compiler under
test, which typically ranges from 500 to 10,000 lines.
Once an error is detected, the program must be minimized (reduced to an error reproducing program as smallas possible) for closer investigation. This is achieved byapplying various size reducing program transformations
as long as the error is reproduced. Orange3 has a built-in
minimizer along with the random program generator.
Although the random testing is a powerful tool to detect compilers’ crash or wrong code generation, lack ofoptimization is hard to detect by the same method, forthe compiled codes yield the same results even thoughintended optimization was not performed.
Detecting missed optimization bydifferential testingThis paper proposes a random test method to detect
missed compiler optimization by diﬀerential testing [4].
While [3] compared the assembly codes generated from apair of equivalent C programs (as in Fig. 2 (a)), we compile a randomly generated program (test.c) by two diﬀerent compilers, or diﬀerent versions of the same compiler,and compare the resulting two assembly codes (test1.sand test2.s), as illustrated in Fig. 2 (b). The test program that yields a signiﬁcant diﬀerence on the assembly-2-III.

TABLE I
Experimental results.
compiler (target) option
GCC-5.0.0 (x86 64) -O3
Clang-3.7.0 (x86 64) -O3
GCC-6.0.0 (x86 64) -O3
GCC-5.3.0 (x86 64) -O3

time [h]

#test

#diﬀ

24 ∗1

62,672593

24 ∗260,536

185

1:
2:
3:
4:
5:
6:
7:

gcc5.s (GCC-5.2.1 -O3)
main:
xorl %eax, %eax

*1 Core i5-4200U 1.60GHz, RAM 7.7GB, Ubuntu 14.10*2 Core i7-5500U 2.40GHz, RAM 7.7GB, Ubuntu 14.04

1:
2:
3:
4:
5:
6:
7:

error1.c
int main (void) {volatile signed int x = 1;
unsigned int t = ((unsigned int)1U<<x);if (t == 2U) ;else builtin abort();return 0;}

gcc.s (GCC-5.0.0 -O3)
main:
subq $24, %rsp
movl $1, %eax
movl $1, 12(%rsp)
movl 12(%rsp), %ecx
sall %cl, %eax
cmpl $2, %eax
jne.L5xorl %eax, %eax
addq $24, %rsp
ret.L5:call abort

error2.cunsigned int x = 1;
int main (void) {long long int a = -2LL;
int t = 1 <= (a/x);
if (t != 1) { builtin abort(); }return 0;}

ret

gcc6.s (GCC-6.0.0 -O3)
main:movl x(%rip), %ecx
movq $-2, %rax
cqto
idivq %rcx
testq %rax, %rax
jg .L7
xorl %eax, %eax
ret.L7
pushq %rax
call abort

Fig. 4. Error program (2).

clang.s (Clang-3.7.0 -O3)
main:pushq %rax
movl $1, 4(%rsp)
movl 4(%rsp), %eax
cmpl $1, %eax
jne.LBB0 2
xorl %eax, %eax
popq %rdx
retq
LBB0 2:
callq abort

Fig. 3. Error program (1).

codes is called an error program, which may detect underoptimization in one of the assembly codes. This method
can detect lack of optimizing transformations in one of
the compilers, which was not always possible in [3]. The
proposed method can be also used for regression test; if
an older version produces better codes than the latest
version, there must be some degeneration.
There are many possible ways of comparing assemblycodes. In this paper, we adopt a simple method based on
the instruction count. This is based on our observationthat the assembly codes from the same C program areusually very similar. Let n and m be the numbers of
the instructions in the two assembly codes where n <m. Then, two codes are judged to be diﬀerent if n/m issmaller than a threshold.
Error programs are minimized for closer investigation.
The same set of program transformations as Orange3 isused. For example, if x1 and x2 are known to evaluate to
3 and 5, respectively, expression x1+x2 is reduced to x1+5,
then to 3+5 and 8. Reduction is repeated automatically as
long as the resulting assembly codes reproduce diﬀerences.
IV. Experimental results
A test system based on the proposed method has beendeveloped in Perl5 and runs on Linux. Results of experiments are summarized in Table I. The ﬁrst test was run
on GCC-5.0.0 and Clang-3.7.0 with the -O3 option. In
24 hours, 62,672 cases were tested and 593 programs detected diﬀerences in the assembly codes. The other test
was on diﬀerent versions of GCC. In 24 hours, 185 out of60,536 programs detected diﬀerences. The thresholds forcomparison were set to 0.6 and 0.7 in the ﬁrst and the second runs, respectively. All the error programs were manually inspected after minimization. Among them, there
were cases where we could not tell if they detected lack ofoptimization, but some revealed defects.
Fig. 3 shows one of the error programs in the ﬁrst test.
Code gcc.s faithfully computes the sequence speciﬁed insource code error1.c, for x is a volatile variable. On theother hand, clang.s just tests if x==1 and omits all theother computation. We can conclude that GCC-5.0.0 has
missed an opportunity for this optimization. Fig. 4 is anerror program from the second test run. Code gcc5.s isapparently succinct than gcc6.s, which means that there
has been some regression in GCC-6.0.0. We have so far
reported 2 bugs to Clang/LLVM1 , and 3 bugs to GCC2
detected by our test system.
V. Conclusion
The paper has presented a new random test method
to detect lack of arithmetic optimization in C compilers.
The current system generates a considerable number offalse positive error programs, so we are now working on
improvement on the method of assembly code comparison.
Acknowledgement
Authors would like to thank all the members of IshiuraLab. of Kwansei Gakuin University. This work was partly
supported by JSPS KAKENHI Grant Number 25330073.

References[1] Nullstone Corporation: Nullstone for C (online), http://www.nullstone.com/.
[2] E. Eide and J. Regehr: “Volatiles are miscompiled, andwhat to do about it,” in Proc. EMSOFT, pp. 255–264 (Oct.
2008).
[3] A. Hashimoto and N. Ishiura: “Detecting arithmetic optimization opportunities for C compilers by randomly generated equivalent programs,” IPSJ Trans. SLDM, vol. 9,
pp. 21–29 (Feb. 2016).
[4] R. B. Evans and A. Savoia: “Diﬀerential testing: A new
approach to change detection,” in Proc. ACM ESEC-FSE,
pp. 549–552 (Sept. 2007).
[5] X. Yang, Y. Chen, E. Eide, and J. Regehr: “Finding andunderstanding bugs in C compilers,” in Proc. ACM PLDI,
pp. 283–294 (June 2011).
[6] E. Nagai, A. Hashimoto, and N. Ishiura: “Reinforcing random testing of arithmetic optimization of C compilers byscaling up size and number of expressions,” IPSJ Trans.
SLDM, vol. 7, pp. 91–100 (Aug. 2014).

-3-

1 https://llvm.org/bugs/

id=23673, 23672
id=66299, 68026, 68431

2 https://gcc.gnu.org/bugzilla/