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, 310 insertions, 4 deletions

diff --git a/gcc/analyzer/sm-malloc.cc b/gcc/analyzer/sm-malloc.cc
index d050ef8..dd10356 100644
--- a/gcc/analyzer/sm-malloc.cc
+++ b/gcc/analyzer/sm-malloc.cc
@@ -87,6 +87,9 @@ enum resource_state
   /* The start state.  */
   RS_START,
 
+  /* State for a pointer that's been unconditionally dereferenced.  */
+  RS_ASSUMED_NON_NULL,
+
   /* State for a pointer that's known to be NULL.  */
   RS_NULL,
 
@@ -126,7 +129,7 @@ struct allocation_state : public state_machine::state
     m_deallocator (deallocator)
   {}
 
-  void dump_to_pp (pretty_printer *pp) const final override;
+  void dump_to_pp (pretty_printer *pp) const override;
 
   const allocation_state *get_nonnull () const;
 
@@ -135,6 +138,25 @@ struct allocation_state : public state_machine::state
   const deallocator *m_deallocator;
 };
 
+/* Custom state subclass, for the "assumed-non-null" state
+   where the assumption happens in a particular frame.  */
+
+struct assumed_non_null_state : public allocation_state
+{
+  assumed_non_null_state (const char *name, unsigned id,
+			  const frame_region *frame)
+  : allocation_state (name, id, RS_ASSUMED_NON_NULL,
+		      NULL, NULL),
+    m_frame (frame)
+  {
+    gcc_assert (m_frame);
+  }
+
+  void dump_to_pp (pretty_printer *pp) const final override;
+
+  const frame_region *m_frame;
+};
+
 /* An enum for choosing which wording to use in various diagnostics
    when describing deallocations.  */
 
@@ -384,14 +406,25 @@ public:
 		     enum tree_code op,
 		     const svalue *rhs) const final override;
 
+  void on_pop_frame (sm_state_map *smap,
+		     const frame_region *) const final override;
+
   bool can_purge_p (state_t s) const final override;
   std::unique_ptr<pending_diagnostic> on_leak (tree var) const final override;
 
   bool reset_when_passed_to_unknown_fn_p (state_t s,
 					  bool is_mutable) const final override;
 
+  state_t
+  maybe_get_merged_states_nonequal (state_t state_a,
+				    state_t state_b) const final override;
+
   static bool unaffected_by_call_p (tree fndecl);
 
+  void maybe_assume_non_null (sm_context *sm_ctxt,
+			      tree ptr,
+			      const gimple *stmt) const;
+
   void on_realloc_with_move (region_model *model,
 			     sm_state_map *smap,
 			     const svalue *old_ptr_sval,
@@ -406,6 +439,10 @@ public:
 
   /* States that are independent of api.  */
 
+  /* States for a pointer that's been unconditionally dereferenced
+     in a particular stack frame.  */
+  hash_map<const frame_region *, state_t> m_assumed_non_null;
+
   /* State for a pointer that's known to be NULL.  */
   state_t m_null;
 
@@ -425,6 +462,16 @@ private:
   const deallocator *
   get_or_create_deallocator (tree deallocator_fndecl);
 
+  state_t
+  get_or_create_assumed_non_null_state_for_frame (const frame_region *frame);
+
+  void
+  maybe_complain_about_deref_before_check (sm_context *sm_ctxt,
+					   const supernode *node,
+					   const gimple *stmt,
+					   const assumed_non_null_state *,
+					   tree ptr) const;
+
   void on_allocator_call (sm_context *sm_ctxt,
 			  const gcall *call,
 			  const deallocator_set *deallocators,
@@ -678,6 +725,14 @@ freed_p (state_machine::state_t state)
   return get_rs (state) == RS_FREED;
 }
 
+/* Return true if STATE is a value that has been assumed to be non-NULL.  */
+
+static bool
+assumed_non_null_p (state_machine::state_t state)
+{
+  return get_rs (state) == RS_ASSUMED_NON_NULL;
+}
+
 /* Class for diagnostics relating to malloc_state_machine.  */
 
 class malloc_diagnostic : public pending_diagnostic
@@ -1428,6 +1483,80 @@ private:
   const char *m_funcname;
 };
 
