This is the mail archive of the
mailing list for the GCC project.
Re: [PATCH]: Speed up dominance frontiers computation
- From: Jeffrey A Law <law at redhat dot com>
- To: Daniel Berlin <dberlin at dberlin dot org>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Mon, 17 Jan 2005 13:35:19 -0700
- Subject: Re: [PATCH]: Speed up dominance frontiers computation
- Organization: Red Hat, Inc
- References: <1105976269.6969.5.camel@DYN253790YKT.watson.ibm.com>
- Reply-to: law at redhat dot com
On Mon, 2005-01-17 at 10:37 -0500, Daniel Berlin wrote:
> The attached patch replaces the dominance frontier algorithm with one
> 1. Is faster in all cases
> 2. Is simpler, smaller, and more intuitive
> 3. Is non-recursive
> The old algorithm used to walk blocks that weren't going to end up in
> the dominance frontier of any block (IE it was the O(sum of the size of
> the dominance frontiers), and grew with the size of the dominance
> frontiers, and the size of the CFG).
> The new algorithm grows only with the size of the CFG. The inner loop
> only touches blocks that will be in the dominance frontier of some
> block, rather than blocks that *could* be in the dominance frontier of
> some block.
> It is roughly 30% faster in all cases, and moreso on large testcases
> where dominance frontier computation was taking any significant amount
> of time (via into-ssa). It is also a win when you are compiling large
> numbers of functions with small numbers of basic blocks, since it
> doesn't do as much work in these cases as the old one, either.
> Bootstrapped and regtested on i686-pc-linux-gnu and powerpc-darwin.
> I also bootstrapped and regtested on these two platforms by running both
> the old algorithm and the new algorithm, and verifying the resulting
> frontiers matched exactly.
> Okay for mainline?
OK assuming you put a reference to the paper in the comments.