[PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Jakub Jelinek]

Hi!

The following testcase ICEs on x86_64-linux since df_note_add_problem ()
call has been added to mode switching.
The problem is that the pro_and_epilogue pass in
prepare_shrink_wrap -> copyprop_hardreg_forward_bb_without_debug_insn
uses regcprop.cc infrastructure which relies on accurate REG_DEAD/REG_UNUSED
notes.  E.g. regcprop.cc
  /* We need accurate notes.  Earlier passes such as if-conversion may
     leave notes in an inconsistent state.  */
  df_note_add_problem ();
documents that.  On the testcase below it is in particular the
      /* Detect obviously dead sets (via REG_UNUSED notes) and remove them.  */
      if (set
          && !RTX_FRAME_RELATED_P (insn)
          && NONJUMP_INSN_P (insn)
          && !may_trap_p (set)
          && find_reg_note (insn, REG_UNUSED, SET_DEST (set))
          && !side_effects_p (SET_SRC (set))
          && !side_effects_p (SET_DEST (set)))
        {
          bool last = insn == BB_END (bb);
          delete_insn (insn);
          if (last)
            break;
          continue;
        } 
case where a stale REG_UNUSED note breaks stuff up (added in vzeroupper
pass, redundant insn after it deleted later).

The following patch makes sure the notes are not stale if shrink wrapping
is enabled.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2023-12-02  Jakub Jelinek  <jakub@redhat.com>

	PR rtl-optimization/112760
	* function.cc (thread_prologue_and_epilogue_insns): If
	SHRINK_WRAPPING_ENABLED, call df_note_add_problem before calling
	df_analyze.

	* gcc.dg/pr112760.c: New test.

--- gcc/function.cc.jj	2023-11-07 08:32:01.699254744 +0100
+++ gcc/function.cc	2023-12-01 13:42:51.885189341 +0100
@@ -6036,6 +6036,11 @@ make_epilogue_seq (void)
 void
 thread_prologue_and_epilogue_insns (void)
 {
+  /* prepare_shrink_wrap uses copyprop_hardreg_forward_bb_without_debug_insn
+     which uses regcprop.cc functions which rely on accurate REG_UNUSED
+     and REG_DEAD notes.  */
+  if (SHRINK_WRAPPING_ENABLED)
+    df_note_add_problem ();
   df_analyze ();
 
   /* Can't deal with multiple successors of the entry block at the
--- gcc/testsuite/gcc.dg/pr112760.c.jj	2023-12-01 13:46:57.444746529 +0100
+++ gcc/testsuite/gcc.dg/pr112760.c	2023-12-01 13:46:36.729036971 +0100
@@ -0,0 +1,22 @@
+/* PR rtl-optimization/112760 */
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-dce -fno-guess-branch-probability --param=max-cse-insns=0" } */
+/* { dg-additional-options "-m8bit-idiv -mavx" { target i?86-*-* x86_64-*-* } } */
+
+unsigned g;
+
+__attribute__((__noipa__)) unsigned short
+foo (unsigned short a, unsigned short b)
+{
+  unsigned short x = __builtin_add_overflow_p (a, g, (unsigned short) 0);
+  g -= g / b;
+  return x;
+}
+
+int
+main ()
+{
+  unsigned short x = foo (40, 6);
+  if (x != 0)
+    __builtin_abort ();
+}

	Jakub

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Richard Sandiford]

Jakub Jelinek <jakub@redhat.com> writes:
> Hi!
>
> The following testcase ICEs on x86_64-linux since df_note_add_problem ()
> call has been added to mode switching.
> The problem is that the pro_and_epilogue pass in
> prepare_shrink_wrap -> copyprop_hardreg_forward_bb_without_debug_insn
> uses regcprop.cc infrastructure which relies on accurate REG_DEAD/REG_UNUSED
> notes.  E.g. regcprop.cc
>   /* We need accurate notes.  Earlier passes such as if-conversion may
>      leave notes in an inconsistent state.  */
>   df_note_add_problem ();
> documents that.  On the testcase below it is in particular the
>       /* Detect obviously dead sets (via REG_UNUSED notes) and remove them.  */
>       if (set
>           && !RTX_FRAME_RELATED_P (insn)
>           && NONJUMP_INSN_P (insn)
>           && !may_trap_p (set)
>           && find_reg_note (insn, REG_UNUSED, SET_DEST (set))
>           && !side_effects_p (SET_SRC (set))
>           && !side_effects_p (SET_DEST (set)))
>         {
>           bool last = insn == BB_END (bb);
>           delete_insn (insn);
>           if (last)
>             break;
>           continue;
>         } 
> case where a stale REG_UNUSED note breaks stuff up (added in vzeroupper
> pass, redundant insn after it deleted later).
>
> The following patch makes sure the notes are not stale if shrink wrapping
> is enabled.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

I still maintain that so much stuff relies on the lack of false-positive
REG_UNUSED notes that (whatever the intention might have been) we need
to prevent the false positive.  Like Andrew says, any use of single_set
is suspect if there's a REG_UNUSED note for something that is in fact used.

