README
dominators
Various dominator tree generators.
It implements two different methods for finding the immediate dominators of a graph.
Implements a nearlinear time iterative dominator generator based on the paper A Simple, Fast Dominance Algorithm using an iterative method^{1}
Yet another Lengauer & Tarjan implementation with variations. From this paper^{2} which you can find a link to it here (and many other places, in case this link goes bad): A fast algorithm for finding dominators in a flowgraph
Install
npm i dominators
Usage
const
{
iterative,
lt,
frontiers_from_preds,
frontiers_from_succs,
reverse_graph
} = require( 'dominators' ),
someGraph = [
[ 1, 8 ], // start
[ 2, 3 ], // a
[ 3 ], // b
[ 4, 5 ], // c
[ 6 ], // d
[ 6 ], // e
[ 7, 2 ], // f
[ 8 ], // g
[] // end
],
immediateDominators = iterative( someGraph ),
// idoms = [ null, 0, 1, 1, 3, 3, 3, 6, 0 ],
df = frontiers_from_succs( someGraph, immediateDominators ),
// df = [ [], [ 8 ], [ 3 ], [ 2, 8 ], [ 6 ], [ 6 ], [ 2, 8 ], [ 8 ], [] ]
// or
same = frontiers_from_preds( reverse_graph( someGraph ), immediateDominators ),
// df = [ [], [ 8 ], [ 3 ], [ 2, 8 ], [ 6 ], [ 6 ], [ 2, 8 ], [ 8 ], [] ]
// See the explanation of parameters below.
ltDoms = lt( someGraph, 0, true ),
// ltDoms = [ null, 0, 1, 1, 3, 3, 3, 6, 0 ],
// The first parameter is your graph, an array of arrays of successor indices.
// The second parameter is the start node, defaults to 0. This is optional and defaults to 0.
// The last parameter is an optional boolean for whether to run it flat or not.
// If it runs flat (set to true) then it will not use recursion for the DFS or the compress
// function. The default is true.
ltDomsSame = lt( someGraph, 0, true );
// ltDoms = [ null, 0, 1, 1, 3, 3, 3, 6, 0 ],
// Read full API documentation below
const myGraph = make_dom( graph );
myGraph.forStrictDominators( n => console.log( `${n} is a strict dominator of 9` ), 9 );
if ( myGraph.strictlyDominates( 7, 9 ) )
console.log( `7 strictly dominates 9` );
console.log( `Node at index 7 strictly dominates these: ${myGraph.strictlyDominates( 7 ).join( ', ' )}` );
console.log( `The strict dominators of 7 are ${myGraph.strictDominators( 7 ).join( ', ' )}` );
Fast LengauerTarjan LINK procedure
For the sake of completeness, below is the fast balanaced version of link, which is not included in the current module code for two reasons:
 The LT algorithm with this LINK only becomes faster than the normal implementation when we're dealing with 10s or 100s of thousands of nodes, in which cases you shouldn't be using JavaScript anyway.
 I don't have test graph large enough to get proper coverage so, since it's not really useful, I decided to remove it.
This implementation uses arrays rather then an object. That's how I originally implemented this algorithm but that makes it incompatible with the current implementation. I won't convert it since it's not used, however, because it is interesting, I've included it here, for interested parties, of which there will probably be at least zero but not more.
balanced_link = ( w ) => {
let s = w,
v = parent[ w ];
do
{
let cs = child[ s ],
bcs = cs !== null ? best[ cs ] : null;
if ( cs !== null && semi[ best[ w ] ] < semi[ bcs ] )
{
let ccs = child[ cs ],
ss = size[ s ],
scs = size[ cs ],
sccs = ccs !== null ? size[ ccs ] : 0;
if ( ss  scs >= scs  sccs )
child[ s ] = ccs;
else
{
size[ cs ] = ss;
ancestor[ s ] = cs;
s = cs;
}
}
else
break;
}
while ( true );
best[ s ] = best[ w ];
if ( size[ v ] < size[ w ] )
{
let t = s;
s = child[ v ];
child[ v ] = t;
}
size[ v ] += size[ w ];
while ( s !== null )
{
ancestor[ s ] = v;
s = child[ s ];
}
}
License
MIT © Julian Jensen
API
Functions
 make_dom(opts) ⇒
