Re: Post Dominator Tree

[Richard Henderson <rth at cygnus dot com>]

On Mon, Jul 03, 2000 at 02:36:26PM -0300, Marcio de Oliveira Buss wrote:
> 	I need to implement the Post-Dominator Tree in the flow
>  pass of the gcc. I found the compute_dominators function in the
>  file flow.c, but I realize that this function does not implement
>  a tree, but only a bitmap that represent the dominator relationship.

It is also possible to get the immediate dominators.  See
simplify_to_immediate_dominators from ssa.c.  There's no
particular reason why we couldn't move this function to flow.c
and export it.  With only a small tweek one could get the
immediate post-dominators.

>  Also, the Tarjan's algorithm sounds more efficient,
>  but this algorithm is not implemented there. If I implemented this
>  algorithm, it would be a contribution to gcc or it is not relevant?

Michael Matz <matzmich@cs.tu-berlin.de> has submitted an implementation:

/* This file implements an algorithm for calculating dominators in linear
   time, as presented in ftp://ftp.diku.dk/diku/semantics/papers/D-320.ps.gz

   That algorithm uses ideas of the old one from Lengauer and Tarjan.

   The implementation in this file does not use microtrees, and so is
   theoretically not linear, but its not clear that the complexity in
   implementing them would be worthwhile.  */

But last I heard we were stalled on copyright assignment paperwork
being processed by the FSF.  See

  http://gcc.gnu.org/ml/gcc-patches/2000-06/msg00794.html

for his code.


r~