Декомпилятор - как структурировать циклы

Структурирование — самая сложная часть разработки декомпилятора (по крайней мере, для языков высокого уровня). Это довольно упрощенный алгоритм, так что это хорошая отправная точка, но вы, вероятно, захотите использовать лучший алгоритм или создать свой собственный, если вы работаете над настоящим декомпилятором.

С учетом этого ответ на ваш актуальный вопрос о том, как он может использовать циклы do-while вместо циклов while, уже есть на странице, на которую вы ссылаетесь.

Каждый цикл можно описать оператором «do-while».

Цикл while (предварительно проверенный цикл) — это частный случай цикла do-while, где нижнее условие всегда истинно, а первый оператор цикла — это «если», выпрыгивающий из цикла. .

Скажи, что у тебя было что-то вроде

beforeloop
while(foo) {
stmt1
stmt2
}
afterloop

Он будет скомпилирован во что-то вроде строк

beforeloop

LOOPBEGIN:
if !foo goto LOOPEND
stmt1
stmt2
goto LOOPBEGIN

LOOPEND:
afterloop

Алгоритм декомпилятора преобразует это в

beforeloop
do {
if (!foo) {break}
stmt1
stmt2
} while (true)
afterloop

Я надеюсь, что это прояснилось. Если нет, не стесняйтесь задавать любые другие вопросы.

Редактировать: пример 2, показывающий, как можно свернуть несколько циклов с одной и той же точкой входа.

for(;;) { while(foo) {} while(bar){} }

Во-первых, for(;;) эквивалентно while(true), поэтому вместо этого я буду использовать следующий (псевдо)код

while(true) { while(foo) {stmt1} while(bar){stmt2} }

Пусть внешний цикл будет циклом A, а внутренние циклы будут циклами B и C. Это компилируется во что-то вроде следующей псевдосборки.

LOOP_A_BEGIN:
LOOP_B_BEGIN:
if !foo goto LOOP_B_END
stmt1
goto LOOP_B_BEGIN
LOOP_B_END:
LOOP_C_BEGIN:
if !bar goto LOOP_C_END
stmt2
goto LOOP_C_BEGIN
LOOP_C_END:
goto LOOP_A_BEGIN

Но, конечно, ярлыки не занимают места. Таким образом, при сворачивании одинаковых ярлыков становится

POINT1:
if !foo goto POINT2
stmt1
goto POINT1
POINT2:
if !bar goto POINT3
stmt2
goto POINT2
POINT3
goto POINT1

Теперь есть две точки с задними ребрами — точка 1 и точка 2. Мы можем создать один цикл для каждого узла, используя для ясности помеченные разрывы. Преобразование не такое прямолинейное, так как вам придется немного возиться с операторами if, но оно все же довольно простое.

LOOP1: while(true) {
    IF1: if (!foo) {
        break IF1;
    }
    else {
        stmt1;
        continue LOOP1;
    }

    LOOP2: while(true) {
        if (!bar) {
            break LOOP2;
        }
        else {
            stmt2;
            continue LOOP2;
        }
    }

    continue LOOP1;
}

Теперь тот же код с ненужными метками упростился.

while(true) {
    if (!foo) {
    }
    else {
        stmt1;
        continue;
    }

    while(true) {
        if (!bar) {
            break;
        }
        else {
            stmt2;
        }
    }
}

Теперь с упрощенными операторами if

while(true) {
    if (foo) {
        stmt1;
        continue;
    }

    while(true) {
        if (!bar) {
            break;
        }
        stmt2;
    }
}

И, наконец, вы можете применить преобразование while(true) if(!x) к внутреннему циклу. Внешний цикл не может быть преобразован таким образом, так как это не простой цикл while(cond) из-за того, что он является результатом объединенных циклов.

while(true) {
    if (foo) {
        stmt1;
        continue;
    }

    while(bar) {
        stmt2;
    }
}

Так что, надеюсь, это демонстрирует, как вы всегда можете обрабатывать случай нескольких циклов с одной и той же точкой входа, объединяя их в один цикл, возможно, за счет необходимости переупорядочивать некоторые операторы if.

Есть статья под названием Больше не нужно, в которой предлагается алгоритм независимое структурирование потока управления. Это хороший кусок работы для понимания и реализации, но я использую его для своего старшего проекта, и похоже, что он работает.

