diff mbox

[GSoC] checking for the loop parallelism

Message ID CABGF_geTMuogsp=qG32ZiWJmnpYSswBUXe=B4NNBXvMMdchM5w@mail.gmail.com
State New
Headers show

Commit Message

Roman Gareev Aug. 4, 2014, 2:23 p.m. UTC 
> I would expect the to mark the i loop as non-parallel, but the j-loop
> as parallel. What is the partial schedule, the set of dependences and
> the dimension you check for both the i and the j loop?

Yes, you are right. The i loop is non-parallel and j-loop is parallel.
I've found that this substraction “ int dimension = isl_space_dim
(schedule_space, isl_dim_out) – 1;” was wrong.

The attached patch contains the improved version of checking for the
loop parallelism, which passes all the tests from
libgomp/testsuite/libgomp.graphite except
graphite-isl-ast-to-gimple.c.

P.S.: I've added checking of the ux's emptiness and of the x's value,
because ux is empty for specific test cases and produces the following
error: “/home/roman/graphite_stuff/isl-0.12.2/isl_union_map.c:418:
union map needs to contain elements in exactly one space”

Comments

Roman Gareev Aug. 4, 2014, 2:24 p.m. UTC | #1 
Sorry for misprint. It passes all the tests from
libgomp/testsuite/libgomp.graphite

> The attached patch contains the improved version of checking for the
> loop parallelism, which passes all the tests from
> libgomp/testsuite/libgomp.graphite except
> graphite-isl-ast-to-gimple.c.
Tobias Grosser Aug. 4, 2014, 2:27 p.m. UTC | #2 
On 04/08/2014 16:23, Roman Gareev wrote:
>> I would expect the to mark the i loop as non-parallel, but the j-loop
>> as parallel. What is the partial schedule, the set of dependences and
>> the dimension you check for both the i and the j loop?
>
> Yes, you are right. The i loop is non-parallel and j-loop is parallel.
> I've found that this substraction “ int dimension = isl_space_dim
> (schedule_space, isl_dim_out) – 1;” was wrong.
>
> The attached patch contains the improved version of checking for the
> loop parallelism, which passes all the tests from
> libgomp/testsuite/libgomp.graphite except
> graphite-isl-ast-to-gimple.c.
>
> P.S.: I've added checking of the ux's emptiness and of the x's value,
> because ux is empty for specific test cases and produces the following
> error: “/home/roman/graphite_stuff/isl-0.12.2/isl_union_map.c:418:
> union map needs to contain elements in exactly one space”

LGTM. Very nice work!

Cheers,
Tobias
diff mbox

Patch

Index: gcc/graphite-dependences.c
===================================================================
--- gcc/graphite-dependences.c	(revision 213256)
+++ gcc/graphite-dependences.c	(working copy)
@@ -53,6 +53,35 @@ 
 #include "graphite-poly.h"
 #include "graphite-htab.h"
 
+isl_union_map *
+scop_get_dependences (scop_p scop)
+{
+  isl_union_map *dependences;
+
+  if (!scop->must_raw)
+    compute_deps (scop, SCOP_BBS (scop),
+		  &scop->must_raw, &scop->may_raw,
+		  &scop->must_raw_no_source, &scop->may_raw_no_source,
+		  &scop->must_war, &scop->may_war,
+		  &scop->must_war_no_source, &scop->may_war_no_source,
+		  &scop->must_waw, &scop->may_waw,
+		  &scop->must_waw_no_source, &scop->may_waw_no_source);
+
+  dependences = isl_union_map_copy (scop->must_raw);
+  dependences = isl_union_map_union (dependences,
+				     isl_union_map_copy (scop->must_war));
+  dependences = isl_union_map_union (dependences,
+				     isl_union_map_copy (scop->must_waw));
+  dependences = isl_union_map_union (dependences,
+				     isl_union_map_copy (scop->may_raw));
+  dependences = isl_union_map_union (dependences,
+				     isl_union_map_copy (scop->may_war));
+  dependences = isl_union_map_union (dependences,
+				     isl_union_map_copy (scop->may_waw));
+
+  return dependences;
+}
+
 /* Add the constraints from the set S to the domain of MAP.  */
 
 static isl_map *
@@ -263,6 +292,11 @@ 
   ux = isl_union_map_copy (deps);
   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
   ux = isl_union_map_apply_range (ux, trans);
+  if (isl_union_map_is_empty (ux))
+    {
+      isl_union_map_free (ux);
+      return NULL;
+    }
   x = isl_map_from_union_map (ux);
 
   return x;
@@ -300,7 +334,7 @@ 
    in which all the inputs before DEPTH occur at the same time as the
    output, and the input at DEPTH occurs before output.  */
 
-static bool
+bool
 carries_deps (__isl_keep isl_union_map *schedule,
 	      __isl_keep isl_union_map *deps,
 	      int depth)
@@ -315,6 +349,8 @@ 
     return false;
 
   x = apply_schedule_on_deps (schedule, deps);
+  if (x == NULL)
+    return false;
   space = isl_map_get_space (x);
   space = isl_space_range (space);
   lex = isl_map_lex_le (space);
Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 213262)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -73,6 +73,14 @@ 
 static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
 						128 : max_mode_int_precision;
 
+struct ast_build_info
+{
+  ast_build_info()
+    : is_parallelizable(false)
+  { };
+  bool is_parallelizable;
+};
+
 /* Converts a GMP constant VAL to a tree and returns it.  */
 
 static tree
@@ -435,7 +443,15 @@ 
   redirect_edge_succ_nodup (next_e, after);
   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 
-  /* TODO: Add checking for the loop parallelism.  */
+  if (flag_loop_parallelize_all)
+  {
+    isl_id *id = isl_ast_node_get_annotation (node_for);
+    gcc_assert (id);
+    ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
+    loop->can_be_parallel = for_info->is_parallelizable;
+    free (for_info);
+    isl_id_free (id);
+  }
 
   return last_e;
 }
@@ -834,6 +850,23 @@ 
   return schedule_isl;
 }
 
+/* This method is executed before the construction of a for node.  */
+static __isl_give isl_id *
+ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
+{
+  isl_union_map *dependences = (isl_union_map *) user;
+  ast_build_info *for_info = XNEW (struct ast_build_info);
+  isl_union_map *schedule = isl_ast_build_get_schedule (build);
+  isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
+  int dimension = isl_space_dim (schedule_space, isl_dim_out);
+  for_info->is_parallelizable =
+    !carries_deps (schedule, dependences, dimension);
+  isl_union_map_free (schedule);
+  isl_space_free (schedule_space);
+  isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
+  return id;
+}
+
 static __isl_give isl_ast_node *
 scop_to_isl_ast (scop_p scop, ivs_params &ip)
 {
@@ -846,8 +879,18 @@ 
   add_parameters_to_ivs_params (scop, ip);
   isl_union_map *schedule_isl = generate_isl_schedule (scop);
   isl_ast_build *context_isl = generate_isl_context (scop);
+  isl_union_map *dependences = NULL;
+  if (flag_loop_parallelize_all)
+  {
+    dependences = scop_get_dependences (scop);
+    context_isl =
+      isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
+					 dependences);
+  }
   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
 							   schedule_isl);
+  if(dependences)
+    isl_union_map_free (dependences);
   isl_ast_build_free (context_isl);
   return ast_isl;
 }
@@ -908,7 +951,20 @@ 
   ivs_params_clear (ip);
   isl_ast_node_free (root_node);
   timevar_pop (TV_GRAPHITE_CODE_GEN);
-  /* TODO: Add dump  */
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      loop_p loop;
+      int num_no_dependency = 0;
+
+      FOR_EACH_LOOP (loop, 0)
+	if (loop->can_be_parallel)
+	  num_no_dependency++;
+
+      fprintf (dump_file, "\n%d loops carried no dependency.\n",
+	       num_no_dependency);
+    }
+
   return !graphite_regenerate_error;
 }
 #endif
Index: gcc/graphite-optimize-isl.c
===================================================================
--- gcc/graphite-optimize-isl.c	(revision 213256)
+++ gcc/graphite-optimize-isl.c	(working copy)
@@ -65,35 +65,6 @@ 
   return res;
 }
 
-static isl_union_map *
-scop_get_dependences (scop_p scop)
-{
-  isl_union_map *dependences;
-
-  if (!scop->must_raw)
-    compute_deps (scop, SCOP_BBS (scop),
-		  &scop->must_raw, &scop->may_raw,
-		  &scop->must_raw_no_source, &scop->may_raw_no_source,
-		  &scop->must_war, &scop->may_war,
-		  &scop->must_war_no_source, &scop->may_war_no_source,
-		  &scop->must_waw, &scop->may_waw,
-		  &scop->must_waw_no_source, &scop->may_waw_no_source);
-
-  dependences = isl_union_map_copy (scop->must_raw);
-  dependences = isl_union_map_union (dependences,
-				     isl_union_map_copy (scop->must_war));
-  dependences = isl_union_map_union (dependences,
-				     isl_union_map_copy (scop->must_waw));
-  dependences = isl_union_map_union (dependences,
-				     isl_union_map_copy (scop->may_raw));
-  dependences = isl_union_map_union (dependences,
-				     isl_union_map_copy (scop->may_war));
-  dependences = isl_union_map_union (dependences,
-				     isl_union_map_copy (scop->may_waw));
-
-  return dependences;
-}
-
 /* getTileMap - Create a map that describes a n-dimensonal tiling.
   
    getTileMap creates a map from a n-dimensional scattering space into an
Index: gcc/graphite-poly.h
===================================================================
--- gcc/graphite-poly.h	(revision 213256)
+++ gcc/graphite-poly.h	(working copy)
@@ -1551,4 +1551,12 @@ 
 	      isl_union_map **must_waw_no_source,
 	      isl_union_map **may_waw_no_source);
 
+isl_union_map *
+scop_get_dependences (scop_p scop);
+
+bool
+carries_deps (__isl_keep isl_union_map *schedule,
+	      __isl_keep isl_union_map *deps,
+	      int depth);
+
 #endif