Ershov 数による式の最適コードの生成 (その2)

ラベル付けアルゴリズムの続きです。昨日は、左辺レジスタに値を畳み込んでいくように変更し、最後に 2 オペランド形式に出力を修正して x86 っぽいリストを得るところまで遊びました。

ところで、最後のリストではレジスタ 2 個で計算できるはずなのに、レジスタ 3 個を使って計算しています。これは、元の Ershov 数を付けるとき、右辺が値のときもレジスタを割り当てていたからです。このような場合、右辺が値のときはレジスタを割り当てる必要がないので、必要なレジスタ数である Ershov 数をゼロにすれば良いはずです。もう一度同じ入力式をのラベルを付けなおしてみると、根の Ershov 数は 2 になって、計算に必要なレジスタ数が期待通りに減ります。

def ershov_numbering!(e)
  if e.left.value?
    e.left.ershov = 1
  else
    ershov_numbering!(e.left)
  end
  if e.right.value?
    e.right.ershov = 0
  else
    ershov_numbering!(e.right)
  end
  if e.left.ershov == e.right.ershov
    e.ershov = e.left.ershov + 1
  else
    e.ershov = e.left.ershov > e.right.ershov ? e.left.ershov : e.right.ershov
  end
  nil
end

ershov_numbering!(e)
p e  # (a:1 -:1 b:0) +:2 (e:1 *:2 (c:1 +:1 d:0))

コード生成手続きの修正箇所は 1 ヶ所だけです。右辺が値のノードは左辺と右辺で異なる Ershov 数になるので、b + 1 ではなく、b にしないといけません。

  if e.value?
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[b], e.op]
  elsif e.right.value?
    generate_left(e.left, b, op, reg, as)
#   generate_left(e.left, b + 1, op, reg, as)
    k = e.ershov
    as << "%8s%-8s%s, %s\n" % ['', op[e.op], reg[b+k-1], e.right.op]
  elsif e.left.ershov == e.right.ershov
    generate_left(e.left, b + 1, op, reg, as)
    generate_left(e.right, b, op, reg, as)
    k = e.ershov
    as << "%8s%-8s%s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+k-2]]

これで生成したコードは次のようにレジスタ 2 個だけで計算をおこないます。

        MOV     EBX, e
        MOV     EAX, c
        ADD     EAX, d
        IMUL    EBX, EAX
        MOV     EAX, a
        SUB     EAX, b
        ADD     EAX, EBX