analyzer: eliminate enum binding_key [PR95006]

I rewrote the way the analyzer's region_model tracks the state of memory
in GCC 11 (in 808f4dfeb3a95f50f15e71148e5c1067f90a126d), which
introduced a store with a binding_map class, mapping binding keys to
symbolic values.

The GCC 11 implementation of binding keys has an enum binding_kind,
which can be "default" vs "direct"; the idea being that direct
bindings take priority over default bindings, where the latter could
be used to represent e.g. a zero-fill of a buffer, and the former
expresses those subregions that have since been touched.

This doesn't work well: it doesn't express the idea of filling
different subregions with different values, or a memset that only
touches part of a buffer, leading to numerous XFAILs in the memset
test cases (and elsewhere).

As preparatory work towards tracking uninitialized values, this patch
eliminates the enum binding_kind, so that all bindings have
equal weight; the order in which they happen is all that matters.
If a write happens which partially overwrites an existing binding,
the new code can partially overwrite a binding, potentially punching a
hole so that an existing binding is split into two parts.

The patch adds some new classes:
- a new "bits_within_svalue" symbolic value to support extracting
  parts of an existing value when its binding is partially clobbered
- a new "repeated_svalue" symbolic value to better express filling
  a region with repeated copies of a symbolic value (e.g. constant
  zero)
- a new "sized_region" region to express accessing a subregion
  with a symbolic size in bytes
and it rewrites e.g. how memset is implemented, so that we can precisely
track which bits in a region have not been touched.

That said, the patch doesn't actually implement "uninitialized" values;
I'm saving that for a followup.

