This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [dataflow]: PATCH: worklist based dataflow solver
On 1/9/07, Daniel Berlin <dberlin@dberlin.org> wrote:
On 1/9/07, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> Daniel Berlin wrote:
> > On 1/9/07, Seongbae Park <seongbae.park@gmail.com> wrote:
> >> This patch cuts the time spent in dataflow solver in half, when
> >> compiling top 5 largest files for building cc1. For one analysis
> >> (reaching store problem used during dse),
> >> traversing in the order of the reverse postorder of inverted CFG
> >> for the forward problems reduces the block visit count by 90%.
> >> The worklist based algorithm reduces it by couple % further.
> >
> > That's pretty funny. We originally changed the algorithm to what it is
> > now because it was faster for the problems it was solving.
> > Oh well.
> trust but verify.
I did.
I ran the numbers myself back then.
Of course, i may have misread them what with having the lantern
running out of oil and all that.
On top of x86-64,
Kenny and I bootstrapped and reg-tested the patch
on x86, PPC and ia64 and all platforms look clean.
Andrew Pinski offered to test it on spu-elf
and it is not finished yet.
Beside the correctness testing,
I also did a compile-time comparison on x86 and IA64,
compiling roughly top 5 largest .i files needed for building cc1.
The compiler was built with --disable-check --disable-bootstrap.
On IA64:
W/o patch W/ patch
insn-recog.i 33.01 32.50
fold-const.i 41.33 40.32
insn-attrtab.i 15.95 15.73
builtin.i 16.62 16.59
dwarf2out.i 18.27 18.26
total 125.18 123.4 1.42% reduction.
On x86:
W/o patch W/ patch
insn-recog.i 18.27 17.24
fold-const.i 5.42 5.38
insn-attrtab.i 35.16 33.14
builtin.i 3.63 3.62
dwarf2out.i 5.14 5.11
total 67.62 64.49 4.68% reduction
All numbers are cc1 time reported by -time.
If requested, I can produce the number of block visit count.
--
#pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com";