Re: [RFC] Don't move cold code out of loop by checking bb count

[Xionghu Luo <luoxhu@linux.ibm.com>]

On 2021/10/15 16:11, Richard Biener wrote:
> On Sat, Oct 9, 2021 at 5:45 AM Xionghu Luo <luoxhu@linux.ibm.com> wrote:
>>
>> Hi,
>>
>> On 2021/9/28 20:09, Richard Biener wrote:
>>> On Fri, Sep 24, 2021 at 8:29 AM Xionghu Luo <luoxhu@linux.ibm.com> wrote:
>>>>
>>>> Update the patch to v3, not sure whether you prefer the paste style
>>>> and continue to link the previous thread as Segher dislikes this...
>>>>
>>>>
>>>> [PATCH v3] Don't move cold code out of loop by checking bb count
>>>>
>>>>
>>>> Changes:
>>>> 1. Handle max_loop in determine_max_movement instead of
>>>> outermost_invariant_loop.
>>>> 2. Remove unnecessary changes.
>>>> 3. Add for_all_locs_in_loop (loop, ref, ref_in_loop_hot_body) in can_sm_ref_p.
>>>> 4. "gsi_next (&bsi);" in move_computations_worker is kept since it caused
>>>> infinite loop when implementing v1 and the iteration is missed to be
>>>> updated actually.
>>>>
>>>> v1: https://gcc.gnu.org/pipermail/gcc-patches/2021-August/576488.html
>>>> v2: https://gcc.gnu.org/pipermail/gcc-patches/2021-September/579086.html
>>>>
>>>> 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, if profile count of the loop bb is colder
>>>> than target loop preheader, it won't be hoisted out of loop.
>>>> Likely for store motion, if all locations of the REF in loop is cold,
>>>> don't do store motion of it.
>>>>
>>>> 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.
>>>>
>>>> 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.
>>>>         (determine_max_movement): Use find_coldest_out_loop.
>>>>         (move_computations_worker): Adjust and fix iteration udpate.
>>>>         (execute_sm_exit): Check pointer validness.
>>>>         (class ref_in_loop_hot_body): New functor.
>>>>         (ref_in_loop_hot_body::operator): New.
>>>>         (can_sm_ref_p): Use for_all_locs_in_loop.
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>>
>>>>         * gcc.dg/tree-ssa/recip-3.c: Adjust.
>>>>         * gcc.dg/tree-ssa/ssa-lim-18.c: New test.
>>>>         * gcc.dg/tree-ssa/ssa-lim-19.c: New test.
>>>>         * gcc.dg/tree-ssa/ssa-lim-20.c: New test.
>>>> ---
>>>>  gcc/loop-invariant.c                       | 10 ++--
>>>>  gcc/tree-ssa-loop-im.c                     | 61 ++++++++++++++++++++--
>>>>  gcc/testsuite/gcc.dg/tree-ssa/recip-3.c    |  2 +-
>>>>  gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-18.c | 20 +++++++
>>>>  gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-19.c | 27 ++++++++++
>>>>  gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-20.c | 25 +++++++++
>>>>  gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-21.c | 28 ++++++++++
>>>>  7 files changed, 165 insertions(+), 8 deletions(-)
>>>>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-18.c
>>>>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-19.c
>>>>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-20.c
>>>>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-21.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 4b187c2cdaf..655fab03442 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 curr_bb)
>>>> +{
>>>> +  class loop *cold_loop, *min_loop;
>>>> +  cold_loop = min_loop = outmost_loop;
>>>> +  profile_count min_count = loop_preheader_edge (min_loop)->src->count;
>>>> +
>>>> +  if (curr_bb && curr_bb->count < loop_preheader_edge (loop)->src->count)
>>>
>>> Honza - can you comment on whether we should compare BB counts this way?
>>>
>>> I would suspect that for, say,
>>>
>>>   for (...)
>>>      if (a)
>>>        X;
>>>      else
>>>        Y;
>>>
>>> that the counts for X and Y will be less than that of the preheader of the loop
>>> only when the loop is estimated to run once.  That is, should we really compare
>>> the to the preheader count or maybe better to the _header_ count which
>>> would keep the number of iterations out of the equation?
>>
>> I quickly tried to replace all the loop_preheader_edge (loop)->src with
>> loop_preheader_edge (loop)->dest, it will cause many failures in
>> gcc.dg/tree-ssa/ssa-lim-*.c, I didn't go deep to investigate, but it seems
>> reasonable to compare the bb count with preheader count as both gimple lim
>> and RTL loop-invariant move instructions to *preheader* instead of *header*
>> after analysis?
> 
> Hmm, yeah - guess I was confused here.
> 
>>>
>>> If we look at maybe_hot_count_p that's a quite sophisticated thing to
>>> compare a count to the "IPA hot", here we're comparing two counts
>>> within a function where it actually matters whether we use a<b or
>>> !(a>=b) since 'unordered' is mapped to false (but there's no ordered_p
>>> function).
>>>
>>> Xionghu, you error on the side of not hoisting for unordered counts here
>>>
>>>> +    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)
>>>
>>> but in the other direction here and on the side of not hoisting
>>> in ref_in_loop_hot_body.
>>>
>>> The three-state relational operator overloads are probably not the
>>> very best idea...
>>> (see profile-count.h for them)
>>>
>> Added new function bb_colder_than_loop_preheader to encapsulate the comparision,
>> if FALSE is returned due to three-state inequality,  find_coldest_out_loop
>> will return the original input to lim->max_loop, and ref_in_loop_hot_body::operator ()
>> will return true to continue perform store motion, both preserve the previous
>> behavior.
> 
> Thanks.  But I don't think the abstraction as written is useful:
> 
> +/* Compare the profile count inequality of COUNT1 and COUNT2, it is three-state
> +   as stated in profile-count.h, FALSE is returned if inequality cannot be
> +   decided.  */
> +bool bb_colder_than_loop_preheader (profile_count count1, profile_count count2)
> +{
> +  if (count1 < count2)
> +    return true;
> +  else
> +    return false;
> +}
> 
> given the following seems to pass the preheader count in place of the BB count.
> 
> +      if (bb_colder_than_loop_preheader (
> +           loop_preheader_edge (min_loop)->src->count, min_count))
> +       cold_loop = min_loop;
> 
> find_coldest_out_loop is also a bit weird, I think we want to find
> the outermost loop between outmost_loop and loop that has a
> lower count than the curr_bb count but
> 
> +  while (min_loop != loop)
> +    {
> +      min_loop = superloop_at_depth (loop, loop_depth (min_loop) + 1);
> +      if (bb_colder_than_loop_preheader (
> +           loop_preheader_edge (min_loop)->src->count, min_count))
> +       cold_loop = min_loop;
> 
> compares the outermost loops count (min_count) against the preheader
> count?  So we're searching for a cold loop with respect to its enclosing loop
> here?

Let me try to explain how it works :)

