[1/2] analyzer: Fix allocation size false positive on conjured svalue [PR109577]

diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
index 2c9c435527e..24cd8960098 100644
--- a/gcc/analyzer/constraint-manager.cc
+++ b/gcc/analyzer/constraint-manager.cc
@@ -2218,6 +2218,137 @@  constraint_manager::get_equiv_class_by_svalue (const svalue *sval,
   return false;
 }
 
+/* Tries to find a svalue inside another svalue.  */
+
+class sval_finder : public visitor
+{
+public:
+  sval_finder (const svalue *query) : m_query (query)
+  {
+  }
+
+  bool found_query_p ()
+  {
+    return m_found;
+  }
+
+  void visit_region_svalue (const region_svalue *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_constant_svalue (const constant_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_unknown_svalue (const unknown_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_poisoned_svalue (const poisoned_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_setjmp_svalue (const setjmp_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_initial_svalue (const initial_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_unaryop_svalue (const unaryop_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_binop_svalue (const binop_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_sub_svalue (const sub_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_repeated_svalue (const repeated_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_bits_within_svalue (const bits_within_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_unmergeable_svalue (const unmergeable_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_placeholder_svalue (const placeholder_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_widening_svalue (const widening_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_compound_svalue (const compound_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_conjured_svalue (const conjured_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_asm_output_svalue (const asm_output_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+  void visit_const_fn_result_svalue (const const_fn_result_svalue  *sval)
+  {
+    m_found |= m_query == sval;
+  }
+
+private:
+  const svalue *m_query;
+  bool m_found;
+};
+
+/* Returns true if SVAL is constrained.  */
+
+bool
+constraint_manager::sval_constrained_p (const svalue *sval) const
+{
+  int i;
+  equiv_class *ec;
+  sval_finder finder (sval);
+  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+    {
+      int j;
+      const svalue *iv;
+      FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
+	{
+	  iv->accept (&finder);
+	  if (finder.found_query_p ())
+	    return true;
+	}
+    }
+  return false;
+}
+
 /* Ensure that SVAL has an equivalence class within this constraint_manager;
    return the ID of the class.  */
 
diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h
index 3afbc7f848e..72753e43c96 100644
--- a/gcc/analyzer/constraint-manager.h
+++ b/gcc/analyzer/constraint-manager.h
@@ -459,6 +459,7 @@  public:
 
   bool get_equiv_class_by_svalue (const svalue *sval,
 				    equiv_class_id *out) const;
+  bool sval_constrained_p (const svalue *sval) const;
   equiv_class_id get_or_add_equiv_class (const svalue *sval);
   tristate eval_condition (equiv_class_id lhs,
 			   enum tree_code op,
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 3bb3df2f063..27b4c03db27 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -2972,7 +2972,7 @@  capacity_compatible_with_type (tree cst, tree pointee_size_tree)
 
    It works by visiting all svalues inside SVAL until it reaches
    atomic nodes.  From those, it goes back up again and adds each
-   node that might be a multiple of SIZE_CST to the RESULT_SET.  */
+   node that is not a multiple of SIZE_CST to the RESULT_SET.  */
 
 class size_visitor : public visitor
 {
@@ -2983,7 +2983,7 @@  public:
     m_root_sval->accept (this);
   }
 
-  bool get_result ()
+  bool is_dubious_capacity ()
   {
     return result_set.contains (m_root_sval);
   }
@@ -2993,22 +2993,10 @@  public:
     check_constant (sval->get_constant (), sval);
   }
 
-  void visit_unknown_svalue (const unknown_svalue *sval ATTRIBUTE_UNUSED)
-    final override
-  {
-    result_set.add (sval);
-  }
-
-  void visit_poisoned_svalue (const poisoned_svalue *sval ATTRIBUTE_UNUSED)
-    final override
-  {
-    result_set.add (sval);
-  }
-
   void visit_unaryop_svalue (const unaryop_svalue *sval) final override
   {
-    const svalue *arg = sval->get_arg ();
-    if (result_set.contains (arg))
+    if (CONVERT_EXPR_CODE_P (sval->get_op ())
+	  && result_set.contains (sval->get_arg ()))
       result_set.add (sval);
   }
 
@@ -3017,28 +3005,24 @@  public:
     const svalue *arg0 = sval->get_arg0 ();
     const svalue *arg1 = sval->get_arg1 ();
 
-    if (sval->get_op () == MULT_EXPR)
-      {
-	if (result_set.contains (arg0) || result_set.contains (arg1))
-	  result_set.add (sval);
-      }
-    else
+    switch (sval->get_op ())
       {
-	if (result_set.contains (arg0) && result_set.contains (arg1))
-	  result_set.add (sval);
+	case MULT_EXPR:
+	  if (result_set.contains (arg0) && result_set.contains (arg1))
+	    result_set.add (sval);
+	  break;
+	case PLUS_EXPR:
+	case MINUS_EXPR:
+	  if (result_set.contains (arg0) || result_set.contains (arg1))
+	    result_set.add (sval);
+	  break;
+	default:
+	  break;
       }
   }
 
-  void visit_repeated_svalue (const repeated_svalue *sval) final override
-  {
-    sval->get_inner_svalue ()->accept (this);
-    if (result_set.contains (sval->get_inner_svalue ()))
-      result_set.add (sval);
-  }
-
   void visit_unmergeable_svalue (const unmergeable_svalue *sval) final override
   {
-    sval->get_arg ()->accept (this);
     if (result_set.contains (sval->get_arg ()))
       result_set.add (sval);
   }
@@ -3048,33 +3032,30 @@  public:
     const svalue *base = sval->get_base_svalue ();
     const svalue *iter = sval->get_iter_svalue ();
 
-    if (result_set.contains (base) && result_set.contains (iter))
+    if (result_set.contains (base) || result_set.contains (iter))
       result_set.add (sval);
   }
 
-  void visit_conjured_svalue (const conjured_svalue *sval ATTRIBUTE_UNUSED)
-    final override
+  void visit_initial_svalue (const initial_svalue *sval) final override
   {
-    equiv_class_id id (-1);
+    equiv_class_id id = equiv_class_id::null ();
     if (m_cm->get_equiv_class_by_svalue (sval, &id))
       {
 	if (tree cst = id.get_obj (*m_cm).get_any_constant ())
 	  check_constant (cst, sval);
-	else
-	  result_set.add (sval);
+      }
+    else if (!m_cm->sval_constrained_p (sval))
+      {
+	result_set.add (sval);
       }
   }
 
-  void visit_asm_output_svalue (const asm_output_svalue *sval ATTRIBUTE_UNUSED)
-    final override
-  {
-    result_set.add (sval);
-  }
-
-  void visit_const_fn_result_svalue (const const_fn_result_svalue
-				      *sval ATTRIBUTE_UNUSED) final override
+  void visit_conjured_svalue (const conjured_svalue *sval) final override
   {
-    result_set.add (sval);
+    equiv_class_id id = equiv_class_id::null ();
+    if (m_cm->get_equiv_class_by_svalue (sval, &id))
+      if (tree cst = id.get_obj (*m_cm).get_any_constant ())
+	check_constant (cst, sval);
   }
 
 private:
@@ -3084,10 +3065,9 @@  private:
       {
       default:
 	/* Assume all unhandled operands are compatible.  */
-	result_set.add (sval);
 	break;
       case INTEGER_CST:
-	if (capacity_compatible_with_type (cst, m_size_cst))
+	if (!capacity_compatible_with_type (cst, m_size_cst))
 	  result_set.add (sval);
 	break;
       }
@@ -3210,7 +3190,7 @@  region_model::check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 	if (!is_struct)
 	  {
 	    size_visitor v (pointee_size_tree, capacity, m_constraints);
-	    if (!v.get_result ())
+	    if (v.is_dubious_capacity ())
 	      {
 		tree expr = get_representative_tree (capacity);
 		ctxt->warn (make_unique <dubious_allocation_size> (lhs_reg,
diff --git a/gcc/testsuite/gcc.dg/analyzer/allocation-size-2.c b/gcc/testsuite/gcc.dg/analyzer/allocation-size-2.c
index 2cf64e97b41..90427229228 100644
--- a/gcc/testsuite/gcc.dg/analyzer/allocation-size-2.c
+++ b/gcc/testsuite/gcc.dg/analyzer/allocation-size-2.c
@@ -76,13 +76,13 @@  void *create_buffer(int32_t n)
   return malloc(n);
 }
 
-void test_7(int32_t n) 
+void test_7(int32_t n)
 {
   int32_t *buf = create_buffer(n * sizeof (int32_t));
   free (buf);
 }
 
-void test_8(int32_t n) 
+void test_8(int32_t n)
 {
   /* FIXME: At the moment, region_model::set_value (lhs, <return_value>)
      is called at the src_node of the return edge. This edge has no stmts
@@ -98,13 +98,11 @@  void test_9 (void)
 {
   int32_t n;
   scanf("%i", &n);
-  /* n is a conjured_svalue.  */
-  void *ptr = malloc (n); /* { dg-message "'n' bytes" "note" } */
-  int32_t *iptr = (int32_t *)ptr; /* { dg-line assign9 } */
+  /* n is a conjured_svalue without any constraint. We have to assume
+     that is a multiple of sizeof (int32_t *); see PR analyzer/110014.  */
+  void *ptr = malloc (n);
+  int32_t *iptr = (int32_t *)ptr;
   free (iptr);
-
-  /* { dg-warning "allocated buffer size is not a multiple of the pointee's size \\\[CWE-131\\\]" "warning" { target *-*-* } assign9 } */
-  /* { dg-message "'int32_t \\*' (\\\{aka '(long )?int \\*'\\\})? here; 'sizeof \\(int32_t (\\\{aka (long )?int\\\})?\\)' is '4'" "note" { target *-*-* } assign9 } */
 }
 
 void test_11 (void)
@@ -157,3 +155,13 @@  void test_13 (void)
   else
     free (ptr);
 }
+
+int *test_14 (size_t n)
+{
+  int *ptr = NULL;
+  /* n is an initial_svalue and guarded such that there is no equiv_class
+     for n itself but only for an binop_svalue containing n.  */
+  if (n % sizeof (int) == 0)
+    ptr = malloc (n);
+  return ptr;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr109577.c b/gcc/testsuite/gcc.dg/analyzer/pr109577.c
new file mode 100644
index 00000000000..a6af6f7019f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr109577.c
@@ -0,0 +1,16 @@ 
+void *malloc (unsigned long);
+
+double *
+unsafe (unsigned long n)
+{
+  return malloc (n * sizeof (double));
+}
+
+double *
+safer (unsigned long n)
+{
+  unsigned long nbytes;
+  if (__builtin_mul_overflow (n, sizeof (double), &nbytes))
+    return 0;
+  return malloc (nbytes);
+}