ttth @ ウィキ
ttth @ ウィキ

buyobuyon 続き


ページに入り切らなくなったので、2月の書き込みを分離しました。


2/26(Mo)


min-rtをコンパイルして、MAKECLSが出ないことに気づき、
MAKECLSが出ないはずがない、きっとバグだ！と思ってコードを見直していたのですが、
バグは見つからず…。
逆にmin-rtの方を見直してみたところ、バグではないという結論に至りました。
う～ん、無駄に時間を使ってしまった…。
コンパイラ係用課題は間に合うのか…。

上記の通り、コンパイラをアップしておきました。
ダウンロード、使い方はこちらから。


2/25(Su)


ええと、スタックポインタとヒープポインタの初期化を入れ忘れていたので、それを追加。
それだけです。
一応、この前と同じfibをコンパイルしたものを。


:INIT;
mov r125, 1048576;
mov r126, EOF;

:MAIN;
mov r2, 15;
jmpl fib_00000002;
add r0, r0, r0;
end;
add r0, r0, r0;

:fib_00000002;
mov r124, 1;
cmplt r123, r124, r2;
not r122, r123;
beq r122, LABEL_00000010;
add r0, r0, r0;
addi r2, r2, 0;
ret;
add r0, r0, r0;
:LABEL_00000010;
addi r125, r125, -3;
storei r2, r125, 2;
mov r121, 2;
sub r2, r2, r121;
storei r127, r125, 0;
jmpl fib_00000002;
add r0, r0, r0;
storei r2, r125, 1;
mov r124, 1;
loadi r123, r125, 2;
sub r2, r123, r124;
jmpl fib_00000002;
add r0, r0, r0;
loadi r124, r125, 1;
add r2, r2, r124;
loadi r127, r125, 0;
addi r125, r125, 3;
ret;
add r0, r0, r0;

