Conversión de un CFG a IL

Question

construyo una CFG de un IL arbitraria y quiero convertir ese CFG volver a IL. El orden de los vértices en el CFG es, por supuesto, no es igual al orden de las instrucciones originales IL.

Esto está muy bien, pero overcomplicates algunas cosas. Imagínese:

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

Esto daría lugar a un gráfico de flujo de la siguiente manera: (Ir B) -> (Ir C) -> (Return) Esto es por supuesto un ejemplo simplificado pero muestra el problema cuando la conversión de la CFG.

¿Hay alguna información disponible sobre este tema en el mundo académico? Pensé que atraviesan el gráfico de abajo hacia arriba sería muy elegante, pero que no funciona en casos más complicados.

Una solución podría ser la de caminar de arriba hacia abajo y la búsqueda de un CF fusionar pero en ese caso no sería capaz de manejar los bucles correcta. Así que la única manera de conseguir este derecho parece ser la de buscar una posible fusionar CF si se produce. Si no es así, tenemos que tener un bucle, lo que significa que se prefiere el bucle y continuar el camino se evalúa después. Esto suena como un problema solveable pero también es muy caro y no puede existir una solución más elegante al problema. Además de un bucle también podría dar lugar a una fusión CF cuando se piensa en un comunicado "romper".

Answer 1

La conversión de CFG en IL: quieres caminar sobre el gráfico, emitiendo cada vértice exactamente una vez (excepto los que son inalcanzables). Así que hay que registrar qué vértices han sido emitida:. Una bandera en el vértice haría, o un hash desde el vértice a Verdadero / Falso

Algunos vértices tendrán más de un sucesor, y sólo se puede seguir uno de ellos directamente; por lo que desea una forma de mantener un registro de los vértices que desea volver a más tarde. Una cola es adecuado para esto.

Esto es más o menos lo que he usado.

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

Tratamiento de las sucursales (vértices con más de un sucesor) es bastante ingenua:. Normalmente desea averiguar cuál es más probable que uno y seguir directamente, si es posible

Answer 2

Esto es más fácil de lo que suena. Básicamente uno puede librarse de cualquier declaración salto en la CFG que se traduce en un gráfico optimizado. sentencias de salto se insertarán atrás una vez se linealiza el gráfico. Esto no mantiene el orden original de las instrucciones, pero los resultados en un método con el mismo flujo de control.