p20250815a の編集

* スタックマシンに関する幻想について
-(by [[K]], 2025.08.15)

** (0) はじめに
-なんかよくわからないけど、スタックマシンはレジスタマシンよりも〇〇に優れているみたいな話を時々聞きます。
-しかしいろいろ実験してきた私としては「ん？それは本当か？？」と思うのです。
-私が思うに、どこかの偉い人がもっともらしく説明したせいで、その後だれも疑わず検証もせず、妄信している内容がいくつかある気がしてなりません。
-だからそれらに疑問を提示して、私なりの実験をして、その結果を示したいと思います。

-[目次]
--(1) スタックマシンでバイトコードを設計すれば、プログラムのバイト数が減る → そんなことはなさそう
--(2) スタックマシンを想定してアセンブラを出力するなら、コンパイラが書きやすくなる → そんなことはなさそう
--(3) 逆ポーランド記法で書かれた式をレジスタマシン向けのアセンブラ記法に直すのは結構な手間がかかる → そんなことはなさそう

--(4) 余興：ポーランド記法をレジスタマシン向けのアセンブラ記法やスタックマシンの向けのアセンブラ記法に直す
--(5) 余興：uckはどうやってバイトコードを短くしたか？
--(6) もっと細かい余談を、Q&A形式で

----
-[Q:0-1] すみません、そもそもスタックマシンってなんですか？
--[A:0-1] 普通の機械語では、どのレジスタとどのレジスタを演算して結果をどこに入れるか、というのを命令の中で指定します。たとえば「 ADD a,3; 」とすれば、aに3が加算されます。
--しかしスタックマシンでは演算命令に演算対象を書きません。「 ADD; 」だけでいいのです。じゃあどれとどれを足すんだ？ってなるわけですが、それは値を「レジスタ型スタック」にどんどんと積んでいき（PUSH命令）、ADD命令が一番上と上から二番目の値に対してADDするのです（このときにこの2つの値はスタックから消されます）。そして計算結果はどこにいくのかというと、それはスタックに積まれるのです。
--スタックマシンのこの挙動は、逆ポーランド記法と相性が良く、逆ポーランド記法がほぼそのまま機械語になるくらいに分かりやすいです。スタックマシンは一時変数をどうするかということを悩まなくていいので、これを好む人はいます。x86でもFPUの基本設計としてスタックマシンが採用されていました。
--しかしスタックマシンはアウトオブオーダ実行などに難があり、今ではほとんど採用されません。x86もSSE拡張を導入して、スタックマシンによらないFPU演算をサポートしました。
--逆ポーランド記法との相性の良さから、スタックマシンはレジスタマシン（＝演算命令に演算対象を明記する、普通の機械語のことです）よりも〇〇で優れているということが先入観で言われているようなのですが、それが本当のことなのかそれを確かめるのがこのページの目的です。

** (1) スタックマシンでバイトコードを設計すれば、プログラムのバイト数が減る
-私はJavaのバイトコードの説明の時に、初めてこの話を聞きました。
-Rubyの実行エンジンである RubyVMでもスタックマシンを採用していて、その理由はこれだと聞いた記憶があります。
-ではJavaのバイトコードは結果としてコンパクトになっているのかと言えば、全然そんなことはないです。でもそれはこのスタックマシン性に由来しているというよりは、他の理由の方が主のような気はしますが。

-まずは「 i = i + 3; 」で考えたいと思います。レジスタマシンで、かつiがレジスタ変数なのであれば、「 ADD i,3; 」だけで済みます。これに対して、スタックマシンであれば、「 PUSH i; PUSH 3; ADD; POP i; 」が必要になります。
-レジスタマシンの場合、「ADD」「i」「3」で3語でした。スタックマシンの場合、7語になっています。仮に「1語は少なくとも1バイトを要する」と考えるなら、この例ではスタックマシンはかなり不利です。
-スタックマシンが不利になりやすい最大の要因はレジスタ変数を全く持てないところだと思います。とにかくpushしなければ演算対象にできないわけです。

