Some performance improvements.

[Michael Matz]

Hi,

the attachment contains patches to three files (flow.c, local-alloc.c and
simplify-rtx.c), together with an old patch for cp/decl.c (see also
http://gcc.gnu.org/ml/gcc-patches/2000-10/msg00628.html ) whic all help
performance, sometimes a lot.

The changes to flow.c are more of cosmetical nature, besides the change to
make_edge, which unnecessarily searches the edge list, even if there is a
cache, and the are no flags to set. This only is visible with huge CFG's.

The changes to simplify-rtx.c:clear_table() are more worthy. With big
functions using many registers, clear_table() is one of the top time
users. Taken from a compile (-O3 khtml_part.ii) without the patch:
  2.72     25.80     3.87    21718     0.18     0.18  clear_table
compared with the patch:
  0.01    134.87     0.02    21718     0.00     0.00  clear_table
(It's similar with other big files)

The changes to local_alloc.c:update_equiv_regs() save even more time by
making the O(|insns| * |Basic Blocks|) clearing of dead regs from live
info a O(|insns| + |Basic Blocks|) variant. Some timings:
without the patch (-O0, Brad's file "_std.i"):
real    0m46.077s
user    0m44.220s
sys     0m1.040s
 local alloc      :  12.91 (29%) usr   0.03 ( 3%) sys  13.24 (29%) wall
16.08      5.04     5.04 18422665     0.00     0.00  bitmap_find_bit
10.86      8.44     3.40        4   850.00  1559.88  calculate_global_regs_live
10.19     11.62     3.19        3  1063.33  2877.05  update_equiv_regs

[9]     27.6    3.19    5.44       3         update_equiv_regs [9]

while with the patch (still -O0):
real    0m33.947s
user    0m32.700s
sys     0m0.990s
 local alloc      :   1.65 ( 5%) usr   0.01 ( 1%) sys   1.66 (5%) wall
13.17      2.87     2.87        4   717.50  1498.14  calculate_global_regs_live
11.29      5.33     2.46  7290601     0.00     0.00  bitmap_operation
10.10      7.53     2.20       10   220.00   220.00  mark_critical_edges
...
 0.18     19.03     0.04        3    13.33    58.69  update_equiv_regs

[67]     0.8    0.04    0.14       3         update_equiv_regs [67]

13 seconds of 46 saved, not bad (well, it's a profiled build, but the
relative winning should be the same).

This saving in local-alloc doesn't change with optimization, and happens
on all bigger files (not only BBB's - Brad's Big Bastard-functions ;-))

The C++ patch is attached again, because I received no messages regarding
it, despite it's fairly large impact on runtime. See the mail above, when
this patch is safe, and for timings. One of the larger C++ file I used for
the timings above (and the C++ part) is in 
http://www.ifh.de/~matz/khtml_part.ii.gz .

All of the patches (alone and together) survive a i386-linux bootstrap,
and give no additional regressions on the test suite.


Ciao,
Michael, hoping to hear this time from someone ;)