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

[Anonymous]

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


F будет узлом с неправильным постдоминатором. Правильным постдоминатором будет узел фиксации цикла G, но мой алгоритм создает H, выходной узел.
Мой алгоритм зависит от следующих функций:

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

[[nodiscard]] std::vector create_rev_postord(const std::vector& nodes) {
std::vector result;
const u32 size = nodes.size();
result.reserve(size);
node_set visited(size, false);

std::vector stack;
stack.emplace_back(nodes.back().m_index, 0);
u32 i = 0;
while (!stack.empty()) {
auto [n, i] = stack.back();
if (!visited[n]) {
visited[n] = true;
}

const auto& preds = nodes[n].m_predecessors;
if (i < preds.size()) {
stack.back().second++;
const auto p = preds[i];
if (!visited[p]) {
stack.emplace_back(p, 0);
}
}
else {
result.insert(result.begin(), n);
stack.pop_back();
}
}
return result;
}

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

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

[[nodiscard]] const control_flow_node& intersect(const node_id node_b1, const node_id node_b2, const std::vector& nodes) {
const control_flow_node* b1 = &nodes[node_b1];
const control_flow_node* b2 = &nodes[node_b2];
while (b1->m_index != b2->m_index) {
while (b1->m_postorder < b2->m_postorder) {
b1 = &nodes[b1->m_ipdom];
}
while (b2->m_postorder < b1->m_postorder) {
b2 = &nodes[b2->m_ipdom];
}
}
return *b1;
}

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

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

void ControlFlowGraph::compute_postdominators() {

auto rev_postdom = create_rev_postord(m_nodes);

static constexpr node_id UNDEF = std::numeric_limits::max();

for (u32 i = m_nodes.size(); i > 0; --i) {
m_nodes[m_nodes.size() - i].m_postorder = rev_postdom[i - 1];
}

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

ipdom[m_nodes.back().m_index] = m_nodes.back().m_index;
m_nodes.back().m_ipdom = m_nodes.back().m_index;

b8 changed = true;
while (changed) {
changed = false;
for (u32 i = 1; i < N; ++i) {
node_id n = rev_postdom[i];
node_id new_ipdom = UNDEF;
const control_flow_node& node = m_nodes.at(n);
const auto dir_s = node.m_directSuccessor;
const auto tar_s = node.m_targetSuccessor;

if (dir_s && ipdom.at(dir_s) != UNDEF) {
new_ipdom = dir_s;
} else if (tar_s && ipdom.at(tar_s) != UNDEF) {
new_ipdom = tar_s;
}
if (new_ipdom == UNDEF) {
continue;
}

if (dir_s && ipdom.at(dir_s) != UNDEF && dir_s != new_ipdom) {
new_ipdom = intersect(dir_s, new_ipdom, m_nodes).m_index;
}
if (tar_s && ipdom.at(tar_s) != UNDEF && tar_s != new_ipdom) {
new_ipdom = intersect(tar_s, new_ipdom, m_nodes).m_index;
}

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

Поскольку здесь мы переворачиваем график, я использую преемников вместо исходных предшественников алгоритмов при поиске постдоминатора циклов.


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