From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id 95E4D385780E for ; Thu, 24 Sep 2020 11:26:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 95E4D385780E Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=ucw.cz Authentication-Results: sourceware.org; spf=none smtp.mailfrom=hubicka@kam.mff.cuni.cz Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 4F9B428299C; Thu, 24 Sep 2020 13:26:36 +0200 (CEST) Date: Thu, 24 Sep 2020 13:26:36 +0200 From: Jan Hubicka To: Richard Biener Cc: GCC Patches , d@dcepelik.cz Subject: Re: Add access through parameter derference tracking to modref Message-ID: <20200924112635.GA59363@kam.mff.cuni.cz> References: <20200924090555.GG6758@kam.mff.cuni.cz> <20200924105442.GA34649@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Status: No, score=-15.1 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, KAM_SHORT, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: Thu, 24 Sep 2020 11:26:42 -0000 > > > > I will do (but need to think bit of a redundancy between comment in > > ipa-modref and ipa-modref-tree) > > One place is enough - just add a pointer to the other place. Here is updated patch I am testing. I adds documentation into ipa-modref-tree.h that is perhaps more natural place and links it from ipa-modref.c documentation. Also note that loads/stores are distinguished since for every function we have both a decision tree for loads and a different decision tree for stores. I do not plan to add more levels to the tree (at least for time being). I think that forming groups by alias sets is quite effective becuase TBAA oracle lookup is cheap and has good chance to disambiguate. For the remaining info tracked I plan simple flat (and capped by small constant) list of accesses. It indeed seems that ptr_deref_may_alias_ref_p_1 is precisely what I need which simplifies the patch. I did not know about it and simply followed for the main oracle does. Once the base/offset tracking is added I will need to figure out when the base pointers are same (or with a known offset) which is not readily available from ptr_deref_may_alias_ref_p_1, but we can do that step by step. Thanks a lot. I am re-testing the patch attached. OK if testing passes? 2020-09-24 Jan Hubicka * doc/invoke.texi: Document -fipa-modref, ipa-modref-max-bases, ipa-modref-max-refs, ipa-modref-max-accesses, ipa-modref-max-tests. * ipa-modref-tree.c (test_insert_search_collapse): Update. (test_merge): Update. (gt_ggc_mx): New function. * ipa-modref-tree.h (struct modref_access_node): New structure. (struct modref_ref_node): Add every_access and accesses array. (modref_ref_node::modref_ref_node): Update ctor. (modref_ref_node::search): New member function. (modref_ref_node::collapse): New member function. (modref_ref_node::insert_access): New member function. (modref_base_node::insert_ref): Do not collapse base if ref is 0. (modref_base_node::collapse): Copllapse also refs. (modref_tree): Add accesses. (modref_tree::modref_tree): Initialize max_accesses. (modref_tree::insert): Add access parameter. (modref_tree::cleanup): New member function. (modref_tree::merge): Add parm_map; merge accesses. (modref_tree::copy_from): New member function. (modref_tree::create_ggc): Add max_accesses. * ipa-modref.c (dump_access): New function. (dump_records): Dump accesses. (dump_lto_records): Dump accesses. (get_access): New function. (record_access): Record access. (record_access_lto): Record access. (analyze_call): Compute parm_map. (analyze_function): Update construction of modref records. (modref_summaries::duplicate): Likewise; use copy_from. (write_modref_records): Stream accesses. (read_modref_records): Sream accesses. (pass_ipa_modref::execute): Update call of merge. * params.opt (-param=modref-max-accesses): New. * tree-ssa-alias.c (alias_stats): Add modref_baseptr_tests. (dump_alias_stats): Update. (modref_may_conflict): Check accesses. (ref_maybe_used_by_call_p_1): Update call to modref_may_conflict. (call_may_clobber_ref_p_1): Update call to modref_may_conflict. gcc/testsuite/ChangeLog: 2020-09-24 Jan Hubicka * gcc.dg/tree-ssa/modref-1.c: New test. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 75203ba2420..623dfb8ac28 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -486,7 +486,7 @@ Objective-C and Objective-C++ Dialects}. -fgcse-sm -fhoist-adjacent-loads -fif-conversion @gol -fif-conversion2 -findirect-inlining @gol -finline-functions -finline-functions-called-once -finline-limit=@var{n} @gol --finline-small-functions -fipa-cp -fipa-cp-clone @gol +-finline-small-functions -fipa-modref -fipa-cp -fipa-cp-clone @gol -fipa-bit-cp -fipa-vrp -fipa-pta -fipa-profile -fipa-pure-const @gol -fipa-reference -fipa-reference-addressable @gol -fipa-stack-alignment -fipa-icf -fira-algorithm=@var{algorithm} @gol @@ -9688,6 +9688,7 @@ compilation time. -fif-conversion @gol -fif-conversion2 @gol -finline-functions-called-once @gol +-fipa-modref @gol -fipa-profile @gol -fipa-pure-const @gol -fipa-reference @gol @@ -10783,11 +10784,18 @@ default at any optimization level. @opindex fipa-profile Perform interprocedural profile propagation. The functions called only from cold functions are marked as cold. Also functions executed once (such as -@code{cold}, @code{noreturn}, static constructors or destructors) are identified. Cold -functions and loop less parts of functions executed once are then optimized for -size. +@code{cold}, @code{noreturn}, static constructors or destructors) are +identified. Cold functions and loop less parts of functions executed once are +then optimized for size. Enabled by default at @option{-O} and higher. +@item -fipa-modref +@opindex fipa-modref +Perform interprocedural mod/ref analysis. This optimization analyzes the side +effects of functions (memory locations that are modified or referenced) and +enables better optimization across the function call boundary. This flag is +enabled by default at @option{-O} and higher. + @item -fipa-cp @opindex fipa-cp Perform interprocedural constant propagation. @@ -12764,6 +12772,18 @@ Deeper chains are still handled by late inlining. Probability (in percent) that C++ inline function with comdat visibility are shared across multiple compilation units. +@item ipa-modref-max-bases +@item ipa-modref-max-refs +@item ipa-modref-max-accesses +Specifies the maximal number of base pointers, referneces and accesses stored +for a single function by mod/ref analysis. + +@item ipa-modref-max-tests +Specifies the maxmal number of tests alias oracle can perform to disambiguate +memory locations using the mod/ref information. This parameter ought to be +bigger than @option{--param ipa-modref-max-bases} and @option{--param +ipa-modref-max-refs}. + @item profile-func-internal-id A parameter to control whether to use function internal id in profile database lookup. If the value is 0, the compiler uses an id that diff --git a/gcc/ipa-modref-tree.c b/gcc/ipa-modref-tree.c index a84508a2268..499dc60b75e 100644 --- a/gcc/ipa-modref-tree.c +++ b/gcc/ipa-modref-tree.c @@ -35,12 +35,13 @@ test_insert_search_collapse () { modref_base_node *base_node; modref_ref_node *ref_node; + modref_access_node a = { -1 }; - modref_tree *t = new modref_tree(1, 2); + modref_tree *t = new modref_tree(1, 2, 2); ASSERT_FALSE (t->every_base); /* Insert into an empty tree. */ - t->insert (1, 2); + t->insert (1, 2, a); ASSERT_NE (t->bases, NULL); ASSERT_EQ (t->bases->length (), 1); ASSERT_FALSE (t->every_base); @@ -58,7 +59,7 @@ test_insert_search_collapse () ASSERT_EQ (ref_node->ref, 2); /* Insert when base exists but ref does not. */ - t->insert (1, 3); + t->insert (1, 3, a); ASSERT_NE (t->bases, NULL); ASSERT_EQ (t->bases->length (), 1); ASSERT_EQ (t->search (1), base_node); @@ -71,7 +72,7 @@ test_insert_search_collapse () /* Insert when base and ref exist, but access is not dominated by nor dominates other accesses. */ - t->insert (1, 2); + t->insert (1, 2, a); ASSERT_EQ (t->bases->length (), 1); ASSERT_EQ (t->search (1), base_node); @@ -79,12 +80,12 @@ test_insert_search_collapse () ASSERT_NE (ref_node, NULL); /* Insert when base and ref exist and access is dominated. */ - t->insert (1, 2); + t->insert (1, 2, a); ASSERT_EQ (t->search (1), base_node); ASSERT_EQ (base_node->search (2), ref_node); /* Insert ref to trigger ref list collapse for base 1. */ - t->insert (1, 4); + t->insert (1, 4, a); ASSERT_EQ (t->search (1), base_node); ASSERT_EQ (base_node->refs, NULL); ASSERT_EQ (base_node->search (2), NULL); @@ -92,7 +93,7 @@ test_insert_search_collapse () ASSERT_TRUE (base_node->every_ref); /* Further inserts to collapsed ref list are ignored. */ - t->insert (1, 5); + t->insert (1, 5, a); ASSERT_EQ (t->search (1), base_node); ASSERT_EQ (base_node->refs, NULL); ASSERT_EQ (base_node->search (2), NULL); @@ -100,13 +101,13 @@ test_insert_search_collapse () ASSERT_TRUE (base_node->every_ref); /* Insert base to trigger base list collapse. */ - t->insert (5, 6); + t->insert (5, 6, a); ASSERT_TRUE (t->every_base); ASSERT_EQ (t->bases, NULL); ASSERT_EQ (t->search (1), NULL); /* Further inserts to collapsed base list are ignored. */ - t->insert (7, 8); + t->insert (7, 8, a); ASSERT_TRUE (t->every_base); ASSERT_EQ (t->bases, NULL); ASSERT_EQ (t->search (1), NULL); @@ -117,24 +118,25 @@ test_merge () { modref_tree *t1, *t2; modref_base_node *base_node; - - t1 = new modref_tree(3, 4); - t1->insert (1, 1); - t1->insert (1, 2); - t1->insert (1, 3); - t1->insert (2, 1); - t1->insert (3, 1); - - t2 = new modref_tree(10, 10); - t2->insert (1, 2); - t2->insert (1, 3); - t2->insert (1, 4); - t2->insert (3, 2); - t2->insert (3, 3); - t2->insert (3, 4); - t2->insert (3, 5); - - t1->merge (t2); + modref_access_node a = { -1 }; + + t1 = new modref_tree(3, 4, 1); + t1->insert (1, 1, a); + t1->insert (1, 2, a); + t1->insert (1, 3, a); + t1->insert (2, 1, a); + t1->insert (3, 1, a); + + t2 = new modref_tree(10, 10, 10); + t2->insert (1, 2, a); + t2->insert (1, 3, a); + t2->insert (1, 4, a); + t2->insert (3, 2, a); + t2->insert (3, 3, a); + t2->insert (3, 4, a); + t2->insert (3, 5, a); + + t1->merge (t2, NULL); ASSERT_FALSE (t1->every_base); ASSERT_NE (t1->bases, NULL); @@ -222,11 +224,21 @@ void gt_pch_nx (modref_base_node*, gt_pointer_operator, void *) {} void gt_ggc_mx (modref_ref_node* &r) { ggc_test_and_set_mark (r); + if (r->accesses) + { + ggc_test_and_set_mark (r->accesses); + gt_ggc_mx (r->accesses); + } } void gt_ggc_mx (modref_ref_node* &r) { ggc_test_and_set_mark (r); + if (r->accesses) + { + ggc_test_and_set_mark (r->accesses); + gt_ggc_mx (r->accesses); + } if (r->ref) gt_ggc_mx (r->ref); } @@ -236,4 +248,6 @@ void gt_pch_nx (modref_ref_node*) {} void gt_pch_nx (modref_ref_node*, gt_pointer_operator, void *) {} void gt_pch_nx (modref_ref_node*, gt_pointer_operator, void *) {} - +void gt_ggc_mx (modref_access_node &) +{ +} diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h index 82e959a7d46..caf5d348dd8 100644 --- a/gcc/ipa-modref-tree.h +++ b/gcc/ipa-modref-tree.h @@ -18,20 +18,101 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ +/* modref_tree represent a decision tree that can be used by alias analysis + oracle to determine whether given memory access can be affected by a function + call. For every function we collect two trees, one for loads and other + for stores. Tree consist of following levels: + + 1) Base: this level represent base alias set of the acecess and refers + to sons (ref nodes). Flag all_refs means that all possible references + are aliasing. + + Because for LTO streaming we need to stream types rahter than alias sets + modref_base_node is implemented as a template. + 2) Ref: this level represent ref alias set and links to acesses unless + all_refs flag is et. + Again ref is an template to allow LTO streaming. + 3) Access: this level represent info about individual accesses. Presently + we record whether access is trhough a dereference of a function parameter +*/ + #ifndef GCC_MODREF_TREE_H #define GCC_MODREF_TREE_H struct ipa_modref_summary; +/* Memory access. */ +struct GTY(()) modref_access_node +{ + /* Index of parameter which specifies the base of access. -1 if base is not + a function parameter. */ + int parm_index; + + /* Return true if access node holds no useful info. */ + bool useful_p () + { + return parm_index != -1; + } +}; template struct GTY((user)) modref_ref_node { T ref; + bool every_access; + vec *accesses; modref_ref_node (T ref): - ref (ref) + ref (ref), + every_access (false), + accesses (NULL) {} + + /* Search REF; return NULL if failed. */ + modref_access_node *search (modref_access_node access) + { + size_t i; + modref_access_node *a; + FOR_EACH_VEC_SAFE_ELT (accesses, i, a) + if (a->parm_index == access.parm_index) + return a; + return NULL; + } + + /* Collapse the tree. */ + void collapse () + { + vec_free (accesses); + accesses = NULL; + every_access = true; + } + + /* Insert access with OFFSET and SIZE. + Collapse tree if it has more than MAX_ACCESSES entries. */ + void insert_access (modref_access_node a, size_t max_accesses) + { + /* If this base->ref pair has no access information, bail out. */ + if (every_access) + return; + + /* Otherwise, insert a node for the ref of the access under the base. */ + modref_access_node *access_node = search (a); + if (access_node) + return; + + /* If this base->ref pair has too many accesses stored, we will clear + all accesses and bail out. */ + if ((accesses && accesses->length () >= max_accesses) + || !a.useful_p ()) + { + if (dump_file && a.useful_p ()) + fprintf (dump_file, + "--param param=modref-max-accesses limit reached\n"); + collapse (); + return; + } + vec_safe_push (accesses, a); + } }; /* Base of an access. */ @@ -67,12 +148,6 @@ struct GTY((user)) modref_base_node if (every_ref) return NULL; - if (!ref) - { - collapse (); - return NULL; - } - /* Otherwise, insert a node for the ref of the access under the base. */ ref_node = search (ref); if (ref_node) @@ -101,7 +176,10 @@ struct GTY((user)) modref_base_node if (refs) { FOR_EACH_VEC_SAFE_ELT (refs, i, r) - ggc_free (r); + { + r->collapse (); + ggc_free (r); + } vec_free (refs); } refs = NULL; @@ -116,12 +194,14 @@ struct GTY((user)) modref_tree vec *, va_gc> *bases; size_t max_bases; size_t max_refs; + size_t max_accesses; bool every_base; - modref_tree (size_t max_bases, size_t max_refs): + modref_tree (size_t max_bases, size_t max_refs, size_t max_accesses): bases (NULL), max_bases (max_bases), max_refs (max_refs), + max_accesses (max_accesses), every_base (false) {} modref_base_node *insert_base (T base) @@ -153,31 +233,92 @@ struct GTY((user)) modref_tree } /* Insert memory access to the tree. */ - void insert (T base, T ref) + void insert (T base, T ref, modref_access_node a) { - modref_base_node *base_node; - - base_node = insert_base (base); - - if (!base && !ref) + /* No useful information tracked; collapse everything. */ + if (!base && !ref && !a.useful_p ()) { collapse (); return; } + + modref_base_node *base_node = insert_base (base); if (!base_node) return; gcc_assert (search (base) != NULL); - base_node->insert_ref (ref, max_refs); + modref_ref_node *ref_node = base_node->insert_ref (ref, max_refs); + + /* No useful ref information and no useful base; collapse everyting. */ if (!base && base_node->every_ref) { collapse (); return; } + if (ref_node) + { + /* No useful ref and access; collapse ref. */ + if (!ref && !a.useful_p ()) + ref_node->collapse (); + else + { + ref_node->insert_access (a, max_accesses); + /* If ref has collapses and there is no useful base; collapse + everything. */ + if (!base && !ref && ref_node->every_access) + collapse (); + } + } } - /* Merge OTHER into the tree. */ - void merge (modref_tree *other) + /* Remove tree branches that are not useful (i.e. they will allways pass). */ + + void cleanup () + { + size_t i, j; + modref_base_node *base_node; + modref_ref_node *ref_node; + + if (!bases) + return; + + for (i = 0; vec_safe_iterate (bases, i, &base_node);) + { + if (base_node->refs) + for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);) + { + if (!ref_node->every_access + && (!ref_node->accesses + || !ref_node->accesses->length ())) + { + base_node->refs->unordered_remove (j); + vec_free (ref_node->accesses); + ggc_delete (ref_node); + } + else + j++; + } + if (!base_node->every_ref + && (!base_node->refs || !base_node->refs->length ())) + { + bases->unordered_remove (i); + vec_free (base_node->refs); + ggc_delete (base_node); + } + else + i++; + } + if (bases && !bases->length ()) + { + vec_free (bases); + bases = NULL; + } + } + + /* Merge OTHER into the tree. + PARM_MAP, if non-NULL, maps parm indexes of callee to caller. -2 is used + to signalize that parameter is local and does not need to be tracked. */ + void merge (modref_tree *other, vec *parm_map) { if (!other) return; @@ -187,9 +328,10 @@ struct GTY((user)) modref_tree return; } - size_t i, j; + size_t i, j, k; modref_base_node *base_node, *my_base_node; modref_ref_node *ref_node, *my_ref_node; + modref_access_node *access_node; FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node) { my_base_node = insert_base (base_node->base); @@ -207,8 +349,36 @@ struct GTY((user)) modref_tree my_ref_node = my_base_node->insert_ref (ref_node->ref, max_refs); if (!my_ref_node) continue; + + if (ref_node->every_access) + { + my_ref_node->collapse (); + continue; + } + FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node) + { + modref_access_node a = *access_node; + if (a.parm_index != -1 && parm_map) + { + if (a.parm_index >= (int)parm_map->length ()) + a.parm_index = -1; + else if ((*parm_map) [a.parm_index] == -2) + continue; + else + a.parm_index = (*parm_map) [a.parm_index]; + } + my_ref_node->insert_access (a, max_accesses); + } } } + if (parm_map) + cleanup (); + } + + /* Copy OTHER to THIS. */ + void copy_from (modref_tree *other) + { + merge (other, NULL); } /* Search BASE in tree; return NULL if failed. */ @@ -225,12 +395,14 @@ struct GTY((user)) modref_tree /* Return ggc allocated instance. We explicitly call destructors via ggc_delete and do not want finalizers to be registered and called at the garbage collection time. */ - static modref_tree *create_ggc (size_t max_bases, size_t max_refs) + static modref_tree *create_ggc (size_t max_bases, size_t max_refs, + size_t max_accesses) { return new (ggc_alloc_no_dtor> ()) - modref_tree (max_bases, max_refs); + modref_tree (max_bases, max_refs, max_accesses); } + /* Remove all records and mark tree to alias with everything. */ void collapse () { size_t i; @@ -248,6 +420,8 @@ struct GTY((user)) modref_tree bases = NULL; every_base = true; } + + /* Release memory. */ ~modref_tree () { collapse (); diff --git a/gcc/ipa-modref.c b/gcc/ipa-modref.c index 43545c1fb09..aa6929ff010 100644 --- a/gcc/ipa-modref.c +++ b/gcc/ipa-modref.c @@ -20,14 +20,8 @@ along with GCC; see the file COPYING3. If not see /* Mod/ref pass records summary about loads and stores performed by the function. This is later used by alias analysis to disambiguate memory - accesses across function calls. The summary has a form of decision tree and - contains: - - - base alias set - and for each: - - ref alias set - - In future more information will be tracked. + accesses across function calls. The summary has a form of decision tree + described in ipa-modref-tree.h. This file contains a tree pass and an IPA pass. Both performs the same analys however tree pass is executed during early and late optimization @@ -144,6 +138,14 @@ modref_summary::useful_p (int ecf_flags) return stores && !loads->every_base; } +/* Dump A to OUT. */ + +static void +dump_access (modref_access_node *a, FILE *out) +{ + fprintf (out, " Parm %i\n", a->parm_index); +} + /* Dump records TT to OUT. */ static void @@ -171,6 +173,15 @@ dump_records (modref_records *tt, FILE *out) FOR_EACH_VEC_SAFE_ELT (n->refs, j, r) { fprintf (out, " Ref %i: alias set %i\n", (int)j, r->ref); + if (r->every_access) + { + fprintf (out, " Every access\n"); + continue; + } + size_t k; + modref_access_node *a; + FOR_EACH_VEC_SAFE_ELT (r->accesses, k, a) + dump_access (a, out); } } } @@ -208,6 +219,15 @@ dump_lto_records (modref_records_lto *tt, FILE *out) print_generic_expr (dump_file, r->ref); fprintf (out, " (alias set %i)\n", r->ref ? get_alias_set (r->ref) : 0); + if (r->every_access) + { + fprintf (out, " Every access\n"); + continue; + } + size_t k; + modref_access_node *a; + FOR_EACH_VEC_SAFE_ELT (r->accesses, k, a) + dump_access (a, out); } } } @@ -268,6 +288,43 @@ get_modref_function_summary (cgraph_node *func) return NULL; } +/* Construct modref_access_node from REF. */ +static modref_access_node +get_access (ao_ref *ref) +{ + modref_access_node a; + tree base; + + base = ref->ref; + while (handled_component_p (base)) + base = TREE_OPERAND (base, 0); + if (TREE_CODE (base) == MEM_REF || TREE_CODE (base) == TARGET_MEM_REF) + { + base = TREE_OPERAND (base, 0); + if (TREE_CODE (base) == SSA_NAME + && SSA_NAME_IS_DEFAULT_DEF (base) + && TREE_CODE (SSA_NAME_VAR (base)) == PARM_DECL) + { + a.parm_index = 0; + for (tree t = DECL_ARGUMENTS (current_function_decl); + t != SSA_NAME_VAR (base); t = DECL_CHAIN (t)) + { + if (!t) + { + a.parm_index = -1; + break; + } + a.parm_index++; + } + } + else + a.parm_index = -1; + } + else + a.parm_index = -1; + return a; +} + /* Record access into the modref_records data structure. */ static void @@ -277,12 +334,13 @@ record_access (modref_records *tt, ao_ref *ref) : ao_ref_base_alias_set (ref); alias_set_type ref_set = !flag_strict_aliasing ? 0 : (ao_ref_alias_set (ref)); + modref_access_node a = get_access (ref); if (dump_file) { - fprintf (dump_file, " - Recording base_set=%i ref_set=%i\n", - base_set, ref_set); + fprintf (dump_file, " - Recording base_set=%i ref_set=%i parm=%i\n", + base_set, ref_set, a.parm_index); } - tt->insert (base_set, ref_set); + tt->insert (base_set, ref_set, a); } /* IPA version of record_access_tree. */ @@ -335,6 +393,7 @@ record_access_lto (modref_records_lto *tt, ao_ref *ref) || variably_modified_type_p (ref_type, NULL_TREE))) ref_type = NULL_TREE; } + modref_access_node a = get_access (ref); if (dump_file) { fprintf (dump_file, " - Recording base type:"); @@ -342,11 +401,12 @@ record_access_lto (modref_records_lto *tt, ao_ref *ref) fprintf (dump_file, " (alias set %i) ref type:", base_type ? get_alias_set (base_type) : 0); print_generic_expr (dump_file, ref_type); - fprintf (dump_file, " (alias set %i)\n", - ref_type ? get_alias_set (ref_type) : 0); + fprintf (dump_file, " (alias set %i) parm:%i\n", + ref_type ? get_alias_set (ref_type) : 0, + a.parm_index); } - tt->insert (base_type, ref_type); + tt->insert (base_type, ref_type, a); } /* Returns true if and only if we should store the access to EXPR. @@ -490,17 +550,47 @@ analyze_call (modref_summary *cur_summary, return false; } + auto_vec parm_map; + + parm_map.safe_grow (gimple_call_num_args (stmt)); + for (unsigned i = 0; i < gimple_call_num_args (stmt); i++) + { + tree op = gimple_call_arg (stmt, i); + STRIP_NOPS (op); + if (TREE_CODE (op) == SSA_NAME + && SSA_NAME_IS_DEFAULT_DEF (op) + && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL) + { + int index = 0; + for (tree t = DECL_ARGUMENTS (current_function_decl); + t != SSA_NAME_VAR (op); t = DECL_CHAIN (t)) + { + if (!t) + { + index = -1; + break; + } + index++; + } + parm_map[i] = index; + } + else if (points_to_local_or_readonly_memory_p (op)) + parm_map[i] = -2; + else + parm_map[i] = -1; + } + /* Merge with callee's summary. */ if (cur_summary->loads) - cur_summary->loads->merge (callee_summary->loads); + cur_summary->loads->merge (callee_summary->loads, &parm_map); if (cur_summary->loads_lto) - cur_summary->loads_lto->merge (callee_summary->loads_lto); + cur_summary->loads_lto->merge (callee_summary->loads_lto, &parm_map); if (!ignore_stores) { if (cur_summary->stores) - cur_summary->stores->merge (callee_summary->stores); + cur_summary->stores->merge (callee_summary->stores, &parm_map); if (cur_summary->stores_lto) - cur_summary->stores_lto->merge (callee_summary->stores_lto); + cur_summary->stores_lto->merge (callee_summary->stores_lto, &parm_map); } return true; @@ -638,21 +728,25 @@ analyze_function (function *f, bool ipa) { gcc_assert (!summary->loads); summary->loads = modref_records::create_ggc (param_modref_max_bases, - param_modref_max_refs); + param_modref_max_refs, + param_modref_max_accesses); gcc_assert (!summary->stores); summary->stores = modref_records::create_ggc (param_modref_max_bases, - param_modref_max_refs); + param_modref_max_refs, + param_modref_max_accesses); } if (lto) { gcc_assert (!summary->loads_lto); summary->loads_lto = modref_records_lto::create_ggc (param_modref_max_bases, - param_modref_max_refs); + param_modref_max_refs, + param_modref_max_accesses); gcc_assert (!summary->stores_lto); summary->stores_lto = modref_records_lto::create_ggc (param_modref_max_bases, - param_modref_max_refs); + param_modref_max_refs, + param_modref_max_accesses); } summary->finished = false; int ecf_flags = flags_from_decl_or_type (current_function_decl); @@ -730,29 +824,33 @@ modref_summaries::duplicate (cgraph_node *, cgraph_node *, { dst_data->stores = modref_records::create_ggc (src_data->stores->max_bases, - src_data->stores->max_refs); - dst_data->stores->merge (src_data->stores); + src_data->stores->max_refs, + src_data->stores->max_accesses); + dst_data->stores->copy_from (src_data->stores); } if (src_data->loads) { dst_data->loads = modref_records::create_ggc (src_data->loads->max_bases, - src_data->loads->max_refs); - dst_data->loads->merge (src_data->loads); + src_data->loads->max_refs, + src_data->loads->max_accesses); + dst_data->loads->copy_from (src_data->loads); } if (src_data->stores_lto) { dst_data->stores_lto = modref_records_lto::create_ggc (src_data->stores_lto->max_bases, - src_data->stores_lto->max_refs); - dst_data->stores_lto->merge (src_data->stores_lto); + src_data->stores_lto->max_refs, + src_data->stores_lto->max_accesses); + dst_data->stores_lto->copy_from (src_data->stores_lto); } if (src_data->loads_lto) { dst_data->loads_lto = modref_records_lto::create_ggc (src_data->loads_lto->max_bases, - src_data->loads_lto->max_refs); - dst_data->loads_lto->merge (src_data->loads_lto); + src_data->loads_lto->max_refs, + src_data->stores_lto->max_accesses); + dst_data->loads_lto->copy_from (src_data->loads_lto); } } @@ -796,6 +894,7 @@ write_modref_records (modref_records_lto *tt, struct output_block *ob) { streamer_write_uhwi (ob, tt->max_bases); streamer_write_uhwi (ob, tt->max_refs); + streamer_write_uhwi (ob, tt->max_accesses); streamer_write_uhwi (ob, tt->every_base); streamer_write_uhwi (ob, vec_safe_length (tt->bases)); @@ -807,11 +906,19 @@ write_modref_records (modref_records_lto *tt, struct output_block *ob) streamer_write_uhwi (ob, base_node->every_ref); streamer_write_uhwi (ob, vec_safe_length (base_node->refs)); + size_t j; modref_ref_node *ref_node; FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node) { stream_write_tree (ob, ref_node->ref, true); + streamer_write_uhwi (ob, ref_node->every_access); + streamer_write_uhwi (ob, vec_safe_length (ref_node->accesses)); + + size_t k; + modref_access_node *access_node; + FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node) + streamer_write_uhwi (ob, access_node->parm_index); } } } @@ -828,13 +935,16 @@ read_modref_records (lto_input_block *ib, struct data_in *data_in, { size_t max_bases = streamer_read_uhwi (ib); size_t max_refs = streamer_read_uhwi (ib); + size_t max_accesses = streamer_read_uhwi (ib); /* Decide whether we want to turn LTO data types to non-LTO (i.e. when LTO re-streaming is not going to happen). */ if (flag_wpa || flag_incremental_link == INCREMENTAL_LINK_LTO) - *lto_ret = modref_records_lto::create_ggc (max_bases, max_refs); + *lto_ret = modref_records_lto::create_ggc (max_bases, max_refs, + max_accesses); else - *nolto_ret = modref_records::create_ggc (max_bases, max_refs); + *nolto_ret = modref_records::create_ggc (max_bases, max_refs, + max_accesses); size_t every_base = streamer_read_uhwi (ib); size_t nbase = streamer_read_uhwi (ib); @@ -897,16 +1007,43 @@ read_modref_records (lto_input_block *ib, struct data_in *data_in, print_generic_expr (dump_file, ref_tree); fprintf (dump_file, "\n"); } - base_tree = NULL; + ref_tree = NULL; } + modref_ref_node *nolto_ref_node = NULL; + modref_ref_node *lto_ref_node = NULL; + if (nolto_base_node) - nolto_base_node->insert_ref (ref_tree ? get_alias_set (ref_tree) - : 0, max_refs); + nolto_ref_node + = nolto_base_node->insert_ref (ref_tree + ? get_alias_set (ref_tree) : 0, + max_refs); if (lto_base_node) - lto_base_node->insert_ref (ref_tree, max_refs); + lto_ref_node = lto_base_node->insert_ref (ref_tree, max_refs); + + size_t every_access = streamer_read_uhwi (ib); + size_t naccesses = streamer_read_uhwi (ib); + + if (nolto_ref_node) + nolto_ref_node->every_access = every_access; + if (lto_ref_node) + lto_ref_node->every_access = every_access; + + for (size_t k = 0; k < naccesses; k++) + { + int parm_index = streamer_read_uhwi (ib); + modref_access_node a = {parm_index}; + if (nolto_ref_node) + nolto_ref_node->insert_access (a, max_accesses); + if (lto_ref_node) + lto_ref_node->insert_access (a, max_accesses); + } } } + if (*lto_ret) + (*lto_ret)->cleanup (); + if (*nolto_ret) + (*nolto_ret)->cleanup (); } /* Callback for write_summary. */ @@ -1305,19 +1442,22 @@ unsigned int pass_ipa_modref::execute (function *) } } + auto_vec parm_map; + /* TODO: compute parm_map. */ + /* Merge in callee's information. */ if (callee_summary->loads && callee_summary->loads != loads) - loads->merge (callee_summary->loads); + loads->merge (callee_summary->loads, &parm_map); if (callee_summary->stores && callee_summary->stores != stores) - stores->merge (callee_summary->stores); + stores->merge (callee_summary->stores, &parm_map); if (callee_summary->loads_lto && callee_summary->loads_lto != loads_lto) - loads_lto->merge (callee_summary->loads_lto); + loads_lto->merge (callee_summary->loads_lto, &parm_map); if (callee_summary->stores_lto && callee_summary->stores_lto != stores_lto) - stores_lto->merge (callee_summary->stores_lto); + stores_lto->merge (callee_summary->stores_lto, &parm_map); } } @@ -1351,13 +1491,13 @@ unsigned int pass_ipa_modref::execute (function *) else { if (loads) - cur_summary->loads->merge (loads); + cur_summary->loads->merge (loads, NULL); if (stores) - cur_summary->stores->merge (stores); + cur_summary->stores->merge (stores, NULL); if (loads_lto) - cur_summary->loads_lto->merge (loads_lto); + cur_summary->loads_lto->merge (loads_lto, NULL); if (stores_lto) - cur_summary->stores_lto->merge (stores_lto); + cur_summary->stores_lto->merge (stores_lto, NULL); } cur_summary->finished = true; if (dump_file) diff --git a/gcc/params.opt b/gcc/params.opt index 5f2e11d6c57..5bc7e1619c5 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -882,7 +882,11 @@ Maximum number of bases stored in each modref tree. -param=modref-max-refs= Common Joined UInteger Var(param_modref_max_refs) Init(16) -Maximum number of refs stored in each modref tree. +Maximum number of references stored in each modref base. + +-param=modref-max-accesses= +Common Joined UInteger Var(param_modref_max_accesses) Init(16) +Maximum number of accesse stored in each modref reference. -param=modref-max-tests= Common Joined UInteger Var(param_modref_max_tests) Init(64) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-1.c new file mode 100644 index 00000000000..a80ca6b67c4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-1.c @@ -0,0 +1,45 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +int p,q,r,s,*ptr=&q, *ptr2=&p; +__attribute__ ((noinline)) +int +test (int *p) +{ + *p = 1; +} +int +test1() +{ + q = 123; + test(&p); + return q; +} +int +test2() +{ + int *ptr = p ? &q : &s; + *ptr = 124; + test(&p); + return *ptr; +} +int +test3() +{ + int *ptr = p ? &p : &s; + q = 125; + test(ptr); + return q; +} +int +test4() +{ + int *ptr1 = p ? &q : &s; + int *ptr = p ? &r : &p; + *ptr1 = 126; + test(ptr); + return *ptr1; +} +/* { dg-final { scan-tree-dump "return 123" "optimized"} } */ +/* { dg-final { scan-tree-dump "return 124" "optimized"} } */ +/* { dg-final { scan-tree-dump "return 125" "optimized"} } */ +/* { dg-final { scan-tree-dump "return 126" "optimized"} } */ diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 18ff529b491..fe390d4ffbe 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -114,6 +114,7 @@ static struct { unsigned HOST_WIDE_INT modref_clobber_may_alias; unsigned HOST_WIDE_INT modref_clobber_no_alias; unsigned HOST_WIDE_INT modref_tests; + unsigned HOST_WIDE_INT modref_baseptr_tests; } alias_stats; void @@ -169,13 +170,18 @@ dump_alias_stats (FILE *s) + alias_stats.modref_use_may_alias); fprintf (s, " modref clobber: " HOST_WIDE_INT_PRINT_DEC" disambiguations, " - HOST_WIDE_INT_PRINT_DEC" queries\n " - HOST_WIDE_INT_PRINT_DEC" tbaa queries (%f per modref query)\n", + HOST_WIDE_INT_PRINT_DEC" queries\n" + " " HOST_WIDE_INT_PRINT_DEC" tbaa queries (%f per modref query)\n" + " " HOST_WIDE_INT_PRINT_DEC" base compares (%f per modref query)\n", alias_stats.modref_clobber_no_alias, alias_stats.modref_clobber_no_alias + alias_stats.modref_clobber_may_alias, alias_stats.modref_tests, ((double)alias_stats.modref_tests) + / (alias_stats.modref_clobber_no_alias + + alias_stats.modref_clobber_may_alias), + alias_stats.modref_baseptr_tests, + ((double)alias_stats.modref_baseptr_tests) / (alias_stats.modref_clobber_no_alias + alias_stats.modref_clobber_may_alias)); } @@ -2423,12 +2429,13 @@ refs_output_dependent_p (tree store1, tree store2) IF TBAA_P is true, use TBAA oracle. */ static bool -modref_may_conflict (modref_tree *tt, ao_ref *ref, bool tbaa_p) +modref_may_conflict (const gimple *stmt, + modref_tree *tt, ao_ref *ref, bool tbaa_p) { alias_set_type base_set, ref_set; modref_base_node *base_node; modref_ref_node *ref_node; - size_t i, j; + size_t i, j, k; if (tt->every_base) return true; @@ -2440,37 +2447,57 @@ modref_may_conflict (modref_tree *tt, ao_ref *ref, bool tbaa_p) int num_tests = 0, max_tests = param_modref_max_tests; FOR_EACH_VEC_SAFE_ELT (tt->bases, i, base_node) { - if (base_node->every_ref) - return true; - - if (!base_node->base) - return true; - if (tbaa_p && flag_strict_aliasing) { + if (num_tests >= max_tests) + return true; alias_stats.modref_tests++; if (!alias_sets_conflict_p (base_set, base_node->base)) continue; num_tests++; } - else - return true; - if (num_tests >= max_tests) + + if (base_node->every_ref) return true; FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node) { /* Do not repeat same test as before. */ - if (ref_set == base_set && base_node->base == ref_node->ref) - return true; - if (!flag_strict_aliasing) - return true; - alias_stats.modref_tests++; - if (alias_sets_conflict_p (ref_set, ref_node->ref)) - return true; - num_tests++; - if (num_tests >= max_tests) + if ((ref_set != base_set || base_node->base != ref_node->ref) + && tbaa_p && flag_strict_aliasing) + { + if (num_tests >= max_tests) + return true; + alias_stats.modref_tests++; + if (!alias_sets_conflict_p (ref_set, ref_node->ref)) + continue; + num_tests++; + } + + /* TBAA checks did not disambiguate, try to use base pointer, for + that we however need to have ref->ref. */ + if (ref_node->every_access || !ref->ref) return true; + + modref_access_node *access_node; + FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node) + { + if (num_tests >= max_tests) + return true; + + if (access_node->parm_index == -1 + || (unsigned)access_node->parm_index + >= gimple_call_num_args (stmt)) + return true; + + + alias_stats.modref_baseptr_tests++; + + if (ptr_deref_may_alias_ref_p_1 + (gimple_call_arg (stmt, access_node->parm_index), ref)) + return true; + num_tests++; + } } } return false; @@ -2510,7 +2537,7 @@ ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p) modref_summary *summary = get_modref_function_summary (node); if (summary) { - if (!modref_may_conflict (summary->loads, ref, tbaa_p)) + if (!modref_may_conflict (call, summary->loads, ref, tbaa_p)) { alias_stats.modref_use_no_alias++; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -2934,7 +2961,7 @@ call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref, bool tbaa_p) modref_summary *summary = get_modref_function_summary (node); if (summary) { - if (!modref_may_conflict (summary->stores, ref, tbaa_p)) + if (!modref_may_conflict (call, summary->stores, ref, tbaa_p)) { alias_stats.modref_clobber_no_alias++; if (dump_file && (dump_flags & TDF_DETAILS))