21

私は Pascal のサブセット用のコンパイラを書いています。コンパイラは、構成されたマシン用のマシン命令を生成します。この機械語用のピープホール オプティマイザーを書きたいのですが、より複雑なパターンの一部を置き換えるのに苦労しています。

ピープホール オプティマイザーの仕様

ピープホール オプティマイザーを作成するためのいくつかの異なるアプローチを調査し、バックエンドのアプローチに落ち着きました。

  • Encoder はemit()、機械語命令が生成されるたびに関数を呼び出します。
  • emit(Instruction currentInstr)のぞき穴の最適化のテーブルをチェックします。
    • 現在の命令がパターンの末尾に一致する場合:
      1. 以前に発行された命令の照合を確認してください
      2. すべての命令がパターンに一致した場合は、コード ストアの末尾を変更して最適化を適用します。
    • 最適化が見つからない場合は、通常どおり命令を発行します

現在の設計アプローチ

メソッドは十分に簡単です。それは私が問題を抱えている実装です。私のコンパイラでは、マシン命令はInstructionクラスに格納されています。InstructionMatchマシン命令の各コンポーネントに一致する正規表現を格納するクラスを作成しました。そのequals(Instruction instr)メソッドはtrue、パターンが機械命令に一致する場合に戻りますinstr。

しかし、自分が持っているルールを完全に適用することはできません。まず、私の現在のアプローチでは、不要なオブジェクトが散らかってしまうと思います。のぞき穴の最適化数の完全なリストが約 400 のパターンになる可能性があることを考えると、これはすぐに手に負えなくなります。さらに、実際には、このアプローチで作業するより難しい置換を取得することはできません (「私の質問」を参照してください)。

代替アプローチ

私が読んだある論文では、以前の命令を 1 つの長い文字列に折り畳み、正規表現を使用して照合および置換し、文字列を機械語命令に変換しています。これは私には悪いアプローチのように思えました。間違っている場合は修正してください。

パターン例、パターン構文

x: JUMP x+1; x+1: JUMP y  -->  x: JUMP y
LOADL x; LOADL y; add     -->  LOADL x+y
LOADA d[r]; STOREI (n)    -->  STORE (n) d[r]

これらの各パターン例は、次の機械命令テンプレートを人間が読み取れる表現にすぎないことに注意してください。

op_code register n d

(通常、n はワード数を示し、d はアドレス変位を示します)。この構文は、命令がコード ストアのx: <instr>address に格納されていることを示しています。x

したがって、オペコードが 5の場合、命令はLOADL 17完全な機械語命令と同等です (この命令では使用されません)。5 0 0 17LOADLnr

私の質問

その背景を踏まえて、私の質問は次のとおりです。以前の命令の一部を変数として置換に含める必要がある場合、パターンを効果的に照合して置換するにはどうすればよいですか? たとえば、 のすべてのインスタンスをLOADL 1; addインクリメント マシン命令に単純に置き換えることができます。これを行うために、前の命令のどの部分も必要ありません。しかし、置換パターンで 2 番目の例の 'x' と 'y' の値を効果的に使用する方法がわかりません。

editInstruction :クラスの各フィールドは単なる整数であることに言及する必要があります(マシン命令では通常のことです)。パターン テーブルでの「x」または「y」の使用は、任意の整数値を表す変数です。

4

1 に答える 1

17

これを行う簡単な方法は、ピープホール オプティマイザーを有限状態マシンとして実装することです。

命令を生成するが命令を発行しない生のコードジェネレーターと、実際のコードをオブジェクト ストリームに送信する発行ルーチンがあると仮定します。

ステート マシンは、コード ジェネレーターが生成する命令をキャプチャし、状態間の遷移によって生成された 0 個以上の命令のシーケンスを記憶します。したがって、状態は、生成されたが発行されていない命令の (短い) シーケンスを暗黙的に記憶します。また、レジスタ名、定数値、アドレッシング モード、抽象的なターゲット メモリ位置など、キャプチャした命令の主要なパラメータを記憶する必要もあります。特別な開始状態は、命令の空の文字列を記憶します。いつでも、送信されていない命令 (「フラッシュ」) を送信できる必要があります。これを常に行うと、ピープホール ジェネレーターが次の命令をキャプチャしてから発行し、有用な作業が行われません。

有用な作業を行うには、マシンができるだけ長いシーケンスをキャプチャする必要があります。通常、マシン命令には多くの種類があるため、実際問題として、連続して覚えることができません。そうしないと、ステート マシンが巨大になります。ただし、最も一般的なマシン命令 (load、add、cmp、branch、store) については、最後の 2 つまたは 3 つを覚えておくと便利です。マシンのサイズは実際には、実行したい最長のピープホール最適化の長さによって決まりますが、その長さが P の場合、マシン全体が P 状態の深さである必要はありません。

各状態には、コード ジェネレーターによって生成された「次の」命令に基づいて、次の状態への遷移があります。状態が N 個の命令のキャプチャを表していると想像してください。トランジションの選択肢は次のとおりです。

  • この状態が表す左端の 0 以上 (これを k と呼びます) の命令をフラッシュし、次の状態 (N-k+1 を表す) に遷移します。これは、マシン命令 I の追加のキャプチャを表す命令です。
  • この状態が表す左端の k 個の命令をフラッシュし、残りの Nk 個の命令を表す状態に遷移し、命令 I を再処理します。
  • 状態を完全にフラッシュし、命令 I も発行します。[実際には開始状態でこれを行うことができます]。

