Ershov 数による式の最適コードの生成

ドラゴンブック (ISBN978-4-7819-1229-5)「8.10 式の最適コードの生成」のアルゴリズム 8.24 「ラベル付けアルゴリズム」で遊んでみます。 このアルゴリズムは、四則演算の式の 2 分木からレジスタを割り当てたいとき、レジスタが足りている場合を扱います。論文リストにある元論文を読んでないので良くわかってないのですけど、これは 1958 年に Andrei P. Ershov がロシア語論文で発表したもののようです。レジスタが不足する場合は、続くアルゴリズム 8.26 で扱ってますが、今回はパスします。

このアルゴリズムでは、式の木のノードに Ershov 数を追記したものを扱います。この数は、ノードの部分式を評価するのに必要なレジスタの個数に一致します。演算子のノードは op に演算子名を、値および変数のノードは左右が nil で op にオペランドを書くことにします。

class Node
  attr_accessor :op, :ershov, :left, :right

  def initialize(op, ershov, left, right)
    @op, @ershov, @left, @right = op, ershov, left, right
  end

  def value?() @left.nil? or @right.nil? end
end

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

ドラゴンブック例 8.23 の式の 2 分木 e の Ershov 数を計算する手続きを定義します。ここでは横着して、破壊的に e のノードの ershov 属性に書き込んでいます。

def ershov_numbering!(e)
  if e.value?
    e.ershov = 1
  else
    ershov_numbering!(e.left)
    ershov_numbering!(e.right)
    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
  end
  nil
end

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

アルゴリズム 8.24 は、Ershov 数が付いた 2 分木 e を右から左へ辿って、レジスタを割り当てつつ、3 オペランドの命令を生成します。生成される命令は、式の右から左へとおこなわれていき、右辺用のレジスタに値を求めます。なぜ、右から左なのか、右辺用のレジスタなのか謎です。レジスタは b 番から b + k - 1 番までを使い、 b + k - 1 番に式の値が求まります。

def generate_right(e, b, op, reg, as)
  if e.value?
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[b], e.op]
  elsif e.left.ershov == e.right.ershov
    generate_right(e.right, b + 1, op, reg, as)
    generate_right(e.left, b, op, reg, as)
    k = e.ershov
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+k-2], reg[b+k-1]]
  elsif e.left.ershov > e.right.ershov
    generate_right(e.left, b, op, reg, as)
    generate_right(e.right, b, op, reg, 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
    generate_right(e.right, b, op, reg, as)
    generate_right(e.left, b, op, reg, as)
    k = e.ershov; m = e.left.ershov
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+m-1], reg[b+k-1]]
  else
    raise 'cannot happen'
  end
  as
end

opcode = {'LD' => 'LD', '+' => 'ADD', '-' => 'SUB', '*' => 'MUL'}
reg = (0 .. 7).collect{|i| "R#{i}" }
print generate_right(e, 1, opcode, reg, '')

このアルゴリズムなら、左右対称にしても動くだろうと思われ、その場合は、2 分木 e を左から右へ辿らせることができるだろうと考えられます。やってみましょう。

def generate_left(e, b, op, reg, as)
  if e.value?
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[b], e.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, %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_left(e.left, b, op, reg, as)
    generate_left(e.right, b, op, reg, 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
    generate_left(e.right, b, op, reg, as)
    generate_left(e.left, b, op, reg, as)
    k = e.ershov; m = e.left.ershov
    as << "%8s%-8s%s, %s, %s\n" % ['', op[e.op], reg[b+k-1], reg[b+m-1], reg[b+k-1]]
  else
    raise 'cannot happen'
  end
  as
end

print generate_left(e, 1, opcode, reg, '')

出力は期待したとおり、ドラゴンブック図 8.24 の generate_right の出力を左右逆にしたものになります。乗算の箇所を除くと、左辺用のレジスタに値を求めており、どちらかというとこっちの方が自然に感じます。

generate_left の出力: 命令  dst, src1, src2 で dst = src1 '命令' src2 形式

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

3 オペランド命令のプロセッサならこれでいいのですけど、x86x86_64 の 2 オペランド命令では上の乗算のような場合でも左辺用のレジスタに値を求めて欲しくなります。安直に実装するなら、MUL 命令の前に SWAP 命令を追加すれば良いのかもしれませんけど、 SWAP 命令追加で済むのは可換演算の加算と乗算で、減算と除算には通用しません。減算と除算でも左辺レジスタに値を畳み込むためには、左辺と右辺の位置関係を変えずに演算できるようにしなければいけません。それなら、レジスタのリスト自体をひっくり返して命令を出力させればよさそうです。

  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_left(e.right, b, op, reg, as)
    generate_left(e.left, b, op, reg, 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

これですべて左辺用レジスタに値を求めていくようになります。

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

それでは 2 オペランドにしましょう。ちょっとした工夫をして、式の値を EAX レジスタに求める*1ようにします。

def generate_left(e, b, op, reg, as)
  if e.value?
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[b], e.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]]
  elsif e.left.ershov > e.right.ershov
    generate_left(e.left, b, op, reg, as)
    generate_left(e.right, b, op, reg, as)
    k = e.ershov; m = e.right.ershov
    as << "%8s%-8s%s, %s\n" % ['', op[e.op], 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_left(e.right, b, op, reg, as)
    generate_left(e.left, b, op, reg, as)
    as << "%8s%-8s%s, %s\n" % ['', op[e.op], 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

x86opcode = {'LD' => 'MOV', '+' => 'ADD', '-' => 'SUB', '*' => 'IMUL'}
x86reg = ['EDI', 'ESI', 'EDX', 'ECX', 'EBX', 'EAX']
print generate_left(e, x86reg.size - e.ershov, x86opcode, x86reg, '')

出力はインテル形式のそれらしいものになります。

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

x86CISC なので、右辺が値のときは、レジスタにいちいちロードせずに、直接演算命令の第 2 オペランドに渡してしまってもかまわないでしょう。

  if e.value?
    as << "%8s%-8s%s, %s\n" % ['', op['LD'], reg[b], e.op]
  elsif e.right.value?
    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]]

これでようやく x86 用らしい出力になります。

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

http://d.hatena.ne.jp/tociyuki/20140509/1399625045 最後の例のレジスタ数を最適化された 2 個に減らします。

*1:レジスタ指定を交換することがあるので、常にEAXへ値が求まる保証がないので、この工夫をする意義はありません。