analyzer: fix ICEs due to sloppy types in bounds-checking [PR110902,PR110928,PR111305,PR111441]

Various analyzer ICEs in our bugzilla relate to sloppy use of types
within bounds-checking.

The bounds-checking code works by comparing symbolic *bit* offsets, and
we don't have a good user-facing type that can represent such an offset
(ptrdiff_type_node is for *byte* offsets).

ana::svalue doesn't enforce valid combinations of types for things like
binary operations.  When I added the access diagrams for GCC 14, this
could lead to attempts to generate trees for such svalues, leading to
trees with invalid combinations of types (e.g. PLUS_EXPR or MULT_EXPR of
incompatible types), leading to ICEs inside the tree folding logic.

I tried two approaches to fixing this.

My first approach was to fix the type-handling throughout the
bounds-checking code to use correct types, using size_type_node for
sizes, ptrdiff_type_node for byte offsets, and trying ptrdiff_type_node
for bit offsets.  I implemented this, and it fixed the crashes, but
unfortunately it led to:
(a) numerous false negatives from the bounds-checking code, due to it
becoming unable to be sure that the accessed offset was beyond the valid
bounds, due to the expressions involved gaining complicated sets of
nested casts.
(b) ugly access diagrams full of nested casts (for capacities, gap
measurements, etc)

So my second approach, implemented in this patch, is to accept that we
don't have a tree type for representing bit offsets.  The patch
represents bit offsets using "typeless" symbolic values i.e. ones for
which get_type () is NULL_TREE, and implements enough support for basic
arithemetic as if these are mathematical integers (albeit ones for which
concrete values within an expression must fit within a signed wide int).
Such values can't be converted to tree, so the patch avoids such
conversions, instead implementing a new svalue::maybe_print_for_user for
printing them to a pretty_printer.  The patch uses ptrdiff_type_node for
byte offsets.

Doing so fixes the crashes, whilst appearing to preserve the behavior of
-Wanalyzer-out-of-bounds in my testing.

gcc/analyzer/ChangeLog:
	PR analyzer/110902
	PR analyzer/110928
	PR analyzer/111305
	PR analyzer/111441
	* access-diagram.cc: Include "analyzer/analyzer-selftests.h".
	(get_access_size_str): Reimplement for conversion of
	implmementation of bit_size_expr from tree to const svalue &.  Use
	svalue::maybe_print_for_user rather than tree printing routines.
	(remove_ssa_names): Make non-static.
	(bit_size_expr::get_formatted_str): Rename to...
	(bit_size_expr::maybe_get_formatted_str): ...this, adding "model"
	param and converting return type to a unique_ptr.  Update for
	conversion of implementation of bit_size_expr from tree to
	const svalue &.  Use svalue::maybe_print_for_user rather than tree
	printing routines.
	(bit_size_expr::print): Rename to...
	(bit_size_expr::maybe_print_for_user): ...this, adding "model"
	param and converting return type to bool.  Update for
	conversion of implementation of bit_size_expr from tree to
	const svalue &.  Use svalue::maybe_print_for_user rather than tree
	printing routines.
	(bit_size_expr::maybe_get_as_bytes): Add "mgr" param and convert
	return type from tree to const svalue *; reimplement.
	(access_range::access_range): Call strip_types when on region_offset
	intializations.
	(access_range::get_size): Update for conversion of implementation
	of bit_size_expr from tree to const svalue &.
	(access_operation::get_valid_bits): Pass manager to access_range
	ctor.
	(access_operation::maybe_get_invalid_before_bits): Likewise.
	(access_operation::maybe_get_invalid_after_bits): Likewise.
	(boundaries::add): Likewise.
	(bit_to_table_map::populate): Add "mgr" param and pass it to
	access_range ctor.
	(access_diagram_impl::access_diagram_impl): Pass manager to
	bit_to_table_map::populate.
	(access_diagram_impl::maybe_add_gap): Use svalue rather than tree
	for symbolic bit offsets.  Port to new bit_size_expr
	representation.
	(access_diagram_impl::add_valid_vs_invalid_ruler): Port to new
	bit_size_expr representation.
	(selftest::assert_eq_typeless_integer): New.
	(ASSERT_EQ_TYPELESS_INTEGER): New.
	(selftest::test_bit_size_expr_to_bytes): New.
	(selftest::analyzer_access_diagram_cc_tests): New.
	* access-diagram.h (class bit_size_expr): Reimplement, converting
	implementation from tree to const svalue &.
	(access_range::access_range): Add "mgr" param.  Call strip_types
	on region_offset initializations.
	(access_range::get_size): Update decl for reimplementation.
	* analyzer-selftests.cc (selftest::run_analyzer_selftests): Call
	selftest::analyzer_access_diagram_cc_tests.
	* analyzer-selftests.h
	(selftest::analyzer_checker_script_cc_tests): Delete this stray
	typo.
	(selftest::analyzer_access_diagram_cc_tests): New decl.
	* analyzer.h (print_expr_for_user): New decl.
	(calc_symbolic_bit_offset): Update decl for reimplementation.
	(strip_types): New decls.
	(remove_ssa_names): New decl.
	* bounds-checking.cc (strip_types): New.
	(region_model::check_symbolic_bounds): Use typeless svalues.
	* region-model-manager.cc
	(region_model_manager::get_or_create_constant_svalue): Add "type"
	param.  Add overload with old signature.
	(region_model_manager::get_or_create_int_cst): Support type being
	NULL_TREE.
	(region_model_manager::maybe_fold_unaryop): Gracefully reject folding
	of casts to NULL_TREE type.
	(get_code_for_cast): Use NOP_EXPR for "casting" svalues to
	NULL_TREE type.
	(region_model_manager::get_or_create_cast): Support "casting"
	svalues to NULL_TREE type.
	(region_model_manager::maybe_fold_binop): Don't crash on inputs
	with NULL_TREE type.  Handle folding of binops on constants with
	NULL_TREE type.  Add missing cast from PR analyzer/110902.
	Support enough folding of other ops on NULL_TREE type to support
	bounds checking.
	(region_model_manager::get_or_create_const_fn_result_svalue):
	Remove assertion that type is nonnull.
	* region-model-manager.h
	(region_model_manager::get_or_create_constant_svalue): Add
	overloaded decl taking a type.
	(region_model_manager::maybe_fold_binop): Make public.
	(region_model_manager::constants_map_t): Use
	constant_svalue::key_t for the key, rather than just tree.
	* region-model.cc (print_expr_for_user): New.
	(selftest::test_array_2): Handle casts.
	* region.cc (region_offset::calc_symbolic_bit_offset): Return
	const svalue & rather than tree, and reimplement accordingly.
	(region::calc_offset): Use ptrdiff_type_node for types of byte
	offsets.
	(region::maybe_print_for_user): New.
	(element_region::get_relative_symbolic_offset): Use NULL_TREE for
	types of bit offsets.
	(offset_region::get_bit_offset): Likewise.
	(sized_region::get_bit_size_sval): Likewise for bit sizes.
	* region.h (region::maybe_print_for_user): New decl.
	* svalue.cc (class auto_add_parens): New.
	(svalue::maybe_print_for_user): New.
	(svalue::cmp_ptr): Support typeless constant svalues.
	(tristate_from_boolean_tree_node): New, taken from...
	(constant_svalue::eval_condition): ...here.  Handle comparison of
	typeless integer svalue constants.
	* svalue.h (svalue::maybe_print_for_user): New decl.
	(class constant_svalue): Support the type of the svalue being
	NULL_TREE.
	(struct default_hash_traits<constant_svalue::key_t>): New.

