a21_txt02

「10日くらいでできる！プログラミング言語自作入門」の続編#1-1

• (by K, 2021.04.05)

(1) はじめに

• このテキストは、「10日くらいでできる！プログラミング言語自作入門」（a21_txt01）の続編にあたります。ですからこの続編テキストのスタート地点は772行のHL-9aになります。
• このシリーズでは、言語に新規の命令を追加することは最小限に抑えて、主にJITコンパイラ化や普通のコンパイラへの改造がメインです。

• 言語に独自の機能を加えていって言語を「進化」させていく話は、「a21_txt03」でやる予定です。そこでは言語がどうすれば便利になるかを考えていきます。

• もくじ（HL-1から順番に読んでいくとわかるように書いています）

• 速度のめやす
  • 速度のめやす1: 10億回ループをgcc-O3(32bit)でやった場合との実行時間の比較です。
  • 速度のめやす2: mandel.cをgcc-O3(32bit)でやった場合との実行時間の比較です。mandel.cはa21_txt01_9aにあります。

• HL-14～16（HL-20～22）は最適化の話ばかりになります。そこに興味がなければ読み飛ばしてしまって構いません。
  • （JITコンパイラ化は、第一に高速化のためにやることなので、ここで最適化をやるのは、合理的な話の流れかなと思っています。）
• たとえばHL-11のあとにHL-11aがあります。これは1回分の内容を2回に分けたほうが理解しやすい（説明しやすい）と考えて分割したもので、内容的には2つで1回分くらいになっています。

(2) HL-11

• ということで、HL-11について説明したいと思います。HL-1から読んでいる人は、HL-10がないじゃないかと思うでしょう。この続編では、HL-11～22を使いたいと思っているので、HL-10は欠番にしました。

• HL-11の基本方針はこうです。
  • [1]compile()関数では、内部コード出力をやめて、代わりにx86の機械語を出力する。
  • [2]exec()関数は不要なので削除。
  • [3]機械語を出力するにあたって、putIc()のままでは全然便利ではないので、putIcX86()を新規に作る。
  • [4]それにともない、putIc()関数は期待通りには動かなくなるので、これを呼び出したらエラー終了するようにしておく（将来的にはこの関数は削除する）。
  • [5]とりあえず、単純代入命令とprint命令だけputIcX86()に対応させる。残りは後回し。
• こうすることで、HL-9aをJITコンパイラ型の言語に改造します。そうすると何がよくなるのかというと、実行速度がうんと速くなるはずなのです。・・・それだけです。
• この改造をすると、言語はCPUに依存するようになります。x86以外ではこのプログラムは動きません。それがデメリットです。・・・またもし自力で改造する場合は、機械語に対する知識も必要になります。今まではC言語で普通に書くだけでうまくできたので、それと比べればハードルは高いです。
• しかしそれでも、やるだけの価値はあります。それほど高速になります。

• 説明が前後していますが「JITコンパイラ」というのは「Just-In-Time コンパイラ」のことで、ソースファイルからコンパイルして実行ファイルを作る普通のコンパイラとは異なり、インタプリタで命令の実行を指示された瞬間に高速にコンパイルして実行するという仕組みのことです。ユーザからはコンパイル動作は全く意識されず、ただの速いスクリプト言語に見えます。

#include <acl.c>

typedef unsigned char *String;	// こう書くと String は unsigned char * の代用になる.

int loadText(String path, String t, int siz) → HL-4と同じなので省略

///////////////////////////////////////////////////////////////////////////////

#define MAX_TC  1000 // トークンコードの最大値.
String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶.
int tl[MAX_TC + 1]; // トークンの長さ.
unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定.
int tcs = 0, tcb = 0;

AInt var[MAX_TC + 1];	// 変数.

int getTc(String s, int len) → HL-8aと同じなので省略

///////////////////////////////////////////////////////////////////////////////

int isAlphabetOrNumber(unsigned char c) → HL-2と同じなので省略

int lexer(String s, int tc[]) → HL-9aと同じなので省略

