yohhoyの日記

2012-02-20

(翻訳)C/C++のStrict Aliasingを理解する または - どうして#$@##@^%コンパイラは僕がしたい事をさせてくれないの!

元記事:Understanding C/C++ Strict Aliasing, or - Why won’t the #$@##@^% compiler let me do what I need to do!, Patrick Horgan氏

訳出メモ:

  • 自分自身の理解のために日本語訳を行ったStrict Aliasing Rules解説記事。
  • 訳文中では"aliasing/alias", "strict aliasing rules", "type punning"をそのまま表記する。直訳すれば"別名(エイリアシング)", "厳密な別名規則", "型もじり(言い換え)"となる。


ところで、何が問題なの?

strict aliasing rulesに関しては多くの混乱が見られます。人々を混乱させる主要因となっているのは、aliasingに言及する2種類の異なるグループ; コンパイラを利用する一般開発者 と コンパイラの製作者 の存在でしょう。この文書ではこれらを解消していこうと思います。ここではC89/90 (6.3), C98/99 (6.7/5)およびC++98 (3.10/15), C++0x (3.10/10)のaliasing rulesに基づいた議論をしていきます。現行のCまたはC++標準でのaliasing rulesを探すには、"may not be aliased"で検索してください。それはaliasingを許す形式について述べたセクションへ脚注中に見つかるでしょう。規格の策定者が当時どのように考えていたかについては、C89 Rationale(論理的根拠)の中でaliasing rulesがなぜどのように存在するかについて述べている§3.3 Expressionを参照してください。

開発者がaliasingへの興味を持つのは、コンパイラがtype punningやstrict aliasing rulesに関する警告を発し、その警告の意味を理解しようとしたときでしょう。彼らは警告メッセージをGoogleで検索し、CかC++規格書のいずれかでaliasingに関するセクションへの言及を探しだし、「そう、alias、これが僕がやりたかった事だ」と考えます。そして、ふさわしい規格書のセクションについて神秘的ルーン文字のごとく研究し、やろうとした事を実現するための規則を予言しようとします。彼らはaliasing rulesとはtype punningを行う方法について書かれたものと考えます。しかし、それは完全なる間違いです。

コンパイラ製作者はstrict aliasing rulesが何を意味するのか知っています。この規則は、どのようなとき変数を介した変更が別の変数に影響を与えないと安全に仮定できるか、をコンパイラ製作者に知らせるために書かれています。逆に言えば、どのようなとき2つの変数が実際には同じメモリ位置を参照するかもしれないと仮定すべきか、を知らせるものです。

そのためこの文書は2つのパートに分かれています。最初に、strict aliasingとはどのようなものでなぜ存在するかについて述べていきます。それから、この規則と衝突せずに開発者がすべき事を行うにはどうすれば良いのか述べていきます。

前半:aliasingとは一体何なのか?

複数のlvalueが同じメモリ位置を指すとき、aliasingとなります(lvalueと聞いたら、代入式の左辺に位置する変数のことと考えてください)。例を示します:

int anint;
int *intptr=&anint;

もし*intptrの値を変更するとanintの値も変化します。これは*intpranintのalias、つまり同じものを指すもう1つの名前となっているためです。もう1つ例を示します:

int anint;
void foo(int &i1, int &i2);
foo(anint,anint);

2個の引数に対してanintを使ったため、foo本体では2つの参照型変数i1i2はaliasになります。つまり、このようにfooが呼び出されたときは同じ位置を指しています。

何が問題なのか?

次のコードを分析しましょう:

int anint;
void foo(double *dblptr)
{
    anint=1;
    *dblptr=3.14159;
    bar(anint);
}

