Geekly Articles each Day

コンパイル。 8：最適化

快適な滞在の後、j-scriptのコンパイラを作成し続けます。
以前の投稿で、 レジスタ割り当ての上限から取られたヒューリスティックを実装し、同時にコードの最適化を開始しました。 そしてその前に、読者は割り当ての実装にバグを発見しました 。

さらに投稿：

  1. バグ修正
  2. コピーのクリーニング
  3. どうしたの？
  4. 折りたたみ定数
  5. 実装

バグ修正


事実、私たちはチートすることを決めたので、初めて変数に値を割り当てるとき、実際にコピーするのではなく、変数の格納場所として中間値を持つレジスタを宣言するだけです。
ID '=' EXPR { $$ = $3 ;
if (vars[ $1 ])
emit(command::add, vars[ $1 ], $3 , 0 );
else
vars[ $1 ] = $3 ; // new var
}

次に、タイプa=2;操作をコンパイルするときa=2; 1つのMOV R1, 2コマンドMOV R1, 2 （畳み込み2から）を取得しMOV R1, 2 vars["a"]=R1 （割り当て畳み込みから）を覚えています。
すべてが真実で、シンプルで自然です。

この問題は、割り当ての右側で、中間値ではなく、長寿命のもの（たとえば、別の変数）が使用されたときに発生しました。
 a = 2;
 b = a;

割り当ての2回目の畳み込みでは、新しいコードは生成されませんvars["b"]=R1覚えておいてください
両方の変数は同じレジスターにあり、そのうちの1つが変更されると、2番目の変数も変更されます。

解決策は表面にあります。新しい変数ごとに新しいレジスタを開始します。
ID '=' EXPR { $$ = $3 ;
if (!vars[ $1 ]) vars[ $1 ] = newreg();
emit(command::add, vars[ $1 ], $3 , 0 );
}

次に、 a=2;からa=2; いくつかのチームを取得する
 MOV R1、2
 R2、R1、0を追加
vars["a"]=R2を覚えておいてください
b = a;続く場合b = a; -その後、 MOV R3, R2, 0 vars["b"]=R3がコードに追加されます

言い換えると、生成されたコードにはレジスタからレジスタへの余分なコピーがたくさんあり、レジスタの目的はさらに遅くなります-使用されるレジスタの数が増えているためです。
コピーが不要な場合（たとえば、割り当ての右側の変数が将来変更されない場合）を見つけ、コピーを使用するコマンドを修正して、オリジナルを使用するようにします。

コピーのクリーニング


コピーの削除は、シリーズの最初の投稿から約束した単純な最適化の1つです。 レジスタ割り当て中に実行される最適化と同様に、データフロー分析はクリーニングに便利です。 DFAの以前の2つのアプリケーション（ライブレジスタの検出に戻って、保存されたレジスタの検索に進む）との重要な違いは、各ポイントで1セットのレジスタではなく、すべてのレジスタを同じセットに分割することです。 これは、前述の2つよりも一般的なDFAのケースとして見ることができます。 （以前は、レジスタは常に「含まれる」と「除外される」の2つのセットに分けられていました。）

レジスタをどのように分割しますか？最終的な分割を受け取った後、コピーの代わりにオリジナルを使用できる場所が表示されますRA代わりに、 RA使用されるすべてのチームで一緒にいる場合はRBを使用できます。

そしてもう1つ微妙な点は、チームからチームへの移行中にセットを構築せず、DFAを開始する前にセットを切り捨てる（すべての着信セットを交差する）ため、セットを空ではなく包括的なセットに初期化する必要があることです-そして、アルゴリズムが機能するため、セットが切り捨てられます必要です。 お金を使わず、すべての既存のレジスタのセットをすべてのチームに保持しないために、このような包括的なセットを指す「欠落しているイテレータ」を考慮することに同意します。

便宜上、パーティションで必要な3つの操作をクラスにフォーマットします。 パーティションには、レジスタが分割されるセットのリスト（最初にレジスタがすべて一緒になっている「グローバル」セットを除く）と、各レジスタ（「グローバル」セットにあるものを除く）が配置されているセットの反復子が格納されます。 。

ツリーstd::setにいくつかの奇妙な問題があったので、似たようなインターフェースを持ちながら、内部にstd::bitset持つbit::setコンテナーを自分で作成しました。 テンプレートパラメータにより、セット内の最大キー値を取得します。
同時に、 bit::setは、セット（ &= 、 |= ）の標準操作が含まれます。

