From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x641.google.com (mail-ej1-x641.google.com [IPv6:2a00:1450:4864:20::641]) by sourceware.org (Postfix) with ESMTPS id AFEC4385780E for ; Thu, 24 Sep 2020 11:31:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org AFEC4385780E Received: by mail-ej1-x641.google.com with SMTP id gr14so4028852ejb.1 for ; Thu, 24 Sep 2020 04:31:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=YcFsI9LQjR9Ov6NWLUgesQd81sHOH/2IchA0cAkcj94=; b=Fq8auX0EaBxTepaWG3Vw6JiTNkTlKRVnS90p/TsO+zpemJu0xXctfQGI6SV3IGl1+C bAQ2FB/PaFD62nuA9soNq6CjnUCzMunTQriMkjpI2LOCv5BLXC1LYTJoxeCqAtUozy2t tGw8YiBTyGq2ztk/tlW+Ik7goBI1rFD3kHDUbvt/zEick1fOxKlXu0aQ0JFslPj4AEWZ KXxCb8N+FVbI73/ECsbWJQ5PK3PDyHU7Xd+7THCWEzqU5KlHuhjWJzhALYflyecChlgE eJthbLKOzZLQfUwsIUBI89eEYlY03ZmOzzXol+RX5itYuhXDKoOKUumkOPT3Q3u3AabZ A/Aw== X-Gm-Message-State: AOAM532xfviMbSOYlMY4GnjxTn/dolmNiRl7IBxEuayphcPLxFo0jM7g FX+/4lU27OtyPjT/s+RRsa9VWvocHx0hKRkr1IVJE67EVX4= X-Google-Smtp-Source: ABdhPJxHDAiHqWpiruCK3ys7lqop2N/0odLQJN+/MFNR8E5LDM7tXa+sPByBQ8arA+1EcCkljmEJh4JcKardMlKJ6+Y= X-Received: by 2002:a17:906:71c9:: with SMTP id i9mr510744ejk.250.1600947092108; Thu, 24 Sep 2020 04:31:32 -0700 (PDT) MIME-Version: 1.0 References: <20200924090555.GG6758@kam.mff.cuni.cz> <20200924105442.GA34649@kam.mff.cuni.cz> <20200924112635.GA59363@kam.mff.cuni.cz> In-Reply-To: <20200924112635.GA59363@kam.mff.cuni.cz> From: Richard Biener Date: Thu, 24 Sep 2020 13:31:21 +0200 Message-ID: Subject: Re: Add access through parameter derference tracking to modref To: Jan Hubicka Cc: GCC Patches , d@dcepelik.cz Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-6.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, 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:31:38 -0000 On Thu, Sep 24, 2020 at 1:26 PM Jan Hubicka wrote: > > > > > > > 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? OK. Richard. > 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))