gcc/analyzer/ChangeLog:
	PR analyzer/95006
	* analyzer.h (class repeated_svalue): New forward decl.
	(class bits_within_svalue): New forward decl.
	(class sized_region): New forward decl.
	(get_field_at_bit_offset): New forward decl.
	* engine.cc (exploded_graph::get_or_create_node): Validate the
	merged state.
	(exploded_graph::maybe_process_run_of_before_supernode_enodes):
	Validate the states at each stage.
	* program-state.cc (program_state::validate): Validate
	m_region_model.
	* region-model-impl-calls.cc (region_model::impl_call_memset):
	Replace special-case logic for handling constant sizes with
	a call to fill_region of a sized_region with the given fill value.
	* region-model-manager.cc (maybe_undo_optimize_bit_field_compare):
	Drop DK_direct.
	(region_model_manager::maybe_fold_sub_svalue):  Fold element-based
	subregions of an initial value into initial values of an element.
	Fold subvalues of repeated svalues.
	(region_model_manager::maybe_fold_repeated_svalue): New.
	(region_model_manager::get_or_create_repeated_svalue): New.
	(get_bit_range_for_field): New.
	(get_byte_range_for_field): New.
	(get_field_at_byte_range): New.
	(region_model_manager::maybe_fold_bits_within_svalue): New.
	(region_model_manager::get_or_create_bits_within): New.
	(region_model_manager::get_sized_region): New.
	(region_model_manager::log_stats): Update for addition of
	m_repeated_values_map, m_bits_within_values_map, and
	m_sized_regions.
	* region-model.cc (region_model::validate): New.
	(region_model::on_assignment): Drop enum binding_kind.
	(region_model::get_initial_value_for_global): Likewise.
	(region_model::get_rvalue_for_bits): Replace body with call to
	get_or_create_bits_within.
	(region_model::get_capacity): Handle RK_SIZED.
	(region_model::set_value): Drop enum binding_kind.
	(region_model::fill_region): New.
	(region_model::get_representative_path_var_1): Handle RK_SIZED.
	* region-model.h (visitor::visit_repeated_svalue): New.
	(visitor::visit_bits_within_svalue): New.
	(region_model_manager::get_or_create_repeated_svalue): New decl.
	(region_model_manager::get_or_create_bits_within): New decl.
	(region_model_manager::get_sized_region): New decl.
	(region_model_manager::maybe_fold_repeated_svalue): New decl.
	(region_model_manager::maybe_fold_bits_within_svalue): New decl.
	(region_model_manager::repeated_values_map_t): New typedef.
	(region_model_manager::m_repeated_values_map): New field.
	(region_model_manager::bits_within_values_map_t): New typedef.
	(region_model_manager::m_bits_within_values_map): New field.
	(region_model_manager::m_sized_regions): New field.
	(region_model::fill_region): New decl.
	* region.cc (region::get_base_region): Handle RK_SIZED.
	(region::base_region_p): Likewise.
	(region::get_byte_size_sval): New.
	(get_field_at_bit_offset): Make non-static.
	(region::calc_offset): Move implementation of cases to
	get_relative_concrete_offset vfunc implementations.  Handle
	RK_SIZED.
	(region::get_relative_concrete_offset): New.
	(decl_region::get_svalue_for_initializer): Drop enum binding_kind.
	(field_region::get_relative_concrete_offset): New, from
	region::calc_offset.
	(element_region::get_relative_concrete_offset): Likewise.
	(offset_region::get_relative_concrete_offset): Likewise.
	(sized_region::accept): New.
	(sized_region::dump_to_pp): New.
	(sized_region::get_byte_size): New.
	(sized_region::get_bit_size): New.
	* region.h (enum region_kind): Add RK_SIZED.
	(region::dyn_cast_sized_region): New.
	(region::get_byte_size): Make virtual.
	(region::get_bit_size): Likewise.
	(region::get_byte_size_sval): New decl.
	(region::get_relative_concrete_offset): New decl.
	(field_region::get_relative_concrete_offset): New decl.
	(element_region::get_relative_concrete_offset): Likewise.
	(offset_region::get_relative_concrete_offset): Likewise.
	(class sized_region): New.
	* store.cc (binding_kind_to_string): Delete.
	(binding_key::make): Drop enum binding_kind.
	(binding_key::dump_to_pp): Delete.
	(binding_key::cmp_ptrs): Drop enum binding_kind.
	(bit_range::contains_p): New.
	(byte_range::dump): New.
	(byte_range::contains_p): New.
	(byte_range::cmp): New.
	(concrete_binding::dump_to_pp): Drop enum binding_kind.
	(concrete_binding::cmp_ptr_ptr): Likewise.
	(symbolic_binding::dump_to_pp): Likewise.
	(symbolic_binding::cmp_ptr_ptr): Likewise.
	(binding_map::apply_ctor_val_to_range): Likewise.
	(binding_map::apply_ctor_pair_to_child_region): Likewise.
	(binding_map::get_overlapping_bindings): New.
	(binding_map::remove_overlapping_bindings): New.
	(binding_cluster::validate): New.
	(binding_cluster::bind): Drop enum binding_kind.
	(binding_cluster::bind_compound_sval): Likewise.
	(binding_cluster::purge_region): Likewise.
	(binding_cluster::zero_fill_region): Reimplement in terms of...
	(binding_cluster::fill_region): New.
	(binding_cluster::mark_region_as_unknown): Drop enum binding_kind.
	(binding_cluster::get_binding): Likewise.
	(binding_cluster::get_binding_recursive): Likewise.
	(binding_cluster::get_any_binding): Likewise.
	(binding_cluster::maybe_get_compound_binding): Reimplement.
	(binding_cluster::get_overlapping_bindings): Delete.
	(binding_cluster::remove_overlapping_bindings): Reimplement in
	terms of binding_map::remove_overlapping_bindings.
	(binding_cluster::can_merge_p): Update for removal of
	enum binding_kind.
	(binding_cluster::on_unknown_fncall): Drop enum binding_kind.
	(binding_cluster::maybe_get_simple_value): Likewise.
	(store_manager::get_concrete_binding): Likewise.
	(store_manager::get_symbolic_binding): Likewise.
	(store::validate): New.
	(store::set_value): Drop enum binding_kind.
	(store::zero_fill_region): Reimplement in terms of...
	(store::fill_region): New.
	(selftest::test_binding_key_overlap): Drop enum binding_kind.
	* store.h (enum binding_kind): Delete.
	(binding_kind_to_string): Delete decl.
	(binding_key::make): Drop enum binding_kind.
	(binding_key::dump_to_pp): Make pure virtual.
	(binding_key::get_kind): Delete.
	(binding_key::mark_deleted): Delete.
	(binding_key::mark_empty): Delete.
	(binding_key::is_deleted): Delete.
	(binding_key::is_empty): Delete.
	(binding_key::binding_key): Delete.
	(binding_key::impl_hash): Delete.
	(binding_key::impl_eq): Delete.
	(binding_key::m_kind): Delete.
	(bit_range::get_last_bit_offset): New.
	(bit_range::contains_p): New.
	(byte_range::contains_p): New.
	(byte_range::operator==): New.
	(byte_range::get_start_byte_offset): New.
	(byte_range::get_next_byte_offset): New.
	(byte_range::get_last_byte_offset): New.
	(byte_range::as_bit_range): New.
	(byte_range::cmp): New.
	(concrete_binding::concrete_binding): Drop enum binding_kind.
	(concrete_binding::hash): Likewise.
	(concrete_binding::operator==): Likewise.
	(concrete_binding::mark_deleted): New.
	(concrete_binding::mark_empty): New.
	(concrete_binding::is_deleted): New.
	(concrete_binding::is_empty): New.
	(default_hash_traits<ana::concrete_binding>::empty_zero_p): Make false.
	(symbolic_binding::symbolic_binding): Drop enum binding_kind.
	(symbolic_binding::hash): Likewise.
	(symbolic_binding::operator==): Likewise.
	(symbolic_binding::mark_deleted): New.
	(symbolic_binding::mark_empty): New.
	(symbolic_binding::is_deleted): New.
	(symbolic_binding::is_empty): New.
	(binding_map::remove_overlapping_bindings): New decl.
	(binding_map::get_overlapping_bindings): New decl.
	(binding_cluster::validate): New decl.
	(binding_cluster::bind): Drop enum binding_kind.
	(binding_cluster::fill_region): New decl.
	(binding_cluster::get_binding): Drop enum binding_kind.
	(binding_cluster::get_binding_recursive): Likewise.
	(binding_cluster::get_overlapping_bindings): Delete.
	(store::validate): New decl.
	(store::set_value): Drop enum binding_kind.
	(store::fill_region): New decl.
	(store_manager::get_concrete_binding): Drop enum binding_kind.
	(store_manager::get_symbolic_binding): Likewise.
	* svalue.cc (svalue::cmp_ptr): Handle SK_REPEATED and
	SK_BITS_WITHIN.
	(svalue::extract_bit_range): New.
	(svalue::maybe_fold_bits_within): New.
	(constant_svalue::maybe_fold_bits_within): New.
	(unknown_svalue::maybe_fold_bits_within): New.
	(unaryop_svalue::maybe_fold_bits_within): New.
	(repeated_svalue::repeated_svalue): New.
	(repeated_svalue::dump_to_pp): New.
	(repeated_svalue::accept): New.
	(repeated_svalue::all_zeroes_p): New.
	(repeated_svalue::maybe_fold_bits_within): New.
	(bits_within_svalue::bits_within_svalue): New.
	(bits_within_svalue::dump_to_pp): New.
	(bits_within_svalue::maybe_fold_bits_within): New.
	(bits_within_svalue::accept): New.
	(bits_within_svalue::implicitly_live_p): New.
	(compound_svalue::maybe_fold_bits_within): New.
	* svalue.h (enum svalue_kind): Add SK_REPEATED and SK_BITS_WITHIN.
	(svalue::dyn_cast_repeated_svalue): New.
	(svalue::dyn_cast_bits_within_svalue): New.
	(svalue::extract_bit_range): New decl.
	(svalue::maybe_fold_bits_within): New vfunc decl.
	(region_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(region_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<region_svalue::key_t>::empty_zero_p): Make false.
	(constant_svalue::maybe_fold_bits_within): New.
	(unknown_svalue::maybe_fold_bits_within): New.
	(poisoned_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(poisoned_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<poisoned_svalue::key_t>::empty_zero_p): Make
	false.
	(setjmp_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(setjmp_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<setjmp_svalue::key_t>::empty_zero_p): Make
	false.
	(unaryop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(unaryop_svalue::key_t::is_empty): Likewise.
	(unaryop_svalue::maybe_fold_bits_within): New.
	(default_hash_traits<unaryop_svalue::key_t>::empty_zero_p): Make
	false.
	(binop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(binop_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<binop_svalue::key_t>::empty_zero_p): Make
	false.
	(sub_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(sub_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<sub_svalue::key_t>::empty_zero_p): Make
	false.
	(class repeated_svalue): New.
	(is_a_helper <const repeated_svalue *>::test): New.
	(struct default_hash_traits<repeated_svalue::key_t>): New.
	(class bits_within_svalue): New.
	(is_a_helper <const bits_within_svalue *>::test): New.
	(struct default_hash_traits<bits_within_svalue::key_t>): New.
	(widening_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(widening_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<widening_svalue::key_t>::empty_zero_p): Make
	false.
	(compound_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(compound_svalue::key_t::is_empty): Likewise.
	(compound_svalue::maybe_fold_bits_within): New.
	(default_hash_traits<compound_svalue::key_t>::empty_zero_p): Make
	false.

gcc/testsuite/ChangeLog:
	PR analyzer/95006
	* gcc.dg/analyzer/clobbers-1.c: New test.
	* gcc.dg/analyzer/clobbers-2.c: New test.
	* gcc.dg/analyzer/data-model-1.c (test_26): Mark xfail as fixed.
	(test_28): Likewise.
	(test_52): Likewise.  Add coverage for end of buffer.
	* gcc.dg/analyzer/explode-1.c: Add leak warning.
	* gcc.dg/analyzer/memset-1.c (test_3): Mark xfail as fixed.
	(test_4): Use char.  Mark xfail as fixed.
	(test_6b): New.
	(test_7): Mark xfail as fixed.  Add coverage for start of buffer.
	(test_8): New.
	(test_9): New.
	* gcc.dg/analyzer/memset-CVE-2017-18549-1.c: New test.
	* gcc.dg/analyzer/symbolic-8.c: New test.

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

7 files changed, 399 insertions, 33 deletions

diff --git a/gcc/testsuite/gcc.dg/analyzer/clobbers-1.c b/gcc/testsuite/gcc.dg/analyzer/clobbers-1.c
new file mode 100644
index 0000000..824dbd4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/clobbers-1.c
@@ -0,0 +1,98 @@
+#include "analyzer-decls.h"
+
+struct foo
+{
+  int i;
+  int j;
+};
+
+struct coord
+{
+  int x;
+  int y;
+  int z;
+};
+
+struct foo g;
+
+void test_1 (void)
+{
+  g.i = 42;
+  if (g.j)
+    __analyzer_eval (g.j); /* { dg-warning "TRUE" } */
+  else
+    __analyzer_eval (g.j); /* { dg-warning "FALSE" } */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void test_2 (void)
+{
+  struct foo f;
+  f.i = 42;
+  if (f.j)
+    __analyzer_eval (f.j); /* { dg-warning "TRUE" } */
+  else
+    __analyzer_eval (f.j); /* { dg-warning "FALSE" } */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void test_3 (struct foo *p)
+{
+  struct foo f = *p;
+  f.i = 42;
+  if (f.j)
+    __analyzer_eval (f.j); /* { dg-warning "TRUE" } */
+  else
+    __analyzer_eval (f.j); /* { dg-warning "FALSE" } */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void test_4 (struct coord *p)
+{
+  struct coord f = *p;
+  f.x = 42;
+  __analyzer_eval (f.y == p->y); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.z == p->z); /* { dg-warning "TRUE" } */
+}
+
+struct s5
+{
+  char arr[8];
+};
+
+void test_5 (struct s5 *p)
+{
+  struct s5 f = *p;
+  f.arr[3] = 42;
+  __analyzer_eval (f.arr[0] == p->arr[0]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[1] == p->arr[1]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[2] == p->arr[2]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[3] == 42); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[4] == p->arr[4]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[5] == p->arr[5]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[6] == p->arr[6]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[7] == p->arr[7]); /* { dg-warning "TRUE" } */
+}
+
+struct s6
+{
+  int before; /* Give "arr" a nonzero offset.  */
+  struct foo arr[4];
+  int after;
+};
+
+void test_6 (struct s6 *p, struct foo *q)
+{
+  struct s6 f = *p;
+  f.arr[1] = *q;
+  __analyzer_eval (f.before == p->before); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[0].i == p->arr[0].i); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[0].j == p->arr[0].j); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[1].i == q->i); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[1].j == q->j); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[2].i == p->arr[2].i); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[2].j == p->arr[2].j); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[3].i == p->arr[3].i); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.arr[3].j == p->arr[3].j); /* { dg-warning "TRUE" } */
+  __analyzer_eval (f.after == p->after); /* { dg-warning "TRUE" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/clobbers-2.c b/gcc/testsuite/gcc.dg/analyzer/clobbers-2.c
new file mode 100644
index 0000000..9a88349
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/clobbers-2.c
@@ -0,0 +1,72 @@
+#include "analyzer-decls.h"
+
+typedef __SIZE_TYPE__ size_t;
+extern void bzero (void *s, size_t n);
+extern void *memset(void *s, int c, size_t n);
+
+void test_1 (void)
+{
+  char arr[16];
+  bzero (arr, sizeof (arr));
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[7] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[8] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[9] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+  /* Clobber in the middle (with prefix and suffix).  */
+  arr[8] = 42;
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[7] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[8] == 0); /* { dg-warning "FALSE" } */
+  __analyzer_eval (arr[8] == 42); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[9] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+}
+
+void test_2 (void)
+{
+  char arr[16];
+  bzero (arr, sizeof (arr));
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[1] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+  /* Clobber at the front (suffix, but no prefix).  */
+  arr[0] = 42;
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "FALSE" } */
+  __analyzer_eval (arr[0] == 42); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[1] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+}
+
+void test_3 (void)
+{
+  char arr[16];
+  bzero (arr, sizeof (arr));
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[14] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+  /* Clobber at the end (prefix, but no suffix).  */
+  arr[15] = 42;
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[14] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "FALSE" } */
+  __analyzer_eval (arr[15] == 42); /* { dg-warning "TRUE" } */
+}
+
+void test_4 (void)
+{
+  char arr[16];
+  bzero (arr, sizeof (arr));
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+  /* Exact overlap, no prefix or suffix.  */
+  memset (arr, 1, 16);
+  __analyzer_eval (arr[0] == 0); /* { dg-warning "FALSE" } */
+  __analyzer_eval (arr[15] == 0); /* { dg-warning "FALSE" } */
+  __analyzer_eval (arr[0] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (arr[15] == 1); /* { dg-warning "TRUE" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-1.c b/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
index 4a62a0e..34932da 100644
--- a/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
@@ -503,9 +503,7 @@ void test_26 (struct coord *p, struct coord *q)
      the dest value.  */
   *p = *q;
   __analyzer_eval (p->x); /* { dg-warning "UNKNOWN" } */
-  __analyzer_eval (p->y == 17); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
-  /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
-  // TODO(xfail): should have been overwritten with q->y
+  __analyzer_eval (p->y == 17); /* { dg-warning "TRUE" } */
 
   __analyzer_eval (q->x); /* { dg-warning "UNKNOWN" } */
   __analyzer_eval (q->y == 17); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
@@ -522,19 +520,11 @@ void test_27 (struct coord *p)
 void test_28 (struct coord *p)
 {
   memset (p, 0, sizeof (struct coord) * 10);
-  __analyzer_eval (p[0].x == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
-  /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
-  // TODO(xfail):
-  __analyzer_eval (p[0].y == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
-  /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
-  // TODO(xfail):
+  __analyzer_eval (p[0].x == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (p[0].y == 0); /* { dg-warning "TRUE" } */
 
-  __analyzer_eval (p[9].x == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
-  /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
-  // TODO(xfail):
-  __analyzer_eval (p[9].y == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
-  /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
-  // TODO(xfail):
+  __analyzer_eval (p[9].x == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (p[9].y == 0); /* { dg-warning "TRUE" } */
 
   __analyzer_eval (p[10].x == 0); /* { dg-warning "UNKNOWN" } */
   __analyzer_eval (p[10].y == 0); /* { dg-warning "UNKNOWN" } */
@@ -1035,8 +1025,8 @@ void test_52 (struct big b)
 {
   struct big d;
   memcpy (&d, &b, sizeof (struct big));
-  __analyzer_eval (b.ia[0] == d.ia[0]); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
-  /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+  __analyzer_eval (b.ia[0] == d.ia[0]); /* { dg-warning "TRUE" } */
+  __analyzer_eval (b.ia[1023] == d.ia[1023]); /* { dg-warning "TRUE" } */
 }
 
 void test_53 (const char *msg)
diff --git a/gcc/testsuite/gcc.dg/analyzer/explode-1.c b/gcc/testsuite/gcc.dg/analyzer/explode-1.c
index 6b62e8e..f48408e 100644
--- a/gcc/testsuite/gcc.dg/analyzer/explode-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/explode-1.c
@@ -12,7 +12,7 @@ void test (void)
 {
   void *p0, *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8;
   void **pp;
-  while (get ())
+  while (get ()) /* { dg-warning "leak" } */
     {
       switch (get ())
 	{
diff --git a/gcc/testsuite/gcc.dg/analyzer/memset-1.c b/gcc/testsuite/gcc.dg/analyzer/memset-1.c
index 5748aa1..94c5a1b 100644
--- a/gcc/testsuite/gcc.dg/analyzer/memset-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/memset-1.c
@@ -36,22 +36,16 @@ void test_3 (int val)
 {
   char buf[256];
   memset (buf, 'A', 256);
-  /* We currently merely mark such regions as "unknown", so querying
-     values within them yields UNKNOWN when ideally it would be TRUE.  */
-  __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
-  /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
+  __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" } */
 }
 
 /* A "memset" with unknown value.  */
 
-void test_4 (int val)
+void test_4 (char val)
 {
   char buf[256];
   memset (buf, val, 256);
-  /* We currently merely mark such regions as "unknown", so querying
-     values within them yields UNKNOWN when ideally it would be TRUE.  */
-  __analyzer_eval (buf[42] == (char)val); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
-  /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
+  __analyzer_eval (buf[42] == (char)val); /* { dg-warning "TRUE" } */
 }
 
 /* A "memset" with unknown num bytes.  */
@@ -98,6 +92,14 @@ void test_6 (int val)
   __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" } */  
 }
 
+void test_6b (int val)
+{
+  char buf[256];
+  memset (buf, 'A', sizeof (buf));
+  memset (buf, 'B', get_zero ());
+  __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" } */  
+}
+
 /* A "memset" of known size that's not the full buffer.  */
 
 void test_7 (void)
@@ -105,10 +107,96 @@ void test_7 (void)
   char buf[256];
   buf[128] = 'A';
   memset (buf, 0, 128);
-  /* We currently merely mark the whole region as "unknown", so querying
-     values within them yields UNKNOWN.  */
-  __analyzer_eval (buf[127] == '\0'); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
-  /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
-  __analyzer_eval (buf[128] == 'A'); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
-  /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
+  __analyzer_eval (buf[0] == '\0'); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[127] == '\0'); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[128] == 'A'); /* { dg-warning "TRUE" } */
+}
+
+void test_8 (void)
+{
+  char buf[20];
+  memset (buf + 0, 0, 1);
+  memset (buf + 1, 1, 1);
+  memset (buf + 2, 2, 1);
+  memset (buf + 3, 3, 1);
+  memset (buf + 4, 4, 2);
+  memset (buf + 6, 6, 2);
+  memset (buf + 8, 8, 4);
+  memset (buf + 12, 12, 8);
+  __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[2] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[3] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[4] == 4); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[5] == 4); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[6] == 6); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[7] == 6); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[8] == 8); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[9] == 8); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[10] == 8); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[11] == 8); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[12] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[13] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[14] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[15] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[16] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[17] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[18] == 12); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[19] == 12); /* { dg-warning "TRUE" } */
+}
+
+/* Various overlapping memset calls with different sizes and values.  */
+
+void test_9 (void)
+{
+  char buf[8];
+  memset (buf, 0, 8);
+  __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[1] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[2] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[3] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[4] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[5] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[6] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+  memset (buf + 1, 1, 4);  
+  __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[2] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[3] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[4] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[5] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[6] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+  memset (buf + 2, 2, 4);  
+  __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[2] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[3] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[4] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[5] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[6] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+  memset (buf + 4, 3, 3);  
+  __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[2] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[3] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[4] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[5] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[6] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+  memset (buf + 0, 4, 3);  
+  __analyzer_eval (buf[0] == 4); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[1] == 4); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[2] == 4); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[3] == 2); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[4] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[5] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[6] == 3); /* { dg-warning "TRUE" } */
+  __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
 }
diff --git a/gcc/testsuite/gcc.dg/analyzer/memset-CVE-2017-18549-1.c b/gcc/testsuite/gcc.dg/analyzer/memset-CVE-2017-18549-1.c
new file mode 100644
index 0000000..9dd1139
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/memset-CVE-2017-18549-1.c
@@ -0,0 +1,107 @@
+/* This is a very simplified version of CVE-2017-18549,
+   a use of uninitialized padding values affecting the Linux kernel
+   (and thus GPLv2).
+
+   It was fixed by e.g. 342ffc26693b528648bdc9377e51e4f2450b4860 on linux-4.13.y
+   in linux-stable.  */
+
+#include "analyzer-decls.h"
+#include <string.h>
+
+typedef unsigned int __u32;
+typedef unsigned int u32;
+typedef unsigned char u8;
+
+/* Adapted from include/uapi/linux/types.h  */
+
+#define __bitwise
+typedef __u32 __bitwise __le32;
+
+/* Adapted from drivers/scsi/aacraid/aacraid.h  */
+
+#define		AAC_SENSE_BUFFERSIZE	 30
+
+struct aac_srb_reply
+{
+	__le32		status;
+	__le32		srb_status;
+	__le32		scsi_status;
+	__le32		data_xfer_length;
+	__le32		sense_data_size;
+	u8		sense_data[AAC_SENSE_BUFFERSIZE];
+
+	/* Manually added to help verify the fix.  */
+	u8 padding[2];
+};
+
+#define		ST_OK		0
+#define SRB_STATUS_SUCCESS                  0x01
+
+/* Adapted from drivers/scsi/aacraid/commctrl.c  */
+
+static int aac_send_raw_srb(/* [...snip...] */)
+{
+	u32 byte_count = 0;
+
+	/* [...snip...] */
+
+	struct aac_srb_reply reply;
+
+	reply.status = ST_OK;
+
+	/* [...snip...] */
+
+	reply.srb_status = SRB_STATUS_SUCCESS;
+	reply.scsi_status = 0;
+	reply.data_xfer_length = byte_count;
+	reply.sense_data_size = 0;
+	memset(reply.sense_data, 0, AAC_SENSE_BUFFERSIZE);
+
+	/* [...snip...] */
+
+	__analyzer_eval (reply.status == ST_OK); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.srb_status == SRB_STATUS_SUCCESS); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.scsi_status == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.data_xfer_length == byte_count); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.sense_data_size == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.sense_data[0] == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.sense_data[AAC_SENSE_BUFFERSIZE - 1] == 0); /* { dg-warning "TRUE" } */
+	/* TODO: the following should be detected as uninitialized, when
+	   that diagnostic is reimplemented.  */
+	__analyzer_eval (reply.padding[0] == 0); /* { dg-warning "UNKNOWN" } */
+	__analyzer_eval (reply.padding[1] == 0); /* { dg-warning "UNKNOWN" } */
+}
+
+static int aac_send_raw_srb_fixed(/* [...snip...] */)
+{
+	u32 byte_count = 0;
+
+	/* [...snip...] */
+
+	struct aac_srb_reply reply;
+
+	/* This is the fix.  */
+	memset(&reply, 0, sizeof(reply));
+
+	reply.status = ST_OK;
+
+	/* [...snip...] */
+
+	reply.srb_status = SRB_STATUS_SUCCESS;
+	reply.scsi_status = 0;
+	reply.data_xfer_length = byte_count;
+	reply.sense_data_size = 0;
+	memset(reply.sense_data, 0, AAC_SENSE_BUFFERSIZE);
+
+	/* [...snip...] */
+
+	__analyzer_eval (reply.status == ST_OK); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.srb_status == SRB_STATUS_SUCCESS); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.scsi_status == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.data_xfer_length == byte_count); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.sense_data_size == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.sense_data[0] == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.sense_data[AAC_SENSE_BUFFERSIZE - 1] == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.padding[0] == 0); /* { dg-warning "TRUE" } */
+	__analyzer_eval (reply.padding[1] == 0); /* { dg-warning "TRUE" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/symbolic-8.c b/gcc/testsuite/gcc.dg/analyzer/symbolic-8.c
new file mode 100644
index 0000000..f9c3596
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/symbolic-8.c
@@ -0,0 +1,11 @@
+/* Merger where "arr" has two different symbolic bindings.  */
+
+void test (int i, int j, int flag)
+{
+  int arr[16];
+
+  if (flag)
+    arr[i] = 42;
+  else
+    arr[j] = 17;
+}