text0006 のバックアップ(No.6)

[ トップ ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• text0006 へ行く。
  • 1 (2019-02-25 (月) 19:05:53)
  • 2 (2019-02-25 (月) 20:05:58)
  • 3 (2019-02-28 (木) 11:01:09)
  • 4 (2019-03-01 (金) 13:48:39)
  • 5 (2019-05-04 (土) 21:48:46)
  • 6 (2019-05-05 (日) 10:11:10)

---

川合のプログラミング言語自作のためのテキスト#0006

• (by K, 2019.02.25)

(11) TJ-03

• お待たせしました。さあついにJITコンパイラです。プログラミング言語の最前線です。

  #include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  #include <windows.h>	// 他のOSではここを書き換える.
  
  void loadText(int argc, const char **argv, unsigned char *t, int siz) → TL-1と同じなので省略
  
  int var[256];	// 変数.
  unsigned char txt[10000];	// ソースコード.
  int pc = 0;	// プログラム・カウンター.
  unsigned char *code;	// 機械語出力先.
  int qc = 0; // 出力用のプログラム・カウンター.
  
  void put32(int i)
  {
      code[qc++] =  i        & 0xff;
      code[qc++] = (i >>  8) & 0xff;
      code[qc++] = (i >> 16) & 0xff;
      code[qc++] = (i >> 24) & 0xff;
  }
  
  #define EAX     0
  #define ECX     1
  
  void getNumber(int reg)  // 定数は2桁以上でもOK. レジスタに値をセットするための命令群を出力する.
  {
      unsigned char c = txt[pc], *p, *q;
      if ('0' <= c && c <= '9') { // 数字.
          p = &txt[pc];
          code[qc++] = 0xb8 + reg;	// MOV reg,const.
          put32(strtol(p, (char **) &q, 0));
          pc += q - p;
          return;
      }
      pc++; // 1文字の変数.
      code[qc++] = 0x8b;	// MOV reg,[const].
      code[qc++] = reg * 8 + 0x05;
      put32((int) &var[c]);
  }
  
  void sub_print(int i)
  {
      printf("%d\n", i);
  }
  
  void sub_time()
  {
      printf("time=%.3f[sec]\n", clock() / (double) CLOCKS_PER_SEC);
  }
  
  int main(int argc, const char **argv)
  {
      int i, j, k, pc0, wqc = 0, wqc2 = 0;
      void (*func)();	// funcは関数へのポインタ型の変数.
      loadText(argc, argv, txt, 10000);
  
      // Windowsに対して、実行権限のあるメモリを特別に要求.
      code = VirtualAlloc(0, 1024 * 1024, MEM_COMMIT, PAGE_EXECUTE_READWRITE);
  
      code[qc++] = 0x83;	// SUB ESP,124.
      code[qc++] = 0xec;	//  この命令でスタックを調整させる.
      code[qc++] = 0x7c;
      for (;;) {
          pc0 = pc;
          if (txt[pc] == 0)	// ファイル終端.
              break;		
          if (txt[pc] == '\n' || txt[pc] == ' ' || txt[pc] == '\t' || txt[pc] == ';') { // 空行など.
              pc++;
          } else if (txt[pc + 1] == '=') { // 2文字目が"=".
              i = txt[pc];	// 1文字の変数名.
              pc += 2;
              getNumber(EAX);
              if (txt[pc] == ';') {
              } else if (txt[pc] == '+') {	// 加算.
                  pc++;
                  getNumber(ECX);
                  code[qc++] = 0x01;	// ADD EAX,ECX.
                  code[qc++] = 0xc8;
              } else if (txt[pc] == '-') {	// 減算.
                  pc++;
                  getNumber(ECX);
                  code[qc++] = 0x29;	// SUB EAX,ECX.
                  code[qc++] = 0xc8;
              } else
                  goto err;
              code[qc++] = 0xa3;	// MOV [const],EAX.
              put32((int) &var[i]);
          } else if (txt[pc] == 'p' && txt[pc + 1] == 'r' && txt[pc + 5] == ' ') { // 最初の2文字しか調べてない(手抜き).
              pc += 6;
              getNumber(EAX);
              code[qc++] = 0x89;	// MOV [ESP],EAX.
              code[qc++] = 0x04;
              code[qc++] = 0x24;
              k = (unsigned char *) sub_print - &code[qc + 5];
              code[qc++] = 0xe8;	// CALL sub_print.
              put32(k);
          } else if (txt[pc] == 'w' && txt[pc + 1] == 'h' && txt[pc + 5] == ' ' && txt[pc + 7] == '<') { // 最初の2文字しか調べてない(手抜き).
              wqc = qc;
              pc += 6;
              getNumber(EAX);	// 1文字の変数名.
              pc++;
              getNumber(ECX);
              if (txt[pc] != '{')
                  goto err;
              pc++;
              code[qc++] = 0x39;	// CMP EAX,ECX.
              code[qc++] = 0xc8;
              code[qc++] = 0x0f;	// JGE ????
              code[qc++] = 0x8d;
              wqc2 = qc;
              put32(0);	// ここは後で更新する.
          } else if (txt[pc] == '}') {
              pc++;
              code[qc++] = 0xe9;
              put32(wqc - (qc + 4));
              k = qc - (wqc2 + 4);
              code[wqc2 + 0] =  k        & 0xff;
              code[wqc2 + 1] = (k >>  8) & 0xff;
              code[wqc2 + 2] = (k >> 16) & 0xff;
              code[wqc2 + 3] = (k >> 24) & 0xff;
          } else if (txt[pc] == 't' && txt[pc + 1] == 'i') { // 最初の2文字しか調べてない(手抜き).
              pc += 4;
              k = (unsigned char *) sub_time - &code[qc + 5];
              code[qc++] = 0xe8;	// CALL sub_time.
              put32(k);
          } else
              goto err;
      }
      code[qc++] = 0x83;	// ADD ESP,124.
      code[qc++] = 0xc4;	//  最初に調整したスタックを元に戻す.
      code[qc++] = 0x7c;
      code[qc++] = 0xc3;	// RET.
  //  for (i = 0; i < qc; i++) { printf("%02x ", code[i]); } exit(0); //  デバッグ用.
      func = (void *) code;
      func();
      exit(0);
  err:
      printf("syntax error : %.10s\n", &txt[pc0]);
      exit(1);
  }

• 重要な注意点：
  • このプログラムはWindows用に書かれています。しかも32ビットアプリです。gccでコンパイルする場合は-m32オプションを忘れずにつけましょう。
  • もしWindows以外で実行したい場合は、以下のように書き換えてください。
• [Q] macOSではどうやればTJ-03が動くの？
  • まず冒頭の #include <windows.h> を以下と入れ替えます。

    #include <mach/mach.h>

  • そんでもって、codeへの代入文を以下のように書き換えます。

    code = malloc(1024 * 1024); vm_protect(mach_task_self(), (vm_address_t) code, 1024 * 1024, FALSE, VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE);

  • これで行けるはずです。
  • 要するにメモリ領域code[]に実行可能権限を付ければいいのです。
  • そして32ビットアプリとしてコンパイルするのを忘れずに。
• [Q] LinuxではどうやればTJ-03が動くの？
  • http://mimumimu.net/blog/2011/11/17/Cコード中にマシン語を埋め込んで実行する。/
  • この記事をよく読んで、上記のmacOSのやり方も参考にして、自分で解決してみましょう。そんなには難しくないはずです。

• このTJ-03はTJ-02と完全互換です。違うのは実行速度だけです。だから以下の1億回ループのプログラムもそのまま実行できます。

  i=0;
  while i<100000000{
     i=i+1;
  }
  print i;
  time;

• 実行速度を比較してみてください。TJ-02はTL-3と比べて数倍の速さを誇っていましたが、TJ-03はそのTJ-02と比較しても数十倍の速さが出るはずです。・・・JITコンパイラがどれほどすごいか感じてもらえたのではないでしょうか？
• しかもこのJITコンパイラはTJ-02と比べてコードを複雑にしないために結構手抜きをしています。つまりまだ速くなる余地を残しているのです。それでもこんなに速いのです。
• 正直、プログラムの中身は良くわからないところがたくさんあると思います。でも行数的には全然大したことはないということにも気づいてください。JITコンパイラは複雑で難しい技術なのではなく、要するに機械語を知っているかどうかの知識の差でしかないのです。プログラミング的な難易度は大したことないのです。・・・これを手掛けない理由があるでしょうか！（笑）。・・・そしてこれを機械語の知識なしに書ける時代がもし来たら・・・。

(12) TJ-03の説明

• 機械語が得意でたまらないという奇特な人を除けば、さすがにこれを説明なしで理解することはできないでしょう。
• まず、上記のサンプルプログラムが、どんな機械語に変換されているのかを示します。

  ソースコード	生成された機械語(16進数)	機械語をアセンブラで書き直したもの（参考用）	アセンブラをさらにC言語っぽく書いてみたもの（参考用）	補足説明
  	83 EC 7C	SUB ESP,124	ESP -= 124;	スタック領域に作業用スペースを確保（ソースコードに無関係に生成）
  i=0;	B8 00 00 00 00	MOV EAX,0	EAX = 0;	これはgetNumber(EAX)が定数0を読み込むために生成したコード
  	A3 xx xx xx xx	MOV [xxxx],EAX	[xxxx] = EAX;	xxxxはvar['i']のアドレス
  while i<100000000{	8B 05 xx xx xx xx	MOV EAX,[xxxx]	EAX = [xxxx];	xxxxはvar['i']のアドレス。これはgetNumber(EAX)が変数iを読み込むために生成したコード
  	B9 00 E1 F5 05	MOV ECX,100000000	ECX = 100000000;	これはgetNumber(ECX)が定数1億を読み込むために生成したコード
  	39 C8	CMP EAX,ECX	if (EAX >= ECX)
  	0F 8D 17 00 00 00	JGE $+23	goto 23バイト先	このとび先は}を発見してから書き込んでいる
  i=i+1;	8B 05 xx xx xx xx	MOV EAX,[xxxx]	EAX = [xxxx];	xxxxはvar['i']のアドレス。これはgetNumber(EAX)が変数iを読み込むために生成したコード
  	B9 01 00 00 00	MOV ECX,1	ECX = 1;	これはgetNumber(ECX)が定数1を読み込むために生成したコード
  	01 C8	ADD EAX,ECX	EAX += ECX;
  	A3 xx xx xx xx	MOV [xxxx],EAX	[xxxx] = EAX;	xxxxはvar['i']のアドレス
  }	E9 D6 FF FF FF	JMP $-42	goto 42バイト前	これはwhile命令のところを指している
  print i;	8B 05 xx xx xx xx	MOV EAX,[xxxx]	EAX = [xxxx];	xxxxはvar['i']のアドレス。これはgetNumber(EAX)が変数iを読み込むために生成したコード
  	89 04 24	MOV [ESP],EAX	[ESP] = EAX;	第一引数にセット（第一引数＝スタックトップ）
  	E8 xx xx xx xx	CALL _sub_print	sub_print();	C言語で書かれた関数を呼び出す
  time;	E8 xx xx xx xx	CALL _sub_time	sub_time();	C言語で書かれた関数を呼び出す
  	83 C4 7C	ADD ESP,124	ESP += 124;	スタック領域の作業用スペースを解放（ソースコードに無関係に生成）
  	C3	RET	return;	機械語関数を終了（ソースコードに無関係に生成）

