[gcc r12-6476] analyzer: fix false +ve on bitwise binops (PR analyzer/102692)

[gcc r12-6476] analyzer: fix false +ve on bitwise binops (PR analyzer/102692)

[David Malcolm]

https://gcc.gnu.org/g:4f34f8cc1d064bfaaed723312c71e92f495d429b

commit r12-6476-g4f34f8cc1d064bfaaed723312c71e92f495d429b
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Fri Jan 7 17:44:23 2022 -0500

    analyzer: fix false +ve on bitwise binops (PR analyzer/102692)
    
    PR analyzer/102692 reports a false positive at -O2 from
    -Wanalyzer-null-dereference on:
      if (!p || q || !p->next)
    
    At the gimple level, -O2 has converted the first || into bitwise or
    controlling a jump:
      _4 = _2 | _3;
      if (_4 != 0)
    and a recursive call has been converted to iteration.  The analyzer hits
    the symbolic value complexity limit whilst analyzing the iteration and
    hits a case where _2 is (_Bool)1 (i.e. true) and _3 (i.e. q) is
    UNKNOWN(_Bool).
    
    There are two issues leading to the false positive; fixing either issue
    fixes the false positive; this patch fixes both for good measure:
    
    (a) The analyzer erronously treats bitwise ops on UNKNOWN(_Bool) as UNKNOWN,
    even for case like (1 | UNKNOWN) where we know the result, leading to
    bogus edges in the exploded graph.  The patch fixes these cases.
    
    (b) The state-handling code creates "UNKNOWN" symbolic values, as a way
    to give up when symbolic expressions get too complicated, and in various
    other cases.  This makes sense when building the exploded graph, since
    we want the analysis to terminate, but doesn't make sense when checking
    the feasibility along a specific path, where we want precision.  The patch
    prevents all use of "unknown" symbolic values when performing feasibility
    checking of a path (before it merely stopped doing complexity-checking),
    by creating a unique placeholder_svalue instead.
    
    This fixes the -Wanalyzer-null-dereference false positive.
    
    Unfortunately, with GCC 12 there's also a false positive from
    -Wanalyzer-use-of-uninitialized-value on this code, which is a separate
    issue that the patch does not fix.
    
    gcc/analyzer/ChangeLog:
            PR analyzer/102692
            * diagnostic-manager.cc
            (class auto_disable_complexity_checks): Rename to...
            (class auto_checking_feasibility): ...this, updating
            the calls accordingly.
            (epath_finder::explore_feasible_paths): Update for renaming.
            * region-model-manager.cc
            (region_model_manager::region_model_manager): Update for change from
            m_check_complexity to m_checking_feasibility.
            (region_model_manager::reject_if_too_complex): Likewise.
            (region_model_manager::get_or_create_unknown_svalue): Handle
            m_checking_feasibility.
            (region_model_manager::create_unique_svalue): New.
            (region_model_manager::maybe_fold_binop): Handle BIT_AND_EXPR and
            BIT_IOR_EXPRs on booleans where we know the result.
            * region-model.cc (test_binop_svalue_folding): Add test coverage
            for the above.
            * region-model.h (region_model_manager::create_unique_svalue): New
            decl.
            (region_model_manager::enable_complexity_check): Replace with...
            (region_model_manager::begin_checking_feasibility): ...this.
            (region_model_manager::disable_complexity_check): Replace with...
            (region_model_manager::end_checking_feasibility): ...this.
            (region_model_manager::m_check_complexity): Replace with...
            (region_model_manager::m_checking_feasibility): ...this.
            (region_model_manager::m_managed_dynamic_svalues): New field.
    
    gcc/testsuite/ChangeLog:
            PR analyzer/102692
            * gcc.dg/analyzer/pr102692.c: New test.
    
    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