+/* Concrete pending_diagnostic subclass for -Wanalyzer-deref-before-check.  */
+
+class deref_before_check : public malloc_diagnostic
+{
+public:
+  deref_before_check (const malloc_state_machine &sm, tree arg)
+  : malloc_diagnostic (sm, arg)
+  {}
+
+  const char *get_kind () const final override { return "deref_before_check"; }
+
+  int get_controlling_option () const final override
+  {
+    return OPT_Wanalyzer_deref_before_check;
+  }
+
+  bool emit (rich_location *rich_loc) final override
+  {
+    if (m_arg)
+      return warning_at (rich_loc, get_controlling_option (),
+			 "check of %qE for NULL after already"
+			 " dereferencing it",
+			 m_arg);
+    else
+      return warning_at (rich_loc, get_controlling_option (),
+			 "check of pointer for NULL after already"
+			 " dereferencing it");
+  }
+
+  label_text describe_state_change (const evdesc::state_change &change)
+    final override
+  {
+    if (change.m_old_state == m_sm.get_start_state ()
+	&& assumed_non_null_p (change.m_new_state))
+      {
+	m_first_deref_event = change.m_event_id;
+	if (m_arg)
+	  return change.formatted_print ("pointer %qE is dereferenced here",
+					 m_arg);
+	else
+	  return label_text::borrow ("pointer is dereferenced here");
+      }
+    return malloc_diagnostic::describe_state_change (change);
+  }
+
+  label_text describe_final_event (const evdesc::final_event &ev) final override
+  {
+    if (m_first_deref_event.known_p ())
+      {
+	if (m_arg)
+	  return ev.formatted_print ("pointer %qE is checked for NULL here but"
+				     " it was already dereferenced at %@",
+				     m_arg, &m_first_deref_event);
+	else
+	  return ev.formatted_print ("pointer is checked for NULL here but"
+				     " it was already dereferenced at %@",
+				     &m_first_deref_event);
+      }
+    else
+      {
+	if (m_arg)
+	  return ev.formatted_print ("pointer %qE is checked for NULL here but"
+				     " it was already dereferenced",
+				     m_arg);
+	else
+	  return ev.formatted_print ("pointer is checked for NULL here but"
+				     " it was already dereferenced");
+      }
+  }
+
+private:
+  diagnostic_event_id_t m_first_deref_event;
+};
+
 /* struct allocation_state : public state_machine::state.  */
 
 /* Implementation of state_machine::state::dump_to_pp vfunc
@@ -1456,6 +1585,17 @@ allocation_state::get_nonnull () const
   return as_a_allocation_state (m_deallocators->m_nonnull);
 }
 
+/* struct assumed_non_null_state : public allocation_state.  */
+
+void
+assumed_non_null_state::dump_to_pp (pretty_printer *pp) const
+{
+  allocation_state::dump_to_pp (pp);
+  pp_string (pp, " (in ");
+  m_frame->dump_to_pp (pp, true);
+  pp_character (pp, ')');
+}
+
 /* malloc_state_machine's ctor.  */
 
 malloc_state_machine::malloc_state_machine (logger *logger)
@@ -1597,6 +1737,22 @@ malloc_state_machine::get_or_create_deallocator (tree deallocator_fndecl)
   return d;
 }
 
+/* Get the "assumed-non-null" state for assumptions made within FRAME,
+   creating it if necessary.  */
+
+state_machine::state_t
+malloc_state_machine::
+get_or_create_assumed_non_null_state_for_frame (const frame_region *frame)
+{
+  if (state_t *slot = m_assumed_non_null.get (frame))
+    return *slot;
+  state_machine::state *new_state
+    = new assumed_non_null_state ("assumed-non-null", alloc_state_id (), frame);
+  add_custom_state (new_state);
+  m_assumed_non_null.put (frame, new_state);
+  return new_state;
+}
+
 /* Try to identify the function declaration either by name or as a known malloc
    builtin.  */
 
@@ -1629,6 +1785,33 @@ known_allocator_p (const_tree fndecl, const gcall *call)
   return false;
 }
 
