[PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Richard Biener]

The following makes the backward threader reject threads whose entry
edge is probably never executed according to the profile.  That in
particular, for the testcase, avoids threading the irq == 1 check
on the path where irq > 31, thereby avoiding spurious -Warray-bounds
diagnostics

  if (irq_1(D) > 31)
    goto <bb 3>; [0.00%]
  else
    goto <bb 4>; [100.00%]

;;   basic block 3, loop depth 0, count 0 (precise), probably never executed
  _2 = (unsigned long) irq_1(D);
  __builtin___ubsan_handle_shift_out_of_bounds (&*.Lubsan_data0, 1, _2);

  _3 = 1 << irq_1(D);
  mask_4 = (u32) _3;
  entry = instance_5(D)->array[irq_1(D)];
  capture (mask_4);
  if (level_6(D) != 0)
    goto <bb 7>; [34.00%]
  else
    goto <bb 5>; [66.00%]

;;   basic block 5, loop depth 0, count 708669600 (estimated locally), maybe hot  if (irq_1(D) == 1)
    goto <bb 7>; [20.97%]
  else
    goto <bb 6>; [79.03%]

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

The testcase in the PR requries both ubsan and sancov so I'm not sure
where to put it but IIRC there were quite some duplicate PRs wrt
threading unlikely paths exposing diagnostics, eventually some
testcase will come out of those (when we identify them).  Note
the patch is quite conservative in only disabling likely never
executed paths rather than requiring maybe_hot_edge_p (OTOH those
are somewhat similar in the end).

I'm going to push it when testing finishes but maybe there are some
testcases to adjust.

	PR tree-optimization/105679
	* tree-ssa-threadbackwards.cc
	(back_threader_profitability::profitable_path_p): Avoid threading
	when the entry edge is probably never executed.
---
 gcc/tree-ssa-threadbackward.cc | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 3519aca84cd..90f5331c265 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -777,6 +777,15 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
 		     "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
 	  return false;
 	}
+      edge entry = find_edge (m_path[m_path.length () - 1],
+			      m_path[m_path.length () - 2]);
+      if (probably_never_executed_edge_p (cfun, entry))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
+		     "path entry is probably never executed.\n");
+	  return false;
+	}
     }
   else if (!m_speed_p && n_insns > 1)
     {
-- 
2.35.3

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Aldy Hernandez]

On Fri, Jul 29, 2022 at 11:02 AM Richard Biener <rguenther@suse.de> wrote:
>
> The following makes the backward threader reject threads whose entry
> edge is probably never executed according to the profile.  That in
> particular, for the testcase, avoids threading the irq == 1 check
> on the path where irq > 31, thereby avoiding spurious -Warray-bounds
> diagnostics
>
>   if (irq_1(D) > 31)
>     goto <bb 3>; [0.00%]
>   else
>     goto <bb 4>; [100.00%]
>
> ;;   basic block 3, loop depth 0, count 0 (precise), probably never executed
>   _2 = (unsigned long) irq_1(D);
>   __builtin___ubsan_handle_shift_out_of_bounds (&*.Lubsan_data0, 1, _2);
>
>   _3 = 1 << irq_1(D);
>   mask_4 = (u32) _3;
>   entry = instance_5(D)->array[irq_1(D)];
>   capture (mask_4);
>   if (level_6(D) != 0)
>     goto <bb 7>; [34.00%]
>   else
>     goto <bb 5>; [66.00%]
>
> ;;   basic block 5, loop depth 0, count 708669600 (estimated locally), maybe hot  if (irq_1(D) == 1)
>     goto <bb 7>; [20.97%]
>   else
>     goto <bb 6>; [79.03%]
>
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
>
> The testcase in the PR requries both ubsan and sancov so I'm not sure
> where to put it but IIRC there were quite some duplicate PRs wrt
> threading unlikely paths exposing diagnostics, eventually some
> testcase will come out of those (when we identify them).  Note
> the patch is quite conservative in only disabling likely never
> executed paths rather than requiring maybe_hot_edge_p (OTOH those
> are somewhat similar in the end).

Sounds reasonable, if for no other reason than to quiet down the
annoyingly large amount of false positives we have because of
aggressive threading, or better ranges as a whole.

