Summary: | [4.3 Regression] tree struct aliasing goes into a loop marking call clobbers. | ||
---|---|---|---|
Product: | gcc | Reporter: | Ramana Radhakrishnan <ramana.radhakrishnan> |
Component: | tree-optimization | Assignee: | Richard Biener <rguenth> |
Status: | RESOLVED FIXED | ||
Severity: | normal | CC: | dave, dberlin, fang, gcc-bugs, pranav.bhandarkar, rguenth |
Priority: | P3 | Keywords: | alias, compile-time-hog |
Version: | 4.3.0 | ||
Target Milestone: | 4.3.0 | ||
Host: | i686-linux-gnu | Target: | arm-none-eabi |
Build: | i686-linux-gnu | Known to work: | |
Known to fail: | Last reconfirmed: | 2007-09-20 12:06:32 | |
Attachments: |
testcase.
patch fixing the problem |
Description
Ramana Radhakrishnan
2007-09-20 10:35:02 UTC
Created attachment 14229 [details]
testcase.
At least the unmodifiable_var_p (alias) call looks suspicious (but probably unrelated to the problem): Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 128618) +++ tree-ssa-alias.c (working copy) @@ -561,7 +561,7 @@ set_initial_properties (struct alias_inf subvar_t svars; svars = get_subvars_for_var (SFT_PARENT_VAR (alias)); for (; svars; svars = svars->next) - if (!unmodifiable_var_p (alias)) + if (!unmodifiable_var_p (svars->var)) mark_call_clobbered (svars->var, pi->escape_mask); } else if (!unmodifiable_var_p (alias)) what we have is that SFT_PARENT_VAR is of type 'union Meep' which has quite a lot of fields and the above loop is quadratic in the number of fields. (gdb) call bitmap_count_bits (pi->pt_vars) $23 = 10307 that is, we have all SFTs in pi->pt_vars and as we process them we loop over all of them again. Created attachment 14230 [details]
patch fixing the problem
This fixes it. The idea is to keep track of which parent vars we need to add
all subvars to the call clobbered list in a bitmap and process them after the
first walk.
4.2 doesn't have this extra loop. (In reply to comment #4) > Created an attachment (id=14230) [edit] > patch fixing the problem > > This fixes it. The idea is to keep track of which parent vars we need to add > all subvars to the call clobbered list in a bitmap and process them after the > first walk. > Yep it does - Thanks for the quick fix. I am testing it now and will let you know in a bit . (In reply to comment #5) > 4.2 doesn't have this extra loop. > Subject: Re: [4.3 Regression] tree struct aliasing goes into a loop marking call clobbers. On 20 Sep 2007 13:52:11 -0000, ramana dot radhakrishnan at celunite dot com <gcc-bugzilla@gcc.gnu.org> wrote: > > > ------- Comment #6 from ramana dot radhakrishnan at celunite dot com 2007-09-20 13:52 ------- > (In reply to comment #4) > > Created an attachment (id=14230) > --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14230&action=view) [edit] > > patch fixing the problem > > > > This fixes it. The idea is to keep track of which parent vars we need to add > > all subvars to the call clobbered list in a bitmap and process them after the > > first walk. I don't have enough context handy in the patch to see if you moved it outside the transitive loop, or just the initial loop. You can move it outside the initial loop, but not the transitive loop, because the SFT's may themselves be pointers (obviously for non-pointer SFT's, you can certainly ignore them). You could also speed this up dramatically by not queuing non-pointers. Subject: Re: [4.3 Regression] tree struct
aliasing goes into a loop marking call clobbers.
On Thu, 20 Sep 2007, dberlin at dberlin dot org wrote:
> ------- Comment #7 from dberlin at gcc dot gnu dot org 2007-09-20 15:12 -------
> Subject: Re: [4.3 Regression] tree struct aliasing goes into a loop marking
> call clobbers.
>
> On 20 Sep 2007 13:52:11 -0000, ramana dot radhakrishnan at celunite
> dot com <gcc-bugzilla@gcc.gnu.org> wrote:
> >
> >
> > ------- Comment #6 from ramana dot radhakrishnan at celunite dot com 2007-09-20 13:52 -------
> > (In reply to comment #4)
> > > Created an attachment (id=14230)
> --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14230&action=view)
> > --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14230&action=view) [edit]
> > > patch fixing the problem
> > >
> > > This fixes it. The idea is to keep track of which parent vars we need to add
> > > all subvars to the call clobbered list in a bitmap and process them after the
> > > first walk.
>
>
> I don't have enough context handy in the patch to see if you moved it
> outside the transitive loop, or just the initial loop.
> You can move it outside the initial loop, but not the transitive loop,
> because the SFT's may themselves be pointers (obviously for
> non-pointer SFT's, you can certainly ignore them).
I only moved it outside of the innermost EXECUTE_IF_SET_IN_BITMAP loop
on aliases, which should be safe. I don't completely understand what
you mean with non queuing non-pointers - I suppose queuing non-pointers
in the worklist in mark_aliases_call_clobbered?
Richard.
Subject: Bug 33508 Author: rguenth Date: Fri Sep 21 09:36:52 2007 New Revision: 128645 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=128645 Log: 2007-09-21 Richard Guenther <rguenther@suse.de> PR tree-optimization/33508 * tree-ssa-alias.c (mark_aliases_call_clobbered): Avoid quadratic loop by keeping a bitmap of variables we have to clobber all subvariables for. (set_initial_properties): Likewise. Modified: trunk/gcc/ChangeLog trunk/gcc/tree-ssa-alias.c Fixed. |