:EOF;

  • 一応コンパイラではnopをadd r0, r0, r0;として出力していますが、
    コンパイラではnopと出力して、アセンブラの方で変換してもらう形にした方が良いですかね？
    今の書き方だと見にくいのは確かですよね…。 -- buyobuyon (2007-02-26 02:15:44)
  • あの、
    :INIT;
    mov r126, 1048576;
    は、
    mov r125...
    ではないですか？
    関数中にr126がなくてr125があるので…
    -- yastak (2007-02-26 15:33:17)
  • すみません、仰るとおりです。
    コンパイラ内部で用いているレジスタのIDから
    実際に使用するレジスタの番号への関数を間に挟むのを忘れていました。

    どちらにせよ、HPの初期化に関して、少し見直す必要がありますね。
    外部変数の領域を考慮していなかったので…。

    外部変数の値のセットってどうすれば良いのですかね？
    とりあえず、外部変数に関してコンパイラでは、MinCaml同様、
    その外部変数と同名のラベルが存在していて、
    そのラベルの値が外部変数の値(配列やTupleならそれが配置されたメモリ領域の先頭アドレス)であることを
    想定しているのですが。 -- buyobuyon (2007-02-26 15:54:32)
  • SPとHPの初期化の間違っていた部分、直しておきました。
    お手数おかけしてしまい、申し訳ありません。 -- buyobuyon (2007-02-26 15:58:58)
  • 修正ありがとうございます！

    >外部変数
    ラベルの値って、そのラベルのおかれた行数と言うことですか？
    それとも、そのラベルのおかれた行数に格納されているデータ、
    ということですか？
    …それとも完全に勘違いしているかな(>_<)汗

    あと、movなんですけど、
    上のソースだと、movをレジスタへの即値代入のように使っていますよね。
    すると、movがどこかでhi,addiの2命令になったときに問題起きませんか？
    mov r1,label
    は今までの2命令mov分増やす（labelが後ろの場合のみ？）べきだけど、
    mov r1,val
    で即値代入の用途に使っていると、2命令mov分増やして代入するとマズイのでは…？
    （movi,movlに分ければ解決しそう？）

    あと、どこかで
    mov r1,val
    ↓
    hi r1,val(上位bit)
    addi r1,r0,val（下位bit）
    という変換になっていたけど、
    addi r1,r1,val（下位bit）
    としないとhiで入れた上位ビットが反映されない気がします～。
    （これはアセンブラ側？）

    すでに解決済みの問題だったらすみません…。 -- yastak (2007-02-26 19:40:51)
  • アドバイスありがとうございます。
    そのように直しておきます -- はりー (2007-02-27 00:10:03)
  • addi r1,r0,valバグの件、すみません。
    2/16のコメント欄で、私が間違えていましたね…。

    外部変数・ラベルのことですが、
    コンパイラの方は、各ラベルがアセンブラによって
    適当な値(先ほど言ったラベルの値とはこれを指す)で
    置き換えられることを期待しているわけです。

    で、その想定しているラベルの値というのは、
    関数やジャンプ先のアドレスを表すラベルの場合は言うまでもありませんが、
    そのほかに、外部変数に関するラベルが存在していて、
    このラベルの値は、ラベルと同名の外部変数(組か配列)が配置された
    メモリ領域の先頭アドレスとなっていることを想定しています。

    問題は、その外部変数の配置とそのラベルの定義なのですが、
    どうすれば良いのかなと。

    アセンブラに、いわゆる".byte"(4バイトだから".word"かな？)のような
    データを書き込むための記法を導入してもらわないといけないかな、
    と思うのですが、どう思います？

    むしろ私の方が勘違いをしているのかな…。 -- buyobuyon (2007-02-27 02:50:30)
  • たとえば、配置は、SP,HPと同様にEP(extern pointer)
    を作って、そこから配置するようにしてみるとか。

    コンパイラコードの冒頭から:INIT;までを外部変数の定義として、
    :EXTERN_001;
    :EXTERN_002;
    ...
    :EXTERN_00n;
    :INIT;
    SP;
    HP;
    EP:

    で、EP + :EXTERN_00nで、外部変数の格納されている場所を示すとか。
    組と配列になると、先頭要素のみなので、
    ダミーのラベルを書いて行を埋めてしまうのはどうでしょう？

    コンパイラコードは冗長になってしまいますが…
    （まぁマシンコードとしては増えないしｗ）

    でもこれだと外部変数～INITまでと、
    INIT以降と、ラベルの処理をわけなければいけない気がしますね。
    （フツウのラベルはそれ自体では行数をとらないので、
    ラベルが続くと全部同じ値になる気が…。）

    すると、外部変数の読み込みは
    LOADI r1,EP,label
    とかになるのかな？
    （という理解で大丈夫ですかね…） -- yastak (2007-02-28 03:15:33)
  • レスありがとうございます。

    う～ん、INITを境にラベルの処理を分けるとすると、
    結局アセンブラに変更が必要ですね…。
    しかも、今のままだと指定したアドレスに指定した値を
    明示的にアセンブラに書かせることができないから、
    結局、外部変数(配列・組)の要素の値の初期化ができませんよね…。
    (できるけどそれにプログラムの実行時間を使ってしまいますよね)

    考えていたのは、コンパイラコードの直後にデータ領域を作って、

    ・
    ・
    ・
    （コンパイラコード）
    :EOF;
    :EXTERN_001;
    .word 0xffffffff
    .word 0xffffffff
    :EXTERN_002;
    .word 0xffffffff
    .word EXTERN_003
    .word 0x00000000
    .word EXTERN_004
    :EXTERN_003;
    ...
    :EXTERN_00n;
    .word 0x10101011
    .word 0x10101011
    :HPTOP;

    という感じで、命令コード列の終端とHPのトップとの間に
    データ領域をとり、.word文で、オペランド値(32bit)を
    そのままその位置に書き込むというようなものなのですが。

    .word文をアセンブラに実装してもらう必要がありますが、
    .wordはただオペランド値をそのまま書き出せば良いだけなので実装は簡単ですし、
    .wordが1行食ってくれるので、ラベルの扱いもそのままで良いはずですよね。

    コンパイラのコードもそのままで良く、
    あと、コンパイラのコードの直後に
    データ領域を表すラベルと.word文の列を
    書き足せばよいのでいろいろと都合がよいですし。

    と、言う感じなのですが、どうですかね…。
    とりあえず、今日はコンパイラ係用課題をやらないと…。 -- buyobuyon (2007-02-28 04:55:39)
  • なるほど…！
    どちらにせよアセンブラの変更は必要だし、
    そうすると、.wordを作ってしまった方がやりやすそうですね！

    コンパイラ課題頑張ってください(>_<)/ -- yastak (2007-02-28 22:36:11)
  • 今、提出しました。
    あれで良いのかどうかは微妙なところですが…。
    46:46まで起きているとつかれますね…。 -- buyobuyon (2007-02-28 22:46:13)
  • とりあえず、.wordによる方針で、
    外部変数定義解析機作ることにしますね。 -- buyobuyon (2007-03-01 12:05:27)



