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

[Bin Cheng <Bin.Cheng@arm.com>]

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

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  <bin.cheng@arm.com>

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

[-- Attachment #2: 0011-partition-type-20170607.txt --]
[-- Type: text/plain, Size: 6093 bytes --]

From 63a21f07ac97d1e93086110d2564900417a2af5a Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
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<int, 3> nodes;
   unsigned i, j;
   int x;
-  data_reference_p dr;
+  data_reference_p dr, dr1, dr2;
+  bitmap_iterator bi, bj;
 
   graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
 
@@ -1167,6 +1222,12 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v)
 
 	  gcc_assert (slot != NULL);
 
+	  /* Partition can only be executed sequentially if there is any
+	     unknown data reference.  */
+	  if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr)
+	      || !DR_INIT (dr) || !DR_STEP (dr))
+	    partition->type = PTYPE_SEQUENTIAL;
+
 	  if (DR_IS_READ (dr))
 	    bitmap_set_bit (partition->reads, *slot);
 	  else
@@ -1174,6 +1235,43 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v)
 	}
     }
 
+  if (partition->type == PTYPE_SEQUENTIAL)
+    return partition;
+
+  /* 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)
+	{
+	  dr2 = (*datarefs_vec)[j];
+	  /* Partition can only be executed sequentially if there is any
+	     data dependence cycle.  */
+	  if (data_dep_in_cycle_p (rdg, dr1, dr2))
+	    {
+	      partition->type = PTYPE_SEQUENTIAL;
+	      return partition;
+	    }
+	}
+    }
+
+  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.  */
+	  if (data_dep_in_cycle_p (rdg, dr1, dr2))
+	    {
+	      partition->type = PTYPE_SEQUENTIAL;
+	      return partition;
+	    }
+	}
+    }
+
   return partition;
 }
 
@@ -1473,8 +1571,9 @@ rdg_build_partitions (struct graph *rdg,
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
-	  fprintf (dump_file, "ldist useful partition:\n");
-	  dump_bitmap (dump_file, partition->stmts);
+	  fprintf (dump_file, "ldist creates useful %s partition:\n",
+		   partition->type == PTYPE_PARALLEL ? "parallel" : "sequent");
+	  bitmap_print (dump_file, partition->stmts, "  ", "\n");
 	}
 
       partitions->safe_push (partition);
-- 
1.9.1