From patchwork Fri Oct 25 11:50:09 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2002321 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=hPti7yOB; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZln14bpbz1xxG for ; Sat, 26 Oct 2024 01:40:05 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A1D843858417 for ; Fri, 25 Oct 2024 14:40:03 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pg1-x52c.google.com (mail-pg1-x52c.google.com [IPv6:2607:f8b0:4864:20::52c]) by sourceware.org (Postfix) with ESMTPS id 1BCB03858D39 for ; Fri, 25 Oct 2024 14:39:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1BCB03858D39 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1BCB03858D39 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::52c ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867159; cv=none; b=SHmItnywq2iG8RPzYEVyUnVomkEHlXJ3bHOt8X75NZmYv3tDcA0QzXg/TtzSY/PbIMRxNyk2dVvh7Zh/Obc5M/M7usXE5RxsDomfDn8rdTlerdP9finWbjIKV7IXzMOpZydoGQNslRdrny8LJv4QirfW5eSLIgXBsSSkSddbtTg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867159; c=relaxed/simple; bh=puhx2WYrsXAqA+bGunzr0fxxOzUMVMhV6FKrMmRwqFw=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=L8s0TSbljbiz5lmHfD2Fz0Es0zEKaKfywJwUsYJhJqRLZpWs8tIaSOQ/OQIFTLYsDk2BbMAZpNPiOWldJO1RkhXNTApR1nhrB6Xno8dx+NmuBQBm4skhDSfovQxqLrGI5pmbqv/Pqz7VOBdnshIVZheagAfcdrNPK6ogLfOro+Q= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pg1-x52c.google.com with SMTP id 41be03b00d2f7-7edb6879196so1178409a12.3 for ; Fri, 25 Oct 2024 07:39:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1729867143; x=1730471943; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=bCVjSxey+jsqWWkKBP00zz2DSBTuQMi6mCOFfUWdaEk=; b=hPti7yOBXZDJkFskjAHYxloie6PzzSRth/pOdo7yCEBRSbjZGIJCesAoprqT7j0IjR UQkMgvJl5d6zddlu+2pasvZ53cJp01Xlwh2nfTxK7p2n8HcyIMqIHVPMn0410PIZ8791 tHy/9P6S9Qty6A0Nvf9VSDZ/wpn51PwyGIgLyA8nN1rO+/lZQ3yC6OhSh0BAUPQGnVFU 0iG1txMDVa3jnWkFMeAxC1C/BRLHPhDnMzP9lGYuw30B3phoS3Dr5+m1Er+vb053D2rD 6PEy7rBUAGHRcZn3OWqhSXDy6JNwOQf8yGntw4lOPPoN0RowY01Bq1pPaZLiKbYWUhv7 SohA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729867143; x=1730471943; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=bCVjSxey+jsqWWkKBP00zz2DSBTuQMi6mCOFfUWdaEk=; b=GlvpYIpdNQB4w0CsyHIab5Vf/yQG0RzVz5FTBTSkc4BNccMB575exosJlO5TA60rdZ DQD4+EhyVz7SwHMhCrbrea+Uy46uopubS91Jll1VZ+xTEaAmSpI5aZOJxi5PkRezsc54 dazzqwqkZ97ESENBxB+85uoVpYShFREs0VjQwf8CfdopMa7G6uTEW5EcMEbqRolVQth7 fD7bOi/Hk8acTJtB35WLD+oRLQbufj0KjPVm5q/de78eSJU6VrQCH+QTfo90guAYwNSA 9O+W6ZHb4xX4TqqvknQg0nVSOlDuB0q89auOvkecsTZcbXfFuS0XxGmn1zQ/1OUBQdQc Xq8g== X-Gm-Message-State: AOJu0YwLXIZhExBtEJykZNmRnLcpaAVavSiAzBFCma5STZ/o6+b9ZpXC mHp/8iKzrYakKChvyM8JP0K/CtGPRI8+I7C8iU+Ox336yi6Em784PkY3GiHdJjyL6rP/q8R6fnu jow== X-Google-Smtp-Source: AGHT+IFxBQzCjrMZu5HEPiYvBSGMGx2hG+JMuRQTIn6hUlePp7BKw18COJb6LD7lA389nDTnbuZIeA== X-Received: by 2002:a05:6a20:ac43:b0:1d5:2b7f:d2f8 with SMTP id adf61e73a8af0-1d989a30ab4mr8126898637.13.1729867142898; Fri, 25 Oct 2024 07:39:02 -0700 (PDT) Received: from free.home ([2804:14c:4d1:44a5::1002]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7205791d9basm1123267b3a.43.2024.10.25.07.39.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 07:39:02 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 49PBo9P31633735 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 25 Oct 2024 08:50:10 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #1/7] allow vuses in ifcombine blocks (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Fri, 25 Oct 2024 08:50:09 -0300 In-Reply-To: (Alexandre Oliva's message of "Fri, 25 Oct 2024 08:07:13 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, WEIRD_QUOTING 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Disallowing vuses in blocks for ifcombine is too strict, and it prevents usefully moving fold_truth_andor into ifcombine. That tree-level folder has long ifcombined loads, absent other relevant side effects. for gcc/ChangeLog * tree-ssa-ifcombine.c (bb_no_side_effects_p): Allow vuses, but not vdefs. --- gcc/tree-ssa-ifcombine.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index 6a3bc99190d9e..ed20a231951a3 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -129,7 +129,7 @@ bb_no_side_effects_p (basic_block bb) enum tree_code rhs_code; if (gimple_has_side_effects (stmt) || gimple_could_trap_p (stmt) - || gimple_vuse (stmt) + || gimple_vdef (stmt) /* We need to rewrite stmts with undefined overflow to use unsigned arithmetic but cannot do so for signed division. */ || ((ass = dyn_cast (stmt)) From patchwork Sat Nov 2 11:27:11 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2005421 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=hGQDjHgz; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Xgb7R4kxvz1xxy for ; Sat, 2 Nov 2024 22:27:47 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 84E273857C4F for ; Sat, 2 Nov 2024 11:27:45 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pl1-x634.google.com (mail-pl1-x634.google.com [IPv6:2607:f8b0:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 0BD5C3858D33 for ; Sat, 2 Nov 2024 11:27:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0BD5C3858D33 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0BD5C3858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::634 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730546846; cv=none; b=WJMVGs4U+2gkeTg3DtQDaLtik86EFba26MY34DEBk0FCxy+9yrwgFhUwjf7fQ/RrYQZ0acXhai6V2Q9ntwM3MGlr+Xa2ExunspnKcB2je8zBZxiF2wJrjNmXtpbDaZhTLJbmqbjFoKAmeDJpq8U2qmAOasy5ZQeapLsouxZGEPw= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730546846; c=relaxed/simple; bh=T5LYJrmTI1CtMkX7xIi9d0SkS6xIyb9APCxRZ/tzVus=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=X+pfA+oS/fck8ogSV7mT72ym2Vud9XYEN9XmFbBXCsA9lgAi4CsX+F3YqWwpRTiomGDUlsCEF6175fPk7apTkDZlodtrHykVzrAjkVRBgKJCOz/AzpXtRX387Ej3PcAVA8Dlmd/WBUQhzYIUTIHoA+CG7Kq3lRGVPT00xDKl2Gc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x634.google.com with SMTP id d9443c01a7336-20cf6eea3c0so23071205ad.0 for ; Sat, 02 Nov 2024 04:27:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1730546843; x=1731151643; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=nEkcqjhVgNFgBuCu5Uj5K7XCZou/mdOWIR0usjnBXlM=; b=hGQDjHgzlDgWHGUvS9hPkSo20Fs2LyUfZ0Qec2MOOpLVNEP41uTmPwgrfq3aHP5sjS 2vhJ+rlu9OyXUXPjobE4dB8yqef8rF+hbmJBtzdhFXUuwl5N5tT41+fuqvdRL4naSTeb rddAR6dC1ep3UG1JWJTrmZCk/htt1jBVSEb5+78fbWy8/KRdA8ZSMrvXB/uhzaYrx0kB RQ5tOMOU5pLJ4Er4COkGgVvQoWueKix+lgRYf5qUPzrwLfPRqVbrEvxZSy4eDW65RATN 6Ub9779oPeteqUngTsb9JXUp/9Ms7BX7ApAq0Mghh7E21ijty/3ba5Csi6BIotpX8MQi 4O1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730546843; x=1731151643; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=nEkcqjhVgNFgBuCu5Uj5K7XCZou/mdOWIR0usjnBXlM=; b=ec7OL5tQVDxpRP1tVoDcgS6Ly3oBdsrxaZjTOYQtnoycB+iOlL9JX5d9KzIH0vZngl 0ZSof/ZPNSOtR29lJn89x+MePYQGUA9bMdrshOTl3rd+QrixS1Rzj4v32au3Tvx46Gn8 WQoceub0kA+t79La3vgGyG8PWuS3VVXENBWbOoR5JU1WEZHBj7I7ww6e2a409lghdtLQ IqqL0Lqz0RPw/vCh1+QaDbdYXvKciR+OUz5wXgCZcG1brHCCttgSkHacmUHwGT36FWk3 iuOlKa+L7EFX1xlGelX9H0LuKJHBiy+tYPyzPuQkdx/2VgYlP1dhZ2+eVIB0B2OkUjpe mI4w== X-Gm-Message-State: AOJu0YzwGMx+x3BTtZ5aXHfNioGpCmlkZQ9aLWCutSUQXZBLyNIuCauf J7JT6ld1MRK39GpQBwYUI4MhDzi4rLvsZ8F9GxbEStZV7M0mw25V3fnVQekUxQ== X-Google-Smtp-Source: AGHT+IGy5xnwCij90DCYf8A+KLHTexZNKlBQzAqDGLhcvQwqApAkrrm4eHUJHH9N3LDbaQ+6D3BUUw== X-Received: by 2002:a17:902:e851:b0:20c:a644:c5bf with SMTP id d9443c01a7336-210c69e6da0mr323288095ad.31.1730546843033; Sat, 02 Nov 2024 04:27:23 -0700 (PDT) Received: from free.home ([2804:7f1:218a:e46a:9e48:eab6:3a44:4bc0]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-211057d469bsm32038505ad.271.2024.11.02.04.27.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 02 Nov 2024 04:27:22 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 4A2BRBkt1947808 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Sat, 2 Nov 2024 08:27:11 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [FYI #5v2/7] extend ifcombine_replace_cond to handle noncontiguous ifcombine Organization: Free thinker, does not speak for AdaCore References: Date: Sat, 02 Nov 2024 08:27:11 -0300 In-Reply-To: (Richard Biener's message of "Wed, 30 Oct 2024 15:17:20 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Here's the adjusted patch that I'll push once #6/7 and #8/7++ are also approved. Retested along with them. Prepare to handle noncontiguous ifcombine, introducing logic to modify the outer condition when needed. There are two cases worth mentioning: - when blocks are noncontiguous, we have to place the combined condition in the outer block to avoid pessimizing carefully crafted short-circuited tests; - even when blocks are contiguous, we prepare for situations in which the combined condition has two tests, one to be placed in outer and the other in inner. This circumstance will not come up when noncontiguous ifcombine is first enabled, but it will when an improved fold_truth_andor is integrated with ifcombine. Combining the condition from inner into outer may require moving SSA DEFs used in the inner condition, and the changes implement this as well. for gcc/ChangeLog * tree-ssa-ifcombine.cc: Include bitmap.h. (ifcombine_mark_ssa_name): New. (struct ifcombine_mark_ssa_name_t): New. (ifcombine_mark_ssa_name_walk): New. (ifcombine_replace_cond): Prepare to handle noncontiguous and split-condition ifcombine. --- gcc/tree-ssa-ifcombine.cc | 175 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 170 insertions(+), 5 deletions(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index b5b72be29bbf9..42b6055121c16 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa.h" #include "attribs.h" #include "asan.h" +#include "bitmap.h" #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT #define LOGICAL_OP_NON_SHORT_CIRCUIT \ @@ -460,17 +461,57 @@ update_profile_after_ifcombine (basic_block inner_cond_bb, } } -/* Replace the conditions in INNER_COND with COND. - Replace OUTER_COND with a constant. */ +/* Set NAME's bit in USED if OUTER dominates it. */ + +static void +ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer) +{ + if (SSA_NAME_IS_DEFAULT_DEF (name)) + return; + + gimple *def = SSA_NAME_DEF_STMT (name); + basic_block bb = gimple_bb (def); + if (!dominated_by_p (CDI_DOMINATORS, bb, outer)) + return; + + bitmap_set_bit (used, SSA_NAME_VERSION (name)); +} + +/* Data structure passed to ifcombine_mark_ssa_name. */ +struct ifcombine_mark_ssa_name_t +{ + /* SSA_NAMEs that have been referenced. */ + bitmap used; + /* Dominating block of DEFs that might need moving. */ + basic_block outer; +}; + +/* Mark in DATA->used any SSA_NAMEs used in *t. */ + +static tree +ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_) +{ + ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_; + + if (*t && TREE_CODE (*t) == SSA_NAME) + ifcombine_mark_ssa_name (data->used, *t, data->outer); + + return NULL; +} + +/* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2. + COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND + replaced with a constant, but if there are intervening blocks, it's best to + adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND. */ static bool ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, gcond *outer_cond, bool outer_inv, tree cond, bool must_canon, tree cond2) { - bool result_inv = inner_inv; - - gcc_checking_assert (!cond2); + bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond)) + != gimple_bb (outer_cond)); + bool result_inv = outer_p ? outer_inv : inner_inv; if (result_inv) cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond); @@ -480,6 +521,130 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, else if (must_canon) return false; + if (outer_p) + { + { + auto_bitmap used; + basic_block outer_bb = gimple_bb (outer_cond); + + bitmap_tree_view (used); + + /* Mark SSA DEFs that are referenced by cond and may thus need to be + moved to outer. */ + { + ifcombine_mark_ssa_name_t data = { used, outer_bb }; + walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL); + } + + if (!bitmap_empty_p (used)) + { + /* Iterate up from inner_cond, moving DEFs identified as used by + cond, and marking USEs in the DEFs for moving as well. */ + gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond); + for (basic_block bb = gimple_bb (inner_cond); + bb != outer_bb; bb = single_pred (bb)) + { + for (gimple_stmt_iterator gsitr = gsi_last_bb (bb); + !gsi_end_p (gsitr); gsi_prev (&gsitr)) + { + gimple *stmt = gsi_stmt (gsitr); + bool move = false; + tree t; + ssa_op_iter it; + + FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF) + if (bitmap_bit_p (used, SSA_NAME_VERSION (t))) + { + move = true; + break; + } + + if (!move) + continue; + + /* Mark uses in STMT before moving it. */ + FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE) + ifcombine_mark_ssa_name (used, t, outer_bb); + + gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT); + } + + /* Surprisingly, there may be PHI nodes in single-predecessor + bocks, as in pr50682.C. Fortunately, since they can't + involve back edges, there won't be references to parallel + nodes that we'd have to pay special attention to to keep + them parallel. We can't move the PHI nodes, but we can turn + them into assignments. */ + for (gphi_iterator gsi = gsi_start_phis (bb); + !gsi_end_p (gsi);) + { + gphi *phi = gsi.phi (); + + gcc_assert (gimple_phi_num_args (phi) == 1); + tree def = gimple_phi_result (phi); + + if (!bitmap_bit_p (used, SSA_NAME_VERSION (def))) + { + gsi_next (&gsi); + continue; + } + + /* Mark uses in STMT before moving it. */ + use_operand_p use_p; + ssa_op_iter it; + FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE) + ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p), + outer_bb); + + tree use = gimple_phi_arg_def (phi, 0); + location_t loc = gimple_phi_arg_location (phi, 0); + + remove_phi_node (&gsi, false); + + gassign *a = gimple_build_assign (def, use); + gimple_set_location (a, loc); + gsi_insert_before (&gsins, a, GSI_NEW_STMT); + } + } + } + } + + if (!is_gimple_condexpr_for_cond (cond)) + { + gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond); + cond = force_gimple_operand_gsi_1 (&gsi, cond, + is_gimple_condexpr_for_cond, + NULL, true, GSI_SAME_STMT); + } + + /* Leave CFG optimization to cfg_cleanup. */ + gimple_cond_set_condition_from_tree (outer_cond, cond); + update_stmt (outer_cond); + + if (cond2) + { + if (inner_inv) + cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2); + + if (tree tcanon = canonicalize_cond_expr_cond (cond2)) + cond2 = tcanon; + if (!is_gimple_condexpr_for_cond (cond2)) + { + gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond); + cond2 = force_gimple_operand_gsi_1 (&gsi, cond2, + is_gimple_condexpr_for_cond, + NULL, true, GSI_SAME_STMT); + } + gimple_cond_set_condition_from_tree (inner_cond, cond2); + } + else + gimple_cond_set_condition_from_tree (inner_cond, + inner_inv + ? boolean_false_node + : boolean_true_node); + update_stmt (inner_cond); + } + else { if (!is_gimple_condexpr_for_cond (cond)) { From patchwork Fri Oct 25 11:52:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2002322 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=jIS6+4pI; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZlp455Vyz1xwy for ; Sat, 26 Oct 2024 01:41:00 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 98F623858282 for ; Fri, 25 Oct 2024 14:40:58 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pf1-x42e.google.com (mail-pf1-x42e.google.com [IPv6:2607:f8b0:4864:20::42e]) by sourceware.org (Postfix) with ESMTPS id CFC1A3858C42 for ; Fri, 25 Oct 2024 14:39:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CFC1A3858C42 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org CFC1A3858C42 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::42e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867163; cv=none; b=P2+ovlZ/JuH9LF9/eDKx4XU9m9i6b/bH8yvZkzSLEDME7CEIcnwgLnfi4N/q9jYk+gt+rsmgvFr6crMNk91SWWcv63gFx0y6RqChp16qcTY5QxEcCpBJ+mRMKGoUmxSdFa7SsxwfriG6C3G1OcQlr8udBQlrG4jDnF16wqfBjS4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867163; c=relaxed/simple; bh=zAW6FdhbAGDDxzO5V7L1mf7To0fjoAdfLmCG4F202Gk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=jRi4iq8hAzPjdlxlquYZYRU6CwLAydlc7YLj1q1SJokvCAXXoFJUq0eKW+wNrklbWiG/3ADdPNTlHwUhovg0+62OwpmfV7PFVPrTtKgqsjY2b3fQbL9Nd/dYvb5HwTELXhrGItxohdYPZjmRmbS9AwNHjXfHLPFqCeErNWwWoig= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pf1-x42e.google.com with SMTP id d2e1a72fcca58-71e5a62031aso1498537b3a.1 for ; Fri, 25 Oct 2024 07:39:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1729867148; x=1730471948; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=kw1BD1MXG98qyOWc98QhUl+9kxVGf5mOJSwt8XimuC8=; b=jIS6+4pIZuTg1DUzXGMmqdqo/7kOQ2aWD/aAo7vZWPL8T8kQnxg8FF/J1dSE8XVr5f yPeWqoYpMZZQLjuGyrIfwgEVz4hO7JOJI345M7Xox93eJw4vwksGAJX3shBCmy4XBLSg SMVfd4b6cZLxN7J0n46oluqg6QHZPRVfZgf8PSq/UdoJKAIiJJ6LOlSaYXiszsZM5GT5 86b++dp1ozAW/1JZdgfSYNWopXvYPr2rSiRA7BSlzJ2Exf68enFq9F4WfGc1uhdSTIAA ncR4R4E7uPjfSjdHygXlTU2uEA0fJhSs+be6qM1z63oeIzBv3Ouco7GAiCMjYWi3FZo/ pyzQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729867148; x=1730471948; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=kw1BD1MXG98qyOWc98QhUl+9kxVGf5mOJSwt8XimuC8=; b=ZmCRZZw+9vXsz3mh32cjIDoe7uK4HZHuyW3s8MdELd5oER7S7eHa//0eYY6YLnoXob uPdGrkL3u61Y8TillaKBcNMLlK7ikxjUEnyUZbXXMFsLkJ0wigU1uOqNegaV4WmErFHp CAnOqbMjoazUsS3gfPDW27CFc86cDXnHQLaV5ZZwX6j9TUs5ekQW2Ph/NU7tGBAq6UT3 v1Q4YgbTEDN2+GSWfbJYOkOqAtM83CP1f6RO3kzh9NBWZOpq7ezSAfhigA0Mb/BhMooM U3auaKHv13HG0E5QArNajCXTKDn79moYP6k0KVWLWJaqH7rXYcM8m6rfCWHmkwa3UUNJ khPA== X-Gm-Message-State: AOJu0Yx5+j2a6cHssy7dHmehq/4CAjNu6ydyX37+3YYq5w/4g8hBnJpZ lGOWi9eFvdpjvBJtMnIduei7vdORs8g0LFVfjeN++Y+wTx767q0Bz4Scev5lmJqer8HaeuKYLeG wZw== X-Google-Smtp-Source: AGHT+IGDXjkBjnCTCl0mHluGH21UXid4TRG3Sd7mr+SGffI5xYYcFJprSDqkXjFsl128buz2Ixisow== X-Received: by 2002:a05:6a00:230a:b0:710:6e83:cd5e with SMTP id d2e1a72fcca58-7203097fce5mr14402792b3a.0.1729867147553; Fri, 25 Oct 2024 07:39:07 -0700 (PDT) Received: from free.home ([2804:14c:4d1:44a5::1002]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7205791d9basm1123267b3a.43.2024.10.25.07.39.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 07:39:07 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 49PBqlh61633844 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 25 Oct 2024 08:52:48 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #3/7] introduce ifcombine_replace_cond (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Fri, 25 Oct 2024 08:52:47 -0300 In-Reply-To: (Alexandre Oliva's message of "Fri, 25 Oct 2024 08:07:13 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, WEIRD_QUOTING 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Refactor ifcombine_ifandif, moving the common code from the various paths that apply the combined condition to a new function. for gcc/ChangeLog * tree-ssa-ifcombine.cc (ifcombine_replace_cond): Factor out of... (ifcombine_ifandif): ... this. --- gcc/tree-ssa-ifcombine.cc | 137 +++++++++++++++++++++------------------------ 1 file changed, 65 insertions(+), 72 deletions(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index 0a2ba970548c8..6dcf5e6efe1de 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -399,6 +399,51 @@ update_profile_after_ifcombine (basic_block inner_cond_bb, outer2->probability = profile_probability::never (); } +/* Replace the conditions in INNER_COND with COND. + Replace OUTER_COND with a constant. */ + +static bool +ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, + gcond *outer_cond, bool outer_inv, + tree cond, bool must_canon, tree cond2) +{ + bool result_inv = inner_inv; + + gcc_checking_assert (!cond2); + + if (result_inv) + cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond); + + if (tree tcanon = canonicalize_cond_expr_cond (cond)) + cond = tcanon; + else if (must_canon) + return false; + + { + if (!is_gimple_condexpr_for_cond (cond)) + { + gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond); + cond = force_gimple_operand_gsi_1 (&gsi, cond, + is_gimple_condexpr_for_cond, + NULL, true, GSI_SAME_STMT); + } + gimple_cond_set_condition_from_tree (inner_cond, cond); + update_stmt (inner_cond); + + /* Leave CFG optimization to cfg_cleanup. */ + gimple_cond_set_condition_from_tree (outer_cond, + outer_inv + ? boolean_false_node + : boolean_true_node); + update_stmt (outer_cond); + } + + update_profile_after_ifcombine (gimple_bb (inner_cond), + gimple_bb (outer_cond)); + + return true; +} + /* If-convert on a and pattern with a common else block. The inner if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. inner_inv, outer_inv indicate whether the conditions are inverted. @@ -408,7 +453,6 @@ static bool ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, basic_block outer_cond_bb, bool outer_inv) { - bool result_inv = inner_inv; gimple_stmt_iterator gsi; tree name1, name2, bit1, bit2, bits1, bits2; @@ -446,26 +490,13 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE, true, GSI_SAME_STMT); - t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, - boolean_type_node, t2, t); - t = canonicalize_cond_expr_cond (t); - if (!t) - return false; - if (!is_gimple_condexpr_for_cond (t)) - { - gsi = gsi_for_stmt (inner_cond); - t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond, - NULL, true, GSI_SAME_STMT); - } - gimple_cond_set_condition_from_tree (inner_cond, t); - update_stmt (inner_cond); - /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, - outer_inv ? boolean_false_node : boolean_true_node); - update_stmt (outer_cond); + t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t); - update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb); + if (!ifcombine_replace_cond (inner_cond, inner_inv, + outer_cond, outer_inv, + t, true, NULL_TREE)) + return false; if (dump_file) { @@ -485,9 +516,8 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, In that case remove the outer test and change the inner one to test for name & (bits1 | bits2) != 0. */ else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv) - && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv)) + && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv)) { - gimple_stmt_iterator gsi; tree t; if ((TREE_CODE (name1) == SSA_NAME @@ -530,33 +560,14 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, bits1 = fold_convert (TREE_TYPE (bits2), bits1); } - /* Do it. */ - gsi = gsi_for_stmt (inner_cond); t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2); - t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, - true, GSI_SAME_STMT); t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); - t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, - true, GSI_SAME_STMT); - t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t, + t = fold_build2 (EQ_EXPR, boolean_type_node, t, build_int_cst (TREE_TYPE (t), 0)); - t = canonicalize_cond_expr_cond (t); - if (!t) + if (!ifcombine_replace_cond (inner_cond, inner_inv, + outer_cond, outer_inv, + t, false, NULL_TREE)) return false; - if (!is_gimple_condexpr_for_cond (t)) - { - gsi = gsi_for_stmt (inner_cond); - t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond, - NULL, true, GSI_SAME_STMT); - } - gimple_cond_set_condition_from_tree (inner_cond, t); - update_stmt (inner_cond); - - /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, - outer_inv ? boolean_false_node : boolean_true_node); - update_stmt (outer_cond); - update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb); if (dump_file) { @@ -576,7 +587,7 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison) { - tree t; + tree t, ts = NULL_TREE; enum tree_code inner_cond_code = gimple_cond_code (inner_cond); enum tree_code outer_cond_code = gimple_cond_code (outer_cond); @@ -602,7 +613,6 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, gimple_bb (outer_cond)))) { tree t1, t2; - gimple_stmt_iterator gsi; bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT; if (param_logical_op_non_short_circuit != -1) logical_op_non_short_circuit @@ -624,39 +634,22 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, gimple_cond_rhs (outer_cond)); t = fold_build2_loc (gimple_location (inner_cond), TRUTH_AND_EXPR, boolean_type_node, t1, t2); - if (result_inv) - { - t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t); - result_inv = false; - } - gsi = gsi_for_stmt (inner_cond); - t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond, - NULL, true, GSI_SAME_STMT); } - if (result_inv) - t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t); - t = canonicalize_cond_expr_cond (t); - if (!t) - return false; - if (!is_gimple_condexpr_for_cond (t)) - { - gsi = gsi_for_stmt (inner_cond); - t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond, - NULL, true, GSI_SAME_STMT); - } - gimple_cond_set_condition_from_tree (inner_cond, t); - update_stmt (inner_cond); - /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, - outer_inv ? boolean_false_node : boolean_true_node); - update_stmt (outer_cond); - update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb); + if (!ifcombine_replace_cond (inner_cond, inner_inv, + outer_cond, outer_inv, + t, false, ts)) + return false; if (dump_file) { fprintf (dump_file, "optimizing two comparisons to "); print_generic_expr (dump_file, t); + if (ts) + { + fprintf (dump_file, " and "); + print_generic_expr (dump_file, ts); + } fprintf (dump_file, "\n"); } From patchwork Fri Oct 25 11:54:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2002323 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=SyTpr+DI; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZlp70yF3z1xwy for ; Sat, 26 Oct 2024 01:41:03 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0DFA83858280 for ; Fri, 25 Oct 2024 14:41:01 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pg1-x52a.google.com (mail-pg1-x52a.google.com [IPv6:2607:f8b0:4864:20::52a]) by sourceware.org (Postfix) with ESMTPS id 5CA243858C98 for ; Fri, 25 Oct 2024 14:39:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5CA243858C98 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 5CA243858C98 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::52a ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867152; cv=none; b=CMjQoxqdFxpw4EviJQmxmXyOgB4dtvn1nHk3syWpyjojbEQdKYdB5R60ypPDGGDuewJc2Z+ZITvyZUWyFaDmQ2g8ysCHQ02QvkPQ0V3zeeanPN6yiNHBaBmbTVve+7ykr5IIIombE2ShWbq/rXVxRLQ1h6ibJ1PB5zF+x6TybKg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867152; c=relaxed/simple; bh=eYTWm/V5fxJc31xy7On5KnH/rP7Jki6+HNAxHw/RJvc=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=OyHz1lwYt6ZLDMqg09OD9f+wDJf4AQhBfLKzjyBTyO9GVNoUnJtjE0SEGOOPDHuSlkjdTUtV4h2L0wMrkc6X9rJNMZqcUKC4Y0ecFnnu3sGq4dvsYVp89dV5HAL9ll2Nc4OeN+X6MuipjAwBrYOsNWM029/xP+oGCV+DlUQAz6Q= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pg1-x52a.google.com with SMTP id 41be03b00d2f7-7ea7ad1e01fso1438372a12.0 for ; Fri, 25 Oct 2024 07:39:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1729867146; x=1730471946; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=nbBGZwgzs6IZx8bn6+hmib4uefLaBoyaT+hVpGRYyk0=; b=SyTpr+DIJiOzIPYRGaK281grAOj63fLREIEENUCGYYZW/vI10q0AvuCnSYXIft7Wgw kdLz2TJme/3xfLMN7gQBkad9QPQxi6YchaWpXlZTd7LqTds3IL+XYJ27dWvkKBsJr5RF pqL24OPQ3T6gixotfb4cGdHxk4n2jmHH5+HJc6xPfecEDkepL76rGfndAOyNjTMFN0li jKFGyT6QalPmdyZYXtGvHdUhOoEGMxzsb0OidueACpHGrUMCoWnJPdPaQV3vd68DbHm+ QB6VSynzJAAYxQcR3DaFuZIbSBrQ718p0U28qcOKd1SthPR5S+ObtyJDuk35DbebFO9o iIjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729867146; x=1730471946; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=nbBGZwgzs6IZx8bn6+hmib4uefLaBoyaT+hVpGRYyk0=; b=gRT9AQTQftMnKEIs7kS3UTO8Ghq6VIiYuyRuwxgQNFgQrD6hRB0t7blsUEkTh1z2vj TD22klfPwL9IZRvRg7ThG5cLZG++juFMAFMbWFVwLqpu45SzZnHUEFDj3NCG57wfXV5T BnE1D4C9hg+p+bOFPZ1ngWhlf0yNMjn87ENHhxG/3MYboAEwiWZnQ8grzPDDL53U0xpX ThfAnG1El+yCMT0OhvVgQo1/AJC45dEkyX5xOwMnS3IyC8t+hi8GsekmqR5AFjfFfd+E +lOqixN9ktZsuvIAmPrK6iovmIucTlVlzrUtW6oDLC+C5tvn8tSo9KiGvDYjWWPX6UqL ScdQ== X-Gm-Message-State: AOJu0Yze73sQY6pH22CXkUz5Fj6JvGR+okRDzLO5xnD13PQ4W6pNktiT AzDAiHk0UzdoBP8LtX0PJFaWW++TbMvYjp22jeXREfZtux6LgFNn66RbOT4TpF7mrI/n6bANiHA qFw== X-Google-Smtp-Source: AGHT+IHsbNjfkEL1gw+2ncHh/nd2l2/DOwnSyA1X0SplE7sfCdZxxWm0H+54BT3dgauCTsaLFPPztg== X-Received: by 2002:a05:6a21:394a:b0:1d9:3acf:8bdd with SMTP id adf61e73a8af0-1d988997592mr9988071637.22.1729867146133; Fri, 25 Oct 2024 07:39:06 -0700 (PDT) Received: from free.home ([2804:14c:4d1:44a5::1002]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7205791d9basm1123267b3a.43.2024.10.25.07.39.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 07:39:05 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 49PBsGcq1633877 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 25 Oct 2024 08:54:16 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #4/7] adjust update_profile_after_ifcombine for noncontiguous ifcombine (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Fri, 25 Oct 2024 08:54:16 -0300 In-Reply-To: (Alexandre Oliva's message of "Fri, 25 Oct 2024 08:07:13 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, WEIRD_QUOTING 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Prepare for ifcombining noncontiguous blocks, adding (still unused) logic to the ifcombine profile updater to handle such cases. for gcc/ChangeLog * tree-ssa-ifcombine.cc (known_succ_p): New. (update_profile_after_ifcombine): Handle noncontiguous blocks. --- gcc/tree-ssa-ifcombine.cc | 109 +++++++++++++++++++++++++++++++++++---------- 1 file changed, 85 insertions(+), 24 deletions(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index 6dcf5e6efe1de..b5b72be29bbf9 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -49,6 +49,21 @@ along with GCC; see the file COPYING3. If not see false) >= 2) #endif +/* Return FALSE iff the COND_BB ends with a conditional whose result is not a + known constant. */ + +static bool +known_succ_p (basic_block cond_bb) +{ + gcond *cond = safe_dyn_cast (*gsi_last_bb (cond_bb)); + + if (!cond) + return true; + + return (CONSTANT_CLASS_P (gimple_cond_lhs (cond)) + && CONSTANT_CLASS_P (gimple_cond_rhs (cond))); +} + /* This pass combines COND_EXPRs to simplify control flow. It currently recognizes bit tests and comparisons in chains that represent logical and or logical or of two COND_EXPRs. @@ -356,14 +371,28 @@ recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv) } -/* Update profile after code in outer_cond_bb was adjusted so - outer_cond_bb has no condition. */ +/* Update profile after code in either outer_cond_bb or inner_cond_bb was + adjusted so that it has no condition. */ static void update_profile_after_ifcombine (basic_block inner_cond_bb, basic_block outer_cond_bb) { - edge outer_to_inner = find_edge (outer_cond_bb, inner_cond_bb); + /* In the following we assume that inner_cond_bb has single predecessor. */ + gcc_assert (single_pred_p (inner_cond_bb)); + + basic_block outer_to_inner_bb = inner_cond_bb; + profile_probability prob = profile_probability::always (); + for (;;) + { + basic_block parent = single_pred (outer_to_inner_bb); + prob *= find_edge (parent, outer_to_inner_bb)->probability; + if (parent == outer_cond_bb) + break; + outer_to_inner_bb = parent; + } + + edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb); edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner ? EDGE_SUCC (outer_cond_bb, 1) : EDGE_SUCC (outer_cond_bb, 0)); @@ -374,29 +403,61 @@ update_profile_after_ifcombine (basic_block inner_cond_bb, std::swap (inner_taken, inner_not_taken); gcc_assert (inner_taken->dest == outer2->dest); - /* In the following we assume that inner_cond_bb has single predecessor. */ - gcc_assert (single_pred_p (inner_cond_bb)); - - /* Path outer_cond_bb->(outer2) needs to be merged into path - outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken) - and probability of inner_not_taken updated. */ - - inner_cond_bb->count = outer_cond_bb->count; + if (outer_to_inner_bb == inner_cond_bb + && known_succ_p (outer_cond_bb)) + { + /* Path outer_cond_bb->(outer2) needs to be merged into path + outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken) + and probability of inner_not_taken updated. */ + + inner_cond_bb->count = outer_cond_bb->count; + + /* Handle special case where inner_taken probability is always. In this + case we know that the overall outcome will be always as well, but + combining probabilities will be conservative because it does not know + that outer2->probability is inverse of + outer_to_inner->probability. */ + if (inner_taken->probability == profile_probability::always ()) + ; + else + inner_taken->probability = outer2->probability + + outer_to_inner->probability * inner_taken->probability; + inner_not_taken->probability = profile_probability::always () + - inner_taken->probability; - /* Handle special case where inner_taken probability is always. In this case - we know that the overall outcome will be always as well, but combining - probabilities will be conservative because it does not know that - outer2->probability is inverse of outer_to_inner->probability. */ - if (inner_taken->probability == profile_probability::always ()) - ; + outer_to_inner->probability = profile_probability::always (); + outer2->probability = profile_probability::never (); + } + else if (known_succ_p (inner_cond_bb)) + { + /* Path inner_cond_bb->(inner_taken) needs to be merged into path + outer_cond_bb->(outer2). We've accumulated the probabilities from + outer_cond_bb->(outer)->...->inner_cond_bb in prob, so we have to + adjust that by inner_taken, and make inner unconditional. */ + + prob *= inner_taken->probability; + outer2->probability += prob; + outer_to_inner->probability = profile_probability::always () + - outer2->probability; + + inner_taken->probability = profile_probability::never (); + inner_not_taken->probability = profile_probability::always (); + } else - inner_taken->probability = outer2->probability + outer_to_inner->probability - * inner_taken->probability; - inner_not_taken->probability = profile_probability::always () - - inner_taken->probability; - - outer_to_inner->probability = profile_probability::always (); - outer2->probability = profile_probability::never (); + { + /* We've moved part of the inner cond to outer, but we don't know the + probabilities for each part, so estimate the effects by moving half of + the odds of inner_taken to outer. */ + + inner_taken->probability *= profile_probability::even (); + inner_not_taken->probability = profile_probability::always () + - inner_taken->probability; + + prob *= inner_taken->probability; + outer2->probability += prob; + outer_to_inner->probability = profile_probability::always () + - outer2->probability; + } } /* Replace the conditions in INNER_COND with COND. From patchwork Fri Oct 25 11:55:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2002325 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=PXSH9BdN; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZlqN0QXjz1xwy for ; Sat, 26 Oct 2024 01:42:08 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E487E3858D39 for ; Fri, 25 Oct 2024 14:42:05 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pj1-x1032.google.com (mail-pj1-x1032.google.com [IPv6:2607:f8b0:4864:20::1032]) by sourceware.org (Postfix) with ESMTPS id 9E0F63858CDA for ; Fri, 25 Oct 2024 14:39:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9E0F63858CDA Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 9E0F63858CDA Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::1032 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867163; cv=none; b=oJP6S6bR6AkGzqUJ1nm/ki8HbMesVn/OJJtoWAnkm4nL9ciiFB4DsWlQHv1gsuwMJb7UN3hgyMY5tegKbTXHbs22BC99HXOAKv/ZpZsyfxL9oFPzrDC0MQ74geRT2iKVLgs2BpLQya+xRp9O79vlc/1cquqpcJmZgve8ldH90k4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867163; c=relaxed/simple; bh=ARpdW9Q+SfNqPFj/Cxek4AjWxxD/ASyUyV7cIyFRu5s=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=nB7bSVms9LsBUno5GNq7+s5lVDdaCXtNqtP/zkVw0YvPxAYDCbMB+gK6G7oGlIqLjA2nZ5KFoimE8odmFynea4mTEmRG/aW2Su4+qDsA8+UmMY25bWlgnEm/9Dd6K7C9sIdJ2J1XItUXx+dKR2xuU1KvBXeJSLGLhSVZGo9W4BE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pj1-x1032.google.com with SMTP id 98e67ed59e1d1-2e3d523a24dso1631486a91.0 for ; Fri, 25 Oct 2024 07:39:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1729867147; x=1730471947; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=buTvauyjRj7ouKKtZMKPDmqqLAF6aGhWfd0foNcOlSw=; b=PXSH9BdN9gHeENpWFscRq3CDcVDUcPSwdO+mHqY+k6ENGIR9y9xIySPzpSimFwMyZC Bv+CrhQz/Gubqu8/6Ced2YyYVgE9ZMFRbeRQiHqrE9nw8Ke+4RpFXM+HSxH/RO8j4Y5A +7zTqvWjGeUB2zwRbpbspx/0+ywWDffpoc1cGfYduWSamVZuNZTo72oGG0P3OWfL1Yp9 4U8bG+aZgAKrX+MJxARq+1WkM/ys4a3FnRdvNyPF8WjKd5k2ko4ELQ0a3nuWTwN/L2Wk tBqfA3VTCFPaijBMYjZnR7t3ImlW9xdRbJDp/utmA4xZZgG2JKEdxLodbDaNtfrapPUo SKxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729867147; x=1730471947; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=buTvauyjRj7ouKKtZMKPDmqqLAF6aGhWfd0foNcOlSw=; b=EPyIs1WxLFuOvBtIvcX6cxwr2wkhz6666xWpSnKRIhJxuYoaZwitKqw2aCvmf0XMNv ffFD6j0PJTsnhGLE633gzj3IZikvjtf3cCtUYDk4ud9JCP+eit3UPpej4Dc+TlsDT3HC 39TN1sWkOou2qekrLkDIAPBPtw7NdD3lgHZPswO8YSjhgWoJ04ca/YgG4O0dlsqHYxA5 CZtngS6qEcXw4nBIdZtMwmPIIH0ywvCxFmO3uY7RKjrNsXbak7ucZ+9XIqJmMqFPM/YU QW8oRRIpmoL8XiPKLwlKbalCmdIjPYdy30sVXDkMWCjgihw/NOKxxJVCd5sK4IsvAHTd es4w== X-Gm-Message-State: AOJu0YyaHxgguEfW9mtfXFpWt2GzcAa8GYmktWoaiptdK7evqA3aFW8b aDYq6c2sg9lhiJ9A9BFSn+sU0REv2hdCLCX/33Bw4dJxR4kgHpnNZQqfdUoqbGgd1mjrvmUvwTD A8g== X-Google-Smtp-Source: AGHT+IHBROJL7S1fpmPt1/omHkDEOzsXhvYV+PIcMqm4S/6Erx+1Y40C5InhT8r/xWTQ5N6cCESm3g== X-Received: by 2002:a17:90b:3015:b0:2e2:e31a:220e with SMTP id 98e67ed59e1d1-2e77f45cbe1mr5759842a91.8.1729867147322; Fri, 25 Oct 2024 07:39:07 -0700 (PDT) Received: from free.home ([2804:14c:4d1:44a5::1002]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e7867fe396sm2824151a91.51.2024.10.25.07.39.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 07:39:07 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 49PBteY01633904 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 25 Oct 2024 08:55:40 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #5/7] extend ifcombine_replace_cond to handle noncontiguous ifcombine (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Fri, 25 Oct 2024 08:55:40 -0300 In-Reply-To: (Alexandre Oliva's message of "Fri, 25 Oct 2024 08:07:13 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, WEIRD_QUOTING 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Prepare to handle noncontiguous ifcombine, introducing logic to modify the outer condition when needed. There are two cases worth mentioning: - when blocks are noncontiguous, we have to place the combined condition in the outer block to avoid pessimizing carefully crafted short-circuited tests; - even when blocks are contiguous, we prepare for situations in which the combined condition has two tests, one to be placed in outer and the other in inner. This circumstance will not come up when noncontiguous ifcombine is first enabled, but it will when an improved fold_truth_andor is integrated with ifcombine. Combining the condition from inner into outer may require moving SSA DEFs used in the inner condition, and the changes implement this as well. for gcc/ChangeLog * tree-ssa-ifcombine.cc: Include bitmap.h. (ifcombine_mark_ssa_name): New. (struct ifcombine_mark_ssa_name_t): New. (ifcombine_mark_ssa_name_walk): New. (ifcombine_replace_cond): Prepare to handle noncontiguous and split-condition ifcombine. --- gcc/tree-ssa-ifcombine.cc | 173 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 168 insertions(+), 5 deletions(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index b5b72be29bbf9..71c7c9074e94a 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa.h" #include "attribs.h" #include "asan.h" +#include "bitmap.h" #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT #define LOGICAL_OP_NON_SHORT_CIRCUIT \ @@ -460,17 +461,57 @@ update_profile_after_ifcombine (basic_block inner_cond_bb, } } -/* Replace the conditions in INNER_COND with COND. - Replace OUTER_COND with a constant. */ +/* Set NAME's bit in USED if OUTER dominates it. */ + +static void +ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer) +{ + if (SSA_NAME_IS_DEFAULT_DEF (name)) + return; + + gimple *def = SSA_NAME_DEF_STMT (name); + basic_block bb = gimple_bb (def); + if (!dominated_by_p (CDI_DOMINATORS, bb, outer)) + return; + + bitmap_set_bit (used, SSA_NAME_VERSION (name)); +} + +/* Data structure passed to ifcombine_mark_ssa_name. */ +struct ifcombine_mark_ssa_name_t +{ + /* SSA_NAMEs that have been referenced. */ + bitmap used; + /* Dominating block of DEFs that might need moving. */ + basic_block outer; +}; + +/* Mark in DATA->used any SSA_NAMEs used in *t. */ + +static tree +ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_) +{ + ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_; + + if (*t && TREE_CODE (*t) == SSA_NAME) + ifcombine_mark_ssa_name (data->used, *t, data->outer); + + return NULL; +} + +/* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2. + COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND + replaced with a constant, but if there are intervening blocks, it's best to + adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND. */ static bool ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, gcond *outer_cond, bool outer_inv, tree cond, bool must_canon, tree cond2) { - bool result_inv = inner_inv; - - gcc_checking_assert (!cond2); + bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond)) + != gimple_bb (outer_cond)); + bool result_inv = outer_p ? outer_inv : inner_inv; if (result_inv) cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond); @@ -480,6 +521,128 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, else if (must_canon) return false; + if (outer_p) + { + { + auto_bitmap used; + basic_block outer_bb = gimple_bb (outer_cond); + + /* Mark SSA DEFs that are referenced by cond and may thus need to be + moved to outer. */ + { + ifcombine_mark_ssa_name_t data = { used, outer_bb }; + walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL); + } + + if (!bitmap_empty_p (used)) + { + /* Iterate up from inner_cond, moving DEFs identified as used by + cond, and marking USEs in the DEFs for moving as well. */ + gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond); + for (basic_block bb = gimple_bb (inner_cond); + bb != outer_bb; bb = single_pred (bb)) + { + for (gimple_stmt_iterator gsitr = gsi_last_bb (bb); + !gsi_end_p (gsitr); gsi_prev (&gsitr)) + { + gimple *stmt = gsi_stmt (gsitr); + bool move = false; + tree t; + ssa_op_iter it; + + FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF) + if (bitmap_bit_p (used, SSA_NAME_VERSION (t))) + { + move = true; + break; + } + + if (!move) + continue; + + /* Mark uses in STMT before moving it. */ + FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE) + ifcombine_mark_ssa_name (used, t, outer_bb); + + gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT); + } + + /* Surprisingly, there may be PHI nodes in single-predecessor + bocks, as in pr50682.C. Fortunately, since they can't + involve back edges, there won't be references to parallel + nodes that we'd have to pay special attention to to keep + them parallel. We can't move the PHI nodes, but we can turn + them into assignments. */ + for (gphi_iterator gsi = gsi_start_phis (bb); + !gsi_end_p (gsi);) + { + gphi *phi = gsi.phi (); + + gcc_assert (gimple_phi_num_args (phi) == 1); + tree def = gimple_phi_result (phi); + + if (!bitmap_bit_p (used, SSA_NAME_VERSION (def))) + { + gsi_next (&gsi); + continue; + } + + /* Mark uses in STMT before moving it. */ + use_operand_p use_p; + ssa_op_iter it; + FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE) + ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p), + outer_bb); + + tree use = gimple_phi_arg_def (phi, 0); + location_t loc = gimple_phi_arg_location (phi, 0); + + remove_phi_node (&gsi, false); + + gassign *a = gimple_build_assign (def, use); + gimple_set_location (a, loc); + gsi_insert_before (&gsins, a, GSI_NEW_STMT); + } + } + } + } + + if (!is_gimple_condexpr_for_cond (cond)) + { + gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond); + cond = force_gimple_operand_gsi_1 (&gsi, cond, + is_gimple_condexpr_for_cond, + NULL, true, GSI_SAME_STMT); + } + + /* Leave CFG optimization to cfg_cleanup. */ + gimple_cond_set_condition_from_tree (outer_cond, cond); + update_stmt (outer_cond); + + if (cond2) + { + if (inner_inv) + cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2); + + if (tree tcanon = canonicalize_cond_expr_cond (cond2)) + cond2 = tcanon; + if (!is_gimple_condexpr_for_cond (cond2)) + { + gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond); + cond2 = force_gimple_operand_gsi_1 (&gsi, cond2, + is_gimple_condexpr_for_cond, + NULL, true, GSI_SAME_STMT); + } + gimple_cond_set_condition_from_tree (inner_cond, cond2); + } + else + gimple_cond_set_condition_from_tree (inner_cond, + inner_inv + ? boolean_false_node + : boolean_true_node); + update_stmt (inner_cond); + } + else { if (!is_gimple_condexpr_for_cond (cond)) { From patchwork Fri Oct 25 11:56:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2002324 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=ea1haREK; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZlpL0SBqz1xwy for ; Sat, 26 Oct 2024 01:41:14 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0A0143858283 for ; Fri, 25 Oct 2024 14:41:12 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pj1-x102a.google.com (mail-pj1-x102a.google.com [IPv6:2607:f8b0:4864:20::102a]) by sourceware.org (Postfix) with ESMTPS id 324243858C48 for ; Fri, 25 Oct 2024 14:39:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 324243858C48 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 324243858C48 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::102a ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867164; cv=none; b=O7K1IK8FF/GrFCVSaIaFobHxXfbxESDYODNmFZu5mGK8sAukuVKMC07QiP7zzdtAeVZIyFV0BYPBaGx5XfBKrbgxAT95F5JFtlH3RS5NCRtWEvHSgCSqjz9xM3CzxKS9uyX1gyo5deCYfBEtekX5u3EIlX5Z0r4vrduApPZ2f7Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729867164; c=relaxed/simple; bh=XYvpgb4aZT5ORZWBSQaBL5r93YaVZlfbbKEiCfdjvW8=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=kzJmdIrurXh6rEvofJFYJsvHSICS9y+5Izotpc1y/tK0qfKMCEuTuEOnCTnUVT/tP41oJgSDMXvB7CVpdo3XB6iAGP7nHIkpgPms9f4V2xYU1D1yTspnTFO+dqKlTkkvILQHfmU92Pef+1s+BCeCGJvgh2KCc1X3OFXRp31qOTw= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pj1-x102a.google.com with SMTP id 98e67ed59e1d1-2e2e2d09decso2223939a91.1 for ; Fri, 25 Oct 2024 07:39:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1729867149; x=1730471949; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=lTOA6R85snVCaMQbGLiTTMSec1rlvHtiArkOVxNmLio=; b=ea1haREKf1pA1VVGjFG98NSR9+yxz3zM0o1O/dvP6sjAiuiN8nB04EOKcAvwc8g0dU wvZflkX4F5jkRXllwFmp/Lp+TvGyuNZmc3ly7w4Tk6RD1KL5zqTf9P+TO0KKF0IC0l46 XQLxYaxuQi8PzBgpzWYlxsInAB4dZH0d6iypELshWqQYhe6cqCep+sDzY05XoEd7d2X2 GNztrdLohBQewJBYWDey/fnWIz0WfYcqeZr9RJLc0GlT2Hg2oOYB+gewG/j7Fw0PAr0v aaohNlkzjolCfLy6mGWM/LzQ4XWzePodG7c0/iEZmi+hvKS7TH28SCZH3Ac2h6TCNg7W Zkcg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729867149; x=1730471949; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=lTOA6R85snVCaMQbGLiTTMSec1rlvHtiArkOVxNmLio=; b=ToBC+FpC7gci+etc+56VJrlRRo7nAkg6WuCymIHDO20W7HtR/AAt7Yj9QaX1wwlGB/ diEkFh/QFVawgRT0bDRO4AlmLC6zBNJ308r3xS3vAa5ZENHnGO7qcGRjH3gFZQ5z7njD wYZd0aepulAVyYnq5uB11sd7033hQPsHujvsndwxVxRsp/kSgCWcPhN1Jv1VldsEHiyK E2yOI4TLMYptuwSkbns+ZyuhvxlCJYdSf1tPC7tBIr9TL8LpcKxQiYaF0OYJA5E362qr viLVzOnsAtndMTViDqD1J+EZp/d7uSXLA9Wucmge/PcUkDO+mWFltgTuM+U6gpezLS/s IbAA== X-Gm-Message-State: AOJu0YwB1LVIe/JEvNBA8MeIkFb3CyqMsmTOegVRxswVIrnyQM8PI+mp qyRfWw7yfm/fEAu8ZKKBNYC7s17LZm90KTFPqIZauoH21KFB+dy538rGi7PZHSRqfiCOJMok9Ct u5Q== X-Google-Smtp-Source: AGHT+IGxNj0fZXYE7rFblEa5rqSeQglPZQFiYCNdUvIX6yjGoNL0LbiPv7yuhTzq+pza1z7RIMgtZw== X-Received: by 2002:a17:90b:111:b0:2da:6e46:ad48 with SMTP id 98e67ed59e1d1-2e77e5a7038mr9123090a91.1.1729867148955; Fri, 25 Oct 2024 07:39:08 -0700 (PDT) Received: from free.home ([2804:14c:4d1:44a5::1002]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e7867fe396sm2824151a91.51.2024.10.25.07.39.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 07:39:08 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 49PBuS6V1633946 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 25 Oct 2024 08:56:28 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #6/7] ifcombine across noncontiguous blocks (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Fri, 25 Oct 2024 08:56:28 -0300 In-Reply-To: (Alexandre Oliva's message of "Fri, 25 Oct 2024 08:07:13 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, WEIRD_QUOTING 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Rework ifcombine to support merging conditions from noncontiguous blocks. This depends on earlier preparation changes. The function that attempted to ifcombine a block with its immediate predecessor, tree_ssa_ifcombine_bb, now loops over dominating blocks eligible for ifcombine, attempting to combine with them. The function that actually drives the combination of a pair of blocks, tree_ssa_ifcombine_bb_1, now takes an additional parameter: the successor of outer that leads to inner. The function that recognizes if_then_else patterns is modified to enable testing without distinguishing between then and else, or to require nondegenerate conditions, that aren't worth combining with. for gcc/ChangeLog * tree-ssa-ifcombine.cc (recognize_if_then_else): Support relaxed then/else testing; require nondegenerate condition otherwise. (tree_ssa_ifcombine_bb_1): Add outer_succ_bb parm, use it instead of inner_cond_bb. Adjust callers. (tree_ssa_ifcombine_bb): Loop over dominating outer blocks eligible for ifcombine. (pass_tree_ifcombine::execute): Noted potential need for changes to the post-combine logic. --- gcc/tree-ssa-ifcombine.cc | 152 ++++++++++++++++++++++++++++++++++++--------- 1 file changed, 123 insertions(+), 29 deletions(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index 71c7c9074e94a..817c95b20252e 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -85,25 +85,34 @@ known_succ_p (basic_block cond_bb) is left to CFG cleanup and DCE. */ -/* Recognize a if-then-else CFG pattern starting to match with the - COND_BB basic-block containing the COND_EXPR. The recognized - then end else blocks are stored to *THEN_BB and *ELSE_BB. If - *THEN_BB and/or *ELSE_BB are already set, they are required to - match the then and else basic-blocks to make the pattern match. - Returns true if the pattern matched, false otherwise. */ +/* Recognize a if-then-else CFG pattern starting to match with the COND_BB + basic-block containing the COND_EXPR. If !SUCCS_ANY, the condition must not + resolve to a constant for a match. Returns true if the pattern matched, + false otherwise. In case of a !SUCCS_ANY match, the recognized then end + else blocks are stored to *THEN_BB and *ELSE_BB. If *THEN_BB and/or + *ELSE_BB are already set, they are required to match the then and else + basic-blocks to make the pattern match. If SUCCS_ANY, *THEN_BB and *ELSE_BB + will not be filled in, and they will be found to match even if reversed. */ static bool recognize_if_then_else (basic_block cond_bb, - basic_block *then_bb, basic_block *else_bb) + basic_block *then_bb, basic_block *else_bb, + bool succs_any = false) { edge t, e; - if (EDGE_COUNT (cond_bb->succs) != 2) + if (EDGE_COUNT (cond_bb->succs) != 2 + || (!succs_any && known_succ_p (cond_bb))) return false; /* Find the then/else edges. */ t = EDGE_SUCC (cond_bb, 0); e = EDGE_SUCC (cond_bb, 1); + + if (succs_any) + return ((t->dest == *then_bb && e->dest == *else_bb) + || (t->dest == *else_bb && e->dest == *then_bb)); + if (!(t->flags & EDGE_TRUE_VALUE)) std::swap (t, e); if (!(t->flags & EDGE_TRUE_VALUE) @@ -886,19 +895,21 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and dispatch to the appropriate if-conversion helper for a particular set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB. - PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */ + PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. + OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards + INNER_COND_BB. */ static bool tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, basic_block then_bb, basic_block else_bb, - basic_block phi_pred_bb) + basic_block phi_pred_bb, basic_block outer_succ_bb) { /* The && form is characterized by a common else_bb with the two edges leading to it mergable. The latter is guaranteed by matching PHI arguments in the else_bb and the inner cond_bb having no side-effects. */ if (phi_pred_bb != else_bb - && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) + && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb) && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb)) { /* We have @@ -915,7 +926,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, /* And a version where the outer condition is negated. */ if (phi_pred_bb != else_bb - && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb) + && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb) && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb)) { /* We have @@ -935,7 +946,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, by matching PHI arguments in the then_bb and the inner cond_bb having no side-effects. */ if (phi_pred_bb != then_bb - && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) + && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb) && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb)) { /* We have @@ -951,7 +962,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, /* And a version where the outer condition is negated. */ if (phi_pred_bb != then_bb - && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb) + && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb) && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb)) { /* We have @@ -975,10 +986,11 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, static bool tree_ssa_ifcombine_bb (basic_block inner_cond_bb) { + bool ret = false; basic_block then_bb = NULL, else_bb = NULL; if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb)) - return false; + return ret; /* Recognize && and || of two conditions with a common then/else block which entry edges we can merge. That is: @@ -987,17 +999,62 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb) and if (a && b) ; - This requires a single predecessor of the inner cond_bb. */ - if (single_pred_p (inner_cond_bb) - && bb_no_side_effects_p (inner_cond_bb)) + This requires a single predecessor of the inner cond_bb. + + Look for an OUTER_COND_BBs to combine with INNER_COND_BB. They need not + be contiguous, as long as inner and intervening blocks have no side + effects, and are either single-entry-single-exit or conditionals choosing + between the same EXIT_BB with the same PHI args, and the path leading to + INNER_COND_BB. ??? We could potentially handle multi-block + single-entry-single-exit regions, but the loop below only deals with + single-entry-single-exit individual intervening blocks. Larger regions + without side effects are presumably rare, so it's probably not worth the + effort. */ + for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL; + single_pred_p (bb) && bb_no_side_effects_p (bb); + bb = outer_cond_bb) { - basic_block outer_cond_bb = single_pred (inner_cond_bb); + bool changed = false; - if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, - then_bb, else_bb, inner_cond_bb)) - return true; + outer_cond_bb = single_pred (bb); - if (forwarder_block_to (else_bb, then_bb)) + /* Skip blocks without conditions. */ + if (single_succ_p (outer_cond_bb)) + continue; + + /* When considering noncontiguous conditions, make sure that all + non-final conditions lead to the same successor of the final + condition, when not taking the path to inner_bb, so that we can + combine C into A, both in A && (B && C), and in A || (B || C), but + neither in A && (B || C), nor A || (B && C). Say, if C goes to + THEN_BB or ELSE_BB, then B must go to either of these, say X, besides + C (whether C is then or else), and A must go to X and B (whether then + or else). + + We test for this, while allowing intervening nonconditional blocks, by + first taking note of which of the successors of the inner conditional + block is the exit path taken by the first considered outer conditional + block. + + Having identified and saved the exit block in EXIT_BB at the end of + the loop, here we test that subsequent conditional blocks under + consideration also use the exit block as a successor, besides the + block that leads to inner_cond_bb, and that the edges to exit share + the same phi values. */ + if (exit_bb + && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true)) + break; + + /* After checking dests and phi args, we can also skip blocks whose + conditions have been optimized down to a constant, without trying to + combine them, but we must not skip the computation of EXIT_BB and the + checking of same phi args. */ + if (known_succ_p (outer_cond_bb)) + changed = false; + else if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, + then_bb, else_bb, inner_cond_bb, bb)) + changed = true; + else if (forwarder_block_to (else_bb, then_bb)) { /* Other possibilities for the && form, if else_bb is empty forwarder block to then_bb. Compared to the above simpler @@ -1006,8 +1063,8 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb) For same_phi_args_p we look at equality of arguments between edge from outer_cond_bb and the forwarder block. */ if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb, - then_bb, else_bb)) - return true; + then_bb, else_bb, bb)) + changed = true; } else if (forwarder_block_to (then_bb, else_bb)) { @@ -1018,12 +1075,46 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb) For same_phi_args_p we look at equality of arguments between edge from outer_cond_bb and the forwarder block. */ if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb, - then_bb, then_bb)) - return true; + then_bb, then_bb, bb)) + changed = true; } + + if (changed) + ret = changed; + + /* If the inner condition is gone, there's no point in attempting to + combine it any further. */ + if (changed && known_succ_p (inner_cond_bb)) + break; + + /* Record the exit path taken by the outer condition. */ + if (!exit_bb) + { + if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true)) + exit_bb = then_bb; + else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true)) + exit_bb = else_bb; + else + break; + } + + /* Before trying an earlier block, make sure INNER_COND_BB and the + current OUTER_COND_BB share the same PHI args at EXIT_BB. We don't + need to check if the latest attempt at combining succeeded, because + that means we'll have already checked. But we can't only check outer + and inner, we have to check that all intervening blocks also get to + exit with the same result, otherwise the transformation may change the + final result. Consider (a ? 0 : b ? 1 : c ? 0 : -1). If we combine + (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0 + rather than 1 when (!a&&b). And if we were to replace inner instead + of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would + yield 1 rather than 0 when (a). */ + if (!changed + && !same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb)) + break; } - return false; + return ret; } /* Main entry for the tree if-conversion pass. */ @@ -1082,7 +1173,10 @@ pass_tree_ifcombine::execute (function *fun) if (tree_ssa_ifcombine_bb (bb)) { /* Clear range info from all stmts in BB which is now executed - conditional on a always true/false condition. */ + conditional on a always true/false condition. ??? When we + combine noncontiguous blocks, do we need to adjust the + intervening blocks as well? If we leave outer conditions + nonconstant, do we still need to modify them? */ reset_flow_sensitive_info_in_bb (bb); for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) From patchwork Fri Oct 25 11:57:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2002364 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=Z6phsCd6; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZn5X5b0Mz1xwF for ; Sat, 26 Oct 2024 02:39:28 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B8E883858CDA for ; Fri, 25 Oct 2024 15:39:26 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pg1-x534.google.com (mail-pg1-x534.google.com [IPv6:2607:f8b0:4864:20::534]) by sourceware.org (Postfix) with ESMTPS id 66CE53858D21 for ; Fri, 25 Oct 2024 15:39:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 66CE53858D21 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 66CE53858D21 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::534 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729870743; cv=none; b=B0PohRO9B5Atl5SwxrApljUbCrpPQFGXWKIB8gDjRub2Li96fiGURW4ahLgwNhdJm2gVwo8DuxdOiCsbr2miv/WV6YHjBblk5a21zS+u9V0CpoVTFYv4wmcOxilzGi+hRJRcuvkj/EmcgmdhgnPCHHtbBqLWvNLqJQQBteZqR1o= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729870743; c=relaxed/simple; bh=qUGRzNZP6PJQSyuPxDCG1eDStJ5YrWEHd3+56E1031s=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=wRqLe5cVUglf6MOkO64gZwb96EsivKf3w+4pwvVgbqMDpz+WrMVuSnjwMNQoMBz6dZlXmjGSl5NrxqM8EZ1ZdjUppQ257R5h8XzhGfKL2p1NF5WoeiD7BbcoTtpG4JO1ZeAI7YoK/c6ZhzBiQQ6TpU8ZCy8mLZqVs5FWzEzC4ik= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pg1-x534.google.com with SMTP id 41be03b00d2f7-7163489149eso1537078a12.1 for ; Fri, 25 Oct 2024 08:39:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1729870740; x=1730475540; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=WmL4r6m4J2PqDWjIc4xH14m1hN+EzrsHOF9g4h8H1OQ=; b=Z6phsCd6duSetpWJUuCrDfIq+wcltkVspFUzKyaspTiRQ5UuajWDNRLWHhB6vfS+1W A/Gry3wKHMPFaq5kVghdiXitjUUlJnb56/O2fjXm34hi0CQkuyxHIEN2TcyvPAWDoPgx vShNpjIvt9MEMPbffGPgjKX62KW1XA0gM/BCk0eIFlzuXwZxGX4UniDnEDYmQgvF+yFi gwPpbTHWzqOoOpRtcHYHeDIv0ORkDbCknsYmnuxAYDYSbJdmXsOMtPS/unBUY444olLC phlrW3CM5BjJ1CvcppNLNlwob3HGN1xSwSfvXg5R55P0bERAD51ejuMpsOfk1DXDN87d j2XA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729870740; x=1730475540; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=WmL4r6m4J2PqDWjIc4xH14m1hN+EzrsHOF9g4h8H1OQ=; b=C+YAhbJi3OAAXqN/lU2Cr4vMnncrWW422n+xNL3YLNvM/xg/qxgKa3vpYw4mW9WGCw Lawy17VruToHB9aJUuIQhvRlNfJTCYZEmcvR/CB4ecXWoXwvq5fO9OGXjKomnBXeIqUa JWwSe6rPTtOBBfoeHGz1jaCUd5SQRipYfmJd5tSDhw8aW6AfWcurc06Pec0GZ0emElP2 FXG4OsQvO9csuYm2VyktGilFGX366+ZAu1q5qpBIaAhRibRee5+jZGtjfm7DgDVbLclH pEZs0rKyMCrweLzbtJbSpLUXrVtnfwoT5olK9hu5Wex4a3KVRIrDpt8V7W5Fealk8acg IgfA== X-Gm-Message-State: AOJu0YxiQ3IQ9dGZUd+0Mv82+I5fCsx/7igTrAp8ezYcIfPz7dm59du4 q4VsuqtOBIcTIEgCJ/HoMH/HjjAvvLXj7daQ3lJ0fMFGAZdUyr+uEzpvQThbzKTNWnNc6QebT41 pcw== X-Google-Smtp-Source: AGHT+IHYi4DE/zxzMhXxa0Ic93ScvmZZQnXs3+wM0IRvULCBf3pzMnYss90W/Sxuh/GXL/l3q4agAg== X-Received: by 2002:a05:6a21:3a4a:b0:1d9:77d1:5a8 with SMTP id adf61e73a8af0-1d978ad716cmr11938849637.4.1729870740136; Fri, 25 Oct 2024 08:39:00 -0700 (PDT) Received: from free.home ([2804:14c:4d1:44a5::1002]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72057921863sm1200276b3a.33.2024.10.25.08.38.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 08:38:59 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 49PBvLsT1633957 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 25 Oct 2024 08:57:21 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #7/7] handle TRUTH_ANDIF cond exprs in ifcombine_replace_cond (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Fri, 25 Oct 2024 08:57:21 -0300 In-Reply-To: (Alexandre Oliva's message of "Fri, 25 Oct 2024 08:07:13 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-10.0 required=5.0 tests=BAYES_00, DATE_IN_PAST_03_06, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, LIKELY_SPAM_BODY, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, WEIRD_QUOTING 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~incoming=patchwork.ozlabs.org@gcc.gnu.org The upcoming move of fold_truth_andor to ifcombine brings with it the possibility of TRUTH_ANDIF cond exprs. Handle them by splitting the cond so as to best use both BB insertion points, but only if they're contiguous. for gcc/ChangeLog * tree-ssa-ifcombine.c (ifcombine_replace_cond): Support TRUTH_ANDIF cond exprs. --- gcc/tree-ssa-ifcombine.cc | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index 817c95b20252e..6194e92bd3816 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -518,6 +518,17 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, gcond *outer_cond, bool outer_inv, tree cond, bool must_canon, tree cond2) { + /* Split cond into cond2 if they're contiguous. ??? We might be able to + handle ORIF as well, inverting both conditions, but it's not clear that + this would be enough, and it never comes up. */ + if (!cond2 + && TREE_CODE (cond) == TRUTH_ANDIF_EXPR + && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond)) + { + cond2 = TREE_OPERAND (cond, 1); + cond = TREE_OPERAND (cond, 0); + } + bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond)) != gimple_bb (outer_cond)); bool result_inv = outer_p ? outer_inv : inner_inv;