Проблемы с реализацией алгоритма Купера-Харви-Кеннеди для поиска непосредственных постдоминаторов в C++. ⇐ C++

[Anonymous]

Я пытаюсь реализовать алгоритм Купера-Харви-Кеннеди из этой статьи на C++. Оригинал используется для поиска доминаторов, однако в моем случае мне нужно найти постдоминаторов. Я знаю, что для этого я могу перевернуть края графа, чтобы «перевернуть» доминаторов из исходного графа и превратить их в постдоминаторов. Я создал несколько отдельных версий алгоритма, но не могу заставить его работать. Часто алгоритм либо зацикливается на неопределенный срок, либо выдает неправильный результат (что я могу проверить, поскольку у меня уже есть гораздо более медленный алгоритм генерации постдоминаторов, который генерирует правильный результат).
Сначала функция помечает каждый узел в соответствии с его порядком в графе:

Код: Выделить всё

void dfs(node_id n,
std::vector& rev_postdom,
std::unordered_map& dfsnum,
std::unordered_set& visited,
const std::map& nodes)
{
if (!visited.insert(n).second) {
return;
}

for (auto pred : nodes.at(n).m_predecessors) {
dfs(pred, rev_postdom, dfsnum, visited, nodes);
}

rev_postdom.push_back(n);
}

Затем функция для поиска пересечения наборов предыдущих постдоминаторов:

Код: Выделить всё

[[nodiscard]] node_id intersect(node_id b1, node_id b2, const std::unordered_map& ipdom, const std::unordered_map& dfsnum) {
while (b1 != b2) {
while (dfsnum.at(b1) < dfsnum.at(b2)) {
node_id next = ipdom.at(b1);
if (next == b1 || next == 0)
return b1;
b1 = next;
}
while (dfsnum.at(b2) < dfsnum.at(b1)) {
node_id next = ipdom.at(b2);
if (next == b2 || next == 0)
return b2;
b2 = next;
}
}
return b1;
}

И основная функция:

Код: Выделить всё

[[nodiscard]] std::unordered_map
ControlFlowGraph::create_postdominator_map() const
{
std::vector rev_postdom;
std::unordered_map dfsnum;
rev_postdom.reserve(m_nodes.size());
dfsnum.reserve(m_nodes.size());
std::unordered_set visited;

dfs(m_returnNode, rev_postdom, dfsnum, visited, m_nodes);
std::reverse(rev_postdom.begin(), rev_postdom.end());

for (u32 i = 0; i < rev_postdom.size(); ++i)
dfsnum[rev_postdom[i]] = i;

const u32 N = rev_postdom.size();
std::unordered_map ipdom;
for (auto n : rev_postdom)
ipdom[n] = 0;

ipdom[m_returnNode] = m_returnNode;

bool changed = true;
while (changed) {
changed = false;
for (u32 i = 1; i < N; ++i) {
node_id n = rev_postdom[i];
node_id new_ipdom = 0;

for (auto s : m_nodes.at(n).m_successors) {
// find first successor with processed postdominator
if (ipdom.at(s) != 0) {
new_ipdom = s;
break;
}
}
// skip if we don't have a processed successor
if (new_ipdom == 0)
continue;

for (auto s : m_nodes.at(n).m_successors) {
if (ipdom.at(s) != 0 && s != new_ipdom)
new_ipdom = intersect(s, new_ipdom, ipdom, dfsnum);
}

if (ipdom.at(n) != new_ipdom) {
ipdom[n] = new_ipdom;
changed = true;
}
}
}
return ipdom;
}

Код: Выделить всё

m_nodes

— это просто упорядоченная карта от node_id (просто u32) к фактической структуре control_flow_node, которая содержит вектор предшественников и преемников. Поскольку здесь мы переворачиваем график, я использую преемников вместо исходных предшественников алгоритма при поиске постдоминатора циклов.
Как видите, я уже внес некоторые изменения в исходный псевдокод, чтобы попытаться исправить алгоритм, но безуспешно. Во-первых, я включил проверку внутри функции пересечения, чтобы избежать бесконечных циклов, с которыми я сталкивался. Это работает, однако вывод по-прежнему неверен. Кроме того, хотя это и не показано в псевдокоде, я пропускаю следующие шаги, если мы не можем найти уже обработанного преемника. Кроме того, я не могу понять, чем моя реализация отличается от псевдокода.

Подробнее здесь: https://stackoverflow.com/questions/798 ... mmediate-p