So sorry to be awkward, but I don't think this is the way to go.  I think
we'll just end up playing whack-a-mole and adding df_note_add_problem to
lots of passes.

(FTR, I'm not saying passes have to avoid false negatives, just false
positives.  If a pass updates an instruction with a REG_UNUSED note,
and the pass is no longer sure whether the register is unused or not,
the pass can just delete the note.)

Richard

> 2023-12-02  Jakub Jelinek  <jakub@redhat.com>
>
> 	PR rtl-optimization/112760
> 	* function.cc (thread_prologue_and_epilogue_insns): If
> 	SHRINK_WRAPPING_ENABLED, call df_note_add_problem before calling
> 	df_analyze.
>
> 	* gcc.dg/pr112760.c: New test.
>
> --- gcc/function.cc.jj	2023-11-07 08:32:01.699254744 +0100
> +++ gcc/function.cc	2023-12-01 13:42:51.885189341 +0100
> @@ -6036,6 +6036,11 @@ make_epilogue_seq (void)
>  void
>  thread_prologue_and_epilogue_insns (void)
>  {
> +  /* prepare_shrink_wrap uses copyprop_hardreg_forward_bb_without_debug_insn
> +     which uses regcprop.cc functions which rely on accurate REG_UNUSED
> +     and REG_DEAD notes.  */
> +  if (SHRINK_WRAPPING_ENABLED)
> +    df_note_add_problem ();
>    df_analyze ();
>  
>    /* Can't deal with multiple successors of the entry block at the
> --- gcc/testsuite/gcc.dg/pr112760.c.jj	2023-12-01 13:46:57.444746529 +0100
> +++ gcc/testsuite/gcc.dg/pr112760.c	2023-12-01 13:46:36.729036971 +0100
> @@ -0,0 +1,22 @@
> +/* PR rtl-optimization/112760 */
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fno-dce -fno-guess-branch-probability --param=max-cse-insns=0" } */
> +/* { dg-additional-options "-m8bit-idiv -mavx" { target i?86-*-* x86_64-*-* } } */
> +
> +unsigned g;
> +
> +__attribute__((__noipa__)) unsigned short
> +foo (unsigned short a, unsigned short b)
> +{
> +  unsigned short x = __builtin_add_overflow_p (a, g, (unsigned short) 0);
> +  g -= g / b;
> +  return x;
> +}
> +
> +int
> +main ()
> +{
> +  unsigned short x = foo (40, 6);
> +  if (x != 0)
> +    __builtin_abort ();
> +}
>
> 	Jakub

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Eric Botcazou]

> So sorry to be awkward, but I don't think this is the way to go.  I think
> we'll just end up playing whack-a-mole and adding df_note_add_problem to
> lots of passes.

We have doing that for the past 15 years though, so what has changed?

> (FTR, I'm not saying passes have to avoid false negatives, just false
> positives.  If a pass updates an instruction with a REG_UNUSED note,
> and the pass is no longer sure whether the register is unused or not,
> the pass can just delete the note.)

Reintroducing the manual management of such notes would be a step backward.

-- 
Eric Botcazou

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Richard Sandiford]

Eric Botcazou <botcazou@adacore.com> writes:
>> So sorry to be awkward, but I don't think this is the way to go.  I think
>> we'll just end up playing whack-a-mole and adding df_note_add_problem to
>> lots of passes.
>
> We have doing that for the past 15 years though, so what has changed?

Off-hand, I couldn't remember a case where we'd done this specifically
for false-positive REG_UNUSED notes.  (There probably were cases though.)

>> (FTR, I'm not saying passes have to avoid false negatives, just false
>> positives.  If a pass updates an instruction with a REG_UNUSED note,
>> and the pass is no longer sure whether the register is unused or not,
>> the pass can just delete the note.)
>
> Reintroducing the manual management of such notes would be a step backward.

I think false-positive REG_UNUSED notes are fundamentally different
from the other cases though.  If a register is unused then its natural
state is to remain unused.  The register will only become used if something
goes out of its way to add new uses of an instruction result that "just
happens to be there".  That's a deliberate decision and needs some
analysis to prove that it's safe.  Requiring the pass to clear REG_UNUSED
notes too doesn't seem like a significant extra burden.

Trying to reduce false-negative REG_UNUSED notes is different,
since deleting any instruction could in principle make a register
go from used to unused.  Same for REG_DEAD notes: if a pass deletes
an instruction with a REG_DEAD note then it shouldn't have to figure
out where the new death occurs.

Not sure how representative this is, but I tried the hack below
to flag cases where single_set is used in passes that don't have
up-to-date notes, then ran it on execute.exp.  The checking fired
for every version of every test.  The collected passes were:

