コンパイル。 7：レジスタ割り当て

ファイル名の長さは無限であり、無限は255文字に設定されます。

-ピーターコリンソン：Unixファイルシステム

したがって、p-codeのプログラムがあり、無制限の数のレジスタ（つまり255）を自由に使用できます。 実際のプロセッサのレジスタの数ははるかに少ない（4つと仮定）。 どうする？

さらに投稿：

1. Pコード解析
2. ライフタイム
3. 実装
4. シンプルな最適化
5. バージョン分割
6. メモリを操作する
7. どうしたの？

Pコード解析

最後の投稿では、コンパイルされたプログラムのダンプがありました。 40のチームは簡単に解読できます。

 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 r04、r01、r02を追加
 0a mov r05、2
 0b div r06、r04、r05
 0cエコー0x162
 0dエコーr06
 0eエコー0xcc
 0f入力r07
 10 mov r08、1
 11 eq r09、r07、r08
 12 jz r09、+ 4（= 0x17）
 13 mov r0a、1
 14サブr0b、r06、r0a
 15 r02、r0b、0を追加
 16 jz 0、+ e（= 0x25）
 17 mov r0c、2
 18 eq r0d、r07、r0c
 19 jz r0d、+ 4（= 0x1e）
 1a mov r0e、1
 1b r0f、r06、r0eを追加
 1c r01、r0f、0を追加
 1d jz 0、+ 7（= 0x25）
 1e mov r10、3
 1f eq r11、r07、r10
 20 jz r11、+ 3（= 0x24）
 21エコー0x146
 22 hlt
 23 jz 0、+ 1（= 0x25）
 24エコー0x16a
 25 jz 0、-0x1f（= 7）
 26エコー0xff
 27 hlt

すべてのレジスタが同時に使用されるわけではないことがわかります。ほとんどのレジスタは、次のコマンドにのみ必要な中間値を保存します。 たとえば、 r03



コマンド07-08



でのみ使用され、 r03



チーム1b-1c



のみ使用されます。 これは、格納された値に同じ物理レジスタを使用することに障害がないことを意味します07-08



コマンドでは1つの値に使用され、 1b-1c



では別の値に使用されます。 異なる値に同時に使用されない2つのレジスタは、1つの物理レジスタに結合できます。



「異なる値に同時に使用される」の定義にはわずかな微妙さがあります。 第一に、レジスタの寿命を最初の言及から最後の言及までの単なる間隔と見なすことは不可能です。コードには、たとえば、すべての方向のジャンプを含めることができます。

    ...
 10 mov r、42
 11 jz 0、20
 12エコーr
    ...
 20 ...
    ...
 30 jz 0、12
    ...

r



はチーム10〜12でのみ言及されていますが、チーム20でも暗黙的に使用されます。これは、その後、12に戻ることができるためです。 したがって、 r



はコマンド20で使用される他のレジスタと組み合わせることはできません。



第二の微妙さ：

    ...
 10 mov r、42
 11エコーr
    ...
 20 ...
    ...
 30 mov r、24
 31エコーr
    ...

コマンド20では、レジスタr



は実際には使用されていませんが、その前（10-11）とその後（30-31）の両方に言及されています。 次の使用（31）の前に値が新しい方法で割り当てられるため、他の値を保存できます。 基本的に、値が異なるため、10-11と31-31でr



に異なる物理レジスタを割り当てることもできます。 ただし、このためには、 r



2つの独立した「バージョン」 r



ことを確認し、それらを個別に処理する必要があります。

ライフタイム

レジスタが使用されるコマンドのセットを繰り返し決定することができます。

• レジスタは、その値を読み取るチームによって必要とされます。
• チームAからBに（直接またはジャンプで）行くことができ、Bがレジスタを必要とする場合、Aがそれを必要とします。
• registerは、値を設定するコマンドに必要ありません。

