Probleme bei der Implementierung des Cooper-Harvey-Kennedy-Algorithmus zum Finden unmittelbarer Postdominatoren in C++ ⇐ C++

[Anonymous]

Ich versuche, den Cooper-Harvey-Kennedy-Algorithmus aus diesem Artikel in C++ zu implementieren. Das Original wird verwendet, um Dominatoren zu finden, in meinem Fall muss ich jedoch die Postdominatoren finden. Zu diesem Zweck bin ich mir bewusst, dass ich die Kanten des Diagramms umkehren kann, um die Dominatoren aus dem ursprünglichen Diagramm zu „Postdominatoren“ zu machen. Der Algorithmus, den ich jetzt habe, funktioniert korrekt, außer innerhalb von Schleifen, wo mehreren Knoten der Ausgangsknoten der Schleife (der Knoten direkt nach der bedingten Prüfung, ob sie in die Schleife eintreten sollen oder nicht) als Postdominatoren zugewiesen wird, obwohl es sich um den Latch-Knoten handeln sollte (der der „größte“ Postdominator für alle Knoten innerhalb der Schleife sein sollte).
Hier ist ein minimal reproduzierbares Beispiel:

Code: Select all

#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