find_coldest_out_loop does two steps check:
1) Check whether curr_bb is cold in it's own loop_father, if it is cold,
just return NULL which means it should not be moved out at all;
2)  curr_bb is NOT cold, assuming the current loop L[m] is the coldest first, 
than try to find a cold loop to be hoisted to from {L[1], L[2], ... L[m]}, 
if L[i]->count < L[m]->count, set the cold_loop to L[i] until find the loop
that has smallest profile_count.


Take the updated ssa-lim-19.c as example, check whether curr_bb(bb 5) is cold in
loop 3, if it is cold, just return NULL, otherwise select the coldest loop in
{loop1, loop2, loop3} and find that loop2 is colder than loop3, return loop2 to
be the target hoist loop.  The first check could AVOID hoist if curr_bb is colder
than loop3, but it is still hot than loop1 and loop2.  Not sure whether it is possible
to construct such cases?


gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-19.c

volatile int x;
void
bar (int, char *, char *);
void
foo (int *a, int n, int m, int s, int t)
{
  int i;
  int j;
  int k;

  for (i = 0; i < m; i++)  // loop 1
    {
      if (__builtin_expect (x, 0))
        for (j = 0; j < n; j++)   // loop 2
          for (k = 0; k < n; k++)   // loop 3
           {
             bar (s / 5, "one", "two");  // curr_bb 
             a[t] = s;
           }
      a[t] = t;  // curr_bb2
    }
}

