From patchwork Wed Mar 23 11:49:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 52247 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 46FEA3865474 for ; Wed, 23 Mar 2022 11:49:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 46FEA3865474 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1648036198; bh=MT/QANoBuwBAItXuUSFC/2fCg3U5omzE03KQvYXO20Y=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=y4M4d3Y7VquUs0k/Ew+aRjCSoVf9XNso/GlgEUAbR6sYSCp1Yw+XAvlqwRNENZ2iZ hJPPvo1k+e/Jz0NUT9UG7Mdnci8gun8L6/B/kODrwT5TumrSrmzL5NSNisgOKYv2YX kIva9HNydVz+frqN3uVcv4OcOVD9LLV2p6+775yw= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 78BB73858405 for ; Wed, 23 Mar 2022 11:49:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 78BB73858405 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 5A99C1F387; Wed, 23 Mar 2022 11:49:27 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 4351313A78; Wed, 23 Mar 2022 11:49:27 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id DfVSD0cJO2KBcgAAMHmgww (envelope-from ); Wed, 23 Mar 2022 11:49:27 +0000 Date: Wed, 23 Mar 2022 12:49:26 +0100 (CET) To: gcc-patches@gcc.gnu.org Subject: [PATCH] rtl-optimization/105028 - fix compile-time hog in form_threads_from_copies MIME-Version: 1.0 Message-Id: <20220323114927.4351313A78@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" form_threads_from_copies processes a sorted array of copies, skipping those with the same thread and conflicting threads and merging the first non-conflicting ones. After that it terminates the loop and gathers the remaining elements of the array, skipping same thread copies, re-starting the process. For a large number of copies this gathering of the rest takes considerable time and it also appears pointless. The following simply continues processing the array which should be equivalent as far as I can see. This takes form_threads_from_copies off the profile radar from previously taking ~50% of the compile-time. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. OK if testing succeeds? Thanks, Richard. 2022-03-23 Richard Biener PR rtl-optimization/105028 * ira-color.cc (form_threads_from_copies): Remove unnecessary copying of the sorted_copies tail. --- gcc/ira-color.cc | 71 +++++++++++++++++++----------------------------- 1 file changed, 28 insertions(+), 43 deletions(-) diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc index e01d1841a08..4a1a325e8e3 100644 --- a/gcc/ira-color.cc +++ b/gcc/ira-color.cc @@ -2348,58 +2348,43 @@ form_threads_from_copies (int cp_num) { ira_allocno_t a, thread1, thread2; ira_copy_t cp; - int i, n; qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func); /* Form threads processing copies, most frequently executed first. */ - for (; cp_num != 0;) + for (int i = 0; i < cp_num; i++) { - for (i = 0; i < cp_num; i++) + cp = sorted_copies[i]; + thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno; + thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno; + if (thread1 == thread2) + continue; + if (! allocno_thread_conflict_p (thread1, thread2)) { - cp = sorted_copies[i]; - thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno; - thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno; - if (thread1 == thread2) - continue; - if (! allocno_thread_conflict_p (thread1, thread2)) + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf + (ira_dump_file, + " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n", + cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), + ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), + cp->freq); + merge_threads (thread1, thread2); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) { - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf - (ira_dump_file, - " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n", - cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), - ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), - cp->freq); - merge_threads (thread1, thread2); - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - { - thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno; - fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)", - ALLOCNO_COLOR_DATA (thread1)->thread_freq, - ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1), - ALLOCNO_FREQ (thread1)); - for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno; - a != thread1; - a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) - fprintf (ira_dump_file, " a%dr%d(%d)", - ALLOCNO_NUM (a), ALLOCNO_REGNO (a), - ALLOCNO_FREQ (a)); - fprintf (ira_dump_file, "\n"); - } - i++; - break; + thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno; + fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)", + ALLOCNO_COLOR_DATA (thread1)->thread_freq, + ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1), + ALLOCNO_FREQ (thread1)); + for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno; + a != thread1; + a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) + fprintf (ira_dump_file, " a%dr%d(%d)", + ALLOCNO_NUM (a), ALLOCNO_REGNO (a), + ALLOCNO_FREQ (a)); + fprintf (ira_dump_file, "\n"); } } - /* Collect the rest of copies. */ - for (n = 0; i < cp_num; i++) - { - cp = sorted_copies[i]; - if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno - != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno) - sorted_copies[n++] = cp; - } - cp_num = n; } }