On Thu, Sep 9, 2021 at 3:56 AM Xionghu Luo <luo...@linux.ibm.com> wrote:
>
>
>
> On 2021/8/26 19:33, Richard Biener wrote:
> > On Tue, Aug 10, 2021 at 4:03 AM Xionghu Luo <luo...@linux.ibm.com> wrote:
> >>
> >> Hi,
> >>
> >> On 2021/8/6 20:15, Richard Biener wrote:
> >>> On Mon, Aug 2, 2021 at 7:05 AM Xiong Hu Luo <luo...@linux.ibm.com> wrote:
> >>>>
> >>>> There was a patch trying to avoid move cold block out of loop:
> >>>>
> >>>> https://gcc.gnu.org/pipermail/gcc/2014-November/215551.html
> >>>>
> >>>> Richard suggested to "never hoist anything from a bb with lower execution
> >>>> frequency to a bb with higher one in LIM invariantness_dom_walker
> >>>> before_dom_children".
> >>>>
> >>>> This patch does this profile count check in both gimple LIM
> >>>> move_computations_worker and RTL loop-invariant.c find_invariants_bb,
> >>>> if the loop bb is colder than loop preheader, don't hoist it out of
> >>>> loop.
> >>>>
> >>>> Also, the profile count in loop split pass should be corrected to avoid
> >>>> lim2 and lim4 mismatch behavior, currently, the new loop preheader 
> >>>> generated
> >>>> by loop_version is set to "[count: 0]:", then lim4 after lsplt pass will
> >>>> move statement out of loop unexpectely when lim2 didn't move it.  This
> >>>> change could fix regression on 544.nab_r from -1.55% to +0.46%.
> >>>>
> >>>> SPEC2017 performance evaluation shows 1% performance improvement for
> >>>> intrate GEOMEAN and no obvious regression for others.  Especially,
> >>>> 500.perlbench_r +7.52% (Perf shows function S_regtry of perlbench is
> >>>> largely improved.), and 548.exchange2_r+1.98%, 526.blender_r +1.00%
> >>>> on P8LE.
> >>>>
> >>>> Regression and bootstrap tested pass on P8LE, any comments?  Thanks.
> >>>
> >>> While I'm not familiar with the RTL invariant motion pass the patch there
> >>> looks reasonable.  Note that we should assess the profile quality
> >>> somehow - I'm not sure how to do that, CCed Honza for that.
> >>
> >> Thanks.
> >>
> >>>
> >>> For the GIMPLE part the patch looks quite complicated - but note it
> >>> probably has to be since LIM performs kind of a "CSE" on loads
> >>> (and stores for store-motion), so when there are multiple stmts
> >>> affected by a hoisting decision the biggest block count has to be
> >>> accounted.  Likewise when there are dependent stmts involved
> >>> that might include conditional stmts (a "PHI"), but the overall
> >>> cost should be looked at.
> >>
> >> Currently, The gimple code check two situations with the patch:
> >> 1) The statement or PHI‘s BB is *colder* then preheader, don't move it out
> >> of loop;
> >> 2) The statement or PHI's BB is *hotter* then preheader, but any of it's 
> >> rhs
> >> couldn't be moved out of loop, also don't move it out of loop to avoid 
> >> definition
> >> not dominates use error.
> >
> > But part 2) is obviously already done.  What I tried to say is your 
> > heuristic
> > doesn't integrate nicely with the pass but I admitted that it might be a bit
> > difficult to find a place to add this heuristic.
> >
> > There is lim_data->cost which we could bias negatively but then this is
> > a cost that is independent on the hoisting distance.  But doing this would
> > work at least for the case where the immediately enclosing loop preheader
> > is hotter than the stmt and with this it would be a patch that's similarly
> > simple as the RTL one.
> >
> > Another possibility is to simply only adjust PHI processing in
> > compute_invariantness, capping movement according to the hotness
> > heuristic.  The same could be done for regular stmts there but I'm
> > not sure that will do good in the end since this function is supposed
> > to compute "correctness" (well, it also has the cost stuff), and it's
> > not the place to do overall cost considerations.
>
> Thanks.  I found that adding a function find_coldest_out_loop and check it in
> outermost_invariant_loop to find the coldest invariant loop between outermost
> loop and itself could also reach the purpose.  Then the gimple code check is
> redundant and could be removed.
>
> >
> >> May be I could collect the number of instructions not hoisted with the 
> >> patch
> >> on regression tests and SPEC2017 to do a estimation for "multiple stmts 
> >> affected"
> >> and "overall cost" need to be considered?  But it seems 
> >> move_computations_worker
> >> couldn't rollback if we still want to hoist multiple stmts out during the 
> >> iterations?
> >>
> >>>
> >>> Now - GIMPLE LIM "costing" is somewhat backward right now
> >>> and it isn't set up to consider those multiple involved stmts.  Plus
> >>> the store-motion part does not have any cost part (but it depends
> >>> on previously decided invariant motions).
> >>>
> >>> I think the way you implemented the check will cause no hoisting
> >>> to be performed instead of, say, hoisting to a different loop level
> >>> only.  Possibly shown when you consider a loop nest like
> >>>
> >>>     for (;;)
> >>>       if (unlikely_cond)
> >>>         for (;;)
> >>>            invariant;
> >>>
> >>> we want to hoist 'invariant' but only from the inner loop even if it
> >>> is invariant also in the outer loop.
> >>
> >>
> >> For this case, theorotically I think the master GCC will optimize it to:
> >>
> >>    invariant;
> >>    for (;;)
> >>      if (unlikely_cond)
> >>        for (;;)
> >>           ;
> >>
> >> 'invariant' is moved out of outer loop, but with the patch, it will get:
> >>
> >>    for (;;)
> >>      if (unlikely_cond)
> >>        {
> >>          invariant;
> >>          for (;;)
> >>             ;
> >>        }
> >>
> >> 'invariant' is *cold* for outer loop, but it is still *hot* for inner loop,
> >> so hoist it out of inner loop, this is exactly what we want, right?
> >
> > Yes.  I had doubts your patch would achieve that.
> >
>
>
> The below updated patch could achieve it:
>
>
> There was a patch trying to avoid move cold block out of loop:
>
> https://gcc.gnu.org/pipermail/gcc/2014-November/215551.html
>
> Richard suggested to "never hoist anything from a bb with lower execution
> frequency to a bb with higher one in LIM invariantness_dom_walker
> before_dom_children".
>
> In gimple LIM analysis,  add find_coldest_out_loop to move invariants to
> expected target loop, then  if profile count of the loop bb is colder
> than target loop preheader, it won't be hoisted out of loop.
>
> SPEC2017 performance evaluation shows 1% performance improvement for
> intrate GEOMEAN and no obvious regression for others.  Especially,
> 500.perlbench_r +7.52% (Perf shows function S_regtry of perlbench is
> largely improved.), and 548.exchange2_r+1.98%, 526.blender_r +1.00%
> on P8LE.
>
> Regression and bootstrap tested pass on P8LE, any comments?  Thanks.

