a21_hlx001_2
の編集
https://essen.osask.jp/?a21_hlx001_2
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
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
a24_memo01
a24_osc20240310
a24_osc20241026
a24_raspberrypi01
a24_useSelfMade
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_2024_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
* HLX-001 の補足ページ#2 -(by [[K]], 2021.08.23) ** (8) HLX-001の最適化アルゴリズム -HLX-001は、いろいろな最適化を比較的コンパクトに実現できていると思うのですが、そのアルゴリズムの詳細や、なぜそういう仕様にしたのかの説明を書いておけば、誰かの参考になるかもしれないと思ったので書いておきます。 --HLX-001そのものについてはこちら → [[a21_hlx001]] ~ -''[5-1] 「比較演算子の結果を0かどうか比較する」という処理を一度の比較にまとめます。'' --AEs_optimizeSub0() [24行] のアルゴリズム: 最適化の範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { if (pの命令がCmpEq~CmpRnz) { r = p; (この命令の場所を覚えておく) } if (pの命令がSetCc && 次の命令がCmpEqかCmpNeで定数0との比較 && SetCcの結果をその先で一切使わない) { if (次の命令がCmpEq) { rに書いてある命令の比較条件を反転させる } pのSetCc命令をNopにしてしまう pの次のCmpEq/CmpNe命令もNopにしてしまう } } --[例1] if ((a > 1) != 0) goto label; // HLX-001が内部的に生成する共通中間コードをC言語風に書いたもの 1: CmpGt(a, 1); // (最適前)上記を共通中間コードで表したもの 2: SetCc(tmp); // この2行目と3行目は最適化によって消される 3: CmpNe(tmp, 0); 4: Jcc(label); 1: CmpGt(a, 1); // (最適化後)このようにうまくいく 2: Jcc(label); --[Q] 「SetCcの結果をその先で一切使わない」ってどうやって判定していますか? ---[A] プログラムでは AEs_isVoid() で判定しています。 ---やっていることは単純で、先の命令を一つずつ順番に見ていって、もしその変数が何らかの命令の引数に使われていれば、それは「使われている」と判断してそこでおしまいです。 ---もしその変数に対して何らかの値が上書きされるか、OpVoid命令で無効化されたら、それは「使われていない」と判断しておしまいです。 ---JmpやJccに出会ってしまったら、その先でどうなるかは分からないので、「使われている」ということにしておしまいです。・・・いやJmpであればさらに追跡も可能そうではありますが、それで最適化ルーチンが無限ループに入ったらいやだなとか、それを回避するためにどの命令がチェック済みかを管理するのも手間だなと思って、やっていません。 ---私としては、そこを頑張らせるよりは、「a = void;」みたいな命令をHLX-001にサポートさせて、プログラム内で「この変数はこの先で値を使わないよ」って明示できるようにしたいです。そうすればコンパイラが追跡を頑張らなくても、同等の最適化結果が得られるようになるので。 ~ -''[5-2] 「定数畳み込み」と「定数伝播」をやります。'' --AEs_optimizeSub4() [138行] のアルゴリズム: 最適化の範囲: p0 ~ p1 変数の値を記憶するテーブルを初期化 for (p = p0; p < p1; p = 次の命令) { 定数代入命令があったら、テーブルに変数の値を登録 その他、結果が定数になるような演算があれば、それも結果をテーブルに登録 もし定数のみの演算ではなく結果が定数じゃないかもしれないと思われるときは、テーブルから変数に関する行を削除 命令の中で変数が使われていたら、その変数がテーブルに登録されていないかを確認し、登録されていれば定数値に置換する ラベル宣言文に当たったら、テーブルをいったん全クリアする(もうどの変数に定数値がはいっているか分からないので) } --[Q] この処理のどこが行数を食っていますか?(全体で138行もあるので) ---[A] 加算で0を足している部分があれば、それは単純代入にできるので置換する、「b = a - a;」のように減算で同じものの引き算になっていたら、答えは定数のゼロに決まっているのでそのようにするなど、そういうパターンの網羅にかなりの行数が費やされています。 ~ -''[5-3] 分岐命令で分岐した先が無条件分岐命令だったら、最初からそこに行くように分岐先を修正します。'' --AEs_optimizeSub2() [87行] のアルゴリズム: 最適化の範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { if (pの命令がJmpかJcc) { 分岐先の命令を見る(NOPなどは読み飛ばす) もしJmpだったら、分岐先を修正 } } ~ -''[5-4] 宣言したけど使われていないラベルを除去します。'' -''[5-5] デッドコード(一度も実行されることのないコード)があればそれをすべて消します。'' --AEs_optimizeSub2() [87行] のアルゴリズム: 最適化範囲: p0 ~ p1 関数の先頭から見て行って、Jcc/Jmpを見つけたら、スタックにそのラベルを登録。RetやJmpを見つけたら、そこで終わり。 終わったら、スタックを見に行って、もしラベルが登録されていればそこからまた見て行ってJcc/Jmpが来たらスタックに登録。・・・これを繰り返す。 同じラベルを二度見に行かないようにフラグで管理。 こうすることで、どうやっても到達しないラベルにはフラグが付いていないことになるので、フラグのないラベルは消す。 その上で、Jmpの後でラベル宣言命令までの間は、どうやっても到達しないコードになるので、これを削る。 --宣言したけど使ってないラベルを消すのは結構有効です。上記の[5-2]や以下の[5-7]ではラベル宣言文があるとそこで最適化が止まってしまうからです。 ~ -''[5-6] 分岐先が次の命令を指している場合、その分岐命令はNOPと同じなので除去します。'' --AEs_optimizeSub2() [87行] のアルゴリズム: 最適化範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { if (pの命令がJmpかJcc) { if (pの次の命令がラベル宣言 && そのラベルはpの分岐先と同じ) { pの分岐命令を消す } } } --こうして無駄な分岐命令が消えると、ラベルを参照する回数が減って、ラベル宣言文が消える場合も出てきて、さらに最適化が進むようになることもあります。 ~ -''[5-7] 演算した結果がその先で一切利用されないことが確実な場合、その演算をする必要はないので、削除してしまいます。'' --AEs_optimizeSub3() [34行] のアルゴリズム: 最適化範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { 命令の開始位置を配列t[i]に記憶させる(以下で、命令を逆順にたどりたいので) } for (i--; i >= 0; i--) { p = t[i]; if (pの演算結果が次のCpyでしか使われていない) { Cpyの代入先へ直接代入するようにする そしてCpyは消す [註] ここは以下のようなコードを最適化する tmp = a + b; c = tmp; → c = a + b; } if (pの演算結果がその先で使われていない) { pの命令を消す } } --[Q] Cpy命令って何ですか? ---[A] ただの代入命令です。 a = b; とかそういうやつです。 Cpy(a, b); になります。 --[Q] 「使われていない」ってどうやって判定していますか? ---[A] プログラムでは AEs_isVoid() で判定しています。これは上記の[5-1]で紹介したものと同じです。 --[Q] なぜ最初に命令の頭出しまでして逆順に処理しようとするのですか?アルゴリズムを見ていると逆順にしなくても最適化できそうですが。 ---[A] 逆順にしなくても最適化ができるのはその通りです。 ---しかし、 b = a + 1; c = b + 2; d = c + 3; (そしてb, c, dはこの先で使われていない)、みたいな感じで命令が並んでいるとき、このアルゴリズムがまず最初に最適化で消せるのは「d = c + 3;」です。cやbは消せません。直後で使われているからです。そして「d = c + 3;」が消えると、次は「c = b + 2;」が消せると気づきます。こうして後ろから消えていくことになるので、AEs_optimizeSub3()を何度も呼び出しなおさなくても済むように、逆順で最適化の処理をしたかったのです。 ~ -''[5-8] HLX-001ではfor文の前に unroll(11) みたいなプリフィクスを付けるとループアンロールができます。'' --HLX-001におけるfor文のアンロールのやり方は次の通りです。 --アンロール回数だけひたすらに展開し、最後にfor文を付けておく。 --[例1] unroll(11) for (s = i = 0; i <= 10; i++) { s = s + i; } print s; // アンロール結果: s = i = 0; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; lop: s = s + 1; i++; if (i <= 10) goto lop; brk: print s; このあと、最適化によって、定数畳み込みや定数伝播がおきて、if文が消えたりただのgotoになったりして、使わないラベルや直後への分岐も消えて、 print 55; だけになります。 * こめんと欄 #comment
タイムスタンプを変更しない
* HLX-001 の補足ページ#2 -(by [[K]], 2021.08.23) ** (8) HLX-001の最適化アルゴリズム -HLX-001は、いろいろな最適化を比較的コンパクトに実現できていると思うのですが、そのアルゴリズムの詳細や、なぜそういう仕様にしたのかの説明を書いておけば、誰かの参考になるかもしれないと思ったので書いておきます。 --HLX-001そのものについてはこちら → [[a21_hlx001]] ~ -''[5-1] 「比較演算子の結果を0かどうか比較する」という処理を一度の比較にまとめます。'' --AEs_optimizeSub0() [24行] のアルゴリズム: 最適化の範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { if (pの命令がCmpEq~CmpRnz) { r = p; (この命令の場所を覚えておく) } if (pの命令がSetCc && 次の命令がCmpEqかCmpNeで定数0との比較 && SetCcの結果をその先で一切使わない) { if (次の命令がCmpEq) { rに書いてある命令の比較条件を反転させる } pのSetCc命令をNopにしてしまう pの次のCmpEq/CmpNe命令もNopにしてしまう } } --[例1] if ((a > 1) != 0) goto label; // HLX-001が内部的に生成する共通中間コードをC言語風に書いたもの 1: CmpGt(a, 1); // (最適前)上記を共通中間コードで表したもの 2: SetCc(tmp); // この2行目と3行目は最適化によって消される 3: CmpNe(tmp, 0); 4: Jcc(label); 1: CmpGt(a, 1); // (最適化後)このようにうまくいく 2: Jcc(label); --[Q] 「SetCcの結果をその先で一切使わない」ってどうやって判定していますか? ---[A] プログラムでは AEs_isVoid() で判定しています。 ---やっていることは単純で、先の命令を一つずつ順番に見ていって、もしその変数が何らかの命令の引数に使われていれば、それは「使われている」と判断してそこでおしまいです。 ---もしその変数に対して何らかの値が上書きされるか、OpVoid命令で無効化されたら、それは「使われていない」と判断しておしまいです。 ---JmpやJccに出会ってしまったら、その先でどうなるかは分からないので、「使われている」ということにしておしまいです。・・・いやJmpであればさらに追跡も可能そうではありますが、それで最適化ルーチンが無限ループに入ったらいやだなとか、それを回避するためにどの命令がチェック済みかを管理するのも手間だなと思って、やっていません。 ---私としては、そこを頑張らせるよりは、「a = void;」みたいな命令をHLX-001にサポートさせて、プログラム内で「この変数はこの先で値を使わないよ」って明示できるようにしたいです。そうすればコンパイラが追跡を頑張らなくても、同等の最適化結果が得られるようになるので。 ~ -''[5-2] 「定数畳み込み」と「定数伝播」をやります。'' --AEs_optimizeSub4() [138行] のアルゴリズム: 最適化の範囲: p0 ~ p1 変数の値を記憶するテーブルを初期化 for (p = p0; p < p1; p = 次の命令) { 定数代入命令があったら、テーブルに変数の値を登録 その他、結果が定数になるような演算があれば、それも結果をテーブルに登録 もし定数のみの演算ではなく結果が定数じゃないかもしれないと思われるときは、テーブルから変数に関する行を削除 命令の中で変数が使われていたら、その変数がテーブルに登録されていないかを確認し、登録されていれば定数値に置換する ラベル宣言文に当たったら、テーブルをいったん全クリアする(もうどの変数に定数値がはいっているか分からないので) } --[Q] この処理のどこが行数を食っていますか?(全体で138行もあるので) ---[A] 加算で0を足している部分があれば、それは単純代入にできるので置換する、「b = a - a;」のように減算で同じものの引き算になっていたら、答えは定数のゼロに決まっているのでそのようにするなど、そういうパターンの網羅にかなりの行数が費やされています。 ~ -''[5-3] 分岐命令で分岐した先が無条件分岐命令だったら、最初からそこに行くように分岐先を修正します。'' --AEs_optimizeSub2() [87行] のアルゴリズム: 最適化の範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { if (pの命令がJmpかJcc) { 分岐先の命令を見る(NOPなどは読み飛ばす) もしJmpだったら、分岐先を修正 } } ~ -''[5-4] 宣言したけど使われていないラベルを除去します。'' -''[5-5] デッドコード(一度も実行されることのないコード)があればそれをすべて消します。'' --AEs_optimizeSub2() [87行] のアルゴリズム: 最適化範囲: p0 ~ p1 関数の先頭から見て行って、Jcc/Jmpを見つけたら、スタックにそのラベルを登録。RetやJmpを見つけたら、そこで終わり。 終わったら、スタックを見に行って、もしラベルが登録されていればそこからまた見て行ってJcc/Jmpが来たらスタックに登録。・・・これを繰り返す。 同じラベルを二度見に行かないようにフラグで管理。 こうすることで、どうやっても到達しないラベルにはフラグが付いていないことになるので、フラグのないラベルは消す。 その上で、Jmpの後でラベル宣言命令までの間は、どうやっても到達しないコードになるので、これを削る。 --宣言したけど使ってないラベルを消すのは結構有効です。上記の[5-2]や以下の[5-7]ではラベル宣言文があるとそこで最適化が止まってしまうからです。 ~ -''[5-6] 分岐先が次の命令を指している場合、その分岐命令はNOPと同じなので除去します。'' --AEs_optimizeSub2() [87行] のアルゴリズム: 最適化範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { if (pの命令がJmpかJcc) { if (pの次の命令がラベル宣言 && そのラベルはpの分岐先と同じ) { pの分岐命令を消す } } } --こうして無駄な分岐命令が消えると、ラベルを参照する回数が減って、ラベル宣言文が消える場合も出てきて、さらに最適化が進むようになることもあります。 ~ -''[5-7] 演算した結果がその先で一切利用されないことが確実な場合、その演算をする必要はないので、削除してしまいます。'' --AEs_optimizeSub3() [34行] のアルゴリズム: 最適化範囲: p0 ~ p1 for (p = p0; p < p1; p = 次の命令) { 命令の開始位置を配列t[i]に記憶させる(以下で、命令を逆順にたどりたいので) } for (i--; i >= 0; i--) { p = t[i]; if (pの演算結果が次のCpyでしか使われていない) { Cpyの代入先へ直接代入するようにする そしてCpyは消す [註] ここは以下のようなコードを最適化する tmp = a + b; c = tmp; → c = a + b; } if (pの演算結果がその先で使われていない) { pの命令を消す } } --[Q] Cpy命令って何ですか? ---[A] ただの代入命令です。 a = b; とかそういうやつです。 Cpy(a, b); になります。 --[Q] 「使われていない」ってどうやって判定していますか? ---[A] プログラムでは AEs_isVoid() で判定しています。これは上記の[5-1]で紹介したものと同じです。 --[Q] なぜ最初に命令の頭出しまでして逆順に処理しようとするのですか?アルゴリズムを見ていると逆順にしなくても最適化できそうですが。 ---[A] 逆順にしなくても最適化ができるのはその通りです。 ---しかし、 b = a + 1; c = b + 2; d = c + 3; (そしてb, c, dはこの先で使われていない)、みたいな感じで命令が並んでいるとき、このアルゴリズムがまず最初に最適化で消せるのは「d = c + 3;」です。cやbは消せません。直後で使われているからです。そして「d = c + 3;」が消えると、次は「c = b + 2;」が消せると気づきます。こうして後ろから消えていくことになるので、AEs_optimizeSub3()を何度も呼び出しなおさなくても済むように、逆順で最適化の処理をしたかったのです。 ~ -''[5-8] HLX-001ではfor文の前に unroll(11) みたいなプリフィクスを付けるとループアンロールができます。'' --HLX-001におけるfor文のアンロールのやり方は次の通りです。 --アンロール回数だけひたすらに展開し、最後にfor文を付けておく。 --[例1] unroll(11) for (s = i = 0; i <= 10; i++) { s = s + i; } print s; // アンロール結果: s = i = 0; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; s = s + i; i++; if (i > 10) goto brk; lop: s = s + 1; i++; if (i <= 10) goto lop; brk: print s; このあと、最適化によって、定数畳み込みや定数伝播がおきて、if文が消えたりただのgotoになったりして、使わないラベルや直後への分岐も消えて、 print 55; だけになります。 * こめんと欄 #comment
テキスト整形のルールを表示する