[PATCH 1/2] IPA ICF: rewrite references into a hash_map.

[Jan Hubicka]

> 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
>