2/23(Fr)


このページだけ落ちてしまっていたので何だろうと思ったら
単にページのサイズが大きくなりすぎただけだったみたいです。
後ろの方を削ったら生き返りました。

ところで、コンパイラが、tupleやクロージャのサイズが、
addiなどの定数部で表現できる範囲を超えた場合の動作は保証しない
という仕様になっているのですが、これは別に良いですよね？
さすがに自由変数が1000個あるクロージャとか作りませんよね？
範囲を超えたときに警告くらい出した方が良いのかな…。

う～ん、そろそろコンパイラ係用特別課題の方もやらないと…。
どれにしようかな…。


  • メモ
    ・まず、mov r1, r1をなんとかしよう。
    ・if not C then A else B を if C then B else A にするのはK正規形のときでOK
    ・複数ある比較命令を有効に利用。
    ・演算の第2オペランドが小さな定数のときにaddiなどを利用する。
    ・意外とadd r0, r0, r0は減らせそうな気がする(条件分岐部分は少し難しいかな…)。 -- buyobuyon (2007-02-23 14:49:40)
  • コンパイラお疲れさまです♪

    えーと、ちょっと確認ですが、
    jmp,movなどはラベル値と即値の両方がありえますよね？
    アセンブラは
    jmp HERE;
    jmp 355;
    の両形式に対応するようにしなければいけないんですよね？

    -- はりー (2007-02-26 00:27:43)
  • movは両方対応してください。
    jmpはとりあえずラベルしか使っていません。

    何なら、ラベルからコピーする命令movlと、
    即値からコピーする命令moviの2つに分けるという方針でも良いですよ。
    コンパイラの方でそれらを使い分けるのは簡単なので。 -- buyobuyon (2007-02-26 01:46:40)
  • あと、mov r1, r2のように、レジスタからレジスタにコピーすることはありませんので。
    (addi r1, r2, 0に変換してあります) -- buyobuyon (2007-02-26 01:51:43)


2/22(Th)


ええと、ご無沙汰いたしております。

コンパイラですが、とりあえずコンパイルできるようになりました。
一応、fibをコンパイルしてみました。シミュレータでのテストは行っていません。 

 let a = 15 in 
   let rec fib x = 
     if x <= 1 then x
       else fib (x - 1) + fib (x - 2)
   in
     let c = fib a in ()


↑が、


:MAIN;
mov r2, 15;
jmpl fib_00000002;
add r0, r0, r0;
end;
add r0, r0, r0;

