Преобразование CFG в IL - PullRequest
Новая
       32

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

1 голос
/ 27 августа 2009

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

Это хорошо, но некоторые вещи усложняют. Представьте себе: 

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

Это приведет к созданию потокового графа, подобного следующему: (переход B) -> (переход C) -> (возврат) Это, конечно, упрощенный пример, но он показывает проблему при конвертации из CFG.

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

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

Ответы [ 2 ]

2 голосов
/ 16 ноября 2009

Преобразование 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

Обработка ветвей (вершин с более чем одним преемником) довольно наивна: обычно вы хотите выяснить, какая из них более вероятна, и, если возможно, следовать ей напрямую.

0 голосов
/ 31 августа 2009

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

...