p20250815a のバックアップ(No.7)

スタックマシンに関する幻想について

(by K, 2025.08.15)

↑

(0) はじめに

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

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

↑

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

↑

(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

こんな感じでうまくいきました。
だからたいして大変ではないのです。

↑

(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命令のコストが無視できるようになれば、スタックマシンでもデメリットはほとんどなくなり、一時変数を明記しないで済むというメリットが生きてきます。