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

レジスタが足りているときの Ershov 数をラベル付けした式の木からコード生成する手順に、途中結果のメモリ退避を加えてレジスタが不足している場合を扱えるようにするのが、ドラゴンブック (ISBN978-4-7819-1229-5) のアルゴリズム 8.26 で、 これは Sethi-Ullman アルゴリズムの一種です。オリジナルは、相変わらず、右辺レジスタに値を畳み込む機械命令を生成するようになっているので、今回もアレンジして、なるべく左から右へ式をたどりつつ、左辺レジスタに値を畳み込むように改めます。

ところで、退避するメモリをシンボルで表すとき、ドラゴンブックの説明を読むとノードの Ershov 数を使えばシンボルが生成できるかのように錯覚しますが、次に示す例のように同じ Ershov 数が付いたノードが入れ子になっている場合があるわけで、シンボルをその都度別々に生成していくのが正解なのは明かです。

    ((a:1 -:2 b:1) *:3 (c:1 +:2 d:1)) +:3 (e:1 *:2 (f:1 +:2 g:1))

シンボル生成は、ここでは手抜きして t の文字に通番をくっつけることにします。

class Symgenerator
  def initialize
    @n = -1
  end
  def gensym
    @n += 1
    "t#{@n}"
  end
end

まず、右辺にある値の Ershov 数を 1 にしたもので動かしてみます。

def ershov_numbering!(e)
#略
  if e.right.value?
    e.right.ershov = 1
#    e.right.ershov = 0
  else
    ershov_numbering!(e.right)
  end
#略
  nil
end

レジスタが足りているコードの演算子ノードの前に、レジスタが不足しているときにメモリ退避を伴うコード生成部分を追加します。メモリ退避を伴う場合、右辺レジスタへの畳み込みがおこなわれる場合にレジスタを交換しておくようにします。

def generate(e, b, op, reg, tmp, as)
  r = reg.size
  if e.value?
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[b], e.op]
  elsif e.ershov > r and e.left.ershov >= r
    reg[r-1], reg[r-2] = reg[r-2], reg[r-1]
    generate(e.left, 0, op, reg, tmp, as)
    t_k = tmp.gensym
    as << "%8s%-8s%s, %s\n" % ['', op['ST'], t_k, reg[r-1]]
    j = e.right.ershov
    b1 = if j >= r then 0 else r - j - 1 end
    generate(e.right, b1, op, reg, tmp, as)
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[r-2], t_k]
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[r-2], reg[r-2], reg[r-1]]
    reg[r-1], reg[r-2] = reg[r-2], reg[r-1]
  elsif e.ershov > r #and e.right.ershov >= r
    generate(e.right, 0, op, reg, tmp, as)
    t_k = tmp.gensym
    as << "%8s%-8s%s, %s\n" % ['', op['ST'], t_k, reg[r-1]]
    j = e.left.ershov
    b1 = if j >= r then 0 else r - j - 1 end
    generate(e.left, b1, op, reg, tmp, as)
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[r-1], reg[r-1], t_k]
#  elsif e.right. value?
#    generate(e.left, b, op, reg, tmp, as)
#    k = e.ershov
#    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+k-1], e.right.op]
  elsif e.left.ershov == e.right.ershov
    generate(e.left, b + 1, op, reg, tmp, as)
    generate(e.right, b, op, reg, tmp, as)
    k = e.ershov
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+k-1], reg[b+k-2]]
  elsif e.left.ershov > e.right.ershov
    generate(e.left, b, op, reg, tmp, as)
    generate(e.right, b, op, reg, tmp, as)
    k = e.ershov; m = e.right.ershov
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+k-1], reg[b+m-1]]
  elsif e.left.ershov < e.right.ershov
    k = e.ershov; m = e.left.ershov
    reg[b+m-1], reg[b+k-1] = reg[b+k-1], reg[b+m-1]
    generate(e.right, b, op, reg, tmp, as)
    generate(e.left, b, op, reg, tmp, as)
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+m-1], reg[b+m-1], reg[b+k-1]]
    reg[b+m-1], reg[b+k-1] = reg[b+k-1], reg[b+m-1]
  else
    raise 'cannot happen'
  end
  as
