Edited at

お前clangとgccは同じだと思ってるだろ?[競プロ]


はじめに

clangとgccが同じだと思っていたのは僕です、ごめんなさい。東京理科大学アドベントカレンダー3日目です。sanoが書きます。ガバガバ記事なので間違っているところを発見してくれた方はこっそりコメントで教えてください。

先日、後輩の競技プログラミングの提出コードのデバッグをしていたところclangとgccで挙動が異なったためそれについて書こうと思います。


問題概要

\sum_{i=1}^{N}\sum_{j=1}^{i-1} abs(x_i-x_j) \\

を求める問題です。(0 =< N =< 10^5)この問題の解法は今回の本質ではないので省きますがソートを行なった後に

\sum_{i=1}^{N}y_i(i - (N - i -1)) \\

を計算すれば計算量が減って楽チンだね〜という問題でした。


問題となったコード

#include <stdio.h>

#include <stdlib.h>
#include <math.h>

int asc(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int main (void)
{
int N, x[100001] = {}, i, j = 0;
long long int sum = 0;
scanf("%d", &N);
for(i = 0;i < N;i++)
{
scanf("%d", &x[i]);
}
qsort(x, N, sizeof(int), asc);
for(i = 0;i <N;i++)
{
sum += x[i] * (i - (N - i -1));
}
printf("%lld\n", sum);
return 0;
}

見る人が見れば一発でこのコードのやばい部分がわかってしまうと思うのですが、問題の部分はここです。

for(i = 0;i <N;i++)

{
sum += x[i] * (i - (N - i -1));
}

このコードでは左辺のsumはlong longで宣言していますが右辺はint型です。そのため左辺に加算していく点では問題のないコードなのですが、右辺の城さんの部分において与えられたデータセットによってはオーバーフローしてしまうんですね。(実際にオーバーフローするようなデータセットが与えられています。)


clangとgccでの挙動の違いについて

なんとこのコード、gccで提出するとWA(不正解)が出てclangで提出するとAC(正解)が出てしまいました。つまりコンパイル後の実行コードに違いがあるということです。有識者slackでお聞きしたところ上記の部分のアセンブラを見比べてくれた方がいました。


clang3.8 (-O2)

  movslq (%rsp), %rdx

movl $1, %ecx
movl $1, %esi
subl %r8d, %esi
movslq %esi, %rsi
imulq %rdx, %rsi
movl $1, %edx


gcc -std=gnu11 -O2

  movl (%rcx), %edx

addq $4, %rcx
imull %eax, %edx
addl $2, %eax
movslq %edx, %rdx
addq %rdx, %rsi

アセンブリはほぼわからないので詳しく説明することができませんが乗算命令の部分に違いがあります。それぞれimulqは64bit乗算命令、imullは32bit乗算命令だそうです。符号付き整数のオーバーフローは未定義動作なのでコンパイラによってどう最適化するのも許されているため、このような違いが出たようです。


まとめ

未定義動作を含むコードを書くと最適化されたときにコンパイラによって違いが出ることがある。というかそもそも未定義動作を書くな!


感謝

@hsjoihs さん、slackでの丁寧な説明ありがとうございました。こんな場で申し訳ないですが感謝申し上げます、非常に助かりました。


参考

未定義動作について書いてくださっている方が他にもいらっしゃったので参考として記載しておきます。自分の記事なんかよりかなりわかりやすいですしためになると思います。

C言語分かってなかった (I Do Not Know C)

未定義動作により最適化レベルで結果が変わるコード

C/C++はnull安全になる前に安全に差の絶対値を計算できるようになるべきではないか

C++ における整数型の怪と "移植性のある" オーバーフローチェッカー (第1回 : 整数型の怪と対策の不足)