The "980505-1.c" bug (The Story Continued)

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

Heya,

I finally understand what is happening, and thus what is wrong :).
I suppose that others that looked at this problem *already* understood,
but hey - I'm new to this whole compiler ;)

Nevertheless, let me try to explain.

To recall, the test case is as follows:

int f(int) __attribute__((const));
void g(void)
{
   int f1, f2, x;
   x = 1;
   f1 = f(x);
   x = 2;
   f2 = f(x);
   if (f1 == f2)	// This is always true
     abort();
}

At first register 23 is assigned to `x', register 24 is assigned to `f1'
and register 25 is assigned to `f2'.

After the first call to f(), the assignment to `f1' is generated as:

(insn 18 16 20 (set (reg:SI 24)
        (reg:SI 0 %eax)) -1 (nil)
    (insn_list:REG_RETVAL 12 (expr_list:REG_EQUAL (expr_list (symbol_ref:SI ("f"))
                (expr_list (reg/v:SI 23)
                    (nil)))
            (nil))))

And after the second call to f(), the assignment to `f2' is generated as:

(insn 32 30 34 (set (reg:SI 25)
        (reg:SI 0 %eax)) -1 (nil)
    (insn_list:REG_RETVAL 26 (expr_list:REG_EQUAL (expr_list (symbol_ref:SI ("f"))
                (expr_list (reg/v:SI 23)
                    (nil)))
            (nil))))

Where the inner expr_list, the arguments passed to function f, is again
(reg/v:SI 23) of course: In both cases f(x) is called.

The problem now is that optimisation done before cse2 eliminates register 23:
The constants 1 and 2 are placed on the stack immedeately before the call to f.

The way cse works is that it can contain invalid expressions in its table
(The table[hash] with linked expressions that are equivalent (invalid == in
the linked list but not equivalent)).
An expression in the table is considered invalid when it contains any
register that is invalid.  A register is invalid when it was assigned a new
value after the last time it was added to the table (this is logical: the
entry in the table is then not valid/equivalent anymore, its value was
changed).

This is detected with reg_tick[reg_no], which counts the number of times a
register was changed, and reg_in_table[reg_no], which counts the number of
times a certain register was added to the table.  When these values are
not equal, the expressions containing the register in the table are ignored
and never considered to be equivalent.

Now here is why it goes wrong:
On entry of cse_main for the second time, we start over with a clean table
and the values 0 (none) and -1 (not in table) in respectively reg_tick[23]
and reg_in_table[23].  Ie:

reg_tick[23] == 0       (never assigned a value to register 23)
reg_in_table[23] == -1  (no expression with register 23 in the table)

which is ok.

Then the CSE comes to the expression

(insn 18 16 26 (set (reg:SI 24)
        (reg:SI 0 %eax)) 54 {movsi+2} (nil)
    (insn_list:REG_RETVAL 12 (expr_list:REG_EQUAL (expr_list (symbol_ref:SI ("f"))
                (expr_list (reg/v:SI 23)
                    (nil)))
            (nil))))

and adds to the table that (reg:SI 24) is now equivalent to the RTX

(expr_list (symbol_ref:SI ("f"))
      (expr_list (reg/v:SI 23)
          (nil)))

And thus (reg/v:SI 23) was added to the table (as part of this expression).

The WEIRD result of adding this *uninitialized* register to the table is
that reg_in_table[23] is incremented - without any other change:

reg_tick[23] == 0
reg_in_table[23] == 0		<-- Just incremented by one

Now reg_tick[23] == reg_in_table[23], and the compiler thinks that
register 23 has a VALID value!

Therefore, the next time it sees register 23, in the second call, it concludes
that the expressions are equal, and thus f2 == f1 == f(register 23).

------------------
Possible solutions

The solution that would lead to the best optimisation is by making sure that
the expression list of the call is correct: The constants are put directly
on the stack, so the expression list should say THAT, and not say that register
23 was used.

However, note that this bug will also go away if register 23 was used for
something else: Then reg_tick[23] != reg_in_table[23] at the moment we
reach insn 32 (during cse2) and the existing faulty expression will be removed.

It might therefore be sufficient to just detect the addition of an expression
with an _uninitialized_ register, and than not add it to the table at all.
(This can be detected by checking if reg_in_table[reg_no] becomes 0 after
incrementing it).

Although that will probably eliminate this bug, it will of course also
lead to a possibly slighty less well optimized code, as it will not be
noticed that the return values of twice the same call are equivalent.
However, since this is the cse2, I think that it will be VERY rare that
such a case would occur (due to optimisations between cse1 and cse2).

Comments?

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

PS I put great effort in trying to write mails that are easy to read (ie:
   you read it ONCE and understand it immedeately).  I hope that makes it
   bareable that the post it pretty long.  If you think it is too long no
   matter what, or if it is still hard to follow - please let me know :)