noreturnの挙動(続)

id:MaD:20081209のコメント欄が長くなり過ぎたので新たに書きます。

稲葉さんからご指摘を受けましたけど、どうも最適化云々はおまけで本命はどうも if(foo) { abort(); } else { return bar; } のようなコードでコンパイラに警告を出させないことのようです。

http://d.hatena.ne.jp/MaD/20081209#c1228920872

警告抑止で使われる事は知っていたのだけれど, おまけも本命もあるのか？と思ってよく考えてみたら全くその通りだった。

非常に勉強になったので説明します。
まず上の様なコードのコントロールフローグラフは一番左の様になります。
return bar;はそこで関数を抜けるので次のエッジは除去しています。
このままだと右側のフローが値を返さないのでコンパイラが困ります。そこでfにnoreturn属性をつけると, 右の関数コール後のエッジが除去される(GCCではこれをnoreturn edgeと呼んでいる)ので,問題が解決します。

基本的にはnoreturnの役割はこれだけ(関数コールの次のエッジをnoreturn edgeにする)です。
そして次に到達不能コード除去(Dead code elimination)という別の最適化が行われると一番右の様になり, 元よりスリムなコードが生成されます。

つまり, 実際に関数呼び出し後の後処理コードを消しているのはDead code eliminationなので, noreturnの最適化効果はいわばたなぼたということですね。(もちろん処理系の実装方法により変わるのですが)

これは私の勉強不足でした。稲葉さんありがとうございました。(もし稲葉さんの意図が上と違うことならば是非教えてください)

そうすると「最適化できないとnoreturnの存在意義なし」とは言えないですね。ごめんなさい。

ただ, 良く分からないでattributeを使っちゃうような素人が利益を得て, 正しく使っている玄人が不利益を被るようなチェックの追加はやっぱり反対ですし, exit()等にnoreturnを追加すべき説得力のある理由もやっぱりないと思います。

言いたいことは言ったので, あとは主査の取りまとめを大人しく待とうと思います。

noreturnの挙動

参加できなかった午前中の会議のレポートが気になってたけど出た。終わっちゃった会議にケチつけるのは野暮だけれど,noreturnの話がなんかいろいろおかしい。「何の為のnoreturn？」という肝心な点がどっかいってる。

exit等にnoreturn属性を付けてほしい

http://d.hatena.ne.jp/faith_and_brave/20081208

なぜ???? exit()は標準関数なんだから, 返らないのはコンパイラが知っていますよ。
規格でも"The function exit() never returns to its caller."ってなってるし。
exit()にnoreturn属性を付けてほしいという人はいったい「何の為に」付けてほしいのか？

「せめて関数が返る場合に未定義エラーというのはどうにかしてくれ」というコメントに修正することになった

http://d.hatena.ne.jp/faith_and_brave/20081208

関数が返る場合のチェックを強制したら,最適化できない(場合によっては遅くなる)んだからnoreturnの存在意義がなくなるじゃん...(´･ω･｀)

例えばnonnullというattributeがあったとして

void f(int *p [[nonnull]]) {
    ....
}

とした場合に, pのnullチェックを挿入しろと言っているようなもんです。それはおかしいでしょう。

[C/C++] C++WG アドホック会議に行ってきた

試験とバイトに挟まれいて, 途中から入って途中で抜けてきた。
誰が誰だかわからないまま抜け出さなければならなかったのが残念。

議題としては文字コード対応の話題で盛り上がったのが印象的。
普段最適化関係しかやっていないので, 文字コードの問題を考えた事は一度もなかった。
コンパイラ屋さんてきには「それライブラリでやって」と言いたくなるような面倒な問題であるのは確実。どういう解決策を提示してもらえるかに期待。

ところで, 「atomic access系の関数にはなぜshared_ptrの参照ではなくポインタを渡すのか？」という話で「ポインタじゃなきゃまずい」という主張をしたところ「参照も結局ポインタだから同じでしょ？」という話になったが, やっぱりそれは違うのでコンパイラ内部で何が行われるかについて後で書こうと思う。

