dominator.nmo

% dominator analysis

% example from sedgewick, algorithms in C++, part 5, figure 19.21, §19.6, p. 191
% edge(from, to)
e(0,1). e(0,2). e(0,3). e(0,5). e(0,6).
e(2,3).
e(3,4). e(3,5).
e(4,9).
e(6,4). e(6,9).
e(7,6).
e(8,7).
e(9,10). e(9,11). e(9,12).
e(11,12).

% all vertices seen by e()
v(?x) :- e(?x,?y).
v(?x) :- e(?y,?x).

% number of in/out-edges for each vertex
in_valence(?x, 0) :- v(?x), ~e(?y, ?x).
in_valence(?x, #count(?y)) :- v(?x), e(?y, ?x).

% distance between any two nodes, if any
dist(0, ?x, ?x) :- v(?x).
dist(1, ?x, ?y) :- e(?x, ?y).
dist(?n + 1, ?x, ?z) :- dist(?n, ?x, ?y), e(?y, ?z).

% which vertices can reach the predecessors, and how many paths to our node exist?
predpred(?x, ?z, #count(?y)) :-
    e(?y, ?z),
    dist(?i, ?x, ?y).

% those that match the number of in-edges dominate (in)directly; record the
% distance to each.
indirectdomdist(?x, ?y, ?i) :-
    predpred(?x, ?y, ?c),
    in_valence(?y, ?c),
    dist(?i, ?x, ?y).

% find the shortest dominator distance
shortestdom(?y, #min(?i)) :- indirectdomdist(?x, ?y, ?i).

% extract the dominator with the shortest distance
dom(?y, ?x) :-
    shortestdom(?y, ?i),
    indirectdomdist(?x, ?y, ?i).
% also record nodes that aren't dominated (have global lifetime)
dom(?x, none) :-
    v(?x),
    ~shortestdom(?x, ?i).

@export dom :- csv{resource = ""}.

% lifetime analysis

rtoposort(#max(?n), ?x) :- dist(?n, ?x, ?y).
% latest layer which depends on a vertex (i.e. after which the vertex can be discarded)
lifetime(#max(?i), ?y) :- e(?x, ?y), rtoposort(?i, ?x).

@export rtoposort :- csv{resource = ""}.
@export lifetime :- csv{resource = ""}.