gcc/ChangeLog:
	PR analyzer/110902
	PR analyzer/110928
	PR analyzer/111305
	PR analyzer/111441
	* selftest.h (ASSERT_NE_AT): New macro.

gcc/testsuite/ChangeLog:
	PR analyzer/110902
	PR analyzer/110928
	PR analyzer/111305
	PR analyzer/111441
	* c-c++-common/analyzer/out-of-bounds-const-fn.c: New test.
	* c-c++-common/analyzer/out-of-bounds-diagram-11.c: Update
	expected diagram output.
	* c-c++-common/analyzer/out-of-bounds-diagram-pr110928.c: New test.
	* c-c++-common/analyzer/out-of-bounds-diagram-pr111305.c: New test.
	* c-c++-common/analyzer/out-of-bounds-diagram-pr111441.c: New test.

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

5 files changed, 130 insertions, 6 deletions

diff --git a/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-const-fn.c b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-const-fn.c
new file mode 100644
index 0000000..7cb8b5f
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-const-fn.c
@@ -0,0 +1,48 @@
+/* Reduced from analyzer ICE seen with git-2.39.0's pack-bitmap.c
+   when bounds-checking the result of __builtin_ctzll.  */
+
+#include <stdint.h>
+#include <stddef.h>
+
+typedef uint64_t eword_t;
+struct ewah_bitmap;
+struct ewah_iterator
+{
+  /* [...] */
+};
+struct bitmap;
+
+void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent);
+int ewah_iterator_next(eword_t *next, struct ewah_iterator *it);
+void bitmap_set(struct bitmap *self, size_t pos);
+
+int rebuild_bitmap(const uint32_t *reposition,
+     struct ewah_bitmap *source,
+     struct bitmap *dest)
+{
+ uint32_t pos = 0;
+ struct ewah_iterator it;
+ eword_t word;
+
+ ewah_iterator_init(&it, source);
+
+ while (ewah_iterator_next(&word, &it)) {
+  uint32_t offset, bit_pos;
+
+  for (offset = 0; offset < (sizeof(eword_t) * 8); ++offset) {
+   if ((word >> offset) == 0)
+    break;
+
+   offset += __builtin_ctzll(word >> offset);
+
+   bit_pos = reposition[pos + offset];
+   if (bit_pos > 0)
+    bitmap_set(dest, bit_pos - 1);
+   else
+    return -1;
+  }
+
+  pos += (sizeof(eword_t) * 8);
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-11.c b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-11.c
index d68ac8f..63ae083 100644
--- a/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-11.c
+++ b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-11.c
@@ -30,9 +30,12 @@ void test6 (size_t size)
                   │                          │       ╭──────────┴─────────╮
                   │                          │       │over-read of 4 bytes│
                   │                          │       ╰────────────────────╯
-      ╭───────────┴──────────╮      ╭────────┴────────╮
-      │size: 'size * 4' bytes│      │'size * 12' bytes│
-      ╰──────────────────────╯      ╰─────────────────╯
+                  │         ╭────────────────┴───────────────╮
+                  │         │'(size * 16) - (size * 4)' bytes│
+                  │         ╰────────────────────────────────╯
+      ╭───────────┴──────────╮
+      │size: 'size * 4' bytes│
+      ╰──────────────────────╯
 
    { dg-end-multiline-output "" } */
 
@@ -55,9 +58,9 @@ void test7 (size_t size)
   └──────────────────────────────────────────────────┘└──────────────────┘
   ├────────────────────────┬─────────────────────────┤├────────┬─────────┤
                            │                                   │
-           ╭───────────────┴──────────────╮          ╭─────────┴────────╮
-           │capacity: 'size * 4 + 3' bytes│          │overflow of 1 byte│
-           ╰──────────────────────────────╯          ╰──────────────────╯
+          ╭────────────────┴───────────────╮         ╭─────────┴────────╮
+          │capacity: '(size * 4) + 3' bytes│         │overflow of 1 byte│
+          ╰────────────────────────────────╯         ╰──────────────────╯
 
    { dg-end-multiline-output "" } */
 
diff --git a/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr110928.c b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr110928.c
new file mode 100644
index 0000000..a0164c9
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr110928.c
@@ -0,0 +1,28 @@
+/* Verify we don't ICE generating out-of-bounds diagram.  */
+
+/* { dg-additional-options "-O0 -fdiagnostics-text-art-charset=unicode" } */
+
+#include <stdio.h>
+#include <stdint.h>
+
+uint64_t d(int32_t h) {
+  uint64_t j[2][6];
+  int32_t k;
+  for (k = 1;;) {
+    printf("FLAG\n");
+    if (h < 106 || j[k][h]) /* { dg-warning "stack-based buffer over-read" } */
+      return 0;
+  }
+}
+int16_t e() {
+  int32_t f[5];
+  for (f[2] = 3; f[2]; --f[2])
+    d(0);
+}
+
+int main() { e(); }
+
+/* We don't care about the exact diagram, just that we don't ICE.  */
+
+/* { dg-allow-blank-lines-in-output 1 } */
+/* { dg-prune-output ".*" } */
diff --git a/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr111305.c b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr111305.c
new file mode 100644
index 0000000..9cb37a5
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr111305.c
@@ -0,0 +1,26 @@
+/* Verify we don't ICE generating out-of-bounds diagram.  */
+
+/* { dg-additional-options "-O0 -fdiagnostics-text-art-charset=unicode" } */
+
+#include <stdio.h>
+#include <stdint.h>
+
+struct a {
+  uint32_t b;
+};
+union c {
+  int8_t b;
+};
+
+int32_t *d( int32_t *j, int32_t k, struct a l) {
+  int64_t m[1]= {0};
+  for (l.b = 0; l.b <= 0; l.b++) {
+    printf("FLAG\n");
+    l.b == 12 && m[l.b]; /* { dg-bogus "stack-based buffer over-read" } */
+  }
+}
+
+/* We don't care about the exact diagram, just that we don't ICE.  */
+
+/* { dg-allow-blank-lines-in-output 1 } */
+/* { dg-prune-output ".*" } */
diff --git a/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr111441.c b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr111441.c
new file mode 100644
index 0000000..df7c714
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/out-of-bounds-diagram-pr111441.c
@@ -0,0 +1,19 @@
+/* Verify we don't ICE generating out-of-bounds diagram.  */
+
+/* { dg-additional-options "-fdiagnostics-text-art-charset=unicode" } */
+
+#include "analyzer-decls.h"
+
+void f() {
+    int a[] = {3, 0, 3, 3, 0, 3, 40883};
+    for (int c = 6; c; c--) {
+        __analyzer_describe(0, a[c]);
+        90 > c || a[c]; /* { dg-bogus "stack-based buffer over-read" } */
+    }
+}
+int main() { f(); }
+
+/* We don't care about the exact diagram, just that we don't ICE.  */
+
+/* { dg-allow-blank-lines-in-output 1 } */
+/* { dg-prune-output ".*" } */