コードを見る限り、bar()の引数は定数1であると仮定するのは安全なように思えます。古き悪しき時代には、コンパイラ製作者は正気の沙汰でないレガシーコードをサポートするため最悪のaliasingを仮定せねばならず、barの引数が1になるという仮定が安全であるとは言えませんでした。もしdblptranintを指す場合はdblptrへの代入を介して値が変化してしまうため、関数呼び出し前にanintの値をリロードするコードを挿入する必要がありました。この状況はfoofoo((double*) &anint)と呼び出された場合に起こりえます

これこそがstrict aliasingが解決しようとする問題です。コンパイラのオプティマイザ(optimizer; 最適化器)製作者にとって容易に達成できる目標が存在しており、その目標を達成するためにあるaliasing rulesにプログラマが従うことを要求します。aliasingと、それによって引き起こされる問題は、Cの時代から存在していました。最近になっての違いは、コンパイラ製作者が規則に対して厳格になり、かつ効率的に最適化を行うために規則を強制していることです。CとC++それぞれの標準では合法的にaliasを行える条件(次のセクションを参照)をリスト化しており、それ以外の全てのケースではコンパイラ製作者がlvalue間に相互作用が無いと仮定することを許容します。リストに載っていない場合はaliasが無いと仮定してよく、コンパイラ製作者はこの仮定に基づく最適化を自由に行えます。リストに載っている場合はaliasingの可能性があるため、コンパイラ製作者はその仮定を置かなければなりません。コンパイラ製作者がこのリストに従い、かつあなたのコードが規則に従っていると見なすとき、strict-aliasingと呼ばれます。strict-aliasingの下では、非互換(incompatible)な型doubleintはaliasになりえないため、コンパイラ製作者には前述の関数fooを最適化する自由度があります。もしfoofoo((double *)&anint)のように呼び出したとしたら、たちまちダメになってしまいますがそれは当然の報いと言えます。

それで、何がaliasになるの?

C9899:201x 6.5 Expressionsより引用*1

7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types:

  • a type compatible with the effective type of the object,
  • a qualified version of a type compatible with the effective type of the object,
  • a type that is the signed or unsigned type corresponding to the effective type of the object,
  • a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
  • an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
  • a character type.

7 オブジェクトは下記のいずれかの型をもつlvalue式によってのみアクセスされて格納された値を持たなけれればならない:

  • オブジェクトの有効な型と互換性のある型、
  • オブジェクトの有効な型と互換性のある型の修飾バージョン、
  • オブジェクトの有効な型に対応するsignedまたはunsignedな型、
  • オブジェクトの有効な型の修飾バージョンに対応するsignedまたはunsignedな型、
  • そのメンバとして前述のいずれかの型を含むアグリゲートまたはunion型(サブアグリゲートや包含するunionのメンバも再帰的に含まれる)、または
  • 文字型。

こられは次のように要約できます:

  • 互換型(compatible type)またはsigned, unsigned, volatileの組合せの付与のみが異なるもの。大抵は互換型とは単に同一の型を意味します。より詳細について知りたければ規格書を読んでください。(例:longへのポインタ型とconst unsigned longへのポインタ型は、同じものを指すかもしれません。)
  • アグリゲート(structまたはclass)もしくはunion型は、その内部に含む型のaliasとできます。(例:関数にintへのポインタが渡された場合、内部にintを含むstructunionへのポインタ、もしくはintを含む別のstructunionを含む型、もしくは...と際限なく、int*は別のポインタが指すstructunionに含まれるintを指すことができます。)
  • 文字型。規格ではchar*, signed char*, unsigned char*が別の何かを指すことが特別に許されています。これは文字型がメモリ上の任意のaliasになり得ることを意味します。
  • C++の場合のみ、動的型(dynamic type)のCV(constおよび/またはvolatile)修飾された基底クラスは派生クラスのaliasになり得ます。(例:クラスdogが基底クラスにクラスanimalを持つ場合、クラスdogクラスanimalへのポインタや参照はaliasになり得ます。)