typedef bit::set<regnum, 255 > regset;

class regPartition {
typedef std::list<regset> regsets;
regsets sets;
std::map<regnum, regsets::iterator> byreg;
// : ""

public :
// :
bool add(regnum copy, regnum orig) {
if (byreg.count(copy)) {
if (byreg[copy]==byreg[orig]) //
return false ;
byreg[copy]->erase(copy);
// ?
if (!byreg[copy]->size())
sets.erase(byreg[copy]);
}
assert(byreg.count(orig));
byreg[copy] = byreg[orig];
byreg[copy]->insert(copy);
return true ;
}

void remove(regnum r) {
if (byreg.count(‌r)) {
if (byreg[r]->size()== 1 ) return ; //
byreg[r]->erase(‌r);
}
byreg[r] = sets.insert(sets.end(), regset());
byreg[r]->insert(‌r);
}

// :
bool isect( /* const */ regPartition& p, const command& self) {
bool changed = false ;
// , p
foreach(i, byreg) {
regnum r = i->first;
// split by p.byreg[r]
regsets::iterator withR = i->second,
withoutR = sets.insert(sets.end(), regset());
foreach2(j, (*withR), next)
// , -- mov :
//
if (!(self.opcode==command::add && !self.src2 &&
((self.src1==r && self.dest==*j)||(self.dest==r && self.src1==*j)))
&&((!p.byreg.count(‌r) && p.byreg.count(*j)) || // R in global, J isn't
(p.byreg.count(‌r) && !p.byreg[r]->count(*j)))) { // R not in global
withR->erase(*j);
withoutR->insert(*j);
byreg[*j] = withoutR;
}
if (!withoutR->size()) //
sets.erase(withoutR);
else //
changed = true ;
}
// , this, p
foreach(i, p.sets) {
regset inP;
foreach(j, (*i))
if (!byreg.count(*j)) inP.insert(*j);
if (inP.size()) {
regsets::iterator newSet = sets.insert(sets.end(), inP);
foreach(j, inP) byreg[*j] = newSet;
changed = true ;
}
}
return changed;
}

// : r ( )
void apply(regnum r, regset& global) {
if (!r) return ; // may not be replaced
assert(byreg.count(‌r));
if (!global.size()) // uninitialized set
global = *byreg[r];
else // initialized; intersect
global &= *byreg[r];
}
}

struct commandn 、新しいフィールドregPartition copies;追加しregPartition copies;
次に、既製の操作を使用して、通常の方法でDFAを実装します。
void copies() {
// )
bool changed = false ;
foreach(i, pcode) {
i->copies = regPartition();
// rule 2
if (writesdest(i)) {
i->copies.remove(i->cmd.dest);
changed = true ;
}
}
while (changed) {
changed = false ;
foreach2(i, pcode, next) {
// rule 1
if (i->cmd.opcode==command::add && !i->cmd.src2)
changed |= i->copies.add(i->cmd.dest, i->cmd.src1);
// rule 3 (next command)
if (hasnext(i))
changed |= next->copies.isect(i->copies, next->cmd);
// rule 3 (jmp target)
if (i->cmd.opcode==command::jz)
changed |= i->tgt->copies.isect(i->copies, i->tgt->cmd);
}
}
// )
std::vector<regset> copies(lastreg+ 1 );
foreach(i, pcode) {
if (readsdest(i))
i->copies.apply(i->cmd.dest, copies[i->cmd.dest]);
if (has2src(i)) {
i->copies.apply(i->cmd.src1, copies[i->cmd.src1]);
i->copies.apply(i->cmd.src2, copies[i->cmd.src2]);
}
}
// )
for (regnum r= 1 ; r<=lastreg; r++) {
copies[r].erase(‌r);
if (copies[r].size()) { // ?
regnum s = *(copies[r].begin()); // r s
foreach(i, pcode) { //
if (i->cmd.dest==r)
i->cmd.dest = s;
if (has2src(i)) {
if (i->cmd.src1==r) i->cmd.src1 = s;
if (i->cmd.src2==r) i->cmd.src2 = s;
}
if (i->cmd.opcode==command::add && i->cmd.src1==i->cmd.dest && !i->cmd.src2) // self-mov
nopOut(i);
}
foreach(c, copies) //
if (c->count(‌r)) {
c->erase(‌r);
c->insert(s);
}
}
}
}
コールcopies(); 活性をチェックする前に、最適化サイクルの最初に挿入してください。