Diff:
---
 gcc/analyzer/diagnostic-manager.cc       |  17 +++--
 gcc/analyzer/region-model-manager.cc     |  55 +++++++++++++++-
 gcc/analyzer/region-model.cc             |  33 ++++++++++
 gcc/analyzer/region-model.h              |  16 ++++-
 gcc/testsuite/gcc.dg/analyzer/pr102692.c | 110 +++++++++++++++++++++++++++++++
 5 files changed, 219 insertions(+), 12 deletions(-)

diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index e9b8fe36177..73c133dd66d 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -303,18 +303,21 @@ private:
 
    Hence this is an RAII class for temporarily disabling complexity-checking
    in the region_model_manager, for use within
-   epath_finder::explore_feasible_paths.  */
+   epath_finder::explore_feasible_paths.
 
-class auto_disable_complexity_checks
+   We also disable the creation of unknown_svalue instances during feasibility
+   checking, instead creating unique svalues, to avoid paradoxes in paths.  */
+
+class auto_checking_feasibility
 {
 public:
-  auto_disable_complexity_checks (region_model_manager *mgr) : m_mgr (mgr)
+  auto_checking_feasibility (region_model_manager *mgr) : m_mgr (mgr)
   {
-    m_mgr->disable_complexity_check ();
+    m_mgr->begin_checking_feasibility ();
   }
-  ~auto_disable_complexity_checks ()
+  ~auto_checking_feasibility ()
   {
-    m_mgr->enable_complexity_check ();
+    m_mgr->end_checking_feasibility ();
   }
 private:
   region_model_manager *m_mgr;
@@ -406,7 +409,7 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
   exploded_path *best_path = NULL;
 
   {
-    auto_disable_complexity_checks sentinel (mgr);
+    auto_checking_feasibility sentinel (mgr);
 
     while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
 				  &best_path))
diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index 998bbe7858c..903cdfde91d 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -73,7 +73,7 @@ region_model_manager::region_model_manager (logger *logger)
   m_stack_region (alloc_region_id (), &m_root_region),
   m_heap_region (alloc_region_id (), &m_root_region),
   m_unknown_NULL (NULL),
-  m_check_complexity (true),
+  m_checking_feasibility (false),
   m_max_complexity (0, 0),
   m_code_region (alloc_region_id (), &m_root_region),
   m_fndecls_map (), m_labels_map (),
@@ -166,7 +166,7 @@ region_model_manager::too_complex_p (const complexity &c) const
 bool
 region_model_manager::reject_if_too_complex (svalue *sval)
 {
-  if (!m_check_complexity)
+  if (m_checking_feasibility)
     return false;
 
   const complexity &c = sval->get_complexity ();
@@ -238,6 +238,11 @@ region_model_manager::get_or_create_int_cst (tree type, poly_int64 val)
 const svalue *
 region_model_manager::get_or_create_unknown_svalue (tree type)
 {
+  /* Don't create unknown values when doing feasibility testing;
+     instead, create a unique svalue.  */
+  if (m_checking_feasibility)
+    return create_unique_svalue (type);
+
   /* Special-case NULL, so that the hash_map can use NULL as the
      "empty" value.  */
   if (type == NULL_TREE)
@@ -255,6 +260,16 @@ region_model_manager::get_or_create_unknown_svalue (tree type)
   return sval;
 }
 
+/* Return a freshly-allocated svalue of TYPE, owned by this manager.  */
+
+const svalue *
+region_model_manager::create_unique_svalue (tree type)
+{
+  svalue *sval = new placeholder_svalue (type, "unique");
+  m_managed_dynamic_svalues.safe_push (sval);
+  return sval;
+}
+
 /* Return the svalue * for the initial value of REG, creating it if
    necessary.  */
 
@@ -584,6 +599,42 @@ region_model_manager::maybe_fold_binop (tree type, enum tree_code op,
 							 cst1, arg1))
 	      return sval;
 	}