Can you split the RTL and GIMPLE changes and measure them separately
please?

> gcc/ChangeLog:
>
>         * loop-invariant.c (find_invariants_bb): Check profile count
>         before motion.
>         (find_invariants_body): Add argument.
>         * tree-ssa-loop-im.c (find_coldest_out_loop): New function.
>         (outermost_invariant_loop): Use find_coldest_out_loop.
>         (determine_max_movement): Likewise.
>         (move_computations_worker): Adjust and fix iteration udpate.
>         (execute_sm): Likewise.
>         (execute_sm_exit): Check pointer validness.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/recip-3.c: Adjust.
>         * gcc.dg/tree-ssa/ssa-lim-16.c: New test.
>         * gcc.dg/tree-ssa/ssa-lim-17.c: New test.
> ---
>   gcc/loop-invariant.c                       | 10 ++-
>   gcc/tree-ssa-loop-im.c                     | 79 ++++++++++++++++++----
>   gcc/testsuite/gcc.dg/tree-ssa/recip-3.c    |  2 +-
>   gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-16.c | 20 ++++++
>   gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-17.c | 26 +++++++
>   5 files changed, 121 insertions(+), 16 deletions(-)
>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-16.c
>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-17.c
>
> diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
> index fca0c2b24be..5c3be7bf0eb 100644
> --- a/gcc/loop-invariant.c
> +++ b/gcc/loop-invariant.c
> @@ -1183,9 +1183,14 @@ find_invariants_insn (rtx_insn *insn, bool 
> always_reached, bool always_executed)
>      call.  */
>
>   static void
> -find_invariants_bb (basic_block bb, bool always_reached, bool 
> always_executed)
> +find_invariants_bb (class loop *loop, basic_block bb, bool always_reached,
> +                   bool always_executed)
>   {
>     rtx_insn *insn;
> +  basic_block preheader = loop_preheader_edge (loop)->src;
> +
> +  if (preheader->count > bb->count)
> +    return;
>
>     FOR_BB_INSNS (bb, insn)
>       {
> @@ -1214,8 +1219,7 @@ find_invariants_body (class loop *loop, basic_block 
> *body,
>     unsigned i;
>
>     for (i = 0; i < loop->num_nodes; i++)
> -    find_invariants_bb (body[i],
> -                       bitmap_bit_p (always_reached, i),
> +    find_invariants_bb (loop, body[i], bitmap_bit_p (always_reached, i),
>                         bitmap_bit_p (always_executed, i));
>   }
>
> diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
> index d9f75d5025e..f5ab6a734e7 100644
> --- a/gcc/tree-ssa-loop-im.c
> +++ b/gcc/tree-ssa-loop-im.c
> @@ -417,6 +417,28 @@ movement_possibility (gimple *stmt)
>     return ret;
>   }
>
> +/* Find coldest loop between outmost_loop and loop by comapring profile 
> count.  */
> +
> +static class loop *
> +find_coldest_out_loop (class loop *outmost_loop, class loop *loop,
> +                      basic_block def_bb = NULL)
> +{
> +  class loop *cold_loop, *min_loop;
> +  cold_loop = min_loop = outmost_loop;
> +  profile_count min_count = loop_preheader_edge (min_loop)->src->count;
> +
> +  if (def_bb && def_bb->count < loop_preheader_edge (loop)->src->count)
> +    return NULL;
> +
> +  while (min_loop != loop)
> +    {
> +      min_loop = superloop_at_depth (loop, loop_depth (min_loop) + 1);
> +      if (loop_preheader_edge (min_loop)->src->count < min_count)
> +       cold_loop = min_loop;
> +    }
> +  return cold_loop;
> +}
> +
>   /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
>      loop to that we could move the expression using DEF if it did not have
>      other operands, i.e. the outermost loop enclosing LOOP in that the value
> @@ -431,18 +453,18 @@ outermost_invariant_loop (tree def, class loop *loop)
>     struct lim_aux_data *lim_data;
>
>     if (!def)
> -    return superloop_at_depth (loop, 1);
> +    return find_coldest_out_loop (superloop_at_depth (loop, 1), loop);
>
>     if (TREE_CODE (def) != SSA_NAME)
>       {
>         gcc_assert (is_gimple_min_invariant (def));
> -      return superloop_at_depth (loop, 1);
> +      return find_coldest_out_loop (superloop_at_depth (loop, 1), loop);
>       }
>
>     def_stmt = SSA_NAME_DEF_STMT (def);
>     def_bb = gimple_bb (def_stmt);
>     if (!def_bb)
> -    return superloop_at_depth (loop, 1);
> +    return find_coldest_out_loop (superloop_at_depth (loop, 1), loop, 
> def_bb);
>
>     max_loop = find_common_loop (loop, def_bb->loop_father);
>
> @@ -452,7 +474,13 @@ outermost_invariant_loop (tree def, class loop *loop)
>                                  loop_outer (lim_data->max_loop));
>     if (max_loop == loop)
>       return NULL;
> -  max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
> +  max_loop = find_coldest_out_loop (max_loop, loop, def_bb);
> +  if (!max_loop)
> +    return NULL;
> +  if (max_loop == loop)
> +    return max_loop;
> +  else
> +    max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
>
>     return max_loop;
>   }