もちろん参照型は同じ問題をかかえており、またポインタ型と参照型間でもaliasになり得ます。規則でaliasになり得ると言っているなら、あらゆるlvalueは別のlvalueのaliasとなり得ると仮定すべきです。aliasingの問題は、ポインタ渡しされた値のときと同様に、参照渡しされた値に対しても考えられます。さらにポインタ型と参照型の任意の組合せにもaliasingの可能性があり、何かが起きたならaliasing rulesを調べるべきです。

後半:コンパイラが嫌がる方法

下記のプログラムは32ビット整数の半分を入れ替えており、これはリトルエンディアンとビッグエンディアンのマシン間でデータをやり取りする際に使われる典型的なコードです。このコードはstrict aliasing rules違反に関する6つの警告を生成しますが、多くの人は警告を無視してしまうでしょう。このプログラムの正しい出力は次の通りです:

00000020 00200000

しかし、最適化を有効にした場合は次の通りです:

00000020 00000020

正にこれこそ警告があなたに伝えようとした事であり、オプティマイザはあなたが望まない事を行っています。オプティマイザがあなたのコードを破壊したと考えてはいけません。コードはもともと壊れており、オプティマイザは単にあなたに対して指摘したに過ぎないのです。

壊れたバージョン
uint32_t
swaphalves(uint32_t a)
{
    uint32_t acopy=a;
    uint16_t *ptr=(uint16_t*)&acopy;// can't use static_cast<>, not legal.
                                    // you should be warned by that.
    uint16_t tmp=ptr[0];
    ptr[0]=ptr[1];
    ptr[1]=tmp;
    return acopy;
}

int main()
{
    uint32_t a;
    a=32;
    cout << hex << setfill('0') << setw(8) << a << endl;
    a=swaphalves(a);
    cout << setw(8) << a << endl;
}

何が間違っているのでしょう?規則ではuint_16_tuint32_tのaliasにはなり得ないため、acopyに対する操作は無視されます。swaphalves関数の中ではacopyに対する変更が行われていないため、関数はオリジナルのaの値を返します。gcc 4.4.1が生成したswaphalvesに対する(注釈付き)x86アセンブラを記載しますので、何が間違っていたのか見ていきましょう:

_Z10swaphalvesj:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $16, %esp
    movl    8(%ebp), %eax   # 引数aを%eaxに取得
    movl    %eax, -8(%ebp)  # その値をacopyへ格納
    leal    -8(%ebp), %eax  # acopyへのポインタをeaxに取得 (ptr=&acopy)
    movl    %eax, -12(%ebp) # ptrを-12(%ebp)に保存
    movl    -12(%ebp), %eax # ptrを%eaxに取得しなおす
    movzwl  (%eax), %eax    # ptr[0]から16ビットをeaxに取得
    movw    %ax, -2(%ebp)   # 16ビットをtmpへ格納
    movl    -12(%ebp), %eax # ptrを%eaxに取得しなおす
    addl    $2, %eax        # ptr[1]取得のために値2を加算
    movzw   (%eax), %edx    # 16ビットを%edxに取得
    movl    -12(%ebp), %eax # ptrを%eaxに取得
    movw    %dx, (%eax)     # 16ビットをptr[1]へ格納
    movl    -12(%ebp), %eax # 再びptrを取得
    leal    2(%eax), %edx   # ptr[1]のアドレスをedxに取得
    movzwl  -2(%ebp), %eax  # tmpeaxに取得
    movw    %ax, (%edx)     # ptr[1]へ格納
    movl    -8(%ebp), %eax  # 全て忘れて、オリジナルのaを戻り値とする
    leave
    ret

なんて恐ろしい!もちろんgccを使っているなら、-fno-strict-aliasingオプションを指定すれば望む出力を得られます。ただし生成されるコードはあまり良くないですし、問題解決の代わりに症状を抑えたに過ぎません。警告や誤った出力を得ること無く同じ事を達成するより良い方法は、swaphalvesをこのように定義することです。注意事項:これはC99以降のC規格でサポートされ、6.5.2.3 Structure and union membersのこの脚注で言及されています:

