This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH]: Speed up dominance frontiers computation


On Mon, 2005-01-17 at 10:37 -0500, Daniel Berlin wrote:
> The attached patch replaces the dominance frontier algorithm with one
> that 
> 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.

jeff


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]