Post Dominator Tree

Post Dominator Tree

[Marcio de Oliveira Buss]

	Good Morning (afternoon) for all...
	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.
 Am I right? 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?

	Buss.

Re: Post Dominator Tree

[Richard Henderson]

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~

Re: Post Dominator Tree

[Jeffrey A Law]

  In message < 20000703120542.E25642@cygnus.com >you write:
  > 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.
Right.


  > But last I heard we were stalled on copyright assignment paperwork
  > being processed by the FSF.  See
Correct.  Michael sent papers (as far as I know), but they haven't
been recorded at the FSF yet.

jeff

Re: Post Dominator Tree

[Michael Matz]

Ho,

On Mon, 3 Jul 2000, Jeffrey A Law wrote:
>   > But last I heard we were stalled on copyright assignment paperwork
>   > being processed by the FSF.  See
> Correct.  Michael sent papers (as far as I know), but they haven't
> been recorded at the FSF yet.

Yep, and assign@gnu.org doesn't answer since a week. Should I resend the
papers?


Ciao,
Michael.

Re: Post Dominator Tree

[Jeffrey A Law]

  In message < Pine.GSO.4.21.0007061553380.9763-100000@platon >you write:
  > Ho,
  > 
  > On Mon, 3 Jul 2000, Jeffrey A Law wrote:
  > >   > But last I heard we were stalled on copyright assignment paperwork
  > >   > being processed by the FSF.  See
  > > Correct.  Michael sent papers (as far as I know), but they haven't
  > > been recorded at the FSF yet.
  > 
  > Yep, and assign@gnu.org doesn't answer since a week. Should I resend the
  > papers?
No.  Sometimes things take a while.  Remember, they're a 100% volunteer
organization.
jeff