As said 'outermost_invariant_loop' is the "correctness" part and I
don't like changing
it this way.  Instead determine_max_movement is what should be adjusted ...

> @@ -684,7 +712,11 @@ determine_max_movement (gimple *stmt, bool 
> must_preserve_exec)
>     if (must_preserve_exec)
>       level = ALWAYS_EXECUTED_IN (bb);
>     else
> -    level = superloop_at_depth (loop, 1);
> +    level = find_coldest_out_loop (superloop_at_depth (loop, 1), loop, bb);

... which you do here (but you should apply that also to the must_preserve_exec
result).

> +
> +  if (!level)
> +    return false;
> +
>     lim_data->max_loop = level;
>
>     if (gphi *phi = dyn_cast <gphi *> (stmt))
> @@ -783,8 +815,10 @@ determine_max_movement (gimple *stmt, bool 
> must_preserve_exec)
>         if (ref
>           && MEM_ANALYZABLE (ref))
>         {
> -         lim_data->max_loop = outermost_indep_loop (lim_data->max_loop,
> -                                                    loop, ref);
> +         level = outermost_indep_loop (lim_data->max_loop, loop, ref);
> +         if (!level)
> +           return false;
> +         lim_data->max_loop = find_coldest_out_loop (level, loop, bb);

... why again here?  outermost_indep_loop honors the passed max_loop.

>           if (!lim_data->max_loop)
>             return false;
>         }
> @@ -1154,6 +1188,7 @@ move_computations_worker (basic_block bb)
>           continue;
>         }
>
> +      edge e = loop_preheader_edge (level);

unncecessary change

