Convertendo um CFG em IL

Question

Construo um CFG a partir de um IL arbitrário e quero converter esse CFG de volta para IL. É claro que a ordem dos vértices no CFG não é igual à ordem das instruções originais da IL.

Isso é bom, mas supercomplica algumas coisas. Imagine:

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

Isso resultaria em um gráfico de fluxo como este: (salto b) -> (salto c) -> (retornar) Este é, obviamente, um exemplo simplificado, mas mostra o problema ao converter fora do CFG.

Existe alguma informação disponível sobre este tópico na academia? Eu pensei que atravessar o gráfico de baixo para cima seria muito elegante, mas isso não funciona em casos mais complicados.

Uma solução pode ser andar de cima para baixo e procurar uma fusão de CF, mas nesse caso eu não seria capaz de lidar com os loops corretos. Portanto, a única maneira de acertar isso parece ser procurar uma possível mesclagem de CF se ocorrer. Caso contrário, precisamos ter um loop, o que significa que o loop é preferido e o caminho contínuo é avaliado posteriormente. Isso parece um problema solvável, mas também é muito caro e pode existir uma solução mais elegante para o problema. Além de um loop, também pode resultar em uma fusão de CF ao pensar em uma declaração "quebra".

Answer 1

Convertendo CFG em IL: Você deseja caminhar sobre o gráfico, emitindo cada vértice exatamente uma vez (exceto aqueles que são inacessíveis). Portanto, você precisa registrar quais vértices foram emitidos: uma bandeira no vértice faria ou um hash de vértice a verdadeiro/falso.

Alguns vértices terão mais de um sucessor, e você só poderá seguir um deles diretamente; Então, você quer uma maneira de acompanhar os vértices que deseja voltar mais tarde. Uma fila é adequada para isso.

Isso é mais ou menos o que eu usei.

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

O tratamento de ramos (vértices com mais de um sucessor) é bastante ingênuo: normalmente você deseja descobrir qual é o mais provável e segue isso diretamente, se possível.

Answer 2

Isso é mais fácil do que parece. Basicamente, pode -se se livrar de qualquer declaração de salto no CFG, o que resulta em um gráfico otimizado. As instruções de salto serão inseridas de volta assim que o gráfico estiver linearizado. Isso não mantém a ordem original das instruções, mas resulta em um método com o mesmo fluxo de controle.