どうしたの？


前回と比較して、コードはさらに2、3のコマンドによって削減されました。
 00 mov r01,0
 01 mov r02、0x3e8
 02エコー0x126
 03 echo r01
 04エコー0xa0
 05エコーr02
 06エコー0xa7
 07 le r03、r01、r02
 08 jz r03、+ 0x1d（= 0x26）
 09 r03、r01、r02を追加
 0a mov r04、2
 0b div r03、r03、r04
 0cエコー0x162
 0dエコーr03
 0eエコー0xcc
 0f入力r04
 10店舗r01、1
 11 mov r01、1
 12 eq r01、r04、r01
 13 jz r01、+ 4（= 0x18）
 14ロードr01、1
 15 mov r02、1
 16サブr02、r03、r02
 17 jz 0、-0x11（= 0x7）
 18 mov r01,2
 19 eq r01、r04、r01
 1a jz r01、+ 3（= 0x1e）
 1b mov r01、1
 1c r01、r03、r01を追加
 1d jz 0、-0x17（= 0x7）
 1eロードr01、1
 1f mov r03、3
 20 eq r03、r04、r03
 21 jz r03、+ 2（= 0x24）
 22エコー0x146
 23 hlt
 24エコー0x16a
 25 jz 0、-0x1f（= 7）
 26エコー0xff
 27 hlt

消えたコマンド（ add r02, r02, 0をadd r02, r02, 0をadd r02, r02, 0 ）については、それらが無意味であることはすぐに明らかになったように思われるかもしれません。 実際、これらのコマンドは、物理レジスタの指定後のみ意味のない形式を取りました。 完成したpコードを出力する前の最後の段階で。 それまでは、オペランドのnレジスタの数は異なっていました。 実行した分析だけで、それらを結合し、無意味になったコピーを削除することが可能になりました。これは、物理レジスタの指定よりずっと前のことです。

折りたたみ定数


前のものと同様に、DFAを使用して実装される別の標準的な最適化は、 定数折りたたみです。 原則は非常に単純です。オペランドの値がわかっている場合、コンパイル時にすぐに操作を実行できます。 たとえば、コードの代わりに
 MOV R1、2
 MOV R2、3
 R3、R1、R2を追加
すぐに生成できます
  MOV R3.5

定数の操作は、以前の既知の結果を計算するのが面倒だったプログラマーの不注意を必ずしも示すものではありません。たとえば、 pixels=1024*768; pixels=786432;よりも読みやすく、保守しやすいpixels=786432;

今回は、各コマンドで、値がわかっているレジスタのセットを値とともに保存しますstd::map<regnum,int>形式で
通常どおり、セットを計算するための3つのルールを定式化します。繰り返しますが、パッセージの方向は順方向です（次の値は前のコマンドのレジスタの値に依存します）。 ノードでの操作-未知のレジスタの結合。

セットが安定したら、両方のオペランドが既知の各操作をMOV置き換えることができます。

同じデータを使用して、別の最適化を実行できます- 定数伝播 （レジスタ参照の代わりに既知の値の置換）。 この最適化は、私たちが選択したpコード形式では不可能です。これは、レジスタとその中に定数に対する操作がないためです。 ただし、このような操作は多くの実際のプロセッサに存在するため、実行可能コードを生成するときに本格的な「定数置換」を実行できます。 ここで、ゼロ値をR0に置き換えることに制限します。

たとえば、 if (1>2) { echo("unreachable"); } if (1>2) { echo("unreachable"); }にコンパイルされます
 MOV R1、1
 MOV R2、2
 GT R3、R1、R2
 JZ R3、ラベル
 ECHO「到達不能」
ラベル：
定数を折り畳む段階で回転します
 MOV R1、1
 MOV R2、2
 MOV R3、0
 JZ R3、ラベル
 ECHO「到達不能」
ラベル：
前回私たちが既に実装した最適化「非生物コードの破壊」は、最初の2つのMOVコマンドを削除します。
同時にゼロ値をR0で置き換える場合：
 MOV R3、0
 JZ R0、ラベル
 ECHO「到達不能」
ラベル：
次に、非生存コードとともに最後のMOVが削除され、「到達不能コードの破壊」によってECHOも削除され、 JZがNOPに変わります。

