A relational callgraph is described with unpredicated rules relating argument-free continuations, connecting a product of n sources and m conditions to a single sink (also called the goal). The format is as follows:
Y :- X[1], X[2], ..., X[n], c[1], c[2], ..., c[m].
means "when all continuations X[1]..X[n] have been called, and all conditions c[1]..c[m] have been met, then the goal Y will be called". Because the right hand side is a product, the arguments are commutative and associative, so that the rule makes no demands as to in what order the sources are called, or the conditions are evaluated.
The resulting graph is a directed hypergraph of the B-graph class, with each rule constituting a B-arc.
The task is now to manifest the relational callgraph as a CFG (control flow graph) that satisfies all rules.
To achieve this, we define algebraic join (&) and meet (|) operators over two continuations. The join of two continuations a & b is their immediate common dominator. The meet of two continuations a | b is their immediate common post-dominator. Both operations are commutative, associative and satisfy absorption and idempotent identities.
Since A | B <-> A, B, each B-arc can be collapsed to a single directed edge if the meet over all its sources is satisfiable.
Initially, only rules with singular sources can be collapsed, which solves all linear dependencies and allows to satisfy dependent rules. We iteratively collapse all satisfiable meets until a fixpoint is reached.
Within the iterations, graph rules must be rewritten so all edges sourcing the same continuation have exclusive conditions, and therefore the continuation's next goal is linearly decidable.
If any B-arcs remain, then it is because no common post-dominator for their sources exists, which requires the user to insert meet rules.
A rule may have a data dependency on a source B that does not dominate the meet G (i.e. function call pattern). If B is an immediate predecessor of G = meet(X[1],...,X[n]), then a phi node can be used. However, if the edge distance between B and G is greater than one, then B's data d must be implicitly forwarded as an option type, and the rule must add a "is option d set" condition.
If this implicit solution is undesired (for the sake of intuitive reasoning, or simplification of the compiler), then an additional constraint can be imposed which requires any source X[i] to be a dominator of G (that is, join(X[i],G) == X[i]).