From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2102) id 3B5343858C27; Wed, 17 Nov 2021 08:17:50 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3B5343858C27 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Frederik Harwath To: gcc-cvs@gcc.gnu.org Subject: [gcc/devel/omp/gcc-11] graphite: Add runtime alias checking X-Act-Checkin: gcc X-Git-Author: Frederik Harwath X-Git-Refname: refs/heads/devel/omp/gcc-11 X-Git-Oldrev: 65cb58c3dfb56d86428599a1896b6b64171e8409 X-Git-Newrev: fde67734b843f9a889912991f12c202e147814bb Message-Id: <20211117081750.3B5343858C27@sourceware.org> Date: Wed, 17 Nov 2021 08:17:50 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 17 Nov 2021 08:17:50 -0000 https://gcc.gnu.org/g:fde67734b843f9a889912991f12c202e147814bb commit fde67734b843f9a889912991f12c202e147814bb Author: Frederik Harwath Date: Tue Nov 16 16:15:08 2021 +0100 graphite: Add runtime alias checking Graphite rejects a SCoP if it contains a pair of data references for which it cannot determine statically if they may alias. This happens very often, for instance in C code which does not use explicit "restrict". This commit adds the possibility to analyze a SCoP nevertheless and perform an alias check at runtime. Then, if aliasing is detected, the execution will fall back to the unoptimized SCoP. TODO This needs more testing on non-OpenACC code. gcc/ChangeLog: * common.opt: Add fgraphite-runtime-alias-checks. * graphite-isl-ast-to-gimple.c (generate_alias_cond): New function. (graphite_regenerate_ast_isl): Use from here. * graphite-poly.c (new_scop): Create unhandled_alias_ddrs vec ... (free_scop): and release here. * graphite-scop-detection.c (dr_defs_outside_region): New function. (dr_well_analyzed_for_runtime_alias_check_p): New function. (graphite_runtime_alias_check_p): New function. (build_alias_set): Record unhandled alias ddrs for later alias check creation if flag_graphite_runtime_alias_checks is true instead of failing. * graphite.h (struct scop): Add field unhandled_alias_ddrs. * sese.h (has_operands_from_region_p): New function. gcc/testsuite/ChangeLog: * gcc.dg/graphite/alias-1.c: New test. Diff: --- gcc/common.opt | 4 + gcc/graphite-isl-ast-to-gimple.c | 60 ++++++++ gcc/graphite-poly.c | 2 + gcc/graphite-scop-detection.c | 239 +++++++++++++++++++++++++++++--- gcc/graphite.h | 4 + gcc/sese.h | 18 +++ gcc/testsuite/gcc.dg/graphite/alias-1.c | 22 +++ 7 files changed, 326 insertions(+), 23 deletions(-) diff --git a/gcc/common.opt b/gcc/common.opt index 771398bc03d..aa695e56dc4 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -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 diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c index 44c06016f1a..caa0160b9bc 100644 --- a/gcc/graphite-isl-ast-to-gimple.c +++ b/gcc/graphite-isl-ast-to-gimple.c @@ -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 &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 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 ()) { diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 2e31b2782c2..27d5e43af12 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -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; diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 46c470210d0..26ba61d1d60 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -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 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. */ diff --git a/gcc/graphite.h b/gcc/graphite.h index 6464d2f50ce..03febfa3998 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -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 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. */ diff --git a/gcc/sese.h b/gcc/sese.h index cd19e601019..c51ea68bfb4 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -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 diff --git a/gcc/testsuite/gcc.dg/graphite/alias-1.c b/gcc/testsuite/gcc.dg/graphite/alias-1.c new file mode 100644 index 00000000000..ee80dae1df3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/alias-1.c @@ -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 *-*-* } } } */