将CFG转换为IL

我使用任意IL构建CFG，并想将该CFG转换回IL。 CFG中顶点的顺序当然不等于原始IL指令的顺序。将CFG转换为IL

这很好，但过于复杂一些东西。想象：

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

这将导致一个流图是这样的：（跳转B） - >（跳转C） - >（返回）当然，这是一个简化的例子，但转换出来时，它示出了该问题的CFG。

在学术界有没有关于此主题的任何信息？我认为自下而上遍历图将非常优雅，但在更复杂的情况下不起作用。

解决方案可能是自顶向下并搜索CF合并，但在这种情况下，我无法正确处理循环。所以唯一的办法就是寻找可能的CF合并，如果它发生的话。如果没有，我们必须有一个循环，这意味着循环是首选，并在之后评估连续路径。这听起来像是一个可解决的问题，但它也非常昂贵，并且可能存在更加优雅的解决方案。除了一个循环在考虑一个“break”语句时还可能导致CF合并。

来源

2009-08-27 Joa Ebert

将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

治疗是很天真：通常你想弄清楚这是更容易，直接跟着那一个，如果可能的话。

来源

2009-11-16 01:06:30 Edmund

一条指令需要一个标签，因为它是一个基本块的领导者，它没有前任，或者多于一个前辈，或者只有一个前辈，但是前辈具有多于一个后辈。 – inv 2010-08-04 00:56:23

这比听起来更容易。基本上可以摆脱CFG中的任何跳转语句，从而得到优化的图表。一旦图形被线性化，跳转语句将被插回。这不会保持指令的原始顺序，但会产生具有相同控制流程的方法。

来源

2009-08-31 12:53:51

将CFG转换为IL

回答

相关问题