khaba/memo001 の編集

* khabaのメモ
-(by [[K]], 2007.02.02)

*** (0)
-これは誰が作るの？ ・・・誰が作ってもいいが、多分誰も作ってくれないと思うので、自分で作る予定。細部の説明をするよりも自分で作るほうが早そうだし。
-でも僕よりももっとうまく作る人がいるかもしれないし、作りたい人が他にいたらそれを妨げる理由は何もないので、是非勝手に（＝断りなく）やってください。

*** (1) 動機・方針
-GBA（GameBoyAdvance）で動くOSASKを作りたい。でもそしたらx86用OSASKとバイナリ互換はできない（当たり前）。ソース互換ならできるかもしれない。
-しかし仮にソース互換にするにしても、エンディアンの問題とかで、完全互換はできないかもしれない（ARM7だけならx86との間にエンディアンの問題は起きないかもしれないが、いずれは他のCPUのことだって考えたい）。それに人によってはソースを公開するのはいやかもしれない。
-それなら中間コード（いわゆるVMのバイトコード）みたいなものを考えて、それを実行時に各CPUのネイティブコードに変換すればいいのではないか。これならエンディアンとかの問題はない。CPUのビット数が違って機種によってint幅が異なる、という問題も起こさずに済ませられる。
-これをkhabaとする。
----
-結局khabaがあるとどんなことができるようになるの？（ここだけですます調）
--khabaはjavaや.netのように、どんなCPUにも適合するようなプログラムを作るためのシステムです。javaや.netよりもいいのは、CPUへの要求がもっとずっと少なくなるように工夫して設計されていることです。16bit-CPUや8bit-CPU、PICマイコンみたいな組み込み系のCPUであってもサポートできるように努力しています。実CPUのbit数とプログラムのint幅は完全に独立しており、たとえ16bit-CPU上のkhabaで32bitのintを使うことができますし、演算結果についても32bit-CPU上で実行した場合と差異はありません。逆に64bit-CPU上で16bitのintを扱うこともできます。また実CPUが8bitの場合に、8bitもあれば十分な演算をわざわざ32bitで処理して遅くなるということもありません。khabaはアプリだけではなくOSも記述できることを目指していますし、khabaで書かれたOSASKも用意するつもりです。khabaアプリを実行する際にはCPUを選びませんが、もちろんOSも選びません。
--khabaのプログラムをjavaや.netに変換することができます。javaや.netのコードをkhabaにすることもできると思います。
--khabaを動かすCPUには以下の機能がなくても基本的には問題ありません（これらがないCPUであっても、まるでこれらの機能を有するCPUであるかのように扱えるし、それによって速度が目に見えて落ちるということもおそらくない）。
---ページング・セグメンテーション・保護例外・キャッシュ制御（キャッシュ制御はいりませんが、少量の速い普通のRAMはあったほうがいいです。これすらない場合は、残念ながら速度が目に見えて低下します。メモリマップ上の特定のアドレス範囲のRAMは他よりも高速、ということで十分です）・動的な分岐予測・カーネルモード／ユーザモードの切り替え、PUSH/POPやCALLなどのスタック操作命令群、長さの異なるレジスタ（EAXをALやAHに分解して使えること）、レジスタの汎用化（汎用レジスタがなくていい＝つまりデータレジスタ／アドレスレジスタの区別があっていい）、割り込み（ハードウェア割り込みとソフトウェア割り込みの両方）、マルチタスク支援、アドレス空間のサイズ拡大（バンク切り替え方式のメモリでもリニアマップ方式のメモリでもかまわないという意味）
--もしkhabaを動かせるCPUを作るのならこれらの機能は実装しないで、その分ロジックを小さくし、以下の面での性能向上を図るべきです。
---レジスタ数を増やす、消費電力を下げる、マルチコア度を上げる、内蔵高速メモリの容量（キャッシュの代わりになる）を増やす、DMAをつける、SIMD命令をつける（レジスタ-レジスタ間演算のみでかまわない）
--タスクセーブができます。セーブしたタスクを異なるOS・異なるCPUで再開可能です（だからもしかしたら分散OS向き？）。タスクセーブ後にプログラムを少しいじって、その後に修正されたプログラムに対して（つまり変数値などはそのままで）再開することも可能です。IA-32用OSASKではここまでの再開能力は想定していませんでした。
--メモリの利用状況を細かく監視できるため、メモリダンプを見る際に、ここは○×構造体、みたいなのがすべて分かります。同じことはファイルにも適用され、バイナリファイルでフォーマットが分からないということはまずないですし、フォーマット変換も自動で可能です。「UNIXという考え方」では、バイナリで出力するなんてよくない、ASCIIとかにするべきだという話があったように思いますが、khabaを前提にしてもいいのなら、むしろCPUへの負荷の多い上にバイト数もかさむASCIIにしろだなんて、ナンセンスもはなはだしいです。

