using dominators in SSA optimizations

Stephen Weeks MLton@sourcelight.com
Thu, 8 Nov 2001 10:14:57 -0800


Matthew, one thing that I noticed in some of the SSA optimization
passes that you checked in is that they use Function.dominatorTree
(which of course invokes a dominator computation) when I think they
don't need to -- in particular, when a (cheaper) depth-first-search
would be sufficient.  For example, in order to implement containsLoop
in inline.fun, all you need to do is a dfs and stop at a back edge.

The only cases where dominators is necessary, as far as I can see, is
common-subexp and redundant-tests.  In the other cases, my gut tells
me that the run-time cost of using dominators over dfs will be
noticeable.

I like the dominatorTree stuff because it is so easy to write
recursive functions over trees -- so maybe we need some abstraction
for dfs of SSA function cfg's.