This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Put scope blocks on a diet


On Nov 28, 2007 11:01 PM, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
>
> >> Can we find the places that are walking the hash table and have them
> >> collect the declarations first, sort them by DECL_UID, and then walk the
> >> sorted array?  Or, use a splay tree instead of a hash table, since splay
> >> trees already have the property that walking the tree will always go in
> >> sorted order?  (Splay trees are of course O(log n) for most operations,
> >> whereas hashtables are O(1), ignoring resizing costs.)
> >
> > Yes, I have done so for referenced_vars by using a bitmap indexed by UID.
> > Which is both space-efficient and fast in average (though O(n) in theory).
> > But this is not appropriate for stage3.
>
> Perhaps not, but other fixes might be.  If that's the problematic table,
> then replacing the walk function with a walk (to collect the nodes), a
> qsort, and an iteration might be fine, and very contained.

Yes, unfortunately I have not identified the walk that causes the problem (where
there might be more than one), but chose to exchange the underlying
data-structure
(also because I needed the global lookup table anyway) which fixes all of the
FOR_EACH_REFERENCED_VAR users - which are quite a few.  For reference, the
two patches are

Introduce a global DECL_UID to tree map:
http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00523.html

Make gimple_df->referenced_vars a bitmap indexed by UID rather than a hashtable:
http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00524.html

In the end these patches should enable us to get rid of the unexpanded_var_list
(and thus the use of TREE_CHAIN for decls) and of the remove_unused_vars
TODO (which takes up quite an amount of time for tramp3d) and let the garbage
collector do this work.

Richard.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]