a21_txt02
の編集
https://essen.osask.jp/?a21_txt02
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
BracketName
EssenRev4
FormattingRules
FrontPage
Help
InterWiki
InterWikiName
InterWikiSandBox
K
MenuBar
PHP
PukiWiki
PukiWiki/1.4
PukiWiki/1.4/Manual
PukiWiki/1.4/Manual/Plugin
PukiWiki/1.4/Manual/Plugin/A-D
PukiWiki/1.4/Manual/Plugin/E-G
PukiWiki/1.4/Manual/Plugin/H-K
PukiWiki/1.4/Manual/Plugin/L-N
PukiWiki/1.4/Manual/Plugin/O-R
PukiWiki/1.4/Manual/Plugin/S-U
PukiWiki/1.4/Manual/Plugin/V-Z
RecentDeleted
SDL2_01
SandBox
WikiEngines
WikiName
WikiWikiWeb
YukiWiki
a21
a21_acl01
a21_bbs01
a21_challengers
a21_count
a21_edu01
a21_edu02
a21_edu03
a21_edu04
a21_edu05
a21_edu06
a21_edu07
a21_edu08
a21_edu09
a21_edu10
a21_edu11
a21_hlx000
a21_hlx001
a21_hlx001_1
a21_hlx001_2
a21_hlx001_3
a21_hlx002
a21_hlx002_1
a21_hlx003
a21_hlx003_1
a21_hlx004_1
a21_memo01
a21_opt
a21_opt02
a21_opt03
a21_p01
a21_special
a21_tl9a
a21_todo
a21_txt01
a21_txt01_10
a21_txt01_1a
a21_txt01_2
a21_txt01_2a
a21_txt01_2b
a21_txt01_3
a21_txt01_4
a21_txt01_5
a21_txt01_6
a21_txt01_6a
a21_txt01_7
a21_txt01_8
a21_txt01_8a
a21_txt01_9
a21_txt01_9a
a21_txt02
a21_txt02_10
a21_txt02_10a
a21_txt02_10b
a21_txt02_11
a21_txt02_11a
a21_txt02_12
a21_txt02_12a
a21_txt02_12b
a21_txt02_1a
a21_txt02_1b
a21_txt02_2
a21_txt02_2a
a21_txt02_3
a21_txt02_3a
a21_txt02_4
a21_txt02_4a
a21_txt02_5
a21_txt02_5a
a21_txt02_6
a21_txt02_6a
a21_txt02_6b
a21_txt02_6b_rev0
a21_txt02_6x
a21_txt02_7
a21_txt02_7a
a21_txt02_8
a21_txt02_8a
a21_txt02_9
a21_txt02_9a
a22_acl2_01
a22_acl2_02
a22_edu12
a22_intro01
a22_intro02
a22_intro03
a22_memman01
a22_memman02
a22_memman03
a22_memman04
a22_memman05
a22_memman06
a22_memman07
a22_memo01
a22_mingw_debug
a22_txt03
a22_txt03_1a
a22_txt03_1b
a22_txt03_2
a22_txt03_2a
a22_ufcs01
a23_bbs
a23_ec001
a23_ec002
a23_intro00
a23_intro000
a23_intro01
a23_intro02
a23_intro03
a23_intro04
a23_intro05
a23_intro06
a23_intro07
a23_intro08
a23_intro09
a23_intro10
a23_intro10wk1
a23_intro10wk2
a23_intro10wk3
a23_intro11
a23_intro12
a23_intro13
a23_intro13wk1
a23_intro14
a23_intro15
a23_intro16
a23_intro90
a23_intro91
a23_neopixel1
a23_os01
a23_useSelfMade
a23_usm001
a23_usm002
a23_usm003
a23_usm004
a23_usm005
a23_usm006
a23_usm007
a23_usm008
a23_usm009
aclib00
aclib01
aclib02
aclib03
aclib04
aclib05
aclib06
aclib07
aclib08
aclib09
aclib10
aclib11
aclib12
aclib13
aclib14
aclib15
aclib16
aclib17
aclib18
aclib19
aclib20
aclib21
aclib22
aclib23
aclib24
aclib25
aclib_bbs
arm64_01
avm0001
edu0001
edu0002
edu0003
esb02b_hrb
esb_dbg
esbasic0001
esbasic0002
esbasic0003
esbasic0004
esbasic0005
esbasic0006
esbasic0007
esbasic0008
esbasic0009
esbasic0010
esbasic0011
esbasic0012
esbasic0013
esbasic0014
esbasic0015
esbasic0016
esbasic0017
esbasic02a
esc0001
escm0001
essen_hist
esvm0001
esvm0002
esvm0003
esvm0004
esvm0005
esvm0006
esvm_i0
hh4a
idea0001
idea0002
idea0003
impressions
jck_0000
jck_0001
kawai
kbcl0_0000
kbcl0_0001
kbcl0_0002
kbcl0_0003
kbcl0_0004
kbcl0_0005
kbcl0_0006
kbcl0_0007
kclib1_0000
kclib1_0001
kclib1_0002
kclib1_0003
kclib1_0004
kclib1_0005
kclib1_0006
kclib1_0007
kclib1_0008
kclib1_0009
kclib1_0010
kpap0001
members
memo0001
osask4g
osask4g_r2
p20200311a
p20200610a
p20200610b
p20200624a
p20200711a
p20200716a
page0001
page0002
page0003
page0004
page0005
page0006
page0007
page0008
page0009
page0010
page0011
page0012
page0013
page0014
page0015
page0016
page0017
page0018
page0019
page0020
page0021
page0022
page0023
populars
seccamp
seccamp2019
sechack
sechack2019
seclang01
sh3_2020
sh3_2020_kw
sh3_2020_nk
sh3_2021_kw
sh3_2021_nk
sh3_2022_kw
sh3_2023_kw
sh3_kw_hist
termux001
termux002
text0001
text0001a
text0002
text0002a
text0003
text0004
text0005
text0006
text0006a
text0007
text0008
text0010
text0011
text0012
text0013
text0014
text0015
text0016
text0017
text0018
text0019
text0020
text0021
tl1c
tl2c
tl3c
tl3d
* 「10日くらいでできる!プログラミング言語自作入門」の続編#1-1 -(by [[K]], 2021.04.05) ** (1) はじめに -このテキストは、「10日くらいでできる!プログラミング言語自作入門」([[a21_txt01]])の続編にあたります。ですからこの続編テキストのスタート地点は772行の[[HL-9a>a21_txt01_9a]]になります。 -このシリーズでは、言語に新規の命令を追加することは最小限に抑えて、主にJITコンパイラ化や普通のコンパイラへの改造がメインです。 -言語に独自の機能を加えていって言語を「進化」させていく話は、「a21_txt03」でやる予定です。そこでは言語がどうすれば便利になるかを考えていきます。 ---- -もくじ(HL-1から順番に読んでいくとわかるように書いています) |ページ名|名前|行数|.exeの大きさ|説明|速度のめやす1|速度のめやす2| |[ [[a21_txt01]] ]|HL-1~HL-9a|RIGHT:49行~772行|RIGHT:6.0KB~20.0KB|「10日くらいでできる!プログラミング言語自作入門」|RIGHT:1520倍~5.5倍|RIGHT:6.4倍| |||||||| |[[a21_txt02]]|HL-11|RIGHT:692行|RIGHT:14.5KB|x86のJITコンパイラ版1号(x64の人は[[a21_txt02_7]]へ進んでください)|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_1a]]|HL-11a|RIGHT:707行|RIGHT:15.0KB|簡単な演算もサポート|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_2]]|HL-12|RIGHT:745行|RIGHT:16.0KB|ループ速度の測定ができるところまで|RIGHT:5.3倍|RIGHT:計測不能| |[[a21_txt02_2a]]|HL-12a|RIGHT:766行|RIGHT:16.5KB|codedumpコマンドと、codeコマンドの追加|RIGHT:5.3倍|RIGHT:計測不能| |[[a21_txt02_3]]|HL-13|RIGHT:827行|RIGHT:21.0KB|配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)|RIGHT:5.3倍|RIGHT:2.0倍| |[[a21_txt02_3a]]|HL-13a|RIGHT:819行|RIGHT:21.0KB|配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)|RIGHT:5.3倍|RIGHT:2.0倍| |[[a21_txt02_4]]|HL-14|RIGHT:865行|RIGHT:21.5KB|レジスタ変数の導入(46行しか増えない簡単な改造だけど、結構な効果がある)|RIGHT:2.0倍|RIGHT:1.2倍| |[[a21_txt02_4a]]|HL-14a|RIGHT:906行|RIGHT:22.5KB|レジスタ変数のための最適化(さらに41行を追加してすごい速さに!)|RIGHT:''1.0倍''|RIGHT:''0.9倍''| |[[a21_txt02_5]]|HL-15|RIGHT:942行|RIGHT:23.0KB|無駄なメモリアクセスの削減|RIGHT:1.0倍|RIGHT:0.9倍| |[[a21_txt02_5a]]|HL-15a|RIGHT:1012行|RIGHT:23.5KB|即値指定命令への対応|RIGHT:1.0倍|RIGHT:0.9倍| |[[a21_txt02_6]]|HL-16|RIGHT:1065行|RIGHT:24.0KB|コンパイル時の定数計算|RIGHT:1.0倍|RIGHT:0.9倍| |[[a21_txt02_6a]]|HL-16a|RIGHT:1081行|RIGHT:24.5KB|変数参照回数の表示|RIGHT:1.0倍|RIGHT:0.9倍| |||||||| |[[a21_txt02_6b]]|HL-16b|RIGHT:1284行|RIGHT:28.5KB|(JITではない)「普通のコンパイラ」になるモードを追加(x86アセンブラを出力)|RIGHT:1.0倍|RIGHT:0.9倍| |||||||| |[[a21_txt02_7]]|HL-17|RIGHT:741行|RIGHT:25.0KB|x64に対応したJITコンパイラ第1号|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_7a]]|HL-17a|RIGHT:756行|RIGHT:26.0KB|簡単な演算もサポート|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_8]]|HL-18|RIGHT:795行|RIGHT:27.0KB|ループ速度の測定ができるところまで|RIGHT:4.2倍|RIGHT:計測不能| |[[a21_txt02_8a]]|HL-18a|RIGHT:816行|RIGHT:27.5KB|codedumpコマンドと、codeコマンドの追加|RIGHT:4.2倍|RIGHT:計測不能| |[[a21_txt02_9]]|HL-19|RIGHT:893行|RIGHT:35.5KB|配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)|RIGHT:4.2倍|RIGHT:1.8倍| |[[a21_txt02_9a]]|HL-19a|RIGHT:899行|RIGHT:36.0KB|配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)|RIGHT:4.2倍|RIGHT:1.8倍| |[[a21_txt02_10]]|HL-20|RIGHT:964行|RIGHT:36.0KB|レジスタ変数の導入(65行しか増えない簡単な改造だけど、結構な効果がある)|RIGHT:2.1倍|RIGHT:1.0倍| |[[a21_txt02_10a]]|HL-20a|RIGHT:1014行|RIGHT:37.0KB|レジスタ変数のための最適化(さらに50行を追加してすごい速さに!・・・なってない)|RIGHT:2.1倍|RIGHT:0.7倍| |[[a21_txt02_10b]]|HL-20b|RIGHT:1035行|RIGHT:37.5KB|アライン命令を追加して、HL-20aの成果がはっきり見えるようになった|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_11]]|HL-21|RIGHT:1070行|RIGHT:38.5KB|無駄なメモリアクセスの削減|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_11a]]|HL-21a|RIGHT:1151行|RIGHT:40.5KB|即値指定命令への対応|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_12]]|HL-22|RIGHT:1204行|RIGHT:41.0KB|コンパイル時の定数計算|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_12a]]|HL-22a|RIGHT:1223行|RIGHT:|変数参照回数の表示|RIGHT:|RIGHT:| |||||||| |[[a21_txt02_12b]]|HL-22b|RIGHT:|RIGHT:|(JITではない)「普通のコンパイラ」になるモードを追加(x64アセンブラを出力)|RIGHT:1.0倍|RIGHT:0.7倍| |||||||| |||||C言語ソースを出力して、トランスコンパイラにしてみる||| -速度のめやす --速度のめやす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]] *こめんと欄 #comment
タイムスタンプを変更しない
* 「10日くらいでできる!プログラミング言語自作入門」の続編#1-1 -(by [[K]], 2021.04.05) ** (1) はじめに -このテキストは、「10日くらいでできる!プログラミング言語自作入門」([[a21_txt01]])の続編にあたります。ですからこの続編テキストのスタート地点は772行の[[HL-9a>a21_txt01_9a]]になります。 -このシリーズでは、言語に新規の命令を追加することは最小限に抑えて、主にJITコンパイラ化や普通のコンパイラへの改造がメインです。 -言語に独自の機能を加えていって言語を「進化」させていく話は、「a21_txt03」でやる予定です。そこでは言語がどうすれば便利になるかを考えていきます。 ---- -もくじ(HL-1から順番に読んでいくとわかるように書いています) |ページ名|名前|行数|.exeの大きさ|説明|速度のめやす1|速度のめやす2| |[ [[a21_txt01]] ]|HL-1~HL-9a|RIGHT:49行~772行|RIGHT:6.0KB~20.0KB|「10日くらいでできる!プログラミング言語自作入門」|RIGHT:1520倍~5.5倍|RIGHT:6.4倍| |||||||| |[[a21_txt02]]|HL-11|RIGHT:692行|RIGHT:14.5KB|x86のJITコンパイラ版1号(x64の人は[[a21_txt02_7]]へ進んでください)|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_1a]]|HL-11a|RIGHT:707行|RIGHT:15.0KB|簡単な演算もサポート|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_2]]|HL-12|RIGHT:745行|RIGHT:16.0KB|ループ速度の測定ができるところまで|RIGHT:5.3倍|RIGHT:計測不能| |[[a21_txt02_2a]]|HL-12a|RIGHT:766行|RIGHT:16.5KB|codedumpコマンドと、codeコマンドの追加|RIGHT:5.3倍|RIGHT:計測不能| |[[a21_txt02_3]]|HL-13|RIGHT:827行|RIGHT:21.0KB|配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)|RIGHT:5.3倍|RIGHT:2.0倍| |[[a21_txt02_3a]]|HL-13a|RIGHT:819行|RIGHT:21.0KB|配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)|RIGHT:5.3倍|RIGHT:2.0倍| |[[a21_txt02_4]]|HL-14|RIGHT:865行|RIGHT:21.5KB|レジスタ変数の導入(46行しか増えない簡単な改造だけど、結構な効果がある)|RIGHT:2.0倍|RIGHT:1.2倍| |[[a21_txt02_4a]]|HL-14a|RIGHT:906行|RIGHT:22.5KB|レジスタ変数のための最適化(さらに41行を追加してすごい速さに!)|RIGHT:''1.0倍''|RIGHT:''0.9倍''| |[[a21_txt02_5]]|HL-15|RIGHT:942行|RIGHT:23.0KB|無駄なメモリアクセスの削減|RIGHT:1.0倍|RIGHT:0.9倍| |[[a21_txt02_5a]]|HL-15a|RIGHT:1012行|RIGHT:23.5KB|即値指定命令への対応|RIGHT:1.0倍|RIGHT:0.9倍| |[[a21_txt02_6]]|HL-16|RIGHT:1065行|RIGHT:24.0KB|コンパイル時の定数計算|RIGHT:1.0倍|RIGHT:0.9倍| |[[a21_txt02_6a]]|HL-16a|RIGHT:1081行|RIGHT:24.5KB|変数参照回数の表示|RIGHT:1.0倍|RIGHT:0.9倍| |||||||| |[[a21_txt02_6b]]|HL-16b|RIGHT:1284行|RIGHT:28.5KB|(JITではない)「普通のコンパイラ」になるモードを追加(x86アセンブラを出力)|RIGHT:1.0倍|RIGHT:0.9倍| |||||||| |[[a21_txt02_7]]|HL-17|RIGHT:741行|RIGHT:25.0KB|x64に対応したJITコンパイラ第1号|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_7a]]|HL-17a|RIGHT:756行|RIGHT:26.0KB|簡単な演算もサポート|RIGHT:計測不能|RIGHT:計測不能| |[[a21_txt02_8]]|HL-18|RIGHT:795行|RIGHT:27.0KB|ループ速度の測定ができるところまで|RIGHT:4.2倍|RIGHT:計測不能| |[[a21_txt02_8a]]|HL-18a|RIGHT:816行|RIGHT:27.5KB|codedumpコマンドと、codeコマンドの追加|RIGHT:4.2倍|RIGHT:計測不能| |[[a21_txt02_9]]|HL-19|RIGHT:893行|RIGHT:35.5KB|配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)|RIGHT:4.2倍|RIGHT:1.8倍| |[[a21_txt02_9a]]|HL-19a|RIGHT:899行|RIGHT:36.0KB|配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)|RIGHT:4.2倍|RIGHT:1.8倍| |[[a21_txt02_10]]|HL-20|RIGHT:964行|RIGHT:36.0KB|レジスタ変数の導入(65行しか増えない簡単な改造だけど、結構な効果がある)|RIGHT:2.1倍|RIGHT:1.0倍| |[[a21_txt02_10a]]|HL-20a|RIGHT:1014行|RIGHT:37.0KB|レジスタ変数のための最適化(さらに50行を追加してすごい速さに!・・・なってない)|RIGHT:2.1倍|RIGHT:0.7倍| |[[a21_txt02_10b]]|HL-20b|RIGHT:1035行|RIGHT:37.5KB|アライン命令を追加して、HL-20aの成果がはっきり見えるようになった|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_11]]|HL-21|RIGHT:1070行|RIGHT:38.5KB|無駄なメモリアクセスの削減|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_11a]]|HL-21a|RIGHT:1151行|RIGHT:40.5KB|即値指定命令への対応|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_12]]|HL-22|RIGHT:1204行|RIGHT:41.0KB|コンパイル時の定数計算|RIGHT:1.0倍|RIGHT:0.7倍| |[[a21_txt02_12a]]|HL-22a|RIGHT:1223行|RIGHT:|変数参照回数の表示|RIGHT:|RIGHT:| |||||||| |[[a21_txt02_12b]]|HL-22b|RIGHT:|RIGHT:|(JITではない)「普通のコンパイラ」になるモードを追加(x64アセンブラを出力)|RIGHT:1.0倍|RIGHT:0.7倍| |||||||| |||||C言語ソースを出力して、トランスコンパイラにしてみる||| -速度のめやす --速度のめやす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]] *こめんと欄 #comment
テキスト整形のルールを表示する