-次に「 y = a * x + b; 」で考えてみます。
-レジスタマシン：「 MUL3 tmp,a,x; ADD3 y,tmp,b; 」→ 8語
-スタックマシン：「 PUSH a; PUSH x; MUL; PUSH b; ADD; POP y; 」 → 10語
-このように式が長くなってくると、レジスタマシンでは一時変数を明示して書かなければいけない分だけ少しずつ不利になってきます。スタックマシンは一時変数を書く必要がありません。一時変数の名前をどうするか（or一時変数としてどのレジスタを使うか）なんて、全く本質的ではないどうでもいいことです。それを明示的に書かされる分だけレジスタマシンは不利です。

-次は「 y = a * x * x + b * x + c; 」でやってみます。
-レジスタマシン：「 MUL3 tmp,a,x; MUL tmp,x; MUL3 tmp2,b,x; ADD tmp,tmp2; ADD3 y,tmp,c; 」→ 18語
-スタックマシン：「 PUSH a; PUSH x; MUL; PUSH x; MUL; PUSH b; PUSH x; MUL; ADD; PUSH c; ADD; POP y; 」 → 19語
-だいぶ差が縮まってきました。

-まあここまでの考察で、「長い式がたくさん想定されるならスタックマシンは有利だけど、実際のプログラムでは短い式もたくさんあるので、スタックマシンの方が有利だとはあまり期待できない」という感じは分かっていただけたと思います。

** (2) スタックマシンを想定してアセンブラを出力するなら、コンパイラが書きやすくなる
-論より証拠だと思うので書き比べてみます。
--''ルール''： 変数は1文字。定数も1桁。演算子は()*/%+-のみ。スペースを入れてはいけない。単項演算子も未対応。さらに式としておかしいものは入力しない想定。
---レジスタマシンかスタックマシンかの違いを見るだけならこの仕様でまったく問題ない。

----
-(2-1) ''レジスタマシン用のコンパイラ''[32行]
 #include <stdio.h>
 #include <string.h>
 
 const char *s;
 char a[4096], t;
 
 char compile(int pri)
 {
     char r, q, op;
     if (*s == '(') {
         s++; r = compile(99); s++; // ')'を読み飛ばす.
     } else {
         r = *s++; // 数値もしくは変数.
     }
     for (;;) {
         op = *s++;
         if (pri >= 4 && (op == '*' || op == '/' || op == '%')) {
             q = compile(3); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, t, r, q); r = t++;
         } else if (pri >= 5 && (op == '+' || op == '-')) {
             q = compile(4); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, t, r, q); r = t++;
         } else
             break;
     }
     s--; return r;
 }
 
 int main(int argc, const char **argv)
 {
     s = argv[1]; if (s == NULL) return 1;
     t = 't'; char r = compile(99); printf("%sresult=%c\n", a, r);
     return 0;
 }
-このプログラムをコンパイルして、reg.exeを作りました。
 >reg 1+2*3
 * t,2,3    → MUL(t, 2, 3); // t=2*3;
 + u,1,t    → ADD(u, 1, t); // u=1+t;
 result=u   → 計算結果はuに入っています、という意味です。 tとかuは一時変数です。
 
 >reg (1+2)*3
 + t,1,2
 * u,t,3
 result=u
 
 >reg (X+Y-1)*(A+B)
 + t,X,Y
 - u,t,1
 + v,A,B
 * w,u,v
 result=w

-[追記] このプログラムがあまりわかりやすくないという指摘を受けました。実は私もちょっと心配していました。
-処理内容としては何も変わっていませんが、以下を(2-1')とします。
 #include <stdio.h>
 #include <string.h>
 
 const char *s;
 char a[4096], t;
 void resetTmp() { t = 't'; }
 char newTmp() { return t++; }
 
 char compile(int pri)
 {
     char r, q, n, op;
     if (*s == '(') {
         s++; r = compile(99); s++; // ')'を読み飛ばす.
     } else {
         r = *s++; // 数値もしくは変数.
     }
     for (;;) {
         op = *s++;
         if (pri >= 4 && (op == '*' || op == '/' || op == '%')) {
             q = compile(3); n = newTmp(); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, n, r, q); r = n;
         } else if (pri >= 5 && (op == '+' || op == '-')) {
             q = compile(4); n = newTmp(); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, n, r, q); r = n;
         } else
             break;
     }
     s--; return r;
 }
 
 int main(int argc, const char **argv)
 {
     s = argv[1]; if (s == NULL) return 1;
     resetTmp(); char r = compile(99); printf("%sresult=%c\n", a, r);
     return 0;
 }