X[Y] と Y[X] は異なる。

注:以下の話は間違いでした(下の方に訂正書きます)

今日見つけた自作コンパイラのバグ。型検査時に

整数[配列]

のパターンを

配列[整数]

の形に直してしまっていた。
a[i]とi[a]が同じというのはC言語では有名な仕様だけれども,オペランドの評価順序の問題があるので実際には同じではない。

同じようなミスで,

(整数) + (ポインタ)

を

(ポインタ) + (整数)

に直すなどをしてしまっていた。
実際にはこれらの入れ替えは正規化をしてオペランドの副作用を除去してからでなければならない。

訂正

上で書いたのは間違いだった。
まずC言語ではオペランドの評価順序は基本的に処理系依存であるという事を忘れていた。

しかし,X[Y]とY[X]が同じかどうかも処理系依存になるのかというと, どうやらそうではないらしい。
まず規格には「(P)+N (equivalently, N+(P)」とあるのでequivalentの意味を間違っていなければ

(ポインタ) + (整数)
(整数) + (ポインタ)

の意味は同じでなければならない。つまり, もし上の式を左->右と評価するならば, 下の式は右->左と評価しなければならない。

そして, 「E1[E2] is identical to (* ((E1) + (E2)))」とあるので,(E1) + (E2)の部分に上と同じ規則が使用されるわけだから,

a[i]
i[a]

のどちらも評価順序が同じでなければならない。上の式がa->iと評価するならば, 下の式もa->iと評価しなければならない。

つまり, 「構文が同じでも型に依存して評価順序が変わる」という奇妙な現象がおきるらしい。

実際にGCCで実験してみたところ,

(puts("foo"), 1) + (puts("bar"), 0);

は

foo
bar

と出力されるが,

(puts("foo"), 1) + (puts("bar"), (void *)0);

は

bar
foo

となった。

ということで, 自分がバグだと思ったものはたまたまバグではなかったわけだが, 仕様を全然わかってなかったという事で反省。

C++0xのaxiom

今まで見逃していたけれども, こんなものが追加されるのか!

a + b == b + a;
(a + b) + c == a + (b + c);

みたいな論理的な性質を型に与えることができるという仕様。

Haskellのrewrite rulesを連想したが論文を見つけた。
Axiom-Based Transformations: Optimisation and Testing
仕様は詳しく見ていないけれど, これは夢が広がるなぁ。

一つ残念なのが, 関数の性質を指定することができないであろうということ。
それができたら, 融合変換みたいな面白いこともできただろうに。

言語仕様が巨大すぎるのでいざコンパイラ作ろうと思っても大変だろうな。

C++0x - (無駄仕様) - (Cの負の遺産)

のような言語がほしくなってきた。

C++0xのCommittee Draftへのコメントへのコメント

コメント一覧を一通り読みましたが, 来週の会議には後半から3時間くらいしか出れないので今の内にコメントを書いておきます。
コンパイラ実装上の観点を中心に。

01. decltypeにスコープ演算子(::)を使用できない

これは賛成です。
ところで, simple-type-specifierからdecltypeを削除しちゃったら, 型として使えませんからこの削除はいけません。
また,

nested-name-specifier:
    ...
    decltype(expression) ::

の最後の::が抜けています。

# この場合, 構文規則に衝突は起きていないだろうか...?

04. noreturn属性の挙動

attributeはコンパイラが解析できない情報を教えてあげる為にあるものですから, attributeが正しいかコンパイラが解析するというのは本末転倒です。
ここでいう「返る」は「返るパスがある」とは意味が違いますから, コンパイラで解析することは不可能です。

# ところで,個人的にはこういうattributeは処理系任せにしちゃった方が良いんじゃないかと思うんですがどうなんでしょうか。どっちみち, 処理系がいろいろ新しいattribute追加しだすと思うので。attribute用の構文を用意したというだけではいけないのでしょうか。

14. コンセプトによってイテレータの機能が制限される

std::RangeコンセプトのイテレータがInputIteratorな理由の一つに,最適化があると思います。
std::Rangeには範囲ベースのforループを記述する為の役割があるわけですが,この拡張のおかげでコンパイラによる自動並列化等のループ最適化が楽になります,しかしこれがランダムアクセスイテレータだとせっかくの範囲ベースが無駄になります。

なので, 私はstd::Range::iteratorがInputIteratorである事を支持します。

26. std::cin などをbinary reopenできる方法がほしい

これはstd::ios::binaryを間違えて理解しています。
標準入力からバイナリを入力するという場合にstd::ios::binaryを指定する意味はないです。
非POSIX準拠システムではファイルシステム中のテキストファイルとバイナリファイルを別々に扱うものがあり, その為にstd::ios::binaryは用意されています。テキスト"データ"とバイナリ"データ"を区別する為のものではないですから, 標準入力からバイナリデータを入力する場合は普通に(streambufとかで)読めば良いです。

Cの構文解析(宣言構文)

C言語の構文解析では宣言構文もなかなか大変なので紹介。処理系を作る人の参考になれば。

変数を宣言・定義する場合, 普通に考えれば

[型] [変数名];
[型] [変数名] = [初期値];

という構文を採用するのが自然だと思う。例えばJavaやD言語などの新しい言語では

int[] x;

の様な構文を採用している。

しかし,CやC++では[型]の部分が構文的に独立していない。例えば

int x[10];

はもちろんけれども,

int *x;

も構文上は

[int] + [*x];

となっている。*1
従って,この構文を正しく読むと「int*型のxの宣言」ではなく「int型のポインタ注釈付きxの宣言」となる。
このx[10]や*xの部分を「宣言子」と言い, 他には関数の仮引数列が含まれる。

このような構文を取るため, C言語では異なる型の識別子を同一の宣言文で宣言することができる。

int x, *y;
double a, b[10], c(void);

構文解析の手順

以上の事情からこれらの構文を解析する際には, ベースとなる型と宣言子を別々に取得した後に, 実際の型を再構築する必要がある。宣言子の構造を保持する為に余分なデータ構造を用意しなければならないけれども, 再構築自体は単純で以下の様になる。

• 宣言子の一番外側の要素から順にベース型に適用して(移して)いく。
• 一番外の定義は
  • ポインタ注釈'*'が最優先
  • 次いで配列"[..]"と関数"(...)"

イメージとしてはこんな感じ。

int *x[10]
 ↓
int - *x[10]  型と宣言子を別々に得る
 ↓
(Pointer int) - x[10] 一番外の'*'を左に移す
 ↓
(Array 10 (Pointer int)) -  x  一番外の[10]を左に移す

ということでxの型「intへのポインタの配列(長さ10)」が得られる。

いくつかの例

int (*x)[10]
 ↓
(Array 10 int)  -  *x
 ↓
(Pointer (Array 10 int)) - x

よりこれは「intの配列(長さ10)へのポインタ」となる。

int f(int x)[10];
 ↓
(Array 10 int) -  f(int x)
 ↓
(Function [int x] (Array 10 int)) - f

よりfの型は「intの配列(長さ10)を返し, 仮引数がint xの関数」となる。Cの関数は配列を返せないのでこれはエラーである。

void (*f(int x))(int x)
 ↓
(Function [int x] void) - *f(int x)
 ↓
(Pointer (Function [int x] void)) - f(int x)
 ↓
(Function [int x] (Pointer (Function [int x] void))) - f

よりfの型は関数ポインタを返す関数となる。

という感じで, 宣言子側から型側へと飾りを移すという作業を再帰的に行う事で変換ができる。

*1:これはC++の参照「&」,C++0xの右辺値参照「&&」でも同様。