各コマンドについて、「入力時」および「出力時」に必要なレジスタのセットを決定し、これらのセットがインストールされるまで3つのルールを適用します。 プログラムで得られるものは次のとおりです。

             反復数：1（入力/出力）2（入力/出力）3（入力/出力）4（入力/出力）...合計（入力/出力）
 00 mov r01,0 / r01
 01 mov r02、0x3e8 / r01 r01 / r01、r02
 02 echo 0x126 / r01 r01 / r01 r01 / r01 r01、r02 / r01、r02
 03 echo r01 r01 / r01 / r01 / r01 / r02 r01、r02 / r01、r02
 04 echo 0xa0 / r02 r02 / r02 r02 / r02 r01、r02 / r01、r02
 05 echo r02 r02 / r02 / r02 / r02 / r01、r02 r01、r02 / r01、r02
 06 echo 0xa7 / r01、r02 r01、r02 / r01、r02 r01、r02 / r01、r02 r01、r02 / r01、r02
 07 le r03、r01、r02 r01、r02 / r01、r02 / r03 r01、r02 / r03 r01、r02 / r01、r02、r03 r01、r02 / r01、r02、r03
 08 jz r03、+ 0x1d（= 0x26）r03 / r03 / r01、r02 r01、r02、r03 / r01、r02 r01、r02、r03 / r01、r02 r01、r02、r03 / r01、r02
 09 r04、r01、r02 r01、r02 / r01、r02 / r01、r02 / r01、r02 / r04 r01、r02 / r01、r02、r04を追加
 0a mov r05、2 / r04、r05 r04 / r04、r05 r04 / r04、r05 r01、r02、r04 / r01、r02、r04、r05
 0b div r06、r04、r05 r04、r05 / r04、r05 / r04、r05 / r04、r05 / r06 r01、r02、r04、r05 / r01、r02、r06
 0cエコー0x162 / r06 r06 / r06 r06 / r06 r01、r02、r06 / r01、r02、r06
 0dエコーr06 r06 / r06 / r06 / r06 / r01、r02、r06 / r01、r02、r06
 0eエコー0xcc r01、r02、r06 / r01、r02、r06
 0f入力r07 / r07 r01、r02、r06 / r01、r02、r06、r07
 10 mov r08、1 / r07、r08 r07 / r07、r08 r07 / r07、r08 r01、r02、r06、r07 / r01、r02、r06、r07、r08
 11 eq r09、r07、r08 r07、r08 / r07、r08 / r09 r07、r08 / r09 r07、r08 / r09 r01、r02、r06、r07、r08 / r01、r02、r06、r07、r09
 12 jz r09、+ 4（= 0x17）r09 / r09 / r09 / r09 / r06、r07 r01、r02、r06、r07、r09 / r01、r02、r06、r07
 13 mov r0a、1 / r06、r0a r06 / r06、r0a r06 / r06、r0a r01、r06 / r01、r06、r0a
 14サブr0b、r06、r0a r06、r0a / r06、r0a / r0b r06、r0a / r0b r06、r0a / r0b r01、r06、r0a / r01、r0b
 15 r02、r0b、0 r0b / r0b / r0b / r0b / r01、r0b / r01、r02を追加
 16 jz 0、+ e（= 0x25）r01、r02 / r01、r02
 17 mov r0c、2 / r07、r0c r07 / r07、r0c r07 / r07、r0c r01、r02、r06、r07 / r01、r02、r06、r07、r0c
 18 eq r0d、r07、r0c r07、r0c / r07、r0c / r0d r07、r0c / r0d r07、r0c / r0d r01、r02、r06、r07、r0c / r01、r02、r06、r07、r0d
 19 jz r0d、+ 4（= 0x1e）r0d / r0d / r0d / r0d / r06、r07 r01、r02、r06、r07、r0d / r01、r02、r06、r07
 1a mov r0e、1 / r06、r0e r06 / r06、r0e r06 / r06、r0e r02、r06 / r02、r06、r0e
 1b r0f、r06、r0e r06、r0e / r06、r0e / r0f r06、r0e / r0f r06、r0e / r0f r02、r06、r0e / r02、r0fを追加
 1c r01、r0f、0 r0f / r0f / r0f / r0f / r02、r0f / r01、r02を追加
 1d jz 0、+ 7（= 0x25）/ r01、r02 r01、r02 / r01、r02
 1e mov r10、3 / r07、r10 r07 / r07、r10 r07 / r07、r10 r01、r02、r07 / r01、r02、r07、r10
 1f eq r11、r07、r10 r07、r10 / r07、r10 / r11 r07、r10 / r11 r07、r10 / r11 r01、r02、r07、r10 / r01、r02、r11
 20 jz r11、+ 3（= 0x24）r11 / r11 / r11 / r11 / r01、r02、r11 / r01、r02
 21エコー0x146
 22 hlt
 23 jz 0、+ 1（= 0x25）/ r01、r02 r01、r02 / r01、r02
 24エコー0x16a / r01、r02 r01、r02 / r01、r02
 25 jz 0、-0x1f（= 7）/ r01、r02 r01、r02 / r01、r02 r01、r02 / r01、r02 r01、r02 / r01、r02
 26エコー0xff
 27 hlt

