Debugging CSE - reg_tick and reg_in_table

[Carlo Wood <carlo at runaway dot xs4all dot nl>]

After reading the comments at the top of cse.c:

<start quote>
...
   When the value of an expression changes, it is necessary to remove from the
   hash table not just that expression but all expressions whose values
   could be different as a result.
...
     2. If the value changing is a register, all expressions
     containing references to that register, and only those,
     must be removed.

   Because searching the entire hash table for expressions that contain
   a register is very slow, we try to figure out when it isn't necessary.
   Precisely, this is necessary only when expressions have been
   entered in the hash table using this register, and then the value has
   changed, and then another expression wants to be added to refer to
   the register's new value.  This sequence of circumstances is rare
   within any one basic block.

   The vectors `reg_tick' and `reg_in_table' are used to detect this case.
   reg_tick[i] is incremented whenever a value is stored in register i.
   reg_in_table[i] holds -1 if no references to register i have been
   entered in the table; otherwise, it contains the value reg_tick[i] had
   when the references were entered.  If we want to enter a reference
   and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
   Until we want to enter a new entry, the mere fact that the two vectors
   don't match makes the entries be ignored if anyone tries to match them.

<end quote>

... it seemed to me that this is what is going wrong (probably the last
sentence).

I looked more closely at the update and behaviour related to reg_tick
and reg_in_table, and find that BEFORE

(insn 23 20 26 (set (reg/v:SI 23)
        (const_int 2)) -1 (nil)
    (nil))

We have:

                00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
reg_tick:       02 01 01 00 00 00 00 02 01 01 01 01 01 01 01 01 00 00 00 00 00 01 00 01 01 00
reg_in_table:   -1 -1 -1 -1 -1 -1 -1 01 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 01 -1 -1
------------------------------------------------------------------------------ 
Equivalent:     
* (plus:SI (reg:SI 7 %esp)
        (const_int 4))
------------------------------------------------------------------------------
Equivalent:
* (const_int 1)
* (reg/v:SI 23)
------------------------------------------------------------------------------
Equivalent:
* (reg:SI 24)
* (reg/v:SI 21)
* (expr_list (symbol_ref:SI ("f"))
        (expr_list (reg/v:SI 23)
            (nil)))

And after that insn, we have:

                00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
reg_tick:       02 01 01 00 00 00 00 02 01 01 01 01 01 01 01 01 00 00 00 00 00 01 00 02 01 00
reg_in_table:   -1 -1 -1 -1 -1 -1 -1 01 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 01 -1 -1
------------------------------------------------------------------------------ 
Equivalent:     
* (plus:SI (reg:SI 7 %esp)
        (const_int 4))
------------------------------------------------------------------------------
Equivalent:
* (const_int 1)
------------------------------------------------------------------------------
Equivalent:
* (const_int 2)
* (reg/v:SI 23)
------------------------------------------------------------------------------
Equivalent:
* (reg:SI 24)
* (reg/v:SI 21)
* (expr_list (symbol_ref:SI ("f"))
        (expr_list (reg/v:SI 23)
            (nil)))

Note that indeed reg_tick[23] was incremented, but the expression containing
(reg/v:SI 23) was not deleted from `table'.

Now the question; at a specific point I couldn't take a decision wether or
not this is a bug, or this is what we want at that point in the code.
Maybe you remember what is/was the intention of this part:

Breakpoint 3, rehash_using_reg (x=0x81be9e4) at ../../egcs-cvs/gcc/cse.c:1691
1691      if (GET_CODE (x) == SUBREG)
(gdb) n
1697      if (GET_CODE (x) != REG
(gdb) l
1692        x = SUBREG_REG (x);
1693
1694      /* If X is not a register or if the register is known not to be in any
1695         valid entries in the table, we have no work to do.  */
1696
1697      if (GET_CODE (x) != REG
1698          || reg_in_table[REGNO (x)] < 0
1699          || reg_in_table[REGNO (x)] != reg_tick[REGNO (x)])
1700        return;
1701
(gdb) p reg_in_table[23]
$16 = 1
(gdb) p reg_tick[23]
$17 = 2
(gdb) call debug_rtx(x)

(reg/v:SI 23)
(gdb) up               
#1  0x80ec956 in cse_insn (insn=0x81bebe0, in_libcall_block=0) at ../../egcs-cvs/gcc/cse.c:7577
7577                  rehash_using_reg (dest);
(gdb) call debug_rtx(insn)

(insn 23 20 26 (set (reg/v:SI 23)
        (const_int 2)) 54 {movsi+2} (nil)
    (expr_list:REG_EQUAL (const_int 2)
        (nil)))

Question: Do we want to `return' from rehash_using_reg without doing
anything here because reg_in_table[23] != reg_tick[23] ?
Is that correct and intended?