+      if (arg0->get_type () == boolean_type_node
+	  && arg1->get_type () == boolean_type_node)
+	{
+	  /* If the LHS are both _Bool, then... */
+	  /* ..."(1 & x) -> x".  */
+	  if (cst0 && !zerop (cst0))
+	    return get_or_create_cast (type, arg1);
+	  /* ..."(x & 1) -> x".  */
+	  if (cst1 && !zerop (cst1))
+	    return get_or_create_cast (type, arg0);
+	  /* ..."(0 & x) -> 0".  */
+	  if (cst0 && zerop (cst0))
+	    return get_or_create_int_cst (type, 0);
+	  /* ..."(x & 0) -> 0".  */
+	  if (cst1 && zerop (cst1))
+	    return get_or_create_int_cst (type, 0);
+	}
+      break;
+    case BIT_IOR_EXPR:
+      if (arg0->get_type () == boolean_type_node
+	  && arg1->get_type () == boolean_type_node)
+	{
+	  /* If the LHS are both _Bool, then... */
+	  /* ..."(1 | x) -> 1".  */
+	  if (cst0 && !zerop (cst0))
+	    return get_or_create_int_cst (type, 1);
+	  /* ..."(x | 1) -> 1".  */
+	  if (cst1 && !zerop (cst1))
+	    return get_or_create_int_cst (type, 1);
+	  /* ..."(0 | x) -> x".  */
+	  if (cst0 && zerop (cst0))
+	    return get_or_create_cast (type, arg1);
+	  /* ..."(x | 0) -> x".  */
+	  if (cst1 && zerop (cst1))
+	    return get_or_create_cast (type, arg0);
+	}
       break;
     case TRUTH_ANDIF_EXPR:
     case TRUTH_AND_EXPR:
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 8708a91551d..b58d0894d4a 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -4555,6 +4555,39 @@ test_binop_svalue_folding ()
     = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR,
 			       x_init_plus_one, cst_sval[1]);
   ASSERT_EQ (x_init_plus_one_plus_one, x_init_plus_two);
+
+  /* Verify various binops on booleans.  */
+  {
+    const svalue *sval_true = mgr.get_or_create_int_cst (boolean_type_node, 1);
+    const svalue *sval_false = mgr.get_or_create_int_cst (boolean_type_node, 0);
+    const svalue *sval_unknown
+      = mgr.get_or_create_unknown_svalue (boolean_type_node);
+    const placeholder_svalue sval_placeholder (boolean_type_node, "v");
+    for (auto op : {BIT_IOR_EXPR, TRUTH_OR_EXPR})
+      {
+	ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+					    sval_true, sval_unknown),
+		   sval_true);
+	ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+					    sval_false, sval_unknown),
+		   sval_unknown);
+	ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+					    sval_false, &sval_placeholder),
+		   &sval_placeholder);
+      }
+    for (auto op : {BIT_AND_EXPR, TRUTH_AND_EXPR})
+      {
+	ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+					    sval_false, sval_unknown),
+		   sval_false);
+	ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+					    sval_true, sval_unknown),
+		   sval_unknown);
+	ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+					    sval_true, &sval_placeholder),
+		   &sval_placeholder);
+      }
+  }
 }
 
 /* Verify that sub_svalues are folded as expected.  */
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index b1fa4fc82af..c78efe8f215 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -286,6 +286,11 @@ public:
   const svalue *maybe_get_char_from_string_cst (tree string_cst,
 						tree byte_offset_cst);
 
+  /* Dynamically-allocated svalue instances.
+     The number of these within the analysis can grow arbitrarily.
+     They are still owned by the manager.  */
+  const svalue *create_unique_svalue (tree type);
+
   /* region consolidation.  */
   const stack_region * get_stack_region () const { return &m_stack_region; }
   const heap_region *get_heap_region () const { return &m_heap_region; }
@@ -332,8 +337,8 @@ public:
 
   void log_stats (logger *logger, bool show_objs) const;
 
-  void enable_complexity_check (void) { m_check_complexity = true; }
-  void disable_complexity_check (void) { m_check_complexity = false; }
+  void begin_checking_feasibility (void) { m_checking_feasibility = true; }
+  void end_checking_feasibility (void) { m_checking_feasibility = false; }
 
   logger *get_logger () const { return m_logger; }
 