*** (2) ターゲット（目的）・最適化
-khabaでは最適化に執着しない。プログラムの2割の部分が実行時間の8割を占めるといわれるが（人によっては1-9ともいうが）、khabaが目指しているのはこのコードのうちの残りの8割の部分の移植の手間をなくすことである。速度が求められる2割の部分については、それぞれのCPU向けのコンパイラ（やアセンブラ）で最適なコードを生成すればよい（つまり手作業で移植する）。もちろんプログラム全体をkhabaだけで書くことはできるが、その場合、実行速度には不満が残るかもしれない。しかしそれは今検討するべき問題ではないと考える。
-khabaは、ネイティブコードと簡単に（＝少ないロスで）交信できる。関数とかも気軽に呼べる。これが担保できないと、上記理想が実現できない。

*** (3)
-khabaはスタックマシンではなく、レジスタマシンである。総レジスタ数は128個か、もしくはそれより多くする（上限を設けないかもしれない）。レジスタのビット数も規定されない。レジスタを使い始める前に、そのレジスタを何ビットレジスタとして使いたいのかを宣言する。宣言は1bitでも2bitでも27bitでもよい。この宣言には、最低ビット数と最大ビット数がある。たとえば最低ビット数8、最大ビット数指定なし、の場合、8bit以上のレジスタ（もしくはメモリ）が割り当てられると仮定してよい。 for (i = 0; i < 100; i++) { hoge...; } のiのために割り当てるレジスタであれば、まさにこのような指定でいいわけである。符号なしで扱うなら7bitで十分だ。
-レジスタマシンにしたのは、khabaをネイティブコードに変換するプログラムに楽をさせ、しかもネイティブコードとの交信をやりやすくするため。たとえばIA-32の場合、レジスタ番号0は、EAXに割り当てられる。レジスタ番号1はECX（本当にEAXやECXにするかどうかは未定。翻訳をやりやすくするため、EAXとかをリザーブにする可能性もあるから・・・MUL/DIV命令やIN/OUT命令を考えると、EAXでしかできないことが結構あり、もしEAXがレジスタ0として利用可能だとすると、DIVをPUSH(EAX);、POP(EAX);ではさまないといけない。リザーブしておけば、EAXは常に破壊可能と想定していいことになるから、このようなPUSH/POPはいらなくなる）。
-レジスタ番号8番以降はIA-32には割り当てるべきレジスタが存在しない。これはメモリに割り当てられる。リザーブレジスタがあれば、8番よりももっと若い番号でもメモリに割り当てられることになりそうだ。何番からメモリ行きになるかは、動的に決まるわけではない。khaba/IA-32仕様に記載され、確定する。レジスタ番号nがどのレジスタになるのかについても、仕様で決める。
-bit数が仕様で規定されずにプログラムで指定するようにした理由は次のとおり。javaや.NETのように32bit固定ということにすると、286やZ80でこれらを実行する際に、本来は8bitもあれば十分なものをあえて32bit処理することになりかねないからである（キャリーフラグなどを使って多倍長処理することになる）。こんなのは無駄なので、多倍長処理は必要なときだけで済ませられるように、このような仕様にした。最大bit数については、おそらくたいていは指定しないことになるだろうが、ラップアラウンド（っていうんだっけ、127+1=-128みたいなやつ）や繰り上がりによるキャリーフラグの挙動を利用する際には指定することになる。
-IA-32で33bit以上のレジスタを使用する場合、上位部分はメモリに割り当てられる。
-リンクするネイティブコードを書く場合、データのやり取りをするとか、どのレジスタを破壊してはいけないかを意識するとき以外で、この仕様を気にする必要はない。