同様に、ゼロ以外の既知の値を持つJZコードから削除できます。 2番目に実装される「特別なケース」は、 ADD RX, (0), RY ADD RX, RY, R0をADD RX, RY, R0に置き換え、コピークリーニングアルゴリズムがこのコマンドのレジスタからレジスタへのコピーを認識するようにすることです。

定数の折りたたみのもう1つの利点は、コマンドで負の値を使用できるようになったことです。 レクサーではNUMトークンを正規表現[0-9]+に設定したため、「-123」タイプの文字列は単項マイナス、次にリテラル123として解釈されました。 したがって、彼らは次のようなpコードにコンパイルしました
 MOV R1、123
 SUB R2、R0、R1
これで、p-codeには正直なチームMOV R1, -123ます。

実装


struct commandnは、さらにいくつかのフィールドで補完されます。
std::map<regnum, int > known; regset unknown;

最適化の基礎は、以前の場合と同様、DFAです。
void constp() {
bool changed = false ;
foreach(i, pcode) {
i->known.clear(); i->unknown.clear();
if (i->cmd.opcode==command::mov) { // rule 1
i->known[i->cmd.dest] = i->cmd.imm;
changed = true ;
} else if (writesdest(i)) { // rule 2
i->unknown.insert(i->cmd.dest);
changed = true ;
}
}
while (changed) {
changed = false ;
foreach2(i, pcode, next) {
// rule 3 (next command)
if (hasnext(i))
changed |= propagate(i, next);
// rule 3 (jmp target)
if (i->cmd.opcode==command::jz)
changed |= propagate(i, i->tgt);
}
}
//
foreach(i, pcode) {
i->known[ 0 ] = 0 ; // R0
if (has2src(i) && i->known.count(i->cmd.src1) && i->known.count(i->cmd.src2))
i->cmd = command(command::mov, i->cmd.dest, ops[i->cmd.opcode](i->known[i->cmd.src1],i->known[i->cmd.src2]));
// 0
if (has2src(i)) {
if (i->known.count(i->cmd.src1) && !i->known[i->cmd.src1])
i->cmd.src1 = 0 ;
if (i->known.count(i->cmd.src2) && !i->known[i->cmd.src2])
i->cmd.src2 = 0 ;
if (i->cmd.opcode==command::add && !i->cmd.src1) { //
i->cmd.src1 = i->cmd.src2;
i->cmd.src2 = 0 ;
}
}
if (readsdest(i) && i->known.count(i->cmd.dest))
if (!i->known[i->cmd.dest])
i->cmd.dest = 0 ;
else // , 0
if (i->cmd.opcode==command::jz) nopOut(i);
}
}

propagate()プロシージャは、不明なレジスタのセットの和集合を実装します。いくつかの既知の値を持つレジスタは、不明と宣言されます。
bool propagate(pcommandn from, pcommandn to) {
bool changed = false ; // :
//
foreach(i, from->known) {
regnum r = i->first;
if (to->known.count(‌r))
if ((to->known[r]!=i->second) // , 1
&&!((to->cmd.opcode==command::mov) && (to->cmd.dest==r))) {
to->known.erase(‌r);
to->unknown.insert(‌r);
changed = true ;
} else ; //
else if (!to->unknown.count(‌r)) { // ,
to->known[r]=i->second;
changed = true ;
}
}
//
foreach(r, from->unknown)
if (!to->unknown.count(*r)) {
to->unknown.insert(*r);
to->known.erase(*r);
changed = true ;
}
return changed;
}

最後に残っているのは、オペランドがわかっている場合の値の実際の計算です。 j-scriptエグゼキューターと同じ方法で、各オペコードに関数を設定します。
int hlt( int src1, int src2) { assert( false ); return 0 ; }
int add( int src1, int src2) { return src1+src2; }
int sub( int src1, int src2) { return src1-src2; }
...
int lt( int src1, int src2) { return src1<src2; }
int (*ops[])( int , int ) = {hlt, hlt, hlt, hlt, hlt, hlt, hlt, add, sub, mul, div, eq, ne, ge, le, gt, lt};

constp();への呼び出しを挿入しますconstp(); copies();前copies(); -そして、最適化を終了します。

次の投稿では、x86 / x64の実際の実行可能コードを設定する物理レジスタを使用して、pコードから収集します。

Source: https://habr.com/ru/post/J101946/

More articles:


All Articles