個々の反復について：

1. 各コマンドの入力時-コマンドが使用するレジスタ。 （ルール番号1）
2. 各コマンドの出力で、そこから到達可能なコマンドの入力をコピーします。 （ルール番号2）
3. 各コマンドの入力で、コマンドによって記録されたレジスタを除いて、その出力をコピーします。 （ルール番号3）
4. 各コマンドの出力で、そこから到達可能なコマンドの入力をコピーします。 （ルール番号2）

さらに、ルールNo. 2とNo. 3が交互に繰り返されます。



数回の反復の後、「レジスタの存続可能性」の最終マークアップを取得します。これは、各チームのニーズを登録します。 次に、pコードのレジスタの名前を物理的なものに変更できます。たとえば、「貪欲」です。「最も必要な」レジスタ（コマンドの最大数が必要）を取得します。 対応するチームでまだ使用されていない物理的な名前に変更します。 繰り返します。

可能な限り十分な物理レジスターを提供する最適な選択は、徹底的な検索によってのみ可能です：このタスクは、「最小の色でグラフを着色する」と同等であり、数学者はそれに対する有効な解決策はないと考えています。 「貪欲な」アプローチは、最悪の可能性ではありません。



次のpレジスタに物理的な空きがない場合はどうすればよいですか？ たとえば、このコードには、それぞれ5つのpレジスタを使用するコマンド（10〜12、17〜19）があります。少なくとも1つに十分なスペースがありません。 メモリ内に保持する必要があることは明らかです。

しかし、レジスターに「あなたは不運だ、あなたはメモリ内に保持されます」と言うだけでは十分ではありません。私たちのpコードの指示はメモリからの値とほとんどの実際のプロセッサのコマンドを処理する方法を知りません。 使用時にメモリから値を取得して登録する必要があります。 どれだけ？ 実際、すべてのレジスタがビジーであるため、メモリ内の値を削除したためです！



この時点で、私が学んだ理論は推測とヒューリスティックで終わります。 私は、十分なレジスタがないチームの前に、「余分なレジスタをメモリに流し込む」ことを決め、その後、メモリからそれらを読み戻しました。 したがって、注ぎ出されたレジスタの「存続期間」では、このコマンドの場所に穴が表示され、この穴で他の目的に解放されたレジスタを使用できます。



コードを「押しのけて」、読み取り/書き込みコマンドをメモリに挿入できるようにするには、中間形式を少し変更する必要があります：これはリンクリストになり、ジャンプターゲットはオフセットとしてではなく、ポインターとして保存されます（リストを有向グラフに変換）。 pコードの生成中に、 バックパッチのために、インデックスでチームを参照する必要があります。 このため、個別の変位ベクトルがあります。

typedef std::list< struct commandn>::iterator pcommandn;

struct commandn {

command cmd;

pcommandn tgt; //

commandn( const command& cmd) : cmd(cmd), tgt( NULL ) {}

};



std::list<commandn> pcode;

std::vector<pcommandn> pcodeidx;



inline int emit( const command& cmd) {

pcodeidx.push_back(pcode.insert(pcode.end(), commandn(cmd)));

return pcode.size()- 1 ;

}

inline int emit(command::opcodes opcode, regnum dest, regnum src1, regnum src2) {

return emit(command(opcode, dest, src1, src2));

}

inline int emit(command::opcodes opcode, regnum dest, short imm) {

return emit(command(opcode, dest, imm));

}

inline void fix( int index, command::opcodes opcode, regnum dest, short imm) {

*pcodeidx[index] = commandn(command(opcode, dest, imm));

}







ジャンプの目標へのポインタは、pコードの生成中に記入するのが困難です。ジャンプを作成する時点では、ターゲットインデックスは既にわかっていますが、どのチームが存在するかはまだ不明です。 まだ作成されていないチームにポインタを置くことには問題があります。 したがって、pコードの解析と生成の終了後、生成されたコードをバイパスしてジャンプポインターを配置します。 次に、レジスタの割り当てに必要なすべての作業を行います。 最後に、pコードをファイルにダンプする前に、それを「シリアル化」する必要があります-各コマンドの最終インデックスを決定し、ジャンプオフセットを入力します。 このために、 int index;



フィールドをstruct commandn



に追加しint index;







