* [committed] analyzer: reject ((i + 1 > 0) && (i < 0)) for integers [PR94362]
@ 2022-01-20 23:59 David Malcolm
2022-01-23 16:34 ` Mikael Morin
0 siblings, 1 reply; 3+ messages in thread
From: David Malcolm @ 2022-01-20 23:59 UTC (permalink / raw)
To: gcc-patches
PR analyzer/94362 reports a false positive from
-Wanalyzer-null-dereference seen when analyzing OpenSSL.
The root cause is that the analyzer's path feasibility checker
erroneously considers this to be feasible:
(R + 1 > 0) && (R < 0)
for int R (the return value from sk_EVP_PKEY_ASN1_METHOD_num),
whereas it's not satisfiable for any int R.
This patch makes the constraint manager try harder to reject
such combinations of conditions, fixing the false positive;
perhaps in the longer term we ought to use an SMT solver.
Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Pushed to trunk as r12-6782-gc4b8f3730a80025192fdb485ad2535c165340e41.
gcc/analyzer/ChangeLog:
PR analyzer/94362
* constraint-manager.cc (bound::ensure_closed): Convert param to
enum bound_kind.
(range::constrained_to_single_element): Likewise.
(range::add_bound): New.
(constraint_manager::add_constraint): Handle SVAL + OFFSET
compared to a constant.
(constraint_manager::get_ec_bounds): Rewrite in terms of
range::add_bound.
(constraint_manager::eval_condition): Reject if range::add_bound
fails.
(selftest::test_constant_comparisons): Add test coverage for
various impossible combinations of integer comparisons.
* constraint-manager.h (enum bound_kind): New.
(struct bound): Likewise.
(bound::ensure_closed): Convert to param to enum bound_kind.
(struct range): Convert to...
(class range): ...this, making fields private.
(range::add_bound): New decls.
* region-model.cc (region_model::add_constraint): Fail if
constraint_manager::add_constraint fails.
gcc/testsuite/ChangeLog:
PR analyzer/94362
* gcc.dg/analyzer/pr94362-1.c: New test.
* gcc.dg/analyzer/pr94362-2.c: New test.
Signed-off-by: David Malcolm <dmalcolm@redhat.com>
---
gcc/analyzer/constraint-manager.cc | 172 ++++++++++++++++++++--
gcc/analyzer/constraint-manager.h | 15 +-
gcc/analyzer/region-model.cc | 5 +-
gcc/testsuite/gcc.dg/analyzer/pr94362-1.c | 60 ++++++++
gcc/testsuite/gcc.dg/analyzer/pr94362-2.c | 42 ++++++
5 files changed, 281 insertions(+), 13 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/analyzer/pr94362-1.c
create mode 100644 gcc/testsuite/gcc.dg/analyzer/pr94362-2.c
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
@@ -117,7 +117,7 @@ minus_one (tree cst)
closed one. */
void
-bound::ensure_closed (bool is_upper)
+bound::ensure_closed (enum bound_kind bound_kind)
{
if (!m_closed)
{
@@ -125,7 +125,7 @@ bound::ensure_closed (bool is_upper)
For example, convert 3 < x into 4 <= x,
and convert x < 5 into x <= 4. */
gcc_assert (CONSTANT_CLASS_P (m_constant));
- m_constant = fold_build2 (is_upper ? MINUS_EXPR : PLUS_EXPR,
+ m_constant = fold_build2 (bound_kind == BK_UPPER ? MINUS_EXPR : PLUS_EXPR,
TREE_TYPE (m_constant),
m_constant, integer_one_node);
gcc_assert (CONSTANT_CLASS_P (m_constant));
@@ -205,8 +205,8 @@ range::constrained_to_single_element ()
return NULL_TREE;
/* Convert any open bounds to closed bounds. */
- m_lower_bound.ensure_closed (false);
- m_upper_bound.ensure_closed (true);
+ m_lower_bound.ensure_closed (BK_LOWER);
+ m_upper_bound.ensure_closed (BK_UPPER);
// Are they equal?
tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
@@ -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;
+ }
+ 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;
+ }
+ 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;
+}
+
+/* Attempt to add (RANGE OP RHS_CONST) as a bound to this range.
+ Return true if feasible; false if infeasible. */
+
+bool
+range::add_bound (enum tree_code op, tree rhs_const)
+{
+ switch (op)
+ {
+ default:
+ return true;
+ case LT_EXPR:
+ /* "V < RHS_CONST" */
+ return add_bound (bound (rhs_const, false), BK_UPPER);
+ case LE_EXPR:
+ /* "V <= RHS_CONST" */
+ return add_bound (bound (rhs_const, true), BK_UPPER);
+ case GE_EXPR:
+ /* "V >= RHS_CONST" */
+ return add_bound (bound (rhs_const, true), BK_LOWER);
+ case GT_EXPR:
+ /* "V > RHS_CONST" */
+ return add_bound (bound (rhs_const, false), BK_LOWER);
+ }
+}
+
/* struct bounded_range. */
bounded_range::bounded_range (const_tree lower, const_tree upper)
@@ -1718,6 +1792,27 @@ constraint_manager::add_constraint (const svalue *lhs,
return false;
}
+ /* If adding
+ (SVAL + OFFSET) > CST,
+ then that can imply:
+ SVAL > (CST - OFFSET). */
+ if (const binop_svalue *lhs_binop = lhs->dyn_cast_binop_svalue ())
+ if (tree rhs_cst = rhs->maybe_get_constant ())
+ if (tree offset = lhs_binop->get_arg1 ()->maybe_get_constant ())
+ if ((op == GT_EXPR || op == LT_EXPR
+ || op == GE_EXPR || op == LE_EXPR)
+ && lhs_binop->get_op () == PLUS_EXPR)
+ {
+ tree offset_of_cst = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs_cst),
+ rhs_cst, offset);
+ const svalue *implied_lhs = lhs_binop->get_arg0 ();
+ enum tree_code implied_op = op;
+ const svalue *implied_rhs
+ = m_mgr->get_or_create_constant_svalue (offset_of_cst);
+ if (!add_constraint (implied_lhs, implied_op, implied_rhs))
+ return false;
+ }
+
add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
return true;
}
@@ -2241,12 +2336,12 @@ constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
case CONSTRAINT_LT:
/* We have "EC_ID < OTHER_CST". */
- result.m_upper_bound = bound (other_cst, false);
+ result.add_bound (bound (other_cst, false), BK_UPPER);
break;
case CONSTRAINT_LE:
/* We have "EC_ID <= OTHER_CST". */
- result.m_upper_bound = bound (other_cst, true);
+ result.add_bound (bound (other_cst, true), BK_UPPER);
break;
}
}
@@ -2263,13 +2358,13 @@ constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
case CONSTRAINT_LT:
/* We have "OTHER_CST < EC_ID"
i.e. "EC_ID > OTHER_CST". */
- result.m_lower_bound = bound (other_cst, false);
+ result.add_bound (bound (other_cst, false), BK_LOWER);
break;
case CONSTRAINT_LE:
/* We have "OTHER_CST <= EC_ID"
i.e. "EC_ID >= OTHER_CST". */
- result.m_lower_bound = bound (other_cst, true);
+ result.add_bound (bound (other_cst, true), BK_LOWER);
break;
}
}
@@ -2350,7 +2445,15 @@ constraint_manager::eval_condition (equiv_class_id lhs_ec,
/* Look at existing bounds on LHS_EC. */
range lhs_bounds = get_ec_bounds (lhs_ec);
- return lhs_bounds.eval_condition (op, rhs_const);
+ tristate result = lhs_bounds.eval_condition (op, rhs_const);
+ if (result.is_known ())
+ return result;
+
+ /* Also reject if range::add_bound fails. */
+ if (!lhs_bounds.add_bound (op, rhs_const))
+ return tristate (false);
+
+ return tristate::unknown ();
}
/* Evaluate the condition LHS OP RHS, without modifying this
@@ -3452,6 +3555,7 @@ test_transitivity ()
static void
test_constant_comparisons ()
{
+ tree int_1 = build_int_cst (integer_type_node, 1);
tree int_3 = build_int_cst (integer_type_node, 3);
tree int_4 = build_int_cst (integer_type_node, 4);
tree int_5 = build_int_cst (integer_type_node, 5);
@@ -3462,6 +3566,8 @@ test_constant_comparisons ()
tree a = build_global_decl ("a", integer_type_node);
tree b = build_global_decl ("b", integer_type_node);
+ tree a_plus_one = build2 (PLUS_EXPR, integer_type_node, a, int_1);
+
/* Given a >= 1024, then a <= 1023 should be impossible. */
{
region_model_manager mgr;
@@ -3562,6 +3668,54 @@ test_constant_comparisons ()
ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4);
ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4);
}
+
+ /* "a > 3 && a <= 3" should be impossible. */
+ {
+ region_model_manager mgr;
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
+ ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_3);
+ }
+
+ /* "(a + 1) > 3 && a < 3" should be impossible. */
+ {
+ region_model_manager mgr;
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3);
+ ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_3);
+ }
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_3);
+ ADD_UNSAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3);
+ }
+ }
+
+ /* "3 < a < 4" should be impossible for integer a. */
+ {
+ region_model_manager mgr;
+ {
+ region_model model (&mgr);
+ 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);
+ ADD_UNSAT_CONSTRAINT (model, int_3, LT_EXPR, a);
+ }
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
+ ADD_UNSAT_CONSTRAINT (model, int_4, GT_EXPR, a);
+ }
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, int_4, GT_EXPR, a);
+ ADD_UNSAT_CONSTRAINT (model, a, GT_EXPR, int_3);
+ }
+ }
}
/* Verify various lower-level implementation details about
diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h
index e93fa7f181a..f67c7647497 100644
--- a/gcc/analyzer/constraint-manager.h
+++ b/gcc/analyzer/constraint-manager.h
@@ -25,6 +25,12 @@ namespace ana {
class constraint_manager;
+enum bound_kind
+{
+ BK_LOWER,
+ BK_UPPER
+};
+
/* One of the end-points of a range. */
struct bound
@@ -33,7 +39,7 @@ struct bound
bound (tree constant, bool closed)
: m_constant (constant), m_closed (closed) {}
- void ensure_closed (bool is_upper);
+ void ensure_closed (enum bound_kind bound_kind);
const char * get_relation_as_str () const;
@@ -44,8 +50,9 @@ struct bound
/* A range of values, used for determining if a value has been
constrained to just one possible constant value. */
-struct range
+class range
{
+public:
range () : m_lower_bound (), m_upper_bound () {}
range (const bound &lower, const bound &upper)
: m_lower_bound (lower), m_upper_bound (upper) {}
@@ -60,6 +67,10 @@ struct range
bool below_lower_bound (tree rhs_const) const;
bool above_upper_bound (tree rhs_const) const;
+ bool add_bound (bound b, enum bound_kind bound_kind);
+ bool add_bound (enum tree_code op, tree rhs_const);
+
+private:
bound m_lower_bound;
bound m_upper_bound;
};
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index b58d0894d4a..f6b7f986a39 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -2801,8 +2801,9 @@ region_model::add_constraint (const svalue *lhs,
if (add_constraints_from_binop (lhs, op, rhs, &out, ctxt))
return out;
- /* Store the constraint. */
- m_constraints->add_constraint (lhs, op, rhs);
+ /* Attempt to store the constraint. */
+ if (!m_constraints->add_constraint (lhs, op, rhs))
+ return false;
/* Notify the context, if any. This exists so that the state machines
in a program_state can be notified about the condition, and so can
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94362-1.c b/gcc/testsuite/gcc.dg/analyzer/pr94362-1.c
new file mode 100644
index 00000000000..1302cedb856
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr94362-1.c
@@ -0,0 +1,60 @@
+/* { dg-additional-options "-Wno-analyzer-too-complex" } */
+/* TODO: remove the need for -Wno-analyzer-too-complex. */
+
+typedef struct evp_pkey_asn1_method_st EVP_PKEY_ASN1_METHOD;
+typedef struct engine_st ENGINE;
+struct stack_st_EVP_PKEY_ASN1_METHOD;
+struct evp_pkey_asn1_method_st {
+ unsigned long pkey_flags;
+};
+
+const EVP_PKEY_ASN1_METHOD *ENGINE_pkey_asn1_find_str(ENGINE **pe,
+ const char *str, int len);
+extern int
+sk_EVP_PKEY_ASN1_METHOD_num(const struct stack_st_EVP_PKEY_ASN1_METHOD *sk);
+extern const EVP_PKEY_ASN1_METHOD *
+sk_EVP_PKEY_ASN1_METHOD_value(const struct stack_st_EVP_PKEY_ASN1_METHOD *sk,
+ int idx);
+extern const EVP_PKEY_ASN1_METHOD hmac_asn1_meth;
+static const EVP_PKEY_ASN1_METHOD *standard_methods[] = {&hmac_asn1_meth};
+static struct stack_st_EVP_PKEY_ASN1_METHOD *app_methods = ((void *)0);
+
+int EVP_PKEY_asn1_get_count(void) {
+ int num = (sizeof(standard_methods) / sizeof((standard_methods)[0]));
+ if (app_methods)
+ num += sk_EVP_PKEY_ASN1_METHOD_num(app_methods);
+ return num;
+}
+
+const EVP_PKEY_ASN1_METHOD *EVP_PKEY_asn1_get0(int idx) {
+ int num = (sizeof(standard_methods) / sizeof((standard_methods)[0]));
+ if (idx < 0)
+ return ((void *)0);
+ if (idx < num)
+ return standard_methods[idx];
+ idx -= num;
+ return sk_EVP_PKEY_ASN1_METHOD_value(app_methods, idx);
+}
+
+const EVP_PKEY_ASN1_METHOD *EVP_PKEY_asn1_find_str(ENGINE **pe, const char *str,
+ int len) {
+ int i;
+ const EVP_PKEY_ASN1_METHOD *ameth = ((void *)0);
+
+ if (pe) {
+ ENGINE *e;
+ ameth = ENGINE_pkey_asn1_find_str(&e, str, len);
+ if (ameth) {
+ *pe = e;
+ return ameth;
+ }
+ *pe = ((void *)0);
+ }
+ for (i = EVP_PKEY_asn1_get_count(); i-- > 0;) {
+ ameth = EVP_PKEY_asn1_get0(i);
+ if (ameth->pkey_flags & 0x1)
+ continue;
+ return ameth;
+ }
+ return ((void *)0);
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94362-2.c b/gcc/testsuite/gcc.dg/analyzer/pr94362-2.c
new file mode 100644
index 00000000000..301d2ed6063
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr94362-2.c
@@ -0,0 +1,42 @@
+/* Verify that we consider various paths to be impossible,
+ using functions to thwart early optimizations. */
+
+#include "analyzer-decls.h"
+
+void test_1 (int idx)
+{
+ if (idx > 0)
+ if (idx - 1 < 0)
+ __analyzer_dump_path (); /* { dg-bogus "" } */
+}
+
+static int called_by_test_1a (int idx)
+{
+ return idx - 1;
+}
+
+void test_1a (int idx)
+{
+ if (idx > 0)
+ if (called_by_test_1a (idx) < 0)
+ __analyzer_dump_path (); /* { dg-bogus "" } */
+}
+
+void test_2 (int idx)
+{
+ if (idx + 1 > 0)
+ if (idx < 0)
+ __analyzer_dump_path (); /* { dg-bogus "" } */
+}
+
+static int called_by_test_2a (int idx)
+{
+ return idx + 1;
+}
+
+void test_2a (int idx)
+{
+ if (called_by_test_2a (idx) > 0)
+ if (idx < 0)
+ __analyzer_dump_path (); /* { dg-bogus "" } */
+}
--
2.26.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [committed] analyzer: reject ((i + 1 > 0) && (i < 0)) for integers [PR94362]
2022-01-20 23:59 [committed] analyzer: reject ((i + 1 > 0) && (i < 0)) for integers [PR94362] David Malcolm
@ 2022-01-23 16:34 ` Mikael Morin
2022-01-26 14:51 ` [committed] analyzer: fix sense in range::add_bound [PR94362] David Malcolm
0 siblings, 1 reply; 3+ messages in thread
From: Mikael Morin @ 2022-01-23 16:34 UTC (permalink / raw)
To: David Malcolm, gcc-patches
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);
}
^ permalink raw reply [flat|nested] 3+ messages in thread
* [committed] analyzer: fix sense in range::add_bound [PR94362]
2022-01-23 16:34 ` Mikael Morin
@ 2022-01-26 14:51 ` David Malcolm
0 siblings, 0 replies; 3+ messages in thread
From: David Malcolm @ 2022-01-26 14:51 UTC (permalink / raw)
To: Mikael Morin, gcc-patches
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 <dmalcolm@redhat.com>
---
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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-01-26 14:51 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-01-20 23:59 [committed] analyzer: reject ((i + 1 > 0) && (i < 0)) for integers [PR94362] David Malcolm
2022-01-23 16:34 ` Mikael Morin
2022-01-26 14:51 ` [committed] analyzer: fix sense in range::add_bound [PR94362] David Malcolm
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).