-こうすれはたぶん読みやすくなります。

----
-(2-2) ''スタックマシン用のコンパイラ''[32行]
 #include <stdio.h>
 #include <string.h>
 
 const char *s;
 char a[4096];
 
 void compile(int pri)
 {
     char op;
     if (*s == '(') {
         s++; compile(99); s++; // ')'を読み飛ばす.
     } else {
         sprintf(a + strlen(a), "push %c\n", *s++); // 数値もしくは変数.
     }
     for (;;) {
         op = *s++;
         if (pri >= 4 && (op == '*' || op == '/' || op == '%')) {
             compile(3); sprintf(a + strlen(a), "%c\n", op);
         } else if (pri >= 5 && (op == '+' || op == '-')) {
             compile(4); sprintf(a + strlen(a), "%c\n", op);
	 } else
             break;
     }
     s--;
 }
 
 int main(int argc, const char **argv)
 {
     s = argv[1]; if (s == NULL) return 1;
     compile(99); printf("%s", a);
     return 0;
 }
-このプログラムをコンパイルして、stk.exeを作りました。
 >stk 1+2*3
 push 1
 push 2
 push 3
 *
 +
  
 >stk (1+2)*3
 push 1
 push 2
 +
 push 3
 *
 
 >stk (X+Y-1)*(A+B)
 push X
 push Y
 +
 push 1
 -
 push A
 push B
 +
 *
----
-見ての通り、どちらも問題なくコンパイルできています。コンパイラの行数は同じでした。
-確かに、レジスタマシンの方が少しコンパイラの記述量が多そうな感じです。でも、この程度の差ですよ？
-このわずかな差が問題なんでしょうか？
-ということで、なんか別の理由でスタックマシンを採用するならそれは全く問題ないと思うのですが、「コンパイラが作りやすくなるから」は理由としては弱い気がします。

-スタックマシンの場合、実行の際にはPUSH命令があるので、その分だけ実行速度は落ちるかもしれません（実行しなければいけない命令数が増える）。
-（まあそれはレジスタマシンがメモリ上にある変数をレジスタにロードするコストと同じなので、レジスタ変数を使わないなら実質的には同じことではあります。）

- MUL(t, 2, 3); や ADD(u, 1, t); をどうやってx86のアセンブラに直せばいいの？という問い合わせがありました。それは[Q:6-3]で説明します。

** (3) 逆ポーランド記法で書かれた式をレジスタマシン向けのアセンブラ記法に直すのは結構な手間がかかる
-まず、逆ポーランド記法で書かれた式をスタックマシン向けのアセンブラに直すのは、言うまでもなく非常に簡単です。定数もしくは変数の前にPUSHをつけて、演算命令はそのままにすればいいからです。
-ではレジスタマシン向けに変換するのはどのくらいの手間でしょうか？

-(3-1) ''レジスタマシン用の逆ポーランド記法コンパイラ''[17行]
 #include <stdio.h>
 #include <string.h>
 
 int main(int argc, const char **argv)
 {
     const char *s = argv[1]; if (s == NULL) return 1;
     char t = 't', a[4096], *p = &a[4096], c; a[0] = 0;
     while ((c = *s++) != '\0') {
         if (strchr("*/%+-", c) != 0) {
             sprintf(a + strlen(a), "%c %c,%c,%c\n", c, t, p[1], p[0]); *++p = t++;
         } else {
             *--p = c;
         }
     }
     printf("%sresult=%c\n", a, *p);
     return 0;
 }
 
 >cnv 123*+
 * t,2,3
 + u,1,t
 result=u
 
 >cnv 12+3*
 + t,1,2
 * u,t,3
 result=u
 
 >cnv XY+1-AB+*
 + t,X,Y
 - u,t,1
 + v,A,B
 * w,u,v
 result=w
