將CFG轉換爲IL

Question

我使用任意IL構建CFG，並想將該CFG轉換回IL。 CFG中頂點的順序當然不等於原始IL指令的順序。

這很好，但過於複雜一些東西。想象：

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

這將導致一個流圖是這樣的：（跳轉B） - >（跳轉C） - >（返回） 當然，這是一個簡化的例子，但轉換出來時，它示出了該問題的CFG。

在學術界有沒有關於此主題的任何信息？我認爲自下而上遍歷圖將非常優雅，但在更復雜的情況下不起作用。

解決方案可能是自頂向下並搜索CF合併，但在這種情況下，我無法正確處理循環。所以唯一的辦法就是尋找可能的CF合併，如果它發生的話。如果沒有，我們必須有一個循環，這意味着循環是首選，並在之後評估連續路徑。這聽起來像是一個可解決的問題，但它也非常昂貴，並且可能存在更加優雅的解決方案。除了一個循環在考慮一個「break」語句時還可能導致CF合併。

Answer 1

將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 

治療是很天真：通常你想弄清楚這是更容易，直接跟着那一個，如果可能的話。

Answer 2

這比聽起來更容易。基本上可以擺脫CFG中的任何跳轉語句，從而得到優化的圖表。一旦圖形被線性化，跳轉語句將被插回。這不會保持指令的原始順序，但會產生具有相同控制流程的方法。