-EAXはリザーブにすることにした。ARMでもR0とR1はリザーブにする。EDXとR2もリザーブにするかもしれない。ECXがレジスタ番号0になるのはほぼ確定。

*** (4)
-khabaではレジスタは原則として汎用ではない。(3)で言っているレジスタはデータレジスタであり、メモリアドレスやI/Oアドレス指定のために使用することはできない。アドレスレジスタのbit数はプログラマによって意識されない。たとえばこれは32bitのnearポインタかもしれないし、48bitのfarポインタかもしれないし、V86の16bit:16bitのfarポインタかもしれない。khabaは実際のネイティブコードを生成するときに、対象となるCPUやOSに応じて、アドレスレジスタのbit数を決定する。したがってネイティブプログラムがkhabaのプログラムとアドレスのやり取りする場合は、CPUが同じでもOSによって別々に準備する必要が出てくることは十分にありうる。
-IA-32の場合、ESPとEBPとESIとEDIがリザーブされており、実レジスタに対応するアドレスレジスタはEBXだけである。他はすべてメモリに置かれる。
     (int) [A0] = 1; /* A0（アドレスレジスタ0）で示されたメモリを1にする。 */
     (int) [A1] = 2;
     (int) [A2] = D0;
-もしintがリトルエンディアンの16bitであるとしたら（intのエンディアンやビット数はプログラムのどこかで定義してある）、
     MOV WORD [EBX],1
     MOV ESI,[EBP+?(A1のある場所)] ←これはもっと複雑になるかもしれない
     MOV WORD [ESI],2
     MOV ESI,[EBP+?(A2のある場所)] ←これはもっと複雑になるかもしれない
     MOV WORD [ESI],ECX
-D0 = A1; のような、アドレスレジスタの値をデータレジスタへ取得しようとする行為はすべて禁止する。また A9 = D4; のような、アドレスレジスタへ普通のデータを入れることも禁止する。 A9 += D4; や D0 = A1 - A0; のようなことは許される。

*** (5) アドレッシング(1)・キャッシュ制御
-アドレッシングの一般型は、[An+(Dn*定数)+(定数)]である。括弧内は省略可能。この式にも現れているが、アドレスレジスタを用いないアドレッシングは許さない。これは次のような設計思想を反映している。
-GBAには256KBのRAMと32KBのRAMがあるが、256KBのほうは回路的にCPUからは遠く、アクセスには2クロックのウェイトが入る。32KBのほうはノーウェイト。これはこう考えたらいいだろう、つまり32KBは可視化されたキャッシュメモリである、しかしメモリのどの部分をキャッシュに入れるかとかはハードウェアによる自動制御がなされない。したがってOSなどが面倒を見るべきだと考える（OSがある場合の話）。
-メモリのある部分がこの速い32KBの範囲内にコピーされることはあるし、また256KBのほうへスワップアウト（というかキャッシュアウト？）されることもありうる。これらは動的に行われるべきだ。これらの場合OSは、そのメモリ域を指しているレジスタ（やメモリ）をアプリに気づかれることなくすべて更新する。
--メモリを更新する必要があるかどうかは、ポインタをどのようにメモリに格納させるかにもよる。たとえばブロックID+オフセットであれば、更新はしなくてよい。
-こういうことをやるためには、アドレッシング形式にアドレスレジスタを必ず含ませる必要がある。
-またアドレスレジスタをアドレッシングに含んでいるからといって、それだけでメモリのどこでもアクセスできるというわけではない。(Dn*定数)+(定数)の部分の値の範囲には当然制限が課される。その制限からアクセス範囲を特定し、これをブロックとして速いRAMに転送するなどをOSが行う。