-こんな感じでうまくいきました。だからたいして大変ではないのです。
-「私の自作言語では数式を逆ポーランド記法で書くので、コンパイル先がスタックマシンの方がよい」ということは言えるかもしれないですが、それでも多分その差は10行程度でしょう。
-私はそれが配慮すべきほどの問題とは思えません。

** (4) 余興：ポーランド記法をレジスタマシン向けのアセンブラ記法やスタックマシンの向けのアセンブラ記法に直す
-(4-1)''ポーランド記法→レジスタマシン''（p2r）[21行]
 #include <stdio.h>
 #include <string.h>
 
 const char *s;
 char a[4096], t;
 
 char val()
 {
     char op = *s++, x, y;
     if (strchr("*/%+-", op) != 0) {
         x = val(); y = val(); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, t, x, y); return t++;
     }
     return op; // 数値もしくは変数.
 }
 
 int main(int argc, const char **argv)
 {
     s = argv[1]; if (s == NULL) return 1;
     t = 't'; char r = val(); printf("%sresult=%c\n", a, r);
     return 0;
 }
 
 >p2r *-+XY1+AB
 + t,X,Y
 - u,t,1
 + v,A,B
 * w,u,v
 result=w
----
-(4-2)''ポーランド記法→スタックマシン''（p2s）[21行]
 #include <stdio.h>
 #include <string.h>
 
 const char *s;
 char a[4096];
 
 void val()
 {
     char op = *s++;
     if (strchr("*/%+-", op) != 0) {
         val(); val(); sprintf(a + strlen(a), "%c\n", op);
     } else {
         sprintf(a + strlen(a), "push %c\n", op);  // 数値もしくは変数.
     }
 }
 
 int main(int argc, const char **argv)
 {
     s = argv[1]; if (s == NULL) return 1;
     val(); printf("%s", a); return 0;
 }
 
 >p2s *-+XY1+AB
 push X
 push Y
 +
 push 1
 -
 push A
 push B
 +
 *

** (5) 余興：uckはどうやってバイトコードを短くしたか？
-uckの前身であるOSECPU-VMの高密度バイトコードでは、(1)のような考察の上でレジスタマシンを採用していました。
-uckではスタックマシンの利点も捨てがたいと思い始めたので、どうにかできないかと試行錯誤しました。

-uckを説明するにはhh4がーみたいな話をしなければいけなくなるのですが、それを全部カットして要点だけ言えば、「バイトコードが短くなったのは、PUSH命令を1ビットにしたから」と言えると思います。
--uckでは4bit命令として0x0～0x6が使えます。このうちの0x0～0x3はPUSH命令です。0x4～0x6は演算命令でADD/SUB/MULです。
--uckでは8bit命令として0x80～0xbfが使えます。このうちの0x80～0xafはPUSH命令です。0xb0～0xbbは演算命令で、0xbc～0xbfもPUSH命令です。
--uckでは12bit命令として0xc00～0xdffが使えます。このうちの0xc00～0xd3fはPUSH命令です。0xdc0～0xdffもPUSH命令です。
--（以下略）
-これらのPUSH命令には引数はなく、どんな値をPUSHするかは命令コードで決まるのです。たとえば0x88なら数値8をPUSHします。
-このように命令番号の「半分以上」を引数なしPUSH命令に割り振っているので、実質的にPUSH命令のコストは1bit未満になっています。
--もっというと、負の数のPUSHって滅多に使わないので、そのたまにしか使わない部分だけを演算命令に置き換えた感じです。
--そのせいでたとえば8bit形式では-9をPUSHできないわけですが、12bit形式なら-9はPUSHできるので実質的には問題ないのです。
--このようにより長い命令長を選んでいけばどんな数値もPUSHできるようになっているので、PUSH命令→演算命令への置き換えは問題なくできています。
-PUSH命令のコストが無視できるようになれば、スタックマシンでもデメリットはほとんどなくなり、一時変数を明記しないで済むというメリットが生きてきます。