int main() {

yyparse();

//

for ( int i= 0 ; i<pcode.size(); i++)

if (pcodeidx[i]->cmd.opcode==command::jz)

pcodeidx[i]->tgt = pcodeidx[i+ 1 +pcodeidx[i]->cmd.imm];



// /

// ...



// /

int index = 0 ;

foreach(i, pcode) i->index = index++;

foreach(i, pcode)

if (i->cmd.opcode==command::jz)

i->cmd.imm = i->tgt->index-i->index- 1 ;



// -

// ...

}







ポイントは小さい：「処理/最適化」を実装します。 ご想像のとおり、ほとんどのコンパイラコードが必要です。

実装

レジスタを割り当てるために、各コマンドに対して（ struct commandn



直接）入力および出力で有効なレジスタのセットを保存します。ライフタイムを決定するためのpコードレジスタ。 および個別に-実際の目的との互換性を判断するための物理レジスタ。

typedef std::set<regnum> aliveset;

enum physreg { firstp = 1 , lastp = 4 };

typedef std::set<physreg> alivesetp;

struct commandn {

// ...

aliveset onenter, onexit; // liveness check

alivesetp onenterp, onexitp; // phys reg allocation

// ...

};







もう1つの便利なことは、コマンドで使用されるレジスタをオペコードで判断することです。

inline bool hasnext(pcommandn cmd) {

return (cmd->cmd.opcode!=command::hlt &&!

(cmd->cmd.opcode==command::jz && !cmd->cmd.dest));

}

inline bool has2src(pcommandn cmd) {

return cmd->cmd.opcode>=command::add;

}

inline bool writesdest(pcommandn cmd) {

return cmd->cmd.opcode>=command::mov;

}

inline bool readsdest(pcommandn cmd) {

return cmd->cmd.opcode>=command::store &&

cmd->cmd.opcode<=command::echo;

}







その後、上の図に従って、各コマンドについて、入力と出力で必要なレジスタのセットを計算します。 同時に、貪欲なアポイントメントのために、各レジスタが必要な回数をカウントします。

std::vector< int > liveness() { // returns usecount

std::vector< int > usecount(lastreg+ 1 );

bool changed = false ;

// rule 1

foreach(i, pcode) {

i->onenter = i->onexit = aliveset();

if (has2src(i)) {

if (i->cmd.src1) {

usecount[i->cmd.src1]++;

i->onenter.insert(i->cmd.src1);

}

if (i->cmd.src2) {

usecount[i->cmd.src2]++;

i->onenter.insert(i->cmd.src2);

}

} else if (readsdest(i) && i->cmd.dest) {

usecount[i->cmd.dest]++;

i->onenter.insert(i->cmd.dest);

}

if (i->onenter.size())

changed = true ;

}

while (changed) {

changed = false ;

foreach2(i, pcode, next) {

int oldsize = i->onenter.size()+i->onexit.size();

// rule 2 (next command)

if (hasnext(i))

i->onexit.insert(next->onenter.begin(), next->onenter.end());

// rule 2 (jmp target)

if (i->cmd.opcode==command::jz)

i->onexit.insert(i->tgt->onenter.begin(), i->tgt->onenter.end());

// rule 3

i->onenter.insert(i->onexit.begin(), i->onexit.end());

if (writesdest(i))

i->onenter.erase(i->cmd.dest);



if (i->onenter.size()+i->onexit.size() != oldsize)

changed = true ;

}

}

return usecount;

}







foreach2



マクロをforeach2



すると、ループの本文の現在の要素と次の要素を確認できます。

#define foreach2(i, list, next) typedef typeof(list) TOKENPASTE2(T, __LINE__ ); \

        for (TOKENPASTE2(T, __LINE__ )::iterator next = list.begin(), i=next++; i != list.end(); i=next, next++)







原則として、チームが「上から下」ではなく「下から上」にバイパスされない場合は、各チームから前のチームに「広がる」必要があるため、反復の総数を減らすことができます。 コードを簡素化するためにトップダウンバイパスが選択されました。 最悪の場合、長さNのコマンドのコードでは、2 N回の反復が必要になります（反復ごとに、コマンドの半分の距離まで必要になります）。 test.jsk



には35回の反復で十分でした。ジャンプすると距離が短くなるためです。



最後に、なぜこれをすべて行ったのか：

// / :

