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

[Martin Liška]

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.

Martin

> 
> Honza