> On 6/3/19 3:48 PM, Jan Hubicka wrote:
> > If I get it right, this replaces reference vectors by a central hash
> > map.
>
> Yes
>
> > I wonder when you need to many querries to them? I would expect
> > the subdividing algorithm to travel the reference lists quite
> > sequentially...
>
> The issue is that if you have a function 'foo' that calls 'bar' let's say
> 1000x.
> Then imagine 'baz' having only one function call and it calls 'bar'.
>
> Then if you divide by 'bar' (by all references of 'bar'), you end up here:
>
> 3131 /* Tests if a class CLS used as INDEXth splits any congruence classes.
> 3132 Bitmap stack BMSTACK is used for bitmap allocation. */
> 3133
> 3134 void
> 3135 sem_item_optimizer::do_congruence_step_for_index (congruence_class
> *cls,
> 3136 unsigned int index)
> 3137 {
> 3138 hash_map <congruence_class *, bitmap> split_map;
> 3139
> 3140 for (unsigned int i = 0; i < cls->members.length (); i++)
> 3141 {
> 3142 sem_item *item = cls->members[i];
> 3143
> 3144 /* Iterate all usages that have INDEX as usage of the item. */
> 3145 for (unsigned int j = 0; j < item->usages.length (); j++)
> 3146 {
> 3147 sem_usage_pair *usage = item->usages[j];
> 3148
> 3149 if (usage->index != index)
> 3150 continue;
>
> And the function will be called 1000x with index = [0, 999]. And then we have
> linear
> search at line 3145 that will most commonly return with false at 3149 because
> function
> 'baz' has only a call with index == 0. That's why it's so slow and why
> hash_table
> help significantly.
Aha, I see. You have one equivalence class and you know that index has
changed and you are looking up if given function use it.
Patch is OK,
Honza
>
> Martin
>
> >
> > Honza
>