The 4 invariant statements are moved to bb 11(loop2) instead of bb 10(loop1)
with this patch.
There are totally 6 combinations when curr_bb is hotter than loop 3.  We need
to compare the "Loop preheader hotness" instead of "every Loop[i] and curr_bb hotness",
returning the coldest loop for this function find_coldest_out_loop, otherwise
unexpected behavior happens.

L1 > L2 > L3   =>  return L3
L1 > L3 > L2   =>  return L2
L2 > L1 > L3   =>  return L3
L2 > L3 > L1   =>  return L1
L3 > L1 > L2   =>  return L2
L3 > L2 > L1   =>  return L1

So bb_colder_than_loop_preheader does two kind of checks, one is checking
L3 preheader count with curr_bb count, another is checking L3 preheader count
with L1 preheader count, L2 preheader count, etc...


ssa-lim-19.c.138t.lim2:
...
   <bb 10> [local count: 16057869]:  // L1 preheader
-  _4 = s_22(D) / 5;
-  _5 = (long unsigned int) t_24(D);
-  _6 = _5 * 4;
-  _7 = a_25(D) + _6;
   _8 = (long unsigned int) t_24(D);
   _9 = _8 * 4;
   _10 = a_25(D) + _9;

   <bb 3> [local count: 145980626]:
   # i_34 = PHI <i_29(12), 0(10)>
   x.0_1 ={v} x;
   if (x.0_1 != 0)
     goto <bb 4>; [10.00%]
   else
     goto <bb 8>; [90.00%]

   <bb 4> [local count: 14598063]:
   if (n_20(D) > 0)
     goto <bb 11>; [89.00%]
   else
     goto <bb 8>; [11.00%]

   <bb 11> [local count: 12992276]:  // L2 preheader
+  _4 = s_22(D) / 5;
+  _5 = (long unsigned int) t_24(D);
+  _6 = _5 * 4;
+  _7 = a_25(D) + _6;
   goto <bb 7>; [100.00%]

   <bb 14> [local count: 850510901]:

   <bb 5> [local count: 955630225]:  // curr_bb
   # k_36 = PHI <k_27(14), 0(7)>
   bar (_4, "one", "two");
   *_7 = s_22(D);
   k_27 = k_36 + 1;
   if (n_20(D) > k_27)
     goto <bb 14>; [89.00%]
   else
     goto <bb 6>; [11.00%]

   <bb 6> [local count: 118111600]:
   j_21 = j_35 + 1;
   if (n_20(D) > j_21)
     goto <bb 13>; [89.00%]
   else
     goto <bb 8>; [11.00%]

   <bb 13> [local count: 105119324]:

   <bb 7> [local count: 118111600]:   // L3 preheader
   # j_35 = PHI <j_21(13), 0(11)>
   goto <bb 5>; [100.00%]

   <bb 8> [local count: 145980626]:
   *_10 = t_24(D);
   i_29 = i_34 + 1;

Re-paste the bb_colder_than_loop_preheader and find_coldest_out_loop:

