Revisiting the use of cselib in alias.c for scheduling

[Steven Bosscher]

Hello,

Back in 2001, GCC could disambiguate almost no MEMs on ia64 because
ia64 has no (reg+offs) addressing modes. Bernd added a trick to alias
and to sched-ebb to use cselib, to substitute a reg address with a
reg+offs address recorded by cselib (see
http://gcc.gnu.org/viewcvs?view=revision&revision=32538 and
http://gcc.gnu.org/viewcvs?view=revision&revision=44716).

There are a couple of problems with this approach:

1. This feature gets almost no testing. By default, the sched-ebb.c
code is only used by ia64 and picochip. A special flag
"-fsched2-use-superblocks" must be given by the user to enable
sched-ebb on other targets. (A bit of searching with Google Code
Search shows that this is not a very popular option ;-). For ia64,
sched-ebb is even only used at -O1 and -O2. At -O3 the selective
scheduler is used instead. All this considered, I think we may
conclude that this code is not used all that much.
As a result, the code appears to be buggy. See
http://gcc.gnu.org/PR43494, and http://gcc.gnu.org/35658 is almost
certainly the same issue.

2. sched-ebb is the only scheduler that uses this. The new "ia64
scheduler" (selective scheduler) does not use cselib but still
outperforms sched-ebb in terms of code generation.

3. GCC now has better alias analysis than it used to, especially with
the alias-exporting stuff that exports the GIMPLE points-to analysis
results, but also just all the other little things that were
contributed over the last 10 years (little things like tree-ssa :)


It is unclear whether the use of cselib brings any benefit. I tried to
measure this by instrumenting true_dependence() and compiling a set of
cc1-i files.

It looks like ~9% extra !true_dependence cases are found with cselib,
with is not insignificant:

situation    calls   depends ratio
with_cselib  186764  70463   0.377284
asis         186764  76375   0.408939 (i.e. no cselib)

On the other hand, the difference in instruction count is really small
(408 instructions more, or 0.02%):

situation    # insns  # bundles  # stops
with_cselib  1984191  611991     530006
asis         1984599  612127     530337
             +0.021%   +0.022%   +0.062%
(insns counted with egrep "^\s+[a-z].* *.s
bundles counted with egrep "^\s+\.[a-z]{3}\s*$" *.s
stops counted with egrep "\s+;;\s*$" *.s)

The "asis" results are the numbers with this patch applied, to disable
cselib in sched-ebb:

Index: sched-ebb.c
===================================================================
--- sched-ebb.c (revision 162278)
+++ sched-ebb.c (working copy)
@@ -275,7 +275,7 @@
     ebb_compute_jump_reg_dependencies,
     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
     NULL,
-    1, 0, 0
+    0, 0, 0
   };

 static struct haifa_sched_info ebb_sched_info =


I would like to remove the cselib code from the scheduler (and,
perhaps, later also from alias.c). It seems to me that:

* the benefit is really small
* there is a better alternative available (selective scheduler)
* that it is just safer to try to minimize the amount of code that
receives so little testing

The latter is especially true for such complicated code as the
scheduler and alias analysis.

What do you all think about this?

Ciao!
Steven