-[Q] ということは、uckはスタックマシンなの？
--[A] いやあ、そう言うときっと本当のスタックマシンに怒られてしまうと思うんですよね・・・。uckではPUSH命令が上記のようになってしまっているだけではなく、演算命令が先行するという「ポーランド記法」「Lisp語順」を採用していて、スタックマシンかどうかもあやしいです。だから（実は）そもそもPUSHしてないわけで・・・。
--ポーランド記法になっているのは、どんな演算子が先行しているのか（＝この数値はどの演算のために使われるのか）という「文脈情報」を解釈に役立てるためです。

** (6) もっと細かい余談を、Q&A形式で
-[Q:6-1] なんか全体的に、コードが短すぎる気がするが？(2)とか見てると、数式をコンパイルするのが32行でできるとか言っているわけだよね？
--[A:6-1] いやでも、ちゃんと動いていますし・・・。構造はちゃんとしていると思うので、演算子を増やしても少ししかコード増えないはずですし、優先順位判定もちゃんとやっています。

-[Q:6-2] 単純にprintfせずに、aに対してsprintfで追記しているのはなぜ？
--[A:6-2] aに追記しているのは、外部に出力する前に、最適化のためにコードを並べ替えたり、不要な命令を削ったりしたい場合もあるよなーと思って、aに追記するスタイルが癖になっているためです。今回の考察に限って言えば、ただのprintfで全く問題ないです。
--毎回strlenするのは明らかに無駄ですが、まあ今回は小規模なサンプルコードということで大目に見てください。

-[Q:6-3] (2-1)で出てきた疑似コードから、実際のx86のアセンブリにするところがわかりません。
--[A:6-3] いろいろな方法が考えられますが、できるだけ簡単な方法で考えるなら、こんな感じでしょうか。
 >reg 1+2*3  [再掲]
 * t,2,3    → MUL(t, 2, 3); // t=2*3;
 + u,1,t    → ADD(u, 1, t); // u=1+t;
 result=u   → 計算結果はuに入っています、という意味です。 tとかuは一時変数です。
 
 ;; MUL(t, 2, 3);
   MOV  EAX,2
   IMUL EAX,3
   MOV  [ESP+x],EAX ; xは変数tに対応するメモリオフセット.
 
 ;; ADD(u, 1, t);
   MOV  EAX,1
   ADD  EAX,[ESP+x] ; xは変数tに対応するメモリオフセット.
   MOV  [ESP+y],EAX ; yは変数uに対応するメモリオフセット.
--このような方法だとレジスタをEAXしか使わないことになります（割り算などをするときは他のレジスタも使うかもしれません）。
--こういう出力をするコンパイラの実装は簡単ですが、他のレジスタをほとんど使わないので不満かもしれません（もったいない！）。どの変数をレジスタ変数にしたらいいかをコンパイラが決められるようになれば、性能は改善するでしょう。でもそれは「コンパイラを簡単に作る」話ではなくて、最適化の話です。
--[追記] buntan-pcプロジェクトのuchanさんは、スタックマシン向けだとコンパイラが作りやすくなると思っている人のうちの一人です。・・・ここで例示したようなレジスタを1～2個しか使わないという方針なら、レジスタマシンでもスタックマシンでもコンパイラ作成の難易度は大差ないと、uchanさんからも意見をもらえました。一方で、レジスタをちゃんと活用しようとするとコンパイラ作成の難易度が上がるのは間違いなくて、それを念頭に「レジスタマシンはコンパイラが作りにくい」と考えているという意見をもらいました。・・・その点は私もそう思います。コンパイラを簡単に作ってそこから最適化を好きなように追加していけばいいと考えるか（＝私）、それともある程度の最適化ができなければレジスタマシンでコンパイラを作る意義はないと考えて「できない、難しい」と思うか（＝uchanさん）は、意見が分かれるところです。

//-（編集中）

// スタックマシンをバイトコードに採用すれば、プログラムが短くかける。
// スタックマシン・モデルを採用すれば、コンパイラが書きやすい。
// スタックマシンなCPUでも性能高く作れる。

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

* スタックマシンに関する幻想について
-(by [[K]], 2025.08.15)

- MUL(t, 2, 3); や ADD(u, 1, t); をどうやってx86のアセンブラに直せばいいの？という問い合わせがありました。それは[Q:6-3]で説明します。

//-（編集中）

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