将CFG转换为IL:您希望遍历图形,每个顶点只发射一次(无法到达的顶点除外)。因此,您需要记录已发射的顶点:顶点上的标志可以,或者从顶点散列为True/False。
某些顶点将有多个后继顶点,您只能直接跟随其中一个;因此,您需要一种方法来跟踪稍后要返回的顶点。队列适用于此。
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
对分支(具有多个后续分支的顶点)的处理非常简单:通常,您希望找出哪一个更可能,如果可能的话,直接遵循该分支。