single_set: bbro
single_set: cc_fusion
single_set: ce1
single_set: ce2
single_set: ce3
single_set: cmpelim
single_set: combine
single_set: compgotos
single_set: cprop
single_set: dwarf2
single_set: fold_mem_offsets
single_set: fwprop1
single_set: fwprop2
single_set: gcse2
single_set: hoist
single_set: init-regs
single_set: ira
single_set: jump2
single_set: jump_after_combine
single_set: loop2_done
single_set: loop2_invariant
single_set: postreload
single_set: pro_and_epilogue
single_set: ree
single_set: reload
single_set: rtl_dce
single_set: rtl pre
single_set: sched1
single_set: sched2
single_set: sched_fusion
single_set: sms
single_set: split1
single_set: split2
single_set: split3
single_set: split5
single_set: subreg3
single_set: ud_dce
single_set: vartrack
single_set: web

which is a lot of passes :)

Some of the calls might be OK in context, due to call-specific
circumstances.  But I think it's generally easier to see/show that
a pass is adding new uses of existing defs than it is to prove that
a use of single_set is safe even when notes aren't up-to-date.

Thanks,
Richard


diff --git a/gcc/df-problems.cc b/gcc/df-problems.cc
index d2cfaf7f50f..ece49f041e0 100644
--- a/gcc/df-problems.cc
+++ b/gcc/df-problems.cc
@@ -3782,6 +3782,8 @@ void
 df_note_add_problem (void)
 {
   df_add_problem (&problem_NOTE);
+  extern bool single_set_ok;
+  single_set_ok = true;
 }
 
 
diff --git a/gcc/passes.cc b/gcc/passes.cc
index 6f894a41d22..d8e12ea2512 100644
--- a/gcc/passes.cc
+++ b/gcc/passes.cc
@@ -2637,9 +2637,14 @@ execute_one_pass (opt_pass *pass)
     do_per_function (verify_curr_properties,
 		     (void *)(size_t)pass->properties_required);
 
+  extern bool single_set_ok;
+  single_set_ok = !df;
+
   /* Do it!  */
   todo_after = pass->execute (cfun);
 