int tc[10000];	// トークンコード.

enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcBrOpn, TcBrCls, TcSqBrOpn, TcSqBrCls, TcCrBrOpn, TcCrBrCls,
    TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt, TcPlus, TcMinus, TcAster, TcSlash, TcPerce, TcAnd, TcShr, TcPlPlus, TcEqu,
    TcComma, TcExpr, TcExpr0, TcTmp0, TcTmp1, TcTmp2, TcTmp3, TcTmp4, TcTmp5, TcTmp6, TcTmp7, TcTmp8, TcTmp9 };

char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 ( ) [ ] { } == != < >= <= > + - * / % & >> ++ = , !!** !!*** _t0 _t1 _t2 _t3 _t4 _t5 _t6 _t7 _t8 _t9";

///////////////////////////////////////////////////////////////////////////////

int phrCmp_tc[32 * 100], ppc1, wpc[9], wpc1[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす.

int phrCmp(int pid, String phr, int pc) → HL-7と同じなので省略

/////////////////////////////////////////////////////////////////////////////// → ここまではHL-9aと全く同じ、ここから改造が始まる.

typedef AInt *IntP; // こう書くと IntP は AInt * の代わりに使えるようになる.

enum { OpCpy = 0, OpCeq, OpCne, OpClt, OpCge, OpCle, OpCgt, OpAdd, OpSub, OpMul, OpDiv, OpMod, OpAnd, OpShr, 
    OpAdd1, OpNeg, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpPrint, OpTime, OpEnd,
    OpPrints, OpAryNew, OpAryInit, OpArySet, OpAryGet, OpOpnWin, OpSetPix0, OpM64s, OpRgb8, OpWait,
    OpXorShift, OpGetPix, OpFilRct0, OpPrm, OpF16Sin, OpF16Cos, OpInkey, OpDrwStr0, OpGprDec, OpBitBlt };

unsigned char *ic, *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ.

void putIc(int op, IntP p0, IntP p1, IntP p2, IntP p3)  // 移行中の間だけ、以下の形で残しておく.
{
    printf("putIc: error\n");
    exit(1);
}

int getHex(int c) // 16進数に使える文字ならそれを0～15の数に変換、そうでなければ-1を返す関数.
{
    if ('0' <= c && c <= '9') return c - '0';
    if ('a' <= c && c <= 'f') return c - 'a' + 10;
    if ('A' <= c && c <= 'F') return c - 'A' + 10;
    return -1;
}

int get32(unsigned char *p)
{
    return p[0] + p[1] * 256 + p[2] * 65536 + p[3] * 16777216;
}

void put32(unsigned char *p, int i)
{
    p[0] =  i        & 0xff; // 1バイト目に、ビット0～7の内容を書き込む.
    p[1] = (i >>  8) & 0xff; // 2バイト目に、ビット8～15の内容を書き込む.
    p[2] = (i >> 16) & 0xff; // 3バイト目に、ビット16～23の内容を書き込む.
    p[3] = (i >> 24) & 0xff; // 4バイト目に、ビット24～31の内容を書き込む.
}

void putIcX86_sub(String s, IntP a[])
{
    int i, j, k;
    for (i = 0; s[i] != 0; ) {
        if (s[i] == ' ' || s[i] == '\t' || s[i] == '_' || s[i] == ':' || s[i] == ';') {
            i++;
        } else if (getHex(s[i]) >= 0 && getHex(s[i + 1]) >= 0) { // 16進数2桁.
            *icq = getHex(s[i]) * 16 + getHex(s[i + 1]);
            i += 2;
            icq++;
        } else if (s[i] == '%') {
            j = s[i + 1] - '0';
            if (s[i + 2] == 'm') {	// mod r/m.
                k = s[i + 3] - '0';
                *icq = 0x05 + k * 8;
                put32(icq + 1, (int) a[j]);
                icq += 5;
                i += 4;
                continue;
            }
            if (s[i + 2] == 'i') {	// int.
                put32(icq, (int) a[j]);
                icq += 4;
            }
            if (s[i + 2] == 'c') {	// char.
                *icq = (int) a[j];
                icq++;
            }
            if (s[i + 2] == 'r') {	// relative.
                put32(icq, (int) a[j] - (int) (icq + 4));
                icq += 4;
            }
            i += 3;
        } else {
            printf("putIcX86: error: '%s'\n", s);
            exit(1);
        }
    }
}

void putIcX86(String s, IntP p0, IntP p1, IntP p2, IntP p3)  // ic[]へ簡単に書き込むための便利関数.
{
    IntP a[4];
    a[0] = p0;
    a[1] = p1;
    a[2] = p2;
    a[3] = p3;
    putIcX86_sub(s, a);
}

///////////////////////////////////////////////////////////////////////////////

char tmp_flag[10]; // 一時変数の利用状況を管理.

int tmpAlloc() → HL-7と同じなので省略

void tmpFree(int i) → HL-7と同じなので省略

///////////////////////////////////////////////////////////////////////////////

void sub_print(int i)
{
    printf("%d\n", i);
}

///////////////////////////////////////////////////////////////////////////////

int epc, epc1;	// exprのためのpcとpc1.

int exprSub(int priority);	// exprSub1()が参照するので、プロトタイプ宣言.
int expr(int j);
int phrCmpPutIc(int pid, String phr, int pc, int *pi, int lenExpr, int op, int *err);

int exprSub1(int i, int priority, int op) → HL-7と同じなので省略

int exprSub(int priority) → HL-9と同じなので省略

int expr(int j) → HL-7と同じなので省略

///////////////////////////////////////////////////////////////////////////////

enum { IfTrue = 0, IfFalse = 1 };

void ifgoto(int i, int not, int label) → HL-8と同じなので省略

int tmpLabelNo;

int tmpLabelAlloc() → HL-8と同じなので省略

#define BInfSiz		10

int binf[BInfSiz * 100], bd, lbd; // binf:block-info, bd:block-depth, lbd:loop-block-depth

enum { BlkIf = 1, BlkFor, BlkMain }; // BlkMainをHL-9aで追加.
enum { IfLabel0 = 1, IfLabel1 };
enum { ForLopBgn = 1, ForCont, ForBrk, ForLbd0, ForWpc01, ForWpc11, ForWpc02, ForWpc12 };

int phrCmpPutIc(int pid, String phr, int pc, int *pi, int lenExpr, int op, int *err)  // 移行中の間だけ、以下の形で残しておく.
{
    if (phrCmp(pid, phr, pc)) {
        printf("phrCmpPutIc: error\n");
        exit(1);
    }
    return 0;
}

int phrCmpPutIcX86(int pid, String phr, int pc, int *pi, int lenExpr, void *sub, int *err)
{
    int e[9], i;
    if (phrCmp(pid, phr, pc)) {
        e[0] = e[1] = e[2] = e[3] = e[4] = e[5] = e[6] = e[7] = e[8] = 0;
        for (i = 0; i < lenExpr; i++) {
            e[i] = expr(i);
        }
        for (i = 0; i < lenExpr; i++) {
	     putIcX86("8b_%0m0; 89_44_24_%1c;", &var[e[i]], (IntP) (i * 4), 0, 0);
        }
        putIcX86("e8_%0r;", sub, 0, 0, 0);
        for (i = 0; i < lenExpr; i++) {
            if (e[i] < 0) {
                *err = -1;
            }
            tmpFree(e[i]);
        }
        if (pi != 0) {
            *pi = tmpAlloc();
            putIcX86("89_%0m0;", &var[*pi], 0, 0, 0);
        }
        return 1;
    }
    return 0;
}

///////////////////////////////////////////////////////////////////////////////

int compile(String s)
{
    int pc, pc1, i, j;
!   unsigned char *icq1, *icp;
    pc1 = lexer(s, tc);
    tc[pc1++] = TcSemi;	// 末尾に「;」を付け忘れることが多いので、付けてあげる.
    tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot;	// エラー表示用のために末尾にピリオドを登録しておく.
    icq = ic;
+   putIcX86("60; 83_ec_7c;", 0, 0, 0, 0); // PUSHAD(); SUB(ESP,124);
    for (i = 0; i < 10; i++) {
        tmp_flag[i] = 0;
    }
    tmpLabelNo = 0;
    bd = lbd = 0;
    for (pc = 0; pc < pc1; ) { // コンパイル開始.
        int e0 = 0, e2 = 0;
        if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入.
!           putIcX86("8b_%1m0; 89_%0m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
        } else if (phrCmp(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) {
        （中略）
!       } else if (phrCmpPutIcX86(4, "print !!**0;", pc, 0, 1, sub_print, &e0)) {
        （中略）
    }
    if (bd > 0) {
        printf("block nesting error (bd=%d, lbd=%d, pc=%d, pc1=%d\n", bd, lbd, pc, pc1);
        return -1;
    }
!   putIcX86("83_c4_7c; 61; c3;", 0, 0, 0, 0); // ADD(ESP,124); POPAD(); RET();
    icq1 = icq;
    // ここにあった「goto先の設定」はいったん全部削除.
    return icq1 - ic;
err:
    printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]);
    return -1;
}

// このあたりにあったexec()関数の記述はすべて削除.
// ついでに変数winの宣言も削除.

int run(String s)
{
    if (compile(s) < 0)
        return 1;
+   void (*func)() = (void (*)()) ic;
!   func();
    return 0;
}

// 以下のmallocRWX()はWindows用の記述. Linux系のOSの場合は本文中で説明します.

#include <windows.h>

void *mallocRWX(int siz)
{
    return VirtualAlloc(0, siz, MEM_COMMIT, PAGE_EXECUTE_READWRITE);
}

///////////////////////////////////////////////////////////////////////////////

void aMain()
{
    unsigned char txt[10000];
    int i;
+   ic = mallocRWX(1024 * 1024); // 1MB
    lexer(tcInit, tc);
    （中略）
}

• プログラムは692行になりました。このHL-11では、printと単純代入命令だけが使えます。代入以外の演算は一切できません（それはHL-11aでやります）。

  >print 1
  1
  
  >print 2
  2
  
  >a=4
  
  >print a
  4

• とてもつまらなくなったのではありますが、しかしこれは全部exec()なしで実現していて、自分の入力がx86の機械語になって実行されているのだと思うと、少し感動します。

(3) HL-11に関する重要な説明

• このHL-11は、x86の32bitモード専用で書かれています。したがって、gccでコンパイルする場合は、32bit対応のコンパイラで、-m32を付けてコンパイルしなければいけません。他のコンパイラでも、もしモードを指定しなければいけない場合は、32bitを指定してください。
• 「なぜ現在主流の64bitではなく、32bitにしたのか？」ですが、32bitモードの機械語が、64bitモードの機械語よりもだいぶ簡単だからです。
  • より具体的に言うと、x64の何が難しいのかというと、JITコンパイラで生成した機械語からC言語で書いておいた関数を呼び出すときに、おそらくその距離は2GBを超えるため、結構ややこしいことをしなければいけなくなることです。この説明をするのが嫌だったのが一つ目の理由です。
  • もう一つは、x64ではOSごとに関数呼び出し規則が違っていて（＝統一されておらず）、それで説明がややこしくなります。その面倒さからも逃げたいと思ったのでした。これが二つ目の理由です。
  • そして、64bitモードにしてもしなくても、速度はほとんど変わらない、ということもあります。これがもし、実行速度が2倍とか3倍とかの違いがあれば、私だって無理して頑張るのですが・・・。また少なくともWindowsの場合は、32bitアプリも64bitアプリも同じように実行できます。違いはありません。
  • ということで、64bitモード対応は将来の課題ということにして、ここではx86の32bitモード専用で話を進めます。なお、32bitモードでのやり方を理解した後でなら、上記の2点だけを気にするだけでよくなるので、もう64bitモード対応はそれほど大変ではありません。いきなり最初からやるのは大変だというだけです。

(4) 今回の改造のあらまし

• 今回からic[ ]に機械語を入れて実行することになるのですが、近年のOSはセキュリティ対策のため、適当な配列に正しい機械語を書き込んで準備しても、それを実行することができません（データ実行防止機能のためです）。
• しかしこれができなければ、そもそもJITコンパイラなんて実現できなくなってしまいます。ということで、それぞれのOSは、実行可能な配列を確保するための特別な手続きを用意しています。

• Windowsの場合は、上記のプログラムのように

  #include <windows.h>
  
  void *mallocRWX(int siz)
  {
      return VirtualAlloc(0, siz, MEM_COMMIT, PAGE_EXECUTE_READWRITE);
  }

• とすることで可能になります。

• LinuxなどのPOSIX系のOSでは、以下のようにやればできます。

  #include <unistd.h>
  #include <sys/mman.h>
  
  void *mallocRWX(int siz)
  {
      return mmap(0, siz, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
  }

• HL-11ではこのmallocRWX()を呼び出して、返値をicに代入して、1MBのic[ ]を準備しています（aMain()の中でこの処理をやっています）。

• ic[ ]の中に機械語を書き込んだ後は、

      void (*func)() = (void (*)()) ic;
      func();

• これで呼び出しています（これはrun()関数の中に書いてあります）。この1行目は変数funcの宣言をして、初期値としてicを代入しています。funcは関数ポインタ型の変数です。すごくわかりにくい書き方をするのですが、これがC言語での書き方なので、それはひとまずそういうものなんだなということで許してください。
• 2行目はただの関数呼び出しです。こうすることで、ic[ ]に書かれた機械語が普通の関数のように実行されるのです。
• ic[ ]に適切な機械語を書き込むのは、compile()関数の仕事です。・・・以上のような構成で、HL-11は作られています。
• なお、ic[ ]に機械語を書き込む際には、1バイトずつ書き込むほうが便利なので、ic[ ]の型も符号なしのchar型に変更しています。

(5) 生成している機械語の説明（putIcX86()やphrCmpPutIcX86()の説明も含む）

• ここを読んでいる多くの人は、おそらくx86の機械語なんて知らないでしょう。普通にプログラムしているだけならそんなことは知らなくていいことです。

• compile()では、ic[ ]の冒頭に、

      putIcX86("60; 83_ec_7c;", 0, 0, 0, 0); // PUSHAD(); SUB(ESP,124);

• を書きこんでいます。また末尾には、

      putIcX86("83_c4_7c; 61; c3;", 0, 0, 0, 0); // ADD(ESP,124); POPAD(); RET();

• を書き込んでいます。・・・まずはこのあたりから説明します。
• まず命令「60」は、1バイトの命令で、EAX～EDIの8つのレジスタの値をスタックに書き込む命令です。ここで保存した値は、末尾の命令「61」ですべて読み込まれて、レジスタの値が元通りになります。・・・こうすることで、プログラム内では8つのレジスタを自由に使えるようになります。どんなに値がおかしくなっても、戻せる保証があるので心配いりません（とはいえ、ESPレジスタは自由にはできないので、実際に自由に使うのはそれ以外の7つのレジスタだけですが）。

• 命令「83_ec_7c」は3バイトの命令で、ESP=ESP-124;を計算させる命令です。これで関数呼び出しのための引数受け渡し領域を確保しています（こんなにたくさんは必要ないかもしれませんが、ひとまず大きめにしてあります）。これに対応しているのが「83_c4_7c」です。こちらはESP=ESP+124;計算させる命令で、上記で確保した領域を解放するために使っています。・・・最後の「c3」はreturn;命令です。

• ここでputIcX86()関数についても説明します。最初に文字列で書き込みたい機械語を記述します。16進数で書けばいいだけなのですが、間にスペースやアンダスコアやコロンやセミコロンを自由に混ぜることができます（どれも単に無視されます）。そのあとに4つのゼロがありますが、これは文字列の中に%拡張命令を書いた時に参照されるデータを置くところで、%拡張を使わないときは単に0を4つ並べておきます（何を書いても無視されます）。

• 単純代入命令では、

      putIcX86("8b_%1m0; 89_%0m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);

• という機械語を使っています。ちなみにここはHL-9aでは

      putIc(OpCpy,  &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);

• になっていました。第二引数以降は完全に同じになっています。違いが少ないほうが理解が早まるだろうと思って頑張りました！

• 命令「8b」と「89」はどちらもアセンブラではMOV命令と呼ばれているもので、メモリから32bitのデータを読み込んでレジスタにしまったり、レジスタの32bitのデータをメモリに書き込んだり、レジスタからレジスタに32bitのデータをコピーしたりすることができます。8bの場合、「メモリ→レジスタ」で、89が「レジスタ→メモリ」になります。「レジスタ→レジスタ」の場合は、8bでも89でもどっちでもOKです。

• 次の%1m0の意味するところは、まず1で「追加引数の[1]を参照しろ、と指示しています。つまりここでは「&var[tc[wpc[1]]]」を選んだことになります。次にmです。これで8b命令のためのパラメータ（機械語用語ではオペランド）を生成することになります。
• 最後の0は、オペランド内の第二引数欄に0を指定せよ、という意味です。
• 8b命令や89命令では、命令コードの直後に「mod r/mバイト」と呼ばれる1バイトを必ず置くことになっています。この1バイトでオペランド内容を記述するのです。この1バイトで指定できるオペランドは2つあって、第一オペランドではメモリかレジスタのどちらかを指定できます。第二オペランドではレジスタしか指定できません（命令によっては第二オペランドで0～7の定数を指定することもあります）。メモリを指定した場合は、さらに何バイトかの追加パラメータが後続する場合もあります。

• この例では第二オペランドは0なので、EAXレジスタを指定したことになります。

• ということでまとめると、最初の8b命令で、 EAX = var[tc[wpc[1]]]; を実行します。次の89命令で、 var[tc[wpc[0]]] = EAX; を実行します。だから変数から変数へ単純代入をしたことになるわけです。

• 次はprint命令です。phrCmpPutIcX86()関数によって、こんな感じに機械語が生成されます。

  putIcX86("8b_%0m0; 89_44_24_%1c;", &var[e[0]], 0, 0, 0);
  putIcX86("e8_%0r", sub_print, 0, 0, 0);

• 1行目で、print命令の引数をEAXに読み込んだ後、[ESP+0] = EAX;で、その値をスタックの一番上に書き込みます。%1cは追加引数[1]の値を1バイト（char）で書き込んでいるだけです。もう少し詳しく言うと、44_24_00が[ESP+0]とEAXを表しています。
  • このmod r/mについての詳しいことは、たとえば https://www.wdic.org/w/SCI/ModR/M に書いてありますが、しかしこれもいきなり見てもよくわからないと思います・・・。
• 2行目のe8命令は、アセンブラではCALL命令と言われているものです。関数を呼び出します。%0rは、e8命令で関数の場所を指定するときに使う拡張命令です（x86では関数呼び出しや分岐命令で分岐先を示す場合、そのアドレスをそのまま書くのではなく、現在位置（＝次の命令の先頭位置）からの相対値で書くことになっています。%0rは、その相対値計算をしてから4バイトを書く拡張命令なのです）。

• これですべてです。結局、60, 61, 83, c3, 8b, 89, e8の7種類の命令しか使っていません。単純代入とprint命令だけならこれで十分だというわけです。

(6) 機械語を調べるためのリンク集

• https://www.wdic.org/w/SCI/ModR/M : mod R/Mについて
• http://ref.x86asm.net/coder32.html : x86の機械語の一覧

次回に続く

• 次回: a21_txt02_1a

こめんと欄