[PATCH] Speed up qsort in IPA ICF

[Richard Biener]

On Thu, Sep 19, 2019 at 3:02 PM Martin Liška <mliska@suse.cz> wrote:
>
> On 9/19/19 1:01 PM, Richard Biener wrote:
> > 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.
>
> Good point, there's a tested patch.

OK.

Thanks,
Richard.

> Martin
>
> >
> > 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(-)
> >>
> >>
>