From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 79F293858C1F for ; Wed, 22 Mar 2023 10:01:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 79F293858C1F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 6229520C28; Wed, 22 Mar 2023 10:01:54 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1679479314; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=+dBpAo0szVGGz1LkEVrvmjGhW8gu6ZModURRQRSbwc0=; b=rG9f7CJ1n+TbKQB68yeYUDh7hkuvmKQCClibpZ9i6vGVssDpsELPHharSlp2zemKHCxQe5 g4CgEjKkOv1RQ3LoqS5iWDfNddPrW4AHwC5WTu4VYZYGv4HOhOOT+TCzn67NWvi8+s6W0R vWLfxNH3AqELcfVG3OXk/WpNjRpcTNY= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1679479314; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=+dBpAo0szVGGz1LkEVrvmjGhW8gu6ZModURRQRSbwc0=; b=JBAQIL7xMHjFfI7ySJekVwDxTe1AD6cwrbaAXxUnF5EOH3tchp4K8UAoe+9JFTRcDriJaN 6jUUpMMeNLNsJwBA== 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 561042C141; Wed, 22 Mar 2023 10:01:54 +0000 (UTC) Date: Wed, 22 Mar 2023 10:01:54 +0000 (UTC) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jakub Jelinek Subject: [PATCH] rtl-optimization/109237 - quadraticness in delete_trivially_dead_insns User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII 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 List-Id: Message-ID: <20230322100154.Jpi0Zi8Q4Qjp8LMisakuK-daKwiiS9zpQ7CWr__AFYE@z> The following addresses quadraticness in processing debug insns in delete_trivially_dead_insns and insn_live_p by using TREE_VISITED on the INSN_VAR_LOCATION_DECL to indicate a later debug bind with the same decl and no intervening real insn or debug marker. That gets rid of the NEXT_INSN walk in insn_live_p in favor of first clearing TREE_VISITED in the first loop over insn and the book-keeping of decls we set the bit since we need to clear them when visiting a real or debug marker insn. That improves the time spent in delete_trivially_dead_insns from 10.6s to 2.2s for the testcase. Bootstrapped and tested on x86_64-unknown-linux-gnu. OK? Thanks, Richard. PR rtl-optimization/109237 * cse.cc (insn_live_p): Remove NEXT_INSN walk, instead check TREE_VISITED on INSN_VAR_LOCATION_DECL. (delete_trivially_dead_insns): Maintain TREE_VISITED on active debug bind INSN_VAR_LOCATION_DECL. --- gcc/cse.cc | 39 ++++++++++++++++++++++++--------------- 1 file changed, 24 insertions(+), 15 deletions(-) diff --git a/gcc/cse.cc b/gcc/cse.cc index 8fbda4ecc86..204047b0e0b 100644 --- a/gcc/cse.cc +++ b/gcc/cse.cc @@ -6906,22 +6906,12 @@ insn_live_p (rtx_insn *insn, int *counts) } else if (DEBUG_INSN_P (insn)) { - rtx_insn *next; - if (DEBUG_MARKER_INSN_P (insn)) return true; - for (next = NEXT_INSN (insn); next; next = NEXT_INSN (next)) - if (NOTE_P (next)) - continue; - else if (!DEBUG_INSN_P (next)) - return true; - /* If we find an inspection point, such as a debug begin stmt, - we want to keep the earlier debug insn. */ - else if (DEBUG_MARKER_INSN_P (next)) - return true; - else if (INSN_VAR_LOCATION_DECL (insn) == INSN_VAR_LOCATION_DECL (next)) - return false; + if (DEBUG_BIND_INSN_P (insn) + && TREE_VISITED (INSN_VAR_LOCATION_DECL (insn))) + return false; return true; } @@ -7007,8 +6997,11 @@ delete_trivially_dead_insns (rtx_insn *insns, int nreg) counts = XCNEWVEC (int, nreg * 3); for (insn = insns; insn; insn = NEXT_INSN (insn)) if (DEBUG_BIND_INSN_P (insn)) - count_reg_usage (INSN_VAR_LOCATION_LOC (insn), counts + nreg, - NULL_RTX, 1); + { + count_reg_usage (INSN_VAR_LOCATION_LOC (insn), counts + nreg, + NULL_RTX, 1); + TREE_VISITED (INSN_VAR_LOCATION_DECL (insn)) = 0; + } else if (INSN_P (insn)) { count_reg_usage (insn, counts, NULL_RTX, 1); @@ -7048,6 +7041,7 @@ delete_trivially_dead_insns (rtx_insn *insns, int nreg) the setter. Then go through DEBUG_INSNs and if a DEBUG_EXPR has been created for the unused register, replace it with the DEBUG_EXPR, otherwise reset the DEBUG_INSN. */ + auto_vec later_debug_set_vars; for (insn = get_last_insn (); insn; insn = prev) { int live_insn = 0; @@ -7110,6 +7104,21 @@ delete_trivially_dead_insns (rtx_insn *insns, int nreg) } cse_cfg_altered |= delete_insn_and_edges (insn); } + else + { + if (!DEBUG_INSN_P (insn) || DEBUG_MARKER_INSN_P (insn)) + { + for (tree var : later_debug_set_vars) + TREE_VISITED (var) = 0; + later_debug_set_vars.truncate (0); + } + else if (DEBUG_BIND_INSN_P (insn) + && !TREE_VISITED (INSN_VAR_LOCATION_DECL (insn))) + { + later_debug_set_vars.safe_push (INSN_VAR_LOCATION_DECL (insn)); + TREE_VISITED (INSN_VAR_LOCATION_DECL (insn)) = 1; + } + } } if (MAY_HAVE_DEBUG_BIND_INSNS) -- 2.35.3