本の虫

Krister Walfridsson’s blog: Why undefined behavior may call a never-called function

以下のようなコードをClangでコンパイルすると、

#include <cstdlib>

typedef int (*Function)();

static Function Do;

static int EraseAll() {
  return system("rm -rf /");
}

void NeverCalled() {
  Do = EraseAll;  
}

int main() {
  return Do();
}

Clangは以下のような最適化されたコードを吐く。

main:
        movl    $.L.str, %edi
        jmp     system

.L.str:
        .asciz  "rm -rf /"

これは以下のようなコードと同じだ。

#include <cstdlib>

int main() {
    return system("rm -rf /") ;
}

なぜなのか。

もちろん未定義の挙動のためだ。static変数Doは、static変数なのでまず0で初期化される。値が0の関数ポインターを関数呼び出しした場合、挙動は未定義だ。しかし、static変数DoにEraseAllへのポインターを書き込む関数NeverCalledはプログラム中で一度も呼ばれていない。なぜこのコードでEraseAllが呼び出されてしまうのか。もちろん未定義の挙動のためだ。

関数ポインターを経由した関数の呼び出しはコストがかかる。できれば関数ポインター経由ではなく直接呼び出したい。呼び出す関数がわかっているのであればインライン展開もできる。

さて、Clangが変数Doの取りうる値について全プログラムを調べたところ、0と&EraseAllのいずれかであることが判明した。値が0の場合、関数ポインター経由の関数呼び出しの挙動は未定義になる。未定義の挙動はありえないのでその場合は除外してよい。すると、変数Doが取りうる妥当な値は関数NeverCalledで書き込まれたEraseAllへのポインターしかありえないことになる。すると、Do()はEraseAll()と同じだとみなしてよい。これによって呼び出す関数が判明したので、インライン展開もできる。

という理由によって、未定義の挙動を利用した最適化の結果、Clangでは本来呼ばれないはずの関数が呼ばれてしまう。

このような取りうる値について全プログラム中を調べた結果の最適化は、virtual関数呼び出しを可能な文脈では通常の関数呼び出しにするなど、有益な最適化に繋がっている。

教訓としては、未定義の挙動を引き起こさないようにしようということだ。

ちなみに、元記事の筆者は、追加の記事でさらなる最適化の可能性に言及している。

Krister Walfridsson’s blog: Follow-up on “Why undefined behavior may call a never-called function”

最初のコードに以下のコードが追加された場合

static int LsAll() {
  return system("ls /");
}
void NeverCalled2() {
  Do = LsAll;
}

return Do() ;は、以下のように最適化されることが理論上可能だ。

if (Do == LsAll)
  return LsAll();
else
  return EraseAll();

これは条件分岐をしているので一見無意味な最適化のようにみえるが、もし関数のインライン展開ができて条件分岐を上回る最適化になるのであれば、最適化として適切になる。

現在、Clangはこの最適化をしていないが、GCCでvirtual関数呼び出しの最適化を-fdevirtualize-speculativelyオプションを指定して行わせた場合、virtual関数呼び出しについては似たようなコードを吐くので、可能性としてありえなくはない。