diff mbox series

[committed] analyzer: fix sense in range::add_bound [PR94362]

Message ID 20220126145112.2906612-1-dmalcolm@redhat.com
State Committed
Commit e966a508e03fe28bfca65a1e60e579fa90355ea6
Headers
Series [committed] analyzer: fix sense in range::add_bound [PR94362] |

Commit Message

David Malcolm Jan. 26, 2022, 2:51 p.m. UTC 
  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 mbox series

Patch

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)
     {