Преобразование CFG в IL

Question

Я строю CFG из произвольного IL и хочу преобразовать этот CFG обратно в IL. Порядок вершин в CFG, конечно, не равен порядку исходных инструкций IL.

Это нормально, но слишком сложно. Представьте:

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

Это приведет к графике потока, как это: (Перейти B) -> (Перейти С) -> (Возврат) Это, конечно, упрощенный пример, но он показывает проблему при преобразовании из от CFG.

Есть ли какая-либо информация по этой теме в academia? Я думал, что пересечение графика снизу вверх будет очень элегантным, но это не работает в более сложных случаях.

Решение может состоять в том, чтобы ходить сверху вниз и искать слияние CF, но в этом случае я не смог бы правильно обрабатывать петли. Таким образом, единственный способ получить это право - это поиск возможного слияния CF, если это произойдет. Если нет, мы должны иметь цикл, который означает, что цикл является предпочтительным, а последующий путь оценивается впоследствии. Это звучит как решаемая проблема, но она также очень дорога, и может возникнуть более элегантное решение проблемы. Кроме того, цикл может также приводить к слиянию CF, когда вы думаете о выражении «break».

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

Это проще, чем кажется. В принципе, можно избавиться от любых высказываний Jump в CFG, что приводит к оптимизации графика. Операторы перехода будут вставляться обратно после линеаризации графика. Это не сохраняет первоначальный порядок инструкций, но приводит к методу с одним и тем же потоком управления.