1

任意の IL から CFG を構築し、その CFG を IL に変換したいと考えています。もちろん、CFG 内の頂点の順序は、元の IL 命令の順序と同じではありません。

これは問題ありませんが、いくつかのものが過度に複雑になります。想像：

Jump 'B'
'C': Return
'B': Jump 'C'

これは次のようなフロー グラフになります: (ジャンプ B) -> (ジャンプ C) -> (リターン) これはもちろん単純化された例ですが、CFG から変換するときの問題を示しています。

学界でこのトピックに関する情報はありますか? グラフをボトムアップでトラバースするのは非常にエレガントだと思いましたが、より複雑なケースではうまくいきません。

解決策は、トップダウンで歩いて CF マージを検索することかもしれませんが、その場合、ループを正しく処理できません。したがって、これを正しく行う唯一の方法は、可能性のある CF マージが発生した場合にそれを検索することのようです。そうでない場合は、ループが必要です。つまり、ループが優先され、その後に続くパスが評価されます。これは解決可能な問題のように思えますが、非常にコストがかかるため、問題に対するより洗練された解決策が存在する可能性があります。また、「break」ステートメントについて考えると、ループによって CF マージが発生する可能性もあります。

4

2 に答える 2

2

CFG を IL に変換する: グラフ上を歩き回り、各頂点を 1 回だけ放出します (到達できないものを除く)。したがって、どの頂点が放出されたかを記録する必要があります。頂点のフラグ、または頂点から True/False へのハッシュです。

一部の頂点には複数のサクセサーがあり、そのうちの 1 つだけを直接たどることができます。そのため、後で戻ってきたい頂点を追跡する方法が必要です。これにはキューが適しています。

これは多かれ少なかれ私が使用したものです。

def needs_label(cfg, v, last):
    if cfg.predecessors(v) > 1:
        # There's more than one way of entering this vertex
        return True
    elif cfg.predecessors(v) == 1 and last != cfg.predecessors(v)[0]:
        # There's only one way, but the last vertex emitted was not that way
        # so it will be entered using a jump.
        return True
    else:
        return False

def emit_label(v):
    print 'label%d' % (v.id)

def emit_vertex(v):
    if v.type == 'branch':
        # Branch to second successor
        print 'br label%d' % cfg.successors(v)[1].id
    else:
        ...

def emit_jump(v):
    print 'jmp label%d' % v.id

def emit_cfg(cfg):
    q = Queue()   # Queue for saving vertices that we want to emit later
    done = {}    # Hash recording which vertices have already been emitted
    q.push(cfg.start())
    while not q.empty():
        v = q.pop()
        last = None
        while v is not None and not done[v]:
            # Emit the vertex, with a prefixed label if necessary
            if needs_label(cfg, v, last):
                emit_label(v)
            emit_vertex(v)
            done[v] = True
            last = v
            # Get the vertex's successors
            succs = cfg.successors(v)
            # If there aren't any, then this path is finished, so go back to
            # the outer loop to pop another saved vertex
            if len(succs) == 0:
                v = None   # Setting this will terminate the inner loop
                continue
            # Stick all the vertices on the stack for later, in case we can't
            # process them all here
            for s in succs:
                q.push(s)
            # Pick a new vertex from the list of successors.  Always pick the first
            # because if it's a branch then the second will have been branched on
            v = succs[0]
            # If it was emitted earlier we need to jump to it
            if done[v]:
                emit_jump(v)
                v = None
            # Otherwise continue the inner loop, walking from the new vertex

ブランチ (複数のサクセサを持つ頂点) の処理は非常に単純です。通常、どちらが可能性が高いかを判断し、可能であればそのブランチを直接追跡します。

于 2009-11-16T01:06:30.013 に答える
0

これは思ったより簡単です。基本的に、最適化されたグラフをもたらす CFG 内の Jump ステートメントを取り除くことができます。グラフが線形化されると、ジャンプ ステートメントが挿入されます。これは命令の元の順序を保持しませんが、同じ制御フローを持つメソッドになります。

于 2009-08-31T12:53:51.467 に答える