[MLton] Faster dominators for MLton

[Matthew Fluet]

On Wed, 7 May 2008, Vesa Karvonen wrote:
> I was reading up on compiler optimizations and got interested in the
> computation of dominators.  So, looking for dominator algorithms, I
> stumbled upon the following paper:
>
>   A Simple, Fast Dominance Algorithm.
>   Keith Cooper and Timothy Harvey and Ken Kennedy.
>   Software Practice and Experience, 2001.
>   http://citeseer.ist.psu.edu/cooper01simple.html
>   http://www.cs.rice.edu/~keith/EMBED/dom.pdf
>
> The algorithm described in the paper is O(N^2), but the paper reports that
> it runs faster, in practice, than the classic Lengauer-Tarjan algorithm.
> I was a bit worried by the O(N^2) bound, because, I assume, MLton computes
> dominators for the whole program, but decided to try to implement it
> anyway.

MLton never computes dominators for a graph that corresponds to all the 
basic blocks in an SSA IL program.  For the contification analysis, the 
dominators are computed on a graph that has nodes equal to the number of 
SSA IL functions in the program + the number of non-tail transfers in the 
program; and has edges equal to the number of tail-transfers in the 
program + 2 * the number of non-tail transfers in the program.

Other passes compute the dominator tree on the control-flow-graph of a 
single SSA IL function: common-subexp, redundant-tests, type-checking. 
So, a faster dominator algorithm would help in a number of places.


I saw the commit to SVN, and think it is a great addition.