while ( 1 ) { //



//

// ...



std::vector< int > usecount = liveness();

std::vector<physreg> physmap(lastreg+ 1 );

foreach(i, pcode)

i->onenterp = i->onexitp = alivesetp();

while ( 1 ) {

//

std::vector< int >::iterator max = std::max_element(usecount.begin(), usecount.end());

if (!*max) break ; //

*max = 0 ;

regnum r = max - usecount.begin();

// . - №r

std::vector< int > collisions(lastp); // 0-based

for (physreg p=firstp; p<=lastp; p=(physreg)(p+ 1 )) { // error: ISO C++ forbids incrementing an enum

foreach(i, pcode) {

if (contains(i->onenter, r) && contains(i->onenterp, p))

collisions[p- 1 ]++;

if (contains(i->onexit, r) && contains(i->onexitp, p))

collisions[p- 1 ]++;

}

if (collisions[p- 1 ]) continue ; // .

physmap[r] = p;

// - №r №p

foreach(i, pcode) {

if (contains(i->onenter, r))

i->onenterp.insert(p);

if (contains(i->onexit, r))

i->onexitp.insert(p);

}

break ; //

}

if (physmap[r]) continue ; //

// . - №r

// : ,

foreach2(i, pcode, next)

if ((i->cmd.opcode!=command::load && i->cmd.opcode!=command::store) &&

((contains(i->onenter, r) && i->onenterp.size()==lastp) ||

(contains(i->onexit, r) && i->onexitp.size()==lastp))) {

// , ,

// ...

goto afterspill;

}

// : ?

yyerror( "don't know how to proceed" );

}

// ;

foreach(i, pcode) {

i->cmd.dest = physmap[i->cmd.dest];

if (has2src(i)) {

i->cmd.src1 = physmap[i->cmd.src1];

i->cmd.src2 = physmap[i->cmd.src2];

}

}

break ;



afterspill : // - " "

}







それでもレジスタをどのように注ぐかについて正確には掘り下げていませんが、上記のコードには多くの問題があることに言及する価値があります。 第一に、ヒューリスティックは最も単純な場合にのみ機能します。 より一般的な状況

    ...
 10にはr1、r2、r3、r4が必要
    ...
 20にはr1、r3、r4、r5が必要
    ...
 30にはr2、r3、r4、r5が必要
    ...

すべての物理r5



がr1,r2,r3,r4



費やされたため、 r5



には物理r5



がありません。 ただし、5つのレジスタすべてが同時に必要な単一のコマンドはありません。



より難しい問題は、すべての流出が無駄なstore/load



ペアでプログラムを詰まらせることであり、それらをきれいにする必要があります-さもなければ、それらで使用されるレジスタは十分な「ノイズ」を作成し、何もレジスタがなくなります。



別のアイデア：流出に起因するライフタイムの穴は、元のpレジスタを異なる物理レジスタに配置できる2つの独立した「バージョン」に分割する可能性があります。 システムの柔軟性のために、バージョン分割を実装する価値があります。外部サイクルを繰り返すたびに、レジスタの寿命が短くなり、物理的なレジスタの分散がより簡単になります。



そして、余分なload



とstore



を削除しようとしたので、他の余分なコマンドも同時に削除します。 pコードの操作には他の副作用がないことを考慮すると、結果でレジスターを計算する以外に、出力で結果が生きていないコマンドを削除できます。 たぶんプログラマーは値を未使用の変数に割り当てるか、 (2+2);



ような演算子を使用しました(2+2);





行内のすべてを削除します。そのため、ヒープへの到達不能コード（たとえばhltの後のjz）を削除し、ジャンプのチェーンを圧縮します（ジャンプを1回のジャンプのジャンプに置き換えます）。



コマンドを削除して、その上のすべてのジャンプを検索および修正しないようにするには、コマンドをnop



に置き換えると便利です。 次のコマンド（ jz r00, +0



）に無条件ジャンプを割り当てます。 利点は、次の反復で、 nop



のジャンプがチェーンに沿って圧縮され、 nop



自体が到達不能なチームとしてクリーンアップされることです。

シンプルな最適化

到達不能なチームを検出するために、詳細なバイパスを使用します。 どのコマンドが既にバイパスされているかを追跡するには、 struct commandn



int reachcnt;



新しいint reachcnt;



フィールドを追加しint reachcnt;





ブール値フィールドで十分です。 しかし、各チームの「エントリーの程度」は、いつか役に立つことがわかるかもしれません。

void markReachable(pcommandn cmd) {

while (!cmd->reachcnt++) {

if (cmd->cmd.opcode==command::jz)

markReachable(cmd->tgt);

if (hasnext(cmd))

cmd++;

else

break ;

}

}



void nopOut(pcommandn cmd) {

pcommandn next = cmd; next++;

cmd->cmd = command(command::jz, 0 , 0 );

cmd->tgt = next;

}