+  single_set_ok = !df;
+
   if (todo_after & TODO_discard_function)
     {
       /* Stop timevar.  */
diff --git a/gcc/rtl.h b/gcc/rtl.h
index e4b6cc0dbb5..af3bd1b7cfa 100644
--- a/gcc/rtl.h
+++ b/gcc/rtl.h
@@ -3607,8 +3607,11 @@ extern void add_auto_inc_notes (rtx_insn *, rtx);
 
 /* Handle the cheap and common cases inline for performance.  */
 
+extern void check_single_set ();
 inline rtx single_set (const rtx_insn *insn)
 {
+  check_single_set ();
+
   if (!INSN_P (insn))
     return NULL_RTX;
 
diff --git a/gcc/rtlanal.cc b/gcc/rtlanal.cc
index 87267ee3b88..e0207e2753a 100644
--- a/gcc/rtlanal.cc
+++ b/gcc/rtlanal.cc
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "rtl-iter.h"
 #include "hard-reg-set.h"
 #include "function-abi.h"
+#include "tree-pass.h"
 
 /* Forward declarations */
 static void set_of_1 (rtx, const_rtx, void *);
@@ -1543,6 +1544,20 @@ record_hard_reg_uses (rtx *px, void *data)
    It may also have CLOBBERs, USEs, or SET whose output
    will not be used, which we ignore.  */
 
+bool single_set_ok;
+void 
+check_single_set ()
+{
+  static opt_pass *last_pass;
+  if (!single_set_ok
+      && current_pass
+      && last_pass != current_pass)
+    {
+      last_pass = current_pass;
+      fprintf (stderr, "single_set: %s\n", current_pass->name);
+    }
+}
+
 rtx
 single_set_2 (const rtx_insn *insn, const_rtx pat)
 {

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Richard Biener]

> Am 02.12.2023 um 14:15 schrieb Richard Sandiford <richard.sandiford@arm.com>:
> 
> Eric Botcazou <botcazou@adacore.com> writes:
>>> So sorry to be awkward, but I don't think this is the way to go.  I think
>>> we'll just end up playing whack-a-mole and adding df_note_add_problem to
>>> lots of passes.
>> 
>> We have doing that for the past 15 years though, so what has changed?
> 
> Off-hand, I couldn't remember a case where we'd done this specifically
> for false-positive REG_UNUSED notes.  (There probably were cases though.)
> 
>>> (FTR, I'm not saying passes have to avoid false negatives, just false
>>> positives.  If a pass updates an instruction with a REG_UNUSED note,
>>> and the pass is no longer sure whether the register is unused or not,
>>> the pass can just delete the note.)
>> 
>> Reintroducing the manual management of such notes would be a step backward.
> 
> I think false-positive REG_UNUSED notes are fundamentally different
> from the other cases though.  If a register is unused then its natural
> state is to remain unused.  The register will only become used if something
> goes out of its way to add new uses of an instruction result that "just
> happens to be there".  That's a deliberate decision and needs some
> analysis to prove that it's safe.  Requiring the pass to clear REG_UNUSED
> notes too doesn't seem like a significant extra burden.
> 
> Trying to reduce false-negative REG_UNUSED notes is different,
> since deleting any instruction could in principle make a register
> go from used to unused.  Same for REG_DEAD notes: if a pass deletes
> an instruction with a REG_DEAD note then it shouldn't have to figure
> out where the new death occurs.
> 
> Not sure how representative this is, but I tried the hack below
> to flag cases where single_set is used in passes that don't have
> up-to-date notes, then ran it on execute.exp.  The checking fired
> for every version of every test.  The collected passes were:
> 
> single_set: bbro
> single_set: cc_fusion
> single_set: ce1
> single_set: ce2
> single_set: ce3
> single_set: cmpelim
> single_set: combine
> single_set: compgotos
> single_set: cprop
> single_set: dwarf2
> single_set: fold_mem_offsets
> single_set: fwprop1
> single_set: fwprop2
> single_set: gcse2
> single_set: hoist
> single_set: init-regs
> single_set: ira
> single_set: jump2
> single_set: jump_after_combine
> single_set: loop2_done
> single_set: loop2_invariant
> single_set: postreload
> single_set: pro_and_epilogue
> single_set: ree
> single_set: reload
> single_set: rtl_dce
> single_set: rtl pre
> single_set: sched1
> single_set: sched2
> single_set: sched_fusion
> single_set: sms
> single_set: split1
> single_set: split2
> single_set: split3
> single_set: split5
> single_set: subreg3
> single_set: ud_dce
> single_set: vartrack
> single_set: web
> 
> which is a lot of passes :)
> 
> Some of the calls might be OK in context, due to call-specific
> circumstances.  But I think it's generally easier to see/show that
> a pass is adding new uses of existing defs than it is to prove that
> a use of single_set is safe even when notes aren't up-to-date.

I think this asks for a verify_notes that checks if notes are conservatively correct as to our definition then?  Not sure if doable for equal/equiv notes though.

Richard 

> Thanks,
> Richard
> 
> 
> diff --git a/gcc/df-problems.cc b/gcc/df-problems.cc
> index d2cfaf7f50f..ece49f041e0 100644
> --- a/gcc/df-problems.cc
> +++ b/gcc/df-problems.cc
> @@ -3782,6 +3782,8 @@ void
> df_note_add_problem (void)
> {
>   df_add_problem (&problem_NOTE);
> +  extern bool single_set_ok;
> +  single_set_ok = true;
> }
> 
> 
> diff --git a/gcc/passes.cc b/gcc/passes.cc
> index 6f894a41d22..d8e12ea2512 100644
> --- a/gcc/passes.cc
> +++ b/gcc/passes.cc
> @@ -2637,9 +2637,14 @@ execute_one_pass (opt_pass *pass)
>     do_per_function (verify_curr_properties,
>             (void *)(size_t)pass->properties_required);
> 
> +  extern bool single_set_ok;
> +  single_set_ok = !df;
> +
>   /* Do it!  */
>   todo_after = pass->execute (cfun);
> 
> +  single_set_ok = !df;
> +
>   if (todo_after & TODO_discard_function)
>     {
>       /* Stop timevar.  */
> diff --git a/gcc/rtl.h b/gcc/rtl.h
> index e4b6cc0dbb5..af3bd1b7cfa 100644
> --- a/gcc/rtl.h
> +++ b/gcc/rtl.h
> @@ -3607,8 +3607,11 @@ extern void add_auto_inc_notes (rtx_insn *, rtx);
> 
> /* Handle the cheap and common cases inline for performance.  */
> 
> +extern void check_single_set ();
> inline rtx single_set (const rtx_insn *insn)
> {
> +  check_single_set ();
> +
>   if (!INSN_P (insn))
>     return NULL_RTX;
> 
> diff --git a/gcc/rtlanal.cc b/gcc/rtlanal.cc
> index 87267ee3b88..e0207e2753a 100644
> --- a/gcc/rtlanal.cc
> +++ b/gcc/rtlanal.cc
> @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
> #include "rtl-iter.h"
> #include "hard-reg-set.h"
> #include "function-abi.h"
> +#include "tree-pass.h"
> 
> /* Forward declarations */
> static void set_of_1 (rtx, const_rtx, void *);
> @@ -1543,6 +1544,20 @@ record_hard_reg_uses (rtx *px, void *data)
>    It may also have CLOBBERs, USEs, or SET whose output
>    will not be used, which we ignore.  */
> 
> +bool single_set_ok;
> +void
> +check_single_set ()
> +{
> +  static opt_pass *last_pass;
> +  if (!single_set_ok
> +      && current_pass
> +      && last_pass != current_pass)
> +    {
> +      last_pass = current_pass;
> +      fprintf (stderr, "single_set: %s\n", current_pass->name);
> +    }
> +}
> +
> rtx
> single_set_2 (const rtx_insn *insn, const_rtx pat)
> {

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Jakub Jelinek]

On Sat, Dec 02, 2023 at 11:04:04AM +0000, Richard Sandiford wrote:
> I still maintain that so much stuff relies on the lack of false-positive
> REG_UNUSED notes that (whatever the intention might have been) we need
> to prevent the false positive.  Like Andrew says, any use of single_set
> is suspect if there's a REG_UNUSED note for something that is in fact used.

The false positive REG_UNUSED in that case comes from
(insn 15 14 35 2 (set (reg:CCZ 17 flags)
        (compare:CCZ (reg:DI 0 ax [111])
            (reg:DI 1 dx [112]))) "pr112760.c":11:22 12 {*cmpdi_1}
     (expr_list:REG_UNUSED (reg:CCZ 17 flags)
        (nil)))
(insn 35 15 36 2 (set (reg:CCZ 17 flags)
        (compare:CCZ (reg:DI 0 ax [111])
            (reg:DI 1 dx [112]))) "pr112760.c":11:22 12 {*cmpdi_1}
     (expr_list:REG_DEAD (reg:DI 1 dx [112])
        (expr_list:REG_DEAD (reg:DI 0 ax [111])
            (nil))))
...
use of flags
Haven't verified what causes the redundant comparison, but postreload cse
then does:
110	      if (!count && cselib_redundant_set_p (body))
111		{
112		  if (check_for_inc_dec (insn))
113		    delete_insn_and_edges (insn);
114		  /* We're done with this insn.  */
115		  goto done;
116		}
So, we'd in such cases need to look up what instruction was the earlier
setter and if it has REG_UNUSED note, drop it.

	Jakub

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Richard Sandiford]

Jakub Jelinek <jakub@redhat.com> writes:
> On Sat, Dec 02, 2023 at 11:04:04AM +0000, Richard Sandiford wrote:
>> I still maintain that so much stuff relies on the lack of false-positive
>> REG_UNUSED notes that (whatever the intention might have been) we need
>> to prevent the false positive.  Like Andrew says, any use of single_set
>> is suspect if there's a REG_UNUSED note for something that is in fact used.
>
> The false positive REG_UNUSED in that case comes from
> (insn 15 14 35 2 (set (reg:CCZ 17 flags)
>         (compare:CCZ (reg:DI 0 ax [111])
>             (reg:DI 1 dx [112]))) "pr112760.c":11:22 12 {*cmpdi_1}
>      (expr_list:REG_UNUSED (reg:CCZ 17 flags)
>         (nil)))
> (insn 35 15 36 2 (set (reg:CCZ 17 flags)
>         (compare:CCZ (reg:DI 0 ax [111])
>             (reg:DI 1 dx [112]))) "pr112760.c":11:22 12 {*cmpdi_1}
>      (expr_list:REG_DEAD (reg:DI 1 dx [112])
>         (expr_list:REG_DEAD (reg:DI 0 ax [111])
>             (nil))))
> ...
> use of flags
> Haven't verified what causes the redundant comparison, but postreload cse
> then does:
> 110	      if (!count && cselib_redundant_set_p (body))
> 111		{
> 112		  if (check_for_inc_dec (insn))
> 113		    delete_insn_and_edges (insn);
> 114		  /* We're done with this insn.  */
> 115		  goto done;
> 116		}
> So, we'd in such cases need to look up what instruction was the earlier
> setter and if it has REG_UNUSED note, drop it.

Hmm, OK.  I guess it's not as simple as I'd imagined.  cselib does have
some code to track which instruction established which equivalence,
but it doesn't currently record what we want, and it would be difficult
to reuse that information here anyway.  Something "simple" like a map of
register numbers to instructions, populated only for REG_UNUSED sets,
would be enough, and low overhead.  But it's not very natural.

Perhaps DF should maintain a flag to say "the current pass keeps
notes up-to-date", with the assumption being that any pass that
uses the notes problem does that.  Then single_set and the
regcprop.cc uses can check that flag.

I don't think it's worth adding the note problem to shrink-wrapping
just for the regcprop code.  If we're prepared to take that compile-time
hit, we might as well run a proper (fast) DCE.

Thanks,
Richard

[PATCH] Maintain a validity flag for REG_UNUSED notes [PR112760] (was Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760])

[Richard Sandiford]

Richard Sandiford <richard.sandiford@arm.com> writes:
> Jakub Jelinek <jakub@redhat.com> writes:
>> On Sat, Dec 02, 2023 at 11:04:04AM +0000, Richard Sandiford wrote:
>>> I still maintain that so much stuff relies on the lack of false-positive
>>> REG_UNUSED notes that (whatever the intention might have been) we need
>>> to prevent the false positive.  Like Andrew says, any use of single_set
>>> is suspect if there's a REG_UNUSED note for something that is in fact used.
>>
>> The false positive REG_UNUSED in that case comes from
>> (insn 15 14 35 2 (set (reg:CCZ 17 flags)
>>         (compare:CCZ (reg:DI 0 ax [111])
>>             (reg:DI 1 dx [112]))) "pr112760.c":11:22 12 {*cmpdi_1}
>>      (expr_list:REG_UNUSED (reg:CCZ 17 flags)
>>         (nil)))
>> (insn 35 15 36 2 (set (reg:CCZ 17 flags)
>>         (compare:CCZ (reg:DI 0 ax [111])
>>             (reg:DI 1 dx [112]))) "pr112760.c":11:22 12 {*cmpdi_1}
>>      (expr_list:REG_DEAD (reg:DI 1 dx [112])
>>         (expr_list:REG_DEAD (reg:DI 0 ax [111])
>>             (nil))))
>> ...
>> use of flags
>> Haven't verified what causes the redundant comparison, but postreload cse
>> then does:
>> 110	      if (!count && cselib_redundant_set_p (body))
>> 111		{
>> 112		  if (check_for_inc_dec (insn))
>> 113		    delete_insn_and_edges (insn);
>> 114		  /* We're done with this insn.  */
>> 115		  goto done;
>> 116		}
>> So, we'd in such cases need to look up what instruction was the earlier
>> setter and if it has REG_UNUSED note, drop it.
>
> Hmm, OK.  I guess it's not as simple as I'd imagined.  cselib does have
> some code to track which instruction established which equivalence,
> but it doesn't currently record what we want, and it would be difficult
> to reuse that information here anyway.  Something "simple" like a map of
> register numbers to instructions, populated only for REG_UNUSED sets,
> would be enough, and low overhead.  But it's not very natural.
>
> Perhaps DF should maintain a flag to say "the current pass keeps
> notes up-to-date", with the assumption being that any pass that
> uses the notes problem does that.  Then single_set and the
> regcprop.cc uses can check that flag.
>
> I don't think it's worth adding the note problem to shrink-wrapping
> just for the regcprop code.  If we're prepared to take that compile-time
> hit, we might as well run a proper (fast) DCE.

Here's a patch that tries to do that.  Boostrapped & regression tested
on aarch64-linux-gnu.  Also tested on x86_64-linux-gnu for the testcase.
(I'll run full x86_64-linux-gnu testing overnight.)

OK to install if that passes?  Not an elegant fix, but it's probably
too much to hope for one of those.

Richard

--------

PR112760 is a miscompilation caused by a stale, false-positive
REG_UNUSED note.  There were originally two consecutive,
identical instructions that set the CC flags.  The first
originally had a REG_UNUSED note, but postreload later deleted
the second in favour of the first, based on cselib_redundant_set_p.

Although in principle it would be possible to remove the note
when making the optimisation, the required bookkeeping wouldn't
fit naturally into what cselib already does.  Doing that would also
arguably be a change of policy.

This patch instead adds a global flag that says whether REG_UNUSED
notes are trustworthy.  The assumption is that any pass that calls
df_note_add_problem cares about REG_UNUSED notes and will keep them
sufficiently up-to-date to support the pass's use of things like
single_set.

gcc/
	PR rtl-optimization/112760
	* df.h (df_d::can_trust_reg_unused_notes): New member variable.
	* df-problems.cc (df_note_add_problem): Set can_trust_reg_unused_notes
	to true.
	* passes.cc (execute_one_pass): Clear can_trust_reg_unused_notes
	after each pass.
	* rtlanal.cc (single_set_2): Check can_trust_reg_unused_notes.
	* regcprop.cc (copyprop_hardreg_forward_1): Likewise.

gcc/testsuite/
	* gcc.dg/pr112760.c: New test.
---
 gcc/df-problems.cc              |  1 +
 gcc/df.h                        |  4 ++++
 gcc/passes.cc                   |  3 +++
 gcc/regcprop.cc                 |  4 +++-
 gcc/rtlanal.cc                  |  8 ++++++--
 gcc/testsuite/gcc.dg/pr112760.c | 22 ++++++++++++++++++++++
 6 files changed, 39 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr112760.c

diff --git a/gcc/df-problems.cc b/gcc/df-problems.cc
index d2cfaf7f50f..d2eb95d35ad 100644
--- a/gcc/df-problems.cc
+++ b/gcc/df-problems.cc
@@ -3782,6 +3782,7 @@ void
 df_note_add_problem (void)
 {
   df_add_problem (&problem_NOTE);
+  df->can_trust_reg_unused_notes = true;
 }
 
 
diff --git a/gcc/df.h b/gcc/df.h
index 402657a7076..a405c000235 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -614,6 +614,10 @@ public:
   /* True if someone added or deleted something from regs_ever_live so
      that the entry and exit blocks need be reprocessed.  */
   bool redo_entry_and_exit;
+
+  /* True if REG_UNUSED notes are up-to-date enough to be free of false
+     positives.  */
+  bool can_trust_reg_unused_notes;
 };
 
 #define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info ((BB)->index))
diff --git a/gcc/passes.cc b/gcc/passes.cc
index 6f894a41d22..0313d0e3689 100644
--- a/gcc/passes.cc
+++ b/gcc/passes.cc
@@ -2640,6 +2640,9 @@ execute_one_pass (opt_pass *pass)
   /* Do it!  */
   todo_after = pass->execute (cfun);
 
+  if (df)
+    df->can_trust_reg_unused_notes = false;
+
   if (todo_after & TODO_discard_function)
     {
       /* Stop timevar.  */
diff --git a/gcc/regcprop.cc b/gcc/regcprop.cc
index a75af2ba7e3..03df9a7cf4f 100644
--- a/gcc/regcprop.cc
+++ b/gcc/regcprop.cc
@@ -820,6 +820,7 @@ copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
       if (set
 	  && !RTX_FRAME_RELATED_P (insn)
 	  && NONJUMP_INSN_P (insn)
+	  && df->can_trust_reg_unused_notes
 	  && !may_trap_p (set)
 	  && find_reg_note (insn, REG_UNUSED, SET_DEST (set))
 	  && !side_effects_p (SET_SRC (set))
@@ -878,7 +879,8 @@ copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
 	 would clobbers.  */
       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 	{
-	  if (REG_NOTE_KIND (link) == REG_UNUSED)
+	  if (df->can_trust_reg_unused_notes
+	      && REG_NOTE_KIND (link) == REG_UNUSED)
 	    {
 	      kill_value (XEXP (link, 0), vd);
 	      /* Furthermore, if the insn looked like a single-set,
diff --git a/gcc/rtlanal.cc b/gcc/rtlanal.cc
index 87267ee3b88..42b07cd9634 100644
--- a/gcc/rtlanal.cc
+++ b/gcc/rtlanal.cc
@@ -1572,7 +1572,9 @@ single_set_2 (const rtx_insn *insn, const_rtx pat)
 		 sets are found in the insn, we check them.  */
 	      if (!set_verified)
 		{
-		  if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
+		  if (df
+		      && df->can_trust_reg_unused_notes
+		      && find_reg_note (insn, REG_UNUSED, SET_DEST (set))
 		      && !side_effects_p (set))
 		    set = NULL;
 		  else
@@ -1580,7 +1582,9 @@ single_set_2 (const rtx_insn *insn, const_rtx pat)
 		}
 	      if (!set)
 		set = sub, set_verified = 0;
-	      else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
+	      else if (!df
+		       || !df->can_trust_reg_unused_notes
+		       || !find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
 		       || side_effects_p (sub))
 		return NULL_RTX;
 	      break;
diff --git a/gcc/testsuite/gcc.dg/pr112760.c b/gcc/testsuite/gcc.dg/pr112760.c
new file mode 100644
index 00000000000..b4ec70e4701
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr112760.c
@@ -0,0 +1,22 @@
+/* PR rtl-optimization/112760 */
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-dce -fno-guess-branch-probability --param=max-cse-insns=0" } */
+/* { dg-additional-options "-m8bit-idiv -mavx" { target i?86-*-* x86_64-*-* } } */
+
+unsigned g;
+
+__attribute__((__noipa__)) unsigned short
+foo (unsigned short a, unsigned short b)
+{
+  unsigned short x = __builtin_add_overflow_p (a, g, (unsigned short) 0);
+  g -= g / b;
+  return x;
+}
+
+int
+main ()
+{
+  unsigned short x = foo (40, 6);
+  if (x != 0)
+    __builtin_abort ();
+}
-- 
2.25.1

Re: [PATCH] Maintain a validity flag for REG_UNUSED notes [PR112760] (was Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760])

[Jakub Jelinek]

On Mon, Dec 04, 2023 at 05:30:45PM +0000, Richard Sandiford wrote:
> > I don't think it's worth adding the note problem to shrink-wrapping
> > just for the regcprop code.  If we're prepared to take that compile-time
> > hit, we might as well run a proper (fast) DCE.
> 
> Here's a patch that tries to do that.  Boostrapped & regression tested
> on aarch64-linux-gnu.  Also tested on x86_64-linux-gnu for the testcase.
> (I'll run full x86_64-linux-gnu testing overnight.)
> 
> OK to install if that passes?  Not an elegant fix, but it's probably
> too much to hope for one of those.

Isn't this way too conservative though, basically limiting single_set
to ~ 15 out of the ~ 65 RTL passes (sure, it will still DTRT for
non-PARALLEL or just PARALLEL with clobbers/uses)?
Do we know about passes other than postreload which may invalidate
REG_UNUSED notes while not purging them altogether?
Given what postreload does, I bet cse/gcse might too.

If we add a RTL checking verification of the notes, we could know
immediately what other passes invalidate it.

So, couldn't we just set such flag at the end of such passes (or only if
they actually remove any redundant insns and thus potentially invalidate
them, perhaps during doing so)?

And on the x86 side, the question from the PR still stands, why is
vzeroupper pass placed exactly after reload and not postreload which
cleans stuff up after reload.

	Jakub

Re: [PATCH] pro_and_epilogue: Call df_note_add_problem () if SHRINK_WRAPPING_ENABLED [PR112760]

[Andrew Pinski]

On Sat, Dec 2, 2023 at 3:04 AM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> Jakub Jelinek <jakub@redhat.com> writes:
> > Hi!
> >
> > The following testcase ICEs on x86_64-linux since df_note_add_problem ()
> > call has been added to mode switching.
> > The problem is that the pro_and_epilogue pass in
> > prepare_shrink_wrap -> copyprop_hardreg_forward_bb_without_debug_insn
> > uses regcprop.cc infrastructure which relies on accurate REG_DEAD/REG_UNUSED
> > notes.  E.g. regcprop.cc
> >   /* We need accurate notes.  Earlier passes such as if-conversion may
> >      leave notes in an inconsistent state.  */
> >   df_note_add_problem ();
> > documents that.  On the testcase below it is in particular the
> >       /* Detect obviously dead sets (via REG_UNUSED notes) and remove them.  */
> >       if (set
> >           && !RTX_FRAME_RELATED_P (insn)
> >           && NONJUMP_INSN_P (insn)
> >           && !may_trap_p (set)
> >           && find_reg_note (insn, REG_UNUSED, SET_DEST (set))
> >           && !side_effects_p (SET_SRC (set))
> >           && !side_effects_p (SET_DEST (set)))
> >         {
> >           bool last = insn == BB_END (bb);
> >           delete_insn (insn);
> >           if (last)
> >             break;
> >           continue;
> >         }
> > case where a stale REG_UNUSED note breaks stuff up (added in vzeroupper
> > pass, redundant insn after it deleted later).
> >
> > The following patch makes sure the notes are not stale if shrink wrapping
> > is enabled.
> >
> > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> I still maintain that so much stuff relies on the lack of false-positive
> REG_UNUSED notes that (whatever the intention might have been) we need
> to prevent the false positive.  Like Andrew says, any use of single_set
> is suspect if there's a REG_UNUSED note for something that is in fact used.
>
> So sorry to be awkward, but I don't think this is the way to go.  I think
> we'll just end up playing whack-a-mole and adding df_note_add_problem to
> lots of passes.
>
> (FTR, I'm not saying passes have to avoid false negatives, just false
> positives.  If a pass updates an instruction with a REG_UNUSED note,
> and the pass is no longer sure whether the register is unused or not,
> the pass can just delete the note.)

Just FYI. This issue with single_use did come up back in 2009 but it
seems like it was glossed over until now.
See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=40209#c5 and the
other comments in that bug report where the patch which fixed the ICE
was just about doing the add of df_note_add_problem .
We definitely need to figure out what should be done here for
single_use; split off the use of REG_UNUSED from single_use and use
df_single_use for that like what was mentioned there. Or just add
df_note_add_problem in other places or fix postreload not to the wrong
thing (but there are definitely other passes like mentioned in that
bug report that does not update REG_UNUSED, e.g. gcse).

Thanks,
Andrew


>
> Richard
>
> > 2023-12-02  Jakub Jelinek  <jakub@redhat.com>
> >
> >       PR rtl-optimization/112760
> >       * function.cc (thread_prologue_and_epilogue_insns): If
> >       SHRINK_WRAPPING_ENABLED, call df_note_add_problem before calling
> >       df_analyze.
> >
> >       * gcc.dg/pr112760.c: New test.
> >
> > --- gcc/function.cc.jj        2023-11-07 08:32:01.699254744 +0100
> > +++ gcc/function.cc   2023-12-01 13:42:51.885189341 +0100
> > @@ -6036,6 +6036,11 @@ make_epilogue_seq (void)
> >  void
> >  thread_prologue_and_epilogue_insns (void)
> >  {
> > +  /* prepare_shrink_wrap uses copyprop_hardreg_forward_bb_without_debug_insn
> > +     which uses regcprop.cc functions which rely on accurate REG_UNUSED
> > +     and REG_DEAD notes.  */
> > +  if (SHRINK_WRAPPING_ENABLED)
> > +    df_note_add_problem ();
> >    df_analyze ();
> >
> >    /* Can't deal with multiple successors of the entry block at the
> > --- gcc/testsuite/gcc.dg/pr112760.c.jj        2023-12-01 13:46:57.444746529 +0100
> > +++ gcc/testsuite/gcc.dg/pr112760.c   2023-12-01 13:46:36.729036971 +0100
> > @@ -0,0 +1,22 @@
> > +/* PR rtl-optimization/112760 */
> > +/* { dg-do run } */
> > +/* { dg-options "-O2 -fno-dce -fno-guess-branch-probability --param=max-cse-insns=0" } */
> > +/* { dg-additional-options "-m8bit-idiv -mavx" { target i?86-*-* x86_64-*-* } } */
> > +
> > +unsigned g;
> > +
> > +__attribute__((__noipa__)) unsigned short
> > +foo (unsigned short a, unsigned short b)
> > +{
> > +  unsigned short x = __builtin_add_overflow_p (a, g, (unsigned short) 0);
> > +  g -= g / b;
> > +  return x;
> > +}
> > +
> > +int
> > +main ()
> > +{
> > +  unsigned short x = foo (40, 6);
> > +  if (x != 0)
> > +    __builtin_abort ();
> > +}
> >
> >       Jakub