+/* If PTR's nullness is not known, transition it to the "assumed-non-null"
+   state for the current frame.  */
+
+void
+malloc_state_machine::maybe_assume_non_null (sm_context *sm_ctxt,
+					     tree ptr,
+					     const gimple *stmt) const
+{
+  const region_model *old_model = sm_ctxt->get_old_region_model ();
+  if (!old_model)
+    return;
+
+  tree null_ptr_cst = build_int_cst (TREE_TYPE (ptr), 0);
+  tristate known_non_null
+    = old_model->eval_condition (ptr, NE_EXPR, null_ptr_cst, NULL);
+  if (known_non_null.is_unknown ())
+    {
+      /* Cast away const-ness for cache-like operations.  */
+      malloc_state_machine *mut_this
+	= const_cast <malloc_state_machine *> (this);
+      state_t next_state
+	= mut_this->get_or_create_assumed_non_null_state_for_frame
+	(old_model->get_current_frame ());
+      sm_ctxt->set_next_state (stmt, ptr, next_state);
+    }
+}
+
 /* Implementation of state_machine::on_stmt vfunc for malloc_state_machine.  */
 
 bool
@@ -1743,6 +1926,8 @@ malloc_state_machine::on_stmt (sm_context *sm_ctxt,
 					   (*this, diag_arg, callee_fndecl, i));
 			  sm_ctxt->set_next_state (stmt, arg, m_stop);
 			}
+		      else if (state == m_start)
+			maybe_assume_non_null (sm_ctxt, arg, stmt);
 		    }
 		}
 	      BITMAP_FREE (nonnull_args);
@@ -1760,6 +1945,36 @@ malloc_state_machine::on_stmt (sm_context *sm_ctxt,
 	  }
       }
 
+  /* Look for pointers explicitly being compared against zero
+     that are in state assumed_non_null i.e. we already defererenced
+     them.
+     We have to do this check here, rather than in on_condition
+     because we add a constraint that the pointer is non-null when
+     dereferencing it, and this makes the apply_constraints_for_gcond
+     find known-true and known-false conditions; on_condition is only
+     called when adding new constraints.  */
+  if (const gcond *cond_stmt = dyn_cast <const gcond *> (stmt))
+    {
+      enum tree_code op = gimple_cond_code (cond_stmt);
+      if (op == EQ_EXPR || op == NE_EXPR)
+	{
+	  tree lhs = gimple_cond_lhs (cond_stmt);
+	  tree rhs = gimple_cond_rhs (cond_stmt);
+	  if (any_pointer_p (lhs)
+	      && any_pointer_p (rhs)
+	      && zerop (rhs))
+	    {
+	      state_t state = sm_ctxt->get_state (stmt, lhs);
+	      if (assumed_non_null_p (state))
+		maybe_complain_about_deref_before_check
+		  (sm_ctxt, node,
+		   stmt,
+		   (const assumed_non_null_state *)state,
+		   lhs);
+	    }
+	}
+    }
+
   if (tree lhs = sm_ctxt->is_zero_assignment (stmt))
     if (any_pointer_p (lhs))
       on_zero_assignment (sm_ctxt, stmt,lhs);
