From patchwork Mon Jul 31 12:39:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 128648 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:918b:0:b0:3e4:2afc:c1 with SMTP id s11csp1986385vqg; Mon, 31 Jul 2023 05:40:38 -0700 (PDT) X-Google-Smtp-Source: APBJJlHpQ/jyvLP4FZq0CVdUZGHT3PQuBse5BRZ2Q12UnZJRGTxkKiYUUc8/sxl6I5VT+Q6f204f X-Received: by 2002:a5d:6611:0:b0:317:49e9:c57 with SMTP id n17-20020a5d6611000000b0031749e90c57mr6124202wru.43.1690807238344; Mon, 31 Jul 2023 05:40:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690807238; cv=none; d=google.com; s=arc-20160816; b=Y5hPlp7EpD/LChFOXXrCAsNXOR9M6Z1KN/HciGP6etww9DAyreu1XZdpMvEQ73/bbP hOXper+Rr3lct1rR1zv1oE6ZBEKWpGcPJ0X//R8iqXNFKtxxA5RbdJk7bM9yPrkRSI1n uDzdpkflH2011GUCQEcITeWtAVe9RgU2Z32SFGhTc3bLANPCG5dkBL7sGHKbVJS4f5oM y5DMByRPrSwrn4QXVdNzEvv+xHin6nOiRPL26x07IaIGKlRPD5I4J0AiutCbsKoks05k lFb+Ny6hjQtb0tR7rAIAgeed3JcwDT7Gagu+VGd3Y/Q9dJedDb7EhZEyEIsbgW/7Aa9Y zBTQ== 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=g/E4EhvCAVwAkp61jJ8Om68kT/tC5HDS6mjg4CakEVo=; fh=etb9MYHN7HLF/sff76ICVdPeKiI8ZsjoOL2bcdG0aog=; b=vZSp8c8pzwHm4MVOuTRTBFdgbw5iMsgRsQpT4NdYq9dB6NnROdtvEzvD82K0fU/C9I JhySJNwGm9pIVPJfV0vUSVBMJyhTrbX2s4Dlbq4AHV00ZSLuZBUd8wDD7lp7zPhGhJ2a tEJPph6hYoKrVn8tXwXQWsYWqOQWnUU4G++O/mg5S9I6S2s2pZp7GWGLbaq9nG9vEfuz N/Qs4Bk3si79K6C+tWzdbJirdy/OFsMCgvHBpxtzfXtYgySLJOcGOkXpX16wl81abPIV 3+/Z3sdfWPQ/VBuZc5Cou9G3Y8VuWu8eB4X0Bvcrf8uYzqVMbt3n+Tsk1vqBk2MLKHz5 ZX1g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=hNZXPjgS; 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 f9-20020a170906138900b0099bca0c5445si2361126ejc.363.2023.07.31.05.40.37 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 31 Jul 2023 05:40:38 -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=hNZXPjgS; 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 1FA743858425 for ; Mon, 31 Jul 2023 12:40:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1FA743858425 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690807237; bh=g/E4EhvCAVwAkp61jJ8Om68kT/tC5HDS6mjg4CakEVo=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=hNZXPjgS796rN5HvYbks8ZiTdU9zSs2YWvtDJsc2Ae1gri9ohLrlhCHAWaEET1iRZ LQSBZKKouKprBj8OQWZWuuqI4e5OXqdCorJBzVdgPO2QC933fo1MUkOvMEb0cdoGl+ CGSTA2ACVlmBJVMTG6WMFNjN3F1kOqp2Gc8KESHk= 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 58A183858CD1 for ; Mon, 31 Jul 2023 12:39:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 58A183858CD1 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 69EBD1F897 for ; Mon, 31 Jul 2023 12:39:52 +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 5F9C52C142 for ; Mon, 31 Jul 2023 12:39:52 +0000 (UTC) Date: Mon, 31 Jul 2023 12:39:52 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Improve sinking with unrelated defs 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: <20230731124037.1FA743858425@sourceware.org> X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1772939890571827812 X-GMAIL-MSGID: 1772939890571827812 statement_sink_location for loads is currently confused about stores that are not on the paths we are sinking across. The following avoids this by explicitely checking whether a block with a store is on any of those paths. To not perform too many walks over the sub-part of the CFG between the orignal stmt location and the found sinking candidate we first collect all blocks to check and then perform a single walk from the sinking candidate location to the original stmt location. We avoid enlarging the region by conservatively handling backedges. The original heuristics what store locations to ignore have been refactored, some can possibly be removed now. If anybody knows a cheaper way to check whether a BB is on a path from block A to block B which is dominated by A I'd be happy to know (or if there would be a clever caching method at least - I'm probably going to limit the number of blocks to walk to aovid quadraticness). Boostrapped and tested on x86_64-unknown-linux-gnu. This depends on the previous sent RFC to limit testsuite fallout. * tree-ssa-sink.cc (pass_sink_code::execute): Mark backedges. (statement_sink_location): Do not consider stores that are not on any path from the original to the destination location. * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 +++ gcc/tree-ssa-sink.cc | 125 ++++++++++++++++---- 2 files changed, 121 insertions(+), 20 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c new file mode 100644 index 00000000000..266ceb000a5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink1-details" } */ + +void bar (); +int foo (int *p, int x) +{ + int res = *p; + if (x) + { + bar (); + res = 1; + } + return res; +} + +/* { dg-final { scan-tree-dump "Sinking # VUSE" "sink1" } } */ diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index cf0a32a954b..e996f46c864 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -388,13 +388,32 @@ statement_sink_location (gimple *stmt, basic_block frombb, imm_use_iterator imm_iter; use_operand_p use_p; + auto_bitmap bbs_to_check; FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt)) { gimple *use_stmt = USE_STMT (use_p); basic_block bb = gimple_bb (use_stmt); + + /* If there is no virtual definition here, continue. */ + if (gimple_code (use_stmt) != GIMPLE_PHI + && !gimple_vdef (use_stmt)) + continue; + + /* When the virtual definition is possibly within the same + irreducible region as the current sinking location all + bets are off. */ + if (((bb->flags & commondom->flags & BB_IRREDUCIBLE_LOOP) + && bb->loop_father == commondom->loop_father) + || ((commondom->flags & BB_IRREDUCIBLE_LOOP) + && flow_loop_nested_p (commondom->loop_father, + bb->loop_father)) + || ((bb->flags & BB_IRREDUCIBLE_LOOP) + && flow_loop_nested_p (bb->loop_father, + commondom->loop_father))) + ; /* For PHI nodes the block we know sth about is the incoming block with the use. */ - if (gimple_code (use_stmt) == GIMPLE_PHI) + else if (gimple_code (use_stmt) == GIMPLE_PHI) { /* If the PHI defines the virtual operand, ignore it. */ if (gimple_phi_result (use_stmt) == gimple_vuse (stmt)) @@ -402,32 +421,97 @@ statement_sink_location (gimple *stmt, basic_block frombb, /* In case the PHI node post-dominates the current insert location we can disregard it. But make sure it is not dominating it as well as can happen in a CFG cycle. */ - if (commondom != bb - && !dominated_by_p (CDI_DOMINATORS, commondom, bb) - && dominated_by_p (CDI_POST_DOMINATORS, commondom, bb) - /* If the blocks are possibly within the same irreducible - cycle the above check breaks down. */ - && !((bb->flags & commondom->flags & BB_IRREDUCIBLE_LOOP) - && bb->loop_father == commondom->loop_father) - && !((commondom->flags & BB_IRREDUCIBLE_LOOP) - && flow_loop_nested_p (commondom->loop_father, - bb->loop_father)) - && !((bb->flags & BB_IRREDUCIBLE_LOOP) - && flow_loop_nested_p (bb->loop_father, - commondom->loop_father))) + if (!dominated_by_p (CDI_DOMINATORS, commondom, bb) + && dominated_by_p (CDI_POST_DOMINATORS, commondom, bb)) continue; - bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src; } - else if (!gimple_vdef (use_stmt)) + + /* For PHIs the relevant block is the edge source. */ + if (gimple_code (use_stmt) == GIMPLE_PHI) + bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src; + if (bb == commondom) continue; + if (bb == frombb) + return false; + /* If the use is not dominated by the path entry it is not on the path. */ if (!dominated_by_p (CDI_DOMINATORS, bb, frombb)) continue; - /* There is no easy way to disregard defs not on the path from - frombb to commondom so just consider them all. */ - commondom = nearest_common_dominator (CDI_DOMINATORS, - bb, commondom); + + /* If BB is definitely on the path, shrink it. Else defer + processing. */ + if (dominated_by_p (CDI_DOMINATORS, commondom, bb)) + commondom = bb; + else + bitmap_set_bit (bbs_to_check, bb->index); + } + + /* Now check whether any of the BBs recorded in bbs_to_check + is on a path from frombb to commondom. If so, adjust + commondom accordingly. */ + if (!bitmap_empty_p (bbs_to_check)) + { + auto_bb_flag visited (cfun); + auto_vec worklist; + auto_vec toclean; + worklist.quick_push (commondom); + do + { + basic_block pb = worklist.pop (); + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, pb->preds) + /* When we run into backedges instead of checking paths + covering those (esp. considering irreducible regions) + simply adjust commondom to the non-backedge common + dominators. */ + if (e->flags & EDGE_DFS_BACK) + { + FOR_EACH_EDGE (e, ei, pb->preds) + if (!(e->flags & EDGE_DFS_BACK)) + commondom + = nearest_common_dominator (CDI_DOMINATORS, + e->src, commondom); + if (!(commondom->flags & visited)) + { + commondom->flags |= visited; + toclean.safe_push (commondom); + worklist.safe_push (commondom); + } + break; + } + else if (e->src == frombb) + ; + else if (!(e->src->flags & visited)) + { + if (bitmap_clear_bit (bbs_to_check, e->src->index)) + { + commondom = nearest_common_dominator (CDI_DOMINATORS, + e->src, + commondom); + if (commondom == frombb) + break; + if (!(commondom->flags & visited)) + { + commondom->flags |= visited; + toclean.safe_push (commondom); + worklist.safe_push (commondom); + } + } + else + { + e->src->flags |= visited; + toclean.safe_push (e->src); + worklist.safe_push (e->src); + } + } + } + while (commondom != frombb + && !worklist.is_empty () + && !bitmap_empty_p (bbs_to_check)); + for (basic_block cb : toclean) + cb->flags &= ~visited; if (commondom == frombb) return false; } @@ -848,6 +932,7 @@ pass_sink_code::execute (function *fun) /* Arrange for the critical edge splitting to be undone if requested. */ unsigned todo = unsplit_edges ? TODO_cleanup_cfg : 0; connect_infinite_loops_to_exit (); + mark_dfs_back_edges (fun); memset (&sink_stats, 0, sizeof (sink_stats)); calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS);