Re: [PATCH GCC][2/2]Refine CFG and bound information for split loops

[Jeff Law <law@redhat.com>]

On 06/14/2017 07:08 AM, Bin Cheng wrote:
> Hi,
> Loop split currently generates below control flow graph for split loops:
> +
> +               .------ guard1  ------.
> +               v                     v
> +         pre1(loop1)    .---------->pre2(loop2)
> +              |         |            |
> +        .--->h1         |           h2<----.
> +        |     |         |            |     |
> +        |    ex1---.    |       .---ex2    |
> +        |    /     v    |       |     \    |
> +        '---l1 guard2---'       |     l2---'
> +                   |            |
> +                   |            |
> +                   '--->join<---'
> +
> In which,
> +   LOOP2 is the second loop after split, GUARD1 and GUARD2 are the two bbs
> +   controling if loop2 should be executed.
> 
> Take added test case as an example, the second loop only iterates for 1 time,
> as a result, the CFG and loop niter bound information can be refined.  In general,
> guard1/guard2 can be folded to true/false if loop2's niters is known at compilation
> time.  This patch does such improvement by analyzing and refining niters of
> loop2; as well as using that information to simplify CFG.  With this patch,
> the second split loop as in test can be completely unrolled by later passes.
In your testcase the second loop iterates precisely once, right?  In
fact, we know it always executes precisely one time regardless of the
incoming value of LEN.  That's the property you're trying to detect and
exploit, right?


> 
> Bootstrap and test on x86_64 and AArch64.  Is it OK?
> 
> Thanks,
> bin
> 2017-06-12  Bin Cheng  <bin.cheng@arm.com>
> 
> 	* tree-ssa-loop-split.c (compute_new_first_bound): Compute and
> 	return bound information for the second split loop.
> 	(adjust_loop_split): New function.
> 	(split_loop): Update calls to above functions.
> 
> gcc/testsuite/ChangeLog
> 2017-06-12  Bin Cheng  <bin.cheng@arm.com>
> 
> 	* gcc.dg/loop-split-1.c: New test.
> 
> 
> 0002-lsplit-refine-cfg-niter-bound-20170601.txt
> 
> 
> From 61855c74c7db6178008f007198aedee9a03f13e6 Mon Sep 17 00:00:00 2001
> From: amker <amker@amker-laptop.(none)>
> Date: Sun, 4 Jun 2017 02:26:34 +0800
> Subject: [PATCH 2/2] lsplit-refine-cfg-niter-bound-20170601.txt
> 
> ---
>  gcc/testsuite/gcc.dg/loop-split-1.c |  16 +++
>  gcc/tree-ssa-loop-split.c           | 197 ++++++++++++++++++++++++++++++++----
>  2 files changed, 194 insertions(+), 19 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/loop-split-1.c
> 
> diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c
> index f8fe8e6..73c7dc2 100644
> --- a/gcc/tree-ssa-loop-split.c
> +++ b/gcc/tree-ssa-loop-split.c
> @@ -387,28 +386,41 @@ connect_loops (struct loop *loop1, struct loop *loop2)
>  
>     Depending on the direction of the IVs and if the exit tests
>     are strict or non-strict we need to use MIN or MAX,
> -   and add or subtract 1.  This routine computes newend above.  */
> +   and add or subtract 1.  This routine computes newend above.
> +
> +   After computing the new bound (on j), we may be able to compare the
> +   first loop's iteration space against the original loop's.  If it is
> +   comparable at compilation time, we may be able to compute the niter
> +   bound of the second loop.  Record the second loop's iteration bound
> +   to SECOND_LOOP_NITER_BOUND which has below meaning:
> +
> +     -3: Don't know anything about the second loop;
> +     -2: The second loop must not be executed;
> +     -1: The second loop must be executed, but niter bound is unknown;
> +      n: The second loop must be executed, niter bound is n (>= 0);
> +
> +   Note we compute niter bound for the second loop's latch.  */
How hard would it be to have a test for each of the 4 cases above?  I
don't always ask for this, but ISTM this is a good chance to make sure
most of the new code gets covered by testing.

