From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from esa3.mentor.iphmx.com (esa3.mentor.iphmx.com [68.232.137.180]) by sourceware.org (Postfix) with ESMTPS id 6B93E385841C for ; Wed, 17 Nov 2021 16:04:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6B93E385841C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=codesourcery.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=mentor.com IronPort-SDR: ycesRS+fM/h/zaYZKoxBGV8p4XqTqgpKaSBdfwzRvfUCkEcBbCE7nw9oJFxInAQuRmUWpn2XT0 PXMP0rPhge4dgfC7K8gD/8ps4HSTFNzmepzaGJ3rrBjgu7FJ1nnVExCRZyS2VEkVRa6xHjy6Sj WdYKkbsIw+egmoM4iHkZLyMQ3PmC/wDXlXK6GPKVhAd+zJ4PEWRqQn4EfFhdfv4abDrNy48QY3 iMtngWpRwOtY3dAZkBFwK1JDIFRW3gkSNBMtGr71YC5h1EXbPwOk9smOCZqbODg8wBL+9tSo/3 vzbIt/HDSD4CvEK64dGxNpQx X-IronPort-AV: E=Sophos;i="5.87,241,1631606400"; d="scan'208";a="68445335" Received: from orw-gwy-01-in.mentorg.com ([192.94.38.165]) by esa3.mentor.iphmx.com with ESMTP; 17 Nov 2021 08:04:09 -0800 IronPort-SDR: B8HIxyB2iBtsKAf2E8pKuK0UzKluoP+ZH8z3CrwEv+IaIENd6VQHyXGraUuxi1WEOLQl9/eM5C qyKXYlTKaQBBkBqHSPpEknWz2zcnmUeDhDsqmRpkPTKcsdxXzYus5RFqb+yww1VSKSnCR/MGLO Tv7hCiOMIjzqq7kLKI7eBdtiny/4N8N3SwHHkkaUF1WaQ4QHNb464dVGk98D0somq7Jfwxm4xu ZdA1ds7ymmhEeCCIKrRxbraHwCqak1rrW9UfkkrtkDKxhMoAbgR/aP3iJjJxht1+D/+X1ktMWA eVY= From: Frederik Harwath To: Subject: [OG11][committed][PATCH 08/22] graphite: Add runtime alias checking Date: Wed, 17 Nov 2021 17:03:16 +0100 Message-ID: <20211117160330.20029-8-frederik@codesourcery.com> X-Mailer: git-send-email 2.33.0 In-Reply-To: <20211117160330.20029-1-frederik@codesourcery.com> References: <20211117160330.20029-1-frederik@codesourcery.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain X-Originating-IP: [137.202.0.90] X-ClientProxiedBy: svr-ies-mbx-01.mgc.mentorg.com (139.181.222.1) To SVR-IES-MBX-04.mgc.mentorg.com (139.181.222.4) X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 17 Nov 2021 16:04:12 -0000 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 chec= k 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. --- 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(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/alias-1.c diff --git a/gcc/common.opt b/gcc/common.opt index 771398bc03de..aa695e56dc48 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 canno= t 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-gim= ple.c index 44c06016f1a2..caa0160b9bce 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 =3D 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 SCO= P. Return true if code generation succeeded. */ @@ -1496,12 +1524,44 @@ graphite_regenerate_ast_isl (scop_p scop) region->if_region =3D if_region; loop_p context_loop =3D region->region.entry->src->loop_father; + gcc_checking_assert (context_loop); edge e =3D single_succ_edge (if_region->true_region->region.entry->dest)= ; basic_block bb =3D split_edge (e); /* Update the true_region exit edge. */ region->if_region->true_region->region.exit =3D 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 dat= a + references of the SCoP statically. Generate an alias check that se= lects + the newly generated version of the SCoP in the true-branch of the + conditional if aliasing can be ruled out at runtime and the origin= al + version of the SCoP, otherwise. */ + + loop_p loop + =3D find_common_loop (scop->scop_info->region.entry->dest->loop_= father, + scop->scop_info->region.exit->src->loop_fath= er); + tree cond =3D generate_alias_cond (scop->unhandled_alias_ddrs, loop)= ; + tree non_alias_cond =3D build1 (TRUTH_NOT_EXPR, boolean_type_node, c= ond); + 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 2e31b2782c24..27d5e43af125 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 =3D 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 =3D NULL; diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 46c470210d05..26ba61d1d601 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 a= n + 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 + =3D "cannot create alias check for SCoP. Data reference's"; + static const char *suf =3D "uses definitions from SCoP.\n"; + opt_result res =3D opt_result::success (); + + if (has_operands_from_region_p (DR_BASE_OBJECT (dr), region)) + res =3D opt_result::failure_at (DR_STMT (dr), "%s base %s", pre, suf); + else if (has_operands_from_region_p (DR_INIT (dr), region)) + res =3D 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 =3D opt_result::failure_at (DR_STMT (dr), "%s step %s", pre, suf); + else if (has_operands_from_region_p (DR_OFFSET (dr), region)) + res =3D opt_result::failure_at (DR_STMT (dr), "%s loop-invariant offse= t %s", + pre, suf); + else if (has_operands_from_region_p (DR_BASE_ADDRESS (dr), region)) + res =3D opt_result::failure_at (DR_STMT (dr), "%s base address %s", pr= e, + suf); + else + for (unsigned i =3D 0; i < DR_NUM_DIMENSIONS (dr); ++i) + if (has_operands_from_region_p (DR_ACCESS_FN (dr, i), region)) + { + res =3D opt_result::failure_at ( + DR_STMT (dr), "%s %d-th access function %s", pre, i + 1, pr= e); + 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 =3D + "data-reference not well-analyzed for runtime check."; + gimple* stmt =3D 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 =3D number_of_latch_executions (loop); + if (niters =3D=3D NULL_TREE || niters =3D=3D chrec_dont_know) + return opt_result::failure_at (DR_STMT (dr1), + "failed to obtain number of iterations o= f " + "loop %d.\n", loop->num); + + opt_result ok =3D dr_well_analyzed_for_runtime_alias_check_p (dr1); + if (!ok) + return ok; + + ok =3D 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 ca= nnot + use definitions made within REGION. */ + + ok =3D dr_defs_outside_region (region, dr1); + if (!ok) + return ok; + + ok =3D 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 =3D scop->drs.length (); struct graph *g =3D 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) =3D 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 =3D 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) =3D=3D 0 - || DR_NUM_DIMENSIONS (dr1->dr) !=3D DR_NUM_DIMENSIONS (dr2->d= r) - || ! 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 =3D dri1->dr; + + for (j =3D i + 1; scop->drs.iterate (j, &dri2); j++) + { + + data_reference_p dr2 =3D 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 =3D DR_NUM_DIMENSIONS (dr1) =3D=3D 0; + bool different_dimensions + =3D DR_NUM_DIMENSIONS (dr1) !=3D DR_NUM_DIMENSIONS (dr2)= ; + bool different_base_objects =3D !operand_equal_p ( + DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), OEP_ADDRESS_= OF); + bool incompatible_types + =3D !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1)= ), + TREE_TYPE (DR_BASE_OBJECT (dr2)))= ; + bool ddr_can_be_handled + =3D !(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 reference= s:\n"; + print_gimple_stmt (dump_file, dr1->stmt, 2, TDF_DETA= ILS); + print_gimple_stmt (dump_file, dr2->stmt, 2, TDF_DETA= ILS); + 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 + =3D find_common_loop ((DR_STMT (dr1))->bb->loop_father, + (DR_STMT (dr2))->bb->loop_father); + edge scop_entry =3D scop->scop_info->region.entry; + dr1 =3D create_data_ref (scop_entry, common_loop, DR_REF (dr= 1), + DR_STMT (dr1), DR_IS_READ (dr1), + DR_IS_CONDITIONAL_IN_STMT (dr1)); + dr2 =3D create_data_ref (scop_entry, common_loop, DR_REF (dr= 2), + 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->regi= on)) + { + ddr_p ddr =3D initialize_data_dependence_relation (dr1, = dr2, + nest_ve= c); + 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 =3D XNEWVEC (int, num_vertices); for (i =3D 0; i < num_vertices; i++) all_vertices[i] =3D i; scop->max_alias_set - =3D graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1; + =3D graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + = 1; free (all_vertices); for (i =3D 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 executi= ng edges that stay inside the current loop, delaying processing exit edges= . */ diff --git a/gcc/graphite.h b/gcc/graphite.h index 6464d2f50ce7..03febfa39986 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 detec= tion + 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 cd19e6010196..c51ea68bfb47 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) =3D=3D SSA_NAME) + return defined_in_sese_p (expr, region); + + for (int i =3D 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 000000000000..ee80dae1df33 --- /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 =3D 0; + + for (i =3D 0; i < 10000; i=3Di+1) + for (j =3D 0; j < 22222; j=3Dj+1) + *sum +=3D x[i] + y[j]; +} + +/* { dg-final { scan-tree-dump "number of SCoPs: 1" "graphite" { xfail *-*= -* } } } */ -- 2.33.0 ----------------- Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstra=DFe 201, 8= 0634 M=FCnchen; Gesellschaft mit beschr=E4nkter Haftung; Gesch=E4ftsf=FChre= r: Thomas Heurung, Frank Th=FCrauf; Sitz der Gesellschaft: M=FCnchen; Regis= tergericht M=FCnchen, HRB 106955