If it is, then I will look further to were it goes wrong :)

-- 
 Carlo Wood  <carlo@runaway.xs4all.nl>

PS Due to the fact that I added quite some debugging code to cse.c,
   the line numbers will not be what you expect :/

PS2 If you still wonder what I mean with "equivalent", here is the debug
   code that I use to print it.  Basicly, I print out the next_same_value
   chains found in `table'.  I give here the whole code because it turns
   out be very handy in debugging cse.c and others might want to use it too :)
   You need to set `top_insn' once to the beginning of the basic block, in
   order to get a continious overview of it.

static void
cse_insn (insn, in_libcall_block)
     rtx insn;
     int in_libcall_block;
{
...
// Put this at the start:
PRINT_RTL(insn, "cse_insn");
...
}

Where

static rtx top_insn;

#define PRINT_RTL(cur_insn, name) \
  do { \
    debug_print_func_rtl(top_insn, insn, __FILE__, __LINE__, name); \
  } while(0)

And

void debug_print_func_rtl(first_insn, cur_insn, file, line, name)
    rtx first_insn;
    rtx cur_insn;
    const char *file;
    int line;
    const char *name;
{
  char fname[256];
  FILE *fn;
  char *p;
  struct timeval t;
  int i;
  gettimeofday(&t, NULL);
  if ((p = strrchr(file, '/')))
    file = p + 1;
  sprintf(fname, "rtl-%lu.%06lu-%s:%04d-%s",
      t.tv_sec, t.tv_usec, file, line, name);
  fn = fopen(fname, "w");
  fprintf(fn, "Current INSN :\n");
  print_inline_rtx(fn, cur_insn, 0);
      fprintf(fn, "\n------------------------------------------------------------------------------\n");
  fprintf(fn, "             \t");
  for (i = 0; i < max_reg; ++i)
    fprintf(fn, "%02d ", i);
  fprintf(fn, "\nreg_tick:    \t");
  for (i = 0; i < max_reg; ++i)
    fprintf(fn, "%02d ", reg_tick[i]);
  fprintf(fn, "\nreg_in_table:\t");
  for (i = 0; i < max_reg; ++i)
    fprintf(fn, "%02d ", reg_in_table[i]);
  fprintf(fn, "\n");
  for (i = 0; i < NBUCKETS; ++i)
  {
    struct table_elt *sh;
    for (sh = table[i]; sh; sh = sh->next_same_hash)
    {
      struct table_elt *p;
      struct table_elt *sv = sh->first_same_value;
      for (p = table[i]; p->first_same_value != sv; p = p->next_same_hash);
      if (p != sh)
        continue;
      fprintf(fn, "------------------------------------------------------------------------------\n");
      fprintf(fn, "Equivalent:\n");
      for (; sv; sv = sv->next_same_value)
      {
        fprintf(fn, "* ");
        print_inline_rtx(fn, sv->exp, 2);
        fprintf(fn, "\n");
      }
    }
  }
  fprintf(fn, "==============================================================================\n");
  if (first_insn)
    print_rtl(fn, first_insn);
  fclose(fn);
}