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