analyzer: new warning: -Wanalyzer-deref-before-check [PR99671]

This patch implements a new -Wanalyzer-deref-before-check within
-fanalyzer.  It complains about code paths in which a pointer is checked
for NULL after it has already been dereferenced.

For example, for the testcase in PR 77432 the diagnostic emits:
deref-before-check-1.c: In function 'test_from_pr77432':
deref-before-check-1.c:6:8: warning: check of 'a' for NULL after already dereferencing it [-Wanalyzer-deref-before-check]
    6 |     if (a)
      |        ^
  'test_from_pr77432': events 1-2
    |
    |    5 |     int b = *a;
    |      |         ^
    |      |         |
    |      |         (1) pointer 'a' is dereferenced here
    |    6 |     if (a)
    |      |        ~
    |      |        |
    |      |        (2) pointer 'a' is checked for NULL here but it was already dereferenced at (1)
    |

and in PR 77425 we had an instance of this hidden behind a
macro, which the diagnostic complains about as follows:

deref-before-check-pr77425.c: In function 'get_odr_type':
deref-before-check-pr77425.c:35:10: warning: check of 'odr_types_ptr' for NULL after already dereferencing it [-Wanalyzer-deref-before-check]
   35 |       if (odr_types_ptr)
      |          ^
  'get_odr_type': events 1-3
    |
    |   27 |   if (cond)
    |      |      ^
    |      |      |
    |      |      (1) following 'false' branch...
    |......
    |   31 |   else if (other_cond)
    |      |           ~~~~~~~~~~~
    |      |           ||
    |      |           |(2) ...to here
    |      |           (3) following 'true' branch...
    |
  'get_odr_type': event 4
    |
    |   11 | #define odr_types (*odr_types_ptr)
    |      |                   ~^~~~~~~~~~~~~~~
    |      |                    |
    |      |                    (4) ...to here
deref-before-check-pr77425.c:33:7: note: in expansion of macro 'odr_types'
    |   33 |       odr_types[val->id] = 0;
    |      |       ^~~~~~~~~
    |
  'get_odr_type': event 5
    |
    |   11 | #define odr_types (*odr_types_ptr)
    |      |                   ~^~~~~~~~~~~~~~~
    |      |                    |
    |      |                    (5) pointer 'odr_types_ptr' is dereferenced here
deref-before-check-pr77425.c:33:7: note: in expansion of macro 'odr_types'
    |   33 |       odr_types[val->id] = 0;
    |      |       ^~~~~~~~~
    |
  'get_odr_type': event 6
    |
    |   35 |       if (odr_types_ptr)
    |      |          ^
    |      |          |
    |      |          (6) pointer 'odr_types_ptr' is checked for NULL here but it was already dereferenced at (5)
    |

gcc/analyzer/ChangeLog:
	PR analyzer/99671
	* analyzer.opt (Wanalyzer-deref-before-check): New warning.
	* diagnostic-manager.cc
	(null_assignment_sm_context::set_next_state): Only add state
	change events for transition to "null" state.
	(null_assignment_sm_context::is_transition_to_null): New.
	* engine.cc (impl_region_model_context::on_pop_frame): New.
	* exploded-graph.h (impl_region_model_context::on_pop_frame): New
	decl.
	* program-state.cc (sm_state_map::clear_any_state): New.
	(sm_state_map::can_merge_with_p): New.
	(program_state::can_merge_with_p): Replace requirement that
	sm-states be equal in favor of an attempt to merge them.
	* program-state.h (sm_state_map::clear_any_state): New decl.
	(sm_state_map::can_merge_with_p): New decl.
	* region-model.cc (region_model::eval_condition): Make const.
	(region_model::pop_frame): Call ctxt->on_pop_frame.
	* region-model.h (region_model::eval_condition): Make const.
	(region_model_context::on_pop_frame): New vfunc.
	(noop_region_model_context::on_pop_frame): New.
	(region_model_context_decorator::on_pop_frame): New.
	* sm-malloc.cc (enum resource_state): Add RS_ASSUMED_NON_NULL.
	(allocation_state::dump_to_pp): Drop "final".
	(struct assumed_non_null_state): New subclass.
	(malloc_state_machine::m_assumed_non_null): New.
	(assumed_non_null_p): New.
	(class deref_before_check): New.
	(assumed_non_null_state::dump_to_pp): New.
	(malloc_state_machine::get_or_create_assumed_non_null_state_for_frame):
	New.
	(malloc_state_machine::maybe_assume_non_null): New.
	(malloc_state_machine::on_stmt): Transition from start state to
	"assumed-non-null" state for pointers passed to
	__attribute__((nonnull)) arguments, and for pointers explicitly
	dereferenced.  Call maybe_complain_about_deref_before_check for
	pointers explicitly compared against NULL.
	(malloc_state_machine::maybe_complain_about_deref_before_check):
	New.
	(malloc_state_machine::on_deallocator_call): Also transition
	"assumed-non-null" states to "freed".
	(malloc_state_machine::on_pop_frame): New.
	(malloc_state_machine::maybe_get_merged_states_nonequal): New.
	* sm-malloc.dot: Update for changes to sm-malloc.cc.
	* sm.h (state_machine::on_pop_frame): New.
	(state_machine::maybe_get_merged_state): New.
	(state_machine::maybe_get_merged_states_nonequal): New.