*** (6) タスクセーブ・エンディアン・完全な型管理
-khabaはOSASKを強く意識しており（GBAで動くOSASKを作ることが最初の動機だったので当然）、khabaでもタスクセーブできなければいけない。しかもセーブしたものを他のCPUで再開できたら、しかもエミュレーションなしでできたら、とてもいいだろう。
-68000とかで実行したタスクをセーブしx86でロードすると、メモリイメージ上のエンディアンが合わないので、16bitメモリアクセス前後に XCHG(AL, AH); みたいなコードを挿入しなければいけないことになる。これはコードが肥大化するし、遅い。それならば、メモリ上のintやshortをすべて反転させてしまえばいいではないか。
-これをやるにはメモリのイメージに対して、どこがintでどこがcharでどこがポインタか、みたいなことを完全に把握しなければならない。だから把握する。この情報があるので、メモリダンプの可読性は非常に高い。構造体も認識するので、デバッグはかなり楽になる。
-IA-16でセーブしたものをIA-32でロードする場合、メモリに余裕があるならintの幅を16bit→32bitにしてしまうほうが、動作が速い。しかしこれをやるとメモリのポインタがずれる恐れがある。でもやる。khabaではメモリ上にストアされたポインタは実際のアドレスではなく、ファイルのパスのような抽象的なもので格納する。実際にはパスそのものを保存するわけではないが、 &stack.func_abc.table.i[12] のような形式へたどれるような情報をもつ。
 struct STACK {
     struct MAIN {
         int i, j, k; /* 関数main()のスタック変数 */
     };
     struct FUNC_AAA { /* main()がfunc_aaa()を呼んだのでスタックに積まれた */
         struct CODEPOINTER ret; /* ここは &code.main.label126 とかが入っているのだろう */
         int i, j;
         float x, y;
     };
     struct FUNC_ABC { /* func_aaa()がfunc_abcを呼んだらしい */
         struct CODEPOINTER ret;
         struct TABLE {
             int i[100];
         };
     };
 };
-当然ながらこのSTACK構造体は動的に変わることになる。関数呼び出しのオーバヘッドはやや大きい。
-この例ではstackの伸びる方向とは逆に書いたが、実際はスタックの伸びる方向にあわせて書くべきだ。・・・が、khabaのスタックがESPのように伸びていくとは決まっていない。
-もしメモリ使用状況マネージャに書き足すのがつらいのなら、スタックはスタック上にとるのではなく、mallocみたいにしたらいいかもしれない。この場合、旧スタックポインタをスタック内に記憶しておくことになるだろう。
 struct FUNC_ABC {
     struct CODEPOINTER ret;
     struct DATAPOINTER oldstack;
     struct TABLE {
             int i[100];
         };
     };
 };
-つまり呼び出し元を探るにはoldstackをたどっていけばいい。チェイン構造である。この場合、この構造体はもはやスタック上にはないので、先の例はこうなるだろうか。 &heap.func_abc.table.i[12] 。
-再帰などで同じ関数が何度も呼ばれたら、 &heap.func_abc~37.table.i[12] とかになるのだろう。
-このmalloc型スタックは、GBAみたいなマシンでは有利かもしれない。GBAは速いRAMが少ないので、大きなスタックをキャッシュに保持するのは大変である。でもmalloc方式にすれば、小さなオブジェクトがたくさんできるだけなので、今使っているものくらいなら問題なくキャッシュに収まる可能性が大きい。
-このような形式でタスクセーブされるため、タスクセーブ後にプログラムを少々書き換えたとしても、再開できないことはない（khabaバイナリを最適化して、ローカル変数名情報などを適当なIDなどに交換してしまったあとだと、改造しても動くというのはやりにくいかもしれないが）。
-khabaでは「unionを使って、floatで書いたものをintで読む」なんてことは絶対に禁止である。しかしunionが使えないわけではない。書いた型と違う型で読んだ場合に例外が起きるというだけのことである。同じ理由で強引にポインタをキャストして値を読むこともできない。
*** (7)ファイルシステムやプログラミングモデルへの影響
-OSASKではメモリレスアーキテクチャをとっており、これはGBAでも引き継がせる予定だが、ということはつまり、メモリイメージというのは、ただのバイナリファイルである。バイナリファイルにこのような型情報がつくわけだ。これは非常に便利である。バイナリファイルに型情報があるのだから、それなりのエディタを作れば、データの任意の部分を人間にわかりやすい形式で表示したり編集したりできるわけだ。
 {
     view = {
          color = white; /* enumであればこのように表示できるはず（ただしこのコメントは実在しない） */
          fontsize = 15;
     };
     history[5] = {
         "abc.txt", "def.txt", "ghi.h", "", ""
     };
     copybuf = "hogehoge";
 };
