a21_hlx001_2
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* 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...
if (次の命令がCmpEq) { rに書いてある命令の比較条...
pのSetCc命令をNopにしてしまう
pの次のCmpEq/CmpNe命令もNopにしてしまう
}
}
--[例1]
if ((a > 1) != 0) goto label; // HLX-001が内部的に生成す...
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に出会ってしまったら、その先でどうなるかは分か...
---私としては、そこを頑張らせるよりは、「a = void;」みた...
~
-''[5-2] 「定数畳み込み」と「定数伝播」をやります。''
--AEs_optimizeSub4() [138行] のアルゴリズム:
最適化の範囲: p0 ~ p1
変数の値を記憶するテーブルを初期化
for (p = p0; p < p1; p = 次の命令) {
定数代入命令があったら、テーブルに変数の値を登録
その他、結果が定数になるような演算があれば、それも結...
もし定数のみの演算ではなく結果が定数じゃないかもしれ...
命令の中で変数が使われていたら、その変数がテーブルに...
ラベル宣言文に当たったら、テーブルをいったん全クリア...
}
--[Q] この処理のどこが行数を食っていますか?(全体で138行...
---[A] 加算で0を足している部分があれば、それは単純代入に...
~
-''[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を見つけたら、スタック...
終わったら、スタックを見に行って、もしラベルが登録されて...
同じラベルを二度見に行かないようにフラグで管理。
こうすることで、どうやっても到達しないラベルにはフラグが...
その上で、Jmpの後でラベル宣言命令までの間は、どうやって...
--宣言したけど使ってないラベルを消すのは結構有効です。上...
~
-''[5-6] 分岐先が次の命令を指している場合、その分岐命令は...
--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; とかそういうやつです。...
--[Q] 「使われていない」ってどうやって判定していますか?
---[A] プログラムでは AEs_isVoid() で判定しています。これ...
--[Q] なぜ最初に命令の頭出しまでして逆順に処理しようとす...
---[A] 逆順にしなくても最適化ができるのはその通りです。
---しかし、 b = a + 1; c = b + 2; d = c + 3; (そしてb, c...
~
-''[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;
このあと、最適化によって、定数畳み込みや定数伝播がおきて...
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...
if (次の命令がCmpEq) { rに書いてある命令の比較条...
pのSetCc命令をNopにしてしまう
pの次のCmpEq/CmpNe命令もNopにしてしまう
}
}
--[例1]
if ((a > 1) != 0) goto label; // HLX-001が内部的に生成す...
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に出会ってしまったら、その先でどうなるかは分か...
---私としては、そこを頑張らせるよりは、「a = void;」みた...
~
-''[5-2] 「定数畳み込み」と「定数伝播」をやります。''
--AEs_optimizeSub4() [138行] のアルゴリズム:
最適化の範囲: p0 ~ p1
変数の値を記憶するテーブルを初期化
for (p = p0; p < p1; p = 次の命令) {
定数代入命令があったら、テーブルに変数の値を登録
その他、結果が定数になるような演算があれば、それも結...
もし定数のみの演算ではなく結果が定数じゃないかもしれ...
命令の中で変数が使われていたら、その変数がテーブルに...
ラベル宣言文に当たったら、テーブルをいったん全クリア...
}
--[Q] この処理のどこが行数を食っていますか?(全体で138行...
---[A] 加算で0を足している部分があれば、それは単純代入に...
~
-''[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を見つけたら、スタック...
終わったら、スタックを見に行って、もしラベルが登録されて...
同じラベルを二度見に行かないようにフラグで管理。
こうすることで、どうやっても到達しないラベルにはフラグが...
その上で、Jmpの後でラベル宣言命令までの間は、どうやって...
--宣言したけど使ってないラベルを消すのは結構有効です。上...
~
-''[5-6] 分岐先が次の命令を指している場合、その分岐命令は...
--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; とかそういうやつです。...
--[Q] 「使われていない」ってどうやって判定していますか?
---[A] プログラムでは AEs_isVoid() で判定しています。これ...
--[Q] なぜ最初に命令の頭出しまでして逆順に処理しようとす...
---[A] 逆順にしなくても最適化ができるのはその通りです。
---しかし、 b = a + 1; c = b + 2; d = c + 3; (そしてb, c...
~
-''[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;
このあと、最適化によって、定数畳み込みや定数伝播がおきて...
print 55;
だけになります。
* こめんと欄
#comment
ページ名: