[Bug tree-optimization/39074] [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong
-- jsm28 at gcc dot gnu dot org changed: What|Removed |Added Priority|P3 |P2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074
[Bug tree-optimization/39074] [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong
--- Comment #16 from rguenth at gcc dot gnu dot org 2009-02-06 09:17 --- Subject: Bug 39074 Author: rguenth Date: Fri Feb 6 09:17:19 2009 New Revision: 143983 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=143983 Log: 2009-02-06 Richard Guenther rguent...@suse.de PR tree-optimization/39074 * tree-ssa-structalias.c (storedanything_id, var_storedanything, storedanything_tree): New. (do_ds_constraint): Simplify ANYTHING shortcutting. Update the STOREDANYTHING solution if the lhs solution contains ANYTHING. (build_pred_graph): Add edges from STOREDANYTHING to all non-direct nodes. (get_constraint_for_1): CONSTRUCTOR is a zero-initializer. Generate NOTHING for it. (init_base_vars): Initialize STOREDANYTHING. (compute_points_to_sets): Free substitution info after building the succ graph. (ipa_pta_execute): Likewise. * gcc.dg/torture/pr39074.c: New testcase. * gcc.dg/torture/pr39074-2.c: Likewise. * gcc.dg/torture/pr39074-3.c: Likewise. Added: branches/alias-improvements/gcc/testsuite/gcc.dg/torture/pr39074-2.c branches/alias-improvements/gcc/testsuite/gcc.dg/torture/pr39074-3.c branches/alias-improvements/gcc/testsuite/gcc.dg/torture/pr39074.c Modified: branches/alias-improvements/gcc/ChangeLog.alias branches/alias-improvements/gcc/tree-ssa-structalias.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074
[Bug tree-optimization/39074] [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong
--- Comment #12 from rguenth at gcc dot gnu dot org 2009-02-04 12:37 --- Which makes it a regression. -- rguenth at gcc dot gnu dot org changed: What|Removed |Added Summary|PTA constraint processing |[4.2/4.3/4.4 Regression] PTA |for *x = y is wrong |constraint processing for *x ||= y is wrong Target Milestone|--- |4.2.5 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074
[Bug tree-optimization/39074] [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong
--- Comment #13 from dberlin at gcc dot gnu dot org 2009-02-04 16:09 --- Subject: Re: PTA constraint processing for *x = y is wrong I don't remember offhand. At one point during 4.2 we used to compute the anything set exactly, and it led to massive issues. Of course, most of those were because the anything set had hundreds or thousands of SFT's :). I'm happy to go with your idea for fixing since fixing shortcutting won't fix it, except for two things: 1. ANYTHING is really limited to all addressable variables (IE address taken and escaping), instead of all variables. It was never meant to represent completely unknown (IE user has set pointer to (char *) 0xdeadbeef). ISTM the set you union in should be based on CALLUSED and ESCAPED or something thereof, or at least should be computable with constraints during solving, and unioned in when it changes. The way off the top of my head to do this is to simply stop using ANYTHING, and use ANYTHING directly, and then have ANYTHING = CALLUSED and ANYTHING = ESCAPED. Assuming you hate that idea for some reason 2. It's probably a lot faster to make a bitmap of these and update it, then union in the bitmap, than to iterate over all varinfos all the time. ISTM you are trying to avoid doing #1 by adding all variables, even though this is going to give you worse than necessary results. Intel actually iterates points-to solving in order to compute the set of nonlocal locations without explicitly adding the set everywhere. See the description of nloc in section 4.1 of On the Importance of Points=To Analysis and Other Memory Disambiguation Methods For C Programs On Wed, Feb 4, 2009 at 4:35 AM, rguenther at suse dot de gcc-bugzi...@gcc.gnu.org wrote: --- Comment #8 from rguenther at suse dot de 2009-02-04 09:35 --- Subject: Re: PTA constraint processing for *x = y is wrong On Wed, 4 Feb 2009, dberlin at dberlin dot org wrote: --- Comment #7 from dberlin at gcc dot gnu dot org 2009-02-04 00:29 --- Subject: Re: PTA constraint processing for *x = y is wrong On Tue, Feb 3, 2009 at 9:24 AM, rguenther at suse dot de gcc-bugzi...@gcc.gnu.org wrote: --- Comment #6 from rguenther at suse dot de 2009-02-03 14:24 --- Subject: Re: PTA constraint processing for *x = y is wrong On Tue, 3 Feb 2009, dberlin at dberlin dot org wrote: Subject: Re: PTA constraint processing for *x = y is wrong There used to be a *ANYTHING = ANYTHING constraint + ANYTHING containing all the variables pointing to ANYTHING that would have taken care of this. You certainly don't want to dynamically add all variables at solving time yourself, since that can't be optimized. This is the reason it works for ESCAPED, there we have an *ESCAPED = ESCAPED constraint. It doesn't work for CALLUSED though, I have a simple fix (CALLUSED is not big usually, so just not using it as a placeholder fixes the issue here). For the ANYTHING problem I have just dealt with it in do_ds_constraint (I'll post an updated patch soon after testing finished). My onl concern is practicality. The last time I did this solely at solving time it was ridiculously slow on large cases, since the solver is much better at difference propagation. Do you remember what testcase(s) this was? I can certainly time removing the shortcutting against handling *ANYTHING (and I'll try to come up with a testcase that is not fixed with just removing the shortcutting). Richard. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074 --- You are receiving this mail because: --- You are on the CC list for the bug, or are watching someone who is. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074
[Bug tree-optimization/39074] [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong
--- Comment #14 from rguenther at suse dot de 2009-02-04 16:26 --- Subject: Re: [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong On Wed, 4 Feb 2009, dberlin at dberlin dot org wrote: --- Comment #13 from dberlin at gcc dot gnu dot org 2009-02-04 16:09 --- Subject: Re: PTA constraint processing for *x = y is wrong I don't remember offhand. At one point during 4.2 we used to compute the anything set exactly, and it led to massive issues. Of course, most of those were because the anything set had hundreds or thousands of SFT's :). I'm happy to go with your idea for fixing since fixing shortcutting won't fix it, except for two things: 1. ANYTHING is really limited to all addressable variables (IE address taken and escaping), instead of all variables. It was never meant to represent completely unknown (IE user has set pointer to (char *) 0xdeadbeef). Yes, is there a bitmap / array in the PTA graph that I can iterate over instead of all vars? ISTM the set you union in should be based on CALLUSED and ESCAPED or something thereof, or at least should be computable with constraints during solving, and unioned in when it changes. Ah, you mean whenever I see *ANYTHING = x union x into a new STORE_TO_ANYTHING solution and have an explicit *ANYTHING = STORE_TO_ANYTHING constraint (which I of course need to handle properly in do_ds_constraint)? That may be indeed faster. The way off the top of my head to do this is to simply stop using ANYTHING, and use ANYTHING directly, and then have ANYTHING = CALLUSED and ANYTHING = ESCAPED. I don't think CALLUSED or ESCAPED are related here. You can store non-addressables into *ANYTHING. Assuming you hate that idea for some reason 2. It's probably a lot faster to make a bitmap of these and update it, then union in the bitmap, than to iterate over all varinfos all the time. ISTM you are trying to avoid doing #1 by adding all variables, even though this is going to give you worse than necessary results. Intel actually iterates points-to solving in order to compute the set of nonlocal locations without explicitly adding the set everywhere. See the description of nloc in section 4.1 of On the Importance of Points=To Analysis and Other Memory Disambiguation Methods For C Programs I'll have a look there. Richard. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074
[Bug tree-optimization/39074] [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong
--- Comment #15 from dberlin at gcc dot gnu dot org 2009-02-04 16:37 --- Subject: Re: [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong On Wed, Feb 4, 2009 at 11:26 AM, rguenther at suse dot de gcc-bugzi...@gcc.gnu.org wrote: --- Comment #14 from rguenther at suse dot de 2009-02-04 16:26 --- Subject: Re: [4.2/4.3/4.4 Regression] PTA constraint processing for *x = y is wrong On Wed, 4 Feb 2009, dberlin at dberlin dot org wrote: --- Comment #13 from dberlin at gcc dot gnu dot org 2009-02-04 16:09 --- Subject: Re: PTA constraint processing for *x = y is wrong I don't remember offhand. At one point during 4.2 we used to compute the anything set exactly, and it led to massive issues. Of course, most of those were because the anything set had hundreds or thousands of SFT's :). I'm happy to go with your idea for fixing since fixing shortcutting won't fix it, except for two things: 1. ANYTHING is really limited to all addressable variables (IE address taken and escaping), instead of all variables. It was never meant to represent completely unknown (IE user has set pointer to (char *) 0xdeadbeef). Yes, is there a bitmap / array in the PTA graph that I can iterate over instead of all vars? Not right now. ISTM the set you union in should be based on CALLUSED and ESCAPED or something thereof, or at least should be computable with constraints during solving, and unioned in when it changes. Ah, you mean whenever I see *ANYTHING = x union x into a new STORE_TO_ANYTHING solution and have an explicit *ANYTHING = STORE_TO_ANYTHING constraint (which I of course need to handle properly in do_ds_constraint)? That may be indeed faster. Something like that. It is going to be faster than doing it one by one all the time. The way off the top of my head to do this is to simply stop using ANYTHING, and use ANYTHING directly, and then have ANYTHING = CALLUSED and ANYTHING = ESCAPED. I don't think CALLUSED or ESCAPED are related here. You can store non-addressables into *ANYTHING. How? If they are non-addressable, that implies they are not pointed to. I think you are going off the rails here :) If you really want to union ANYTHING into things, the simplest way is to change from doing: ANYTHING = ANYTHING a = y p_4 = ANYTHING p_1 = p_4 p_1 = a x_6 = *p_1 derefaddrtmp.11 = i *x_6 = derefaddrtmp.11 y.0_7 = y to ANYTHING = *ANYTHING ANYTHING = all pointers pre-built or whatever we decided on a = y p_4 = ANYTHING p_1 = p_4 p_1 = a x_6 = *p_1 derefaddrtmp.11 = i *x_6 = derefaddrtmp.11 y.0_7 = y Then p_4 will get the entire anything set, and it will propagate around just like you wanted. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39074