Re: C compile time

[Jan Hubicka <jh at suse dot cz>]

> Jan Hubicka wrote:
> 
> >>Dara Hazeghi wrote:
> >>
> >>   
> >>
> >>>Okay, here's the updated table. Checking is disabled
> >>>on all compilers.
> >>>
> >>>gcc version     -O0     -O1     -O2     -O3
> >>>2.7.2.3         128.04  131.02  163.51  176.01
> >>>2.8.1           128.86  140.79  182.35  194.63
> >>>2.90.29         130.60  140.57  186.29  199.32
> >>>2.91.66         132.44  148.48  203.71  219.21
> >>>2.95.3          143.38  180.97  250.94  276.85
> >>>3.0.4           169.79  210.73  320.24  365.15
> >>>3.2.3           193.48  269.43  424.74  519.85
> >>>3.3             184.15  282.57  442.64  529.93
> >>>3.3-branch      184.15  283.89  443.66  535.10
> >>>3.4-mainline    195.34  302.02  483.84  704.59
> >>>3.4-mainline*   175.84  269.78  426.77  627.13
> >>>3.5-tree-ssa    223.33  327.91  503.58  702.11 
> >>>
> >>>     
> >>>
> >>So with Andrew P's patch, mainline C is faster than 3.3, hurray!
> >>
> >>The slowdown at -O3 is of course due to unit-at-a-time, which can be a 
> >>big memory sucker if there are lots of opportunities to inline static 
> >>   
> >>
> >
> >I was doing some estimates there, and for compiling SPEC sources the
> >slowdown is proportinal to the code size growth caused by
> >unit-at-a-time.  So the problem does not seem to be increased memory
> >overhead, just the fact that we find more inlining opurtunities and
> >inline more. GCC is probably good testcase for this as many parts are
> >ordered top-down instead of bottom-up or old inliner likes.
> >
> 
> You can also use the test case for PR 10155 to see the RAM abuse (and PR 
> 11121 while you're at it :-)

I seem to recall what happens for GCC compilation - in my original
unit-at-a-time benchmarking I did same test and found almost all
slowdown to come from insn-recog. That one is large file divided into
few functions that all inline together (as they are called once) and we
run into several quadratic bottlenecks.  Originally it took about 1 hour
to compile on my K6 test machine.   I implemented
-finline-functions-called-once for this reason but during the review
process we concluded to remove it.  Perhaps this is good reason to put
it back.

I did elliminated majority of these (there was reload-cse, local cse,
sheduler problems) with single exception of GCSE that has problems with
doing transparent bitmaps for memories.  I didn't see direct way to get
out of that - you do have too many memories and to many alias classes to
care about.  The function analyses transparency of all these memories
even in the areas they are not live - this is how does PRE algorithm work
and without SSAPRE there is probably not too much to invent about.  The
algorithm simply is N^3.

One sollution would be to limit growth of the function I am inlining
once into so functions won't get too large and we won't exhibit this too
often.  I seen some of the testcases at unit-at-a-time and they usually
seem to exhibit similar behaviour.

There are several other things we can do with unit-at-a-time - limit
overall growth of compilation unit or decide whether to inline or not
based on overall growth, not function size.

Unfortunate thing on this path is that I will probably not be able to do
unit-at-a-time for C++ without some help and thus this work won't help
C++ where we get major problems.

Other sollution would be to not give up so easilly and try to push more
on keeping compiler linear on the compilation.  For GCSE we probably can
give up when having too many memory references and simply do not record
the others.  Similarly we can deal with quadratic bottlenecks in the
scheduler, but I am not sure whether we will run into problems in
register allocation that is unavoidably quadratic by definition but do
far does not appear to cause major obstackles.

What about others think?

Honza
> 
> Gr.
> Steven
> 
> 
> 
>