コンパイラでコードを最適化した後に一時変数を取り除く

Question

私はコンパイラの静的解析モジュールを、古典的な書籍のコンパイラの指示に従って作成しています。 Ullmanらによる原理、技法およびツール。

AST表現を3つのアドレスコード表現に変換して最適化（基本的にはデッドコードの除去とコピーの伝播）を行い、同様の3つのアドレスコード表現（バイトコードに変換する方が適しています）に変換します。そのために

、私は私のコード表現は、このようになりますように、一時的な変数を作成する必要があります。

t = IntLit(0) 
t1 = left < right 
t2 = !t1 
cjump if t2 to L0: 
t3 = number[right] 
v = t3 
t4 = left - IntLit(1) 
i = t4 
j = right 
cont01 = True() 
L2: 
t5 = !cont01 
cjump if t5 to L3: 
cont02 = True() 
L4: 
t6 = !cont02 
cjump if t6 to L5: 
t7 = i + IntLit(1) 
i = t7 
t8 = number[t7] 
Removed dead code: aux03 = t8 
t10 = t8 < v 
t9 = !t10 
t11 = !t9 
cjump if t11 to L6: 
cont02 = False() 
jump L7: 
L6: 
cont02 = True() 
L7: 
jump L4: 
L5: 
cont02 = True() 
L8: 
t12 = !cont02 
cjump if t12 to L9: 
t13 = j - IntLit(1) 
j = t13 
t14 = number[t13] 
Removed dead code: aux03 = t14 
t16 = v < t14 
t15 = !t16 
t17 = !t15 
cjump if t17 to L10: 
cont02 = False() 
jump L11: 
L10: 
cont02 = True() 
L11: 
jump L8: 
L9: 
t18 = number[i] 
t = t18 
t19 = number[j] 
number[i] = t19 
number[j] = t18 
t21 = i + IntLit(1) 
t20 = j < t21 
t22 = !t20 
cjump if t22 to L12: 
cont01 = False() 
jump L13: 
L12: 
cont01 = True() 
L13: 
jump L2: 
L3: 
t23 = number[i] 
number[j] = t23 
t24 = number[right] 
number[i] = t24 
number[right] = t 
t25 = i - IntLit(1) 
t26 = This().Sort(left,t25) 
Removed dead code: nt = t26 
t27 = i + IntLit(1) 
t28 = This().Sort(t27,right) 
Removed dead code: nt = t28 
jump L1: 
L0: 
Removed dead code: nt = IntLit(0) 
L1: 
return IntLit(0) 

私は、コード生成のための一時的な変数を取り除くたかったが、私はできないように私には見えます。私は、次のコードを取得

def printing() : Int = { 
    var i : Int; 
    var j : Int; 
    var z : Int; 

    i = this.printing1(); 
    z = i; 
    println(z); 

    return i; 
    } 

：：私は一時的な変数を削除するには何をやっている

t1 = This().printing1() 
Removed dead code: i = t1 
Removed dead code: z = t1 
println(t1) 
return t1 

は先に自分の価値を伝播することで、以下の方法を考えてみましょう。通常の状況では、私はただ一つのコピーが必要です。しかし、コピーの伝播では、私はそれを何度も行う必要があります。

これは問題ありませんが、コードの削除と組み合わせてください。メソッド呼び出しが非一時変数に割り当てられることは保証できません（上記のコードを参照）。

したがって、一時変数がメソッド呼び出しの結果を格納する前に1つだけ存在する場合、私は明らかにそのメソッド呼び出しをコピーして終了することができます。存在しないときは、POP命令でスタックから結果を取り除くことができます。しかし、複数の出現があるときは、私はいくつかの呼び出しを得るため、指示をコピーできません。

私の結論は、私は一時的な変数を維持する必要があるということです。

一時変数のリードを得るのに役立つ別の戦略がありますか？

Answer 1

現在の内部表現（つまりAST）を使用してすべての一時変数を取り除くことは可能かどうかわかりませんが、レジスタ割り当てアルゴリズムを使用してその量を減らすことができます。

毎回、新しい一時変数を生成するようにコードで調べます。これは、コンパイラが（単純化のために）CPUに無限のレジスタがあると仮定した場合の問題に似ています。そして、アーキテクチャが持つ有限のレジスタを実際に使用するコードを生成する必要があります。無限のレジスタ/変数からより小さい有限集合に減らすために、レジスタ割り当てアルゴリズムが使用される。

テーマについては、Engineering a Compiler by Keith Cooperの書籍全体（13）を参照してください。私の心に来た何how this is done in real compilers like GCC.

上の多くの情報もあり

は、レジスタなどの変数を考え、その後、必要最小限にその数を減らすために、レジスタ割り当てアルゴリズムを使用することです。

この考えは明らかに私の10セントです。コンパイラを設計することは実際にはあなたの実際の問題を解決するために深いコラボレーションを必要とする非常に複雑な問題です。