-これはテキストエディタの設定ファイル（兼履歴保存ファイル）の例である。もちろんこれくらいの読みやすい設定ファイルを持つテキストエディタは既にごまんとありkhabaのアドバンテージとはいえないが、しかしこのようなファイルが、実際はただの100バイト前後のバイナリであって、解読ルーチンなしできわめて高速に読めるのである（バイナリなので当然）。これはかなりいけていると思う。しかもただのテキストファイルではないので、viewとかの部分（つまりメンバ名の部分）は編集できないだろうし（無理に編集することもできるだろうけど、その場合違う構造体になってしまうのでもはやこのアプリには読み込めない）、whiteのところはwhiteのほかにblueやredなどを選択すればいいだけにもできる。汎用・バイナリ・バリュー・エディタ？
-これが現在実行中のアプリのスタックやヒープに対してもできるのだから、デバッガなんてもういらないかも。
-出力についても同じようなことがいえるかもしれない。たとえば、2つの整数aとbを入力して、それらの和であるcを出力するプログラムを考えるとする。普通に書けば、標準入力からscanfして、和を算出し、printfするだろう。もしくは入力をコマンドラインにするかもしれない。なんにせよ、ASCII文字列をバイナリに変換し、計算し、結果をASCIIにしなければいけない。
-khabaならどうだろうか。まずここで述べたように、入力部分をバイナリ化できる。以下C言語で書くが、これは説明のためであって、khaba版Cがこのような文法になることを保証するものではない。
 struct IFILE { /* INTが仮に32bitだとすれば、8バイトの構造体（ファイル） */
     INT a, b;
 };
 
 void main(INT argc, STRING *argv)
 {
     if (argc >= 2) {
         struct IFILE *p = mapping_struct(arg[1], "r", struct IFILE);
         if (p != NULL) { 
            printf("%d\n", p->a + p->b);
            unmapping(p);
         }
     }
     return;
 }
-とりあえずこれで、scanfはなくなった。しかしprintfは残る。printfは重い関数だし、バイナリで入力したのに結果がASCIIだなんて、なんかみっともない。ということでこうしてみる。
 struct IOFILE {
     INT a, b, c;
 };
 
 void main(INT argc, STRING *argv)
 {
     if (argc >= 2) {
         struct IOFILE *p = mapping_struct(arg[1], "rw", struct IOFILE);
         if (p != NULL) {
             p->c = p->a + p->b;
             unmapping(p);
         }
     }
     return;
 }
-これはすごい。結果もバイナリだ。しかも重い関数がない。結果がバイナリなので、汎用バイナリバリューエディタがあれば、10進数に限られることなく好きな進法で表示もできる。
-バイナリだと32bitを超える計算ができないという問題があると思うかもしれないが、上記プログラムのkhabaコードを実コードへ変換する際に、INTをint64とみなして処理せよというオプションをつければ、それだけで解決する。その場合読み書き用のバイナリも型変換してから使う（こんなのはもちろんツールで簡単にできる）。つまり、値が同じなら、int幅が変わった程度でバイナリを手で作り直す必要はまったくない。

