From patchwork Thu Sep 19 09:06:46 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 1164458 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-509254-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="K6cObauc"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 46YrZV545bz9sNk for ; Thu, 19 Sep 2019 19:06:58 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:cc:message-id:date:mime-version:content-type; q=dns; s=default; b=DhWbeKgXxnIkgG0sHJP0oaMHWCAN1ANr+kAKNv/vF4BeO21aRX DvhfpKUx0RoBbMeNa3m2Q5glJ8NY598j+l97JZDiPh9v2/hpBLXZ+jedJhUjNfD9 uPpv7h7L7TwRkKydqamO+nbFgXmK+MX9qPPYloDc+FIM7gHz82DxREhUw= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:cc:message-id:date:mime-version:content-type; s= default; bh=LAJ6M2WN4ySV3YzfiCIL2jryV4Q=; b=K6cObaucjUJTqIumHnEu N9KSDbspiSS9sWBcZlHfVMP4Z3Jw2WxCeKcTmCOzhpP3Q4bnUElRWC+osPX/JxtE lrbYjI3pDLchC3cUz3gQHara23E8cZLXP5FTrHYao1vK/0e+X45fA8h2K0C66iNu 9qOv/iHAsx7XW/wgxL8goGM= Received: (qmail 34508 invoked by alias); 19 Sep 2019 09:06:51 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 34500 invoked by uid 89); 19 Sep 2019 09:06:51 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-18.0 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS autolearn=ham version=3.3.1 spammy=dereferences, icf X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 19 Sep 2019 09:06:48 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 6836BAF57; Thu, 19 Sep 2019 09:06:46 +0000 (UTC) From: =?utf-8?q?Martin_Li=C5=A1ka?= Subject: [PATCH] Speed up qsort in IPA ICF To: gcc-patches@gcc.gnu.org Cc: Alexander Monakov Message-ID: Date: Thu, 19 Sep 2019 11:06:46 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.8.0 MIME-Version: 1.0 X-IsSubscribed: yes 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 * 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(-) 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 classes; };