optimization problem in flow

[scott snyder <snyder at fnal dot gov>]

hi -

I just ran into a problem with the gcc optimizer producing incorrect
code.  This is with the cvs version of gcc (2.96 20000222 (experimental)),
on an i686-pc-linux-gnu platform (RH 6.1).

The following input shows the problem when compiled with the
c++ compiler with -O2 (this is distilled from code in libstdc++ v3).
[Nb, in this version of the compiler, there was another, trivial,
problem in init_output_buffer that caused an ICE.  But that's already
been fixed in cvs.]


- x.cc ----------------------------------------------------
void _M_do_left_shift(unsigned __shift, unsigned long _M_w[2])
{
    const unsigned __wshift = __shift / 32;
    const unsigned __sub_offset = 32 - __shift;

    unsigned __n = 1;
    for ( ; __n > __wshift; --__n)
      _M_w[__n] = (_M_w[__n] << __shift) |
		((_M_w[__n - 1] >> __sub_offset) );
}


-----------------------------------------------------------

Here's the start of the generated code for this routine.
Note the use of the stack slot -16(%ebp):

_M_do_left_shift__FUiPUl:
.LFB1:
	pushl	%ebp
.LCFI0:
	movl	%esp, %ebp
.LCFI1:
	pushl	%edi
.LCFI2:
	pushl	%esi
.LCFI3:
	pushl	%ebx
.LCFI4:
	movl	$1, %ebx
	subl	$8, %esp
.LCFI5:
	movl	8(%ebp), %edi
	movl	%edi, %esi
	shrl	$5, %esi
	subl	%edi, -16(%ebp)  ; <-- reference to uninitialized stack slot
	cmpl	%esi, %ebx

The subl instruction comes from the statement

    const unsigned __sub_offset = 32 - __shift;

and is the subtraction of __shift.  However, it appears that an initial
store of 32 to the local got lost.

I tried looking at the RTL dumps to pinpoint the pass where the problem
appears.  In the dump 13.greg, i find the sequence:

(insn 25 20 27 (set (mem/u:SI (plus:SI (reg:SI 6 ebp)
                (const_int -16 [0xfffffff0])) 0)
        (const_int 32 [0x20])) 37 {*movsi_1} (nil)
    (nil))

(note 27 25 29 "" NOTE_INSN_DELETED)

(insn 29 27 34 (parallel[ 
            (set (mem/u:SI (plus:SI (reg:SI 6 ebp)
                        (const_int -16 [0xfffffff0])) 0)
                (minus:SI (mem/u:SI (plus:SI (reg:SI 6 ebp)
                            (const_int -16 [0xfffffff0])) 0)
                    (reg/v:SI 5 edi)))
            (clobber (reg:CC 17 flags))
        ] ) 198 {*subsi_1} (insn_list 25 (nil))
    (nil))


But in dump 14.flow2, this is changed to:

(note 25 20 27 "" NOTE_INSN_DELETED)

(note 27 25 29 "" NOTE_INSN_DELETED)

(insn 29 27 34 (parallel[ 
            (set (mem/u:SI (plus:SI (reg:SI 6 ebp)
                        (const_int -16 [0xfffffff0])) 0)
                (minus:SI (mem/u:SI (plus:SI (reg:SI 6 ebp)
                            (const_int -16 [0xfffffff0])) 0)
                    (reg/v:SI 5 edi)))
            (clobber (reg:CC 17 flags))
        ] ) 198 {*subsi_1} (insn_list 25 (nil))
    (expr_list:REG_UNUSED (reg:CC 17 flags)
        (nil)))


So the store gets erroneously deleted in the second flow pass.
I tried stepping through the code in flow.c to see what was going
on.  What i found was that when propagate_block() calls mark_used_regs()
for the `minus' insn, the stack slot -16(ebp) is not removed
from mem_set_list.  To test whether this should happen,
mark_used_regs() calls anti_dependence() with two identical
arguments (the mem expression from the minus rtx).  The reason,
in turn, that anti_dependence returns false is that the rtx has the
unchanging flag set.

I tried making the following quick hack to flow.c to work around this.
I don't think that this is a correct fix; however, it fixes
the problem i was seeing and doesn't cause any testsuite regressions.

thanks,
sss

2000-02-22  scott snyder  <snyder@fnal.gov>

	* flow.c (mark_used_regs): Match an element of mem_set_list if
	rtx_equal_p, as well as anti_dependence.

--- flow.c-orig	Tue Feb 22 20:52:49 2000
+++ flow.c	Tue Feb 22 20:52:58 2000
@@ -4332,7 +4332,8 @@ mark_used_regs (needed, live, x, flags, 
 	      while (temp)
 		{
 		  next = XEXP (temp, 1);
-		  if (anti_dependence (XEXP (temp, 0), x))
+		  if (anti_dependence (XEXP (temp, 0), x) ||
+                      rtx_equal_p (XEXP (temp, 0), x))
 		    {
 		      /* Splice temp out of the list.  */
 		      if (prev)