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

[Bin.Cheng]

On Fri, Jun 30, 2017 at 5:09 PM, Jeff Law  wrote:
> 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  
>>
>>   * 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  
>>
>>   * 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 
>> 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)
>>  {

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

[Jeff Law]

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  
> 
>   * 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  
> 
>   * 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 
> 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 

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

[Bernhard Reutner-Fischer]

On 14 June 2017 at 15:08, 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.

@@ -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))

Did you mean to drop the above integer_nonzerop() in favour of
distinguishing -1 and -2 below or did you disable -2 on purpose?
If so then i'd swap the order of the NULL check and the wi:: as
supposedly faster and easier to read..

thanks,

+{
+  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.  */
+  *second_loop_niter_bound = -2;
+  return newbound;
+ }
+}
+

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

[Bin Cheng]

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.

Bootstrap and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin
2017-06-12  Bin Cheng  

* 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  

* gcc.dg/loop-split-1.c: New test.From 61855c74c7db6178008f007198aedee9a03f13e6 Mon Sep 17 00:00:00 2001
From: amker 
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/testsuite/gcc.dg/loop-split-1.c 
b/gcc/testsuite/gcc.dg/loop-split-1.c
new file mode 100644
index 000..2fd3e04
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-split-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsplit-loops -fdump-tree-lsplit-details" } */
+
+int foo (int *a, int *b, int len)
+{
+  int k;
+  for (k = 1; k <= len; k++)
+{
+  a[k]++;
+
+  if (k < len)
+   b[k]++;
+}
+}
+
+/* { dg-final { scan-tree-dump "The second split loop iterates at 0 latch 
times." "lsplit" } } */
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
@@ -364,10 +364,9 @@ connect_loops (struct loop *loop1, struct loop *loop2)
 
 /* This returns the new bound for iterations given the original iteration
space in NITER, an arbitrary new bound BORDER, assumed to be some
-   comparison value with a different IV, the initial value GUARD_INIT of
-   that other IV, and the comparison code GUARD_CODE that compares
-   that other IV with BORDER.  We return an SSA name, and place any
-   necessary statements for that computation into *STMTS.
+   comparison value with a different IV, the initial value GUARD_INIT and
+   STEP of the other IV, and the comparison code GUARD_CODE that compares
+   that other IV with BORDER.
 
For example for such a loop:
 
@@ -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.  */
 
 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
-