From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2209) id EE0373858D28; Mon, 6 Dec 2021 23:37:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EE0373858D28 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="utf-8" From: David Malcolm To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-5815] analyzer: fix equivalence class state purging [PR103533] X-Act-Checkin: gcc X-Git-Author: David Malcolm X-Git-Refname: refs/heads/master X-Git-Oldrev: 325c6163a33af91264d1b7817a45b8425d5e6a4f X-Git-Newrev: c9543403c19fdc3c3b5a8db8546340de085bd14e Message-Id: <20211206233713.EE0373858D28@sourceware.org> Date: Mon, 6 Dec 2021 23:37:13 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 06 Dec 2021 23:37:14 -0000 https://gcc.gnu.org/g:c9543403c19fdc3c3b5a8db8546340de085bd14e commit r12-5815-gc9543403c19fdc3c3b5a8db8546340de085bd14e Author: David Malcolm Date: Mon Dec 6 14:04:35 2021 -0500 analyzer: fix equivalence class state purging [PR103533] Whilst debugging state explosions seen when enabling taint detection with -fanalyzer (PR analyzer/103533), I noticed that constraint manager instances could contain stray, redundant constants, such as this instance: constraint_manager: equiv classes: ec0: {(int)0 == [m_constant]‘0’} ec1: {(size_t)4 == [m_constant]‘4’} constraints: where there are two equivalence classes, each just containing a constant, with no constraints using them. This patch makes constraint_manager::canonicalize more aggressive about purging state, handling the case of purging a redundant EC containing just a constant. gcc/analyzer/ChangeLog: PR analyzer/103533 * constraint-manager.cc (equiv_class::contains_non_constant_p): New. (constraint_manager::canonicalize): Call it when determining redundant ECs. (selftest::test_purging): New selftest. (selftest::run_constraint_manager_tests): Likewise. * constraint-manager.h (equiv_class::contains_non_constant_p): New decl. Signed-off-by: David Malcolm Diff: --- gcc/analyzer/constraint-manager.cc | 149 ++++++++++++++++++++++++++++++++++++- gcc/analyzer/constraint-manager.h | 2 + 2 files changed, 149 insertions(+), 2 deletions(-) diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index ea6b5dc60e0..76e44e77d0a 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -1145,6 +1145,30 @@ equiv_class::canonicalize () m_vars.qsort (svalue::cmp_ptr_ptr); } +/* Return true if this EC contains a variable, false if it merely + contains constants. + Subroutine of constraint_manager::canonicalize, for removing + redundant ECs. */ + +bool +equiv_class::contains_non_constant_p () const +{ + if (m_constant) + { + for (auto iter : m_vars) + if (iter->maybe_get_constant ()) + continue; + else + /* We have {non-constant == constant}. */ + return true; + /* We only have constants. */ + return false; + } + else + /* Return true if we have {non-constant == non-constant}. */ + return m_vars.length () > 1; +} + /* Get a debug string for C_OP. */ const char * @@ -2718,8 +2742,7 @@ constraint_manager::canonicalize () { equiv_class *ec = m_equiv_classes[i]; if (!used_ecs.contains (ec) - && ((ec->m_vars.length () < 2 && ec->m_constant == NULL_TREE) - || (ec->m_vars.length () == 0))) + && !ec->contains_non_constant_p ()) { m_equiv_classes.unordered_remove (i); delete ec; @@ -3704,6 +3727,127 @@ test_many_constants () } } +/* Verify that purging state relating to a variable doesn't leave stray + equivalence classes (after canonicalization). */ + +static void +test_purging (void) +{ + tree int_0 = build_int_cst (integer_type_node, 0); + tree a = build_global_decl ("a", integer_type_node); + tree b = build_global_decl ("b", integer_type_node); + + /* "a != 0". */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0); + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1); + + /* Purge state for "a". */ + const svalue *sval_a = model.get_rvalue (a, NULL); + model.purge_state_involving (sval_a, NULL); + model.canonicalize (); + /* We should have an empty constraint_manager. */ + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0); + } + + /* "a != 0" && "b != 0". */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0); + ADD_SAT_CONSTRAINT (model, b, NE_EXPR, int_0); + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 3); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 2); + + /* Purge state for "a". */ + const svalue *sval_a = model.get_rvalue (a, NULL); + model.purge_state_involving (sval_a, NULL); + model.canonicalize (); + /* We should just have the constraint/ECs involving b != 0. */ + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1); + ASSERT_CONDITION_TRUE (model, b, NE_EXPR, int_0); + } + + /* "a != 0" && "b == 0". */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0); + ADD_SAT_CONSTRAINT (model, b, EQ_EXPR, int_0); + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1); + + /* Purge state for "a". */ + const svalue *sval_a = model.get_rvalue (a, NULL); + model.purge_state_involving (sval_a, NULL); + model.canonicalize (); + /* We should just have the EC involving b == 0. */ + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0); + ASSERT_CONDITION_TRUE (model, b, EQ_EXPR, int_0); + } + + /* "a == 0". */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0); + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0); + + /* Purge state for "a". */ + const svalue *sval_a = model.get_rvalue (a, NULL); + model.purge_state_involving (sval_a, NULL); + model.canonicalize (); + /* We should have an empty constraint_manager. */ + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0); + } + + /* "a == 0" && "b != 0". */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0); + ADD_SAT_CONSTRAINT (model, b, NE_EXPR, int_0); + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1); + + /* Purge state for "a". */ + const svalue *sval_a = model.get_rvalue (a, NULL); + model.purge_state_involving (sval_a, NULL); + model.canonicalize (); + /* We should just have the constraint/ECs involving b != 0. */ + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1); + ASSERT_CONDITION_TRUE (model, b, NE_EXPR, int_0); + } + + /* "a == 0" && "b == 0". */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0); + ADD_SAT_CONSTRAINT (model, b, EQ_EXPR, int_0); + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0); + + /* Purge state for "a". */ + const svalue *sval_a = model.get_rvalue (a, NULL); + model.purge_state_involving (sval_a, NULL); + model.canonicalize (); + /* We should just have the EC involving b == 0. */ + ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1); + ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0); + ASSERT_CONDITION_TRUE (model, b, EQ_EXPR, int_0); + } +} + /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */ static void @@ -4035,6 +4179,7 @@ run_constraint_manager_tests (bool transitivity) test_constraint_impl (); test_equality (); test_many_constants (); + test_purging (); test_bounded_range (); test_bounded_ranges (); diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h index 0a430eae91f..c7b9d9c697b 100644 --- a/gcc/analyzer/constraint-manager.h +++ b/gcc/analyzer/constraint-manager.h @@ -248,6 +248,8 @@ public: json::object *to_json () const; + bool contains_non_constant_p () const; + /* An equivalence class can contain multiple constants (e.g. multiple different zeroes, for different types); these are just for the last constant added. */