void simpleopt() {

//

foreach(i, pcode)

if (i->cmd.opcode==command::jz)

while (i->tgt->cmd.opcode==command::jz && !i->tgt->cmd.dest)

i->tgt = i->tgt->tgt;

//

foreach(i, pcode) i->reachcnt = 0 ;

markReachable(pcode.begin());

foreach2(i, pcode, next)

if (!i->reachcnt)

pcode.erase(i);

// nop:

foreach2(i, pcode, next)

if (i->cmd.opcode==command::jz &&

!i->cmd.dest && i->tgt==next)

pcode.erase(i);

}



// :

simpleopt();

//

liveness();

bool changed = false ;

foreach(i, pcode)

if (writesdest(i) && !contains(i->onexit, i->cmd.dest)) {

nopOut(i);

changed = true ;

}

if (changed) continue ;

//

// ...



バージョン分割

レジスタの「必要間隔」にギャップがある場合、つまり ある命令セットの値が別のセットに侵入することはありません。つまり、レジスタを、より短い寿命のレジスタのペアに分割することができます。

別のグラフアルゴリズムは、ライフタイムから不連続なフラグメントを抽出するのに役立ちます：接続されたコンポーネントの検索。

私たちは、コードの有効性よりもコードの明快さを追求しています。 したがって、pvg内にpvgがあり、グラフ全体を走査することでコンポーネントがマージされます。



struct commandn



は、今日の最後の別のフィールドが必要ですstd::map<regnum,regnum> version;





その中に、各対応コマンド「p-register-> version number」を保存します。

コマンドで大文字と小文字が使用されているが、 version



まだ一致していない場合、回避策はまだこのコマンドに到達していません。

外部pvgの場合、新しいフィールドを開始しないために、 markReachable()



と同じreachcnt



を使用します

std::map<regnum,regnum> renameto; //



void versionizeReg(pcommandn cmd, regnum r, regnum rv) { // r rv

while (!contains(cmd- > version, r) &&

(contains(cmd- > onenter, r) || contains(cmd- > onexit, r))) {

//

cmd- > version[r] = renameto[rv];

if (cmd- > cmd.dest==r) cmd- > cmd.dest=renameto[rv];

if (has2src(cmd)) {

if (cmd- > cmd.src1==r) cmd- > cmd.src 1 =renameto[rv];

if (cmd- > cmd.src2==r) cmd- > cmd.src 2 =renameto[rv];

}

if (!contains(cmd- > onexit,r)) return ; //

if (cmd- > cmd.opcode==command::jz &&

contains(cmd- > tgt- > onenter, r)) {

versionizeReg(cmd- > tgt, r, rv);

}

if (hasnext(cmd)) {

cmd++;

if (contains(cmd- > onenter, r))

continue ;

}

return ; //

}

// ?

if (contains(cmd- > version, r) && cmd- > version[r]!=renameto[rv]) {

// renameto[rv] cmd->version[r]

regnum from = std::max(cmd- > version[r], renameto[rv]),

to = std::min(cmd- > version[r], renameto[rv]);

renameto[from] = to;

foreach(i, pcode) {

if (i- > cmd.dest==from) i- > cmd.dest = to;

if (has2src(i)) {

if (i- > cmd.src1==from) i- > cmd.src 1 = to;

if (i- > cmd.src2==from) i- > cmd.src 2 = to;

}

if (contains(i- > version, r) && i- > version[r]==from)

i- > version[r] = to;

}

}

}



void versionize(pcommandn cmd) {

while (!cmd- > reachcnt++) {

// versionize registers that live on exit

foreach(r, cmd- > onexit)

if (!contains(cmd- > version, *r)) {

regnum rv = newreg();

renameto[rv] = rv;

versionizeReg(cmd, *r, rv);

}

if (cmd- > cmd.opcode==command::jz)

versionize(cmd- > tgt);

if (hasnext(cmd))

cmd++;

else

break ;

}

}



// :

foreach(i, pcode) {

i- > version.clear();

i- > reachcnt = 0 ;

}

renameto.clear();

int lastbasereg = lastreg;

versionize(pcode.begin());

// , 1

foreach(i, pcode) {

if (i- > cmd.dest) i- > cmd.dest-=lastbasereg;

if (has2src(i)) {

if (i- > cmd.src1) i- > cmd.src 1 -=lastbasereg;

if (i- > cmd.src2) i- > cmd.src 2 -=lastbasereg;

}

}

