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

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

[Carlo Wood]

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 :)

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

[Jeffrey A Law]

  In message < 199807100056.CAA11845@jolan.ppro >you write:
  > 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).
Note determining whether or not a reg or memory location is initialized
is not generally a solveable problem.

Even within the context of GCC's local CSE pass it is not a solveable
problem since the reg or memory could be set in a flow predecessor
block -- remember local CSE throws away all information at block boundaries
So it will not know that the register was set in a previous block.

jeff

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

[Carlo Wood]

I wrote:

| 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

Woops. I concluded this from the comments at the start of cse.c,
but it should of course read:

  The WEIRD result of adding this *uninitialized* register to the table is
  that reg_in_table[23] is set to 0 - without any other change:
  
  reg_tick[23] == 0
  reg_in_table[23] == 0		<-- Just made equal to reg_tick[23]

---

The "libcall" case is just one of the many cases this can happen :/.
I think therefore that Jeffs patch (cvs diff -c3p -r1.39 -r1.40 cse.c)
is not sufficient for the whole family of bugs of this type.

reg_in_table[i] = reg_tick[i]  occurs at one single line in the code.
When I put the following in front of it:

if (reg_tick[i] == 0)
  abort();

then, with Jeffs patch added, "make check-gcc" fails for THOUSANDS of
test cases!  In other words: It is VERY commmon that an expression with
an uninitialized register is validated as having a meaningful value :/.

I am afraid that the only correct way to go is to tackle all different
cases seperately :/.  In the mean time the following "work around" works:

if (reg_tick[i] > 0)
  reg_in_table[i] = reg_tick[i];

instead of just "reg_in_table[i] = reg_tick[i]" thus.

The disadvantage of this is that it is possible to get less then optimal
optimisation.  But I suppose it doesn't happen that often that it makes a
difference ;) (because out of thousands, only one test case really resulted
in a bug; and I expect an equivalent percentage to get less well optimized).

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

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

[Jeffrey A Law]

  In message < 199807110128.DAA16618@jolan.ppro >you write:
  > The "libcall" case is just one of the many cases this can happen :/.
  > I think therefore that Jeffs patch (cvs diff -c3p -r1.39 -r1.40 cse.c)
  > is not sufficient for the whole family of bugs of this type.
  > 
  > reg_in_table[i] = reg_tick[i]  occurs at one single line in the code.
  > When I put the following in front of it:
  > 
  > if (reg_tick[i] == 0)
  >   abort();
  > 
  > then, with Jeffs patch added, "make check-gcc" fails for THOUSANDS of
  > test cases!  In other words: It is VERY commmon that an expression with
  > an uninitialized register is validated as having a meaningful value :/.
Nope.  See my previous message.  It is common for local CSE to not see an
initializing instruction for a register.  This is not a problem.

jeff

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

[Jeffrey A Law]

You're missing a critical piece of understanding.

The references to (reg 23) in the notes of the RETVAL insn are wrong
once CSE changes the code in the libcall block to use the constant
instead of (reg 23) as an argument.

The notes should have been modified during the first CSE pass to refer
to the real arguments used in the libcall sequence.

This is what my patch fixed.  The notes in the RETVAL insn are updated
at the same time as the instructions in the libcall sequence itself are
updated.


You briefly touched on this in one of your messages:

  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.

This is exactly what my patch does.




--


jeff

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

[Carlo Wood]

| Nope.  See my previous message.  It is common for local CSE to not see an
| initializing instruction for a register.  This is not a problem.

Ah.  Than it makes sense that almost every test case broke ;).
Thanks for taking the time to explain this to me!

I suppose I am fully satified now with how this bug was handled (by you),
learned a lot about cse, and wil be moving on to the next bug :)

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