On 9/19/19 1:01 PM, Richard Biener wrote:
> On Thu, Sep 19, 2019 at 11:06 AM Martin Liška <mli...@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.
Martin
>
> Richard.
>
>> Thanks,
>> Martin
>>
>> gcc/ChangeLog:
>>
>> 2019-09-19 Martin Liska <mli...@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(-)
>>
>>
>From 05a78667e932e554dfbd69433ad66242cbca6492 Mon Sep 17 00:00:00 2001
From: Martin Liska <mli...@suse.cz>
Date: Thu, 19 Sep 2019 09:41:39 +0200
Subject: [PATCH] Speed up qsort in IPA ICF.
gcc/ChangeLog:
2019-09-19 Martin Liska <mli...@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 std::pair for
easier sorting.
(sem_item_optimizer::merge_classes): Likewise.
---
gcc/ipa-icf.c | 49 ++++++++++++++++---------------------------------
1 file changed, 16 insertions(+), 33 deletions(-)
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index c9c3cb4a331..59b7f8b1b9d 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -3350,13 +3350,7 @@ sort_sem_items_by_decl_uid (const void *a, const void *b)
int uid1 = DECL_UID (i1->decl);
int uid2 = DECL_UID (i2->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return uid1 - uid2;
}
/* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
@@ -3369,13 +3363,7 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
int uid1 = DECL_UID (c1->members[0]->decl);
int uid2 = DECL_UID (c2->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ return uid1 - uid2;
}
/* Sort pair of congruence_class_groups A and B by
@@ -3384,20 +3372,11 @@ sort_congruence_classes_by_decl_uid (const void *a, const void *b)
static int
sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
{
- const congruence_class_group *g1
- = *(const congruence_class_group * const *)a;
- const congruence_class_group *g2
- = *(const congruence_class_group * const *)b;
-
- int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
- int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
-
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- else
- return 0;
+ const std::pair<congruence_class_group *, int> *g1
+ = *(const std::pair<congruence_class_group *, int> *const *) a;
+ const std::pair<congruence_class_group *, int> *g2
+ = *(const std::pair<congruence_class_group *, int> *const *) b;
+ return g1->second - g2->second;
}
/* After reduction is done, we can declare all items in a group
@@ -3445,10 +3424,14 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
}
}
- auto_vec <congruence_class_group *> classes (m_classes.elements ());
+ auto_vec<std::pair<congruence_class_group *, int> > classes (
+ m_classes.elements ());
for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
it != m_classes.end (); ++it)
- classes.quick_push (*it);
+ {
+ int uid = DECL_UID ((*it)->classes[0]->members[0]->decl);
+ classes.quick_push (std::pair<congruence_class_group *, int> (*it, uid));
+ }
classes.qsort (sort_congruence_class_groups_by_decl_uid);
@@ -3470,11 +3453,11 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
}
unsigned int l;
- congruence_class_group *it;
+ std::pair<congruence_class_group *, int> *it;
FOR_EACH_VEC_ELT (classes, l, it)
- for (unsigned int i = 0; i < it->classes.length (); i++)
+ for (unsigned int i = 0; i < it->first->classes.length (); i++)
{
- congruence_class *c = it->classes[i];
+ congruence_class *c = it->first->classes[i];
if (c->members.length () == 1)
continue;
--
2.23.0
