[PR65637] Fix ssa-handling code in expand_omp_for_static_chunk

[PR65637] Fix ssa-handling code in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 922 bytes --]

Hi,

This patch series fixes PR65637.

Currently, ssa-handling code in expand_omp_for_static_chunk is dead and not 
exercised by testing.

Ssa-handling code in omp-low.c is only triggered by pass_parallelize_loops, and 
that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it constructs, so 
that only exercises the expand_omp_for_static_nochunk path.

Using the attached trigger patch, we excercise the ssa-handling code in 
expand_omp_for_static_chunk. The following patch series fixes the problems in 
the ssa-handling code that we encounter.

1. Fix gcc_assert in expand_omp_for_static_chunk
2. Fix inner loop phi in expand_omp_for_static_chunk
3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk

The patch series has been bootstrapped and reg-tested on x86_64 together with 
attached trigger patch.

I'll post the patches from the patch series individually, in response to this email.

Thanks,
- Tom

[-- Attachment #2: 0001-Set-chunk_size-to-one-for-parloops-parallel.patch --]
[-- Type: text/x-patch, Size: 663 bytes --]

Set chunk_size to one for parloops parallel

---
 gcc/tree-parloops.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index 62a6444..862c420 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -1719,6 +1719,7 @@ create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
   type = TREE_TYPE (cvar);
   t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
   OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
+  OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t) = integer_one_node;
 
   for_stmt = gimple_build_omp_for (NULL, GF_OMP_FOR_KIND_FOR, t, 1, NULL);
   gimple_set_location (for_stmt, loc);
-- 
1.9.1

[PR65637][PATCH][1/3] Fix gcc_assert in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2054 bytes --]

On 15-04-15 15:10, Tom de Vries wrote:
> Hi,
>
> This patch series fixes PR65637.
>
> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and not
> exercised by testing.
>
> Ssa-handling code in omp-low.c is only triggered by pass_parallelize_loops, and
> that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it constructs, so
> that only exercises the expand_omp_for_static_nochunk path.
>
> Using the attached trigger patch, we excercise the ssa-handling code in
> expand_omp_for_static_chunk. The following patch series fixes the problems in
> the ssa-handling code that we encounter.
>
> 1. Fix gcc_assert in expand_omp_for_static_chunk
> 2. Fix inner loop phi in expand_omp_for_static_chunk
> 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> The patch series has been bootstrapped and reg-tested on x86_64 together with
> attached trigger patch.
>
> I'll post the patches from the patch series individually, in response to this
> email.
>

This patch fixes a segfault in an gcc_assert in expand_omp_for_static_chunk
while compiling autopar/pr46099.c.

When compiling f1 from autopar/pr46099.c using expand_omp_for_static_chunk, we
redirect the edge (trip_update_bb -> fin_bb) to point to iter_part_bb:
...
       redirect_edge_and_branch (single_succ_edge (trip_update_bb), iter_part_bb);
...

And fin_bb is an empty block without any phis, so during the redirect we don't
store any entries in the edge_var_map:
...
(gdb) call debug_bb (fin_bb)
;; basic block 18, loop depth 0, count 0, freq 0, maybe hot
;;  prev block 21, next block 16, flags: (NEW)
;;  pred:       21 [100.0%]  (FALLTHRU)
;;              19 (FALSE_VALUE)
;;  succ:       16 [100.0%]  (FALLTHRU)
...

Consequently, head will be NULL.
...
       vec<edge_var_map> *head = redirect_edge_var_map_vector (re);
...

And because head is NULL, this assert causes a segfault:
...
   gcc_assert (gsi_end_p (psi) && i == head->length ());
...

This patch fixes that, by handling the case that head is NULL in the assert.

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0002-Fix-gcc_assert-in-expand_omp_for_static_chunk.patch --]
[-- Type: text/x-patch, Size: 816 bytes --]

Fix gcc_assert in expand_omp_for_static_chunk

2015-04-15  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/65637
	* omp-low.c (expand_omp_for_static_chunk): Fix gcc_assert for the case
	that head is NULL.

---
 gcc/omp-low.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index 80bddf0..f7b9d11 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -7274,7 +7274,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	  locus = redirect_edge_var_map_location (vm);
 	  add_phi_arg (nphi, redirect_edge_var_map_def (vm), re, locus);
 	}
-      gcc_assert (gsi_end_p (psi) && i == head->length ());
+      gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
       redirect_edge_var_map_clear (re);
       while (1)
 	{
-- 
1.9.1

[PR65637][PATCH][3/5] Fix gcc_assert in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1401 bytes --]

[ Was: Re: [PR65637][PATCH][1/3] Fix gcc_assert in 
expand_omp_for_static_chunk ]

On 15/04/15 15:15, Tom de Vries wrote:
> On 15-04-15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>

<SNIP>

> This patch fixes a segfault in an gcc_assert in expand_omp_for_static_chunk
> while compiling autopar/pr46099.c.
>
> When compiling f1 from autopar/pr46099.c using
> expand_omp_for_static_chunk, we
> redirect the edge (trip_update_bb -> fin_bb) to point to iter_part_bb:
> ...
>        redirect_edge_and_branch (single_succ_edge (trip_update_bb),
> iter_part_bb);
> ...
>
> And fin_bb is an empty block without any phis, so during the redirect we
> don't
> store any entries in the edge_var_map:
> ...
> (gdb) call debug_bb (fin_bb)
> ;; basic block 18, loop depth 0, count 0, freq 0, maybe hot
> ;;  prev block 21, next block 16, flags: (NEW)
> ;;  pred:       21 [100.0%]  (FALLTHRU)
> ;;              19 (FALSE_VALUE)
> ;;  succ:       16 [100.0%]  (FALLTHRU)
> ...
>
> Consequently, head will be NULL.
> ...
>        vec<edge_var_map> *head = redirect_edge_var_map_vector (re);
> ...
>
> And because head is NULL, this assert causes a segfault:
> ...
>    gcc_assert (gsi_end_p (psi) && i == head->length ());
> ...
>
> This patch fixes that, by handling the case that head is NULL in the
> assert.
>

This updated patch includes a test-case.

OK for trunk?

Thanks,
- Tom


[-- Attachment #2: 0003-Fix-gcc_assert-in-expand_omp_for_static_chunk.patch --]
[-- Type: text/x-patch, Size: 2499 bytes --]

Fix gcc_assert in expand_omp_for_static_chunk

2015-08-31  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/65637
	* omp-low.c (expand_omp_for_static_chunk): Fix gcc_assert for the case
	that head is NULL.

	* gcc.dg/autopar/pr46099-chunk-size.c: New test.
---
 gcc/ChangeLog                                     |  6 +++
 gcc/omp-low.c                                     |  2 +-
 gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c | 47 +++++++++++++++++++++++
 3 files changed, 54 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a0123b1..5a273ba 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2015-05-18  Tom de Vries  <tom@codesourcery.com>
+
+	PR tree-optimization/65637
+	* omp-low.c (expand_omp_for_static_chunk): Fix gcc_assert for the case
+	that head is NULL.
+
 2015-08-31  Tom de Vries  <tom@codesourcery.com>
 
 	* tree-ssa-loop-manip.c (find_uses_to_rename_use)
diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index c3dfc51..4e732ae 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -7326,7 +7326,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	  locus = redirect_edge_var_map_location (vm);
 	  add_phi_arg (nphi, redirect_edge_var_map_def (vm), re, locus);
 	}
