This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Speedup compile/20001226-1.c compilation
On 9/12/06, Jan Hubicka <hubicka@ucw.cz> wrote:
> > * cfganal.c (compute_dominance_frontiers_1): Don't be quadratic.
>
> I'd commit this as obvious, to be honest.
> It makes the comment true (i'm actually rather surprised nobody
> noticed this before. I certainly missed it when i rewrote the code,
> which was still faster than the old code!)
OK, comitted.
I was just wondering if I missed something obvious ;)
Nope.
I transcribed the algorithm from the pseudocode, forgetting the text
near it that said
"There is a small amount of bookkeeping not shown; specifically, any j should
be added to a node's dominance frontier only once, but the data
structure used for
the dominance frontier sets will dictate the amount of additional work
necessary.
In our implementation, we use linked lists for dominance-frontier
sets, so we keep a
SparseSet [18] to restrict multiple entries – when a join point is
entered into a node's
dominance-frontier set, we put that node into the SparseSet, and,
before a join point
is entered into a node's dominance-frontier set, we check to see if
that node is already
in the SparseSet."
Why they wouldn't show this (it's one god damn line of pseudocode) is
beyond me, but whatever :)