end

これで、レジスタ数が 2 個のとき、式 (a - b) + (e * (c + d)) からコードを生成してみます。

ershov_numbering!(e)

opcode = {'LD' => 'LD', 'ST' => 'ST', '+' => 'ADD', '-' => 'SUB', '*' => 'MUL'}
reg = ['R1', 'R2']
tmp = Symgenerator.new

print generate(e, 0, opcode, reg, tmp, '')

一時変数を使いながら、左辺レジスタに値を畳み込む機械命令を生成します。

        LD      R1, a
        LD      R2, b
        SUB     R1, R1, R2
        ST      t0, R1
        LD      R2, c
        LD      R1, d
        ADD     R2, R2, R1
        LD      R1, e
        MUL     R1, R1, R2
        LD      R2, t0
        ADD     R2, R2, R1

さらに複雑な式でやってみます。

# ((a - b) * (c + d)) + (e * (f + g))
e = Node.new('+', 0,
      Node.new('*', 0,
        Node.new('-', 0,
          Node.new('a', 0, nil, nil),
          Node.new('b', 0, nil, nil)),
        Node.new('+', 0,
          Node.new('c', 0, nil, nil),
          Node.new('d', 0, nil, nil))),
      Node.new('*', 0,
        Node.new('e', 0, nil, nil),
        Node.new('+', 0,
          Node.new('f', 0, nil, nil),
          Node.new('g', 0, nil, nil))))

今度は、一時変数が 2 個になります。

        LD      R2, a
        LD      R1, b
        SUB     R2, R2, R1
        ST      t0, R2
        LD      R2, c
        LD      R1, d
        ADD     R2, R2, R1
        LD      R1, t0
        MUL     R1, R1, R2
        ST      t1, R1
        LD      R2, f
        LD      R1, g
        ADD     R2, R2, R1
        LD      R1, e
        MUL     R1, R1, R2
        LD      R2, t1
        ADD     R2, R2, R1

続いて、右辺が値のときにレジスタにロードしない機械命令を生成してみます。

def ershov_numbering!(e)
#略
  if e.right.value?
#   e.right.ershov = 1
    e.right.ershov = 0
  else
    ershov_numbering!(e.right)
  end

def generate(e, b, op, reg, tmp, as)
#略
  elsif e.right. value?
    generate(e.left, b, op, reg, tmp, as)
    k = e.ershov
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+k-1], e.right.op]
  elsif e.left.ershov == e.right.ershov

一時変数が一つに減った機械命令になります。

        LD      R1, a
        SUB     R1, R1, b
        LD      R2, c
        ADD     R2, R2, d
        MUL     R1, R1, R2
        ST      t0, R1
        LD      R1, e
        LD      R2, f
        ADD     R2, R2, g
        MUL     R1, R1, R2
        LD      R2, t0
        ADD     R2, R2, R1

レジスタの退避を伴うときも、左辺レジスタに値を畳み込んでいくコードを生成できました。それでは、これを x86 用に使えるかというと、残念ながら x86 の整数除算命令 DIV および IDVI の左辺レジスタは、レジスタ対 EDX EAX 固定です。ラベル付き木からのコード生成は、全部のレジスタが汎用であることを前提にしているため、x86 の除算を扱うことができません。式の木の大きさに対する線形時間でのレジスタ割り当てを x86 でおこなうには、EDX と EAX を外した 4 個のレジスタでおこなうか、除算命令をレジスタ退避とレジスタの値移動の組み合わせに変えてコード生成するのがてっとり早いのでしょう。凝るなら、実レジスタを割り当てるのではなく、仮想レジスタの組み合わせ集合を割り当てておいてから、後処理で実レジスタの割り当てをおこなっても良いのでしょう。面倒なことです。