Conversion d'un CFG en IL

Question

Je construis un CFG à partir d'un IL arbitraire et je veux convertir ce CFG en IL. L'ordre des sommets dans le CFG n'est bien sûr pas égal à l'ordre des instructions IL originales.

C'est très bien mais trop compliqué. Imaginez:

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

Cela se traduirait par un graphique de flux comme ceci: (Jump B) -> (Jump C) -> (retour) Ceci est bien sûr un exemple simplifié, mais il montre le problème lors de la conversion des du CFG.

Y at-il des informations disponibles sur ce sujet dans le milieu universitaire? Je pensais que traverser le graphique du bas vers le haut serait très élégant, mais cela ne fonctionne pas dans les cas plus compliqués.

Une solution pourrait être de marcher de haut en bas et de rechercher une fusion CF, mais dans ce cas, je ne serais pas en mesure de gérer correctement les boucles. Donc, la seule façon d'obtenir ce droit semble être de rechercher une fusion CF possible si cela se produit. Sinon, nous devons avoir une boucle, ce qui signifie que la boucle est préférée et que le chemin continu est évalué par la suite. Cela ressemble à un problème résoluble, mais il est également très coûteux et il pourrait exister une solution plus élégante au problème. En outre, une boucle peut également entraîner une fusion CF en pensant à une déclaration de "break".

Answer 1

Conversion de CFG en IL: vous voulez parcourir le graphique, en émettant chaque sommet exactement une fois (sauf ceux qui sont inaccessibles). Vous avez donc besoin d'enregistrer quels sommets ont été émis: un drapeau sur le sommet ferait l'affaire, ou un hachage de vertex à True/False.

Certains sommets auront plus d'un successeur, et vous ne pouvez en suivre qu'un seul directement; donc vous voulez un moyen de garder une trace des sommets que vous souhaitez revenir plus tard. Une file d'attente est appropriée pour cela.

C'est plus ou moins ce que j'ai utilisé.

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 

Traitement des branches (sommets avec plus d'un successeur) est assez naïve: normalement, vous voulez savoir ce qui est plus probable et que l'on suivre directement, si possible.

Answer 2

C'est plus facile que ça en a l'air. Fondamentalement, on peut se débarrasser de toutes les instructions Jump dans le CFG qui résulte en un graphique optimisé. Les instructions de saut seront insérées une fois le graphique linéarisé. Cela ne conserve pas l'ordre original des instructions mais aboutit à une méthode avec le même flux de contrôle.