[tree-ssa] CCP inefficiencies

[law@redhat.com]

Wow.  Our CCP implementation is expensive.  Like absurdly so.

It looks like a lot of the problem is the over-eager copying of nodes
so that we can replace their operands and try to fold them.  This is
in itself rather expensive, but it also creates lots of garbage for
the collector to clean up.  Ugh.  

To give you an idea of how bad things are, if you stop compilation 
immediately after we tear down the SSA form, you'll find that CCP
is regularly taking 10-25% of the compilation time.

A quick prototype which avoids the silly copying of nodes and folding
of expressions which are unlikely to generate a constant drastically
improves this situation:


For insn-attrtab.i we have:

 garbage collection    :   1.79 (14%) usr   0.02 ( 4%) sys   1.82 (13%) wall
 tree CCP              :   3.32 (26%) usr   0.24 (44%) sys   3.60 (27%) wall


Now with my scheme we get:

 garbage collection    :   1.20 (12%) usr   0.01 ( 3%) sys   1.18 (12%) wall
 tree CCP              :   0.74 ( 8%) usr   0.01 ( 3%) sys   0.77 ( 8%) wall


Note the drastic improvement in the time spent inside CCP.  Also note the
significant improvement in time spent inside the garbage collector.


Or another example -- combine.i:

 garbage collection    :   0.65 (20%) usr   0.00 ( 0%) sys   0.64 (18%) wall
 tree CCP              :   0.59 (18%) usr   0.03 (20%) sys   0.71 (21%) wall


With my implementation:
 garbage collection    :   0.35 (14%) usr   0.00 ( 0%) sys   0.34 (13%) wall
 tree CCP              :   0.13 ( 5%) usr   0.00 ( 0%) sys   0.16 ( 6%) wall


Or yet another example, reload.i:

 garbage collection    :   0.30 (14%) usr   0.00 ( 0%) sys   0.31 (13%) wall
 tree CCP              :   0.48 (22%) usr   0.03 (18%) sys   0.50 (21%) wall

With my implementation:

 garbage collection    :   0.18 (10%) usr   0.00 ( 0%) sys   0.20 (11%) wall
 tree CCP              :   0.14 ( 8%) usr   0.00 ( 0%) sys   0.10 ( 5%) wall


Do you want another?  reload1.i:

 garbage collection    :   0.58 (22%) usr   0.00 ( 0%) sys   0.60 (21%) wall
 tree CCP              :   0.49 (18%) usr   0.01 ( 8%) sys   0.41 (14%) wall

With my implementation:
 garbage collection    :   0.20 (11%) usr   0.00 ( 0%) sys   0.20 (11%) wall
 tree CCP              :   0.10 ( 6%) usr   0.00 ( 0%) sys   0.10 ( 5%) wall

Do you sense a pattern here? :-)

Overall (and remember, the compiler is stopped once tree-ssa is finished)
we go from 139.11 seconds to 118.44 seconds.  Significantly fewer
major and minor page faults (which is an indicator that we're probably
sweeping through less memory in the collector).

Anyway, just wanted to give everyone a heads up to some upcoming changes...

Jeff