@@ -429,7 +434,12 @@ private:
 		   asm_output_svalue *> asm_output_values_map_t;
   asm_output_values_map_t m_asm_output_values_map;
 
-  bool m_check_complexity;
+  bool m_checking_feasibility;
+
+  /* "Dynamically-allocated" svalue instances.
+     The number of these within the analysis can grow arbitrarily.
+     They are still owned by the manager.  */
+  auto_delete_vec<svalue> m_managed_dynamic_svalues;
 
   /* Maximum complexity of svalues that weren't rejected.  */
   complexity m_max_complexity;
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr102692.c b/gcc/testsuite/gcc.dg/analyzer/pr102692.c
new file mode 100644
index 00000000000..c8993c82980
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr102692.c
@@ -0,0 +1,110 @@
+/* { dg-additional-options "-O2 -Wno-analyzer-too-complex" } */
+/* TODO: remove the need for -Wno-analyzer-too-complex.  */
+
+struct lisp;
+union vectorlike_header { long size; };
+
+static struct lisp *
+make_lisp_ptr (void *ptr, int type)
+{
+  char *p = ptr;
+  void *q = p + type;
+  return q;
+}
+
+static _Bool
+TAGGEDP (struct lisp *a, unsigned tag)
+{
+  return ! (((unsigned) (long) a - tag) & 7);
+}
+
+static _Bool
+VECTORLIKEP (struct lisp *x)
+{
+  return TAGGEDP (x, 5);
+}
+
+extern _Bool
+PSEUDOVECTOR_TYPEP (union vectorlike_header const *a, int code);
+
+static _Bool
+PSEUDOVECTORP (struct lisp *a, int code)
+{
+  if (! VECTORLIKEP (a))
+    return 0;
+  else
+    return PSEUDOVECTOR_TYPEP ((union vectorlike_header *) ((char *) a - 5),
+			       code);
+}
+
+struct Lisp_Overlay
+{
+  union vectorlike_header header;
+  struct lisp *end;
+  struct Lisp_Overlay *next;
+};
+
+static _Bool
+OVERLAYP (struct lisp *x)
+{
+  return PSEUDOVECTORP (x, 4);
+}
+
+static struct Lisp_Overlay *
+XOVERLAY (struct lisp *a)
+{
+  void *r = (char *) a - 5;
+  return r;
+}
+struct buffer { struct Lisp_Overlay *overlays_before; };
+
+long marker_position (struct lisp *);
+
+void
+fix_overlays_before (struct buffer *bp, long prev, long pos)
+{
+  struct Lisp_Overlay *tail = bp->overlays_before, *parent = 0, *right_pair;
+  struct lisp *tem;
+  long end;
+  while (tail
+	 && (tem = make_lisp_ptr (tail, 5),
+	     (end = marker_position (XOVERLAY (tem)->end)) >= pos))
+    {
+      parent = tail;
+      tail = tail->next;
+    }
+  if (!tail || end < prev || !tail->next) /* { dg-bogus "use of uninitialized value 'end'" "uninit" { xfail *-*-* } } */
+    /* { dg-bogus "dereference of NULL 'tail'" "null deref" { target *-*-* } .-1 } */
+    return;
+  right_pair = parent;
+  parent = tail;
+  tail = tail->next;
+  while (tail)
+    {
+      tem = make_lisp_ptr (tail, 5);
+      end = marker_position (XOVERLAY (tem)->end);
+      if (end == pos)
+	{
+	  struct Lisp_Overlay *found = tail;
+	  tail = found->next;
+	  parent->next = tail;
+	  if (!right_pair)
+	    {
+	      found->next = bp->overlays_before;
+	      bp->overlays_before = found;
+	    }
+	  else
+	    {
+	      found->next = right_pair->next;
+	      right_pair->next = found;
+	    }
+	}
+      else if (end == prev)
+	{
+	  parent = tail;
+	  tail = tail->next;
+	}
+      else
+	break;
+    }
+}