From 90f7c3007d58c5cb538d00351c038f3f2cfcaf67 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 6 Mar 2020 10:13:59 -0500 Subject: [PATCH] analyzer: improvements to region_model::get_representative_tree This patch extends region_model::get_representative_tree so that dumps are able to refer to string literals, which I've found useful in investigating a state-bloat issue. Doing so uncovered a bug in the handling of views I introduced in r10-7024-ge516294a1acb28aaaad44cfd583cc6a80354044e where the code was erroneously using TREE_TYPE on the view region's type, rather than just using its type, which the patch also fixes. gcc/analyzer/ChangeLog: * analyzer.h (class array_region): New forward decl. * program-state.cc (selftest::test_program_state_dumping_2): New. (selftest::analyzer_program_state_cc_tests): Call it. * region-model.cc (array_region::constant_from_key): New. (region_model::get_representative_tree): Handle region_svalue by generating an ADDR_EXPR. (region_model::get_representative_path_var): In view handling, remove erroneous TREE_TYPE when determining the type of the tree. Handle array regions and STRING_CST. (selftest::assert_dump_tree_eq): New. (ASSERT_DUMP_TREE_EQ): New macro. (selftest::test_get_representative_tree): New selftest. (selftest::analyzer_region_model_cc_tests): Call it. * region-model.h (region::dyn_cast_array_region): New vfunc. (array_region::dyn_cast_array_region): New vfunc implementation. (array_region::constant_from_key): New decl. gcc/testsuite/ChangeLog: * gcc.dg/analyzer/malloc-4.c: Update expected output of leak to reflect fix to region_model::get_representative_path_var, adding the missing "*" from the cast. --- gcc/analyzer/ChangeLog | 19 ++++++ gcc/analyzer/analyzer.h | 1 + gcc/analyzer/program-state.cc | 46 ++++++++++++++ gcc/analyzer/region-model.cc | 100 +++++++++++++++++++++++++++++-- gcc/analyzer/region-model.h | 3 + gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/analyzer/malloc-4.c | 2 +- 7 files changed, 172 insertions(+), 5 deletions(-) diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog index 84c619e..e51a1cd 100644 --- a/gcc/analyzer/ChangeLog +++ b/gcc/analyzer/ChangeLog @@ -1,5 +1,24 @@ 2020-03-06 David Malcolm + * analyzer.h (class array_region): New forward decl. + * program-state.cc (selftest::test_program_state_dumping_2): New. + (selftest::analyzer_program_state_cc_tests): Call it. + * region-model.cc (array_region::constant_from_key): New. + (region_model::get_representative_tree): Handle region_svalue by + generating an ADDR_EXPR. + (region_model::get_representative_path_var): In view handling, + remove erroneous TREE_TYPE when determining the type of the tree. + Handle array regions and STRING_CST. + (selftest::assert_dump_tree_eq): New. + (ASSERT_DUMP_TREE_EQ): New macro. + (selftest::test_get_representative_tree): New selftest. + (selftest::analyzer_region_model_cc_tests): Call it. + * region-model.h (region::dyn_cast_array_region): New vfunc. + (array_region::dyn_cast_array_region): New vfunc implementation. + (array_region::constant_from_key): New decl. + +2020-03-06 David Malcolm + * analyzer.h (dump_quoted_tree): New decl. * engine.cc (exploded_node::dump_dot): Pass region model to sm_state_map::print. diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h index 78d6009..8d0d169 100644 --- a/gcc/analyzer/analyzer.h +++ b/gcc/analyzer/analyzer.h @@ -43,6 +43,7 @@ class svalue; class setjmp_svalue; class region; class map_region; + class array_region; class symbolic_region; class region_model; class region_model_context; diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 804800f..24b6783 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -1467,6 +1467,51 @@ test_program_state_dumping () "rmodel: p: &r2 malloc: {sv1: unchecked (`p')}"); } +/* Verify that program_state::dump_to_pp works for string literals. */ + +static void +test_program_state_dumping_2 () +{ + /* Create a program_state for a global ptr "p" that points to + a string constant. */ + tree p = build_global_decl ("p", ptr_type_node); + + tree string_cst_ptr = build_string_literal (4, "foo"); + + auto_delete_vec checkers; + extrinsic_state ext_state (checkers); + + program_state s (ext_state); + region_model *model = s.m_region_model; + region_id p_rid = model->get_lvalue (p, NULL); + svalue_id str_sid = model->get_rvalue (string_cst_ptr, NULL); + model->set_value (p_rid, str_sid, NULL); + + ASSERT_DUMP_EQ + (s, ext_state, false, + "rmodel: r0: {kind: `root', parent: null, sval: null}\n" + "|-globals: r1: {kind: `globals', parent: r0, sval: null, map: {`p': r2}}\n" + "| `-`p': r2: {kind: `primitive', parent: r1, sval: sv3, type: `void *'}\n" + "| |: sval: sv3: {type: `void *', &r4}\n" + "| |: type: `void *'\n" + "`-r3: {kind: `array', parent: r0, sval: sv0, type: `const char[4]', array: {[0]: r4}}\n" + " |: sval: sv0: {type: `const char[4]', `\"foo\"'}\n" + " |: type: `const char[4]'\n" + " `-[0]: r4: {kind: `primitive', parent: r3, sval: null, type: `const char'}\n" + " |: type: `const char'\n" + "svalues:\n" + " sv0: {type: `const char[4]', `\"foo\"'}\n" + " sv1: {type: `int', `0'}\n" + " sv2: {type: `const char *', &r4}\n" + " sv3: {type: `void *', &r4}\n" + "constraint manager:\n" + " equiv classes:\n" + " constraints:\n"); + + ASSERT_DUMP_EQ (s, ext_state, true, + "rmodel: p: &\"foo\"[0]"); +} + /* Verify that program_states with identical sm-state can be merged, and that the merged program_state preserves the sm-state. */ @@ -1570,6 +1615,7 @@ analyzer_program_state_cc_tests () { test_sm_state_map (); test_program_state_dumping (); + test_program_state_dumping_2 (); test_program_state_merging (); test_program_state_merging_2 (); } diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index e7e517a..87980e7 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -2494,6 +2494,16 @@ array_region::key_from_constant (tree cst) return result; } +/* Convert array_region::key_t KEY into a tree constant. */ + +tree +array_region::constant_from_key (key_t key) +{ + tree array_type = get_type (); + tree index_type = TYPE_DOMAIN (array_type); + return build_int_cst (index_type, key); +} + /* class function_region : public map_region. */ /* Compare the fields of this function_region with OTHER, returning true @@ -5669,9 +5679,7 @@ region_model::add_new_malloc_region () return add_region (new symbolic_region (heap_rid, NULL_TREE, true)); } -/* Attempt to return a tree that represents SID, or return NULL_TREE. - Find the first region that stores the value (e.g. a local) and - generate a representative tree for it. */ +/* Attempt to return a tree that represents SID, or return NULL_TREE. */ tree region_model::get_representative_tree (svalue_id sid) const @@ -5679,6 +5687,8 @@ region_model::get_representative_tree (svalue_id sid) const if (sid.null_p ()) return NULL_TREE; + /* Find the first region that stores the value (e.g. a local) and + generate a representative tree for it. */ unsigned i; region *region; FOR_EACH_VEC_ELT (m_regions, i, region) @@ -5689,6 +5699,18 @@ region_model::get_representative_tree (svalue_id sid) const return pv.m_tree; } + /* Handle string literals and various other pointers. */ + svalue *sval = get_svalue (sid); + if (region_svalue *ptr_sval = sval->dyn_cast_region_svalue ()) + { + region_id rid = ptr_sval->get_pointee (); + path_var pv = get_representative_path_var (rid); + if (pv.m_tree) + return build1 (ADDR_EXPR, + TREE_TYPE (sval->get_type ()), + pv.m_tree); + } + return maybe_get_constant (sid); } @@ -5727,7 +5749,7 @@ region_model::get_representative_path_var (region_id rid) const path_var parent_pv = get_representative_path_var (parent_rid); if (parent_pv.m_tree && reg->get_type ()) return path_var (build1 (NOP_EXPR, - TREE_TYPE (reg->get_type ()), + reg->get_type (), parent_pv.m_tree), parent_pv.m_stack_depth); } @@ -5750,6 +5772,32 @@ region_model::get_representative_path_var (region_id rid) const } } + /* Handle elements within an array. */ + if (array_region *array_reg = parent_region->dyn_cast_array_region ()) + { + array_region::key_t key; + if (array_reg->get_key_for_child_region (rid, &key)) + { + path_var parent_pv = get_representative_path_var (parent_rid); + if (parent_pv.m_tree && reg->get_type ()) + { + tree index = array_reg->constant_from_key (key); + return path_var (build4 (ARRAY_REF, + reg->get_type (), + parent_pv.m_tree, index, + NULL_TREE, NULL_TREE), + parent_pv.m_stack_depth); + } + } + } + + /* Handle string literals. */ + svalue_id sid = reg->get_value_direct (); + if (svalue *sval = get_svalue (sid)) + if (tree cst = sval->maybe_get_constant ()) + if (TREE_CODE (cst) == STRING_CST) + return path_var (cst, 0); + return path_var (NULL_TREE, 0); } @@ -7273,6 +7321,25 @@ assert_condition (const location &loc, ASSERT_EQ_AT (loc, actual, expected); } +/* Implementation detail of ASSERT_DUMP_TREE_EQ. */ + +static void +assert_dump_tree_eq (const location &loc, tree t, const char *expected) +{ + auto_fix_quotes sentinel; + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + dump_tree (&pp, t); + ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); +} + +/* Assert that dump_tree (T) is EXPECTED. */ + +#define ASSERT_DUMP_TREE_EQ(T, EXPECTED) \ + SELFTEST_BEGIN_STMT \ + assert_dump_tree_eq ((SELFTEST_LOCATION), (T), (EXPECTED)); \ + SELFTEST_END_STMT + /* Implementation detail of ASSERT_DUMP_EQ. */ static void @@ -7321,6 +7388,30 @@ test_dump () ASSERT_DUMP_EQ (model, true, ""); } +/* Verify that region_model::get_representative_tree works as expected. */ + +static void +test_get_representative_tree () +{ + /* STRING_CST. */ + { + tree string_cst = build_string (4, "foo"); + region_model m; + svalue_id str_sid = m.get_rvalue (string_cst, NULL); + tree rep = m.get_representative_tree (str_sid); + ASSERT_EQ (rep, string_cst); + } + + /* String literal. */ + { + tree string_cst_ptr = build_string_literal (4, "foo"); + region_model m; + svalue_id str_sid = m.get_rvalue (string_cst_ptr, NULL); + tree rep = m.get_representative_tree (str_sid); + ASSERT_DUMP_TREE_EQ (rep, "&\"foo\"[0]"); + } +} + /* Verify that calling region_model::get_rvalue repeatedly on the same tree constant retrieves the same svalue_id. */ @@ -8372,6 +8463,7 @@ analyzer_region_model_cc_tests () { test_tree_cmp_on_constants (); test_dump (); + test_get_representative_tree (); test_unique_constants (); test_svalue_equality (); test_region_equality (); diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index c782e93..c1fe592 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -844,6 +844,7 @@ public: virtual enum region_kind get_kind () const = 0; virtual map_region *dyn_cast_map_region () { return NULL; } + virtual array_region *dyn_cast_array_region () { return NULL; } virtual const symbolic_region *dyn_cast_symbolic_region () const { return NULL; } @@ -1354,6 +1355,7 @@ public: /* region vfuncs. */ region *clone () const FINAL OVERRIDE; enum region_kind get_kind () const FINAL OVERRIDE { return RK_ARRAY; } + array_region *dyn_cast_array_region () { return this; } region_id get_element (region_model *model, region_id this_rid, @@ -1400,6 +1402,7 @@ public: void validate (const region_model &model) const FINAL OVERRIDE; static key_t key_from_constant (tree cst); + tree constant_from_key (key_t key); private: static int key_cmp (const void *, const void *); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 59c9988..358d1de 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2020-03-06 David Malcolm + + * gcc.dg/analyzer/malloc-4.c: Update expected output of leak to + reflect fix to region_model::get_representative_path_var, adding + the missing "*" from the cast. + 2020-03-06 Wilco Dijkstra * gcc.target/aarch64/fmla_intrinsic_1.c: Check for correct lane syntax. diff --git a/gcc/testsuite/gcc.dg/analyzer/malloc-4.c b/gcc/testsuite/gcc.dg/analyzer/malloc-4.c index 94d2825..c9c275a 100644 --- a/gcc/testsuite/gcc.dg/analyzer/malloc-4.c +++ b/gcc/testsuite/gcc.dg/analyzer/malloc-4.c @@ -17,4 +17,4 @@ void a5 (void) { struct bar *qb = NULL; hv (&qb); -} /* { dg-warning "leak of '\\(struct foo\\)qb'" } */ +} /* { dg-warning "leak of '\\(struct foo \\*\\)qb'" } */ -- 2.7.4