Re: [PATCH] Speed up qsort in IPA ICF

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Sep 19, 2019 at 11:06 AM Martin Liška <mliska@suse.cz> wrote:
>
> Hi.
>
> As Alexander pointed out, the sort_congruence_class_groups_by_decl_uid is the most
> expensive qsort operator in tramp3d compilation. It does unfortunate 7 pointer dereferences
> via: DECL_UID (classes[i]->classes[0]->members[0]->decl). I'm suggesting to cache that
> in congruence_class_group.
>
> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
>
> Ready to be installed?

Since we're populating the classes vector right before you could elide
the new field and do it in the same iteration by having

auto_vec <std::pair<congruence_class_group *, unsigned> > classes

and pushing *it, DECL_UID and then sorting by the readily available
UID in the data?  That makes the sort use a linear memory region
w/o dereferences.

Richard.

> Thanks,
> Martin
>
> gcc/ChangeLog:
>
> 2019-09-19  Martin Liska  <mliska@suse.cz>
>
>         * ipa-icf.c (sort_sem_items_by_decl_uid): Simplify comparator.
>         (sort_congruence_classes_by_decl_uid): Likewise.
>         (sort_congruence_class_groups_by_decl_uid): Use
>         congruence_class_group::uid.
>         (sem_item_optimizer::merge_classes): Cache
>         DECL_UID (classes[i]->classes[0]->members[0]->decl).
>         * ipa-icf.h (struct congruence_class_group): New field.
> ---
>  gcc/ipa-icf.c | 29 +++++------------------------
>  gcc/ipa-icf.h |  1 +
>  2 files changed, 6 insertions(+), 24 deletions(-)
>
>