From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id C80953858401 for ; Wed, 23 Aug 2023 15:22:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C80953858401 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1692804135; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=W+4bf4KO5UtRXVvE/z0hEUcXEul3JVAEJhJYLdJkeKU=; b=O5RKk7Q4eyM2GlOchS3m5mhgpgJkMK4ZzjIhBkJUW+LslNT8ryYf/cpy25HKMfB0h4Lhr1 PSPCQzxyTy1A1lFzUdv62+XT08mxTMijxpKEnP6Zf3xVNb4rqzK5k8yrbsuTek3qk6X7gN BauHefDjfpwVhk8Od53/e121kN02VqQ= Received: from mimecast-mx02.redhat.com (66.187.233.73 [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-64-CQqUm3AcM3C5udvmhSH0Gw-1; Wed, 23 Aug 2023 11:22:13 -0400 X-MC-Unique: CQqUm3AcM3C5udvmhSH0Gw-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.rdu2.redhat.com [10.11.54.1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id A2D8A3811F36 for ; Wed, 23 Aug 2023 15:22:13 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.246]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 3B8CF40C206F; Wed, 23 Aug 2023 15:22:13 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.17.1) with ESMTPS id 37NFMBDg351620 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 23 Aug 2023 17:22:11 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 37NFMB31351619; Wed, 23 Aug 2023 17:22:11 +0200 From: Aldy Hernandez To: GCC patches Cc: Andrew MacLeod , Aldy Hernandez Subject: [PATCH] [frange] Relax floating point relational folding. Date: Wed, 23 Aug 2023 17:22:00 +0200 Message-ID: <20230823152209.351604-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.1 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: [Jakub/Andrew: I've been staring at this for far too long and could use another pair of eyes.] This patch implements a new frelop_early_resolve() that handles the NAN special cases instead of calling into the integer version which can break for some combinations. Relaxing FP conditional folding in this matter allows ranger to do a better job resulting in more threading opportunities, among other things. In auditing ranger versus DOM scoped tables I've noticed we are too cautious when folding floating point conditionals involving relationals. We refuse to fold anything if there is the possibility of a NAN, but this is overly restrictive. For example: if (x_5 != y_8) if (x_5 != y_8) link_error (); In range-ops, we fail to fold the second conditional because frelop_early_resolve bails on anything that may have a NAN, but in the above case the possibility of a NAN is inconsequential. However, there are some cases where we must be careful, because a NAN can complicate matters: if (x_5 == x_5) ... Here the operands to EQ_EXPR are the same so we get VREL_EQ as the relation. However, we can't fold the conditional unless we know x_5 cannot be a NAN. On the other hand, we can fold the second conditional here: if (x_5 == x_5) if (x_5 > x_5) Because on the TRUE side of the first conditional we are guaranteed to be free of NANs. This patch is basically an inline of the integer version of relop_early_resolve() with special casing for floats. The main thing to keep in mind is that the relation coming into a range-op entry may have a NAN, and for that one must look at the operands. This makes the relations akin to unordered comparisons, making VREL_LT behave like VREL_UNLT would. The tricky corner cases are VREL_EQ and VREL_NE, as discussed above. Apart from these that are special cased, the relation table for intersect should work fine for returning a FALSE, even with NANs. The union table, not so much and is documented in the code. This allows us to add some optimizations for the unordered operators. For example, a relation of VREL_LT on entry to an operator allows us to fold an UNLT_EXPR as true, even with NANs because in this case VREL_LT is really VREL_UNLT which maps perfectly. BTW, we batted some ideas on how to get this work, and it seems this is the cleaner route with the special cases nestled in the operators themselves. Another idea is to add unordered relations, but that would require bloating the various tables adding spots for VREL_UNEQ, VREL_UNLT, etc, plus adding relations for VREL_UNORDERED so the intersects work correctly. I'm not wed to either one, and we can certainly revisit this if it becomes burdensome to maintain (or to get right). I'll hold off until the end of the week to commit, to wait for feedback. Tested on x86-64 Linux. gcc/ChangeLog: * range-op-float.cc (frelop_early_resolve): Rewrite for better NAN handling. (operator_not_equal::fold_range): Adjust for relations. (operator_lt::fold_range): Same. (operator_gt::fold_range): Same. (foperator_unordered_equal::fold_range): Same. (foperator_unordered_lt::fold_range): Same. (foperator_unordered_le::fold_range): Same. (foperator_unordered_gt::fold_range): Same. (foperator_unordered_ge::fold_range): Same. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/vrp-float-12.c: New test. --- gcc/range-op-float.cc | 148 +++++++++++++++---- gcc/testsuite/gcc.dg/tree-ssa/vrp-float-12.c | 23 +++ 2 files changed, 143 insertions(+), 28 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-float-12.c diff --git a/gcc/range-op-float.cc b/gcc/range-op-float.cc index e30b489c410..14199647744 100644 --- a/gcc/range-op-float.cc +++ b/gcc/range-op-float.cc @@ -268,22 +268,75 @@ maybe_isnan (const frange &op1, const frange &op2) return op1.maybe_isnan () || op2.maybe_isnan (); } -// Floating version of relop_early_resolve that takes into account NAN -// and -ffinite-math-only. +// Floating point version of relop_early_resolve that takes NANs into +// account. +// +// For relation opcodes, first try to see if the supplied relation +// forces a true or false result, and return that. +// Then check for undefined operands. If none of this applies, +// return false. +// +// TRIO are the relations between operands as they appear in the IL. +// MY_REL is the relation that corresponds to the operator being +// folded. For example, when attempting to fold x_3 == y_5, MY_REL is +// VREL_EQ, and if the statement is dominated by x_3 > y_5, then +// TRIO.op1_op2() is VREL_GT. +// +// Relations in a floating point world are a bit tricky, as TRIO +// behaves as the corresponding unordered variant if either operand +// could be a NAN. For example, when resolving "if (x_5 == x_5)", the +// relation is VREL_EQ, but it behaves like VREL_UNEQ if NANs are a +// possibility. Similarly, the false edge of "if (x >= y)" has a +// relation of VREL_LT, but behaves as VREL_UNLT unless we can prove +// neither operand can be NAN. +// +// ?? It is unclear whether providing unordered VREL relations would +// simplify things, as we'd have to add more entries to various +// tables, tweak all the op1_op2_relation() entries, etc. static inline bool frelop_early_resolve (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel, relation_kind my_rel) + relation_trio trio, relation_kind my_rel) { + relation_kind rel = trio.op1_op2 (); + + if (maybe_isnan (op1, op2)) + { + // There's not much we can do for VREL_EQ if NAN is a + // possibility. It is up to the caller to deal with these + // special cases. + if (rel == VREL_EQ) + return empty_range_varying (r, type, op1, op2); + } + // If known relation is a complete subset of this relation, always + // return true. However, avoid doing this when NAN is a possibility + // as we'll incorrectly fold conditions: + // + // if (x_3 >= y_5) + // ; + // else + // ;; With NANs the relation here is basically VREL_UNLT, so we + // ;; can't fold the following: + // if (x_3 < y_5) + else if (relation_union (rel, my_rel) == my_rel) + { + r = range_true (type); + return true; + } + + // If known relation has no subset of this relation, always false. + if (relation_intersect (rel, my_rel) == VREL_UNDEFINED) + { + r = range_false (type); + return true; + } + // If either operand is undefined, return VARYING. if (empty_range_varying (r, type, op1, op2)) return true; - // We can fold relations from the oracle when we know both operands - // are free of NANs, or when -ffinite-math-only. - return (!maybe_isnan (op1, op2) - && relop_early_resolve (r, type, op1, op2, rel, my_rel)); + return false; } // Set VALUE to its next real value, or INF if the operation overflows. @@ -738,9 +791,17 @@ operator_equal::op1_op2_relation (const irange &lhs, const frange &, bool operator_not_equal::fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel) const + relation_trio trio) const { - if (frelop_early_resolve (r, type, op1, op2, rel, VREL_NE)) + relation_kind rel = trio.op1_op2 (); + + // VREL_NE & NE_EXPR is always true, even with NANs. + if (rel == VREL_NE) + { + r = range_true (type); + return true; + } + if (frelop_early_resolve (r, type, op1, op2, trio, VREL_NE)) return true; // x != NAN is always TRUE. @@ -862,9 +923,17 @@ operator_not_equal::op1_op2_relation (const irange &lhs, const frange &, bool operator_lt::fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel) const + relation_trio trio) const { - if (frelop_early_resolve (r, type, op1, op2, rel, VREL_LT)) + relation_kind rel = trio.op1_op2 (); + + // VREL_EQ & LT_EXPR is impossible, even with NANs. + if (rel == VREL_EQ) + { + r = range_false (type); + return true; + } + if (frelop_early_resolve (r, type, op1, op2, trio, VREL_LT)) return true; if (op1.known_isnan () @@ -1083,9 +1152,17 @@ operator_le::op1_op2_relation (const irange &lhs, const frange &, bool operator_gt::fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel) const + relation_trio trio) const { - if (frelop_early_resolve (r, type, op1, op2, rel, VREL_GT)) + relation_kind rel = trio.op1_op2 (); + + // VREL_EQ & GT_EXPR is impossible, even with NANs. + if (rel == VREL_EQ) + { + r = range_false (type); + return true; + } + if (frelop_early_resolve (r, type, op1, op2, trio, VREL_GT)) return true; if (op1.known_isnan () @@ -1587,9 +1664,12 @@ class foperator_unordered_lt : public range_operator public: bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel = TRIO_VARYING) const final override + relation_trio trio = TRIO_VARYING) const final override { - if (op1.known_isnan () || op2.known_isnan ()) + relation_kind rel = trio.op1_op2 (); + + if (op1.known_isnan () || op2.known_isnan () + || rel == VREL_LT) { r = range_true (type); return true; @@ -1601,7 +1681,7 @@ public: if (op2.maybe_isnan ()) op2_no_nan.clear_nan (); if (!range_op_handler (LT_EXPR).fold_range (r, type, op1_no_nan, - op2_no_nan, rel)) + op2_no_nan, trio)) return false; // The result is the same as the ordered version when the // comparison is true or when the operands cannot be NANs. @@ -1699,9 +1779,12 @@ class foperator_unordered_le : public range_operator public: bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel = TRIO_VARYING) const final override + relation_trio trio = TRIO_VARYING) const final override { - if (op1.known_isnan () || op2.known_isnan ()) + relation_kind rel = trio.op1_op2 (); + + if (op1.known_isnan () || op2.known_isnan () + || rel == VREL_LE) { r = range_true (type); return true; @@ -1713,7 +1796,7 @@ public: if (op2.maybe_isnan ()) op2_no_nan.clear_nan (); if (!range_op_handler (LE_EXPR).fold_range (r, type, op1_no_nan, - op2_no_nan, rel)) + op2_no_nan, trio)) return false; // The result is the same as the ordered version when the // comparison is true or when the operands cannot be NANs. @@ -1807,9 +1890,12 @@ class foperator_unordered_gt : public range_operator public: bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel = TRIO_VARYING) const final override + relation_trio trio = TRIO_VARYING) const final override { - if (op1.known_isnan () || op2.known_isnan ()) + relation_kind rel = trio.op1_op2 (); + + if (op1.known_isnan () || op2.known_isnan () + || rel == VREL_GT) { r = range_true (type); return true; @@ -1821,7 +1907,7 @@ public: if (op2.maybe_isnan ()) op2_no_nan.clear_nan (); if (!range_op_handler (GT_EXPR).fold_range (r, type, op1_no_nan, - op2_no_nan, rel)) + op2_no_nan, trio)) return false; // The result is the same as the ordered version when the // comparison is true or when the operands cannot be NANs. @@ -1919,9 +2005,12 @@ class foperator_unordered_ge : public range_operator public: bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel = TRIO_VARYING) const final override + relation_trio trio = TRIO_VARYING) const final override { - if (op1.known_isnan () || op2.known_isnan ()) + relation_kind rel = trio.op1_op2 (); + + if (op1.known_isnan () || op2.known_isnan () + || rel == VREL_GE) { r = range_true (type); return true; @@ -1933,7 +2022,7 @@ public: if (op2.maybe_isnan ()) op2_no_nan.clear_nan (); if (!range_op_handler (GE_EXPR).fold_range (r, type, op1_no_nan, - op2_no_nan, rel)) + op2_no_nan, trio)) return false; // The result is the same as the ordered version when the // comparison is true or when the operands cannot be NANs. @@ -2030,9 +2119,12 @@ class foperator_unordered_equal : public range_operator public: bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_trio rel = TRIO_VARYING) const final override + relation_trio trio = TRIO_VARYING) const final override { - if (op1.known_isnan () || op2.known_isnan ()) + relation_kind rel = trio.op1_op2 (); + + if (op1.known_isnan () || op2.known_isnan () + || rel == VREL_EQ) { r = range_true (type); return true; @@ -2044,7 +2136,7 @@ public: if (op2.maybe_isnan ()) op2_no_nan.clear_nan (); if (!range_op_handler (EQ_EXPR).fold_range (r, type, op1_no_nan, - op2_no_nan, rel)) + op2_no_nan, trio)) return false; // The result is the same as the ordered version when the // comparison is true or when the operands cannot be NANs. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-12.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-12.c new file mode 100644 index 00000000000..0c9426dfef5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-12.c @@ -0,0 +1,23 @@ +// { dg-do compile } +// { dg-options "-O2 -fdisable-tree-fre1 -fdump-tree-evrp" } + +void link_error (); +void func (); + +void foo1 (float x, float y) +{ + if (x != y) + if (x == y) + link_error(); +} + +void foo2 (float a, float b) +{ + if (a != b) + // This conditional should be folded away. + if (a != b) + func (); +} + +// { dg-final { scan-tree-dump-not "link_error" "evrp" } } +// { dg-final { scan-tree-dump-times "if \\(a_2\\(D\\) != b_3\\(D\\)" 1 "evrp" } } -- 2.41.0