Одним из моих побочных проектов является decompiler, который превращает собственный код в LLVM IR, упрощает его и выводит псевдо-C. Важнейшей фазой программного процесса является структурирование структуры управления, зависящее от структуры шаблона, которая находит области в программе и превращает их в структурированные операторы потока управления (т.е. не gotos).
Мне пришлось развернуть свой собственный код для поиска регионов, потому что регионы LLVM не выглядят точно, как их ожидает газета. Тем не менее, для нахождения регионов требуется, чтобы у вас было дерево после доминанты, и оказывается, что алгоритм построения дерева LLVM после доминанты не может сделать его для функций, у которых нет конечного блока, например функций, которые "заканчиваются" бесконечным циклом.
Это похоже на то, что алгоритм построения дерева требует отправной точки. Обычно отправной точкой является возвращаемый блок функции, поскольку он пост-доминирует над каждым другим блоком; но в функциях, которые вращаются в бесконечный цикл, нет никаких функций, поскольку у них нет терминатора return или unreachable. (На этом этапе, возможно, стоит отметить, что региональный код LLVM также опирается на дерево пост-доминант и также бесполезен для функций, для которых он не может быть построен.)
Мне кажется, что хотя этот алгоритм терпит неудачу, тот факт, что функция не возвращается, не означает, что вы не можете создать для него дерево пост-доминант. 1 In факт, если этот бесконечный цикл имеет один обратный фронт (что я могу обеспечить), node с этим задним фронтом обязательно пост-доминирует в каждом другом node на графике, поэтому должно быть возможно сделать дерево post-dominator.
Если бы я мог найти node, я мог бы, вероятно, доставить его в инфраструктуру post-dom LLVM и получить из него разумное дерево post-dominator. К сожалению, я не очень изобретателен и единственный простой способ, который я могу придумать, чтобы определить, что ключевым node является то, что "это то, что пост-доминирует во всем", что, безусловно, не поможет мне загружать пост-доминанту дерево.
Поиск задних кромок не является особенно сложным. Как говорит Дуг Карри, вы можете сделать это с помощью простой DFS, и на самом деле другая часть моего проекта делает именно это. Однако, в случае функции с бесконечным циклом и вложенными, завершающими циклами, я не знаю, как бы я сказал внутренний задний край от внешнего заднего края без информации о доминировании. (Если это может помочь, на этом этапе процесса каждый цикл, как гарантируется, имеет единственную запись node и не более одного выхода node.)
Итак, как я могу построить дерево пост-доминанты функции, которая не имеет никакого возвращаемого базового блока?
1. Мой опыт работы с компилятором и графикой теории полностью самоуничтожен. Это может быть неточно.
