CSE deletes valid REG_EQUAL?

CSE deletes valid REG_EQUAL?

[Xionghu Luo]

Hi all,

In PR51505(https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51505), Paolo Bonzini 
added the code to delete REG_EQUAL notes in df_remove_dead_eq_notes:

gcc/df-problems.c:
df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
{
...
	case REG_EQUAL:
	case REG_EQUIV:
	  {
	    /* Remove the notes that refer to dead registers.  As we have at most
	       one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
	       so we need to purge the complete EQ_USES vector when removing
	       the note using df_notes_rescan.  */
	    df_ref use;
	    bool deleted = false;

	    FOR_EACH_INSN_EQ_USE (use, insn)
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
		  && DF_REF_LOC (use)
		  && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
		  && !bitmap_bit_p (live, DF_REF_REGNO (use))
		  && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
		{
		  deleted = true;
		  break;
		}
	    if (deleted)
	      {
		rtx next;
		if (REG_DEAD_DEBUGGING)
		  df_print_note ("deleting: ", insn, link);
		next = XEXP (link, 1);
		free_EXPR_LIST_node (link);
		*pprev = link = next;
		df_notes_rescan (insn);
	      }
...
}


while I have a test case as below:


typedef long myint_t;
__attribute__ ((noinline)) myint_t
hash_loop (myint_t nblocks, myint_t hash)
{
    int i;
    for (i = 0; i < nblocks; i++)
      hash = ((hash + 13) | hash) + 0x66546b64;
    return hash;
}

before cse1:

   22: L22:
   16: NOTE_INSN_BASIC_BLOCK 4
   17: r125:DI=r120:DI+0xd
   18: r118:DI=r125:DI|r120:DI
   19: r126:DI=r118:DI+0x66540000
   20: r120:DI=r126:DI+0x6b64
      REG_EQUAL r118:DI+0x66546b64
   21: r119:DI=r119:DI-0x1
   23: r127:CC=cmp(r119:DI,0)
   24: pc={(r127:CC!=0)?L22:pc}
      REG_BR_PROB 955630228

The dump in cse1:

   16: NOTE_INSN_BASIC_BLOCK 4
   17: r125:DI=r120:DI+0xd
   18: r118:DI=r125:DI|r120:DI
      REG_DEAD r125:DI
      REG_DEAD r120:DI
   19: r126:DI=r118:DI+0x66540000
      REG_DEAD r118:DI
   20: r120:DI=r126:DI+0x6b64
      REG_DEAD r126:DI
   21: r119:DI=r119:DI-0x1
   23: r127:CC=cmp(r119:DI,0)
   24: pc={(r127:CC!=0)?L22:pc}
      REG_DEAD r127:CC
      REG_BR_PROB 955630228
      ; pc falls through to BB 6


The output shows "REQ_EQUAL r118:DI+0x66546b64" is deleted by df_remove_dead_eq_notes,
but r120:DI is not REG_DEAD here, so is it correct here to check insn use and find that
r118:DI is dead then do the delete?


Thanks,
Xionghu

Re: CSE deletes valid REG_EQUAL?

[Jeff Law]

On 11/12/20 7:02 PM, Xionghu Luo via Gcc wrote:
> Hi all,
>
> In PR51505(https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51505), Paolo Bonzini 
> added the code to delete REG_EQUAL notes in df_remove_dead_eq_notes:
>
> gcc/df-problems.c:
> df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
> {
> ...
> 	case REG_EQUAL:
> 	case REG_EQUIV:
> 	  {
> 	    /* Remove the notes that refer to dead registers.  As we have at most
> 	       one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
> 	       so we need to purge the complete EQ_USES vector when removing
> 	       the note using df_notes_rescan.  */
> 	    df_ref use;
> 	    bool deleted = false;
>
> 	    FOR_EACH_INSN_EQ_USE (use, insn)
> 	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
> 		  && DF_REF_LOC (use)
> 		  && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
> 		  && !bitmap_bit_p (live, DF_REF_REGNO (use))
> 		  && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
> 		{
> 		  deleted = true;
> 		  break;
> 		}
> 	    if (deleted)
> 	      {
> 		rtx next;
> 		if (REG_DEAD_DEBUGGING)
> 		  df_print_note ("deleting: ", insn, link);
> 		next = XEXP (link, 1);
> 		free_EXPR_LIST_node (link);
> 		*pprev = link = next;
> 		df_notes_rescan (insn);
> 	      }
> ...
> }
>
>
> while I have a test case as below:
>
>
> typedef long myint_t;
> __attribute__ ((noinline)) myint_t
> hash_loop (myint_t nblocks, myint_t hash)
> {
>     int i;
>     for (i = 0; i < nblocks; i++)
>       hash = ((hash + 13) | hash) + 0x66546b64;
>     return hash;
> }
>
> before cse1:
>
>    22: L22:
>    16: NOTE_INSN_BASIC_BLOCK 4
>    17: r125:DI=r120:DI+0xd
>    18: r118:DI=r125:DI|r120:DI
>    19: r126:DI=r118:DI+0x66540000
>    20: r120:DI=r126:DI+0x6b64
>       REG_EQUAL r118:DI+0x66546b64
>    21: r119:DI=r119:DI-0x1
>    23: r127:CC=cmp(r119:DI,0)
>    24: pc={(r127:CC!=0)?L22:pc}
>       REG_BR_PROB 955630228
>
> The dump in cse1:
>
>    16: NOTE_INSN_BASIC_BLOCK 4
>    17: r125:DI=r120:DI+0xd
>    18: r118:DI=r125:DI|r120:DI
>       REG_DEAD r125:DI
>       REG_DEAD r120:DI
>    19: r126:DI=r118:DI+0x66540000
>       REG_DEAD r118:DI
>    20: r120:DI=r126:DI+0x6b64
>       REG_DEAD r126:DI
>    21: r119:DI=r119:DI-0x1
>    23: r127:CC=cmp(r119:DI,0)
>    24: pc={(r127:CC!=0)?L22:pc}
>       REG_DEAD r127:CC
>       REG_BR_PROB 955630228
>       ; pc falls through to BB 6
>
>
> The output shows "REQ_EQUAL r118:DI+0x66546b64" is deleted by df_remove_dead_eq_notes,
> but r120:DI is not REG_DEAD here, so is it correct here to check insn use and find that
> r118:DI is dead then do the delete?

It doesn't matter where the death occurs, any REG_DEAD note will cause
the REG_EQUAL note to be removed.  So given the death note for r118,
then any REG_EQUAL note that references r118 will be removed.  This is
overly pessimistic as the note may still be valid/useful at some
points.  See

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92291


Jeff


ps.  Note that a REG_EQUAL note is valid at a particular point in the IL
-- it is not a function-wide equivalence.  So you have to be careful
using such values as they can be invalidated by other statements. 
Contrast to a REG_EQUIV note where the equivalence is global and you
don't have to worry about invalidation.

Re: CSE deletes valid REG_EQUAL?

[Segher Boessenkool]

Hi guys,

On Thu, Nov 12, 2020 at 09:10:14PM -0700, Jeff Law wrote:
> On 11/12/20 7:02 PM, Xionghu Luo via Gcc wrote:
> > The output shows "REQ_EQUAL r118:DI+0x66546b64" is deleted by df_remove_dead_eq_notes,
> > but r120:DI is not REG_DEAD here, so is it correct here to check insn use and find that
> > r118:DI is dead then do the delete?
> 
> It doesn't matter where the death occurs, any REG_DEAD note will cause
> the REG_EQUAL note to be removed.  So given the death note for r118,
> then any REG_EQUAL note that references r118 will be removed.  This is
> overly pessimistic as the note may still be valid/useful at some
> points.  See
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92291

The note even *always* is valid where it is!  As you say, the REG_EQUAL
is only (necessarily) valid at *that* insn.  And this insn *sets* the
reg (that is the only case when a REG_EQ* is allowed at all), so if the
eq reg is dead (i.e. unused) the whole insn is, and the insn can be
removed.

Removing all REG_EQUAL notes for regs that become dead anywhere seems
to just be a thinko?  All pseudos are dead somewhere!  (Yeah okay,
infinite loops, but other than that.)


Segher

Re: CSE deletes valid REG_EQUAL?

[Jeff Law]

On 11/13/20 6:55 AM, Segher Boessenkool wrote:
> Hi guys,
>
> On Thu, Nov 12, 2020 at 09:10:14PM -0700, Jeff Law wrote:
>> On 11/12/20 7:02 PM, Xionghu Luo via Gcc wrote:
>>> The output shows "REQ_EQUAL r118:DI+0x66546b64" is deleted by df_remove_dead_eq_notes,
>>> but r120:DI is not REG_DEAD here, so is it correct here to check insn use and find that
>>> r118:DI is dead then do the delete?
>> It doesn't matter where the death occurs, any REG_DEAD note will cause
>> the REG_EQUAL note to be removed.  So given the death note for r118,
>> then any REG_EQUAL note that references r118 will be removed.  This is
>> overly pessimistic as the note may still be valid/useful at some
>> points.  See
>>
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92291
> The note even *always* is valid where it is!  As you say, the REG_EQUAL
> is only (necessarily) valid at *that* insn.  And this insn *sets* the
> reg (that is the only case when a REG_EQ* is allowed at all), so if the
> eq reg is dead (i.e. unused) the whole insn is, and the insn can be
> removed.
>
> Removing all REG_EQUAL notes for regs that become dead anywhere seems
> to just be a thinko?  All pseudos are dead somewhere!  (Yeah okay,
> infinite loops, but other than that.)
Yea, but the code which wipes the notes probably has no sense of where
in the RTL stream the note is valid and where it is not.  So it does the
fairly dumb thing and just ends up wiping them all away because as you
noted, most pseudos have a death somewhere.  One might argue that the
code is OK as-is, but just needs to be run later.  After cse2 would be
the most logical location since CSE is probably the heaviest user of the
notes.  But I'd worry that the problems referenced in c#2 of bz51505
could crop up in other contexts than just combine.

jeff

Re: CSE deletes valid REG_EQUAL?

[Paolo Bonzini]

On 17/11/20 02:12, Jeff Law wrote:
>> Removing all REG_EQUAL notes for regs that become dead anywhere

That's not what it does.

>> seems to just be a thinko?  All pseudos are dead somewhere!  (Yeah okay,
>> infinite loops, but other than that.)
>
> Yea, but the code which wipes the notes probably has no sense of where
> in the RTL stream the note is valid and where it is not.  So it does the
> fairly dumb thing and just ends up wiping them all away because as you
> noted, most pseudos have a death somewhere.

It shouldn't wipe all of them.  It doesn't look at all REG_EQUAL notes 
in the function; it looks at the notes one insn at a time, and wipes the 
REG_EQUAL notes for registers that are dead _at that insn_.  See how the 
loop uses DF_INSN_EQ_USES:

            for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++)
              {
                df_ref use = *use_rec;
                if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
                    && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
                    && ! bitmap_bit_p (live, DF_REF_REGNO (use)))
                  {
                    deleted = true;
                    break;
                  }
              }

and it is called as

       df_kill_notes (insn, live);

> One might argue that the code is OK as-is, but just needs to be run
> later.  After cse2 would be the most logical location since CSE is
> probably the heaviest user of the notes.  But I'd worry that the
> problems referenced in c#2 of bz51505 could crop up in other contexts
> than just combine.

Yeah, it was a design decision of DF to ignore REG_EQUAL/REG_EQUIV notes 
when computing liveness and adding REG_DEAD notes[1].  Unfortunately 
this all predates my involvement in DF and I'm also unfamiliar with how 
REG_DEAD and REG_EQUAL notes interacted in flow.c times.  But it's very 
unlikely that after ~10 years there aren't more places with the same 
issue that PR51505 worked around.

Paolo

[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51505#c3