-      gcc_assert (gsi_end_p (psi) && i == head->length ());
+      gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
       redirect_edge_var_map_clear (re);
       while (1)
 	{
diff --git a/gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c b/gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c
new file mode 100644
index 0000000..709841a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c
@@ -0,0 +1,47 @@
+/* PR tree-optimization/46099.  */
+/* { dg-do compile } */
+/* { dg-options "-ftree-parallelize-loops=2 -fcompare-debug -O --param parloops-chunk-size=100" } */
+
+static inline void
+bar (int *i)
+{
+  int j = *i;
+}
+
+void baz (int *, int *, int *);
+
+void
+f1 (int n)
+{
+  int i;
+  for (i = 0; i < n; i++)
+    bar (&i);
+}
+
+void
+f2 (int n)
+{
+  int i;
+  int a[10000], b[10000], c[10000];
+  baz (a, b, c);
+  for (i = 0; i < n; i++)
+    {
+      void *p = c;
+      a[i] = b[i] + c[i];
+    }
+  baz (a, b, c);
+}
+
+void
+f3 (int n)
+{
+  int i;
+  int a[10000], b[10000], c[10000];
+  baz (a, b, c);
+  for (i = 0; i < n; i++)
+    {
+      a[i] = b[i] + c[i];
+      void *p = c;
+    }
+  baz (a, b, c);
+}
-- 
1.9.1

Re: [PR65637][PATCH][3/5] Fix gcc_assert in expand_omp_for_static_chunk

[Jakub Jelinek]

On Mon, Aug 31, 2015 at 01:55:40PM +0200, Tom de Vries wrote:
> Fix gcc_assert in expand_omp_for_static_chunk
> 
> 2015-08-31  Tom de Vries  <tom@codesourcery.com>
> 
> 	PR tree-optimization/65637
> 	* omp-low.c (expand_omp_for_static_chunk): Fix gcc_assert for the case
> 	that head is NULL.
> 
> 	* gcc.dg/autopar/pr46099-chunk-size.c: New test.
> ---
>  gcc/ChangeLog                                     |  6 +++
>  gcc/omp-low.c                                     |  2 +-
>  gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c | 47 +++++++++++++++++++++++
>  3 files changed, 54 insertions(+), 1 deletion(-)
>  create mode 100644 gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c
> 
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index a0123b1..5a273ba 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2015-05-18  Tom de Vries  <tom@codesourcery.com>
> +
> +	PR tree-optimization/65637
> +	* omp-low.c (expand_omp_for_static_chunk): Fix gcc_assert for the case
> +	that head is NULL.
> +
>  2015-08-31  Tom de Vries  <tom@codesourcery.com>
>  
>  	* tree-ssa-loop-manip.c (find_uses_to_rename_use)
> diff --git a/gcc/omp-low.c b/gcc/omp-low.c
> index c3dfc51..4e732ae 100644
> --- a/gcc/omp-low.c
> +++ b/gcc/omp-low.c
> @@ -7326,7 +7326,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
>  	  locus = redirect_edge_var_map_location (vm);
>  	  add_phi_arg (nphi, redirect_edge_var_map_def (vm), re, locus);
>  	}
> -      gcc_assert (gsi_end_p (psi) && i == head->length ());
> +      gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
>        redirect_edge_var_map_clear (re);
>        while (1)
>  	{

Ok.

> diff --git a/gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c b/gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c
> new file mode 100644
> index 0000000..709841a
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/autopar/pr46099-chunk-size.c

I'd name the testcase just pr46099-2.c.

> @@ -0,0 +1,47 @@
> +/* PR tree-optimization/46099.  */
> +/* { dg-do compile } */
> +/* { dg-options "-ftree-parallelize-loops=2 -fcompare-debug -O --param parloops-chunk-size=100" } */

But more importantly, if you haven't changed anything in the testcase
beyond dg-options, just
#include "pr46099.c"
here rather than duplicating the whole testcase.  Ok with that change.

	Jakub

[PR65637][PATCH][2/3] Fix inner loop phi in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1622 bytes --]

On 15-04-15 15:10, Tom de Vries wrote:
> Hi,
>
> This patch series fixes PR65637.
>
> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and not
> exercised by testing.
>
> Ssa-handling code in omp-low.c is only triggered by pass_parallelize_loops, and
> that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it constructs, so
> that only exercises the expand_omp_for_static_nochunk path.
>
> Using the attached trigger patch, we excercise the ssa-handling code in
> expand_omp_for_static_chunk. The following patch series fixes the problems in
> the ssa-handling code that we encounter.
>
> 1. Fix gcc_assert in expand_omp_for_static_chunk
> 2. Fix inner loop phi in expand_omp_for_static_chunk
> 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> The patch series has been bootstrapped and reg-tested on x86_64 together with
> attached trigger patch.
>
> I'll post the patches from the patch series individually, in response to this
> email.
>

This patch fixes an libgomp.c/autopar-1.c execution failure.

For autopar-1.c, the original loop has a loop phi:
...
# s.5_20 = PHI <s.5_12(4), 0.0(20)>
...

After expand_omp_for_static_chunk, there's an inner and an outer loop. The outer
loop phi is:
...
# s.5_11 = PHI <0.0(15), s.5_12(21)>
...

and the inner loop phi is:
...
# s.5_20 = PHI <s.5_12(4), 0.0(20)>
...

The inner loop phi should not have 0.0 as argument, but the result of the outer
loop phi, like this:
...
# s.5_20 = PHI <s.5_12(4), s.5_11(20)>
...

This patch fixes the inner loop phi, and allows the autopar-1.c execution test
to pass.

OK for trunk?

Thanks,
- Tom


[-- Attachment #2: 0003-Fix-inner-loop-phi-in-expand_omp_for_static_chunk.patch --]
[-- Type: text/x-patch, Size: 1747 bytes --]

Fix inner loop phi in expand_omp_for_static_chunk

2015-04-15  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/65637
	* omp-low.c (find_phi_with_arg_on_edge): New function.
	(expand_omp_for_static_chunk): Fix inner loop phi.

---
 gcc/omp-low.c | 25 ++++++++++++++++++++++++-
 1 file changed, 24 insertions(+), 1 deletion(-)

diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index f7b9d11..62cbed0 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -6844,6 +6844,22 @@ expand_omp_for_static_nochunk (struct omp_region *region,
     }
 }
 
+static gphi *
+find_phi_with_arg_on_edge (tree arg, edge e)
+{
+  basic_block bb = e->dest;
+
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi);
+       gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      if (PHI_ARG_DEF_FROM_EDGE (phi, e) == arg)
+	return phi;
+    }
+
+  return NULL;
+}
 
 /* A subroutine of expand_omp_for.  Generate code for a parallel
    loop with static schedule and a specified chunk size.  Given
@@ -7272,7 +7288,14 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	    t = vextra;
 	  add_phi_arg (nphi, t, ene, locus);
 	  locus = redirect_edge_var_map_location (vm);
-	  add_phi_arg (nphi, redirect_edge_var_map_def (vm), re, locus);
+	  tree back_arg = redirect_edge_var_map_def (vm);
+	  add_phi_arg (nphi, back_arg, re, locus);
+	  gphi *inner_loop_phi
+	    = find_phi_with_arg_on_edge (back_arg,
+					 find_edge (cont_bb, body_bb));
+	  gcc_assert (inner_loop_phi != NULL);
+	  add_phi_arg (inner_loop_phi, gimple_phi_result (nphi),
+		       find_edge (seq_start_bb, body_bb), locus);
 	}
       gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
       redirect_edge_var_map_clear (re);
-- 
1.9.1

[PR65637][PATCH][4/5] Fix inner loop phi in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 995 bytes --]

[ was: Re: [PR65637][PATCH][2/3] Fix inner loop phi in 
expand_omp_for_static_chunk ]

On 15/04/15 15:17, Tom de Vries wrote:
> On 15-04-15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>

<SNIP>

>
> This patch fixes an libgomp.c/autopar-1.c execution failure.
>
> For autopar-1.c, the original loop has a loop phi:
> ...
> # s.5_20 = PHI <s.5_12(4), 0.0(20)>
> ...
>
> After expand_omp_for_static_chunk, there's an inner and an outer loop.
> The outer
> loop phi is:
> ...
> # s.5_11 = PHI <0.0(15), s.5_12(21)>
> ...
>
> and the inner loop phi is:
> ...
> # s.5_20 = PHI <s.5_12(4), 0.0(20)>
> ...
>
> The inner loop phi should not have 0.0 as argument, but the result of
> the outer
> loop phi, like this:
> ...
> # s.5_20 = PHI <s.5_12(4), s.5_11(20)>
> ...
>
> This patch fixes the inner loop phi, and allows the autopar-1.c
> execution test
> to pass.
>

This updated patch includes a test-case. It also handles simple latches.

OK for trunk?

Thanks,
- Tom



[-- Attachment #2: 0004-Fix-inner-loop-phi-in-expand_omp_for_static_chunk.patch --]
[-- Type: text/x-patch, Size: 3725 bytes --]

Fix inner loop phi in expand_omp_for_static_chunk

2015-08-31  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/65637
	* omp-low.c (find_phi_with_arg_on_edge): New function.
	(expand_omp_for_static_chunk): Fix inner loop phi.

	* testsuite/libgomp.c/autopar-1-chunk-size.c: New test.
---
 gcc/ChangeLog                                      |  6 +++
 gcc/omp-low.c                                      | 30 ++++++++++++++-
 libgomp/testsuite/libgomp.c/autopar-1-chunk-size.c | 44 ++++++++++++++++++++++
 3 files changed, 79 insertions(+), 1 deletion(-)
 create mode 100644 libgomp/testsuite/libgomp.c/autopar-1-chunk-size.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 5a273ba..a14564c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,6 +1,12 @@
 2015-05-18  Tom de Vries  <tom@codesourcery.com>
 
 	PR tree-optimization/65637
+	* omp-low.c (find_phi_with_arg_on_edge): New function.
+	(expand_omp_for_static_chunk): Fix inner loop phi.
+
+2015-05-18  Tom de Vries  <tom@codesourcery.com>
+
+	PR tree-optimization/65637
 	* omp-low.c (expand_omp_for_static_chunk): Fix gcc_assert for the case
 	that head is NULL.
 
diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index 4e732ae..e2be7c7 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -6885,6 +6885,22 @@ expand_omp_for_static_nochunk (struct omp_region *region,
     }
 }
 
+static gphi *
+find_phi_with_arg_on_edge (tree arg, edge e)
+{
+  basic_block bb = e->dest;
+
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi);
+       gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      if (PHI_ARG_DEF_FROM_EDGE (phi, e) == arg)
+	return phi;
+    }
+
+  return NULL;
+}
 
 /* A subroutine of expand_omp_for.  Generate code for a parallel
    loop with static schedule and a specified chunk size.  Given
@@ -7324,7 +7340,19 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	    t = vextra;
 	  add_phi_arg (nphi, t, ene, locus);
 	  locus = redirect_edge_var_map_location (vm);
-	  add_phi_arg (nphi, redirect_edge_var_map_def (vm), re, locus);
+	  tree back_arg = redirect_edge_var_map_def (vm);
+	  add_phi_arg (nphi, back_arg, re, locus);
+	  edge ce = find_edge (cont_bb, body_bb);
+	  if (ce == NULL)
+	    {
+	      ce = BRANCH_EDGE (cont_bb);
+	      gcc_assert (single_succ (ce->dest) == body_bb);
+	      ce = single_succ_edge (ce->dest);
+	    }
+	  gphi *inner_loop_phi = find_phi_with_arg_on_edge (back_arg, ce);
+	  gcc_assert (inner_loop_phi != NULL);
+	  add_phi_arg (inner_loop_phi, gimple_phi_result (nphi),
+		       find_edge (seq_start_bb, body_bb), locus);
 	}
       gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
       redirect_edge_var_map_clear (re);
diff --git a/libgomp/testsuite/libgomp.c/autopar-1-chunk-size.c b/libgomp/testsuite/libgomp.c/autopar-1-chunk-size.c
new file mode 100644
index 0000000..5a36474
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/autopar-1-chunk-size.c
@@ -0,0 +1,44 @@
+/* { dg-do run } */
+/* { dg-additional-options "-ftree-parallelize-loops=4 -ffast-math --param parloops-chunk-size=100" } */
+
+extern void abort (void);
+
+double d[1024], e[1024];
+int f[1024], g[1024];
+
+double __attribute__((noinline))
+foo (void)
+{
+  double s = 0.0;
+  int i;
+  for (i = 0; i < 1024; i++)
+    s += d[i] - e[i];
+  return s;
+}
+
+int __attribute__((noinline))
+bar (void)
+{
+  int s = 0, i;
+  for (i = 0; i < 1024; i++)
+    s += f[i] - g[i];
+  return s;
+}
+
+int
+main (void)
+{
+  int i;
+  for (i = 0; i < 1024; i++)
+    {
+      d[i] = i * 2;
+      e[i] = i;
+      f[i] = i * 2;
+      g[i] = i;
+    }
+  if (foo () != 1023 * 1024 / 2)
+    abort ();
+  if (bar () != 1023 * 1024 / 2)
+    abort ();
+  return 0;
+}
-- 
1.9.1

Re: [PR65637][PATCH][4/5] Fix inner loop phi in expand_omp_for_static_chunk

[Jakub Jelinek]

On Mon, Aug 31, 2015 at 02:00:10PM +0200, Tom de Vries wrote:
> --- a/gcc/omp-low.c
> +++ b/gcc/omp-low.c
> @@ -6885,6 +6885,22 @@ expand_omp_for_static_nochunk (struct omp_region *region,
>      }
>  }
>  

Please add a function comment.

> +static gphi *
> +find_phi_with_arg_on_edge (tree arg, edge e)
> +{
> +  basic_block bb = e->dest;
> +
> +  for (gphi_iterator gpi = gsi_start_phis (bb);
> +       !gsi_end_p (gpi);
> +       gsi_next (&gpi))
> +    {
> +      gphi *phi = gpi.phi ();
> +      if (PHI_ARG_DEF_FROM_EDGE (phi, e) == arg)
> +	return phi;
> +    }
> +
> +  return NULL;
> +}

> --- /dev/null
> +++ b/libgomp/testsuite/libgomp.c/autopar-1-chunk-size.c
> @@ -0,0 +1,44 @@
> +/* { dg-do run } */
> +/* { dg-additional-options "-ftree-parallelize-loops=4 -ffast-math --param parloops-chunk-size=100" } */

Similarly to previous patch, just use autopar-2.c as filename
and #include "autopar-1.c" rather than duplicating it.

Ok with those changes.

	Jakub

[PR65637][PATCH][3/3] Handle 2 preds for fin_bb in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 5409 bytes --]

On 15-04-15 15:10, Tom de Vries wrote:
> Hi,
>
> This patch series fixes PR65637.
>
> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and not
> exercised by testing.
>
> Ssa-handling code in omp-low.c is only triggered by pass_parallelize_loops, and
> that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it constructs, so
> that only exercises the expand_omp_for_static_nochunk path.
>
> Using the attached trigger patch, we excercise the ssa-handling code in
> expand_omp_for_static_chunk. The following patch series fixes the problems in
> the ssa-handling code that we encounter.
>
> 1. Fix gcc_assert in expand_omp_for_static_chunk
> 2. Fix inner loop phi in expand_omp_for_static_chunk
> 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> The patch series has been bootstrapped and reg-tested on x86_64 together with
> attached trigger patch.
>
> I'll post the patches from the patch series individually, in response to this
> email.
>

This patch fixes compilation of autopar/reduc-3.c in
expand_omp_for_static_chunk.

We encounter two situations in expand_omp_for_static_chunk:
1. single_pred_p (fin_bb)
    This situation happens for f.i. autopar-1.c, which uses a compile-time
    constant loop bound.
2. !single_pred_p (fin_bb)
    This situation happens for autopar/reduc-3.c, which uses a compile-time
    unknown loop bound.