:fib_00000002;
mov r124, 1;
cmplt r123, r124, r2;
not r122, r123;
beq r122, LABEL_00000010;
add r0, r0, r0;
addi r2, r2, 0;
ret;
add r0, r0, r0;
:LABEL_00000010;
addi r125, r125, -3;
storei r2, r125, 2;
mov r121, 2;
sub r2, r2, r121;
storei r127, r125, 0;
jmpl fib_00000002;
add r0, r0, r0;
storei r2, r125, 1;
mov r124, 1;
loadi r123, r125, 2;
sub r2, r123, r124;
jmpl fib_00000002;
add r0, r0, r0;
loadi r124, r125, 1;
add r2, r2, r124;
loadi r127, r125, 0;
addi r125, r125, 3;
ret;
add r0, r0, r0;


となりました。
コンパイラの方のソースのupはしばらくお待ちを。今、ひどい状態なので。

一応、前回書き込み以降進んだことは、仮想マシンコードでの不要定義除去、
末尾呼び出し最適化に対応したレジスタ割り付け、SAVEとSPの操作の挿入、
ほぼアセンブリコードに対応するデータ構造への変換、アセンブリコード生成、
ですね。

ジャンプ系命令とSTOREDの直後は、とりあえず全てNOPにしてあります。
これらはアセンブリコードに対応するデータ構造上でいくらか変換をすれば
ある程度別の命令で埋まると思います。


2/18(Su)


