From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 39B223858D26 for ; Wed, 22 May 2024 09:39:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 39B223858D26 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 39B223858D26 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1716370800; cv=none; b=oU9a/gz967NlhGrgfuKm49kjE3EP4PMpRwBIPk4IphUHDcZ/MsdHTRi/qthc6t+t0iGNKItc9BDQdBdj4uF9efNQiJLY3iRJOmZBHETb7hR2IM6ztGDArnyXSr0liWQ9PDF8h5bVbmJgKNYouuq8SQ+QVVZTlzl9isCkzK89xao= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1716370800; c=relaxed/simple; bh=tPlGCdeH9ToTQTtPUxqIo6JeqYBM8NMsTm47QSSccrk=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=rXk8nmqVUvOhI16ikwmFEbnmL2kfXbVErk6hXn+pexOalZUaIFHC+WjJtb+bUhDHdRqHwF2+GFWf1dabzF1U+NVBR2pxIeecjVYTq3sldD7LtQIP2Ga98rYsp7F18X3qh9kx9e3xN5q3caWgyBT079faWDSVKgmbhUqvGfmENkE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from murzim.nue2.suse.org (unknown [10.168.4.243]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 3519B34C50 for ; Wed, 22 May 2024 09:39:57 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1716370797; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=CZ/0nZMruV8tnpjJD5EUE7O/PaSW7EbSrYCiTcP9alg=; b=NWnSqyPFVYHbTxpW7dZAnLUVje16JYctgzT6pv1torpYhPLnZkOXaLwinzxrdQymQgpKQG YuNA4vayZAhWX8jTUJvvIA99IVV8prBcjREp4cjBxHcF5GxxhCJ/LvyiTrLbuhtLHm2S21 +6KxAvF/WxuCMsGT5+aaekoO2G2TToM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1716370797; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=CZ/0nZMruV8tnpjJD5EUE7O/PaSW7EbSrYCiTcP9alg=; b=Bi6SJrKTC3t7HAR/0Ic6ZcT4T9YgeNmWI8Sh+vNJket1TSa6GVRs/bkHpXCI3a7vv9GoFi PVY+20/0nT//RrBA== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1716370797; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=CZ/0nZMruV8tnpjJD5EUE7O/PaSW7EbSrYCiTcP9alg=; b=NWnSqyPFVYHbTxpW7dZAnLUVje16JYctgzT6pv1torpYhPLnZkOXaLwinzxrdQymQgpKQG YuNA4vayZAhWX8jTUJvvIA99IVV8prBcjREp4cjBxHcF5GxxhCJ/LvyiTrLbuhtLHm2S21 +6KxAvF/WxuCMsGT5+aaekoO2G2TToM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1716370797; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=CZ/0nZMruV8tnpjJD5EUE7O/PaSW7EbSrYCiTcP9alg=; b=Bi6SJrKTC3t7HAR/0Ic6ZcT4T9YgeNmWI8Sh+vNJket1TSa6GVRs/bkHpXCI3a7vv9GoFi PVY+20/0nT//RrBA== Date: Wed, 22 May 2024 11:39:57 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/115144 - improve sinking destination choice MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Score: -1.69 X-Spam-Level: X-Spamd-Result: default: False [-1.69 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-0.89)[-0.890]; NEURAL_HAM_SHORT(-0.20)[-0.988]; MIME_GOOD(-0.10)[text/plain]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; ARC_NA(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; FUZZY_BLOCKED(0.00)[rspamd.com]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FROM_HAS_DN(0.00)[]; RCVD_COUNT_ZERO(0.00)[0]; MISSING_XM_UA(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; TO_DN_NONE(0.00)[]; MIME_TRACE(0.00)[0:+] X-Spam-Status: No, score=-10.4 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: <20240522093957.futzCiSy2srelKCW1_p75393unuS_C7hx30T9DOr4gs@z> When sinking code closer to its uses we already try to minimize the distance we move by inserting at the start of the basic-block. The following makes sure to sink closest to the control dependence check of the region we want to sink to as well as make sure to ignore control dependences that are only guarding exceptional code. This restores somewhat the old profile check but without requiring nearly even probabilities. The patch also makes sure to not give up completely when the best sink location is one we do not want to sink to but possibly then choose the next best one. Re-bootstrap and regtest running on x86_64-unknown-linux-gnu after a minor fix. PR tree-optimization/115144 * tree-ssa-sink.cc (do_not_sink): New function, split out from ... (select_best_block): Here. First pick valid block to sink to. From that search for the best valid block, avoiding sinking across conditions to exceptional code. * gcc.dg/tree-ssa/ssa-sink-22.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c | 14 +++ gcc/tree-ssa-sink.cc | 101 +++++++++++++------- 2 files changed, 82 insertions(+), 33 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c new file mode 100644 index 00000000000..e35626d4070 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink1-details" } */ + +extern void abort (void); + +int foo (int x, int y, int f) +{ + int tem = x / y; + if (f) + abort (); + return tem; +} + +/* { dg-final { scan-tree-dump-not "Sinking" "sink1" } } */ diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index 2188b7523c7..a06b43e61af 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -172,6 +172,38 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) return commondom; } +/* Return whether sinking STMT from EARLY_BB to BEST_BB should be avoided. */ + +static bool +do_not_sink (gimple *stmt, basic_block early_bb, basic_block best_bb) +{ + /* Placing a statement before a setjmp-like function would be invalid + (it cannot be reevaluated when execution follows an abnormal edge). + If we selected a block with abnormal predecessors, just punt. */ + if (bb_has_abnormal_pred (best_bb)) + return true; + + /* If the latch block is empty, don't make it non-empty by sinking + something into it. */ + if (best_bb == early_bb->loop_father->latch + && empty_block_p (best_bb)) + return true; + + /* Avoid turning an unconditional read into a conditional one when we + still might want to perform vectorization. */ + if (best_bb->loop_father == early_bb->loop_father + && loop_outer (best_bb->loop_father) + && !best_bb->loop_father->inner + && gimple_vuse (stmt) + && flag_tree_loop_vectorize + && !(cfun->curr_properties & PROP_loop_opts_done) + && dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, early_bb) + && !dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, best_bb)) + return true; + + return false; +} + /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator tree, return the best basic block between them (inclusive) to place statements. @@ -185,54 +217,57 @@ select_best_block (basic_block early_bb, basic_block late_bb, gimple *stmt) { + /* First pick a block we do not disqualify. */ + while (late_bb != early_bb + && do_not_sink (stmt, early_bb, late_bb)) + late_bb = get_immediate_dominator (CDI_DOMINATORS, late_bb); + basic_block best_bb = late_bb; basic_block temp_bb = late_bb; - while (temp_bb != early_bb) { /* Walk up the dominator tree, hopefully we'll find a shallower loop nest. */ temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb); + /* Do not consider blocks we do not want to sink to. */ + if (temp_bb != early_bb && do_not_sink (stmt, early_bb, temp_bb)) + ; + /* If we've moved into a lower loop nest, then that becomes our best block. */ - if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb)) + else if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb)) best_bb = temp_bb; - } - /* Placing a statement before a setjmp-like function would be invalid - (it cannot be reevaluated when execution follows an abnormal edge). - If we selected a block with abnormal predecessors, just punt. */ - if (bb_has_abnormal_pred (best_bb)) - return early_bb; - - /* If we found a shallower loop nest, then we always consider that - a win. This will always give us the most control dependent block - within that loop nest. */ - if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb)) - return best_bb; + /* A higher loop nest is always worse. */ + else if (bb_loop_depth (temp_bb) > bb_loop_depth (best_bb)) + ; - /* Do not move stmts to post-dominating places on the same loop depth. */ - if (dominated_by_p (CDI_POST_DOMINATORS, early_bb, best_bb)) - return early_bb; + /* But sink the least distance, if the new candidate on the same + loop depth is post-dominated by the current best block pick + the new candidate. */ + else if (dominated_by_p (CDI_POST_DOMINATORS, temp_bb, best_bb)) + best_bb = temp_bb; - /* If the latch block is empty, don't make it non-empty by sinking - something into it. */ - if (best_bb == early_bb->loop_father->latch - && empty_block_p (best_bb)) - return early_bb; + /* Avoid sinking across a conditional branching to exceptional + code. In practice this does not reduce the number of dynamic + executions of the sunk statement (this includes EH and + branches leading to abort for example). Treat this case as + post-dominating. */ + else if (single_pred_p (best_bb) + && single_pred_edge (best_bb)->src == temp_bb + && (single_pred_edge (best_bb)->flags & EDGE_FALLTHRU + || (single_pred_edge (best_bb)->probability + >= profile_probability::always ()))) + best_bb = temp_bb; + } - /* Avoid turning an unconditional read into a conditional one when we - still might want to perform vectorization. */ - if (best_bb->loop_father == early_bb->loop_father - && loop_outer (best_bb->loop_father) - && !best_bb->loop_father->inner - && gimple_vuse (stmt) - && flag_tree_loop_vectorize - && !(cfun->curr_properties & PROP_loop_opts_done) - && dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, early_bb) - && !dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, best_bb)) - return early_bb; + gcc_checking_assert (best_bb == early_bb + || (!do_not_sink (stmt, early_bb, best_bb) + && ((bb_loop_depth (best_bb) + < bb_loop_depth (early_bb)) + || !dominated_by_p (CDI_POST_DOMINATORS, + early_bb, best_bb)))); return best_bb; } -- 2.35.3