The two situations are represented as control flow graphs here:
...
1.
   x
   |
   |
   *
entry_bb
   |
   |
   *
iter_part_bb --* seq_start_bb
   |        *         |
   |         \       ...
   *          \       |
fin_bb        \      *
   |            -- trip_update_bb
   |
   *
   x

2.
   x
   |
   |
   *
region.entry --* entry_bb
   |                |
   |                |
   *                *
fin_bb   *--   iter_part_bb --* seq_start_bb
   |                       *        |
   |                        \      ...
   *                         \      |
   x                          \     *
			      -- trip_update_bb
...

This patch handles the !single_pred_p (fin_bb) scenario, while keeping the
single_pred_p (fin_bb) scenario undisturbed.

With the patch, the resulting split-off function looks like this:
...
main1._loopfn.0 (voidD.41 * .paral_data_paramD.2498)
{
;;   basic block 2, loop depth 0, count 0, freq 79, maybe hot
;;    prev block 0, next block 3, flags: (NEW, REACHABLE)
;;    pred:       ENTRY (FALLTHRU)
   .paral_data_param_2 = .paral_data_param_1(D);
   .paral_data_load.12_3 = (struct  *) .paral_data_param_2;
   # VUSE <.MEM_33(D)>
   _4 = .paral_data_load.12_3->D.2490;
   # VUSE <.MEM_33(D)>
   ub_5 = .paral_data_load.12_3->ubD.2491;
   # VUSE <.MEM_33(D)>
   uc_6 = .paral_data_load.12_3->ucD.2492;
   if (0 < _4)
     goto <bb 4>;
   else
     goto <bb 3>;
;;    succ:       4 [100.0%]  (TRUE_VALUE)
;;                3 [0.0%]  (FALSE_VALUE)

;;   basic block 3, loop depth 0, count 0, freq 0, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE)
;;    pred:       2 [0.0%]  (FALSE_VALUE)
;;                5 (FALSE_VALUE)
   # udiff.8_7 = PHI <0(2), udiff.8_8(5)>
   _9 = &.paral_data_load.12_3->udiff.8D.2493;
   # .MEM_34 = VDEF <.MEM_33(D)>
   # USE = anything
   # CLB = anything
   __atomic_fetch_add_4D.1247 (_9, udiff.8_7, 0);
   # VUSE <.MEM_34>
   return;
;;    succ:       EXIT

;;   basic block 4, loop depth 0, count 0, freq 79, maybe hot
;;    prev block 3, next block 5, flags: (NEW, REACHABLE)
;;    pred:       2 [100.0%]  (TRUE_VALUE)
   _10 = omp_get_num_threadsD.1287 ();
   _11 = (unsigned int) _10;
   _12 = omp_get_thread_numD.1286 ();
   _13 = (unsigned int) _12;
   .trip.13_14 = 0;
;;    succ:       5 [100.0%]  (FALLTHRU)

;;   basic block 5, loop depth 1, count 0, freq 79, maybe hot
;;    prev block 4, next block 6, flags: (NEW, REACHABLE)
;;    pred:       4 [100.0%]  (FALLTHRU)
;;                8 [100.0%]  (FALLTHRU)
   # udiff.8_8 = PHI <0(4), udiff.8_15(8)>
   # .trip.13_16 = PHI <.trip.13_14(4), .trip.13_17(8)>
   _18 = _11 * .trip.13_16;
   _19 = _13 + _18;
   _20 = _19 + 1;
   _21 = MIN_EXPR <_4, _20>;
   if (_19 < _4)
     goto <bb 6>;
   else
     goto <bb 3>;
;;    succ:       6 [100.0%]  (TRUE_VALUE)
;;                3 (FALSE_VALUE)

;;   basic block 6, loop depth 1, count 0, freq 79, maybe hot
;;    prev block 5, next block 7, flags: (NEW, REACHABLE)
;;    pred:       5 [100.0%]  (TRUE_VALUE)
   ivtmp_22 = _19;
;;    succ:       7 [100.0%]  (FALLTHRU)

;;   basic block 7, loop depth 2, count 0, freq 7920, maybe hot
;;    prev block 6, next block 8, flags: (NEW, REACHABLE)
;;    pred:       6 [100.0%]  (FALLTHRU)
;;                7 [100.0%]  (TRUE_VALUE)
   # udiff.8_23 = PHI <udiff.8_8(6), udiff.8_15(7)>
   # ivtmp_24 = PHI <ivtmp_22(6), ivtmp_25(7)>
   i.9_28 = (intD.6) ivtmp_24;
   # VUSE <.MEM_33(D)>
   _29 = *ub_5[i.9_28];
   # VUSE <.MEM_33(D)>
   _30 = *uc_6[i.9_28];
   _31 = _29 - _30;
   udiff.8_15 = udiff.8_23 + _31;
   i.9_32 = i.9_28 + 1;
   ivtmp_25 = ivtmp_24 + 1;
   if (ivtmp_25 < _21)
     goto <bb 7>;
   else
     goto <bb 8>;
;;    succ:       7 [100.0%]  (TRUE_VALUE)
;;                8 (FALSE_VALUE)

;;   basic block 8, loop depth 1, count 0, freq 0, maybe hot
;;    prev block 7, next block 1, flags: (NEW, REACHABLE)
;;    pred:       7 (FALSE_VALUE)
   .trip.13_17 = .trip.13_16 + 1;
   goto <bb 5>;
;;    succ:       5 [100.0%]  (FALLTHRU)

}
...

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0004-Handle-2-preds-for-fin_bb-in-expand_omp_for_static_c.patch --]
[-- Type: text/x-patch, Size: 2577 bytes --]

Handle 2 preds for fin_bb in expand_omp_for_static_chunk

2015-04-15  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/65637
	* omp-low.c (expand_omp_for_static_chunk): Handle case that fin_bb has 2
	predecessors.

---
 gcc/omp-low.c | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)

diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index 62cbed0..6d7d82d 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -6991,7 +6991,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
       se->probability = REG_BR_PROB_BASE / 2000 - 1;
       if (gimple_in_ssa_p (cfun))
 	{
-	  int dest_idx = find_edge (entry_bb, fin_bb)->dest_idx;
+	  int dest_idx = find_edge (iter_part_bb, fin_bb)->dest_idx;
 	  for (gphi_iterator gpi = gsi_start_phis (fin_bb);
 	       !gsi_end_p (gpi); gsi_next (&gpi))
 	    {
@@ -7262,7 +7262,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
       /* When we redirect the edge from trip_update_bb to iter_part_bb, we
 	 remove arguments of the phi nodes in fin_bb.  We need to create
 	 appropriate phi nodes in iter_part_bb instead.  */
-      se = single_pred_edge (fin_bb);
+      se = find_edge (iter_part_bb, fin_bb);
       re = single_succ_edge (trip_update_bb);
       vec<edge_var_map> *head = redirect_edge_var_map_vector (re);
       ene = single_succ_edge (entry_bb);
@@ -7277,6 +7277,10 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	  phi = psi.phi ();
 	  t = gimple_phi_result (phi);
 	  gcc_assert (t == redirect_edge_var_map_result (vm));
+
+	  if (!single_pred_p (fin_bb))
+	    t = copy_ssa_name (t, phi);
+
 	  nphi = create_phi_node (t, iter_part_bb);
 
 	  t = PHI_ARG_DEF_FROM_EDGE (phi, se);
@@ -7296,16 +7300,20 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	  gcc_assert (inner_loop_phi != NULL);
 	  add_phi_arg (inner_loop_phi, gimple_phi_result (nphi),
 		       find_edge (seq_start_bb, body_bb), locus);
+
+	  if (!single_pred_p (fin_bb))
+	    add_phi_arg (phi, gimple_phi_result (nphi), se, locus);
 	}
       gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
       redirect_edge_var_map_clear (re);
-      while (1)
-	{
-	  psi = gsi_start_phis (fin_bb);
-	  if (gsi_end_p (psi))
-	    break;
-	  remove_phi_node (&psi, false);
-	}
+      if (single_pred_p (fin_bb))
+	while (1)
+	  {
+	    psi = gsi_start_phis (fin_bb);
+	    if (gsi_end_p (psi))
+	      break;
+	    remove_phi_node (&psi, false);
+	  }
 
       /* Make phi node for trip.  */
       phi = create_phi_node (trip_main, iter_part_bb);
-- 
1.9.1

[PR65637][PATCH][5/5] Handle 2 preds for fin_bb in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 5004 bytes --]

