@@ -1636,6 +1636,10 @@ fgraphite-identity
Common Var(flag_graphite_identity) Optimization
Enable Graphite Identity transformation.
+fgraphite-runtime-alias-checks
+Common Var(flag_graphite_runtime_alias_checks) Optimization Init(1)
+Allow Graphite to add runtime alias checks to loop-nests if aliasing cannot be resolved statically.
+
fhoist-adjacent-loads
Common Var(flag_hoist_adjacent_loads) Optimization
Enable hoisting adjacent loads to encourage generating conditional move
@@ -1456,6 +1456,34 @@ generate_entry_out_of_ssa_copies (edge false_entry,
}
}
+/* Create a condition that evaluates to TRUE if all ALIAS_DDRS are free of
+ aliasing. */
+
+static tree
+generate_alias_cond (vec<ddr_p> &alias_ddrs, loop_p context_loop)
+{
+ gcc_checking_assert (flag_graphite_runtime_alias_checks
+ && alias_ddrs.length () > 0);
+ gcc_checking_assert (context_loop);
+
+ auto_vec<dr_with_seg_len_pair_t> check_pairs;
+ compute_alias_check_pairs (context_loop, &alias_ddrs, &check_pairs);
+ gcc_checking_assert (check_pairs.length () > 0);
+
+ tree alias_cond = NULL_TREE;
+ create_runtime_alias_checks (context_loop, &check_pairs, &alias_cond);
+ gcc_checking_assert (alias_cond);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Generated runtime alias check: ");
+ print_generic_expr (dump_file, alias_cond, dump_flags);
+ fprintf (dump_file, "\n");
+ }
+
+ return alias_cond;
+}
+
/* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
Return true if code generation succeeded. */
@@ -1496,12 +1524,44 @@ graphite_regenerate_ast_isl (scop_p scop)
region->if_region = if_region;
loop_p context_loop = region->region.entry->src->loop_father;
+ gcc_checking_assert (context_loop);
edge e = single_succ_edge (if_region->true_region->region.entry->dest);
basic_block bb = split_edge (e);
/* Update the true_region exit edge. */
region->if_region->true_region->region.exit = single_succ_edge (bb);
+ if (flag_graphite_runtime_alias_checks
+ && scop->unhandled_alias_ddrs.length () > 0)
+ {
+ /* SCoP detection has failed to handle the aliasing between some data
+ references of the SCoP statically. Generate an alias check that selects
+ the newly generated version of the SCoP in the true-branch of the
+ conditional if aliasing can be ruled out at runtime and the original
+ version of the SCoP, otherwise. */
+
+ loop_p loop
+ = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
+ scop->scop_info->region.exit->src->loop_father);
+ tree cond = generate_alias_cond (scop->unhandled_alias_ddrs, loop);
+ tree non_alias_cond = build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
+ set_ifsese_condition (region->if_region, non_alias_cond);
+
+ /* The loop-nest vec is shared by all DDRs. */
+ DDR_LOOP_NEST (scop->unhandled_alias_ddrs[0]).release ();
+
+ unsigned int i;
+ struct data_dependence_relation *ddr;
+
+ FOR_EACH_VEC_ELT (scop->unhandled_alias_ddrs, i, ddr)
+ if (ddr)
+ free_dependence_relation (ddr);
+ scop->unhandled_alias_ddrs.truncate (0);
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
+
t.translate_isl_ast (context_loop, root_node, e, ip);
if (! t.codegen_error_p ())
{
@@ -264,6 +264,7 @@ new_scop (edge entry, edge exit)
scop_set_region (s, region);
s->pbbs.create (3);
s->drs.create (3);
+ s->unhandled_alias_ddrs.create (1);
s->dependence = NULL;
return s;
}
@@ -284,6 +285,7 @@ free_scop (scop_p scop)
scop->pbbs.release ();
scop->drs.release ();
+ scop->unhandled_alias_ddrs.release ();
isl_set_free (scop->param_context);
scop->param_context = NULL;
@@ -1542,6 +1542,123 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
return new_gimple_poly_bb (bb, drs, reads, writes);
}
+/* Checks if all parts of DR are defined outside of REGION. This allows an
+ alias check involving DR to be placed in front of the region. */
+
+static opt_result
+dr_defs_outside_region (const sese_l ®ion, data_reference_p dr)
+{
+ static const char *pre
+ = "cannot create alias check for SCoP. Data reference's";
+ static const char *suf = "uses definitions from SCoP.\n";
+ opt_result res = opt_result::success ();
+
+ if (has_operands_from_region_p (DR_BASE_OBJECT (dr), region))
+ res = opt_result::failure_at (DR_STMT (dr), "%s base %s", pre, suf);
+ else if (has_operands_from_region_p (DR_INIT (dr), region))
+ res = opt_result::failure_at (DR_STMT (dr), "%s constant offset %s", pre,
+ suf);
+ else if (has_operands_from_region_p (DR_STEP (dr), region))
+ res = opt_result::failure_at (DR_STMT (dr), "%s step %s", pre, suf);
+ else if (has_operands_from_region_p (DR_OFFSET (dr), region))
+ res = opt_result::failure_at (DR_STMT (dr), "%s loop-invariant offset %s",
+ pre, suf);
+ else if (has_operands_from_region_p (DR_BASE_ADDRESS (dr), region))
+ res = opt_result::failure_at (DR_STMT (dr), "%s base address %s", pre,
+ suf);
+ else
+ for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
+ if (has_operands_from_region_p (DR_ACCESS_FN (dr, i), region))
+ {
+ res = opt_result::failure_at (
+ DR_STMT (dr), "%s %d-th access function %s", pre, i + 1, pre);
+ break;
+ }
+
+ return opt_result::success ();
+}
+
+/* Check that all constituents of DR that are used by the
+ "compute_alias_check_pairs" function have been analyzed as required. */
+
+static opt_result
+dr_well_analyzed_for_runtime_alias_check_p (data_reference_p dr)
+{
+ static const char* error =
+ "data-reference not well-analyzed for runtime check.";
+ gimple* stmt = DR_STMT (dr);
+
+ if (! DR_BASE_ADDRESS (dr))
+ return opt_result::failure_at (stmt, "%s no base address.\n", error);
+ else if (! DR_OFFSET (dr))
+ return opt_result::failure_at (stmt, "%s no offset.\n", error);
+ else if (! DR_INIT (dr))
+ return opt_result::failure_at (stmt, "%s no init.\n", error);
+ else if (! DR_STEP (dr))
+ return opt_result::failure_at (stmt, "%s no step.\n", error);
+ else if (! tree_fits_uhwi_p (DR_STEP (dr)))
+ return opt_result::failure_at (stmt, "%s step too large.\n", error);
+
+ DEBUG_PRINT (dump_data_reference (dump_file, dr));
+
+ return opt_result::success ();
+}
+
+/* Return TRUE if it is possible to create a runtime alias check for
+ data-references DR1 and DR2 from LOOP and place it in front of REGION. */
+
+static opt_result
+graphite_runtime_alias_check_p (data_reference_p dr1, data_reference_p dr2,
+ class loop *loop, const sese_l ®ion)
+{
+ gcc_checking_assert (loop);
+ gcc_checking_assert (dr1);
+ gcc_checking_assert (dr2);
+
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "Attempting runtime alias check creation for DRs:\n");
+ dump_data_reference (dump_file, dr1);
+ dump_data_reference (dump_file, dr2);
+ }
+
+ if (!optimize_loop_for_speed_p (loop))
+ return opt_result::failure_at (DR_STMT (dr1),
+ "runtime alias check not supported when"
+ " optimizing for size.\n");
+
+ /* Verify that we have enough information about the data-references and
+ context loop to construct a runtime alias check expression with
+ "compute_alias_check_pairs". */
+ tree niters = number_of_latch_executions (loop);
+ if (niters == NULL_TREE || niters == chrec_dont_know)
+ return opt_result::failure_at (DR_STMT (dr1),
+ "failed to obtain number of iterations of "
+ "loop %d.\n", loop->num);
+
+ opt_result ok = dr_well_analyzed_for_runtime_alias_check_p (dr1);
+ if (!ok)
+ return ok;
+
+ ok = dr_well_analyzed_for_runtime_alias_check_p (dr2);
+ if (!ok)
+ return ok;
+
+ /* The runtime alias check would be placed before REGION and hence it cannot
+ use definitions made within REGION. */
+
+ ok = dr_defs_outside_region (region, dr1);
+ if (!ok)
+ return ok;
+
+ ok = dr_defs_outside_region (region, dr2);
+ if (!ok)
+ return ok;
+
+ return opt_result::success ();
+}
+
/* Compute alias-sets for all data references in DRS. */
static bool
@@ -1549,7 +1666,7 @@ build_alias_set (scop_p scop)
{
int num_vertices = scop->drs.length ();
struct graph *g = new_graph (num_vertices);
- dr_info *dr1, *dr2;
+ dr_info *dri1, *dri2;
int i, j;
int *all_vertices;
@@ -1557,33 +1674,110 @@ build_alias_set (scop_p scop)
= find_common_loop (scop->scop_info->region.entry->dest->loop_father,
scop->scop_info->region.exit->src->loop_father);
- FOR_EACH_VEC_ELT (scop->drs, i, dr1)
- for (j = i+1; scop->drs.iterate (j, &dr2); j++)
- if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
- {
- /* Dependences in the same alias set need to be handled
- by just looking at DR_ACCESS_FNs. */
- if (DR_NUM_DIMENSIONS (dr1->dr) == 0
- || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
- || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
- DR_BASE_OBJECT (dr2->dr),
- OEP_ADDRESS_OF)
- || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
- TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
- {
- free_graph (g);
- return false;
- }
- add_edge (g, i, j);
- add_edge (g, j, i);
- }
+ gcc_checking_assert (nest);
+
+ vec<loop_p> nest_vec;
+ nest_vec.create (1);
+ if (flag_graphite_runtime_alias_checks)
+ nest_vec.safe_push (nest);
+
+ FOR_EACH_VEC_ELT (scop->drs, i, dri1)
+ {
+ data_reference_p dr1 = dri1->dr;
+
+ for (j = i + 1; scop->drs.iterate (j, &dri2); j++)
+ {
+
+ data_reference_p dr2 = dri2->dr;
+ if (!(DR_IS_READ (dr1) && DR_IS_READ (dr2))
+ && dr_may_alias_p (dr1, dr2, nest))
+ {
+ /* Dependences in the same alias set need to be handled
+ by just looking at DR_ACCESS_FNs. */
+ bool dimension_zero = DR_NUM_DIMENSIONS (dr1) == 0;
+ bool different_dimensions
+ = DR_NUM_DIMENSIONS (dr1) != DR_NUM_DIMENSIONS (dr2);
+ bool different_base_objects = !operand_equal_p (
+ DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), OEP_ADDRESS_OF);
+ bool incompatible_types
+ = !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1)),
+ TREE_TYPE (DR_BASE_OBJECT (dr2)));
+ bool ddr_can_be_handled
+ = !(dimension_zero || different_dimensions
+ || different_base_objects || incompatible_types);
+
+ if (!ddr_can_be_handled)
+ {
+ DEBUG_PRINT (
+ dp << "[build_alias_set] "
+ "Cannot handle aliasing between data references:\n";
+ print_gimple_stmt (dump_file, dr1->stmt, 2, TDF_DETAILS);
+ print_gimple_stmt (dump_file, dr2->stmt, 2, TDF_DETAILS);
+ dp << "\n");
+ if (dimension_zero)
+ DEBUG_PRINT (dp << "DR1 has dimension 0.\n");
+ if (different_base_objects)
+ DEBUG_PRINT (dp << "DRs have different base objects.\n");
+ if (different_dimensions)
+ DEBUG_PRINT (dp << "DRs have different dimensions.\n");
+ if (incompatible_types)
+ DEBUG_PRINT (dp <<
+ "DRs have incompatible base object types.\n");
+ }
+
+ if (ddr_can_be_handled)
+ {
+ add_edge (g, i, j);
+ add_edge (g, j, i);
+ continue;
+ }
+
+ loop_p common_loop
+ = find_common_loop ((DR_STMT (dr1))->bb->loop_father,
+ (DR_STMT (dr2))->bb->loop_father);
+ edge scop_entry = scop->scop_info->region.entry;
+ dr1 = create_data_ref (scop_entry, common_loop, DR_REF (dr1),
+ DR_STMT (dr1), DR_IS_READ (dr1),
+ DR_IS_CONDITIONAL_IN_STMT (dr1));
+ dr2 = create_data_ref (scop_entry, common_loop, DR_REF (dr2),
+ DR_STMT (dr2), DR_IS_READ (dr2),
+ DR_IS_CONDITIONAL_IN_STMT (dr2));
+
+ if (flag_graphite_runtime_alias_checks
+ && graphite_runtime_alias_check_p (dr1, dr2, nest,
+ scop->scop_info->region))
+ {
+ ddr_p ddr = initialize_data_dependence_relation (dr1, dr2,
+ nest_vec);
+ scop->unhandled_alias_ddrs.safe_push (ddr);
+ }
+ else
+ {
+ if (flag_graphite_runtime_alias_checks)
+ {
+ unsigned int i;
+ struct data_dependence_relation *ddr;
+
+ FOR_EACH_VEC_ELT (scop->unhandled_alias_ddrs, i, ddr)
+ if (ddr)
+ free_dependence_relation (ddr);
+ scop->unhandled_alias_ddrs.truncate (0);
+ }
+
+ nest_vec.release ();
+ free_graph (g);
+ return false;
+ }
+ }
+ }
+ }
all_vertices = XNEWVEC (int, num_vertices);
for (i = 0; i < num_vertices; i++)
all_vertices[i] = i;
scop->max_alias_set
- = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
+ = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
free (all_vertices);
for (i = 0; i < g->n_vertices; i++)
@@ -1703,7 +1897,6 @@ gather_bbs::after_dom_children (basic_block bb)
}
}
-
/* Compute sth like an execution order, dominator order with first executing
edges that stay inside the current loop, delaying processing exit edges. */
@@ -368,6 +368,10 @@ struct scop
/* The maximum alias set as assigned to drs by build_alias_sets. */
unsigned max_alias_set;
+ /* A set of ddrs that were rejected by build_alias_set during scop detection
+ and that must be handled by other means (runtime checking). */
+ vec<ddr_p> unhandled_alias_ddrs;
+
/* All the basic blocks in this scop that contain memory references
and that will be represented as statements in the polyhedral
representation. */
@@ -153,6 +153,24 @@ defined_in_sese_p (tree name, const sese_l &r)
return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
}
+/* Returns true if EXPR has operands that are defined in REGION. */
+
+static bool
+has_operands_from_region_p (tree expr, const sese_l ®ion)
+{
+ if (!expr || is_gimple_min_invariant (expr))
+ return false;
+
+ if (TREE_CODE (expr) == SSA_NAME)
+ return defined_in_sese_p (expr, region);
+
+ for (int i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
+ if (has_operands_from_region_p (TREE_OPERAND (expr, i), region))
+ return true;
+
+ return false;
+}
+
/* Returns true when LOOP is in REGION. */
static inline bool
new file mode 100644
@@ -0,0 +1,22 @@
+/* This test demonstrates a loop nest that Graphite cannot handle
+ because of aliasing. It should be possible to handle this loop nest
+ by creating a runtime alias check like in the very similar test
+ alias-0-runtime-check.c. However Graphite analyses the data
+ reference with respect to the innermost loop that contains the data
+ reference, the variable "i" remains uninstantiated (in contrast to
+ "j"), and consequently the alias check cannot be placed outside of
+ the SCoP since "i" is not defined there. */
+
+/* { dg-options "-O2 -fgraphite-identity -fgraphite-runtime-alias-checks -fdump-tree-graphite-details" } */
+
+void sum(int *x, int *y, unsigned *sum)
+{
+ unsigned i,j;
+ *sum = 0;
+
+ for (i = 0; i < 10000; i=i+1)
+ for (j = 0; j < 22222; j=j+1)
+ *sum += x[i] + y[j];
+}
+
+/* { dg-final { scan-tree-dump "number of SCoPs: 1" "graphite" { xfail *-*-* } } } */