From patchwork Thu Dec 15 12:58:37 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 33646 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp335614wrn; Thu, 15 Dec 2022 05:00:21 -0800 (PST) X-Google-Smtp-Source: AA0mqf5fezDH7PIwWtL6q7i+UIHdNOGvf4iz+kmQLIgNwFmeaPTtE5bBFoliW9A3ZULFtjIDhCaA X-Received: by 2002:a05:6402:3895:b0:468:354a:4d6 with SMTP id fd21-20020a056402389500b00468354a04d6mr8400218edb.20.1671109221110; Thu, 15 Dec 2022 05:00:21 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1671109221; cv=none; d=google.com; s=arc-20160816; b=Fw1tQiMUiKt2SEZRFpDckPg44nwMF3tH5pj2UsqBh6AS81FmX+HUDzeV6OnOuhbgll sGOisr//Uac98464+KvxCQdHCil6aaof+pK8ob523fC9vKONRy80Hbsi5OTfbixZTGex sx9uRGTkGAyDYZl4/vq9Vqo+0x4AZmo9Z5pV49584QUQwUUFEk+2THVkjDl52wTxUKEm AkCljkJgPUD9inIDKpTx56fOfPjnLXjipzS7D7dkC7jnGd6/+fJSaSfJjxX8DBWDX93U KSB91AYRjSC5LObKIDKVMhbXqBNXK2InmyOXpK+ynGAvghU7WVKrTsFENH87fzvBXRM9 +f+g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:sender:errors-to:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :mime-version:user-agent:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=ffvycuEwyPdCLJJ6comok2PX1iQVLUfJ8wtvrFPW96o=; b=ZCNaVQpoYLBXrS6NCIlxzZlWvojS+IUpDEezVQaAF8ccFtk6O/QkEqjmDP7fD4FyeR nzBqlWU9yDhf4a2JFtppREwS8IPVVAsjci7q2QmVlJAuJ1tNlfllEry6CKpNwZ8m3Vws vTGI48UBtGuWTbLYf8X0UfN6c85HiuIYIazQWoQH4rt7uSqsiZmciIq9ubnbXgTRix5l x8UQdOHRaINdU2Q0WJ79KD1f5qrYjxQyctsRzdL/4hKZoEq1VXYb2lxflKAsyKX3zolH V0pLE3h31s9nmDtiHTa5DkZsb76yz0cg5EI0n4XeR4+r4XHT2Dw/Z6sMtxMe+qhogIPy z7Zw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=coS1AwIQ; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id w6-20020a05640234c600b0046af4b03015si17299804edc.8.2022.12.15.05.00.20 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Dec 2022 05:00:21 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=coS1AwIQ; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 46408388CF26 for ; Thu, 15 Dec 2022 13:00:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 46408388CF26 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1671109213; bh=ffvycuEwyPdCLJJ6comok2PX1iQVLUfJ8wtvrFPW96o=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=coS1AwIQb6Fd3C+lWe0x3KZAwT9fqwZrxhSanzBOcD8WDlsEF7Q+6K2YUjdnrY9YQ gOEkVzWEGc9oiRViT4tD1YK9+f7w6eWtsdZAjak05ooyLjaJVdklYlzqWHRx+rcr2T S/HRxmO0vWIPgb6zLi8Z31CrZEcbhtLtbIS6EbuA= 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 [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 942B2388DD42 for ; Thu, 15 Dec 2022 12:58:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 942B2388DD42 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 85AB85BCF4 for ; Thu, 15 Dec 2022 12:58:37 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 7FED32C141 for ; Thu, 15 Dec 2022 12:58:37 +0000 (UTC) Date: Thu, 15 Dec 2022 12:58:37 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] middle-end/108086 - avoid quadraticness in copy_edges_for_bb User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20221215130013.46408388CF26@sourceware.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1752285022549600516?= X-GMAIL-MSGID: =?utf-8?q?1752285022549600516?= For the testcase in PR108086 it's visible that we split blocks multiple times when inlining and that causes us to adjust the block tail stmt BBs multiple times, once for each split. The fix is to walk backwards and split from the tail instead. For a reduced testcase this improves compile-time at -O by 4%. Bootstrap and regtest running on x86_64-unknown-linux-gnu. PR middle-end/108086 * tree-inline.cc (copy_edges_for_bb): Walk stmts backwards for splitting the block to avoid quadratic behavior with setting stmts BB on multliple splits. --- gcc/tree-inline.cc | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-) diff --git a/gcc/tree-inline.cc b/gcc/tree-inline.cc index 7b507dd2a38..79897f41e86 100644 --- a/gcc/tree-inline.cc +++ b/gcc/tree-inline.cc @@ -2569,13 +2569,17 @@ copy_edges_for_bb (basic_block bb, profile_count num, profile_count den, && !old_edge->src->aux) new_bb->count -= old_edge->count ().apply_scale (num, den); - for (si = gsi_start_bb (new_bb); !gsi_end_p (si);) + /* Walk stmts from end to start so that splitting will adjust the BB + pointer for each stmt at most once, even when we split the block + multiple times. */ + bool seen_nondebug = false; + for (si = gsi_last_bb (new_bb); !gsi_end_p (si);) { bool can_throw, nonlocal_goto; gimple *copy_stmt = gsi_stmt (si); /* Do this before the possible split_block. */ - gsi_next (&si); + gsi_prev (&si); /* If this tree could throw an exception, there are two cases where we need to add abnormal edge(s): the @@ -2595,25 +2599,23 @@ copy_edges_for_bb (basic_block bb, profile_count num, profile_count den, if (can_throw || nonlocal_goto) { - if (!gsi_end_p (si)) - { - while (!gsi_end_p (si) && is_gimple_debug (gsi_stmt (si))) - gsi_next (&si); - if (gsi_end_p (si)) - need_debug_cleanup = true; - } - if (!gsi_end_p (si)) - /* Note that bb's predecessor edges aren't necessarily - right at this point; split_block doesn't care. */ + /* If there's only debug insns after copy_stmt don't split + the block but instead mark the block for cleanup. */ + if (!seen_nondebug) + need_debug_cleanup = true; + else { + /* Note that bb's predecessor edges aren't necessarily + right at this point; split_block doesn't care. */ edge e = split_block (new_bb, copy_stmt); - - new_bb = e->dest; - new_bb->aux = e->src->aux; - si = gsi_start_bb (new_bb); + e->dest->aux = new_bb->aux; + seen_nondebug = false; } } + if (!is_gimple_debug (copy_stmt)) + seen_nondebug = true; + bool update_probs = false; if (gimple_code (copy_stmt) == GIMPLE_EH_DISPATCH)