[ was: Re: [PR65637][PATCH][3/3] Handle 2 preds for fin_bb in 
expand_omp_for_static_chunk ]

On 15/04/15 15:23, Tom de Vries wrote:
> On 15-04-15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>

<SNIP>

> This patch fixes compilation of autopar/reduc-3.c in
> expand_omp_for_static_chunk.
>
> We encounter two situations in expand_omp_for_static_chunk:
> 1. single_pred_p (fin_bb)
>     This situation happens for f.i. autopar-1.c, which uses a compile-time
>     constant loop bound.
> 2. !single_pred_p (fin_bb)
>     This situation happens for autopar/reduc-3.c, which uses a compile-time
>     unknown loop bound.
>
> The two situations are represented as control flow graphs here:
> ...
> 1.
>    x
>    |
>    |
>    *
> entry_bb
>    |
>    |
>    *
> iter_part_bb --* seq_start_bb
>    |        *         |
>    |         \       ...
>    *          \       |
> fin_bb        \      *
>    |            -- trip_update_bb
>    |
>    *
>    x
>
> 2.
>    x
>    |
>    |
>    *
> region.entry --* entry_bb
>    |                |
>    |                |
>    *                *
> fin_bb   *--   iter_part_bb --* seq_start_bb
>    |                       *        |
>    |                        \      ...
>    *                         \      |
>    x                          \     *
>                    -- trip_update_bb
> ...
>
> This patch handles the !single_pred_p (fin_bb) scenario, while keeping the
> single_pred_p (fin_bb) scenario undisturbed.
>
> With the patch, the resulting split-off function looks like this:
> ...
> main1._loopfn.0 (voidD.41 * .paral_data_paramD.2498)
> {
> ;;   basic block 2, loop depth 0, count 0, freq 79, maybe hot
> ;;    prev block 0, next block 3, flags: (NEW, REACHABLE)
> ;;    pred:       ENTRY (FALLTHRU)
>    .paral_data_param_2 = .paral_data_param_1(D);
>    .paral_data_load.12_3 = (struct  *) .paral_data_param_2;
>    # VUSE <.MEM_33(D)>
>    _4 = .paral_data_load.12_3->D.2490;
>    # VUSE <.MEM_33(D)>
>    ub_5 = .paral_data_load.12_3->ubD.2491;
>    # VUSE <.MEM_33(D)>
>    uc_6 = .paral_data_load.12_3->ucD.2492;
>    if (0 < _4)
>      goto <bb 4>;
>    else
>      goto <bb 3>;
> ;;    succ:       4 [100.0%]  (TRUE_VALUE)
> ;;                3 [0.0%]  (FALSE_VALUE)
>
> ;;   basic block 3, loop depth 0, count 0, freq 0, maybe hot
> ;;    prev block 2, next block 4, flags: (NEW, REACHABLE)
> ;;    pred:       2 [0.0%]  (FALSE_VALUE)
> ;;                5 (FALSE_VALUE)
>    # udiff.8_7 = PHI <0(2), udiff.8_8(5)>
>    _9 = &.paral_data_load.12_3->udiff.8D.2493;
>    # .MEM_34 = VDEF <.MEM_33(D)>
>    # USE = anything
>    # CLB = anything
>    __atomic_fetch_add_4D.1247 (_9, udiff.8_7, 0);
>    # VUSE <.MEM_34>
>    return;
> ;;    succ:       EXIT
>
> ;;   basic block 4, loop depth 0, count 0, freq 79, maybe hot
> ;;    prev block 3, next block 5, flags: (NEW, REACHABLE)
> ;;    pred:       2 [100.0%]  (TRUE_VALUE)
>    _10 = omp_get_num_threadsD.1287 ();
>    _11 = (unsigned int) _10;
>    _12 = omp_get_thread_numD.1286 ();
>    _13 = (unsigned int) _12;
>    .trip.13_14 = 0;
> ;;    succ:       5 [100.0%]  (FALLTHRU)
>
> ;;   basic block 5, loop depth 1, count 0, freq 79, maybe hot
> ;;    prev block 4, next block 6, flags: (NEW, REACHABLE)
> ;;    pred:       4 [100.0%]  (FALLTHRU)
> ;;                8 [100.0%]  (FALLTHRU)
>    # udiff.8_8 = PHI <0(4), udiff.8_15(8)>
>    # .trip.13_16 = PHI <.trip.13_14(4), .trip.13_17(8)>
>    _18 = _11 * .trip.13_16;
>    _19 = _13 + _18;
>    _20 = _19 + 1;
>    _21 = MIN_EXPR <_4, _20>;
>    if (_19 < _4)
>      goto <bb 6>;
>    else
>      goto <bb 3>;
> ;;    succ:       6 [100.0%]  (TRUE_VALUE)
> ;;                3 (FALSE_VALUE)
>
> ;;   basic block 6, loop depth 1, count 0, freq 79, maybe hot
> ;;    prev block 5, next block 7, flags: (NEW, REACHABLE)
> ;;    pred:       5 [100.0%]  (TRUE_VALUE)
>    ivtmp_22 = _19;
> ;;    succ:       7 [100.0%]  (FALLTHRU)
>
> ;;   basic block 7, loop depth 2, count 0, freq 7920, maybe hot
> ;;    prev block 6, next block 8, flags: (NEW, REACHABLE)
> ;;    pred:       6 [100.0%]  (FALLTHRU)
> ;;                7 [100.0%]  (TRUE_VALUE)
>    # udiff.8_23 = PHI <udiff.8_8(6), udiff.8_15(7)>
>    # ivtmp_24 = PHI <ivtmp_22(6), ivtmp_25(7)>
>    i.9_28 = (intD.6) ivtmp_24;
>    # VUSE <.MEM_33(D)>
>    _29 = *ub_5[i.9_28];
>    # VUSE <.MEM_33(D)>
>    _30 = *uc_6[i.9_28];
>    _31 = _29 - _30;
>    udiff.8_15 = udiff.8_23 + _31;
>    i.9_32 = i.9_28 + 1;
>    ivtmp_25 = ivtmp_24 + 1;
>    if (ivtmp_25 < _21)
>      goto <bb 7>;
>    else
>      goto <bb 8>;
> ;;    succ:       7 [100.0%]  (TRUE_VALUE)
> ;;                8 (FALSE_VALUE)
>
> ;;   basic block 8, loop depth 1, count 0, freq 0, maybe hot
> ;;    prev block 7, next block 1, flags: (NEW, REACHABLE)
> ;;    pred:       7 (FALSE_VALUE)
>    .trip.13_17 = .trip.13_16 + 1;
>    goto <bb 5>;
> ;;    succ:       5 [100.0%]  (FALLTHRU)
>
> }
> ...
>

OK for trunk?

This updated patch includes a test-case.

Thanks,
- Tom


[-- Attachment #2: 0005-Handle-2-preds-for-fin_bb-in-expand_omp_for_static_c.patch --]
[-- Type: text/x-patch, Size: 4593 bytes --]

Handle 2 preds for fin_bb in expand_omp_for_static_chunk

2015-08-31  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/65637
	* omp-low.c (expand_omp_for_static_chunk): Handle case that fin_bb has 2
	predecessors.

	* gcc.dg/autopar/reduc-3-chunk-size.c: New test.
---
 gcc/ChangeLog                                     |  6 +++
 gcc/omp-low.c                                     | 26 +++++++----
 gcc/testsuite/gcc.dg/autopar/reduc-3-chunk-size.c | 56 +++++++++++++++++++++++
 3 files changed, 79 insertions(+), 9 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/autopar/reduc-3-chunk-size.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a14564c..c9e426f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,6 +1,12 @@
 2015-05-18  Tom de Vries  <tom@codesourcery.com>
 
 	PR tree-optimization/65637
+	* omp-low.c (expand_omp_for_static_chunk): Handle case that fin_bb has 2
+	predecessors.
+
+2015-05-18  Tom de Vries  <tom@codesourcery.com>
+
+	PR tree-optimization/65637
 	* omp-low.c (find_phi_with_arg_on_edge): New function.
 	(expand_omp_for_static_chunk): Fix inner loop phi.
 
diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index e2be7c7..f3257ac 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -7033,7 +7033,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
       se->probability = REG_BR_PROB_BASE / 2000 - 1;
       if (gimple_in_ssa_p (cfun))
 	{
-	  int dest_idx = find_edge (entry_bb, fin_bb)->dest_idx;
+	  int dest_idx = find_edge (iter_part_bb, fin_bb)->dest_idx;
 	  for (gphi_iterator gpi = gsi_start_phis (fin_bb);
 	       !gsi_end_p (gpi); gsi_next (&gpi))
 	    {
@@ -7314,7 +7314,7 @@ expand_omp_for_static_chunk (struct omp_region *region,
       /* When we redirect the edge from trip_update_bb to iter_part_bb, we
 	 remove arguments of the phi nodes in fin_bb.  We need to create
 	 appropriate phi nodes in iter_part_bb instead.  */
-      se = single_pred_edge (fin_bb);
+      se = find_edge (iter_part_bb, fin_bb);
       re = single_succ_edge (trip_update_bb);
       vec<edge_var_map> *head = redirect_edge_var_map_vector (re);
       ene = single_succ_edge (entry_bb);
@@ -7329,6 +7329,10 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	  phi = psi.phi ();
 	  t = gimple_phi_result (phi);
 	  gcc_assert (t == redirect_edge_var_map_result (vm));
+
+	  if (!single_pred_p (fin_bb))
+	    t = copy_ssa_name (t, phi);
+
 	  nphi = create_phi_node (t, iter_part_bb);
 
 	  t = PHI_ARG_DEF_FROM_EDGE (phi, se);
@@ -7353,16 +7357,20 @@ expand_omp_for_static_chunk (struct omp_region *region,
 	  gcc_assert (inner_loop_phi != NULL);
 	  add_phi_arg (inner_loop_phi, gimple_phi_result (nphi),
 		       find_edge (seq_start_bb, body_bb), locus);
+
+	  if (!single_pred_p (fin_bb))
+	    add_phi_arg (phi, gimple_phi_result (nphi), se, locus);
 	}
       gcc_assert (gsi_end_p (psi) && (head == NULL || i == head->length ()));
       redirect_edge_var_map_clear (re);
-      while (1)
-	{
-	  psi = gsi_start_phis (fin_bb);
-	  if (gsi_end_p (psi))
-	    break;
-	  remove_phi_node (&psi, false);
-	}
+      if (single_pred_p (fin_bb))
+	while (1)
+	  {
+	    psi = gsi_start_phis (fin_bb);
+	    if (gsi_end_p (psi))
+	      break;
+	    remove_phi_node (&psi, false);
+	  }
 
       /* Make phi node for trip.  */
       phi = create_phi_node (trip_main, iter_part_bb);
diff --git a/gcc/testsuite/gcc.dg/autopar/reduc-3-chunk-size.c b/gcc/testsuite/gcc.dg/autopar/reduc-3-chunk-size.c
new file mode 100644
index 0000000..ca4ab2f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/reduc-3-chunk-size.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-parallelize-loops=4 -fdump-tree-parloops-details -fdump-tree-optimized --param parloops-chunk-size=100" } */
+
+#include <stdarg.h>
+#include <stdlib.h>
+
+#define N 1600
+
+unsigned int ub[N];
+unsigned int uc[N];
+
+/* Reduction of unsigned-int.  */
+
+int __attribute__ ((noinline))
+main1 (int n, int res)
+{
+  int i;
+  unsigned int udiff;
+
+  udiff = 0;
+  for (i = 0; i < n; i++) {
+    udiff += (ub[i] - uc[i]);
+  }
+
+  /* check results:  */
+  if (udiff != res)
+    abort ();
+
+  return 0;
+}
+
+void __attribute__((noinline))
+init_arrays ()
+{
+  int i;
+
+  for (i = 0; i < N; i++)
+    {
+      ub[i] = i * 3;
+      uc[i] = i;
+    }
+}
+
+int
+main (void)
+{
+  init_arrays ();
+  main1 (N, 2558400);
+  main1 (N-1, 2555202);
+  return 0;
+}
+
+
+/* { dg-final { scan-tree-dump-times "Detected reduction" 1 "parloops" } } */
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 2 "parloops" } } */
+
-- 
1.9.1

Re: [PR65637][PATCH][5/5] Handle 2 preds for fin_bb in expand_omp_for_static_chunk

[Jakub Jelinek]

On Mon, Aug 31, 2015 at 02:02:57PM +0200, Tom de Vries wrote:
> 2015-08-31  Tom de Vries  <tom@codesourcery.com>
> 
> 	PR tree-optimization/65637
> 	* omp-low.c (expand_omp_for_static_chunk): Handle case that fin_bb has 2
> 	predecessors.

Ok.
> 
> 	* gcc.dg/autopar/reduc-3-chunk-size.c: New test.

But for the testcase similarly to previous patches, I'd call it
reduc-4.c and #include "reduc-3.c" instead of duplicating it.

	Jakub

[PING][PR65637] Fix ssa-handling code in expand_omp_for_static_chunk

[Tom de Vries]

On 15-04-15 15:10, Tom de Vries wrote:
> Hi,
>
> This patch series fixes PR65637.
>
> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and not
> exercised by testing.
>
> Ssa-handling code in omp-low.c is only triggered by pass_parallelize_loops, and
> that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it constructs, so
> that only exercises the expand_omp_for_static_nochunk path.
>
> Using the attached trigger patch, we excercise the ssa-handling code in
> expand_omp_for_static_chunk. The following patch series fixes the problems in
> the ssa-handling code that we encounter.
>
> 1. Fix gcc_assert in expand_omp_for_static_chunk
> 2. Fix inner loop phi in expand_omp_for_static_chunk
> 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> The patch series has been bootstrapped and reg-tested on x86_64 together with
> attached trigger patch.
>
> I'll post the patches from the patch series individually, in response to this
> email.
>

Ping for the three patches.

Thanks,
- Tom

> 0001-Set-chunk_size-to-one-for-parloops-parallel.patch
>
>
> Set chunk_size to one for parloops parallel
>
> ---
>   gcc/tree-parloops.c | 1 +
>   1 file changed, 1 insertion(+)
>
> diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
> index 62a6444..862c420 100644
> --- a/gcc/tree-parloops.c
> +++ b/gcc/tree-parloops.c
> @@ -1719,6 +1719,7 @@ create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
>     type = TREE_TYPE (cvar);
>     t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
>     OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
> +  OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t) = integer_one_node;
>
>     for_stmt = gimple_build_omp_for (NULL, GF_OMP_FOR_KIND_FOR, t, 1, NULL);
>     gimple_set_location (for_stmt, loc);
> -- 1.9.1
>

Re: [PING][PR65637] Fix ssa-handling code in expand_omp_for_static_chunk

[Tom de Vries]

On 18-05-15 14:53, Tom de Vries wrote:
> On 15-04-15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>
>> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and not
>> exercised by testing.
>>
>> Ssa-handling code in omp-low.c is only triggered by pass_parallelize_loops, and
>> that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it constructs, so
>> that only exercises the expand_omp_for_static_nochunk path.
>>
>> Using the attached trigger patch, we excercise the ssa-handling code in
>> expand_omp_for_static_chunk. The following patch series fixes the problems in
>> the ssa-handling code that we encounter.
>>
>> 1. Fix gcc_assert in expand_omp_for_static_chunk
>> 2. Fix inner loop phi in expand_omp_for_static_chunk
>> 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>>
>> The patch series has been bootstrapped and reg-tested on x86_64 together with
>> attached trigger patch.
>>
>> I'll post the patches from the patch series individually, in response to this
>> email.
>>
>
> Ping for the three patches.
>

Committed to gomp-4_0-branch.

> Thanks,
> - Tom
>
>> 0001-Set-chunk_size-to-one-for-parloops-parallel.patch
>>
>>
>> Set chunk_size to one for parloops parallel
>>
>> ---
>>   gcc/tree-parloops.c | 1 +
>>   1 file changed, 1 insertion(+)
>>
>> diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
>> index 62a6444..862c420 100644
>> --- a/gcc/tree-parloops.c
>> +++ b/gcc/tree-parloops.c
>> @@ -1719,6 +1719,7 @@ create_parallel_loop (struct loop *loop, tree loop_fn,
>> tree data,
>>     type = TREE_TYPE (cvar);
>>     t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
>>     OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
>> +  OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t) = integer_one_node;
>>
>>     for_stmt = gimple_build_omp_for (NULL, GF_OMP_FOR_KIND_FOR, t, 1, NULL);
>>     gimple_set_location (for_stmt, loc);
>> -- 1.9.1
>>
>

[PING^2][PR65637] Fix ssa-handling code in expand_omp_for_static_chunk

[Tom de Vries]

On 18/05/15 14:53, Tom de Vries wrote:
> On 15-04-15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>
>> Currently, ssa-handling code in expand_omp_for_static_chunk is dead
>> and not
>> exercised by testing.
>>
>> Ssa-handling code in omp-low.c is only triggered by
>> pass_parallelize_loops, and
>> that pass doesn't specify a chunk size on the GIMPLE_OMP_FOR it
>> constructs, so
>> that only exercises the expand_omp_for_static_nochunk path.
>>
>> Using the attached trigger patch, we excercise the ssa-handling code in
>> expand_omp_for_static_chunk. The following patch series fixes the
>> problems in
>> the ssa-handling code that we encounter.
>>
>> 1. Fix gcc_assert in expand_omp_for_static_chunk
>> 2. Fix inner loop phi in expand_omp_for_static_chunk
>> 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>>
>> The patch series has been bootstrapped and reg-tested on x86_64
>> together with
>> attached trigger patch.
>>
>> I'll post the patches from the patch series individually, in response
>> to this
>> email.
>>
>
> Ping for the three patches.
>

Ping^2.

Original posting at 
https://gcc.gnu.org/ml/gcc-patches/2015-04/msg00757.html .

Thanks,
- Tom

Re: [PR65637] Fix ssa-handling code in expand_omp_for_static_chunk

[Tom de Vries]

On 15/04/15 15:10, Tom de Vries wrote:
> Hi,
>
> This patch series fixes PR65637.
>
> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and
> not exercised by testing.
>
> Ssa-handling code in omp-low.c is only triggered by
> pass_parallelize_loops, and that pass doesn't specify a chunk size on
> the GIMPLE_OMP_FOR it constructs, so that only exercises the
> expand_omp_for_static_nochunk path.
>
> Using the attached trigger patch, we excercise the ssa-handling code in
> expand_omp_for_static_chunk.
 >
 > 1. Fix gcc_assert in expand_omp_for_static_chunk
 > 2. Fix inner loop phi in expand_omp_for_static_chunk
 > 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk

I'm posting an updated series.

1. Add param parloops-chunk-size
2. Handle simple latch bb in expand_omp_for_static_chunk
3. Fix gcc_assert in expand_omp_for_static_chunk
4. Fix inner loop phi in expand_omp_for_static_chunk
5. Handle 2 preds for fin_bb in expand_omp_for_static_chunk

There are two new patches, (1) and (2) in the new numbering.

The first patch adds a param parloops-chunk-size, which means the 
ssa-handling code in expand_omp_for_static_chunk is no longer dead.

The second patch handles simple latches in expand_omp_for_static_chunk, 
similar to the fix for PR66846 in expand_omp_for_static_nochunk.

The rest of the patches are now updated to include the testcases (and 
patch number 4 has been updated to handle simple latches).

The patch series has been bootstrapped and reg-tested on x86_64.

I'll post the patches from the patch series individually. The first two 
in response to this email, the latter three in response to the earlier 
submissions.

Thanks,
- Tom

[PATCH][1/5] Add param parloops-chunk-size

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1940 bytes --]