>         if (dump_file && (dump_flags & TDF_DETAILS))
>         {
>           fprintf (dump_file, "Moving PHI node\n");
> @@ -1191,14 +1226,13 @@ move_computations_worker (basic_block bb)
>           tree lhs = gimple_assign_lhs (new_stmt);
>           SSA_NAME_RANGE_INFO (lhs) = NULL;
>         }
> -      gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
> +      gsi_insert_on_edge (e, new_stmt);
>         remove_phi_node (&bsi, false);
>       }
>
>     for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
>       {
>         edge e;
> -
>         gimple *stmt = gsi_stmt (bsi);
>
>         lim_data = get_lim_data (stmt);
> @@ -1221,8 +1255,12 @@ move_computations_worker (basic_block bb)
>         /* We do not really want to move conditionals out of the loop; we just
>          placed it here to force its operands to be moved if necessary.  */
>         if (gimple_code (stmt) == GIMPLE_COND)
> -       continue;
> +       {
> +         gsi_next (&bsi);
> +         continue;
> +       }

looks like an omission - do you now run into this?

>
> +      e = loop_preheader_edge (level);

unnecessary change

>         if (dump_file && (dump_flags & TDF_DETAILS))
>         {
>           fprintf (dump_file, "Moving statement\n");
> @@ -1231,7 +1269,6 @@ move_computations_worker (basic_block bb)
>                    cost, level->num);
>         }
>
> -      e = loop_preheader_edge (level);
>         gcc_assert (!gimple_vdef (stmt));
>         if (gimple_vuse (stmt))
>         {
> @@ -2133,6 +2170,19 @@ execute_sm (class loop *loop, im_mem_ref *ref,
>     bool multi_threaded_model_p = false;
>     gimple_stmt_iterator gsi;
>     sm_aux *aux = new sm_aux;
> +  basic_block bb = gimple_bb (first_mem_ref_loc (loop, ref)->stmt);
> +
> +  edge e = loop_preheader_edge (loop);
> +  if (e->src->count > bb->count)
> +    {
> +      if (dump_file && (dump_flags & TDF_DETAILS))
> +       {
> +         fprintf (dump_file, "Don't execute store motion of ");
> +         print_generic_expr (dump_file, ref->mem.ref);
> +         fprintf (dump_file, " from loop %d\n", loop->num);
> +       }
> +      return;
> +    }

why do you need this?  I think you instead want to adjust 'can_sm_ref_p'
where you want to use sth like

  for_all_locs_in_loop (loop, ref, ...)

and ... being a lambda or function that checks loc->stmt and if at least one
reference is executed in a hot part of 'loop' then we should apply store-motion.
Do this last because it looks somewhat expensive.

>
>     if (dump_file && (dump_flags & TDF_DETAILS))
>       {
> @@ -2241,7 +2291,12 @@ execute_sm_exit (class loop *loop, edge ex, 
> vec<seq_entry> &seq,
>         }
>         else
>         {
> -         sm_aux *aux = *aux_map.get (ref);
> +         sm_aux **paux = aux_map.get (ref);
> +         sm_aux *aux;
> +         if (paux)
> +           aux = *paux;
> +         else
> +           continue;
>           if (!aux->store_flag || kind == sm_ord)
>             {
>               gassign *store;
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c 
> b/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c
> index 638bf38db8c..641c91e719e 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c
> @@ -23,4 +23,4 @@ float h ()
>         F[0] += E / d;
>   }
>
> -/* { dg-final { scan-tree-dump-times " / " 1 "recip" } } */
> +/* { dg-final { scan-tree-dump-times " / " 5 "recip" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-16.c 
> b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-16.c
> new file mode 100644
> index 00000000000..2303f3d5d86
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-16.c
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-lim2-details" } */
> +
> +volatile int x;
> +void
> +assert_fail (int, char *, char *);
> +void
> +foo (int *a, int n, int k)
> +{
> +  int i;
> +
> +  for (i = 0; i < n; i++)
> +    {
> +      if (__builtin_expect (x, 0))
> +       assert_fail (k / 5, "one", "two");

I don't think these are very good testcases since 'assert' is usually
noreturn which would place the whole block outside of the loop (it's
a loop exit then).  But naming the function 'foo' would make it less
obviously pointless.

> +      a[i] = k;
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-not "out of loop 1" "lim2" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-17.c 
> b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-17.c
> new file mode 100644
> index 00000000000..3b1c7c0cb3e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-17.c
> @@ -0,0 +1,26 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-lim2-details" } */
> +
> +volatile int x;
> +void
> +assert_fail (int, char *, char *);
> +void
> +foo (int *a, int n, int m, int k, int s)
> +{
> +  int i;
> +  int j;
> +
> +  for (i = 0; i < m; i++)
> +    {
> +      if (__builtin_expect (x, 0))
> +       for (j = 0; j < n; j++)
> +         {
> +           assert_fail (k / 5, "one", "two");
> +         a[s] = k;
> +       }
> +      a[s] = s;
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "out of loop 2" 4 "lim2" } } */
> +/* { dg-final { scan-tree-dump-times "out of loop 1" 3 "lim2" } } */
> --
> 2.27.0.90.geebb51ba8c
>
>

Reply via email to