k 命令をフラッシュするとき、実際に発行されるのは、これらの k のピープホール最適化バージョンです。そのような命令を発行する際に、必要なものは何でも計算できます。また、残りの命令のパラメーターを適切に「シフト」することも覚えておく必要があります。

これはすべて、ピープホール オプティマイザーの状態変数と、コード ジェネレーターが次の命令を生成する各ポイントでの case ステートメントを使用して、非常に簡単に実装できます。case ステートメントは、ピープホール オプティマイザーの状態を更新し、遷移操作を実装します。

私たちのマシンが拡張スタックマシンであると仮定します。

 PUSHVAR x
 PUSHK i
 ADD
 POPVAR x
 MOVE x,k

ただし、生コード ジェネレーターは純粋なスタック マシン命令のみを生成します。たとえば、MOV 命令はまったく発行しません。ピープホール オプティマイザにこれを実行してもらいます。

私たちが気にかけているのぞき穴のケースは次のとおりです。

 PUSHK i, PUSHK j, ADD ==> PUSHK i+j
 PUSHK i, POPVAR x ==> MOVE x,i

状態変数は次のとおりです。

 PEEPHOLESTATE (an enum symbol, initialized to EMPTY)
 FIRSTCONSTANT (an int)
 SECONDCONSTANT (an int)

私たちのケースステートメント:

GeneratePUSHK:
    switch (PEEPHOLESTATE) {
        EMPTY: PEEPHOLESTATE=PUSHK;
               FIRSTCONSTANT=K;
               break;
        PUSHK: PEEPHOLESTATE=PUSHKPUSHK;
               SECONDCONSTANT=K;
               break;
        PUSHKPUSHK:
        #IF consumeEmitLoadK // flush state, transition and consume generated instruction
               emit(PUSHK,FIRSTCONSTANT);
               FIRSTCONSTANT=SECONDCONSTANT;
               SECONDCONSTANT=K;
               PEEPHOLESTATE=PUSHKPUSHK;
               break;
        #ELSE // flush state, transition, and reprocess generated instruction
               emit(PUSHK,FIRSTCONSTANT);
               FIRSTCONSTANT=SECONDCONSTANT;
               PEEPHOLESTATE=PUSHK;
               goto GeneratePUSHK;  // Java can't do this, but other langauges can.
        #ENDIF
     }

  GenerateADD:
    switch (PEEPHOLESTATE) {
        EMPTY: emit(ADD);
               break;
        PUSHK: emit(PUSHK,FIRSTCONSTANT);
               emit(ADD);
               PEEPHOLESTATE=EMPTY;
               break;
        PUSHKPUSHK:
               PEEPHOLESTATE=PUSHK;
               FIRSTCONSTANT+=SECONDCONSTANT;
               break:
     }  

  GeneratePOPX:
    switch (PEEPHOLESTATE) {
        EMPTY: emit(POP,X);
               break;
        PUSHK: emit(MOV,X,FIRSTCONSTANT);
               PEEPHOLESTATE=EMPTY;
               break;
        PUSHKPUSHK:
               emit(MOV,X,SECONDCONSTANT);
               PEEPHOLESTATE=PUSHK;
               break:
     }

GeneratePUSHVARX:
    switch (PEEPHOLESTATE) {
        EMPTY: emit(PUSHVAR,X);
               break;
        PUSHK: emit(PUSHK,FIRSTCONSTANT);
               PEEPHOLESTATE=EMPTY;
               goto GeneratePUSHVARX;
        PUSHKPUSHK:
               PEEPHOLESTATE=PUSHK;
               emit(PUSHK,FIRSTCONSTANT);
               FIRSTCONSTANT=SECONDCONSTANT;
               goto GeneratePUSHVARX;
     }

#IF は、2 つの異なるスタイルの遷移を示しています。1 つは生成された命令を使用するもので、もう 1 つは使用しないものです。この例ではどちらでも機能します。これらの case ステートメントが数百になると、両方のタイプが便利であることがわかります。「消費しない」バージョンは、コードを小さく保つのに役立ちます。

ピープホール オプティマイザをフラッシュするルーチンが必要です。

  flush() {
    switch (PEEPHOLESTATE) {
        EMPTY: break;
        PUSHK: emit(PUSHK,FIRSTCONSTANT);
               break;
        PUSHKPUSHK:
               emit(PUSHK,FIRSTCONSTANT),
               emit(PUSHK,SECONDCONSTANT),
               break:
      }
      PEEPHOLESTATE=EMPTY;
      return; }

このピープホール オプティマイザが次の生成コードで何を行うかを検討するのは興味深いことです。

      PUSHK  1
      PUSHK  2
      ADD
      PUSHK  5
      POPVAR X
      POPVAR Y

この FSA スキーム全体が行うことは、状態遷移でパターン マッチングを非表示にし、ケースで一致したパターンへの応答を非表示にすることです。これは手作業でコーディングでき、高速で、コーディングとデバッグが比較的簡単です。しかし、ケースの数が多くなると、そのようなステート マシンを手動で構築する必要はなくなります。このステート マシンを生成するツールを作成できます。これの適切な背景は、FLEX または LALR パーサー ステート マシンの生成です。ここでは説明しません:-}

于 2012-05-11T03:17:06.307 に答える