久々の24時前の書き込み…。
とりあえず、関数呼び出しもSpillも条件分岐もないプログラムのレジスタ割り付けはできるようになりました。
まぁ、つまりまだ何もできないわけですが、細かい関数の実装が終わったということです。
あと、条件分岐合流時のつじつま合わせと、SAVEの挿入ですね。

  • メモ
    if文による選択や関数の返り値の部分は、
    単なるmovだとtargettingがうまくいかない。
    (restore(v), (v' := v, NULL))
    → 直接v'にLOAD
    の変換が必要。 -- buyobuyon (2007-02-19 00:21:03)
  • クロージャ変換にバグ発見…。
    こんな調子で、コンパイラは最終的に動くのだろうか…。 -- buyobuyon (2007-02-19 05:10:24)
  • クロージャ変換の方は直りました。
    あとは、SAVEの挿入。
    テストするのが面倒です…。 -- buyobuyon (2007-02-19 08:25:31)
  • なるほどね。ありがとう！

    負の数も考慮して（する必要ある？）
    nがー1024〜1023のときはaddiのみにすればいいのかな
    そうするとn>=1024,n<1024の場合の（movが2命令に変換される）
    回数だけを行数に足せばいいんだよね？

    色々聞いてすみません。。。(m_m) -- はりー (2007-02-19 18:00:00)
  • ↑たぶん、そうだと思います。 -- buyobuyon (2007-02-19 23:55:51)


2/17(Sa)


コードを書き始めてから問題があることに気づいて書き直す、ということを繰り返しているもので、
ほとんど進んではいませんが、一応作業をしていることだけアピール。

  • 作業を進めれば進めるほどシンプルになっていく…。 -- buyobuyon (2007-02-18 05:32:31)


2/16(Fr)


私にとっては2/15の34時30分ですが…。
ええと、仮想マシンコード生成のデータ形式を新しいのに書き換えるのが終わって、
レジスタ割り付けのうち、一番悩んでいた部分である、条件分岐のところでのレジスタ割り当ての要求
(退避すべきかどうか、どのレジスタに割り当てて欲しいかなど)をコードにまとめ終えたところです。
いろいろと妥協もあったので、賢いレジスタ割り付けになるかどうかは微妙です…。
そもそもSpill無視ですし…。
まだまだ先は長いですが、とりあえず一休み。

  • 34時３０分。。。
    本当にお疲れ様です。
    -- harry (2007-02-16 12:02:13)
  • To ぶよぶよん
    質問です。
    えーとmovのところですが、

    （1）例えばラベルfuncがn行目(ただしnはラベル値だから32ビット）
    でしたら
    mov r1, func;
    を
    hi r1 (n>>11)　　　　　ーーーまずラベル値の上位21ビットをr1に入れる
    addi r1, r0 , ((n<<21)>>21)　ーーー更に下位11ビットを足す
    にすればいいのかな？

    （2）でもラベル値が11ビット越えることはそんなに無いと思うから、
    条件分岐で
    n<2047(11ビット以下で収まる）の場合は直接
    movをaddi r1, r0, nに
    n>=2048の場合はこのようにaddiとhiの組み合わせにした方が速い？？かもしれないよね？どっちがいいのかな？

    (3)演算命令のオペランドにラベル値が出てくるのはここだけでいいのかな？


    -- はりー (2007-02-17 13:33:32)
  • (1)
    はい。(nは符号無し整数(>>, <<が論理シフト)ですよね？)
    ただ、movが2命令に置き換わるので、
    正確にはnは行数ではなくて、行数にそれまでのmov数を足した値になりますよね？

    (2)
    ええと、11ビット超えることは結構あるような気が…。
    でも、11ビットで収まる範囲にも多くの関数が置かれるはずなので、
    addiのみで済む場合にはaddiのみにするよう最適化すれば、
    結構な効果は得られると思います。

    (3)
    たぶん…。 -- buyobuyon (2007-02-17 14:46:35)
  • あ、あとaddiの定数部分は11bitの符号付き整数なので、
    addiのみでOKなのはn<1024のときですよね。 -- buyobuyon (2007-02-17 14:50:05)


2/15(Th)


ええと、まだほとんどコードは書いていないのですが…。

一応、Cで書いているので充分速いだろうということで、コンパイルにかかる時間は考えず
(面倒なので、DPなんて考えず、同じものを何度も計算するつもり)、
またレジスタが充分にあるので、Spillはほとんど起こらないものとして
(Spillが起こっても正しく動くが、生成されるプログラムの効率は保証しない)
レジスタ割り付けの方法を考えています。

あとは、条件分岐のときをどうするか…。例えば
A; if B then C else D; E
で、Aで定義されたものがEで使用され、Cには関数呼び出しがあり、Dには無い場合には、
C内で退避・復帰を行うのが良いですよね。一方、
A; if B then C else D; if E then F else G; if H then I else J; K
で、Aで定義されたものがKで使用され、CとFとIに関数呼び出しがあり、DとGとJには無い場合には、
3回退避を行う方が大変なので、Aの直後で退避を行った方が良いですよね。
退避・復帰が必要なパスの密度(全パス中の退避・復帰が必要なパスの割合)が1/2以下なら
if内部で退避・復帰、それ以下ならif外部で退避し、
確実に必要になった時点(密度が1になった時点)で復帰。
こんなので、良いかなと考えているのですが、実装するのが面倒だな…、と。

あと、インライン展開をしたときに、Spillがほとんど起こらないという前提が崩れそうで怖いです…。

う～ん…、とりあえずコードを書きながら考えます。

  • 再帰関数は、再帰呼び出しする側の分岐先の方が多く実行されるでしょうし、
    そちら側の分岐を中心に考える機構がないと厳しいですかね…。 -- buyobuyon (2007-02-15 21:35:27)
  • とりあえず、ifの片側でのみ退避・復帰を行うことを考えると、
    現在採用している、MinCamlのデータ構造を真似て作ったデータ構造では都合が悪いので、
    それを変更するため、仮想マシンコード生成の部分を現在いじっています。 -- buyobuyon (2007-02-15 23:20:51)


2/13(Tu)


試験が終わってからしばらくばたんきゅーしていましたが、ようやく調子が元に戻ってきました。

現在はレジスタ割り付けを実装中です。
実装中とはいっても、まだ何となくの方針が頭に浮かんだ程度で、
細かい実装をどうすればよいかを混乱しながら考えているところですが…。


さらに続きはbuyobuyon古へ。
「buyobuyon中」をウィキ内検索
最終更新：2007年03月13日 22:12