Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Richard Biener]

On Fri, Jun 23, 2017 at 12:25 PM, Bin.Cheng  wrote:
> And the patch.
>
> On Fri, Jun 23, 2017 at 11:24 AM, Bin.Cheng  wrote:
>> On Tue, Jun 20, 2017 at 12:34 PM, Richard Biener
>>  wrote:
>>> On Tue, Jun 20, 2017 at 11:18 AM, Bin.Cheng  wrote:
 On Fri, Jun 16, 2017 at 11:10 AM, Richard Biener
  wrote:
> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng  wrote:
>> Hi,
>> This patch checks and records if partition can be executed in parallel by
>> looking if there exists data dependence cycles.  The information is 
>> needed
>> for distribution because the idea is to distribute parallel type 
>> partitions
>> away from sequential ones.  I believe current distribution doesn't work
>> very well because it does blind distribution/fusion.
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>
> +  /* In case of no data dependence.  */
> +  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
> +return false;
> +  /* Or the data dependence can be resolved by compilation time alias
> + check.  */
> +  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
> +  get_alias_set (DR_REF (dr2
> +return false;
>
> dependence analysis should use TBAA already, in which cases do you need 
> this?
> It seems to fall foul of the easy mistake of not honoring GCCs memory 
> model
> as well ... see dr_may_alias_p.
 I see.  Patch updated with this branch removed.

>
> +  /* Further check if any data dependence prevents us from executing the
> + partition parallelly.  */
> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
> +{
> +  dr1 = (*datarefs_vec)[i];
> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj)
> +   {
>
> what about write-write dependences?
>
> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
> +{
> +  dr1 = (*datarefs_vec)[i];
> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj)
> +   {
> + dr2 = (*datarefs_vec)[j];
> + /* Partition can only be executed sequentially if there is any
> +data dependence cycle.  */
>
> exact copy of the loop nest follows?!  Maybe you meant to iterate
> over writes in the first loop.
 Yes, this is a copy-paste typo.  Patch is also simplified because
 read/write are recorded together now.  Is it OK?
>>>
>>> Ok.
>> Sorry I have to update this patch because one of my mistake.  I didn't
>> update partition type when fusing them.  For some partition fusion,
>> the update is necessary otherwise we end up with inaccurate type and
>> inaccurate fusion later.  Is it Ok?

Ok.

>> Thanks,
>> bin
>> 2017-06-20  Bin Cheng  
>>
>> * tree-loop-distribution.c (enum partition_type): New.
>> (struct partition): New field type.
>> (partition_merge_into): Add parameter.  Update partition type.
>> (data_dep_in_cycle_p, update_type_for_merge): New functions.
>> (build_rdg_partition_for_vertex): Compute partition type.
>> (rdg_build_partitions): Dump partition type.
>> (distribute_loop): Update calls to partition_merge_into.

Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Bin.Cheng]

And the patch.

On Fri, Jun 23, 2017 at 11:24 AM, Bin.Cheng  wrote:
> On Tue, Jun 20, 2017 at 12:34 PM, Richard Biener
>  wrote:
>> On Tue, Jun 20, 2017 at 11:18 AM, Bin.Cheng  wrote:
>>> On Fri, Jun 16, 2017 at 11:10 AM, Richard Biener
>>>  wrote:
 On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng  wrote:
> Hi,
> This patch checks and records if partition can be executed in parallel by
> looking if there exists data dependence cycles.  The information is needed
> for distribution because the idea is to distribute parallel type 
> partitions
> away from sequential ones.  I believe current distribution doesn't work
> very well because it does blind distribution/fusion.
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

 +  /* In case of no data dependence.  */
 +  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 +return false;
 +  /* Or the data dependence can be resolved by compilation time alias
 + check.  */
 +  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
 +  get_alias_set (DR_REF (dr2
 +return false;

 dependence analysis should use TBAA already, in which cases do you need 
 this?
 It seems to fall foul of the easy mistake of not honoring GCCs memory model
 as well ... see dr_may_alias_p.
>>> I see.  Patch updated with this branch removed.
>>>

 +  /* Further check if any data dependence prevents us from executing the
 + partition parallelly.  */
 +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
 +{
 +  dr1 = (*datarefs_vec)[i];
 +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj)
 +   {

 what about write-write dependences?

 +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
 +{
 +  dr1 = (*datarefs_vec)[i];
 +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj)
 +   {
 + dr2 = (*datarefs_vec)[j];
 + /* Partition can only be executed sequentially if there is any
 +data dependence cycle.  */

 exact copy of the loop nest follows?!  Maybe you meant to iterate
 over writes in the first loop.
>>> Yes, this is a copy-paste typo.  Patch is also simplified because
>>> read/write are recorded together now.  Is it OK?
>>
>> Ok.
> Sorry I have to update this patch because one of my mistake.  I didn't
> update partition type when fusing them.  For some partition fusion,
> the update is necessary otherwise we end up with inaccurate type and
> inaccurate fusion later.  Is it Ok?
>
> Thanks,
> bin
> 2017-06-20  Bin Cheng  
>
> * tree-loop-distribution.c (enum partition_type): New.
> (struct partition): New field type.
> (partition_merge_into): Add parameter.  Update partition type.
> (data_dep_in_cycle_p, update_type_for_merge): New functions.
> (build_rdg_partition_for_vertex): Compute partition type.
> (rdg_build_partitions): Dump partition type.
> (distribute_loop): Update calls to partition_merge_into.
From 3a00323b1773eaeab368d29fd5995d09afc0cb4e Mon Sep 17 00:00:00 2001
From: Bin Cheng 
Date: Fri, 23 Jun 2017 10:43:05 +0100
Subject: [PATCH 10/13] partition-type-20170608.txt

---
 gcc/tree-loop-distribution.c | 139 ++-
 1 file changed, 123 insertions(+), 16 deletions(-)

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 516d5f7..87fdc15 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -528,11 +528,19 @@ build_rdg (struct loop *loop, control_dependences *cd)
 }
 
 
-
+/* Kind of distributed loop.  */
 enum partition_kind {
 PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
 };
 
+/* Type of distributed loop.  */
+enum partition_type {
+/* The distributed loop can be executed parallelly.  */
+PTYPE_PARALLEL = 0,
+/* The distributed loop has to be executed sequentially.  */
+PTYPE_SEQUENTIAL
+};
+
 /* Partition for loop distribution.  */
 struct partition
 {
@@ -546,6 +554,7 @@ struct partition
  number of loop (latch) iterations.  */
   bool plus_one;
   enum partition_kind kind;
+  enum partition_type type;
   /* data-references a kind != PKIND_NORMAL partition is about.  */
   data_reference_p main_dr;
   data_reference_p secondary_dr;
@@ -615,18 +624,16 @@ static const char *fuse_message[] = {
   "they are in the same dependence scc",
   "there is no point to distribute loop"};
 
-/* Merge PARTITION into the partition DEST.  */
-
 static void
-partition_merge_into (partition *dest, partition *partition, enum fuse_type ft)
-{
-  dest->kind = PKIND_NORMAL;
-  bitmap_ior_into (dest->stmts, partition->stmts);
-  if (partition_reduction_p (partition))
-   

Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Bin.Cheng]

On Tue, Jun 20, 2017 at 12:34 PM, Richard Biener
 wrote:
> On Tue, Jun 20, 2017 at 11:18 AM, Bin.Cheng  wrote:
>> On Fri, Jun 16, 2017 at 11:10 AM, Richard Biener
>>  wrote:
>>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng  wrote:
 Hi,
 This patch checks and records if partition can be executed in parallel by
 looking if there exists data dependence cycles.  The information is needed
 for distribution because the idea is to distribute parallel type partitions
 away from sequential ones.  I believe current distribution doesn't work
 very well because it does blind distribution/fusion.
 Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>
>>> +  /* In case of no data dependence.  */
>>> +  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
>>> +return false;
>>> +  /* Or the data dependence can be resolved by compilation time alias
>>> + check.  */
>>> +  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
>>> +  get_alias_set (DR_REF (dr2
>>> +return false;
>>>
>>> dependence analysis should use TBAA already, in which cases do you need 
>>> this?
>>> It seems to fall foul of the easy mistake of not honoring GCCs memory model
>>> as well ... see dr_may_alias_p.
>> I see.  Patch updated with this branch removed.
>>
>>>
>>> +  /* Further check if any data dependence prevents us from executing the
>>> + partition parallelly.  */
>>> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
>>> +{
>>> +  dr1 = (*datarefs_vec)[i];
>>> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj)
>>> +   {
>>>
>>> what about write-write dependences?
>>>
>>> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
>>> +{
>>> +  dr1 = (*datarefs_vec)[i];
>>> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj)
>>> +   {
>>> + dr2 = (*datarefs_vec)[j];
>>> + /* Partition can only be executed sequentially if there is any
>>> +data dependence cycle.  */
>>>
>>> exact copy of the loop nest follows?!  Maybe you meant to iterate
>>> over writes in the first loop.
>> Yes, this is a copy-paste typo.  Patch is also simplified because
>> read/write are recorded together now.  Is it OK?
>
> Ok.
Sorry I have to update this patch because one of my mistake.  I didn't
update partition type when fusing them.  For some partition fusion,
the update is necessary otherwise we end up with inaccurate type and
inaccurate fusion later.  Is it Ok?

Thanks,
bin
2017-06-20  Bin Cheng  

* tree-loop-distribution.c (enum partition_type): New.
(struct partition): New field type.
(partition_merge_into): Add parameter.  Update partition type.
(data_dep_in_cycle_p, update_type_for_merge): New functions.
(build_rdg_partition_for_vertex): Compute partition type.
(rdg_build_partitions): Dump partition type.
(distribute_loop): Update calls to partition_merge_into.

Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Richard Biener]

On Tue, Jun 20, 2017 at 11:18 AM, Bin.Cheng  wrote:
> On Fri, Jun 16, 2017 at 11:10 AM, Richard Biener
>  wrote:
>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng  wrote:
>>> Hi,
>>> This patch checks and records if partition can be executed in parallel by
>>> looking if there exists data dependence cycles.  The information is needed
>>> for distribution because the idea is to distribute parallel type partitions
>>> away from sequential ones.  I believe current distribution doesn't work
>>> very well because it does blind distribution/fusion.
>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>
>> +  /* In case of no data dependence.  */
>> +  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
>> +return false;
>> +  /* Or the data dependence can be resolved by compilation time alias
>> + check.  */
>> +  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
>> +  get_alias_set (DR_REF (dr2
>> +return false;
>>
>> dependence analysis should use TBAA already, in which cases do you need this?
>> It seems to fall foul of the easy mistake of not honoring GCCs memory model
>> as well ... see dr_may_alias_p.
> I see.  Patch updated with this branch removed.
>
>>
>> +  /* Further check if any data dependence prevents us from executing the
>> + partition parallelly.  */
>> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
>> +{
>> +  dr1 = (*datarefs_vec)[i];
>> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj)
>> +   {
>>
>> what about write-write dependences?
>>
>> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
>> +{
>> +  dr1 = (*datarefs_vec)[i];
>> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj)
>> +   {
>> + dr2 = (*datarefs_vec)[j];
>> + /* Partition can only be executed sequentially if there is any
>> +data dependence cycle.  */
>>
>> exact copy of the loop nest follows?!  Maybe you meant to iterate
>> over writes in the first loop.
> Yes, this is a copy-paste typo.  Patch is also simplified because
> read/write are recorded together now.  Is it OK?

Ok.

Thanks,
Richard.

> Thanks,
> bin
> 2017-06-07  Bin Cheng  
>
> * tree-loop-distribution.c (enum partition_type): New.
> (struct partition): New field type.
> (partition_merge_into): Update partition type.
> (data_dep_in_cycle_p): New function.
> (build_rdg_partition_for_vertex): Compute partition type.
> (rdg_build_partitions): Dump partition type.

Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Bin.Cheng]

On Fri, Jun 16, 2017 at 11:10 AM, Richard Biener
 wrote:
> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng  wrote:
>> Hi,
>> This patch checks and records if partition can be executed in parallel by
>> looking if there exists data dependence cycles.  The information is needed
>> for distribution because the idea is to distribute parallel type partitions
>> away from sequential ones.  I believe current distribution doesn't work
>> very well because it does blind distribution/fusion.
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>
> +  /* In case of no data dependence.  */
> +  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
> +return false;
> +  /* Or the data dependence can be resolved by compilation time alias
> + check.  */
> +  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
> +  get_alias_set (DR_REF (dr2
> +return false;
>
> dependence analysis should use TBAA already, in which cases do you need this?
> It seems to fall foul of the easy mistake of not honoring GCCs memory model
> as well ... see dr_may_alias_p.
I see.  Patch updated with this branch removed.

>
> +  /* Further check if any data dependence prevents us from executing the
> + partition parallelly.  */
> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
> +{
> +  dr1 = (*datarefs_vec)[i];
> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj)
> +   {
>
> what about write-write dependences?
>
> +  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
> +{
> +  dr1 = (*datarefs_vec)[i];
> +  EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj)
> +   {
> + dr2 = (*datarefs_vec)[j];
> + /* Partition can only be executed sequentially if there is any
> +data dependence cycle.  */
>
> exact copy of the loop nest follows?!  Maybe you meant to iterate
> over writes in the first loop.
Yes, this is a copy-paste typo.  Patch is also simplified because
read/write are recorded together now.  Is it OK?

Thanks,
bin
2017-06-07  Bin Cheng  

* tree-loop-distribution.c (enum partition_type): New.
(struct partition): New field type.
(partition_merge_into): Update partition type.
(data_dep_in_cycle_p): New function.
(build_rdg_partition_for_vertex): Compute partition type.
(rdg_build_partitions): Dump partition type.
From f2313383cb516badacbd99a5bc0a0e4fceef1bbf Mon Sep 17 00:00:00 2001
From: Bin Cheng 
Date: Fri, 9 Jun 2017 13:11:59 +0100
Subject: [PATCH 10/13] partition-type-20170607.txt

---
 gcc/tree-loop-distribution.c | 91 +---
 1 file changed, 85 insertions(+), 6 deletions(-)

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index a2e543e..d741e9e 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -526,11 +526,19 @@ build_rdg (struct loop *loop, control_dependences *cd)
 }
 
 
-
+/* Kind of distributed loop.  */
 enum partition_kind {
 PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
 };
 
+/* Type of distributed loop.  */
+enum partition_type {
+/* The distributed loop can be executed parallelly.  */
+PTYPE_PARALLEL = 0,
+/* The distributed loop has to be executed sequentially.  */
+PTYPE_SEQUENTIAL
+};
+
 /* Partition for loop distribution.  */
 struct partition
 {
@@ -544,6 +552,7 @@ struct partition
  number of loop (latch) iterations.  */
   bool plus_one;
   enum partition_kind kind;
+  enum partition_type type;
   /* data-references a kind != PKIND_NORMAL partition is about.  */
   data_reference_p main_dr;
   data_reference_p secondary_dr;
@@ -619,6 +628,9 @@ static void
 partition_merge_into (partition *dest, partition *partition, enum fuse_type ft)
 {
   dest->kind = PKIND_NORMAL;
+  if (dest->type == PTYPE_PARALLEL)
+dest->type = partition->type;
+
   bitmap_ior_into (dest->stmts, partition->stmts);
   if (partition_reduction_p (partition))
 dest->reduction_p = true;
@@ -1115,6 +1127,42 @@ get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b)
   return *slot;
 }
 
+/* In reduced dependence graph RDG for loop distribution, return true if
+   dependence between references DR1 and DR2 leads to a dependence cycle
+   and such dependence cycle can't be resolved by runtime alias check.  */
+
+static bool
+data_dep_in_cycle_p (struct graph *rdg,
+		 data_reference_p dr1, data_reference_p dr2)
+{
+  struct data_dependence_relation *ddr;
+
+  /* Re-shuffle data-refs to be in topological order.  */
+  if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
+  > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
+std::swap (dr1, dr2);
+
+  ddr = get_data_dependence (rdg, dr1, dr2);
+
+  /* In case of no data dependence.  */
+  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+return false;
+  /* For unknown data dependence or known 

Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Richard Biener]

On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng  wrote:
> Hi,
> This patch checks and records if partition can be executed in parallel by
> looking if there exists data dependence cycles.  The information is needed
> for distribution because the idea is to distribute parallel type partitions
> away from sequential ones.  I believe current distribution doesn't work
> very well because it does blind distribution/fusion.
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

+  /* In case of no data dependence.  */
+  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+return false;
+  /* Or the data dependence can be resolved by compilation time alias
+ check.  */
+  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
+  get_alias_set (DR_REF (dr2
+return false;

dependence analysis should use TBAA already, in which cases do you need this?
It seems to fall foul of the easy mistake of not honoring GCCs memory model
as well ... see dr_may_alias_p.

+  /* Further check if any data dependence prevents us from executing the
+ partition parallelly.  */
+  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
+{
+  dr1 = (*datarefs_vec)[i];
+  EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj)
+   {

what about write-write dependences?

+  EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi)
+{
+  dr1 = (*datarefs_vec)[i];
+  EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj)
+   {
+ dr2 = (*datarefs_vec)[j];
+ /* Partition can only be executed sequentially if there is any
+data dependence cycle.  */

exact copy of the loop nest follows?!  Maybe you meant to iterate
over writes in the first loop.

Richard.


> Thanks,
> bin
> 2017-06-07  Bin Cheng  
>
> * tree-loop-distribution.c (alias.h): Include header file.
> (enum partition_type): New.
> (struct partition): New field type.
> (partition_merge_into): Update partition type.
> (data_dep_in_cycle_p): New function.
> (build_rdg_partition_for_vertex): Compute partition type.
> (rdg_build_partitions): Dump partition type.

[PATCH GCC][11/13]Annotate partition by its parallelism execution type

[Bin Cheng]

Hi,
This patch checks and records if partition can be executed in parallel by
looking if there exists data dependence cycles.  The information is needed
for distribution because the idea is to distribute parallel type partitions
away from sequential ones.  I believe current distribution doesn't work
very well because it does blind distribution/fusion.
Bootstrap and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin
2017-06-07  Bin Cheng  

* tree-loop-distribution.c (alias.h): Include header file.
(enum partition_type): New.
(struct partition): New field type.
(partition_merge_into): Update partition type.
(data_dep_in_cycle_p): New function.
(build_rdg_partition_for_vertex): Compute partition type.
(rdg_build_partitions): Dump partition type.From 63a21f07ac97d1e93086110d2564900417a2af5a Mon Sep 17 00:00:00 2001
From: Bin Cheng 
Date: Fri, 9 Jun 2017 13:11:59 +0100
Subject: [PATCH 11/14] partition-type-20170607.txt

---
 gcc/tree-loop-distribution.c | 107 +--
 1 file changed, 103 insertions(+), 4 deletions(-)

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index eacd9a1..7e31fee8 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -51,6 +51,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-pass.h"
 #include "ssa.h"
 #include "gimple-pretty-print.h"
+#include "alias.h"
 #include "fold-const.h"
 #include "cfganal.h"
 #include "gimple-iterator.h"
@@ -535,11 +536,19 @@ build_rdg (struct loop *loop, control_dependences *cd)
 }
 
 
-
+/* Kind of distributed loop.  */
 enum partition_kind {
 PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
 };
 
+/* Type of distributed loop.  */
+enum partition_type {
+/* The distributed loop can be executed parallelly.  */
+PTYPE_PARALLEL = 0,
+/* The distributed loop has to be executed sequentially.  */
+PTYPE_SEQUENTIAL
+};
+
 /* Partition for loop distribution.  */
 struct partition
 {
@@ -553,6 +562,7 @@ struct partition
  number of loop (latch) iterations.  */
   bool plus_one;
   enum partition_kind kind;
+  enum partition_type type;
   /* data-references a kind != PKIND_NORMAL partition is about.  */
   data_reference_p main_dr;
   data_reference_p secondary_dr;
@@ -632,6 +642,9 @@ static void
 partition_merge_into (partition *dest, partition *partition, enum fuse_type ft)
 {
   dest->kind = PKIND_NORMAL;
+  if (dest->type == PTYPE_PARALLEL)
+dest->type = partition->type;
+
   bitmap_ior_into (dest->stmts, partition->stmts);
   if (partition_reduction_p (partition))
 dest->reduction_p = true;
@@ -1141,6 +1154,47 @@ get_data_dependence (struct graph *rdg, data_reference_p 
a, data_reference_p b)
   return (*slot)->ddr;
 }
 
+/* In reduced dependence graph RDG for loop distribution, return true if
+   dependence between references DR1 and DR2 leads to a dependence cycle
+   and such dependence cycle can't be resolved by runtime alias check.  */
+
+static bool
+data_dep_in_cycle_p (struct graph *rdg,
+data_reference_p dr1, data_reference_p dr2)
+{
+  struct data_dependence_relation *ddr;
+
+  /* Re-shuffle data-refs to be in topological order.  */
+  if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
+  > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
+std::swap (dr1, dr2);
+
+  ddr = get_data_dependence (rdg, dr1, dr2);
+
+  /* In case of no data dependence.  */
+  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+return false;
+  /* Or the data dependence can be resolved by compilation time alias
+ check.  */
+  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
+  get_alias_set (DR_REF (dr2
+return false;
+  /* For unknown data dependence or known data dependence which can't be
+ expressed in classic distance vector, we check if it can be resolved
+ by runtime alias check.  If yes, we still consider data dependence
+ as won't introduce data dependence cycle.  */
+  else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
+  || DDR_NUM_DIST_VECTS (ddr) == 0)
+return !runtime_alias_check_p (ddr, NULL, true);
+  else if (DDR_NUM_DIST_VECTS (ddr) > 1)
+return true;
+  else if (DDR_REVERSED_P (ddr)
+  || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1))
+return false;
+
+  return true;
+}
+
 /* Returns a partition with all the statements needed for computing
the vertex V of the RDG, also including the loop exit conditions.  */
 
@@ -1151,7 +1205,8 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v)
   auto_vec nodes;
   unsigned i, j;
   int x;
-  data_reference_p dr;
+  data_reference_p dr, dr1, dr2;
+  bitmap_iterator bi, bj;
 
   graphds_dfs (rdg, , 1, , false, NULL);
 
@@ -1167,6 +1222,12 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v)
 
  gcc_assert (slot !=