+/* Compare the profile count inequality of COUNT1 and COUNT2, it is three-state
+   as stated in profile-count.h, FALSE is returned if inequality cannot be
+   decided.  */
+bool bb_colder_than_loop_preheader (profile_count count1, profile_count count2)
+{
+  if (count1 < count2)
+    return true;
+  else
+    return false;
+}
+
+/* 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 curr_bb)
+{
+  class loop *cold_loop, *min_loop;
+  cold_loop = min_loop = outmost_loop;
+  profile_count min_count = loop_preheader_edge (min_loop)->src->count;
+
+  /* If bb_colder_than_loop_preheader returns false due to three-state
+    comparision, OUTMOST_LOOP is returned finally to preserve the behavior.
+    Otherwise, return the coldest loop between OUTMOST_LOOP and LOOP.  */
+  if (curr_bb
+      && bb_colder_than_loop_preheader (curr_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 (bb_colder_than_loop_preheader (
+	    loop_preheader_edge (min_loop)->src->count, min_count))
+	cold_loop = min_loop;
+    }
+  return cold_loop;
+}
+


> 
> Why is this function not simply
> 
> +static class loop *
> +find_coldest_out_loop (class loop *outmost_loop, class loop *loop,
> +                      basic_block curr_bb)
> +{
>      while (bb_colder_than_loop_preheader (curr_bb->count,
>                loop_preheader_edge (outermost_loop)->src->count))
>         {
>             if (outermost_loop == loop)
>               return NULL;
>             outermost_loop = superloop_at_depth (loop, loop_depth
> (outermost_loop) + 1);
>         }
>      return outermost_loop;
> }

If change like this, when processing curr_bb(5), outermost_loop will
return loop 1 since curr_bb->count > Loop1_prehead->count, the while
loop stopped.  This doesn't meet what we want.  

> 
> ?
> 
> Likewise I wonder why ref_in_loop_hot_body::operator () needs to call
> find_coldest_out_loop and why it not simply does
> 
> +bool
> +ref_in_loop_hot_body::operator () (mem_ref_loc *loc)
> +{
> +  basic_block curr_bb = gimple_bb (loc->stmt);
>     if (bb_colder_than_loop_preheader (curr_bb->count,
> loop_preheader_edge (l)->src->count))
>       return false;
>    return true;
>    }

Likely for this part,

+/* Find out the coldest loop between loop L and innermost loop, compare the
+   hotness between current BB and coldest loop preheader by profile count.  */
+bool
+ref_in_loop_hot_body::operator () (mem_ref_loc *loc)
+{
+  basic_block curr_bb = gimple_bb (loc->stmt);
+  class loop *inner_loop = curr_bb->loop_father;
+  class loop *cold_loop = l;
+  if (l != inner_loop)
+    cold_loop = find_coldest_out_loop (l, inner_loop, curr_bb);
+  if (!cold_loop)
+    return false;
+  edge e = loop_preheader_edge (cold_loop);
+  /*  If bb_colder_than_loop_preheader is false due to three-state inequality
+     comparision, TRUE is returned to continue perform store motion.  */
+  if (bb_colder_than_loop_preheader (curr_bb->count, e->src->count))
+    return false;
+  else
+    return true;
+}

l is the input of ref_in_loop_hot_body, it is an out loop, we need to find a
cold_loop between l and inner_loop.  Reason is there may be cold loop between
l and inner_loop, which means we shouldn't do store-motion from curr_bb to l
directly.
After reconsideration, I think the bb_colder_than_loop_preheader could be
 removed since curr_bb is checked in find_coldest_out_loop already.  And remove
the "l != inner_loop" check:

+/* Find out the coldest loop between loop L and innermost loop.  */
+bool
+ref_in_loop_hot_body::operator () (mem_ref_loc *loc)
+{
+  basic_block curr_bb = gimple_bb (loc->stmt);
+  class loop *inner_loop = curr_bb->loop_father;
+  class loop *cold_loop = l;
+  cold_loop = find_coldest_out_loop (l, inner_loop, curr_bb);
+  if (!cold_loop)
+    return false;
+  return true;
+}


-- 
Thanks,
Xionghu