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

[Anonymous]

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

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

#include 
#include 
#include 
#include 
#include 

using node_id = uint16_t;
using b8 = bool;
using u32 = uint32_t;

using node_set = std::vector;

struct control_flow_node {
std::vector m_predecessors;
node_id m_directSuccessor = 0;
node_id m_targetSuccessor = 0;
node_id m_startLine = 0;
node_id m_endLine = 0;
node_id m_index = 0;
node_id m_postorder = 0;
node_id m_ipdom = 0;
};

[[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;
}

[[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;
}

void compute_postdominators(std::vector& m_nodes) {
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;
}
}
}
}

int main() {
std::vector nodes(14);

for (node_id i = 0; i < nodes.size();  ++i)
nodes[i].m_index = i;

nodes[0].m_directSuccessor = 1;

nodes[1].m_directSuccessor = 2;
nodes[1].m_targetSuccessor = 13;

nodes[2].m_directSuccessor = 3;
nodes[2].m_targetSuccessor = 5;

nodes[3].m_directSuccessor = 4;
nodes[3].m_targetSuccessor = 5;

nodes[4].m_targetSuccessor = 12;

nodes[5].m_directSuccessor = 6;
nodes[5].m_targetSuccessor = 8;

nodes[6].m_directSuccessor = 7;

nodes[7].m_targetSuccessor = 12;

nodes[8].m_directSuccessor = 9;
nodes[8].m_targetSuccessor = 11;

nodes[9].m_directSuccessor = 10;
nodes[9].m_targetSuccessor = 11;

nodes[10].m_targetSuccessor = 12;

nodes[11].m_directSuccessor = 12;

nodes[12].m_targetSuccessor = 1;

nodes[0].m_predecessors = {};

nodes[1].m_predecessors = {0, 12};

nodes[2].m_predecessors = {1};

nodes[3].m_predecessors = {2};
nodes[5].m_predecessors = {2, 3};

nodes[4].m_predecessors = {3};

nodes[12].m_predecessors = {4, 7, 10, 11};

nodes[6].m_predecessors = {5};
nodes[8].m_predecessors = {5};

nodes[7].m_predecessors = {6};

nodes[9].m_predecessors = {8};
nodes[11].m_predecessors = {8, 9};

nodes[10].m_predecessors = {9};

nodes[13].m_predecessors = {1};

compute_postdominators(nodes);

for (u32 i = 0; i < nodes.size(); ++i)
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/79815102/trouble-implementing-the-cooper-harvey-kennedy-algorithm-for-finding-immediate-p[/url]