analyzer: reject ((i + 1 > 0) && (i < 0)) for integers [PR94362]

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.

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>

5 files changed, 281 insertions, 13 deletions

diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
index 568e715..7c4a85b 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 e93fa7f..f67c764 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 b58d089..f6b7f98 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 0000000..1302ced
--- /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 0000000..301d2ed
--- /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 "" } */
+}