Re: [PATCH] tree-optimization/102155 - fix LIM fill_always_executed_in CFG walk

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

On 2021/9/10 21:54, Xionghu Luo via Gcc-patches wrote:
> 
> 
> On 2021/9/9 18:55, Richard Biener wrote:
>> diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
>> index 5d6845478e7..4b187c2cdaf 100644
>> --- a/gcc/tree-ssa-loop-im.c
>> +++ b/gcc/tree-ssa-loop-im.c
>> @@ -3074,15 +3074,13 @@ fill_always_executed_in_1 (class loop *loop, 
>> sbitmap contains_call)
>>           break;
>>         if (bb->loop_father->header == bb)
>> -        {
>> -          if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
>> -        break;
>> -
>> -          /* In a loop that is always entered we may proceed anyway.
>> -         But record that we entered it and stop once we leave it
>> -         since it might not be finite.  */
>> -          inn_loop = bb->loop_father;
>> -        }
>> +        /* Record that we enter into a subloop since it might not
>> +           be finite.  */
>> +        /* ???  Entering into a not always executed subloop makes
>> +           fill_always_executed_in quadratic in loop depth since
>> +           we walk those loops N times.  This is not a problem
>> +           in practice though, see PR102253 for a worst-case 
>> testcase.  */
>> +        inn_loop = bb->loop_father;
> 
> 
> Yes your two patches extracted the get_loop_body_in_dom_order out and 
> removed
> the inn_loop break logic when it doesn't dominate outer loop.  Confirmed 
> the replacement
> could improve for saving ~10% build time due to not full DOM walker and 
> marked the previously
> ignored ALWAYS_EXECUTED bbs.
> But if we don't break for inner loop again, why still keep the 
> *inn_loop* variable?
> It seems unnecessary and confusing, could we just remove it and restore 
> the original
> infinte loop check in bb->succs for better understanding?


What's more, the refine of this fix is incorrect for PR78185.


commit 483e400870601f650c80f867ec781cd5f83507d6
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Sep 2 10:47:35 2021 +0200

     Refine fix for PR78185, improve LIM for code after inner loops
     
     This refines the fix for PR78185 after understanding that the code
     regarding to the comment 'In a loop that is always entered we may
     proceed anyway.  But record that we entered it and stop once we leave
     it.' was supposed to protect us from leaving possibly infinite inner
     loops.  The simpler fix of moving the misplaced stopping code
     can then be refined to continue processing when the exited inner
     loop is finite, improving invariant motion for cases like in the
     added testcase.
     
     2021-09-02  Richard Biener  <rguenther@suse.de>
     
             * tree-ssa-loop-im.c (fill_always_executed_in_1): Refine
             fix for PR78185 and continue processing when leaving
             finite inner loops.
     
             * gcc.dg/tree-ssa/ssa-lim-16.c: New testcase.


3<-------
|        |
6<---    |
| \  |   |
|  \ |   |
4    8   |
|---     |
|  |     |
5  7------
|
1

loop 2 is an infinite loop, it is only ALWAYS_EXECUTED for loop 2,
but r12-3313-g483e40087 sets it ALWAYS_EXECUTED for loop 1.
We need to restore it like this:
https://gcc.gnu.org/pipermail/gcc-patches/2021-September/579195.html


diff of pr78185.c.138t.lim2:
;;
  ;; Loop 1
  ;;  header 3, latch 7
  ;;  depth 1, outer 0
  ;;  nodes: 3 7 4 6 8
  ;;
  ;; Loop 2
  ;;  header 6, latch 8
  ;;  depth 2, outer 1
  ;;  nodes: 6 8
  ;; 2 succs { 3 }
  ;; 3 succs { 6 }
  ;; 6 succs { 4 8 }
  ;; 8 succs { 6 }
  ;; 4 succs { 7 5 }
  ;; 7 succs { 3 }
  ;; 5 succs { 1 }
  Memory reference 1: var1
-BB 6 is always executed in loop 1
  BB 3 is always executed in loop 1
+BB 6 is always executed in loop 2
  Basic block 3 (loop 1 -- depth 1):

  Basic block 6 (loop 2 -- depth 2):


> 
> 
> diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
> index d1e2104233b..82a0509e0c4 100644
> --- a/gcc/tree-ssa-loop-im.c
> +++ b/gcc/tree-ssa-loop-im.c
> @@ -3200,7 +3200,6 @@ fill_always_executed_in_1 (class loop *loop, 
> sbitmap contains_call)
>   {
>     basic_block bb = NULL, last = NULL;
>     edge e;
> -  class loop *inn_loop = loop;
> 
>     if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
>       {
> @@ -3213,17 +3212,6 @@ fill_always_executed_in_1 (class loop *loop, 
> sbitmap contains_call)
>            edge_iterator ei;
>            bb = worklist.pop ();
> 
> -         if (!flow_bb_inside_loop_p (inn_loop, bb))
> -           {
> -             /* When we are leaving a possibly infinite inner loop
> -                we have to stop processing.  */
> -             if (!finite_loop_p (inn_loop))
> -               break;
> -             /* If the loop was finite we can continue with processing
> -                the loop we exited to.  */
> -             inn_loop = bb->loop_father;
> -           }
> -
>            if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
>              last = bb;
> 
> @@ -3232,8 +3220,15 @@ fill_always_executed_in_1 (class loop *loop, 
> sbitmap contains_call)
> 
>           /* If LOOP exits from this BB stop processing.  */
>            FOR_EACH_EDGE (e, ei, bb->succs)
> +         {
>              if (!flow_bb_inside_loop_p (loop, e->dest))
>                break;
> +           /* Or we enter a possibly non-finite loop.  */
> +           if (flow_loop_nested_p (bb->loop_father,
> +                 e->dest->loop_father)
> +               && ! finite_loop_p (e->dest->loop_father))
> +             break;
> +         }
>            if (e)
>              break;
> 
> @@ -3242,15 +3237,6 @@ fill_always_executed_in_1 (class loop *loop, 
> sbitmap contains_call)
>            if (bb->flags & BB_IRREDUCIBLE_LOOP)
>              break;
> 
> -         if (bb->loop_father->header == bb)
> -           /* Record that we enter into a subloop since it might not
> -              be finite.  */
> -           /* ???  Entering into a not always executed subloop makes
> -              fill_always_executed_in quadratic in loop depth since
> -              we walk those loops N times.  This is not a problem
> -              in practice though, see PR102253 for a worst-case 
> testcase.  */
> -           inn_loop = bb->loop_father;
> -
>            /* Walk the body of LOOP sorted by dominance relation.  
> Additionally,
>               if a basic block S dominates the latch, then only blocks 
> dominated
>               by S are after it.
> 
> 
> 
>>         /* Walk the body of LOOP sorted by dominance relation.  
>> Additionally,
>>            if a basic block S dominates the latch, then only blocks 
>> dominated
> 

-- 
Thanks,
Xionghu