+===========+
|P/ECE研究室|
+===========+

P/ECE研究記録 2013年
====================

* Tue Jul 30 00:00:00 JST 2013 Naoyuki Sawa
- gcc33 条件演算子の最適化バグ

	P/ECE開発環境のCコンパイラgcc33には、条件演算子の最適化バグがあります。
	『「0と比較する条件式」の条件演算子をネストすると、間違った結果を返すコードが生成される』というバグです。
	以下に、再現方法と、回避方法を説明します。

	■再現プログラム

		ダウンロードはこちら：　http://www.piece-me.org/archive/tropbug-20030730-src.zip

		//◆コンパイル方法
		//┃最適化オプション「-O」「-O1」「-O2」のどれかを指定してコンパイルすると、最適化バグが発生します。
		//┃最適化オプション「-O」「-O1」「-O2」どれも指定せずにコンパイルすれば、最適化バグは発生しません。
		#include <piece.h>
		unsigned char vbuff[DISP_X * DISP_Y];

		//■関数仕様：aが0でなければaを返す。bが0でなければbを返す。どちらでもなければcを返す。
		//□条件演算子を使用する ⇒ ×最適化バグが発生する
		int test11(int a, int b, int c) {
		        int x;
		        x = a ? a : b ? b : c;
		        return x;
		}
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		int test12(int a, int b, int c) {
		        int x;
		        x = (a != 0) ? a : (b != 0) ? b : c;
		        return x;
		}
		//□条件演算子を使用し、明示的に右結合を書く ⇒ ×最適化バグが発生する
		int test13(int a, int b, int c) {
		        int x;
		        x = a ? a : (b ? b : c);
		        return x;
		}
		//□GCC拡張機能を使用する ⇒ ○最適化バグが発生しない
		int test14(int a, int b, int c) {
		        int x;
		        x = a ? : b ? : c;
		        return x;
		}
		//□if文を使用する ⇒ ○最適化バグが発生しない
		int test15(int a, int b, int c) {
		        int x;
		        if(a) { x = a; } else if(b) { x = b; } else { x = c; }
		        return x;
		}
		//■関数仕様：aが0超過ならばaを返す。bが0超過ならばbを返す。どちらでもなければcを返す。
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		int test21(int a, int b, int c) {
		        int x;
		        x = (a > 0) ? a : (b > 0) ? b : c;
		        return x;
		}
		//■関数仕様：aが1以上ならばaを返す。bが1以上ならばbを返す。どちらでもなければcを返す。
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		int test31(int a, int b, int c) {
		        int x;
		        x = (a >= 1) ? a : (b >= 1) ? b : c;
		        return x;
		}
		//■関数仕様：aが1超過ならばaを返す。bが1超過ならばbを返す。どちらでもなければcを返す。
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ○最適化バグが発生しない
		int test41(int a, int b, int c) {
		        int x;
		        x = (a > 1) ? a : (b > 1) ? b : c;
		        return x;
		}
		//■関数仕様：aが0未満ならばaを返す。bが0未満ならばbを返す。どちらでもなければcを返す。
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		int test51(int a, int b, int c) {
		        int x;
		        x = (a < 0) ? a : (b < 0) ? b : c;
		        return x;
		}
		//■関数仕様：aが-1以下ならばaを返す。bが-1以下ならばbを返す。どちらでもなければcを返す。
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ○最適化バグが発生しない
		int test61(int a, int b, int c) {
		        int x;
		        x = (a <= -1) ? a : (b <= -1) ? b : c;
		        return x;
		}
		//■関数仕様：aが0超過ならばaを返す。bが0未満ならばbを返す。どちらでもなければcを返す。
		//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		int test71(int a, int b, int c) {
		        int x;
		        x = (a > 0) ? a : (b < 0) ? b : c;
		        return x;
		}

		void pceAppInit() {
		        //一般的な初期化
		        pceLCDDispStop();
		        pceLCDSetBuffer(vbuff);
		        pceLCDDispStart();
		        //画面クリア
		        memset(vbuff, 0, sizeof vbuff);
		        pceFontSetPos(0, 0);
		        pceFontSetType(2);
		        //テスト関数を呼び出します
		        pceFontPrintf("test11 %4d\n", test11(0,  123, 0));
		        pceFontPrintf("test12 %4d\n", test12(0,  123, 0));
		        pceFontPrintf("test13 %4d\n", test13(0,  123, 0));
		        pceFontPrintf("test14 %4d\n", test14(0,  123, 0));
		        pceFontPrintf("test15 %4d\n", test15(0,  123, 0));
		        pceFontPrintf("test21 %4d\n", test21(0,  123, 0));
		        pceFontPrintf("test31 %4d\n", test31(0,  123, 0));
		        pceFontPrintf("test41 %4d\n", test41(0,  123, 0));
		        pceFontPrintf("test51 %4d\n", test51(0, -123, 0));
		        pceFontPrintf("test61 %4d\n", test61(0, -123, 0));
		        pceFontPrintf("test71 %4d\n", test71(0, -123, 0));
		        //画面転送
		        pceLCDTrans();
		}
		void pceAppProc(int count) {
		        //SELECTボタンが押されたら終了します
		        if(pcePadGet() & TRG_SELECT) { pceAppReqExit(0); }
		}
		void pceAppExit() {
		        //何もしません
		}

	■再現方法

		まず、再現プログラムを、最適化無しでコンパイルして実行してみます。
		実行結果は、こうなります:

			http://www.piece-me.org/tropbug_ok.png
			┏━━━━━━┓
			┃test11   123┃
			┃test12   123┃
			┃test13   123┃
			┃test14   123┃
			┃test15   123┃
			┃test21   123┃
			┃test31   123┃
			┃test41   123┃
			┃test51  -123┃
			┃test61  -123┃
			┃test71  -123┃
			┗━━━━━━┛

		最適化無しの実行結果が、正しい実行結果です。
		次に、再現プログラムを、最適化有りでコンパイルして実行してみます。
		実行結果は、こうなります。

			http://www.piece-me.org/tropbug_ng.png
			┏━━━━━━┓
			┃test11     0┃
			┃test12     0┃
			┃test13     0┃
			┃test14   123┃
			┃test15   123┃
			┃test21     0┃
			┃test31     0┃
			┃test41   123┃
			┃test51     0┃
			┃test61  -123┃
			┃test71     0┃
			┗━━━━━━┛

		最適化有りの実行結果は、一部が違っています。
		最適化無しと最適化有りとで、実行結果が同じなのは、test14,test15,test41,test61 です。
		最適化無しと最適化有りとで、実行結果が異なるのは、test11,test12,test13,test21,test31,test51,test71 です。
		前者が、最適化バグが発生しないケース、後者が、最適化バグが発生するケースとなります。

	■最適化コード

		再現プログラムを最適化有りでコンパイルした時に、gcc33が生成するアセンプラコードを、以下に示します。
		(見易さのために、整形してコメントを追記してあります。テスト関数以外は関係無いので、省いてあります。)

		;//■関数仕様：aが0でなければaを返す。bが0でなければbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用する ⇒ ×最適化バグが発生する
		test11:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a != 0) { goto __L11; }
		                jrne            __L11                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrne            __L11                   ;// if(a != 0) { goto __L11; }  ;//バグ。「if(b != 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L11:                                                  ;//
		                ret                                     ;// return x;
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		test12:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a != 0) { goto __L12; }
		                jrne            __L12                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrne            __L12                   ;// if(a != 0) { goto __L12; }  ;//バグ。「if(b != 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L12:                                                  ;//
		                ret                                     ;// return x;
		;//□条件演算子を使用し、明示的に右結合を書く ⇒ ×最適化バグが発生する
		test13:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a != 0) { goto __L13; }
		                jrne            __L13                   ;// 
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrne            __L13                   ;// if(a != 0) { goto __L13; }  ;//バグ。「if(b != 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L13:                                                  ;// 
		                ret                                     ;// return x;
		;//□GCC拡張機能を使用する ⇒ ○最適化バグが発生しない
		test14:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a != 0) { goto __L14; }
		                jrne            __L14                   ;// 
		                ld.w            %r10,%r14               ;// x = c;
		                cmp             %r13,0                  ;// if(b == 0) { goto __L14; }
		                jreq            __L14                   ;// 
		                ld.w            %r10,%r13               ;// x = b;
		__L14:                                                  ;// 
		                ret                                     ;// return x;
		;//□if文を使用する ⇒ ○最適化バグが発生しない
		test15:
		                ld.w            %r10,%r12               ;// x = a;
		                ld.w            %r12,%r14               ;// y = c;      ;//間違いではないが、無駄なコードが生成されている
		                cmp             %r10,0                  ;// if(a != 0) { goto __L15; }
		                jrne            __L15                   ;//
		                ld.w            %r10,%r12               ;// x = c;      ;//間違いではないが、無駄なコードが生成されている
		                cmp             %r13,0                  ;// if(b == 0) { goto __L15; }
		                jreq            __L15                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		__L15:                                                  ;//
		                ret                                     ;// return x;
		;//■関数仕様：aが0超過ならばaを返す。bが0超過ならばbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		test21:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a > 0) { goto __L21; }
		                jrgt            __L21                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrgt            __L21                   ;// if(a > 0) { goto __L21; }   ;//バグ。「if(b > 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L21:                                                  ;//
		                ret                                     ;// return x;
		;//■関数仕様：aが1以上ならばaを返す。bが1以上ならばbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		test31:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a > 0) { goto __L31; }
		                jrgt            __L31                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrgt            __L31                   ;// if(a > 0) { goto __L31; }   ;//バグ。「if(b > 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L31:                                                  ;//
		                ret                                     ;// return x;
		//■関数仕様：aが1超過ならばaを返す。bが1超過ならばbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ○最適化バグが発生しない
		test41:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,1                  ;// if(a >  1) { goto __L41; }
		                jrgt            __L41                   ;//
		                ld.w            %r10,%r14               ;// x = c;
		                cmp             %r13,1                  ;// if(b <= 1) { goto __L41; }
		                jrle            __L41                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		__L41:                                                  ;//
		                ret                                     ;// return x;
		;//■関数仕様：aが0未満ならばaを返す。bが0未満ならばbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		test51:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a < 0) { goto __L51; }
		                jrlt            __L51                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrlt            __L51                   ;// if(a < 0) { goto __L51; }   ;//バグ。「if(b < 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L51:                                                  ;//
		                ret                                     ;// return x;
		;//■関数仕様：aが-1以下ならばaを返す。bが-1以下ならばbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ○最適化バグが発生しない
		test61:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,-1                 ;// if(a <= -1) { goto __L61; }
		                jrle            __L61                   ;//
		                ld.w            %r10,%r14               ;// x = c;
		                cmp             %r13,-1                 ;// if(b >  -1) { goto __L61; }
		                jrgt            __L61                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		__L61:                                                  ;//
		                ret                                     ;// return x;
		;//■関数仕様：aが0超過ならばaを返す。bが0未満ならばbを返す。どちらでもなければcを返す。
		;//□条件演算子を使用し、明示的に比較式を書く ⇒ ×最適化バグが発生する
		test71:
		                ld.w            %r10,%r12               ;// x = a;
		                cmp             %r10,0                  ;// if(a > 0) { goto __L71; }
		                jrgt            __L71                   ;//
		                ld.w            %r10,%r13               ;// x = b;
		                ;//バグ。「cmp %r10,0」が足りない       ;//
		                jrlt            __L71                   ;// if(a < 0) { goto __L71; }   ;//バグ。「if(b < 0)」であるべき
		                ld.w            %r10,%r14               ;// x = c;
		__L71:                                                  ;//
		                ret                                     ;// return x;

	■結果の考察

		□最適化バグが発生するケース

		①「0と比較する条件式」の条件演算子をネストすると、最適化バグが発生します。⇒test11
		②「0と比較する条件式」を、明示的に比較式を書いても、最適化バグが発生することに変わりはありません。⇒test12
		③「0と比較する条件式」を、明示的に右結合を書いても、最適化バグが発生することに変わりはありません。⇒test13
		④「0と比較する条件式」とは、「＝0」だけでなく、「＜0」「≦0」「≧0」「＞0」である場合も、最適化バグが発生します。⇒test21,test51
		　一つ目の条件式と二つ目の条件式が異なっていても、どちらも「0と比較する条件式」であれば、最適化バグが発生します。⇒test71
		④「0と比較する条件式」とは、「結果的に0と比較する条件式」である場合も、最適化バグが発生します。⇒test31
		　「結果的に0と比較する条件式」とは、たとえば、「≧1」です。
		　何故こうなるかというと、gcc33は「≧1」の条件式を「＞0」に変換してコードを生成するからです。(常に変換するかどうかは不明)

		□最適化バグが発生しないケース

		⑤GCC拡張機能を使用して、「＝0」の条件式を省略した書き方をすると、最適化バグが発生しません。⇒test14
		⑥条件演算子を使用せず、if文をネストして書くと、最適化バグが発生しません。⇒test15
		⑦「0と比較する条件式」でない場合は、最適化バグが発生しません。⇒test41
		⑧「結果的に0と比較する条件式」に変換できる場合であっても、「≦-1」の場合は、最適化バグが発生しません。⇒test61
		　前述(④)の通りgcc33は「≧1」の条件式を「＞0」に変換しますが、何故か「≦-1」を「＜0」に変換しないからです。(常に変換しないかどうかは不明)

	■まとめ

		この最適化バグは、かなり危険だと思います。
		「変数a,b,cの中で最初にNULLでない値を取得する」という目的で、「a?a:b?b:c;」と書くことが良くあるからです。
		たとえば「a=NULL,b=foo,c=NULL;」の場合に、「a?a:b?b:c;」の結果がfooでなくNULLになってしまいます。

		「＝0」「＝NULL」の条件式ならば、GCC拡張機能を使って「a?:b?:c;」と書けば、最適化バグを回避できます。
		しかし、大小比較である場合はGCC拡張機能に置き換えられないので、この回避方法は使えません。

		□結論：確実に安全を期すためには:
		┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
		┃「0と比較する条件式」の条件演算子をネストすることは避けて、常にif文のネストを使うようにする ┃
		┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

		自分でプログラムを書く場合は、上記の点に留意して書けば良いのですが、オープンソース等をP/ECEでコンパイルして使う場合は、もっと要注意です。
		特に、前述の「a?a:b?b:c;」が含まれているケースが、多いと思います。
		何かうまく動かない場合は、この最適化バグが原因でないか、ソースを目視確認する必要があるでしょう・・・(面倒ですが(^^;)

	■今後の課題(TODO)

		目視確認するのは面倒だし見落とすおそれがあるので、ある程度チェックを自動化できないか検討します。
		たとえば、『C言語ソースを読み込んで、条件演算子のネスト部分を抽出するフィルタ』を作成して、ソース全体から危険そうな部分のみを自動抽出し、
		抽出した部分について、『「0と比較する条件式」の条件演算子のネスト』であるかどうかだけを、目視確認すれば済むようにしたいです。