Моя реализация доступна на GitHub по адресу zneak/fcd. Проект использует LLVM IR в качестве промежуточного представления.

EDIT На очень высоком уровне алгоритм работает следующим образом:

Доминирование

Просто чтобы убедиться, что эти концепции понятны: узел A доминирует над узлом Z, если любой путь от входа в граф до Z должен проходить через A. Точно так же узел Z постдоминирует над узлом Z. node A, если любой путь от A до конца графа должен проходить через Z.

Регионы

Алгоритм структурирует регионы. Регион — это часть графа, которая имеет одно ребро входа и одно ребро выхода. Я лично расширил это определение на базовые блоки (регионы имеют один блок входа и один блок выхода) и сделал так, чтобы блок выхода был исключен из региона.

Я использую следующее определение региона:

• Узел входа доминирует над узлом выхода;
• Узел выхода постдоминирует над узлом входа;
• Как только вы достигнете выхода, любой путь, который приведет вас обратно в регион, проходит через входной узел. (Этот последний бит очень важен и решает проблемы, связанные с циклами.)

Определение подразумевает, что вход доминирует над каждым узлом через выходной узел, а выходной узел доминирует над каждым узлом из входа.

Нормализация циклов

Петля — это область с «обратным краем» (узел с краем, возвращающимся к уже посещенному узлу, если вы прошли граф в глубину).

Убедитесь, что циклы представлены как регионы с одним входом и одним выходом с одним обратным краем. То есть у них должен быть только один входной узел (на который также указывает заднее ребро) и один преемник. Когда это не так, вы можете ввести новый входной блок и сделать так, чтобы все ребра указывали на него, а затем использовать Φ-узел для перенаправления выполнения оттуда (другими словами, ввести переменную, которую вы устанавливаете в конце каждого входящего блока). блок и выполните if (var == 0) { first entry } else if (var == 1) { second entry } из нового блока).

В моей реализации это происходит на этапе StructurizeCFG в ветке master, на момент написания. Однако он дает плохие результаты, потому что работает гораздо усерднее, чем нужно. Мне это нужно только для структурирования циклов, но оно также структурирует конструкции if-else, и, хотя это не нарушает алгоритм, оно вводит waaaay во многие Φ-узлы, чтобы получить красивый результат. На момент написания также существует ветка под названием seseloop с пользовательским проходом, чтобы убедиться, что циклы имеют один вход и один выход. Этот проход не затрагивает конструкции if-else, если в этом нет необходимости.

Структурируйте свои функции

Пройдите базовый блок-граф в обратном порядке. Определите регионы, начиная с этого блока. Вы можете использовать дерево пост-доминаторов, чтобы немного ускорить это, так как область должна заканчиваться пост-доминаторами блока (поэтому для каждого блока проверяйте только пост-доминаторы блока).

Если входной блок имеет задний край, указывающий на него, структурируйте его как петлю. Если нет, структурируйте его как регион. Когда регион структурирован, поместите его обратно на график в виде свернутого отдельного узла, который можно включить в другой более крупный структурированный регион.

Это происходит в ast/ast_backend.cpp.

Структурирование регионов

Используйте обход в глубину (пропуская циклы) в области, чтобы определить условие, приводящее к выполнению любого блока. Например:

Узел A не имеет условий. Узел B достигается, если условие в конце узла A истинно. Узел C достигается, если он ложный. Узел D достигается, если он был либо истинным, либо ложным.

(A);
if (a_cond) (B);
if (!a_cond) (C);
if (a_cond || !a_cond) (D);

Затем вам придется упростить эти условия, что, к сожалению, является NP-полной задачей. В общем, не должно быть слишком сложно вернуться к чему-то вроде A; if (a_cond) B; else C; D;, свернув a_cond || !a_cond и сравнив условные термины по порядку.

Структурирующие циклы

В основном вы делаете то же самое, как если бы вы структурировали регион, не заботясь о том, что это цикл, но после этого вы добавляете операторы break (с условиями, когда это уместно) в конце блоков, которые могут выйти из цикла, и вы заключаете регион в цикл. while true блок. Затем авторы определили 6 шаблонов, которые можно заменить более удобочитаемыми шаблонами (например, while true, начинающийся с if (cond) break, можно преобразовать в while !cond).

И это все.