Блог

Я уже сгенерировал соответствующий CFG моего исходного кода. Затем я хочу изменить CFG (объединить некоторые узлы). В конце концов, мне нужно преобразовать измененный CFG обратно в соответствующий исходный код. Как я мог это сделать? На данный момент я использую LLVM.

Это обманчиво сложная проблема. Обычно CFG упрощен так, что исходный код не может быть восстановлен. Например, циклы while и for заменяются тестами и инструкциями условного перехода. Я уверен, что это относится к промежуточной форме LLVM: s, так что вам не повезло.

Однако, если CFG не был упрощен, можно воссоздать абстрактное синтаксическое дерево программы (AST). Для этого вам необходимо располагать базовые блоки CFG в программном порядке. Это не сложно, поскольку это естественный порядок, который вы получаете при создании CFG. Вам также необходимо предварительно вычислить непосредственный доминатор каждого базового блока. Вы можете найти алгоритм для вычисления этого в статье Простой, быстрый алгоритм доминирования. Затем алгоритм выполняется следующим образом:

1. Для каждого блока, кроме первого:
   1. Проверьте, является ли этот блок прямым дочерним элементом его непосредственного доминатора. Т. е. является ли этот блок первым блоком в предложении while, for или if-else.
      1. Если да, добавьте блок к дочерним элементам его непосредственного доминатора.
      2. Если нет, пометьте этот блок как последователь его непосредственного доминатора.
2. Используйте собранные данные для построения AST следующим образом:
3. Пройдите данные последователя от первого блока в CFG до последнего блока, у которого нет последователя.
   1. Для каждого блока, который является for, if или while, повторите с шага 3, но начните с первого и второго дочернего элемента (в случае else) блока.

Вот некоторый код Python, который реализует алгоритм:

 from ast import *

class BasicBlock:
    def __init__(self, insns):
        self.insns = insns

    def type(self):
        return type(self.insns[-1]) if self.insns else None

def build_tree(bb, foll, children):
    nodes = []
    while bb:
        if not bb.insns:
            break
        last_insn = bb.insns[-1]
        childs = children[bb]
        tp = bb.type()
        if tp in (For, If, While):
            last_insn.body = 
                build_tree(childs[0], foll, children)
            if len(childs) == 2:
                last_insn.orelse = 
                    build_tree(childs[1], foll, children)
        nodes.extend(bb.insns)
        bb = foll.get(bb)
    return nodes

def is_dom_child(bb, dom_bb, succ):
    childs = succ[dom_bb]
    if bb in childs:
        tp = dom_bb.type()
        if tp in (If, For, While) and childs[0] == bb:
            return True
        if (tp == If and bb == childs[1] and
            not reachable(succ, childs[0], childs[1], {dom_bb})):
            return True
    return False

def bbs_to_ast(bbs, succ, idoms):
    foll = {}
    children = defaultdict(list)
    for bb in bbs[1:]:
        dom_bb = idoms[bb]
        if is_dom_child(bb, dom_bb, succ):
            children[dom_bb].append(bb)
        else:
            foll[dom_bb] = bb
    nodes = build_tree(bbs[0], foll, children)
    return Module(nodes, [])

def print_bbs(bbs, succ, idoms):
    mod = bbs_to_ast(bbs,  succ, idoms)
    return unparse(mod)