From mboxrd@z Thu Jan 1 00:00:00 1970 From: Richard Henderson To: Marcio de Oliveira Buss Cc: gcc@gcc.gnu.org Subject: Re: Post Dominator Tree Date: Mon, 03 Jul 2000 12:05:00 -0000 Message-id: <20000703120542.E25642@cygnus.com> References: X-SW-Source: 2000-07/msg00028.html 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 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~