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.