From patchwork Sat Nov 2 11:19:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 2005420 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=QRmeINvy; 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 4XgZz755Fsz1xwF for ; Sat, 2 Nov 2024 22:20:32 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 36A503857C68 for ; Sat, 2 Nov 2024 11:20:30 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pf1-x42f.google.com (mail-pf1-x42f.google.com [IPv6:2607:f8b0:4864:20::42f]) by sourceware.org (Postfix) with ESMTPS id 6571B3858D33 for ; Sat, 2 Nov 2024 11:20:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6571B3858D33 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 6571B3858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::42f ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730546412; cv=none; b=AH7sp64D7kHOwbjzk2XKEgpMaW+RILPNU1Dz4nYXbZbziPlTE0sQX570JY8NxCX2SgTl8CfhFqzUutxXXS20EKmZBJEFjzd0p5A7VBoW4KuFKwMACHn2ajBCTE+BBakg9u/zW5RcTgMSMzuFnJs63qxIOO8Zy/YZcwPXjIVuh7c= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730546412; c=relaxed/simple; bh=H+Nj0OZsmAq5s3/Qj3ytr14NC2sd4YZpo46DDfp4jYE=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=ivpXUx+8uRRpTk2s1ytKbHw8S6hC1ptNa9Gg8ZfTqFyakRI8kRnoRKhhY9GstK/4nsBp8/0V2/gceYJq7cHaPixHGkjJkz7wRHLzr02YhsljOGxwYF19xXccwI0dK9uVYF9Vicz9rA8pno6m+608DQk+YF89GxqRUYgZK6sag0g= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pf1-x42f.google.com with SMTP id d2e1a72fcca58-71e5130832aso2221148b3a.0 for ; Sat, 02 Nov 2024 04:20:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1730546408; x=1731151208; 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=Tps8xyxRg1Bw1Fqo/CogUBpp7JnPjfJZDXvPhiUzXTE=; b=QRmeINvyBHqxbbXOGVn5I/21aIf2edge8loSOCqHPXkC8/u0QCxTr4ey4/8+PQZgm8 g2BYvQQTipFzQJUPoTL9Rg4alQ3IIICGfg1d+DYGTdsntZpXoPzL6U8ve99EYV40Vyj+ dmjeYMwIXs2NnIC59A6wCKYdCjojjx1CD8g9KvL49GTsnfrfnADgWYsanl/XmYsrFcND aRcvNpv6AsNOOAfUMjD/XfHPPBgZDFzDtDJeYoO1MopAxfkDxzIMX42ydCcwSKyhxiVX DEo6D8EQMqHEoE424EM++9vaADJkYGVHirzDbc1inFip+ej9c5XTM/yPCaEuraKShwcj R9tg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730546408; x=1731151208; 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=Tps8xyxRg1Bw1Fqo/CogUBpp7JnPjfJZDXvPhiUzXTE=; b=iBZrJ0hNsqjQ4iQ4mLaA0fVp2GiUqpOxSHF1tY8ZWfVoKQyyAjhoU4SR7Wi/RvqedX 4Q1sEqBUDpuPz/Qt6czVPY/vCvoFNdcPwDqKR676SxIPta8tssPviYxY6yK2idetKJRv QH+vhcNeQ5eeQZMsgE7x3/Gv07hpGGSjvxPrczKfa/PmOalRRvqa6ol84IDqi+423UDe ICl0G4HfIUmftp0+NZ7NZ8ZEFDRe6Nmr4VhrU1PNbyLbxec/s4iT2XoSTf4sh+yeiDVW hE6mVqdMjyADzd3zdNvdHdp0weNSYnGZW8c92bsU5bLGOLuYLIuA/rVIocVHOocp2EU2 BJ2Q== X-Gm-Message-State: AOJu0YynU9/k0G2O5VdjLjmS76fEFHNhAVF6rgFcL6RDBK4F2qmz+m8X 9OGQtsG8AppH/PBBUQhrlofSTLhU6gPs1Xz1bs35nb7Kh9aRO0kob8W1ElmvGm+2MNpaylsfz27 ebw== X-Google-Smtp-Source: AGHT+IEOS9E3muOlFO/nj7Hek4jocpeVwX++mr+Y5n0o7MCG0Q0W2mSuiLOocNOlQ1V/v74k6fO8uw== X-Received: by 2002:a05:6a21:478b:b0:1d9:278a:9ab with SMTP id adf61e73a8af0-1dba54a619dmr10797785637.35.1730546408261; Sat, 02 Nov 2024 04:20:08 -0700 (PDT) Received: from free.home ([2804:7f1:218a:e46a:9e48:eab6:3a44:4bc0]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7ee5f92f24csm2283726a12.36.2024.11.02.04.20.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 02 Nov 2024 04:20:07 -0700 (PDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 4A2BJuSG1947533 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Sat, 2 Nov 2024 08:19:57 -0300 From: Alexandre Oliva To: Richard Biener Cc: GCC Patches Subject: [PATCH #8/7++] limit ifcombine stmt moving and adjust flow info (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine) Organization: Free thinker, does not speak for AdaCore References: Date: Sat, 02 Nov 2024 08:19:56 -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-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 It became apparent that conditions could be combined that had deep SSA dependency trees, that might thus require moving lots of statements. Set a hard upper bound for now, hopefully to be replaced by a dynamically computed bound, based on probabilities and costs. Also reset flow sensitive info and avoid introducing undefined behavior when moving stmts from under guarding conditions. Finally, rework the preexisting reset of flow sensitive info and avoidance of undefined behavior to be done when needed on all affected inner blocks: reset flow info whenever enclosing conditions change, and avoid undefined behavior whenever enclosing conditions become laxer. Regstrapped on x86_64-linux-gnu. Ok to install? for gcc/ChangeLog * tree-ssa-ifcombine.cc (ifcombine_rewrite_to_defined_overflow): New. (ifcombine_replace_cond): Reject conds that would require moving too many stmts. Reset flow sensitive info and avoid undefined behavior in moved stmts. Reset flow sensitive info in all inner blocks when the outer condition changes, and avoid undefined behavior whenever the outer condition becomes laxer, adapted and moved from... (pass_tree_ifcombine::execute): ... here. --- gcc/tree-ssa-ifcombine.cc | 114 +++++++++++++++++++++++++++++++++++---------- 1 file changed, 89 insertions(+), 25 deletions(-) diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc index ac4811e42e082..ae1b039335a85 100644 --- a/gcc/tree-ssa-ifcombine.cc +++ b/gcc/tree-ssa-ifcombine.cc @@ -508,6 +508,25 @@ ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_) return NULL; } +/* Rewrite a stmt, that presumably used to be guarded by conditions that could + avoid undefined overflow, into one that has well-defined overflow, so that + it won't invoke undefined behavior once the guarding conditions change. */ + +static inline void +ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi) +{ + gassign *ass = dyn_cast (gsi_stmt (gsi)); + if (!ass) + return; + tree lhs = gimple_assign_lhs (ass); + if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + || POINTER_TYPE_P (TREE_TYPE (lhs))) + && arith_code_with_undefined_signed_overflow + (gimple_assign_rhs_code (ass))) + rewrite_to_defined_overflow (&gsi); +} + + /* 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 @@ -518,6 +537,7 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, gcond *outer_cond, bool outer_inv, tree cond, bool must_canon, tree cond2) { + bool split_single_cond = false; /* 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. */ @@ -527,11 +547,13 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, { cond2 = TREE_OPERAND (cond, 1); cond = TREE_OPERAND (cond, 0); + split_single_cond = true; } bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond)) != gimple_bb (outer_cond)); bool result_inv = outer_p ? outer_inv : inner_inv; + bool strictening_outer_cond = !split_single_cond && outer_p; if (result_inv) cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond); @@ -558,9 +580,11 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, if (!bitmap_empty_p (used)) { + const int max_stmts = 6; + auto_vec stmts; + /* 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)) { @@ -582,11 +606,14 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, if (!move) continue; + if (stmts.length () < max_stmts) + stmts.quick_push (stmt); + else + return false; + /* 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 @@ -609,22 +636,59 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, continue; } + if (stmts.length () < max_stmts) + stmts.quick_push (phi); + else + return false; + /* 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); + } + } + /* ??? Test whether it makes sense to move STMTS. */ + + /* Move the STMTS that need moving. From this point on, we're + committing to the attempted ifcombine. */ + gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond); + unsigned i; + gimple *stmt; + FOR_EACH_VEC_ELT (stmts, i, stmt) + { + if (gphi *phi = dyn_cast (stmt)) + { + tree def = gimple_phi_result (phi); tree use = gimple_phi_arg_def (phi, 0); location_t loc = gimple_phi_arg_location (phi, 0); + gphi_iterator gsi = gsi_for_phi (phi); 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); } + else + { + gimple_stmt_iterator gsitr = gsi_for_stmt (stmt); + gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT); + } + } + + for (; gsi_stmt (gsins) != outer_cond; gsi_next (&gsins)) + { + /* Clear range info from all defs we've moved from under + conditions. */ + tree t; + ssa_op_iter it; + FOR_EACH_SSA_TREE_OPERAND (t, gsi_stmt (gsins), it, SSA_OP_DEF) + reset_flow_sensitive_info (t); + /* Avoid introducing undefined overflows while at that. */ + ifcombine_rewrite_to_defined_overflow (gsins); } } } @@ -684,6 +748,27 @@ ifcombine_replace_cond (gcond *inner_cond, bool inner_inv, update_stmt (outer_cond); } + /* We're changing conditions that guard inner blocks, so reset flow sensitive + info and avoid introducing undefined behavior. */ + for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond); + bb != end; bb = single_pred (bb)) + { + /* Clear range info from all stmts in BB which is now guarded by + different conditionals. */ + reset_flow_sensitive_info_in_bb (gimple_bb (inner_cond)); + + /* We only need to worry about introducing undefined behavior if we've + relaxed the outer condition. */ + if (strictening_outer_cond) + continue; + + /* Avoid introducing undefined behavior as we move stmts that used to be + guarded by OUTER_COND. */ + for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond)); + !gsi_end_p (gsi); gsi_next (&gsi)) + ifcombine_rewrite_to_defined_overflow (gsi); + } + update_profile_after_ifcombine (gimple_bb (inner_cond), gimple_bb (outer_cond)); @@ -1184,28 +1269,7 @@ pass_tree_ifcombine::execute (function *fun) if (safe_is_a (*gsi_last_bb (bb))) 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. ??? 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)) - { - gassign *ass = dyn_cast (gsi_stmt (gsi)); - if (!ass) - continue; - tree lhs = gimple_assign_lhs (ass); - if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) - || POINTER_TYPE_P (TREE_TYPE (lhs))) - && arith_code_with_undefined_signed_overflow - (gimple_assign_rhs_code (ass))) - rewrite_to_defined_overflow (&gsi); - } - cfg_changed |= true; - } + cfg_changed |= true; } free (bbs);