• x86の32ビットの機械語では、レジスタと呼ばれるCPU内の変数を使って処理を進めていきます。上記で出てきている、EAX, ECX, ESPというのはどれもレジスタ名です。他にも5つのレジスタがあり、合計8つのレジスタがあります（本当は他にもありますが、それらは用途がかなり特殊化されており、自由には使えません）。
  • またこのESPはスタックの管理のために使うレジスタなので、それほど自由には使えません。
• TJ-03では変数iなどはvar[]の中にあり、つまりこれはメモリ上にあるので、MOV命令でレジスタに読み込んだり、MOV命令でレジスタから書き込んだりして処理を進めています。
• 機械語は覚えるのが容易ではないので、コード表などから調べてきます。でもフル仕様のコード表はそれだけですごい量なので、簡易版を参照するといいかもしれません。
  • 簡易版のコード表: text0006a

(13) なぜ32ビットコードにしたのか？

• 今は64ビット対応のCPUがかなり普及して、OSやコンパイラも64ビット対応したものが入手しやすくなっています。だから64ビットで作ってしまえば、先進的でよさそうに思うかもしません。
• 64ビット化することで大きく変わるのは、使えるレジスタの数です。32ビットでは自由に使えるレジスタが7本ありますが、64ビットでは15本になります。それ以外では、32ビットモードではポインタが4バイトで64ビットモードではポインタが8バイトになるくらいの違いしかありません。・・・レジスタはキャッシュメモリみたいな効果があります。だからキャッシュメモリが倍増すると思ってください。ただしキャッシュメモリとは違って、コンパイラが上手にレジスタ割り当てを行わなければ性能は出ません。だからJITコンパイラでレジスタ割り当てを頑張る気がないのであれば、64ビットに手を出しても自己満足以上のものは得られません（まあ2GBを超える巨大な配列を扱えるというメリットもありますが）。
• 仮に割り付けを十分に頑張ったとして、レジスタが倍増すると速度も倍増するでしょうか？いいえ、違います。上位7個の頻出変数をレジスタにキープするだけで全体のアクセスのかなりの割合がカバーできます。そしてそれが15個に増えてもカバー率はせいぜい1割くらいしか向上しません。だから速度もその程度しか変わりません（だから一般にアプリやOSが64ビット化しても実行速度は大きくは向上しないわけです）。
• また64ビットの機械語はややこしいことになっているので、32ビットの機械語よりも複雑です。さらに64ビットではC言語での呼び出し規約がOS間で統一されていないという問題もあります。・・・ということでいきなり64ビットのJITコンパイラに挑戦して失敗のリスクを上げても、得られるメリットは大きくないので、お勧めしがたいのです。
• もちろん32ビットのJITコンパイラが書けるようになってから、64ビットのJITコンパイラに挑戦してみるというのは、十分によい選択肢だと思います。差異はそれほど大きくはありませんので、32ビットでできるようになった後なら、きっと乗り越えられるでしょう。

次回に続く

• 次回: （この先にJCKライブラリを利用した話を予定していますが、準備ができるのは当分先です。）

こめんと欄

• セキュリティキャンプに挑戦中のものです。このlinuxで実行権限のあるメモリを特別に要求するプログラムはmallocでやるとドツボにはまって、 if (posix_memalign((void**)&code, 1024 * 1024, 1024 * 1024) == -1){ printf("memalign:error"); exit(1); } // Linuxに対して、実行権限のあるメモリを特別に要求 if (mprotect((void*)code, 1024*1024, PROT_READ | PROT_WRITE | PROT_EXEC) == -1){ printf("mprotect:error"); exit(1); }みたいな感じでいいのでしょうか。 -- taka2 2019-05-04 (土) 21:24:46
• 無事問題が解決し、このJITコンパイラを試すことができました。本当に早いですね！！ -- taka2 2019-05-04 (土) 21:48:46
• 自己解決素晴らしいです！ -- K 2019-05-05 (日) 10:11:10

コメント	お名前	NameLink

     

Site admin: K

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 5.6.40. HTML convert time: 0.017 sec.