On 31/08/15 13:41, Tom de Vries wrote:
> On 15/04/15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>
>> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and
>> not exercised by testing.
>>
>> Ssa-handling code in omp-low.c is only triggered by
>> pass_parallelize_loops, and that pass doesn't specify a chunk size on
>> the GIMPLE_OMP_FOR it constructs, so that only exercises the
>> expand_omp_for_static_nochunk path.
>>
>> Using the attached trigger patch, we excercise the ssa-handling code in
>> expand_omp_for_static_chunk.
>  >
>  > 1. Fix gcc_assert in expand_omp_for_static_chunk
>  > 2. Fix inner loop phi in expand_omp_for_static_chunk
>  > 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> I'm posting an updated series.
>
> 1. Add param parloops-chunk-size
> 2. Handle simple latch bb in expand_omp_for_static_chunk
> 3. Fix gcc_assert in expand_omp_for_static_chunk
> 4. Fix inner loop phi in expand_omp_for_static_chunk
> 5. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> There are two new patches, (1) and (2) in the new numbering.
>
> The first patch adds a param parloops-chunk-size, which means the
> ssa-handling code in expand_omp_for_static_chunk is no longer dead.
>
> The second patch handles simple latches in expand_omp_for_static_chunk,
> similar to the fix for PR66846 in expand_omp_for_static_nochunk.
>
> The rest of the patches are now updated to include the testcases (and
> patch number 4 has been updated to handle simple latches).
>
> The patch series has been bootstrapped and reg-tested on x86_64.
>
> I'll post the patches from the patch series individually. The first two
> in response to this email, the latter three in response to the earlier
> submissions.
>

Hi,

this patch adds a param parloops-chunk-size.

The param is used to set the chunk-size of the schedule of omp-for loops 
generated by parloops.

Thanks,
- Tom