gcc/ChangeLog:
	* doc/gcc/gcc-command-options/options-that-control-static-analysis.rst:
	Add -Wanalyzer-deref-before-check.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/deref-before-check-1.c: New test.
	* gcc.dg/analyzer/deref-before-check-2.c: New test.
	* gcc.dg/analyzer/deref-before-check-pr77425.c: New test.
	* gcc.dg/analyzer/malloc-1.c (test_51): New test.

gcc/ChangeLog:
	PR analyzer/99671
	* tristate.h (tristate::is_unknown): New.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

1 files changed, 74 insertions, 9 deletions

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index d00fd5e..a0585f5 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -518,6 +518,14 @@ sm_state_map::impl_set_state (const svalue *sval,
   return true;
 }
 
+/* Clear any state for SVAL from this state map.  */
+
+void
+sm_state_map::clear_any_state (const svalue *sval)
+{
+  m_map.remove (sval);
+}
+
 /* Set the "global" state within this state map to STATE.  */
 
 void
@@ -719,6 +727,67 @@ sm_state_map::canonicalize_svalue (const svalue *sval,
   return sval;
 }
 
+/* Attempt to merge this state map with OTHER, writing the result
+   into *OUT.
+   Return true if the merger was possible, false otherwise.
+
+   Normally, only identical state maps can be merged, so that
+   differences between state maps lead to different enodes
+
+   However some state machines may support merging states to
+   allow for discarding of less important states, and thus avoid
+   blow-up of the exploded graph.  */
+
+bool
+sm_state_map::can_merge_with_p (const sm_state_map &other,
+				const state_machine &sm,
+				const extrinsic_state &ext_state,
+				sm_state_map **out) const
+{
+  /* If identical, then they merge trivially, with a copy.  */
+  if (*this == other)
+    {
+      delete *out;
+      *out = clone ();
+      return true;
+    }
+
+  delete *out;
+  *out = new sm_state_map (sm);
+
+  /* Otherwise, attempt to merge element by element. */
+
+  /* Try to merge global state.  */
+  if (state_machine::state_t merged_global_state
+      = sm.maybe_get_merged_state (get_global_state (),
+				   other.get_global_state ()))
+    (*out)->set_global_state (merged_global_state);
+  else
+    return false;
+
+  /* Try to merge state each svalue's state (for the union
+     of svalues represented by each smap).
+     Ignore the origin information.  */
+  hash_set<const svalue *> svals;
+  for (auto kv : *this)
+    svals.add (kv.first);
+  for (auto kv : other)
+    svals.add (kv.first);
+  for (auto sval : svals)
+    {
+      state_machine::state_t this_state = get_state (sval, ext_state);
+      state_machine::state_t other_state = other.get_state (sval, ext_state);
+      if (state_machine::state_t merged_state
+	    = sm.maybe_get_merged_state (this_state, other_state))
+	(*out)->impl_set_state (sval, merged_state, NULL, ext_state);
+      else
+	return false;
+    }
+
+  /* Successfully merged all elements.  */
+  return true;
+}
+
 /* class program_state.  */
 
 /* program_state's ctor.  */
@@ -1283,11 +1352,14 @@ program_state::can_merge_with_p (const program_state &other,
   gcc_assert (out);
   gcc_assert (m_region_model);
 
-  /* Early reject if there are sm-differences between the states.  */
+  /* Attempt to merge the sm-states.  */
   int i;
   sm_state_map *smap;
   FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
-    if (*m_checker_states[i] != *other.m_checker_states[i])
+    if (!m_checker_states[i]->can_merge_with_p (*other.m_checker_states[i],
+						ext_state.get_sm (i),
+						ext_state,
+						&out->m_checker_states[i]))
       return false;
 
   /* Attempt to merge the region_models.  */
@@ -1298,13 +1370,6 @@ program_state::can_merge_with_p (const program_state &other,
 					 this, &other))
     return false;
 
-  /* Copy m_checker_states to OUT.  */
-  FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
-    {
-      delete smap;
-      out->m_checker_states[i] = m_checker_states[i]->clone ();
-    }
-
   out->m_region_model->canonicalize ();
 
   return true;