*** (8) コードラベル・割り込み
-タスクをセーブするにあたり、EIP（CPUによってはPCともいうけど）を保存する必要があるが、上記例のように &code.main.label126 のような形に変換しなければいけない。となると対応するラベルを大量に自動生成するか、もしくはタスクセーブ可能なポイントを絞る必要がある。
-タスクセーブ可能なポイントが大量にあってもそれほどのメリットはないだろうと考えられる（むしろラベル情報が多すぎてkhabaコードのファイルサイズが爆発しかねない）。数十～数百命令に1つの割合でタスクセーブ可能なチェックポイントみたいなものがあれば、実用上の問題はないだろう。それくらいなら、ループ命令の分岐先のラベルやサブルーチンコールの戻り番地用のラベルだけでも十分だろうし、もしかしたらさらに間引いても良い。
-これはつまり任意の個所でタスクセーブができるわけではないことを意味するが、これはむしろタスクセーブにとって都合の悪い中途半端な状況でのセーブを自動的に回避できるというメリットもある。
-ネイティブに変換されたコードは、ラベルのあるチェックポイントに差し掛かるたびに、ワークエリア内のフラグをポーリングして、タスクセーブの準備ができましたというAPIを呼び出すかどうかを判定する。
-これをもう少し推し進めて考えると、そもそもCPUの割り込み機能だってなくてもいいのかもしれない。デメリットとしては、割り込みに対してワーストケースで数百から数千クロック遅れるということがあるが、それくらいはあまり問題にならない気もする（むしろそこまでタイミングにシビアすぎるハードウェアのほうがいけない？・・・せめて小規模なバッファくらいは持っていてほしい）。割り込み制御回路を節約できれば、CPU回路はもっと節約できるだろうし、CLIやSTIなど割り込み禁止・許可の命令を命令セットに準備しておく必要もなくなる。そのぶんレジスタ数を増やしたり、マルチコア度を上げるほうが総合的な性能向上（処理速度、消費電力あたりの処理能力など）が上昇しそうな気がする。
-もちろん割り込みがあるかどうかを判定するためのチェック命令や条件分岐命令の実行時間分のロスはある。しかしこれは数十～数百命令に1つの割合で挿入されるだけであり、これでネイティブコードの量が増えたり、実行速度が落ちたりはするだろうが、それは1%以下だろうと思われる。
-なお、これを理想的にやるのなら、CPUの割り込み要求ピンの内容がそのままフラグレジスタのあるビットに直結されて（これは各デバイスのIRQ信号のORの結果）、そのビットが1なら分岐するという ji 命令（jump if interrupt）みたいなのがあるといいだろう。これならチェックポイントでのチェックによるロスは最小化できる。

*** (9) フラグ
-

*** memo
//-GBAには（自動の）キャッシュ（制御回路）がない・そもそもRAMも少ない→アクセスウィンドウ→メモリアクセスに制限をつける
//-エンディアンの問題・ポインタ変数の自動補正→構造体（データタイプ）の把握→非線形配列アクセス→自動型変換？ファイルシステム？
//-コードラベル、CPU機能の削除（割り込み機能は不要？）
-これらの長所を完全に生かすためには、リンクするネイティブコードにも多少のしきたりを押し付けるべき。
-レジスタスタック（sparcに似ている？：むしろAMD 29000に近い）、レジスタ間連続代入
-khabaが効率よく動かせるCPUとは？それは理想のCPUか？
-定数レジスタ。代入以外のmodifyはできない。個別代入は遅くてもいい。分岐予測ビットのあるオペコード（かオペランド）。
-コンパイラは、ポインタが不要な変数（だから配列はダメ）以外の変数を全部レジスタ変数にする。
-JITに限定しない。クロスでもいい。PICマイコンなどでやろうとするとJITはインタプリタ式にしかできないから、非JITを認めるのは現実的。
-バウンダリチェックをネイティブでやる必要はない。バウンダリチェックは実行頻度が少ないし、機種・環境依存ではないから。
-2000年問題もこれなら少ない労力で解消できたはず。プログラム側は修正するべきだけど、データはYEAR型とかであれば自動で拡張できたはずだから。文字のエンコード問題も解消できるかもしれない。
-データレジスタ128本、定数レジスタ64本、アドレスレジスタ64本くらいが理想かも。グローバルなレジスタ群もほしいな。16+8+8くらいかな。

//x86はきたない、MIPS、使える技術こそ！、文明再出発学
*** こめんと欄
-このページは誰かに意見を求めるためではなく、自分の記憶の整理のためにあるので、こめんと欄はありません。

タイムスタンプを変更しない

* khabaのメモ
-(by [[K]], 2007.02.02)

-EAXはリザーブにすることにした。ARMでもR0とR1はリザーブにする。EDXとR2もリザーブにするかもしれない。ECXがレジスタ番号0になるのはほぼ確定。

*** (9) フラグ
-

テキスト整形のルールを表示する