@@ -1778,7 +1993,9 @@ malloc_state_machine::on_stmt (sm_context *sm_ctxt,
 	  tree arg = TREE_OPERAND (op, 0);
 
 	  state_t state = sm_ctxt->get_state (stmt, arg);
-	  if (unchecked_p (state))
+	  if (state == m_start)
+	    maybe_assume_non_null (sm_ctxt, arg, stmt);
+	  else if (unchecked_p (state))
 	    {
 	      tree diag_arg = sm_ctxt->get_diagnostic_tree (arg);
 	      sm_ctxt->warn (node, stmt, arg,
@@ -1808,6 +2025,53 @@ malloc_state_machine::on_stmt (sm_context *sm_ctxt,
   return false;
 }
 
+/* Given a check against null of PTR in assumed-non-null state STATE,
+   potentially add a deref_before_check warning to SM_CTXT.  */
+
+void
+malloc_state_machine::
+maybe_complain_about_deref_before_check (sm_context *sm_ctxt,
+					 const supernode *node,
+					 const gimple *stmt,
+					 const assumed_non_null_state *state,
+					 tree ptr) const
+{
+  const region_model *model = sm_ctxt->get_old_region_model ();
+  if (!model)
+    return;
+
+  /* Don't complain if the current frame (where the check is occurring) is
+     deeper than the frame in which the "not null" assumption was made.
+     This suppress false positives for cases like:
+
+	void foo (struct s *p)
+	{
+	  int val = s->some_field; // deref here
+	  shared_helper (p);
+	}
+
+     where "shared_helper" has:
+
+	void shared_helper (struct s *p)
+	{
+	  if (!p) // check here
+	    return;
+	  // etc
+	}
+
+     since the check in "shared_helper" is OK.  */
+  const frame_region *checked_in_frame = model->get_current_frame ();
+  const frame_region *assumed_nonnull_in_frame = state->m_frame;
+  if (checked_in_frame->get_index () > assumed_nonnull_in_frame->get_index ())
+    return;
+
+  tree diag_ptr = sm_ctxt->get_diagnostic_tree (ptr);
+  sm_ctxt->warn
+    (node, stmt, ptr,
+     make_unique<deref_before_check> (*this, diag_ptr));
+  sm_ctxt->set_next_state (stmt, ptr, m_stop);
+}
+
 /* Handle a call to an allocator.
    RETURNS_NONNULL is true if CALL is to a fndecl known to have
    __attribute__((returns_nonnull)).  */
@@ -1870,8 +2134,8 @@ malloc_state_machine::on_deallocator_call (sm_context *sm_ctxt,
 
   state_t state = sm_ctxt->get_state (call, arg);
 
-  /* start/unchecked/nonnull -> freed.  */
-  if (state == m_start)
+  /* start/assumed_non_null/unchecked/nonnull -> freed.  */
+  if (state == m_start || assumed_non_null_p (state))
     sm_ctxt->set_next_state (call, arg, d->m_freed);
   else if (unchecked_p (state) || nonnull_p (state))
     {
@@ -2016,6 +2280,31 @@ malloc_state_machine::on_condition (sm_context *sm_ctxt,
     }
 }
 
+/* Implementation of state_machine::on_pop_frame vfunc for malloc_state_machine.
+   Clear any "assumed-non-null" state where the assumption happened in
+   FRAME_REG.  */
+
+void
+malloc_state_machine::on_pop_frame (sm_state_map *smap,
+				    const frame_region *frame_reg) const
+{
+  hash_set<const svalue *> svals_to_clear;
+  for (auto kv : *smap)
+    {
+      const svalue *sval = kv.first;
+      state_t state = kv.second.m_state;
+      if (assumed_non_null_p (state))
+	{
+	  const assumed_non_null_state *assumed_state
+	    = (const assumed_non_null_state *)state;
+	  if (frame_reg == assumed_state->m_frame)
+	    svals_to_clear.add (sval);
+	}
+    }
+  for (auto sval : svals_to_clear)
+    smap->clear_any_state (sval);
+}
+
 /* Implementation of state_machine::can_purge_p vfunc for malloc_state_machine.
    Don't allow purging of pointers in state 'unchecked' or 'nonnull'
    (to avoid false leak reports).  */
@@ -2053,6 +2342,23 @@ malloc_state_machine::reset_when_passed_to_unknown_fn_p (state_t s,
   return is_mutable;
 }
 
+/* Implementation of state_machine::maybe_get_merged_states_nonequal vfunc
+   for malloc_state_machine.
+
+   Support discarding "assumed-non-null" states when merging with
+   start state.  */
+
+state_machine::state_t
+malloc_state_machine::maybe_get_merged_states_nonequal (state_t state_a,
+							state_t state_b) const
+{
+  if (assumed_non_null_p (state_a) && state_b == m_start)
+    return m_start;
+  if (state_a == m_start && assumed_non_null_p (state_b))
+    return m_start;
+  return NULL;
+}
+
 /* Return true if calls to FNDECL are known to not affect this sm-state.  */
 
 bool