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 C0A053858411 for ; Wed, 26 Jan 2022 14:51:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C0A053858411 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-614-jer-rVxlMOeAAZ01Hactjg-1; Wed, 26 Jan 2022 09:51:16 -0500 X-MC-Unique: jer-rVxlMOeAAZ01Hactjg-1 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id BE0AC1083F62; Wed, 26 Jan 2022 14:51:14 +0000 (UTC) Received: from t14s.localdomain.com (unknown [10.2.17.161]) by smtp.corp.redhat.com (Postfix) with ESMTP id 4BCB57CADB; Wed, 26 Jan 2022 14:51:14 +0000 (UTC) From: David Malcolm To: Mikael Morin , gcc-patches@gcc.gnu.org Subject: [committed] analyzer: fix sense in range::add_bound [PR94362] Date: Wed, 26 Jan 2022 09:51:12 -0500 Message-Id: <20220126145112.2906612-1-dmalcolm@redhat.com> In-Reply-To: <5c117e61-a678-ba0f-85db-2aed59f3d0d1@orange.fr> References: <5c117e61-a678-ba0f-85db-2aed59f3d0d1@orange.fr> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.12 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-13.0 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_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 26 Jan 2022 14:51:21 -0000 On Sun, 2022-01-23 at 17:34 +0100, Mikael Morin wrote: > Hello, > > Le 21/01/2022 à 00:59, David Malcolm via Gcc-patches a écrit : > > diff --git a/gcc/analyzer/constraint-manager.cc > > b/gcc/analyzer/constraint-manager.cc > > index 568e7150ea7..7c4a85bbb24 100644 > > --- a/gcc/analyzer/constraint-manager.cc > > +++ b/gcc/analyzer/constraint-manager.cc > > @@ -301,6 +301,80 @@ range::above_upper_bound (tree rhs_const) > > const > > m_upper_bound.m_constant).is_true (); > > } > > > > +/* Attempt to add B to the bound of the given kind of this range. > > + Return true if feasible; false if infeasible. */ > > + > > +bool > > +range::add_bound (bound b, enum bound_kind bound_kind) > > +{ > > + b.ensure_closed (bound_kind); > > + > > + switch (bound_kind) > > + { > > + default: > > + gcc_unreachable (); > > + case BK_LOWER: > > + /* Discard redundant bounds. */ > > + if (m_lower_bound.m_constant) > > + { > > + m_lower_bound.ensure_closed (BK_LOWER); > > + if (!tree_int_cst_lt (b.m_constant, > > + m_lower_bound.m_constant)) > > + return true; > > isn’t this condition reversed? > > > + } > > + m_lower_bound = b; > > + break; > > + case BK_UPPER: > > + /* Discard redundant bounds. */ > > + if (m_upper_bound.m_constant) > > + { > > + m_upper_bound.ensure_closed (BK_UPPER); > > + if (tree_int_cst_le (b.m_constant, > > + m_upper_bound.m_constant)) > > + return true; > > same here. > > All the tests added have just one lower and one upper bound, so they > don’t use the short-circuit code, but amending one of them as follows > makes the problem appear as the test starts to fails. It should > continue to work, shouldn’t it? > > > diff --git a/gcc/analyzer/constraint-manager.cc > b/gcc/analyzer/constraint-manager.cc > index 7c4a85bbb24..3f38b857722 100644 > --- a/gcc/analyzer/constraint-manager.cc > +++ b/gcc/analyzer/constraint-manager.cc > @@ -3697,6 +3697,7 @@ test_constant_comparisons () > region_model_manager mgr; > { > region_model model (&mgr); > + ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a); > ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a); > ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4); > } Good catch, thanks. Fixed as follows, which also moves the rejection of contradictory constraints in range::add_bound to earlier, so that this code can be self-tested. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r12-6875-ge966a508e03fe28bfca65a1e60e579fa90355ea6. gcc/analyzer/ChangeLog: PR analyzer/94362 * constraint-manager.cc (range::add_bound): Fix tests for discarding redundant constraints. Perform test for rejecting unsatisfiable constraints earlier so that they don't update the object on failure. (selftest::test_range): New. (selftest::test_constant_comparisons): Add test coverage for existing constraints becoming narrower until they are unsatisfiable. (selftest::run_constraint_manager_tests): Call test_range. Signed-off-by: David Malcolm --- gcc/analyzer/constraint-manager.cc | 93 +++++++++++++++++++++++++----- 1 file changed, 79 insertions(+), 14 deletions(-) diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 7c4a85bbb24..88b0988513a 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -318,35 +318,42 @@ range::add_bound (bound b, enum bound_kind bound_kind) if (m_lower_bound.m_constant) { m_lower_bound.ensure_closed (BK_LOWER); - if (!tree_int_cst_lt (b.m_constant, - m_lower_bound.m_constant)) + if (tree_int_cst_le (b.m_constant, + m_lower_bound.m_constant)) return true; } + if (m_upper_bound.m_constant) + { + m_upper_bound.ensure_closed (BK_UPPER); + /* Reject B <= V <= UPPER when B > UPPER. */ + if (!tree_int_cst_le (b.m_constant, + m_upper_bound.m_constant)) + return false; + } m_lower_bound = b; break; + case BK_UPPER: /* Discard redundant bounds. */ if (m_upper_bound.m_constant) { m_upper_bound.ensure_closed (BK_UPPER); - if (tree_int_cst_le (b.m_constant, - m_upper_bound.m_constant)) + if (!tree_int_cst_lt (b.m_constant, + m_upper_bound.m_constant)) return true; } + if (m_lower_bound.m_constant) + { + m_lower_bound.ensure_closed (BK_LOWER); + /* Reject LOWER <= V <= B when LOWER > B. */ + if (!tree_int_cst_le (m_lower_bound.m_constant, + b.m_constant)) + return false; + } m_upper_bound = b; break; } - if (m_lower_bound.m_constant - && m_upper_bound.m_constant) - { - m_lower_bound.ensure_closed (BK_LOWER); - m_upper_bound.ensure_closed (BK_UPPER); - /* Reject LOWER <= V <= UPPER when LOWER > UPPER. */ - if (!tree_int_cst_le (m_lower_bound.m_constant, - m_upper_bound.m_constant)) - return false; - } return true; } @@ -3093,6 +3100,49 @@ namespace selftest { These have to be written in terms of a region_model, since the latter is responsible for managing svalue instances. */ +/* Verify that range::add_bound works as expected. */ + +static void +test_range () +{ + tree int_0 = build_int_cst (integer_type_node, 0); + tree int_1 = build_int_cst (integer_type_node, 1); + tree int_2 = build_int_cst (integer_type_node, 2); + tree int_5 = build_int_cst (integer_type_node, 5); + + { + range r; + ASSERT_FALSE (r.constrained_to_single_element ()); + + /* (r >= 1). */ + ASSERT_TRUE (r.add_bound (GE_EXPR, int_1)); + + /* Redundant. */ + ASSERT_TRUE (r.add_bound (GE_EXPR, int_0)); + ASSERT_TRUE (r.add_bound (GT_EXPR, int_0)); + + ASSERT_FALSE (r.constrained_to_single_element ()); + + /* Contradiction. */ + ASSERT_FALSE (r.add_bound (LT_EXPR, int_1)); + + /* (r < 5). */ + ASSERT_TRUE (r.add_bound (LT_EXPR, int_5)); + ASSERT_FALSE (r.constrained_to_single_element ()); + + /* Contradiction. */ + ASSERT_FALSE (r.add_bound (GE_EXPR, int_5)); + + /* (r < 2). */ + ASSERT_TRUE (r.add_bound (LT_EXPR, int_2)); + ASSERT_TRUE (r.constrained_to_single_element ()); + + /* Redundant. */ + ASSERT_TRUE (r.add_bound (LE_EXPR, int_1)); + ASSERT_TRUE (r.constrained_to_single_element ()); + } +} + /* Verify that setting and getting simple conditions within a region_model work (thus exercising the underlying constraint_manager). */ @@ -3700,6 +3750,20 @@ test_constant_comparisons () ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a); ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4); } + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a); + ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a); + ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5); + ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4); + } + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a); + ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5); + ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a); + ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4); + } { region_model model (&mgr); ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_4); @@ -4323,6 +4387,7 @@ run_constraint_manager_tests (bool transitivity) int saved_flag_analyzer_transitivity = flag_analyzer_transitivity; flag_analyzer_transitivity = transitivity; + test_range (); test_constraint_conditions (); if (flag_analyzer_transitivity) { -- 2.26.3