This is the mail archive of the
mailing list for the GCC project.
Re: Put scope blocks on a diet
On Nov 28, 2007 11:01 PM, Mark Mitchell <email@example.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
(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:
Make gimple_df->referenced_vars a bitmap indexed by UID rather than a hashtable:
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.