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に変換する：グラフ上を歩き回り、各頂点を正確に1回発光します（到達できないものを除く）。そのため、どの頂点が放出されたかを記録する必要があります：頂点のフラグが行う、または頂点から真/偽へのハッシュです。

いくつかの頂点には、複数の後続があり、それらのうちの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 

治療はかなりナイーブです：通常、あなたがより多くの可能性が高い把握し、可能な場合、直接その1をフォローしたいです。

Answer 2

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