lastreg -= lastbasereg;







実際のレジスターの注入を実装することは残っています。 ヒューリスティックを指定します：生きているが、コマンドで使用されていないレジスタを注ぎ出すことができます。

regnum spillable(pcommandn cmd) { // ,

aliveset alive;

alive.insert(cmd->onenter.begin(), cmd->onenter.end());

alive.insert(cmd->onexit.begin(), cmd->onexit.end());

alive.erase(cmd->cmd.dest);

if (has2src(cmd)) {

alive.erase(cmd->cmd.src1);

alive.erase(cmd->cmd.src2);

}

if (!alive.size()) return 0 ;

return *alive.begin();

}







別のmap



は、レジスタのすべての流出が同じ場所に収まるように、レジスタ番号によってそのコピーの「アドレス」をメモリに保存します。 アドレスは、最初の流出時にのみレジスタに割り当てられます。

// spill slots

std::map<regnum, int > spill;

int lastspill = 0 ;



void spillAt(pcommandn cmd, regnum victim, pcommandn next) {

// /

int spslot = spill[victim];

if (!spslot) {

spslot = ++lastspill;

spill[victim] = spslot;

}

// store load

pcommandn me = pcode.insert(next, *cmd);

cmd->cmd = command(command::store, victim, spslot);

commandn load(command(command::load, victim, spslot));

if (hasnext(me))

pcode.insert(next, load);

if (me->cmd.opcode==command::jz)

me->tgt = pcode.insert(me->tgt, load);

}







チームはstore-cmd-load



トリプルに置き換えられるため、チームへの既存のジャンプは、その前に挿入されたstore



にジャンプする必要があります。 コード全体でこのようなジャンプを探しないようにcmd



次のコマンドでcmd



コピーを挿入し、 元のコマンドをstore



置き換えます。

同様に、コマンドが条件付きジャンプの場合、両方の結果でload



実行する必要がありload



。 したがって、次のコマンドで追加し、ジャンプの目標の前に挿入します。



（コマンドをあるコマンドから別のコマンドに移動する可能性があるため、最初のツリー実装のように、 echo



の行を「識別子」によってコマンド自体にバインドする必要があります。コマンドインデックスもポインタも変更されません。）



2番目のヒューリスティック：すべての物理レジスターが占有されているチームを見つけることができなかった場合、「最適な」物理レジスター（既に割り当てられているレジスターとの衝突が最も少ない）を取得し、必要な場所で解放します。

// . - №r

regnum victim;

// 1: ,

foreach2(i, pcode, next)

if ((i->cmd.opcode!=command::load && i->cmd.opcode!=command::store) &&

((contains(i->onenter, r) && i->onenterp.size()==lastp) ||

(contains(i->onexit, r) && i->onexitp.size()==lastp))) {

victim = spillable(i);

assert(victim);

spillAt(i, victim, next);

goto afterspill;

}

// 2: " "

physreg bestfit = (physreg)(std::max_element(collisions.begin(), collisions.end())-collisions.begin()+ 1 );

foreach2(i, pcode, next)

if ((i->cmd.opcode!=command::load && i->cmd.opcode!=command::store) &&

((contains(i->onenter, r) && contains(i->onenterp, bestfit)) ||

(contains(i->onexit, r) && contains(i->onexitp, bestfit))) &&

(victim = spillable(i))) {

spillAt(i, victim, next);

goto afterspill;

}

yyerror( "don't know how to proceed" );







バージョンを分割するときは、スロット番号をコピーすることを忘れないでください（同じレジスタのすべてのバージョンが1つのスロットに保存されます）。次に、バージョンの名前を変更するときは、 spill



を更新することを忘れないでください。



コンパイラはほとんど機能しています。 最後の問題は、無意味なload



とstore



大量に生成され、それらのために意味のあるコマンド用のレジスタがないことです。

メモリを操作する

最初に、一部のレジスタがload/store



コマンドで排他的に使用されることが判明する場合があります。

このようなコマンドは無意味です。レジスタは常に、読み取られたスロットと同じスロットに書き込まれます。

バージョンを分割した後にクリーンアップを挿入します。短いライフタイムで多くのレジスタを取得する必要があります。

//

std::vector< bool > used(lastreg+ 1 );

foreach(i, pcode) {

if (writesdest(i) && i->cmd.opcode!=command::load)

used[i->cmd.dest] = true ;

if (readsdest(i) && i->cmd.opcode!=command::store)

used[i->cmd.dest] = true ;

if (has2src(i)) {

used[i->cmd.src1] = true ;

used[i->cmd.src2] = true ;

}

}