Object
This will associated a graph with a number of useful utility functions. It will return an object with a variety of functions that operate on the graphs.
You might notice that many of these functions I took from the WebKit
dominators.h
file, which I really liked, and, although I rewrote the code completely (obviously, since it was inC++
), I decided to keep their comments with a few small alterations or corrections. I decided to not use their iterated dominance frontier code, because it was as efficient as it could be. Instead, I implemented one that uses a DJgraph that I found in Chapter 4 of "The SSA Book," called "Advanced Contruction Algorithms for SSA" by D. Das, U. Ramakrishna, V. Sreedhar. That book doesn't seem to be published or, if it has, I've missed it. You can build the book yourself, supposedly, (I couldn't make that work, though) from here: SSA Book or you can probably find a PDF version of it somewhere on the web, which is what I did. iterative(succs, [startIndex], [flat]) ⇒
Array.<number>
Implements a nearlinear time iterative dominator generator based on this paper: (A Simple, Fast Dominance Algorithm)[https://www.cs.rice.edu/~keith/Embed/dom.pdf] Citation: Cooper, Keith & Harvey, Timothy & Kennedy, Ken. (2006). A Simple, Fast Dominance Algorithm. Rice University, CS Technical Report 0633870
 check(vertices, idoms)
Find dominance frontiers
 frontiers_from_preds(preds, idoms)
Find dominance frontiers
 frontiers_from_succs(succs, idoms)
Find dominance frontiers
 lt(nodes, [startIndex], [flat])
 normalize(nodes) ⇒
Array.<Array.<number>>
 condRefToSelf(seed, [chk], [dest]) ⇒
Array.<Array.<number>>
 simpleRefToSelf(seed, [dest]) ⇒
Array.<Array.<number>>
 create_j_edges(_nodes, [domLevels], [domTree], [idoms]) ⇒
*
This will create and return the Jedges of a graph. The Jedges, or Join edges, make up onehalf of the DJgraph. For more information read the documentation for the DJgraph.
You need only pass the nodes of the graph to this function. The rest of the parameters are optional and will be computed if not provided. I allow the options to pass them in case you already have them calculated from elsewhere, just to make things a bit faster. If no arguments are provided other than the basic vertices, it will compute the immediate dominators, create the dominator tree, and compute the levels, and discard all of those results. Not a big deal unless you're dealing with very large graphs, in which case you should calculate those separately and provide them as inputs here.
 create_levels(nodes) ⇒
Array.<number>
Calculate the level of each node in terms of how many edges it takes to reach the root. For the sake of simplicity, this uses a BFS to compute depth values.
 create_nodes(_nodes, [idoms])
A convenience method. It returns an array of object, one for each nodes in the graph, and in that order, that holds most of the information you could want for working with graphs.
Specifically, each node looks as descibed in the typedef for GraphNode.
 create_dj_graph(nodes, [idoms], [domTree])
Returns a DJgraph which is a graph that consts of the dominator tree and select join edges from the input graph.
Typedefs
 DomWalkerOptions :
object
 GraphNode :
object
Object
make_dom(opts) ⇒ This will associated a graph with a number of useful utility functions. It will return an object with a variety of functions that operate on the graphs.
You might notice that many of these functions I took from the WebKit dominators.h
file, which
I really liked, and, although I rewrote the code completely (obviously, since it was in C++
), I decided
to keep their comments with a few small alterations or corrections. I decided to not use their iterated dominance frontier
code, because it was as efficient as it could be. Instead, I implemented one that uses a DJgraph
that I found in Chapter 4 of "The SSA Book," called "Advanced Contruction Algorithms for SSA" by
D. Das, U. Ramakrishna, V. Sreedhar. That book doesn't seem to be published or, if it has, I've
missed it. You can build the book yourself, supposedly, (I couldn't make that work, though) from here: SSA Book
or you can probably find a PDF version of it somewhere on the web, which is what I did.
Kind: global function
Param  Type 

opts  DomWalkerOptions  Array.<Array.<number>> 
Example
const myGraph = make_dom( graph );
myGraph.forStrictDominators( n => console.log( `${n} is a strict dominator of 9` ), 9 );
Example
if ( myGraph.strictlyDominates( 7, 9 ) )
console.log( `7 strictly dominates 9` );
Example
console.log( `Node at index 7 strictly dominates these: ${myGraph.strictlyDominates( 7 ).join( ', ' )}` );
console.log( `The strict dominators of 7 are ${myGraph.strictDominators( 7 ).join( ', ' )}` );
 make_dom(opts) ⇒
Object
 ~alternative_idf(defs) ⇒
Array
 ~forIteratedDominanceFrontier(fn, defs)
 ~iteratedDominanceFrontier(defs) ⇒
Array.<number>
 ~forStrictDominators(fn, to)
 ~forDominators(fn, to)
 ~strictDominators(to) ⇒
Array.<number>
 ~dominators() ⇒
Array.<number>
 ~strictlyDominates(from, [to]) ⇒
boolean
Array.<number>
 ~dominates(from, [to]) ⇒
boolean
Array.<number>
 ~forStrictlyDominates(fn, from, [notStrict])
 ~forDominates(fn, from)
 ~forDominanceFrontier(fn, from)
 ~dominanceFrontier(from) ⇒
Array.<number>
 ~forPrunedIteratedDominanceFrontier(fn, from)
 ~alternative_idf(defs) ⇒
Array
make_dom~alternative_idf(defs) ⇒ This calculates the iterated dominance frontier quickest of all but requires that you have already computed the dominance frontier for each individual node. If you call this without frontiers being set, it will calculate all of them the first time.
Kind: inner method of make_dom
Param  Type 

defs  Array.<number> 
make_dom~forIteratedDominanceFrontier(fn, defs)
Same as iteratedDominanceFrontier( defs )
except it doesn't return anything but will
invoke the callback as it discovers each node in the iterated dominance frontier.
Kind: inner method of make_dom
Param  Type  Description 

fn  function 
A callback function with one argument, a node in the DF of the input list 
defs  Array.<number> 
A list of definition nodes 
Array.<number>
make_dom~iteratedDominanceFrontier(defs) ⇒ Given a list of definition nodes, let's call them start nodes, this will return the dominance frontier of those nodes. If you're doing SSA, this would be where you'd want to place phifunctions when building a normal SSA tree. To create a pruned or minimal tree, you'd probably have to discard some of these but it makes for a starting point.
Kind: inner method of make_dom
Returns: Array.<number>
  A list of all node sin the DF of the input set
Param  Type  Description 

defs  Array.<number> 
A list of definition nodes 
make_dom~forStrictDominators(fn, to)
Loops through each strict dominator of the given node.
Kind: inner method of make_dom
Param  Type 

fn  function 
to  number 
make_dom~forDominators(fn, to)
This will visit the dominators starting with the to
node and moving up the idom tree
until it gets to the root.
Kind: inner method of make_dom
Param  Type 

fn  function 
to  number 
Array.<number>
make_dom~strictDominators(to) ⇒ This will return all strict dominators for the given node. Same as dominators
but
excluding the given node.
Kind: inner method of make_dom
Param  Type 

to  number 
Array.<number>
make_dom~dominators() ⇒ This returns a list of all dominators for the given node, including the node itself since a node always dominates itself.
Kind: inner method of make_dom
boolean
 Array.<number>
make_dom~strictlyDominates(from, [to]) ⇒ This will return one of two things. If call with two node numbers, it will return a boolean
indicating
if the first node strictly dominates the second node.
If called with only one node number then it will create a list of all nodes strictly dominated by the given node.
Kind: inner method of make_dom
Param  Type 

from  number 
[to]  number 
boolean
 Array.<number>
make_dom~dominates(from, [to]) ⇒ This is the same as the strictlyDominates()
function but includes the given node.
Kind: inner method of make_dom
Param  Type 

from  number 
[to]  number 
make_dom~forStrictlyDominates(fn, from, [notStrict])
Thie loops through all nodes strictly dominated by the given node.
Kind: inner method of make_dom
Param  Type  Default 

fn  function 

from  number 

[notStrict]  boolean 
false 
make_dom~forDominates(fn, from)
Thie loops through all nodes strictly dominated by the given node, including the node itself.
Kind: inner method of make_dom
Param  Type 

fn  function 
from  number 
make_dom~forDominanceFrontier(fn, from)
Paraphrasing from Dominator (graph theory):
"The dominance frontier of a block 'from' is the set of all blocks 'to' such that 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly dominate 'to'."
A useful corner case to remember: a block may be in its own dominance frontier if it has a loop edge to itself, since it dominates itself and so it dominates its own immediate predecessor, and a block never strictly dominates itself.
Kind: inner method of make_dom
Param  Type 

fn  function 
from  number 
Array.<number>
make_dom~dominanceFrontier(from) ⇒ Returns the dominanace frontier of a given node.
Kind: inner method of make_dom
Param  Type 

from  number 
make_dom~forPrunedIteratedDominanceFrontier(fn, from)
This is a close relative of forIteratedDominanceFrontier(), which allows the given predicate function to return false to indicate that we don't wish to consider the given block. Useful for computing pruned SSA form.
Kind: inner method of make_dom
Param  Type 

fn  function 
from  Array.<number> 
Array.<number>
iterative(succs, [startIndex], [flat]) ⇒ Implements a nearlinear time iterative dominator generator based on this paper: (A Simple, Fast Dominance Algorithm)[https://www.cs.rice.edu/~keith/Embed/dom.pdf] Citation: Cooper, Keith & Harvey, Timothy & Kennedy, Ken. (2006). A Simple, Fast Dominance Algorithm. Rice University, CS Technical Report 0633870
Kind: global function
Param  Type  Default 

succs  Array.<(Array.<number>number)> 

[startIndex]  number 
0 
[flat]  boolean 
true 
Array.<Array.<number>>
iterative~nsuccs : Kind: inner constant of iterative
check(vertices, idoms)
Find dominance frontiers
Kind: global function
Param  Type 

vertices  Array.<Array.<number>> 
idoms  Array.<?number> 
frontiers_from_preds(preds, idoms)
Find dominance frontiers
Kind: global function
Param  Type 

preds  Array.<Array.<number>> 
idoms  Array.<?number> 
frontiers_from_succs(succs, idoms)
Find dominance frontiers
Kind: global function
Param  Type 

succs  Array.<Array.<number>> 
idoms  Array.<?number> 
lt(nodes, [startIndex], [flat])
Kind: global function
Param  Type  Default 

nodes  Array.<Array.<number>> 

[startIndex]  number 
0 
[flat]  boolean 
true 
Array.<Array.<number>>
normalize(nodes) ⇒ Kind: global function
Param  Type 

nodes  Array.<(Array.<number>number)> 
Array.<Array.<number>>
condRefToSelf(seed, [chk], [dest]) ⇒ Kind: global function
Returns: Array.<Array.<number>>
 }
Param  Type 

seed  Array.<Array.<number>> 
[chk]  function 
[dest]  Array.<Array.<number>> 
Array.<Array.<number>>
simpleRefToSelf(seed, [dest]) ⇒ Kind: global function
Returns: Array.<Array.<number>>
 }
Param  Type 

seed  Array.<Array.<number>> 
[dest]  Array.<Array.<number>> 
*
create_j_edges(_nodes, [domLevels], [domTree], [idoms]) ⇒ This will create and return the Jedges of a graph. The Jedges, or Join edges, make up onehalf of the DJgraph. For more information read the documentation for the DJgraph.
You need only pass the nodes of the graph to this function. The rest of the parameters are optional and will be computed if not provided. I allow the options to pass them in case you already have them calculated from elsewhere, just to make things a bit faster. If no arguments are provided other than the basic vertices, it will compute the immediate dominators, create the dominator tree, and compute the levels, and discard all of those results. Not a big deal unless you're dealing with very large graphs, in which case you should calculate those separately and provide them as inputs here.
Kind: global function
See: create_dj_graph
Param  Type  Description 

_nodes  Array.<Array.<number>> 
An array of arrays of successors indices, as always 
[domLevels]  Array.<number> 
The levels (or depth) of the nodes in the dominator tree 
[domTree]  Array.<Array.<number>> 
The dominator tree in the standard format, same as _nodes 
[idoms]  Array.<number> 
The immediate dominators 
Array.<number>
create_levels(nodes) ⇒ Calculate the level of each node in terms of how many edges it takes to reach the root. For the sake of simplicity, this uses a BFS to compute depth values.
Kind: global function
Returns: Array.<number>
  An array of depth (i.e. level) numbers
Param  Type  Description 

nodes  Array.<Array.<number>> 
The graph 
create_nodes(_nodes, [idoms])
A convenience method. It returns an array of object, one for each nodes in the graph, and in that order, that holds most of the information you could want for working with graphs.
Specifically, each node looks as descibed in the typedef for GraphNode.
Kind: global function
See: GraphNode
Param  Type  Description 

_nodes  Array.<Array.<number>> 
The usual graph nodes 
[idoms]  Array.<number> 
The immediate dominators, if not provided, they will be computed 
create_dj_graph(nodes, [idoms], [domTree])
Returns a DJgraph which is a graph that consts of the dominator tree and select join edges from the input graph.
Kind: global function
Param  Type  Description 

nodes  Array.<Array.<number>> 
Graph in the usual format 
[idoms]  Array.<number> 
Immediate dominators, if omiteed, they will be computed 
[domTree]  Array.<Array.<number>> 
Dominator tree, it omitted, will be computed 
object
DomWalkerOptions : Kind: global typedef
Properties
Name  Type 

nodes  Array.<Array.<number>> 
idoms  Array.<?number> 
domTree  Array.<Array.<number>> 
jEdges  Array.<Array.<number>> 
frontiers  Array.<Array.<number>> 
djGraph  Array.<Array.<Array.<number>>> 
domLevels  Array.<number> 
object
GraphNode : Kind: global typedef
Properties
Name  Type  Description 

id  number 
The index of this node in the original array 
succs  Array.<number> 
The successor node indices 
preds  Array.<number> 
The predecessor node indices 
domSuccs  Array.<number> 
The dominator tree successor indices 
idom  number 
The immediate dominator and, of course, dominator tree predecessor 
level  number 
The depth (or level) of the vertex 
domLevel  number 
The depth in the dominator tree 
jSuccs  Array.<number> 
The successor Jedges, if any, of this node 
jPreds  Array.<number> 
The predecessor Jedges, if any, of this node 
^{1} Cooper, Keith & Harvey, Timothy & Kennedy, Ken. (2006). A Simple, Fast Dominance Algorithm. Rice University, CS Technical Report 0633870
^{2} Thomas Lengauer and Robert Endre Tarjan. 1979. A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1, 1 (January 1979), 121141. DOI=http://dx.doi.org/10.1145/357062.357071