[PATCH] Speed up qsort in IPA ICF

["Martin Liška" <mliska@suse.cz>]

[-- Attachment #1: Type: text/plain, Size: 943 bytes --]

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



[-- Attachment #2: 0001-Speed-up-qsort-in-IPA-ICF.patch --]
[-- Type: text/x-patch, Size: 2044 bytes --]

diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index c9c3cb4a331..d78635ad6b3 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
@@ -3388,16 +3376,7 @@ sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
     = *(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;
+  return g1->uid - g2->uid;
 }
 
 /* After reduction is done, we can declare all items in a group
@@ -3450,6 +3429,8 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
        it != m_classes.end (); ++it)
     classes.quick_push (*it);
 
+  for (unsigned i = 0; i < classes.length (); i++)
+    classes[i]->uid = DECL_UID (classes[i]->classes[0]->members[0]->decl);
   classes.qsort (sort_congruence_class_groups_by_decl_uid);
 
   if (dump_file)
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index 2bf0f156ef6..e7bb4afcfee 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -461,6 +461,7 @@ struct congruence_class_group
 {
   hashval_t hash;
   sem_item_type type;
+  int uid;
   vec <congruence_class *> classes;
 };