LLVM Project Blog: What Every C Programmer Should Know About Undefined Behavior #1/3
LLVM Project News and Details from the Trenches
Friday, May 13, 2011
What Every C Programmer Should Know About Undefined Behavior #1/3
すべての C プログラマーが未定義動作について知っておくべきこと (1/3)
People occasionally ask why LLVM-compiled code sometimes generates SIGTRAP signals when the
optimizer is turned on. After digging in, they find that Clang generated a "ud2"
instruction (assuming X86 code) - the same as is generated by __builtin_trap(). There are
several issues at work here, all centering around undefined behavior in C code and how LLVM
handles it.
オプティマイザーが有効にされているときに、LLVM でコンパイルされたコードがときどき
SIGTRAP シグナルを発生させることがあるのはなぜかとユーザーが時折り尋ねてくることがあり
ます。調べてみると彼らは Clang が (X86コードを仮定した場合) "ud2" 命令を生成
していることを発見します。これは __builtin_trap() によって生成されるものと同じです。
そこにはいくつかの issue がありますが、
C のコードにおける未定義動作とそれを LLVM がどのように handle しているかという点に集約されます。
This blog post (the first in a series of three) tries to explain some of these issues so that
you can better understand the tradeoffs and complexities involved, and perhaps learn a few
more of the dark sides of C. It turns out that C is not a "high level assembler"
like many experienced C programmers (particularly folks with a low-level focus) like to think,
and that C++ and Objective-C have directly inherited plenty of issues from it.
この(三回シリーズの第一回である)ブログ投稿ではあなたがより良くトレードオフと
complexities involved を理解し、さらにおそらくあともう少しの C の dark sides を学ぶた
めにこれらの issues の幾つかの説明を試みます。C が、経験を積んだ多くの C プログラマー
(とりわけハード寄りの low-level な部分に focus している人たち) が考えるような高度なア
センブラー ("high level assembler") ではなく、また、C++ や Objective-C は C
から plenty of issues (多くのことがら) をそのまま受け継いでいるということを明らかにします。
Introduction to Undefined Behavior
未定義動作への introduction
Both LLVM IR and the C programming language have the concept of "undefined behavior".
Undefined behavior is a broad topic with a lot of nuances. The best introduction I've found
to it is a post on John Regehr's Blog. The short version of this excellent article is that
many seemingly reasonable things in C actually have undefined behavior, and this is a common
source of bugs in programs. Beyond that, any undefined behavior in C gives license to the
implementation (the compiler and runtime) to produce code that formats your hard drive,
does completely unexpected things, or worse. Again, I would highly recommend reading
John's article.
LLVM IR とプログラミング言語の C の両方ともが“未定義動作”という考え方 (consept) を持
っています。未定義動作とは a lot of nuances を伴った broad topic です。わたしが見つけ
た best introduction は Jonh Regehr の blog にあった投稿です。この素晴らしい article
の short version にはC に実際にある未定義動作のうちの reasonable であると思われるもの
がたくさんありますが、そしてこれはプログラム中に存在するバグの common source です。
Beyond that,
C におけるすべての未定義動作はハードディスクをフォーマットしたり完全に予想外のことを行
うコードかさもなければ有用なコードを生成するための(コンパイラーやランタイムの)実装のラ
イセンスを与えます。繰り返しになりますが、John の article を読むことを強くお勧めします。
Undefined behavior exists in C-based languages because the designers of C wanted it to
be an extremely efficient low-level programming language. In contrast, languages like
Java (and many other 'safe' languages) have eschewed undefined behavior because they want
safe and reproducible behavior across implementations, and willing to sacrifice performance
to get it. While neither is "the right goal to aim for," if you're a C programmer
you really should understand what undefined behavior is.
C ベースの言語には未定義動作が存在します。それは、C の設計者たちはこの言語を extermely
に効率的なハードウェア寄りのプログラミング言語 (low-level programming language) とする
ことを望んだからです。それとは対象的に、Java のような言語 (と多くの“安全な”言語) は
未定義動作を避けていました。それは、その設計者たちが言語を安全かつ複数の実装をまたがっ
て reprocucible な動作をするものにしてするよう望み、そのために性能を犠牲にすることを選
択したからです。どちらも "the right goal to aim for," (目指すべき正しい目標)
ですが、もしあなたが C プログラマーであるのなら、未定義動作がどういったものなのかを本
当に理解しておくべきです。
Before getting into the details, it is worth briefly mentioning what it takes for a
compiler to get good performance out a broad range of C apps, because there is no
magic bullet. At a very high level, compilers produce high performance apps by a)
doing a good job at bread and butter algorithms like register allocation, scheduling,
etc. b) knowing lots and lots of "tricks" (e.g. peephole optimizations, loop
transformations, etc), and applying them whenever profitable. c) being good at
eliminating unnecessary abstractions (e.g. redundancy due to macros in C, inlining
functions, eliminating temporary objects in C++, etc) and d) not screwing anything up.
While any of the optimizations below may sound trivial, it turns out that saving just
one cycle out of a critical loop can make some codec run 10% faster or take 10% less
power.
詳細に入る前に、broad range of C apps で良好な性能を得るためにコンパイラーが行っている
ことについて手短に言及しておくことには価値があります。なぜなら魔法の弾丸 (magic bullet)
というものは存在しないのですから。非常に高い水準で以下のことがらを行うことでコンパイラ
ーは高性能のアプリケーションを生成します。
a) レジスター割り当てやスケジューリングなどのような基本的なアルゴリズム
(bread and butter algorithms) できちんと仕事をする
b) 数多くの (lots and lots of) “トリック”(覗き穴最適化、ループの変形、など)
を知り、そして profitable なときはつねにそれらを適用する。
c) 不必要な抽象化
(redundancy due to macros in C, 関数のインライン化、C++ における一時オブジェクトの削除、など)
の除去をうまくやる。
d) 一切害を及ぼさない。
While any of the optimizations below may sound trivial, it turns out that saving just
one cycle out of a critical loop can make some codec run 10% faster or take 10% less
power.
上で挙げた最適化は瑣末 (trivial) なものに思えるかも知れません。しかし、たったの 1サイ
クルを critical loop から取り除くことで一部の codec では 10% の高速化と 10% の電力節約
ができるかもしれないのです。
Advantages of Undefined Behavior in C, with Examples
C における未定義動作のアドバンテージ
Before getting into the dark side of undefined behavior and LLVM's policy and behavior
when used as a C compiler, I thought it would be helpful to consider a few specific
cases of undefined behavior, and talk about how each enables better performance than a
safe language like Java. You can look at this either as "optimizations
enabled" by the class of undefined behavior or as the "overhead avoided"
that would be required to make each case defined. While the compiler optimizer could
eliminate some of these overheads some of the time, to do so in general (for every
case) would require solving the halting problem and many other "interesting
challenges".
未定義動作や C コンパイラーとして使ったときの LLVM の policy and behavor の暗黒面に入
り込む前に、この未定義動作のアドバンテージというものが未定義動作のうちのごく少数の
specific cases を良く考える手助けやそれぞれの未定義動作が Java のような安全な言語
(safe language) よりも良好な性能をどのように可能にしているのかについて述べる手助けにな
るとわたしは考えました。このことは未定義動作のクラスによって可能となる最適化もしくは
"overhead avoided" that would be required to make each case defined.
(定義するとオーバーヘッドが必須となってしまうようなものの除去?)
のいずれかによって調べることが可能です。コンパイラーのオプティマイザーはこういったオー
バーヘッドの一部をときには取り除くことができるかもしれませんが、すべてのケースにおいて
そのようにすることは halting problem の解決とその他多くの "interesting
challenges" を要求します。
It is also worth pointing out that both Clang and GCC nail down a few behaviors that
the C standard leaves undefined. The things I'll describe are both undefined according
to the standard and treated as undefined behavior by both of these compilers in their
default modes.
C の標準が未定義のまま放置している Clang と GCC の両方ともが nail down する少数の動作
(a few behavior) を指摘することにも価値があります。わたしがこれから説明することは
both undefined according to the standard でありかつ
どちらのコンパイラーもそのデフォルトモードで未定義動作として扱っているものです。
Use of an uninitialized variable: This is commonly known as source of problems in C
programs and there are many tools to catch these: from compiler warnings to static and
dynamic analyzers. This improves performance by not requiring that all variables be
zero initialized when they come into scope (as Java does). For most scalar variables,
this would cause little overhead, but stack arrays and malloc'd memory would incur a
memset of the storage, which could be quite costly, particularly since the storage is
usually completely overwritten.
未初期化変数の使用:
これは C プログラムにおける source of problems として一般に知られているもので、これを
捕捉するツールはコンパイラーの警告から静的/動的解析まで数多くあります。これは、(Java
がやっているような)スコープに変数が現れたときにゼロでの初期化を要求しないことによって
性能を向上させます。大部分のスカラー変数ではこれはわずかのオーバーヘッドにしかなりませ
んが、スタック上の配列 (stack arrays) や malloc されたメモリー (malloc'd memory) はそ
の領域に対する memset を招き (incur) ます。確保された領域は一般的には完全に上書きされ
てしまうものなので、そうやって memset することは quite costly な可能性があります。
Signed integer overflow: If arithmetic on an 'int' type (for example) overflows, the
result is undefined. One example is that "INT_MAX+1" is not guaranteed to be
INT_MIN. This behavior enables certain classes of optimizations that are important for
some code. For example, knowing that INT_MAX+1 is undefined allows optimizing
"X+1 > X" to "true". Knowing the multiplication
"cannot" overflow (because doing so would be undefined) allows optimizing
"X*2/2" to "X". While these may seem trivial, these sorts of
things are commonly exposed by inlining and macro expansion. A more important
optimization that this allows is for "<=" loops like this:
符号付き整数のオーバーフロー:
(たとえば) 'int' 型に対する算術式がオーバーフローすると、その結果は未定義です。一つの
例としては、"INT_MAX+1" が INT_MIN になることは保証されていません。この振る舞い
は、一部のコードには重要であるような特定の最適化(certain classes of optimizations) を
可能にします。例えば、INT_MAX+1 が未定義であることが分かっていれば、"X+1 > X" を "true"
に最適化できます。乗算が (オーバーフローしたときに行うことが未定義であるために)“オー
バーフローできない”ことがわかっていれば"X*2/2" を "X" に最適化できま
す。このようなことは些細に思えるかもしれませんが、この種のことはインライン化やマクロの
展開において日常的に見られるものなのです。これによって可能になるより重要な最適化は次の
ような for "<=" ループに対するものです:
for (i = 0; i <= N; ++i) { ... }
In this loop, the compiler can assume that the loop will iterate exactly N+1 times if
"i" is undefined on overflow, which allows a broad range of loop
optimizations to kick in. On the other hand, if the variable is defined to wrap around
on overflow, then the compiler must assume that the loop is possibly infinite (which
happens if N is INT_MAX) - which then disables these important loop optimizations.
This particularly affects 64-bit platforms since so much code uses "int" as
induction variables.
このループでコンパイラーは、"i" がオーバーフローについて未定義であればループ
が正確に N+1 回繰り返されると仮定できます。一方この変数がオーバーフローしたときに wrap
around するように定義されていたならば、コンパイラーはそのループが無限ループとなる可能
性がある (N が INT_MAX の場合発生します) が、ことを仮定しなければならず、それによって
この種の重要なループ最適化を disable してしまいます。この最適化は特に 64ビットプラット
フォームで効果があります。それは多くのコードが "int" を induction variables
として使っているからです。
It is worth noting that unsigned overflow is guaranteed to be defined as 2's complement
(wrapping) overflow, so you can always use them. The cost to making signed
integer overflow defined is that these sorts of optimizations are simply lost (for
example, a common symptom is a ton of sign extensions inside of loops on 64-bit
targets). Both Clang and GCC accept the "-fwrapv" flag which forces the
compiler to treat signed integer overflow as defined (other than divide of INT_MIN by -1).
符号なし整数のオーバーフローが 2の補数のオーバーフローであるかのように定義されることを
保証することは大変価値のあることです (it is worth nothing)。ですから、いつでもこれを使
うことが可能です。符号付き整数のオーバーフローを定義するための代償はこの種の最適化を失
ってしまうことです(たとえば 64ビットターゲット上のループの内側での大量の符号拡張があり
がちです)。Clang と GCC の両方とも符号付き整数のオーバーフローが (INT_MIN を -1 で割っ
たもの以外として)定義されたものであるかのようにコンパイラーに強制する
"-fwrapv" フラグを受け付けます。
Oversized Shift Amounts: Shifting a uint32_t by 32 or more bits is undefined. My guess
is that this originated because the underlying shift operations on various CPUs do
different things with this: for example, X86 truncates 32-bit shift amount to 5 bits
(so a shift by 32-bits is the same as a shift by 0-bits), but PowerPC truncates 32-bit
shift amounts to 6 bits (so a shift by 32 produces zero). Because of these hardware
differences, the behavior is completely undefined by C (thus shifting by 32-bits on
PowerPC could format your hard drive, it is *not* guaranteed to produce zero). The
cost of eliminating this undefined behavior is that the compiler would have to emit an
extra operation (like an 'and') for variable shifts, which would make them twice as
expensive on common CPUs.
大きすぎるシフト量:
uinnt32_t を32ビット以上シフトしたときの結果は未定義です。わたしは 種々の CPU がシフト
操作において異なる動作をすることが理由でこのようになっているのではないかと思っています。
たとえば X86 では 32 ビットのシフト量は 5ビットの範囲に丸められますが (したがって 32ビ
ットシフトの結果は0ビットシフトの結果と同じです)、PowerPC では 6ビットの範囲で丸められ
ます (したがって 32ビットシフトの結果はゼロになります)。これらはハードウェアの違いであ
るので、その動作は C では全くの未定義です (したがって PowerPC 上で 32 ビットシフトした
ことによってあなたのハードディスクをフォーマットしてしまうかもしれませんし、シフトの結
果が 0になることは保証*されていません*)。この未定義動作の除去のコストはコンパイラーが
変数のシフトのために ('and' のような) extra operation を emit しなければならないもので
あり、これは一般的な CPU では操作を二倍高価なものにしてしまうものです。
Dereferences of Wild Pointers and Out of Bounds Array Accesses: Dereferencing random
pointers (like NULL, pointers to free'd memory, etc) and the special case of accessing
an array out of bounds is a common bug in C applications which hopefully needs no
explanation. To eliminate this source of undefined behavior, array accesses would have
to each be range checked, and the ABI would have to be changed to make sure that range
information follows around any pointers that could be subject to pointer arithmetic.
This would have an extremely high cost for many numerical and other applications, as
well as breaking binary compatibility with every existing C library.
wild ポインターの dereference や配列の範囲外へのアクセス:
(NULL や free 済みのメモリーなどの) random ポインターを dereferecing することや配列の
範囲外へのアクセスの special case は説明するまでもないほどの C applocations における一
般的なバグです。この未定義動作の source を取り除くには配列のアクセスでは範囲チェックが
必須となって、また、ポインター演算が必要となるであろうすべてのポインターに範囲情報が付
くようにその ABI (Application Binary Interface) も変更しなければならなくなるでしょう。
これは数値演算やその他のアプリケーションにとっては既存のすべてのCライブラリとのバイナ
リ互換を壊してしまうばかりでなくextermely high cost となるでしょう。
Dereferencing a NULL Pointer: contrary to popular belief, dereferencing a null pointer
in C is undefined. It is not defined to trap, and if you mmap a page at 0, it is not
defined to access that page. This falls out of the rules that forbid dereferencing
wild pointers and the use of NULL as a sentinel. NULL pointer dereferences being
undefined enables a broad range of optimizations: in contrast, Java makes it invalid
for the compiler to move a side-effecting operation across any object pointer
dereference that cannot be proven by the optimizer to be non-null. This significantly
punishes scheduling and other optimizations. In C-based languages, NULL being
undefined enables a large number of simple scalar optimizations that are exposed as a
result of macro expansion and inlining.
NULL ポインターの dereferencing:
一般に信じられていることに反して、C における null ポインターの dereferencing は未定義
です。null ポインターの dereference をしたときにトラップするように定義されてはいません
し、あるページを 0番地に mmap したときにもそのページにアクセスするとは定義されていませ
ん。これは wild ポインターの dereference やNULL を番兵として使うことを禁止するルールを
falls out します。NULL ポインターの dereference を未定義にすることで広範囲の最適化が可
能となります:対照的に、Java はコンパイラーに対してオプティマイザーが non-null であるか
どうかをprove できない任意のオブジェクトポインター dereference をまたがった副作用を持
つ操作(side-effecting operation) の移動を invalid にしています。これはスケジューリング
やその他の最適化を significantly に punishes (罰する、やっつける)します。C ベースの言
語では NULL を未定義としておくことで、マクロ展開やインライン化の結果として生じる単純な
scalar optimizations の多くが可能となります。
If you're using an LLVM-based compiler, you can dereference a "volatile"
null pointer to get a crash if that's what you're looking for, since volatile loads
and stores are generally not touched by the optimizer. There is currently no flag that
enables random NULL pointer loads to be treated as valid accesses or to make random
loads know that their pointer is "allowed to be null".
LLVM ベースのコンパイラーを使っている場合、コンパイラーをクラッシュさせたいのであれば
その目的のために "volatile" null pointer を dereference できます。それは
volatile のロードやストアは一般的にオプティマイザーが関与しないところだからです。
random NULL ポインターのロードを valid access として扱うことやrandom ロードが対象とな
るポインターが "allowed to be null" かどうかをわかるにすることを有効にするフ
ラグは現状ではありません
Violating Type Rules: It is undefined behavior to cast an int* to a float* and
dereference it (accessing the "int" as if it were a "float"). C
requires that these sorts of type conversions happen through unions: using pointer
casts is not correct and undefined behavior results. The rules for this are quite
nuanced and I don't want to go into the details here (there is an exception for char*,
vectors have special properties, unions change things, etc). This behavior enables an
analysis known as "Type-Based Alias Analysis" (TBAA) which is used by a
broad range of memory access optimizations in the compiler, and can significantly
improve performance of the generated code. For example, this rule allows clang to
optimize this function:
型規則違反:
int* から float* へのキャストやキャスト結果の dereference ("float" であるかのごとく
"int" にアクセスする) は未定義動作です。C はこの種の型変換 (type conversions) が共用体
を通して起きることを要求しています。ポインターのキャストを使うことは正しくない (not
correct) と同時に、結果は未定義なものになります。これに対する規則は quite nuanced です
が、ここでは詳細を述べません
(there is an exception for char*,
vectors have special properties,
unions change things, etc)。
この振る舞いは TBAA ("Type-Based Alias Analysis") として知られるコンパイラー
におけるメモリーアクセス最適化の広範囲で使用されている解析を可能にし、生成されたコード
の性能を significantly に改善できるようにします。たとえばこの規則は clang が
float *P;
void zero_array() {
int i;
for (i = 0; i < 10000; ++i)
P[i] = 0.0f;
}
into "memset(P, 0, 40000)". This optimization also allows many loads to be hoisted
out of loops, common subexpressions to be eliminated, etc. This class of undefined behavior
can be disabled by passing the -fno-strict-aliasing flag, which disallows this analysis. When
this flag is passed, Clang is required to compile this loop into 10000 4-byte stores (which is
several times slower), because it has to assume that it is possible for any of the stores to
change the value of P, as in something like this:
この関数を最適化して "memset(P, 0, 40000)" としてしまえるようにします。この
最適化はまた多くのロードをループの外に追い出したり共通部分式を削除したりするような最適
化などを可能とします。このクラスの未定義動作はこの解析を禁止する -fno-strict-aliasing
フラグを渡すことでdisable できます。このフラグが渡されたとき Clang はこのループを (数
倍遅い) 10,000 個の四バイトストア命令にする ことをコンパイラーに要求しますが、それは次
の例のように何かをストアするために P の値を変更する可能性があることを仮定する必要があ
るからです。
int main() {
P = (float*)&P; // cast causes TBAA violation in zero_array.
zero_array(); // キャストによって zero_array 内で TBAA違反が引き起こされる
}
This sort of type abuse is pretty uncommon, which is why the standard committee decided that
the significant performance wins were worth the unexpected result for "reasonable"
type casts. It is worth pointing out that Java gets the benefits of type-based optimizations
without these drawbacks because it doesn't have unsafe pointer casting in the language at all.
この種の abuse は pretty uncommon であり、そしてそれは significant な performance wins
は "reasonable" type casts による予想外の結果 (unexpected result) を容認する
だけの価値があると標準化委員会 (standard committee) が判断したものです。Java がこの種
の drawbacks なしに型ベースの最適化によって利益を得たことを指摘することには価値があり
ます。それは Java が unsafe なポインターのキャストを言語として持っていないからです。
Anyway, I hope that this gives you an idea of some of the classes of optimizations enabled by
undefined behavior in C. There are many other kinds of course, including sequence point
violations like "foo(i, ++i)", race conditions in multithreaded programs,
violating 'restrict', divide by zero, etc.
いずれにしても、C における未定義動作によって有効となる幾つか最適化のクラスの考え方をあ
なたに示せたことを望みます。もちろん、この他にも "foo(i, ++i)" のようなシー
ケンスポイント違反、マルチスレッドプログラムにおける競合条件、ゼロ除算による
'restrict' 違反などを含む多くの種類があります。
In our next post, we'll discuss why undefined behavior in C is a pretty scary thing if
performance is not your only goal. In our final post in the series, we'll talk about how
LLVM and Clang handle it.
次回は、なぜ性能が唯一の目標でないときには C における未定義動作は pretty scary thing
なのかについて論じます。そしてシリーズの最終回では LLVM と Clang がそれをどのように
handle するかについて述べます。
-Chris Lattner
Posted by Chris Lattner at 11:25 AM
![GUNDAM A (ガンダムエース) 2011年 07月号 [雑誌]](http://ecx.images-amazon.com/images/I/615dGTYvioL._SL160_.jpg)
![月刊 アフタヌーン 2011年 07月号 [雑誌]](http://ecx.images-amazon.com/images/I/61%2BQP7L%2BpVL._SL160_.jpg)
