> 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”
--
Cheers, Roman Gareev.
2014-08-4 Roman Gareev <gareevro...@gmail.com>
[gcc/]
* graphite-isl-ast-to-gimple.c: Add a new struct ast_build_info.
(translate_isl_ast_for_loop): Add checking of the
flag_loop_parallelize_all.
(ast_build_before_for): New function.
(scop_to_isl_ast): Add checking of the
flag_loop_parallelize_all.
* graphite-dependences.c: Move the defenition of the
scop_get_dependences from graphite-optimize-isl.c to this file.
(apply_schedule_on_deps): Add checking of the ux's emptiness.
(carries_deps): Add checking of the x's value.
* graphite-optimize-isl.c: Move the defenition of the
scop_get_dependences to graphite-dependences.c.
* graphite-poly.h: Add declarations of scop_get_dependences
and carries_deps.
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