How does this fit in with Jeff's original idea of isolating known
problematic paths (null dereferences?), which in theory are also
unlikely?

Thanks for doing this.
Aldy

>
> I'm going to push it when testing finishes but maybe there are some
> testcases to adjust.
>
>         PR tree-optimization/105679
>         * tree-ssa-threadbackwards.cc
>         (back_threader_profitability::profitable_path_p): Avoid threading
>         when the entry edge is probably never executed.
> ---
>  gcc/tree-ssa-threadbackward.cc | 9 +++++++++
>  1 file changed, 9 insertions(+)
>
> diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> index 3519aca84cd..90f5331c265 100644
> --- a/gcc/tree-ssa-threadbackward.cc
> +++ b/gcc/tree-ssa-threadbackward.cc
> @@ -777,6 +777,15 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
>                      "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
>           return false;
>         }
> +      edge entry = find_edge (m_path[m_path.length () - 1],
> +                             m_path[m_path.length () - 2]);
> +      if (probably_never_executed_edge_p (cfun, entry))
> +       {
> +         if (dump_file && (dump_flags & TDF_DETAILS))
> +           fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
> +                    "path entry is probably never executed.\n");
> +         return false;
> +       }
>      }
>    else if (!m_speed_p && n_insns > 1)
>      {
> --
> 2.35.3
>

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Richard Biener]

On Fri, 29 Jul 2022, Aldy Hernandez wrote:

> On Fri, Jul 29, 2022 at 11:02 AM Richard Biener <rguenther@suse.de> wrote:
> >
> > The following makes the backward threader reject threads whose entry
> > edge is probably never executed according to the profile.  That in
> > particular, for the testcase, avoids threading the irq == 1 check
> > on the path where irq > 31, thereby avoiding spurious -Warray-bounds
> > diagnostics
> >
> >   if (irq_1(D) > 31)
> >     goto <bb 3>; [0.00%]
> >   else
> >     goto <bb 4>; [100.00%]
> >
> > ;;   basic block 3, loop depth 0, count 0 (precise), probably never executed
> >   _2 = (unsigned long) irq_1(D);
> >   __builtin___ubsan_handle_shift_out_of_bounds (&*.Lubsan_data0, 1, _2);
> >
> >   _3 = 1 << irq_1(D);
> >   mask_4 = (u32) _3;
> >   entry = instance_5(D)->array[irq_1(D)];
> >   capture (mask_4);
> >   if (level_6(D) != 0)
> >     goto <bb 7>; [34.00%]
> >   else
> >     goto <bb 5>; [66.00%]
> >
> > ;;   basic block 5, loop depth 0, count 708669600 (estimated locally), maybe hot  if (irq_1(D) == 1)
> >     goto <bb 7>; [20.97%]
> >   else
> >     goto <bb 6>; [79.03%]
> >
> > Bootstrap and regtest running on x86_64-unknown-linux-gnu.
> >
> > The testcase in the PR requries both ubsan and sancov so I'm not sure
> > where to put it but IIRC there were quite some duplicate PRs wrt
> > threading unlikely paths exposing diagnostics, eventually some
> > testcase will come out of those (when we identify them).  Note
> > the patch is quite conservative in only disabling likely never
> > executed paths rather than requiring maybe_hot_edge_p (OTOH those
> > are somewhat similar in the end).
> 
> Sounds reasonable, if for no other reason than to quiet down the
> annoyingly large amount of false positives we have because of
> aggressive threading, or better ranges as a whole.
> 
> How does this fit in with Jeff's original idea of isolating known
> problematic paths (null dereferences?), which in theory are also
> unlikely?

If profile estimation gets to see those the paths should turn unlikely.
Path isolation should also make sure to adjust the profile accordingly,
though local profile adjustments are somewhat difficult.

Richard.

> Thanks for doing this.
> Aldy
> 
> >
> > I'm going to push it when testing finishes but maybe there are some
> > testcases to adjust.
> >
> >         PR tree-optimization/105679
> >         * tree-ssa-threadbackwards.cc
> >         (back_threader_profitability::profitable_path_p): Avoid threading
> >         when the entry edge is probably never executed.
> > ---
> >  gcc/tree-ssa-threadbackward.cc | 9 +++++++++
> >  1 file changed, 9 insertions(+)
> >
> > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> > index 3519aca84cd..90f5331c265 100644
> > --- a/gcc/tree-ssa-threadbackward.cc
> > +++ b/gcc/tree-ssa-threadbackward.cc
> > @@ -777,6 +777,15 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
> >                      "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
> >           return false;
> >         }
> > +      edge entry = find_edge (m_path[m_path.length () - 1],
> > +                             m_path[m_path.length () - 2]);
> > +      if (probably_never_executed_edge_p (cfun, entry))
> > +       {
> > +         if (dump_file && (dump_flags & TDF_DETAILS))
> > +           fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
> > +                    "path entry is probably never executed.\n");
> > +         return false;
> > +       }
> >      }
> >    else if (!m_speed_p && n_insns > 1)
> >      {
> > --
> > 2.35.3
> >
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Jeff Law]

On 7/29/2022 2:54 AM, Richard Biener via Gcc-patches wrote:
> The following makes the backward threader reject threads whose entry
> edge is probably never executed according to the profile.  That in
> particular, for the testcase, avoids threading the irq == 1 check
> on the path where irq > 31, thereby avoiding spurious -Warray-bounds
> diagnostics
>
>    if (irq_1(D) > 31)
>      goto <bb 3>; [0.00%]
>    else
>      goto <bb 4>; [100.00%]
>
> ;;   basic block 3, loop depth 0, count 0 (precise), probably never executed
>    _2 = (unsigned long) irq_1(D);
>    __builtin___ubsan_handle_shift_out_of_bounds (&*.Lubsan_data0, 1, _2);
>
>    _3 = 1 << irq_1(D);
>    mask_4 = (u32) _3;
>    entry = instance_5(D)->array[irq_1(D)];
>    capture (mask_4);
>    if (level_6(D) != 0)
>      goto <bb 7>; [34.00%]
>    else
>      goto <bb 5>; [66.00%]
>
> ;;   basic block 5, loop depth 0, count 708669600 (estimated locally), maybe hot  if (irq_1(D) == 1)
>      goto <bb 7>; [20.97%]
>    else
>      goto <bb 6>; [79.03%]
>
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
>
> The testcase in the PR requries both ubsan and sancov so I'm not sure
> where to put it but IIRC there were quite some duplicate PRs wrt
> threading unlikely paths exposing diagnostics, eventually some
> testcase will come out of those (when we identify them).  Note
> the patch is quite conservative in only disabling likely never
> executed paths rather than requiring maybe_hot_edge_p (OTOH those
> are somewhat similar in the end).
>
> I'm going to push it when testing finishes but maybe there are some
> testcases to adjust.
>
> 	PR tree-optimization/105679
> 	* tree-ssa-threadbackwards.cc
> 	(back_threader_profitability::profitable_path_p): Avoid threading
> 	when the entry edge is probably never executed.
OK.   And more generally I'm absolutely OK with improving the costing 
heuristics.

The one thing we need to keep in mind when adding this kind of check is 
that we may start seeing new diagnostics from the middle end -- while 
the path may not be profitable to thread from a performance standpoint, 
it may be useful to thread from a diagnostic standpoint.

But I'd argue that for such cases we really want to move to a model 
where the predicate analysis bits are used consistently to prune away 
"can't happen" cases for middle end diagnostics rather than relying on 
threading to optimize away can't happen cold paths.

Jeff

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Iain Sandoe]

Hi Richi,

> On 29 Jul 2022, at 09:54, Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> 
> The following makes the backward threader reject threads whose entry
> edge is probably never executed according to the profile.  That in
> particular, for the testcase, avoids threading the irq == 1 check
> on the path where irq > 31, thereby avoiding spurious -Warray-bounds
> diagnostics

This breaks bootstrap on i686-darwin{9,17} with what looks like a valid  warning (werrors on stage2)

cc1plus  … -O2 -Wall … is enough to.

I can repeat it on a cross from x86_64-darwin19, so I can probably reduce the .ii (it’s like 2M5 raw) and file a PR if you like - depends if the solution might be obvious to you …

thanks
Iain

--------

In file included from /src-local/gcc-master/gcc/hash-table.h:248,
                 from /src-local/gcc-master/gcc/coretypes.h:486,
                 from /src-local/gcc-master/gcc/tree-ssa-threadbackward.cc:22:
In member function ‘T& vec<T, A, vl_embed>::operator[](unsigned int) [with T = basic_block_def*; A = va_heap]’,
    inlined from ‘const T& vec<T>::operator[](unsigned int) const [with T = basic_block_def*]’ at /src-local/gcc-master/gcc/vec.h:1486:20,
    inlined from ‘bool back_threader_profitability::profitable_path_p(const vec<basic_block_def*>&, tree, edge, bool*)’ at /src-local/gcc-master/gcc/tree-ssa-threadbackward.cc:781:37:
/src-local/gcc-master/gcc/vec.h:890:19: warning: array subscript 4294967294 is above array bounds of ‘basic_block_def* [1]’ [-Warray-bounds]
  890 |   return m_vecdata[ix];
      |          ~~~~~~~~~^
/src-local/gcc-master/gcc/vec.h: In member function ‘bool back_threader_profitability::profitable_path_p(const vec<basic_block_def*>&, tree, edge, bool*)’:
/src-local/gcc-master/gcc/vec.h:635:5: note: while referencing ‘vec<basic_block_def*, va_heap, vl_embed>::m_vecdata’
  635 |   T m_vecdata[1];
      |     ^~~~~~~~~

=====

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Jeff Law]

On 7/31/2022 1:17 PM, Iain Sandoe via Gcc-patches wrote:
> Hi Richi,
>
>> On 29 Jul 2022, at 09:54, Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>>
>> The following makes the backward threader reject threads whose entry
>> edge is probably never executed according to the profile.  That in
>> particular, for the testcase, avoids threading the irq == 1 check
>> on the path where irq > 31, thereby avoiding spurious -Warray-bounds
>> diagnostics
> This breaks bootstrap on i686-darwin{9,17} with what looks like a valid  warning (werrors on stage2)
>
> cc1plus  … -O2 -Wall … is enough to.
>
> I can repeat it on a cross from x86_64-darwin19, so I can probably reduce the .ii (it’s like 2M5 raw) and file a PR if you like - depends if the solution might be obvious to you …
I suspect what's happening here is by suppressing the jump thread we're 
leaving an unexecutable path through the CFG in the IL.   The warning is 
likely on that unexecutable path or at a join point where the 
unexecutable path re-joins the main path through the CFG.

Jeff

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Richard Biener]

On Sun, 31 Jul 2022, Iain Sandoe wrote:

> Hi Richi,
> 
> > On 29 Jul 2022, at 09:54, Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> > 
> > The following makes the backward threader reject threads whose entry
> > edge is probably never executed according to the profile.  That in
> > particular, for the testcase, avoids threading the irq == 1 check
> > on the path where irq > 31, thereby avoiding spurious -Warray-bounds
> > diagnostics
> 
> This breaks bootstrap on i686-darwin{9,17} with what looks like a valid  warning (werrors on stage2)
> 
> cc1plus  … -O2 -Wall … is enough to.
> 
> I can repeat it on a cross from x86_64-darwin19, so I can probably reduce the .ii (it’s like 2M5 raw) and file a PR if you like - depends if the solution might be obvious to you …

Can you open a bugreport and attach full preprocessed source at start?

Note at the start of the function we have

  if (m_path.length () <= 1)
      return false;

so

      edge entry = find_edge (m_path[m_path.length () - 1],
                              m_path[m_path.length () - 2]);

is known to not access m_path out-of-bounds ...

Thanks,
Richard.

> 
> thanks
> Iain
> 
> --------
> 
> In file included from /src-local/gcc-master/gcc/hash-table.h:248,
>                  from /src-local/gcc-master/gcc/coretypes.h:486,
>                  from /src-local/gcc-master/gcc/tree-ssa-threadbackward.cc:22:
> In member function ‘T& vec<T, A, vl_embed>::operator[](unsigned int) [with T = basic_block_def*; A = va_heap]’,
>     inlined from ‘const T& vec<T>::operator[](unsigned int) const [with T = basic_block_def*]’ at /src-local/gcc-master/gcc/vec.h:1486:20,
>     inlined from ‘bool back_threader_profitability::profitable_path_p(const vec<basic_block_def*>&, tree, edge, bool*)’ at /src-local/gcc-master/gcc/tree-ssa-threadbackward.cc:781:37:
> /src-local/gcc-master/gcc/vec.h:890:19: warning: array subscript 4294967294 is above array bounds of ‘basic_block_def* [1]’ [-Warray-bounds]
>   890 |   return m_vecdata[ix];
>       |          ~~~~~~~~~^
> /src-local/gcc-master/gcc/vec.h: In member function ‘bool back_threader_profitability::profitable_path_p(const vec<basic_block_def*>&, tree, edge, bool*)’:
> /src-local/gcc-master/gcc/vec.h:635:5: note: while referencing ‘vec<basic_block_def*, va_heap, vl_embed>::m_vecdata’
>   635 |   T m_vecdata[1];
>       |     ^~~~~~~~~
> 
> =====

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)

Re: [PATCH] tree-optimization/105679 - disable backward threading of unlikely entry

[Iain Sandoe]

> On 1 Aug 2022, at 09:21, Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> 
> On Sun, 31 Jul 2022, Iain Sandoe wrote:
> 
>> Hi Richi,
>> 
>>> On 29 Jul 2022, at 09:54, Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>>> 
>>> The following makes the backward threader reject threads whose entry
>>> edge is probably never executed according to the profile.  That in
>>> particular, for the testcase, avoids threading the irq == 1 check
>>> on the path where irq > 31, thereby avoiding spurious -Warray-bounds
>>> diagnostics
>> 
>> This breaks bootstrap on i686-darwin{9,17} with what looks like a valid  warning (werrors on stage2)
>> 
>> cc1plus  … -O2 -Wall … is enough to.
>> 
>> I can repeat it on a cross from x86_64-darwin19, so I can probably reduce the .ii (it’s like 2M5 raw) and file a PR if you like - depends if the solution might be obvious to you …
> 
> Can you open a bugreport and attach full preprocessed source at start?

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

> Note at the start of the function we have
> 
>  if (m_path.length () <= 1)
>      return false;
> 
> so
> 
>      edge entry = find_edge (m_path[m_path.length () - 1],
>                              m_path[m_path.length () - 2]);
> 
> is known to not access m_path out-of-bounds ...

yes, I saw that .. so I guess somehow that information is getting dropped.
thanks
Iain

> 
> Thanks,
> Richard.
> 
>> 
>> thanks
>> Iain
>> 
>> --------
>> 
>> In file included from /src-local/gcc-master/gcc/hash-table.h:248,
>>                 from /src-local/gcc-master/gcc/coretypes.h:486,
>>                 from /src-local/gcc-master/gcc/tree-ssa-threadbackward.cc:22:
>> In member function ‘T& vec<T, A, vl_embed>::operator[](unsigned int) [with T = basic_block_def*; A = va_heap]’,
>>    inlined from ‘const T& vec<T>::operator[](unsigned int) const [with T = basic_block_def*]’ at /src-local/gcc-master/gcc/vec.h:1486:20,
>>    inlined from ‘bool back_threader_profitability::profitable_path_p(const vec<basic_block_def*>&, tree, edge, bool*)’ at /src-local/gcc-master/gcc/tree-ssa-threadbackward.cc:781:37:
>> /src-local/gcc-master/gcc/vec.h:890:19: warning: array subscript 4294967294 is above array bounds of ‘basic_block_def* [1]’ [-Warray-bounds]
>>  890 |   return m_vecdata[ix];
>>      |          ~~~~~~~~~^
>> /src-local/gcc-master/gcc/vec.h: In member function ‘bool back_threader_profitability::profitable_path_p(const vec<basic_block_def*>&, tree, edge, bool*)’:
>> /src-local/gcc-master/gcc/vec.h:635:5: note: while referencing ‘vec<basic_block_def*, va_heap, vl_embed>::m_vecdata’
>>  635 |   T m_vecdata[1];
>>      |     ^~~~~~~~~
>> 
>> =====
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
> Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
> HRB 36809 (AG Nuernberg)