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

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

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?


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