85. If the member used to access the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

85. unionオブジェクトの中身に対するアクセスに使われたメンバが同オブジェクトへの値の格納で直近に使われたメンバと同じでないならば、値のオブジェクト表現の適切な箇所は6.2.6で言及される通りに新しい型のオブジェクト表現として再解釈される。(このプロセスは“type punning”と呼ばれることがある。) これはtrap representationになりうる*2

ただしC++では話が変わってきます。私が知る限り全てのC++コンパイラがこれをサポートしますが、C++標準では許容しておらず、この方法に頼るのはリスクを伴います。この議論の直後にmemcpyによる別の解決策を示したいと思います。こちらはほんの少し非効率(そうでないこともある)ですが、CとC++の両方でサポートされます。

Unionバージョン:Cは解決するがC++では非ポータブル
uint32_t
swaphalves(uint32_t a)
{
    typedef union {
        uint32_t as32bit;
        uint16_t as16bit[2];
    } swapem;

    swapem s={a};
    uint16_t tmp;
    tmp=s.as16bit[0];
    s.as16bit[0]=s.as16bit[1];
    s.as16bit[1]=tmp;
    return s.as32bit;
}

C++コンパイラはunionのメンバが同じメモリに位置することを知っており、これがコンパイラが良質なコードを出力するのを助けます:

_Z10swaphalvesj:
    pushl   %ebp          # オリジナルのebp値を保存
    movl    %esp, %ebp    # ebpがスタックフレームを指す
    movl    8(%ebp), %eax # aeaxに取得
    popl    %ebp          # オリジナルのebp値を復元
    roll    $16, %eax     # a2つの16ビット部を入れ替え、それを戻り値とする
    ret

つまり、妙なキャストを用いて間違ったコードを得るか、strict aliasingを無効化して非効率なコードを得るか、正しく効率的なコードを得るかのいずれかになります。

memcpyを使った場合も、char*を用いた入れ替え操作のデータ移動と同じことを実現できますし、同程度に効率が良いものとなるでしょう。ちょっと待って、どうしてそうなるの?少なくとも2回のmemcpy呼び出しが必要となるのに!gccや他のモダンなコンパイラでは賢いオプティマイザを備えており、大抵の場合(今回のケースでも)memcpy呼び出しを省略するでしょう。このため、この方法は最もポータブルで他の方法と同じくらい効率的になります。どのように行うか見ていきましょう:

memcpyバージョン:C/C++規格準拠かつ効率的
uint32_t
swaphalves(uint32_t a)
{
    uint16_t as16bit[2],tmp;
    memcpy(as16bit, &a, sizeof(a));
    tmp = as16bit[0];
    as16bit[0] = as16bit[1];
    as16bit[1] = tmp;
    memcpy(&a, as16bit, sizeof(a));
    return a;
}

上記のコードに対し、2つのmemcpy呼び出しが追加されたこと(最適化で取り除かれる可能性あり)以外は、Cコンパイラは前の解決策と似たようなコードを生成するでしょう。なお、gccは前の解決策と全く同じコードを生成します。memcpy呼び出しの代わりに局所的charポインタを介した読み/書きを行うような別の解決策も想像できます。

似たような問題は、パケット逐次解析を行うネットワーク関連コードに見られます。ここで示したようにunionやmemcpyはあなたの友人となるでしょう。

restrictキーワード

C99では、C++には導入されていませんが、restrictキーワードを用いてポインタが指す先がaliasにならないとコンパイラに約束できます。コンパイラがaliasを想定しなければならない状況でも、その仮定が不要であるとコンパイラに約束することができます。つまり、このように:

void foo(int * restrict i1, int * restrict i2);

