Last active
July 6, 2024 11:37
-
-
Save paniq/74ab16ac86fc5076a447b5a8078bd10f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% 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 = ""}. | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment