[Bug tree-optimization/105030] New: store motion if-change flag causes if-conversion optimization can't be taken.

[Bug tree-optimization/105030] New: store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

            Bug ID: 105030
           Summary: store motion if-change flag causes if-conversion
                    optimization can't be taken.
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: guihaoc at gcc dot gnu.org
  Target Milestone: ---

// source code
extern void bar (double *, int);

void foo (double a[], int n)
{
  double atemp = 0.5;
  for (int i = 0; i < n; i++)
    if (a[i] < atemp)
      atemp = a[i];
  bar (&atemp, n);
}

// -O3 -fdump-tree-lim2
  if (_4 < atemp.0_5)
    goto <bb 4>; [50.00%]
  else
    goto <bb 5>; [50.00%]

  <bb 4> [local count: 477815112]:
  atemp_lsm.4_24 = _4;
  atemp_lsm_flag.5_25 = 1;

It creates the lsm flag in lim2 pass. So the "then" block has two sets which
blocks the if-conversion optimization.

//assemble -O3 -ffast-math -fno-unroll-loops on ppc64le
.L5:
        lfd 0,0(3)
        addi 3,3,8
        fcmpu 0,12,0
        ble 0,.L3
        fmr 12,0
        li 9,1
.L3:
        bdnz .L5
        andi. 9,9,0x1
        beq 0,.L2
        stfd 12,32(1)

Inefficient fcmpu is used. If the source code is tweaked as below, the
efficient xvmindp is generated.

// tweaked source code
extern void bar (double *, int);

void foo (double a[], int n)
{
  double atemp = 0.5;
  for (int i = 0; i < n; i++)
    if (a[i] < atemp)
      atemp = a[i];
  double btemp = atemp;
  bar (&btemp, n);
}

//assembly
.L4:
        lxv 0,0(9)
        addi 9,9,16
        xvmindp 12,12,0
        bdnz .L4

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

HaoChen Gui <guihaoc at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
               Host|                            |powerpc-*-linux-gnu

--- Comment #1 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
   bool always_stored = ref_always_accessed_p (loop, ref, true);
   if (maybe_mt
       && (bb_in_transaction (loop_preheader_edge (loop)->src)
           || (! flag_store_data_races && ! always_stored)))
     multi_threaded_model_p = true;

Could we consider multi_threaded_model_p here is false for a local auto
variable?

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
That occured to me as well - I think the answer is maybe.  In principle
foo() could launch a thread and make the 'atemp' available to it.  As long
as foo() outlives thread termination that should be all well-defined and so
we'd have to take this possibility into account.

There's currently no code ruling this out and doing that is likely difficult.
So maybe the answer is to add -fallow-store-data-races={local,all}, map
-fallow-store-data-races to -fallow-store-data-races=all and make
-fallow-store-data-races=local the default?

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

--- Comment #3 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #2)
> That occured to me as well - I think the answer is maybe.  In principle
> foo() could launch a thread and make the 'atemp' available to it.  As long
> as foo() outlives thread termination that should be all well-defined and so
> we'd have to take this possibility into account.
> 
> There's currently no code ruling this out and doing that is likely difficult.
> So maybe the answer is to add -fallow-store-data-races={local,all}, map
> -fallow-store-data-races to -fallow-store-data-races=all and make
> -fallow-store-data-races=local the default?

For the local automatic variables(not global, not static), they should be
stored on one's own thread stack. I think they can't be accessed by other
threads. Other threads should create their own instance for the local automatic
variables. So 'atemp' is thread safe in the example code? Could you please
explain why it's unsafe when foo outlives thread termination? Thanks a lot.

diff --git a/gcc/tree-ssa-loop-im.cc b/gcc/tree-ssa-loop-im.cc
index 6d9316eed1f..e2b6b927351 100644
--- a/gcc/tree-ssa-loop-im.cc
+++ b/gcc/tree-ssa-loop-im.cc
@@ -2219,7 +2219,10 @@ execute_sm (class loop *loop, im_mem_ref *ref,
   bool always_stored = ref_always_accessed_p (loop, ref, true);
   if (maybe_mt
       && (bb_in_transaction (loop_preheader_edge (loop)->src)
-         || (! flag_store_data_races && ! always_stored)))
+         || (! flag_store_data_races && ! always_stored
+             && (!auto_var_in_fn_p (ref->mem.ref, current_function_decl)
+                 || TREE_THIS_VOLATILE (ref->mem.ref)
+                 || TREE_STATIC (ref->mem.ref)))))
     multi_threaded_model_p = true;

Could we use above conditions to exclude local auto variables from
multi-threaded safe considerations?

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
something like

void *bar (void *x)
{
  *(double *)x = 1.;
}

void foo(int n)
{
   double atemp;
   pthread_create (..., bar, &atemp);
   for (int i = 0; i < n; i++)
     if (a[i] < atemp)
       atemp = a[i];
   pthread_join (...);
   if (atemp != 1.)
     abort ();
}

if it is ensured the store to atemp in the loop never takes place then
we have created a store data race when applying store motion.  Of course
thread creation/join can be hidden in other functions called from foo()
as long as 'atemp' escapes to callers.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

--- Comment #5 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> something like
> 
> void *bar (void *x)
> {
>   *(double *)x = 1.;
> }
> 
> void foo(int n)
> {
>    double atemp;
>    pthread_create (..., bar, &atemp);
>    for (int i = 0; i < n; i++)
>      if (a[i] < atemp)
>        atemp = a[i];
>    pthread_join (...);
>    if (atemp != 1.)
>      abort ();
> }
> 
> if it is ensured the store to atemp in the loop never takes place then
> we have created a store data race when applying store motion.  Of course
> thread creation/join can be hidden in other functions called from foo()
> as long as 'atemp' escapes to callers.

I got it. Thanks a lot.
In the original case, the bar is called after the loop. So we still think the
atemp is safe for multi-threaded, as atemp can't be changed by others threads?
If the bar is executed before the loop, it's unsafe. Could we check all blocks
dominated by the loop head to find out the reference used in a call?

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenther at suse dot de]

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

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 25 Mar 2022, guihaoc at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105030
> 
> --- Comment #5 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #4)
> > something like
> > 
> > void *bar (void *x)
> > {
> >   *(double *)x = 1.;
> > }
> > 
> > void foo(int n)
> > {
> >    double atemp;
> >    pthread_create (..., bar, &atemp);
> >    for (int i = 0; i < n; i++)
> >      if (a[i] < atemp)
> >        atemp = a[i];
> >    pthread_join (...);
> >    if (atemp != 1.)
> >      abort ();
> > }
> > 
> > if it is ensured the store to atemp in the loop never takes place then
> > we have created a store data race when applying store motion.  Of course
> > thread creation/join can be hidden in other functions called from foo()
> > as long as 'atemp' escapes to callers.
> 
> I got it. Thanks a lot.
> In the original case, the bar is called after the loop. So we still think the
> atemp is safe for multi-threaded, as atemp can't be changed by others threads?
>
> If the bar is executed before the loop, it's unsafe. Could we check all blocks
> dominated by the loop head to find out the reference used in a call?

Yes, we could look at whether there's an escape point of 'atemp' between
function entry and the loop.  Similarly there would have to be a
possible pthread_join _after_ the loop (even if there's an escape point
before the loop).

Not sure if it's worth the trouble though - do you have a compelling
real-world example where it would help?

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

--- Comment #7 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
The original case comes from a Fortran program. I rewrote it with C. As the
arguments are passed by reference in Fortran (by default), the problem is
common. But I am not sure if it has a large performance impact.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenther at suse dot de]

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

--- Comment #8 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 25 Mar 2022, guihaoc at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105030
> 
> --- Comment #7 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
> The original case comes from a Fortran program. I rewrote it with C. As the
> arguments are passed by reference in Fortran (by default), the problem is
> common. But I am not sure if it has a large performance impact.

For the fortran case it probably helps to instead check the
points-to escaped solution, so

  auto_var_in_fn_p (var, cfun)
  && !pt_solution_includes (&cfun->gimple_df->escaped, var)

since the fortran frontend marks by reference passed as not escaping
(unless they are POINTER or so, don't remember exactly).  Note
this isn't flow-sensitive so it doesn't help the C example you gave
where the variable would be in the functions escaped set.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

--- Comment #9 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
Escaped for 'atemp' doesn't be set with Fortran source code, while it's set
with C source code. 'auto_var_in_fn_p + pt_solution_includes' works for Fortran
code. But if the function is a head of the loop in Fortran, it's still unsafe
for multithreaded.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenther at suse dot de]

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

--- Comment #10 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 28 Mar 2022, guihaoc at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105030
> 
> --- Comment #9 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
> Escaped for 'atemp' doesn't be set with Fortran source code, while it's set
> with C source code. 'auto_var_in_fn_p + pt_solution_includes' works for Fortran
> code. But if the function is a head of the loop in Fortran, it's still unsafe
> for multithreaded.

The fortran standard requires you to annotate the parameter with
POINTER to make it escaped (or to make it threaded).  But still
the only way for a thread (but not a coroutine for example!)
to access stack from another thread is to make a pointer to an
object on the stack escape to it.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

--- Comment #11 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
I tested C source code with Ofast. The Ofast enables data store race. It should
do store motion but it fails. The problem is on cselim pass. It does
conditional store replacement. The 'atemp' is converted to its alias set - 'MEM
<double> [(void *)&atemp]' in the if-else blocks and remains untouch out of the
if-else.

   atemp.0_5 = atemp;
  if (_4 < atemp.0_5)
    goto <bb 5>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 4> [local count: 477815113]:
  cstore_18 = MEM <double> [(void *)&atemp];

  <bb 5> [local count: 955630225]:
  # cstore_17 = PHI <cstore_18(4), _4(3)>
  MEM <double> [(void *)&atemp] = cstore_17;

Then in lim2 pass, it thinks 'atemp' and 'MEM <double> [(void *)&atemp]' are
independent. So the store can't be moved out.

Memory reference 1: *_3
Memory reference 2: atemp
Memory reference 3: MEM <double> [(void *)&atemp]
Querying dependency of refs 3 and 1: independent.
Querying dependency of refs 3 and 2: dependent.
Querying SM WAR dependencies of ref 3 in loop 1: dependent

I wonder if 'atemp' is equivalent to 'MEM <double> [(void *)&atemp]'. Why we
shall use alias-set zero in cselim pass.

 /* Make both store and load use alias-set zero as we have to
     deal with the case of the store being a conditional change
     of the dynamic type.  */

  while (handled_component_p (*basep))
    basep = &TREE_OPERAND (*basep, 0);
  if (TREE_CODE (*basep) == MEM_REF
      || TREE_CODE (*basep) == TARGET_MEM_REF)
    TREE_OPERAND (*basep, 1)
      = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
  else
    *basep = build2 (MEM_REF, TREE_TYPE (*basep),
                     build_fold_addr_expr (*basep),
                     build_zero_cst (ptr_type_node));

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to HaoChen Gui from comment #11)
> I tested C source code with Ofast. The Ofast enables data store race. It
> should do store motion but it fails. The problem is on cselim pass. It does
> conditional store replacement. The 'atemp' is converted to its alias set -
> 'MEM <double> [(void *)&atemp]' in the if-else blocks and remains untouch
> out of the if-else.
> 
>    atemp.0_5 = atemp;
>   if (_4 < atemp.0_5)
>     goto <bb 5>; [50.00%]
>   else
>     goto <bb 4>; [50.00%]
> 
>   <bb 4> [local count: 477815113]:
>   cstore_18 = MEM <double> [(void *)&atemp];
> 
>   <bb 5> [local count: 955630225]:
>   # cstore_17 = PHI <cstore_18(4), _4(3)>
>   MEM <double> [(void *)&atemp] = cstore_17;
> 
> Then in lim2 pass, it thinks 'atemp' and 'MEM <double> [(void *)&atemp]' are
> independent. So the store can't be moved out.
> 
> Memory reference 1: *_3
> Memory reference 2: atemp
> Memory reference 3: MEM <double> [(void *)&atemp]
> Querying dependency of refs 3 and 1: independent.
> Querying dependency of refs 3 and 2: dependent.
> Querying SM WAR dependencies of ref 3 in loop 1: dependent
> 
> I wonder if 'atemp' is equivalent to 'MEM <double> [(void *)&atemp]'. Why we
> shall use alias-set zero in cselim pass.
> 
>  /* Make both store and load use alias-set zero as we have to
>      deal with the case of the store being a conditional change
>      of the dynamic type.  */
> 
>   while (handled_component_p (*basep))
>     basep = &TREE_OPERAND (*basep, 0);
>   if (TREE_CODE (*basep) == MEM_REF
>       || TREE_CODE (*basep) == TARGET_MEM_REF)
>     TREE_OPERAND (*basep, 1)
>       = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
>   else
>     *basep = build2 (MEM_REF, TREE_TYPE (*basep),
>                      build_fold_addr_expr (*basep),
>                      build_zero_cst (ptr_type_node));

This is to deal with a more generic case.  In this particular case there's
a load from atemp always executed when executing the conditional and
we could devise some condition under which using the original alias set
of the conditional store unconditional is correct (but it's not going to be
trivial).

Store motion is (unfortunately) tied to "exactly" matching load/store
pairs:

Memory reference 1: *_3
Memory reference 2: atemp(address-taken)
Memory reference 3: MEM <double> [(void *)&atemp(address-taken)]

here we have reference 2 and 3 so that will inevitably fail.  We already do
some "unification" but do not try to merge TBAA info there.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[guihaoc at gcc dot gnu.org]

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

--- Comment #13 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
Could we use the original alias set if the tree code of 'atemp' is var_decl? Is
it safe? In which situation we shall use alias-set zero? Thanks.

[Bug tree-optimization/105030] store motion if-change flag causes if-conversion optimization can't be taken.

[rguenther at suse dot de]

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

--- Comment #14 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 8 Apr 2022, guihaoc at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105030
> 
> --- Comment #13 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
> Could we use the original alias set if the tree code of 'atemp' is var_decl? Is
> it safe? In which situation we shall use alias-set zero? Thanks.

No, just being a VAR_DECL is not good enough.  Basically you have to
somehow have knowledge about the dynamic type of the object we store
to before the store and see whether the conditional store might
change that.  If so the store needs to use a type that allows accesses
to both the original and the possibly changed dynamic type from
existing accesses following the now unconditional store.

When the access is to a VAR_DECL we can look for the case where
the access is to the full variable (partial stores are always difficult
to judge wrt dynamic type changes) and whether there is a dominating
load (also to the full variable) that either uses the same type
or allows us to find a common type to use.