i1i2は決して同じメモリを指さないことを、コンパイラに約束しています。あなたはfooの実装について十分知っている必要がありますし、i1i2を介したアクセスが決してaliasにならないとした約束を守るように引数を渡さなければなりません。コンパイラはあなたを信じて最良の最適化を行います。もし約束を破るとしたら話は別です(そして、ほぼ確実に泣きを見ることになります)。なお、このキーワードはC++では使えません。

もしコメント、訂正、改善提案、例示等あれば、遠慮せずにメールをください。

Thanks,
Patrick Horgan

賛辞と謝辞

boost-usersやgcc-helpメーリングリストでこの文書に関する議論に参加してくれた皆様に感謝します。ここで使ったmemcpyバージョンを書き、同一アセンブラが生成されることを指摘してくれたVáclav HaismanとThomas Hellerに、union定義によるポータブルな方法およびgccがmemcpy呼び出しを省くことも指摘してくれたAndrew Haleyに感謝します。

さらに誤植を指摘してくれたGabe Jonesに感謝します:)

*1:訳注: 2012年2月現在は、正式な標準規格 ISO/IEC 9899:2011 が発行済み。

*2:訳注:"trap representation"はCの規格で"an object representation that need not represent a value of the object type."と定義されている。c++ - trap representation - Stack Overflowなども参照のこと。

koheptakohepta 2015/08/08 04:07 > movw %dx, (%eax) # 16ビットをptr[1]へ格納
のコメントは "16ビットをptr[0]へ格納"

> movl -8(%ebp), %eax # 全て忘れて、オリジナルのaを戻り
は movl 8(%ebp), %eax ではないでしょうか?

-8(%ebp) は acopy だと思います。

yohhoyyohhoy 2015/08/11 20:45 頂いた2点のコメントですが、どちらも訂正不要と考えています。

>> movw %dx, (%eax) # 16ビットをptr[1]へ格納
> のコメントは "16ビットをptr[0]へ格納"
3行前の「addl $2, %eax」でeaxレジスタ値+2していますから、ここはコメント通り ptr[1] に相当します。

>> movl -8(%ebp), %eax # 全て忘れて、オリジナルのaを戻り
> は movl 8(%ebp), %eax ではないでしょうか?
> -8(%ebp) は acopy だと思います。
変数acopyへ退避した値はオリジナルの引数値aですから、論理的な誤りはありません。Cコンパイラが「return acopy;」からアセンブリに直訳した結果ですね。

anonymousanonymous 2016/02/20 10:27 上のかたではありませんが、気になりましたのでコメントさせていただきます。
文脈を取り違えていたら申し訳ないのですが、上記アセンブラは「一見良さげに見えるコードをコンパイルしたら最適化により正しく動作しないものになった」例だと認識しています。
しかし、手元のgccが生成したアセンブラのswaphalves関数部分を上のアセンブラで上書きしたところ、正しい出力(値がスワップされた出力)を得られました。
該当アドレス、つまり-8(%ebp)に格納された値をptrを通じて間接的に書き換える処理がきちんと行われているため、スワップされた値が出力されるものと思われます。
koheptaさんが言っているように movl 8(%ebp), %eax としたところスワップされませんでしたが、おそらくそうではなく、そもそも貼り付けるアセンブラが間違っていたのでは無いかと思われます。
上記アセンブラは最適化をかけたにしては冗長なコードが多すぎるため、「最適化をかけたら動かない例」を見せるはずが間違えて「最適化をかけていないときの出力」を貼り付けてしまったのではないでしょうか。

yohhoyyohhoy 2016/02/26 21:16 koheptaさん anonymousさん が指摘された問題を理解しました。
誤って最適化なしアセンブラ出力を載せている可能性がありますね。実際にコードを動かしてみても、確かに正しい結果の方が得られます。

アセンブラコードが誤っていても趣旨が無効になるわけでもないため、原文に合わせてこのままとしておきます。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証