From patchwork Thu Jul 27 09:31:49 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 126878 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a985:0:b0:3e4:2afc:c1 with SMTP id t5csp983269vqo; Thu, 27 Jul 2023 03:00:01 -0700 (PDT) X-Google-Smtp-Source: APBJJlHVhQtLTh9V0C8yU8KfH6OXOYd80LeWZRZALlKz2E3OnVCDBrdw4ttwJD4lInesBBdTxOhr X-Received: by 2002:a05:6402:1b1a:b0:522:3aae:c69b with SMTP id by26-20020a0564021b1a00b005223aaec69bmr1323231edb.20.1690452001769; Thu, 27 Jul 2023 03:00:01 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690452001; cv=none; d=google.com; s=arc-20160816; b=i42wL8IhVf4AbLHAqqtT50kKda80LdzxqGjkVMpYAmM/NMbyIwTKyr4oNXwTvQdQtz rYOg0wLYyaXHD7zTmE1tOWaR5FD+37flGOntBBrU6cCZZRh8fQCpFTII75E85UIPJlwv rbA12Xg9KomOhO2q6Fn38OSthDPaq0Fip+BbaC9SWRb8aJz2S0xWe4BUc25GYSjkLd7k 9LNoYMvpoONYfs3YLTmSKBVKQfkYzUZRk19QyIXqD/3XZkUBAxUeE7afw/Oq/ahLiaP/ xB1XI04424A/dCwe7E2eEN5v/L+XmW0LK3+VGXZYm2vX+pwb0KYt0Uu8HAgYldaHX2/P BDEg== 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=aaqhKSb9TIS9P5bhFG65ODzLk3xbGLVrvafDG6SqlxU=; fh=etb9MYHN7HLF/sff76ICVdPeKiI8ZsjoOL2bcdG0aog=; b=RLJt8mJIkqGkwt7Go/uoZpEHU+dNr293PXiR4v3B+Jd7L4yJzjKgGIhU3CkaH7R1rZ /NIrSoF/uzXPTP7fDuAeJ4cGwayvLgDCCHh61hwTwqMfYTvjg1rH6OCtbFS0xAsIEpjm Gn8JpQfadFzIbe4mkIlkAQmWw4iHlViFhdAvW3fb+ast8WyL18ICp10Gn8fF9W+pgC2Y Ev3Gq8k3NJlSIwvxkYyU1MtG03CQqmIxnoCKosYx5boirvZgj3MdKpyvHPVeCzJx3IFX 4PXib40ZePgo+Q/mSjdOYwUaGRdb67bysrzZvHYKTQ61QFeBiQzGkJwVnG+uyVoM5ynr wDLQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=nBsBuJPl; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id e5-20020a50ec85000000b005223f88615fsi694863edr.108.2023.07.27.03.00.01 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 27 Jul 2023 03:00:01 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=nBsBuJPl; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 31E2D38881C7 for ; Thu, 27 Jul 2023 09:34:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 31E2D38881C7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690450478; bh=aaqhKSb9TIS9P5bhFG65ODzLk3xbGLVrvafDG6SqlxU=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=nBsBuJPl4sLuwNZ9uGiMzTL0CIQ8ykrcM8Uboosf/f8RgZn+z72CJUcWMLGlwNKfw umdPRgSGj4sxSs2SeXiL7KG387vCoS614UkLQkO90D7pA+ZBu+4rQ6YsYSsdDLFXrZ r+ifAHSJJpU3a1lBNy71qT+tAydWiv/m00WvUJE4= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id A31AA3962DDF for ; Thu, 27 Jul 2023 09:31:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A31AA3962DDF Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id B7EB321A90 for ; Thu, 27 Jul 2023 09:31:49 +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 AE8082C142 for ; Thu, 27 Jul 2023 09:31:49 +0000 (UTC) Date: Thu, 27 Jul 2023 09:31:49 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Remove recursive post-dominator traversal in sinking 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, T_SCC_BODY_TEXT_LINE 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: <20230727093438.31E2D38881C7@sourceware.org> X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1772567398068482480 X-GMAIL-MSGID: 1772567398068482480 The following turns the recursive post-dominator traversal in GIMPLE code sinking to a worklist. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. * tree-ssa-sink.cc (sink_code_in_bb): Remove recursion, instead use a worklist ... (pass_sink_code::execute): ... in the caller. --- gcc/tree-ssa-sink.cc | 27 ++++++++++++++++----------- 1 file changed, 16 insertions(+), 11 deletions(-) diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index 74dae0fa3c0..ab1cbffb32a 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -673,7 +673,6 @@ sink_common_stores_to_bb (basic_block bb) static unsigned sink_code_in_bb (basic_block bb) { - basic_block son; gimple_stmt_iterator gsi; edge_iterator ei; edge e; @@ -686,12 +685,12 @@ sink_code_in_bb (basic_block bb) /* If this block doesn't dominate anything, there can't be any place to sink the statements to. */ if (first_dom_son (CDI_DOMINATORS, bb) == NULL) - goto earlyout; + return todo; /* We can't move things across abnormal edges, so don't try. */ FOR_EACH_EDGE (e, ei, bb->succs) if (e->flags & EDGE_ABNORMAL) - goto earlyout; + return todo; for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) { @@ -765,13 +764,6 @@ sink_code_in_bb (basic_block bb) gsi_prev (&gsi); } - earlyout: - for (son = first_dom_son (CDI_POST_DOMINATORS, bb); - son; - son = next_dom_son (CDI_POST_DOMINATORS, son)) - { - todo |= sink_code_in_bb (son); - } return todo; } @@ -861,7 +853,20 @@ pass_sink_code::execute (function *fun) memset (&sink_stats, 0, sizeof (sink_stats)); calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS); - todo |= sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun)); + + auto_vec worklist; + worklist.quick_push (EXIT_BLOCK_PTR_FOR_FN (fun)); + do + { + basic_block bb = worklist.pop (); + todo |= sink_code_in_bb (bb); + for (basic_block son = first_dom_son (CDI_POST_DOMINATORS, bb); + son; + son = next_dom_son (CDI_POST_DOMINATORS, son)) + worklist.safe_push (son); + } + while (!worklist.is_empty ()); + statistics_counter_event (fun, "Sunk statements", sink_stats.sunk); statistics_counter_event (fun, "Commoned stores", sink_stats.commoned); free_dominance_info (CDI_POST_DOMINATORS);