foreach(i, pcode)

if ((i->cmd.opcode==command::load && !used[i->cmd.dest]) ||

(i->cmd.opcode==command::store && !used[i->cmd.dest]))

nopOut(i);







第二に、同じload



チェーンがある場合、読み取りレジスタが生きていないため、最後のチェーン以外はすべて削除されます。 しかし、同じstore



チェーンがある場合、それらを削除するには、何か新しいものを考え出す必要があります。 このアルゴリズムは、レジスタの必要性の反復定義に非常に似ていますが、「保存しない」を定義して、すでに保存されているレジスタのすべての保存をクリアします。

• レジスタは、値を設定するコマンドには保存されません。
• チームAから（直接またはジャンプで）Bに移動でき、レジスタがAに保存されていない場合、Bには保存されません。
• レジスタは、その値を保存するコマンドに保存されます。

このアルゴリズムは、配布の方向のみが前のアルゴリズムと異なることがわかります。必要性は各チームから前のチームにまで拡張され、非保存は次のチームに拡張されます。

一般に、プログラムの各ポイントでレジスタのセットを計算するための反復アルゴリズムは、 データフロー分析と呼ばれ、2つの名前を除いて、他の多くの最適化に使用されます。



void unsaved() {

bool changed = false ;

// rule 1

foreach(i, pcode) {

i->onenter = i->onexit = aliveset();

if (writesdest(i)) {

i->onexit.insert(i->cmd.dest);

changed = true ;

}

}

while (changed) {

changed = false ;

foreach2(i, pcode, next) {

int oldsize = i->onenter.size()+i->onexit.size();

// rule 2 (next command)

if (hasnext(i))

next->onenter.insert(i->onexit.begin(), i->onexit.end());

// rule 2 (jmp target)

if (i->cmd.opcode==command::jz)

i->tgt->onenter.insert(i->onexit.begin(), i->onexit.end());

// rule 3

i->onexit.insert(i->onenter.begin(), i->onenter.end());

if (i->cmd.opcode==command::store)

i->onexit.erase(i->cmd.dest);



if (i->onenter.size()+i->onexit.size() != oldsize)

changed = true ;

}

}

}



afterspill : // - " "

unsaved();

foreach(i, pcode)

if (i->cmd.opcode==command::store && !contains(i->onenter, i->cmd.dest))

nopOut(i);

}



どうしたの？

コンパイラー全体： tyomitch.net.ru/jsk.y.regs.html

5万行のうち、解析の5分の1だけが属します。 実際、他のコンパイラの人件費と比較して、パーサーは面白くない些細なことのようです。 しかし、これは、パーサーの作成が骨に吸い込まれ、準備ができているものしか使用できないためです。 一方、コードを処理するとき、フィクションの余地があります。



レジスタの割り当てと最初の最適化の結果、生成されたコードはいくつかのコマンドのみで拡張されました。

 00 mov r01,0
 01 mov r02、0x3e8
 02エコー0x12e
 03 echo r01
 04エコー0xa8
 05エコーr02
 06エコー0xaf
 07 le r03、r01、r02
 08 jz r03、+ 0x1f（= 0x28）
 09 r03、r01、r02を追加
 0a mov r04、2
 0b div r03、r03、r04
 0cエコー0x16a
 0dエコーr03
 0eエコー0xd4
 0f入力r04
 10店舗r01、1
 11 mov r01、1
 12 eq r01、r04、r01
 13 jz r01、+ 5（= 0x19）
 14ロードr01、1
 15 mov r02、1
 16サブr02、r03、r02
 17 r02、r02、0を追加
 18 jz 0、-0x12（= 0x7）
 19 mov r01、2
 1a eq r01、r04、r01
 1b jz r01、+ 4（= 0x20）
 1c mov r01、1
 1d r01、r03、r01を追加
 1e r01、r01、0を追加
 1f jz 0、-0x19（= 0x7）
 20ロードr01、1
 21 mov r03、3
 22 eq r03、r04、r03
 23 jz r03、+ 2（= 0x26）
 24エコー0x14e
 25 hlt
 26エコー0x172
 27 jz 0、-0x21（= 7）
 28エコー0x107
 29 hlt

ただし、使用されるレジスタは4つだけなので、このpコードはおそらく実際のプロセッサのマシンコードに変換されます。



8月も継続します。休暇に行くので、この投稿を空港から直接追加します。

みなさん素敵な夏を！