4命令プロセサで"どう書く"
あらすじ : http://d.hatena.ne.jp/mjt/20110125/p2
というわけで、JCC / ADD(C) / NOR / STOREの4命令しかないプロセサで各種操作をどう書けるのかを考えるコーナー。
以下の例を見れば、この4命令が如何にギリギリかわかるはず。。
(命令の紹介)
元ネタ( http://read.pudn.com/downloads42/sourcecode/embed/145720/mcpu-doc.pdf )では以下の4命令を紹介している。
- JCC = (Jump if Carry Clear) キャリーフラグがセットされていなかったら、ジャンプする。どちらの場合もキャリーフラグをクリアする。
- ADD = レジスタに、指定された番地のメモリ内容を加算し、キャリーフラグをアップデートする。
- NOR = レジスタと指定された番地のメモリ内容のNORを取って、キャリーフラグをクリアする。
- STORE = レジスタの内容を指定された番地のメモリに格納する。
レジスタは1つしかないので指定する方法は無い。
NOP
NOPは"事実上"何もしない命令ならなんでも良い。
NOPは普通のプロセサでも普通の命令の意味の無いパターンを使っていることがある。i386のNOPはXCHG EAX, EAXなので、本当に何もしないわけではなく、EAXレジスタとEAXレジスタの内容を交換する。ちなみに、amd64ではこのNOPは本当のNOPになった( http://www.pagetable.com/?p=6 )。
しかし、今回の4命令プロセサには本当のNOPは書けない。
- JCC (次の命令)
JCCを使って次の命令にジャンプすれば上手くいきそうに思えるが、JCCはキャリーフラグをクリアしてしまう。
というわけで、ゴミ置き場をメモリ上に確保して、そこに意味のないSTOREをするのが好ましい。。
NOPなんかこういうギリギリプロセサでは要らないだろうと思われるかもしれないが、NOPはコードのパッチに有用なので、有るに越したことは無い。
JMP(絶対ジャンプ)
NOPが書けないよりも困りそうなのが絶対ジャンプ。幸いなことに、絶対ジャンプは簡単に書ける。
JCC next # clear carry next: JCC DEST
JCCを2回やることで絶対ジャンプになる。もしジャンプ命令を逆の意味、つまり"キャリーがセットされていたらジャンプ"にしていたらもっと多くの命令が必要になるだろう。。今回のプロセサは、キャリーを確実にセットする簡単な方法は無い。
LOAD(値のロード)
値をロードするには演算を使うしかない。よって適当な場所に定数を確保しておくしか方法が無い。これはギリギリプロセサでは常套手段であり、RISCプロセサやDSPでも"必ずゼロになるレジスタ"や”必ずオール1になるレジスタ"がよく出てくる。
値のロード方法は用意した定数によって異なるが、簡単には、ALLONE(いわゆる-1)を用意して:
NOR ALLONE # レジスタをゼロにする ADD value # value番地の内容をレジスタにロード
NOR ALLONEがゼロになる理由は真理値表を書けばわかる。
NOT / OR / AND / XOR
これらは情報科の授業のテストで頻出。
- NOT
NOTはゼロとNORを取れば良い。つまり、
NOR ZERO
- OR
NORはORのNOTなので、さらにNOTを取れば良い。
NOR value NOR ZERO # NOT
ANDやXORはちょっと難しい。これらは値を一旦ストアする以外の方法では構成できない(はず)。
相対ジャンプ / 相対ロード / 相対ストア / CALL & RET
いわゆるポインタの操作はプログラムの自己書き換えによって行うことになる。よっていわゆる"ハーバードアーキテクチャ"を採用すると大変なことになってしまう。
他のギリギリプロセサ、例えばParallaxのPropeller*1も同様のアーキテクチャを採用している(http://www.parallax.com/Portals/0/Downloads/docs/prod/prop/PropellerDatasheet-v1.2.pdf の6.4を見ればわかるように、RETとJMPが全く同じエンコードになっている。PropellerのアセンブラはRET(JMP)命令の書き換えコードを自動的に生成してくれる。)
シフト / ローテート
左シフトは簡単に書ける。一旦適当なところにストアしてADD。
STORE tmp ADD tmp
左ローテートはキャリーと定数ONE(1)を使って、
STORE tmp ADD tmp JCC skip ADD ONE skip:
のように書ける。
逆に、右シフトは非常に難しい。。常套手段は表引きによる方法。しかし表引きは上記のように自己書き換え以外の手段では行えないので、ローテートで実装する方が簡単だろう。つまり(レジスタ巾 - シフト数)だけローテートし、不要な値をマスクする。
1
上記のように、数値 1 を使いたいケースはそれなりに多岐に渡る。もちろん、ROM中に1を入れておけば良いだけの話だが、ALLONEが有るとしたら、
NOR ALLONE # レジスタにゼロを格納 STORE zero # ゼロをメモリの適当なところに格納 ADD ALLONE # レジスタにALLONEを格納 ADD ALLONE # レジスタの内容が(not 1)になる NOR zero # レジスタのNOTを取って1を得る
のようにして生成できる。ALLONEのかわりにZEROからでも作ることはできる。逆に、このどちらかは絶対に必要ということになる。