From patchwork Thu Sep 18 07:43:53 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 120445 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C15503858C39 for ; Thu, 18 Sep 2025 07:45:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C15503858C39 Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=mNqo/nNi; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=HeYOPXQU; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=enElo3ok; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=cFj6YJcC 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 [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 450123858D33 for ; Thu, 18 Sep 2025 07:43:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 450123858D33 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 450123858D33 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=1758181436; cv=none; b=WkxspykLAAoMbS0qyGx8v3uYim/hhHeYK04/JAmvCKEDYt3+9M/hnAAhW4pBdRIBJeOVddSjP78LxIZs0UypdjiMH09hwGJvT9WYfBiDFq1Mu00CP/o2VkHj1ZpnlEIOVlLfOyHelIBEfcLh4H0hIy5utZW5sSVDzoFHwrJOfAs= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1758181436; c=relaxed/simple; bh=eSYr0RQuIlaUkXO0OLjwvK/uNuWOo8UC41I/IfuC3CM=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=wrCP3UvBVtg/nephYkE030P974BI4oQS++SNilynTmiR962D2YozzzpjOsJ54kAqnIsRmVomBKoE44p7aFGFA9DI94PGxrM2njKFU9siJ/rIYcyIKBKtf6sniHyQgpu/56P/eEzYBNWIMujbSlXIlnrr6GkoG78QUArhT6SN+Gc= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 450123858D33 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 77A4633C7C for ; Thu, 18 Sep 2025 07:43:53 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1758181434; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=kACn7pipUhu+K8+s4dtHxpD+bGppkxssOQfvqLoa6JE=; b=mNqo/nNioMzpTV4m0yIIAygfx2aolkHJtKP7q9ZZdpWI8nM/4VhfntVTjjJUycoyoVM+DR ooNu1svyhl9FOV/c2Kqa55rL3ryi1BS1F1ZHniIZkzppo3vhD5eQZPCFoJaGtKM7kBgO13 ZTX+EtKPcPBCjxWf+SjE9y/+S6lmIrU= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1758181434; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=kACn7pipUhu+K8+s4dtHxpD+bGppkxssOQfvqLoa6JE=; b=HeYOPXQUe8LvvNONWjbckCe0QLjXIR8jh7xQ0mCM6ziAo+IhzzJevXzTtJery+CoEasL02 pIr1OggWBF0uBNCg== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1758181433; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=kACn7pipUhu+K8+s4dtHxpD+bGppkxssOQfvqLoa6JE=; b=enElo3okw0kjnMdskXXPGDolVLnLqJX1wliCQSvJoH9BxCxZGI9oIn2G/260v3mrj0x4Mc lVxqp5en0voNkqIyNlOh2SOM7polrSq3SKE4pX9mV/i0N4mg5z4ND7u1KkqBjDOzw1GTqh 9lzyzHigJaKPFQYOtSA+3rR+Z64EsDc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1758181433; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=kACn7pipUhu+K8+s4dtHxpD+bGppkxssOQfvqLoa6JE=; b=cFj6YJcCAyeCOQWPmW5lvdIdj5lmOOnYH14XVEYZm0YEfZlQoQXp43IM7nhxwlFilp8D0e n40eLKljfZB+T5Cw== Date: Thu, 18 Sep 2025 09:43:53 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/121720 - missed PRE hoisting MIME-Version: 1.0 X-Spamd-Result: default: False [-1.80 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-1.00)[-0.999]; NEURAL_HAM_SHORT(-0.20)[-0.989]; MIME_GOOD(-0.10)[text/plain]; TO_MATCH_ENVRCPT_ALL(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; MISSING_XM_UA(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; TO_DN_NONE(0.00)[]; ARC_NA(0.00)[]; RCVD_COUNT_ZERO(0.00)[0]; FUZZY_RATELIMITED(0.00)[rspamd.com]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; MIME_TRACE(0.00)[0:+]; FROM_HAS_DN(0.00)[] X-Spam-Level: X-Spam-Score: -1.80 X-Spam-Status: No, score=-10.7 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~patchwork=sourceware.org@gcc.gnu.org Message-Id: <20250918074503.C15503858C39@sourceware.org> The following re-implements the fix for PR84830 where the original fix causes missed optimizations. The issue with PR84830 is that we end up growing ANTIC_IN value set during iteration which happens because we conditionally prune values based on ANTIC_OUT - TMP_GEN expressions. But when ANTIC_OUT was computed including the MAX set on one edge we fail to take into account the implicitly represented MAX expression set. The following rectifies this by not pruning the value set in bitmap_set_subtract_expressions in such case. This avoids the pruning from the ANTIC_IN value set when MAX is involved and thus later growing, removing the need to explicitly prune it with the last iteration set. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR tree-optimization/121720 * tree-ssa-pre.cc (bitmap_set_subtract_expressions): Add flag to tell whether we should copy instead of prune the value set. (compute_antic_aux): Remove intersection of ANTIC_IN with the old solution. When subtracting TMP_GEN from ANTIC_OUT do not prune the value set when MAX was involved in the ANTIC_OUT computation. * gcc.dg/tree-ssa/ssa-pre-36.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-36.c | 24 ++++++++ gcc/tree-ssa-pre.cc | 71 ++++++++++------------ 2 files changed, 56 insertions(+), 39 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-36.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-36.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-36.c new file mode 100644 index 00000000000..51de1be2eb5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-36.c @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-pre-stats" } */ + +static unsigned long * +min_element(unsigned long* array, unsigned long size) +{ + unsigned long* min = &array[0]; + + for (unsigned long i = 1; i < size; ++i) + if (array[i] < *min) + min = &array[i]; + + return min; +} + +unsigned long +min(unsigned long* array, unsigned long size) +{ + return *min_element(array, size); +} + +/* We want to hoist the *min dereference before the loop. */ +/* { dg-final { scan-tree-dump "HOIST inserted: 1" "pre" } } */ +/* { dg-final { scan-tree-dump-times "= \\\*" 2 "pre" } } */ diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc index 99331730bc2..18b36259cb4 100644 --- a/gcc/tree-ssa-pre.cc +++ b/gcc/tree-ssa-pre.cc @@ -908,7 +908,8 @@ sorted_array_from_bitmap_set (bitmap_set_t set) /* Subtract all expressions contained in ORIG from DEST. */ static bitmap_set_t -bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig) +bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig, + bool copy_values = false) { bitmap_set_t result = bitmap_set_new (); bitmap_iterator bi; @@ -917,12 +918,15 @@ bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig) bitmap_and_compl (&result->expressions, &dest->expressions, &orig->expressions); - FOR_EACH_EXPR_ID_IN_SET (result, i, bi) - { - pre_expr expr = expression_for_id (i); - unsigned int value_id = get_expr_value_id (expr); - bitmap_set_bit (&result->values, value_id); - } + if (copy_values) + bitmap_copy (&result->values, &dest->values); + else + FOR_EACH_EXPR_ID_IN_SET (result, i, bi) + { + pre_expr expr = expression_for_id (i); + unsigned int value_id = get_expr_value_id (expr); + bitmap_set_bit (&result->values, value_id); + } return result; } @@ -2076,7 +2080,6 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) edge e; edge_iterator ei; - bool was_visited = BB_VISITED (block); bool changed = ! BB_VISITED (block); bool any_max_on_edge = false; @@ -2118,6 +2121,20 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) first = e; else if (BB_VISITED (e->dest)) worklist.quick_push (e); + else if (0 && !(e->flags & EDGE_DFS_BACK)) + { + /* When our reverse iteration order does not match up with + a forward DFS which can in happen with unfortunate + choices of fake edges to exits from infinite loops, we + have to avoid intermangling two ANTIC iterations by + using ANTIC_IN computed in the previous iteration. + As we cannot easily do this stabilize the iteration by + not allowing a MAX set on such edge initially. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "ANTIC_IN is uncomputed on non-DFS_BACK " + "%d->%d\n", e->src->index, e->dest->index); + worklist.quick_push (e); + } else { /* Unvisited successors get their ANTIC_IN replaced by the @@ -2192,8 +2209,13 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) invalid if translated from ANTIC_OUT to ANTIC_IN. */ prune_clobbered_mems (ANTIC_OUT, block, any_max_on_edge); - /* Generate ANTIC_OUT - TMP_GEN. */ - S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block)); + /* Generate ANTIC_OUT - TMP_GEN. Note when there's a MAX solution + on one edge do not prune values as we need to consider the resulting + expression set MAX as well. This avoids a later growing ANTIC_IN + value-set during iteration, when the explicitly represented + expression set grows. */ + S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block), + any_max_on_edge); /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */ ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block), @@ -2207,35 +2229,6 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) /* clean (ANTIC_IN (block)) is defered to after the iteration converged because it can cause non-convergence, see for example PR81181. */ - /* Intersect ANTIC_IN with the old ANTIC_IN. This is required until - we properly represent the maximum expression set, thus not prune - values without expressions during the iteration. */ - if (was_visited - && bitmap_and_into (&ANTIC_IN (block)->values, &old->values)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "warning: intersecting with old ANTIC_IN " - "shrinks the set\n"); - /* Prune expressions not in the value set. */ - bitmap_iterator bi; - unsigned int i; - unsigned int to_clear = -1U; - FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi) - { - if (to_clear != -1U) - { - bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear); - to_clear = -1U; - } - pre_expr expr = expression_for_id (i); - unsigned int value_id = get_expr_value_id (expr); - if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id)) - to_clear = i; - } - if (to_clear != -1U) - bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear); - } - if (!bitmap_set_equal (old, ANTIC_IN (block))) changed = true;