[-- Attachment #2: 0001-Add-param-parloops-chunk-size.patch --]
[-- Type: text/x-patch, Size: 2378 bytes --]

Add param parloops-chunk-size

2015-08-31  Tom de Vries  <tom@codesourcery.com>

	* doc/invoke.texi (parloops-chunk-size): Add item.
	* params.def (PARAM_PARLOOPS_CHUNK_SIZE): Add DEFPARAM.
	* tree-parloops.c: Include params.h.
	(create_parallel_loop): Set chunk-size of schedule of omp-for loop, if
	param parloops-chunk-size is used.
---
 gcc/doc/invoke.texi | 4 ++++
 gcc/params.def      | 5 +++++
 gcc/tree-parloops.c | 5 +++++
 3 files changed, 14 insertions(+)

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index c0ec0fd..6dd144d 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -11000,6 +11000,10 @@ path.  The default is 10.
 Maximum number of new jump thread paths to create for a finite state
 automaton.  The default is 50.
 
+@item parloops-chunk-size
+Chunk size of omp schedule for loops parallelized by parloops.  The default
+is 0.
+
 @end table
 @end table
 
diff --git a/gcc/params.def b/gcc/params.def
index c8b3a90..11238cb 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -1135,6 +1135,11 @@ DEFPARAM (PARAM_MAX_FSM_THREAD_PATHS,
 	  "max-fsm-thread-paths",
 	  "Maximum number of new jump thread paths to create for a finite state automaton",
 	  50, 1, 999999)
+
+DEFPARAM (PARAM_PARLOOPS_CHUNK_SIZE,
+	  "parloops-chunk-size",
+	  "Chunk size of omp schedule for loops parallelized by parloops",
+	  0, 0, 0)
 /*
 
 Local variables:
diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index d017479..c164121 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -57,6 +57,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-nested.h"
 #include "cgraph.h"
 #include "tree-ssa.h"
+#include "params.h"
 
 /* This pass tries to distribute iterations of loops into several threads.
    The implementation is straightforward -- for each loop we test whether its
@@ -2092,6 +2093,10 @@ create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
   type = TREE_TYPE (cvar);
   t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
   OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
+  int chunk_size = PARAM_VALUE (PARAM_PARLOOPS_CHUNK_SIZE);
+  if (chunk_size != 0)
+    OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t)
+      = build_int_cst (integer_type_node, chunk_size);
 
   for_stmt = gimple_build_omp_for (NULL, GF_OMP_FOR_KIND_FOR, t, 1, NULL);
   gimple_set_location (for_stmt, loc);
-- 
1.9.1

Re: [PATCH][1/5] Add param parloops-chunk-size

[Jakub Jelinek]

On Mon, Aug 31, 2015 at 01:45:25PM +0200, Tom de Vries wrote:
> Add param parloops-chunk-size
> 
> 2015-08-31  Tom de Vries  <tom@codesourcery.com>
> 
> 	* doc/invoke.texi (parloops-chunk-size): Add item.
> 	* params.def (PARAM_PARLOOPS_CHUNK_SIZE): Add DEFPARAM.
> 	* tree-parloops.c: Include params.h.
> 	(create_parallel_loop): Set chunk-size of schedule of omp-for loop, if
> 	param parloops-chunk-size is used.

Ok for trunk.

	Jakub

[PATCH][2/5] Handle simple latch bb in expand_omp_for_static_chunk

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2044 bytes --]

On 31/08/15 13:41, Tom de Vries wrote:
> On 15/04/15 15:10, Tom de Vries wrote:
>> Hi,
>>
>> This patch series fixes PR65637.
>>
>> Currently, ssa-handling code in expand_omp_for_static_chunk is dead and
>> not exercised by testing.
>>
>> Ssa-handling code in omp-low.c is only triggered by
>> pass_parallelize_loops, and that pass doesn't specify a chunk size on
>> the GIMPLE_OMP_FOR it constructs, so that only exercises the
>> expand_omp_for_static_nochunk path.
>>
>> Using the attached trigger patch, we excercise the ssa-handling code in
>> expand_omp_for_static_chunk.
>  >
>  > 1. Fix gcc_assert in expand_omp_for_static_chunk
>  > 2. Fix inner loop phi in expand_omp_for_static_chunk
>  > 3. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> I'm posting an updated series.
>
> 1. Add param parloops-chunk-size
> 2. Handle simple latch bb in expand_omp_for_static_chunk
> 3. Fix gcc_assert in expand_omp_for_static_chunk
> 4. Fix inner loop phi in expand_omp_for_static_chunk
> 5. Handle 2 preds for fin_bb in expand_omp_for_static_chunk
>
> There are two new patches, (1) and (2) in the new numbering.
>
> The first patch adds a param parloops-chunk-size, which means the
> ssa-handling code in expand_omp_for_static_chunk is no longer dead.
>
> The second patch handles simple latches in expand_omp_for_static_chunk,
> similar to the fix for PR66846 in expand_omp_for_static_nochunk.
>
> The rest of the patches are now updated to include the testcases (and
> patch number 4 has been updated to handle simple latches).
>
> The patch series has been bootstrapped and reg-tested on x86_64.
>
> I'll post the patches from the patch series individually. The first two
> in response to this email, the latter three in response to the earlier
> submissions.
>

Hi,

this patch handles simple latches in expand_omp_for_static_chunk, 
similar to how it's done for expand_omp_for_static_nochunk in the fix 
for PR66846 ( 
https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/omp-low.c?annotate=226427&pathrev=226427#l6539 
).

Thanks,
- Tom


[-- Attachment #2: 0002-Handle-simple-latch-bb-in-expand_omp_for_static_chun.patch --]
[-- Type: text/x-patch, Size: 2003 bytes --]

Handle simple latch bb in expand_omp_for_static_chunk

2015-08-31  Tom de Vries  <tom@codesourcery.com>

	* omp-low.c (expand_omp_for_static_chunk): Handle simple latch bb.
---
 gcc/omp-low.c | 21 +++++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)

diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index aa2a598..c3dfc51 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -6960,7 +6960,8 @@ expand_omp_for_static_chunk (struct omp_region *region,
   body_bb = single_succ (seq_start_bb);
   if (!broken_loop)
     {
-      gcc_assert (BRANCH_EDGE (cont_bb)->dest == body_bb);
+      gcc_assert (BRANCH_EDGE (cont_bb)->dest == body_bb
+		  || single_succ (BRANCH_EDGE (cont_bb)->dest) == body_bb);
       gcc_assert (EDGE_COUNT (cont_bb->succs) == 2);
       trip_update_bb = split_edge (FALLTHRU_EDGE (cont_bb));
     }
@@ -7261,6 +7262,11 @@ expand_omp_for_static_chunk (struct omp_region *region,
   if (!broken_loop)
     {
       se = find_edge (cont_bb, body_bb);
+      if (se == NULL)
+	{
+	  se = BRANCH_EDGE (cont_bb);
+	  gcc_assert (single_succ (se->dest) == body_bb);
+	}
       if (gimple_omp_for_combined_p (fd->for_stmt))
 	{
 	  remove_edge (se);
@@ -7351,14 +7357,25 @@ expand_omp_for_static_chunk (struct omp_region *region,
 
   if (!broken_loop)
     {
+      struct loop *loop = body_bb->loop_father;
       struct loop *trip_loop = alloc_loop ();
       trip_loop->header = iter_part_bb;
       trip_loop->latch = trip_update_bb;
       add_loop (trip_loop, iter_part_bb->loop_father);
 
+      if (loop != entry_bb->loop_father)
+	{
+	  gcc_assert (loop->header == body_bb);
+	  gcc_assert (broken_loop
+		      || loop->latch == region->cont
+		      || single_pred (loop->latch) == region->cont);
+	  trip_loop->inner = loop;
+	  return;
+	}
+
       if (!gimple_omp_for_combined_p (fd->for_stmt))
 	{
-	  struct loop *loop = alloc_loop ();
+	  loop = alloc_loop ();
 	  loop->header = body_bb;
 	  if (collapse_bb == NULL)
 	    loop->latch = cont_bb;
-- 
1.9.1

Re: [PATCH][2/5] Handle simple latch bb in expand_omp_for_static_chunk

[Jakub Jelinek]

On Mon, Aug 31, 2015 at 01:50:42PM +0200, Tom de Vries wrote:
> @@ -7351,14 +7357,25 @@ expand_omp_for_static_chunk (struct omp_region *region,
>  
>    if (!broken_loop)
>      {
> +      struct loop *loop = body_bb->loop_father;
>        struct loop *trip_loop = alloc_loop ();
>        trip_loop->header = iter_part_bb;
>        trip_loop->latch = trip_update_bb;
>        add_loop (trip_loop, iter_part_bb->loop_father);
>  
> +      if (loop != entry_bb->loop_father)
> +	{
> +	  gcc_assert (loop->header == body_bb);
> +	  gcc_assert (broken_loop

This is in a block code guarded with !broken_loop.
So, either you should just leave the "broken_loop || " out, or
you need to move it elsewhere, outside of the block guarded with
!broken_loop.

	Jakub