Profile cover photo
Profile photo
Rui Ueyama
1,067 followers
1,067 followers
About
Rui's posts

Post has attachment

Post has attachment

Post has attachment

CS243の予習として去年の講義内容のスライドをみていたら、Datalogというよくわからない記法を使ってアルゴリズムが説明してあった。調べてみるとどうもPrologをチューリング不完全にしたような論理言語らしい。確かにプログラムの解析はなんでもグラフの問題になるというか、代入とか処理の流れの合流とかの関係をたくさん定義しておいてある関係が満たされているかどうか確認する、みたいな感じになるから、こういうもので説明するのはいいかもな。そういやPrologとか実装したことない。

Nexus 6入手の軌跡(まだ入手してない)
11/05 Google Playで瞬時に売り切れる。手動のみでは買えないと悟る
11/12 毎週水曜日に売るということなので毎秒3回くらいアップデートをチェックするスクリプトを書いて超高速で操作をして買う(買えた)
11/26 出荷予定なのに出荷されない。サポートに問い合わせるも$10のPlayクーポンなどで懐柔される
12/03 感謝祭が過ぎた後やっと出荷
12/08 配送遅延。感謝祭セールの影響?
12/10 さらに遅延。カリフォルニアの嵐の影響?
12/12 やっと会社に届く。国内の宅配で9日もかかった。本来間に合うはずだったのに俺がすでに日本にいってしまっているので転送を頼む
12/18 物品の国際配送は会社では扱っていないため留め置かれていることが発覚

結論としてはできる限りの努力は尽くしたが何もかもがダメ。

Stanfordのオンラインの社会人コースを取ってみた。Program analysis and optimization (CS243)。この分野は俺も多少はプロだから実は簡単かと思ったけど、去年の試験問題とかをみてみるとやっぱり答えがわからない。このレベルのガベージコレクタとかは楽勝だがフロー解析とかはよくしらないからなぁ。勉強しないと。

サーベイの続き。Chris Lattnerが書いたLLVMの論文を読んでみたけど、これはLLVMのわかりやすいイントロダクションとしてもっと前に読んでいるべきだったな。中間言語はLLVMのやり方でいいと思うんだけど、それ以外のやり方がわからないという状態で真似するのは面白くないので、もうちょっと情報を仕入れたい。Typed aseemblyというキーワードで調べてみるとよさそうな気がする。

多少サーベイしてみた。LLVMはMemory SSA形式だみたいな話を聞いた気がしたので、Memory SSAで引っかかった論文をまず見てみたら、冒頭に「SSAはスカラー型のデータフローを表現するには適しているが、配列や配列のような集合型や、グローバルな変数へのポインタなどにうまく適用しにくい」みたいなことが書いてあった。まさにそこが引っかかっていたところだよ、とか思ったら、著者は同じチームの人だった。なんだキミか・・。(論文自体はGCCの知識が前提みたいな感じでちょっと理解できた自信ないが。)

CやC++の非常によく書けているブログもみつけたけどこれも社内でLLVMやっていて以前に話したことある人だった。やっぱり結構集まってるのね。環境としては過分なくらいで申し分ない。

いま書いているコンパイラバックエンドでは、パーザからの出力をx86-64アセンブリに落とすには次のような手順になる。

普通のCの式は a + b * (c + d) みたいに入れ子になっていて、パーザの出力の段階でもこれは木構造のまま残っている。アセンブリでは基本的にレジスタAにレジスタBを足す、みたいな二項の演算しかできないので、ここのギャップをまず埋めなければいけない。そのためには計算途中の値を明示的に取り出して

%1 = c + d
%2 =  b * %1
%3 = %1 + %2

みたいな表現に単純化する(構文木を下って内側から処理していけばこの変換は簡単にできる)。

あとはこの式1行についてアセンブリを1行出力していけば完成、なわけだが、変数は何個にでもなりうる一方でレジスタ数は有限(16個とか)なので、このギャップも埋めてやらないといけない。

必要に応じてレジスタの値をメモリに退避(スピルするという)すればよいのだが、これには色々なやり方がある。性能に大きく影響してくる部分でもあるのでここらへんはよく研究されている。

いまのところは超簡単な方法として、全部のテンポラリな変数をスタックに割り当ててしまって、レジスタが足りなくなったら必ずスピルするようにしてしまった。あとで使われない変数まで退避するので無駄が多いけど、これをきちんとやるためにはliveness analysis(ある段階でもう変数がそれ以降使われないかどうかの解析)をやらないといけないので、とりあえずはこれでよしとする。

ここらへんの分野になってくるとなぜかそこそこ理論も知ってるけど、たぶんもう一回本のそこらへんを読むことになるんだろうなあという感じ。

可能ならバックエンドは1000行〜2000行程度に収めたい。え、これだけ? というくらいが理想。書きかけの状態で300行ちょっとだからまだどうなるかよくわからない。

新バックエンドはとりあえず int main() { int x = 2; return x + 3; } くらいはコンパイルできるようになった。逆に言うとこれくらいしかできないけど。

方針としてはClangが出力するLLVMアセンブリ的な中間コードにいったん内部的に変換してからアセンブリに変換することにした。あまり面白みはないが実現可能なことは間違いないだろうから無難な選択肢だろう。

結局また今日もレキサーのリファクタリングをしてしまった。トランスレーションフェーズごとにきれいにコードを分離したのでコードの質は上がったと思うけど、完成だと思ってもいくらでもいじり続けられるのは生産性という面ではいいんだか悪いんだか。
Wait while more posts are being loaded