Does case -2 really occur in practice or are you just being safe?  ISTM
that if case -2 occurs then the loop shouldn't have been split to begin
with.  If this happens in practice, do we clean up all the dead code if
the bounds are set properly.

Similarly for N = 0, presumably meaning the second loop iterates exactly
once, but never traverses its backedge, is there any value in changing
the loop latch test so that it's always false?  Or will that get cleaned
up later?


>  
>  static tree
> -compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter,
> -			 tree border,
> -			 enum tree_code guard_code, tree guard_init)
> +compute_new_first_bound (struct tree_niter_desc *niter, tree border,
> +			 enum tree_code guard_code, tree guard_init,
> +			 tree step, HOST_WIDE_INT *second_loop_niter_bound)
>  {
> -  /* The niter structure contains the after-increment IV, we need
> -     the loop-enter base, so subtract STEP once.  */
>    tree controlbase = niter->control.base;
>    tree controlstep = niter->control.step;
>    tree enddiff, end = niter->bound;
>    tree type;
>  
> -  /* Compute end-beg.  */
> +  /* Compute end-beg.
> +     Note the niter structure contains the after-increment IV, we need the
> +     loop-enter base, so subtract STEP once.  */
>    if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
>      {
>        controlstep = fold_build1 (NEGATE_EXPR,
>  				 TREE_TYPE (controlstep), controlstep);
>        enddiff = fold_build_pointer_plus (controlbase, controlstep);
>  
> -      type = unsigned_type_for (enddiff);
> +      type = unsigned_type_for (TREE_TYPE (enddiff));
Isn't this an indication the trunk sources are broken?  Consider pushing
this forward independent of the rest of this change if it looks like
we're going to have to iterate more than once or twice.



> @@ -462,8 +476,148 @@ compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter,
>  			      build_int_cst (type, addbound));
>      }
>  
> -  newbound = fold_build2 (minmax, TREE_TYPE (border), border, newbound);
> -  return force_gimple_operand (newbound, stmts, true, NULL_TREE);
> +  tree cmp_rslt = fold_build2 (cmp_code, boolean_type_node, border, newbound);
> +  /* Only handle simple case with unit step.  */
> +  if (wi::eq_p (wi::abs (step), 1)
> +      && cmp_rslt != NULL_TREE && integer_nonzerop (cmp_rslt))
> +    {
> +      if (integer_nonzerop (cmp_rslt))
> +	{
> +	  tree niter_type, diff;
> +
> +	  niter_type = unsigned_type_for (TREE_TYPE (newbound));
> +	  /* The split condition indicates smaller iteration space than the
> +	     original loop, so the second loop must be executed.  */
> +	  if (cmp_code == LT_EXPR)
> +	    diff = fold_build2 (MINUS_EXPR, niter_type,
> +				fold_convert (niter_type, newbound),
> +				fold_convert (niter_type, border));
> +	  else
> +	    diff = fold_build2 (MINUS_EXPR, niter_type,
> +				fold_convert (niter_type, border),
> +				fold_convert (niter_type, newbound));
> +
> +	  /* Check if niter can be computed.  */
> +	  if (tree_fits_shwi_p (diff) && !tree_int_cst_sign_bit (diff))
> +	    *second_loop_niter_bound = tree_to_shwi (diff) - 1;
> +	  else
> +	    *second_loop_niter_bound = -1;
> +
> +	  return border;
> +	}
> +      else if (integer_zerop (cmp_rslt))
> +	{
> +	  /* The split condition indicates larger iteration space than the
> +	     oiginal loop, so the second loop must not be executed.  */
s/oiginal/original/


Overall I like it and it looks reasonably close to being ready.   Let's
get the answers to the few questions above and decide how to move
forward after that.

Thanks,

Jeff