2015 年電子情報通信学会基礎・ 境界ソ サイ エ テ ィ 大会

A-3-1

差分ランダムテストに基づくコンパイラの最適化機会の検出
Detecting Missed Oppotunities in Compiler Optimization by Diﬀerential Random Testing
橋本淳史 ∗Atsushi Hashimoto

岩辻光功
Mitsuyoshi Iwatsuji
関西学院大学 理工学部

School of Science and Technology, Kwansei Gakuin University

はじめにコンパイラには高い信頼性とともに高い最適化の性能が求められる. このため, コンパイラのテストにおいては, 生成されるコードが正しいかのみならず, 意図通りの最適化が行われているかどうかも重要なテスト項目になる. 文献 [1] では, 2 つの等価なテストプログラムをコンパイルし, 得られたアセンブリコードを比較することによって最適化機会の逸失を検出している. しかしこの手法では, コンパイラが両方のプログラムに対して最適化を行えないことは検出できない. そこで本稿では, 差分テスト [2] に基づく最適化機会の検出手法を提案する.

は, 式の削減や部分式の定数への置換等のプログラム縮約操作を差分が生じる限り繰り返すことにより行う.
表 1 実験結果

1compiler (target) option #test #diﬀ
GCC-5.0.0 (x86 64) -O362,672 593
Clang-3.7.0 (x86 64) -O3
24 時間 (Ubuntu 14.10, Core i5-4200U 1.60GHz, RAM 7.7GB)

実験結果
本手法に基づくテストシステムを Perl で実装した.
GCC-5.0.0 と Clang-3.7.0 (いずれも-O3 オプション) に対し, 閾値を 0.6 としてテストを 24 時間行った. 結果
を表１に示す. 総テスト数は 62,672 であり, そのうち593 個で差分を検出した. 最小化したプログラムの一つを図 3 に示す. Clang が生成するコードの方が簡潔であり, GCC の最適化が不十分であることがわかる. 本手法により検出した最適化機会の逸失は, GCC に 1 件 1 ,Clang/LLVM に 2 件 2 それぞれ報告している.

4

C コンパイラランダムテストシステム Orange3
Orange3 [3] は, C コンパイラの算術最適化を対象としたランダムテストシステムであり, 図 1 のようなプログラムによって算術式 (13–14 行目) に対するコードが正しく生成されているかどうかをテストする. 式数, 式の形, 演算子, 変数の型および初期値は設定に基づきランダムに決定される. ゼロ除算等の未定義動作は式生成時に回避される.
2test.c
int main (void){
volatile signed int x = 1;
unsigned int t = ((unsigned int)1U<<x);if (t == 2U) ;else builtin abort();return 0;}

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: {7:signed short x1 = 6;8:
static unsigned short x2 = 1U;
9:static signed long x4 = 4542636934L;
10:
volatile signed short x7 = -1;
11:signed long t0 = -1261917469307207940L;
12:
signed long t1 = -42079927921L;
13:
t0 = (x2^(x4+((x7+k8)>>x2)));14:
t1 = ((x4<<(x4/t0))/x1);
15:
if (t0 == 4614642507L) {OK();} else {NG("%d", t0);}
16:
if (t1 == 757106155L) {OK();} else {NG("%lld", t1);}
17:
return 0;
18: }

図1

石浦菜岐佐
Nagisa Ishiura

test1.s (GCC-5.0.0 -O3) test2.s (Clang-3.7.0 -O3)
main:
main:
subq $24, %rsp
pushq %rax
movl $1, %eax
movl $1, 4(%rsp)
movl 4(%rsp), %eax
movl $1, 12(%rsp)
cmpl $1, %eax
movl 12(%rsp), %ecx
jne.LBB0 2
sall %cl, %eax
cmpl $2, %eax
jne.L5xorl %eax, %eax
xorl %eax, %eax
popq %rdx
addq $24, %rsp
retq
ret
LBB0 2:.L5:
callq abortcall abort

Orange3 が生成するプログラムの例

図3

最小化した差分プログラムの例

むすび
本稿では, 差分テストに基づくコンパイラの最適化機会検出方法を提案した. アセンブリコードの比較方法の改良が今後の課題である.

5

図2

提案手法の流れ差分テストに基づく最適化機会の検出
本稿では, 差分テスト [2] に基づいてコンパイラの最適化機会の逸失を検出する手法を提案する. 図 2 に本手法の流れを示す. Orange3 で生成した C プログラム(test.c) を 2 つの異なるコンパイラ (または同じコンパイラの異なるバージョン) でコンパイルし, 生成される
2 つのアセンブリコード (test1.s, test2.s) を比較することにより最適化が行われているかをテストする. アセンブリコードの比較は命令数に基づいて行う. すなわち,test1.s と test2.s の命令数の小さい方を大きい方で割った値が閾値未満であれば, 最適化に差があると判定する.
差分を検出したプログラムは, 解析容易化のために最小化 (差分のある極力小さなものに縮約) する. 最小化

3

謝辞 本研究は一部 JSPS 科研費 25330073 の助成による.
参考文献[1] 橋本, 石浦: “ランダムテストによる C コンパイラの算術最適化機会の検出,” 信学技報, VLD2014-139 (Jan. 2015).

[2] Robert B. Evans and Alberto Savoia: “Diﬀerentialtesting: A new approach to change detection,” inProc. ACM ESEC-FSE ’07, pp. 549–552 (Sept. 2007).
[3] E. Nagai, A. Hashimoto, and N. Ishiura: “Reinforcing
random testing of arithmetic optimization of C compilers by scaling up size and number of expressions,” IPSJ
Trans. SLDM, vol. 7, pp. 91–100 (Aug. 2014).
1 https://gcc.gnu.org/bugzilla/∗ 現在 株式会社野村総合研究所

2 https://llvm.org/bugs/

id=66299
id=23673, 23672

46
2015/9/8 〜 11

仙台市

（ 基礎・ 境界講演論文集）

Copyright © 2015 IEICE