From 455f58ec50465aed9d92dc31d68708a05e499388 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 31 Jan 2020 09:20:38 -0500 Subject: [PATCH] analyzer: fix ICE with pointers between stack frames (PR 93438) PR analyzer/93438 reports an ICE when merging two region_models in which an older stack frame has a local pointing to a local in a more recent stack frame. stack older frame int *: "ow" --+ | newer frame | int: "pk" <---+ The root cause is that the state-merging code assumes that all frame regions in the merged model have already been created. stack_region::can_merge_p iterates through the frames, creating and populating each merged frame in turn, so when it attempts to populate the older frame, it attempts to reference the newer frame in the merged model, which doesn't exist yet. This patch reworks stack_region::can_merge_p to use a two-pass approach in which all frames in the merged model are created first, and then are all populated, fixing the bug. gcc/analyzer/ChangeLog: PR analyzer/93438 * region-model.cc (stack_region::can_merge_p): Split into a two pass approach, creating all stack regions first, then populating them. (selftest::test_state_merging): Add test coverage for (a) the case of self-merging a model in which a local in an older stack frame points to a local in a more recent stack frame (which previously would ICE), and (b) the case of self-merging a model in which a local points to a global (which previously worked OK). gcc/testsuite/ChangeLog: PR analyzer/93438 * gcc.dg/analyzer/torture/pr93438.c: New test. * gcc.dg/analyzer/torture/pr93438-2.c: New test. --- gcc/analyzer/ChangeLog | 12 ++ gcc/analyzer/region-model.cc | 115 +++++++++++++++--- gcc/testsuite/ChangeLog | 6 + .../gcc.dg/analyzer/torture/pr93438-2.c | 26 ++++ .../gcc.dg/analyzer/torture/pr93438.c | 13 ++ 5 files changed, 153 insertions(+), 19 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog index a46ee269f65..8806a775acb 100644 --- a/gcc/analyzer/ChangeLog +++ b/gcc/analyzer/ChangeLog @@ -1,3 +1,15 @@ +2020-01-31 David Malcolm + + PR analyzer/93438 + * region-model.cc (stack_region::can_merge_p): Split into a two + pass approach, creating all stack regions first, then populating + them. + (selftest::test_state_merging): Add test coverage for (a) the case + of self-merging a model in which a local in an older stack frame + points to a local in a more recent stack frame (which previously + would ICE), and (b) the case of self-merging a model in which a + local points to a global (which previously worked OK). + 2020-01-31 David Malcolm * analyzer.cc (is_named_call_p): Replace tests for fndecl being diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index b546114bfd5..f116c0ae7a2 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -2624,27 +2624,45 @@ stack_region::can_merge_p (const stack_region *stack_region_a, stack_region *merged_stack = merged_model->get_region (rid_merged_stack); - for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++) - { - region_id rid_a = stack_region_a->get_frame_rid (i); - frame_region *frame_a = merger->get_region_a (rid_a); + /* First, create all frames in the merged model, without populating them. + The merging code assumes that all frames in the merged model already exist, + so we have to do this first to handle the case in which a local in an + older frame points at a local in a more recent frame. */ + for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++) + { + region_id rid_a = stack_region_a->get_frame_rid (i); + frame_region *frame_a = merger->get_region_a (rid_a); - region_id rid_b = stack_region_b->get_frame_rid (i); - frame_region *frame_b = merger->get_region_b (rid_b); + region_id rid_b = stack_region_b->get_frame_rid (i); + frame_region *frame_b = merger->get_region_b (rid_b); - if (frame_a->get_function () != frame_b->get_function ()) - return false; - frame_region *merged_frame = new frame_region (rid_merged_stack, - frame_a->get_function (), - frame_a->get_depth ()); - region_id rid_merged_frame = merged_model->add_region (merged_frame); - merged_stack->push_frame (rid_merged_frame); - - if (!map_region::can_merge_p (frame_a, frame_b, - merged_frame, rid_merged_frame, - merger)) - return false; - } + if (frame_a->get_function () != frame_b->get_function ()) + return false; + + frame_region *merged_frame = new frame_region (rid_merged_stack, + frame_a->get_function (), + frame_a->get_depth ()); + region_id rid_merged_frame = merged_model->add_region (merged_frame); + merged_stack->push_frame (rid_merged_frame); + } + + /* Now populate the frames we created. */ + for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++) + { + region_id rid_a = stack_region_a->get_frame_rid (i); + frame_region *frame_a = merger->get_region_a (rid_a); + + region_id rid_b = stack_region_b->get_frame_rid (i); + frame_region *frame_b = merger->get_region_b (rid_b); + + region_id rid_merged_frame = merged_stack->get_frame_rid (i); + frame_region *merged_frame + = merged_model->get_region (rid_merged_frame); + if (!map_region::can_merge_p (frame_a, frame_b, + merged_frame, rid_merged_frame, + merger)) + return false; + } return true; } @@ -7721,6 +7739,11 @@ test_state_merging () integer_type_node); tree addr_of_a = build1 (ADDR_EXPR, ptr_type_node, a); + /* Param "q", a pointer. */ + tree q = build_decl (UNKNOWN_LOCATION, PARM_DECL, + get_identifier ("q"), + ptr_type_node); + { region_model model0; region_model model1; @@ -7991,6 +8014,60 @@ test_state_merging () region_model merged; ASSERT_TRUE (model0.can_merge_with_p (model1, &merged)); } + + /* Verify that we can merge a model in which a local in an older stack + frame points to a local in a more recent stack frame. */ + { + region_model model0; + model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); + region_id q_in_first_frame = model0.get_lvalue (q, NULL); + + /* Push a second frame. */ + region_id rid_2nd_frame + = model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); + + /* Have a pointer in the older frame point to a local in the + more recent frame. */ + svalue_id sid_ptr = model0.get_rvalue (addr_of_a, NULL); + model0.set_value (q_in_first_frame, sid_ptr, NULL); + + /* Verify that it's pointing at the newer frame. */ + region_id rid_pointee + = model0.get_svalue (sid_ptr)->dyn_cast_region_svalue ()->get_pointee (); + ASSERT_EQ (model0.get_region (rid_pointee)->get_parent (), rid_2nd_frame); + + model0.canonicalize (NULL); + + region_model model1 (model0); + ASSERT_EQ (model0, model1); + + /* They should be mergeable, and the result should be the same + (after canonicalization, at least). */ + region_model merged; + ASSERT_TRUE (model0.can_merge_with_p (model1, &merged)); + merged.canonicalize (NULL); + ASSERT_EQ (model0, merged); + } + + /* Verify that we can merge a model in which a local points to a global. */ + { + region_model model0; + model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); + model0.set_value (model0.get_lvalue (q, NULL), + model0.get_rvalue (addr_of_y, NULL), NULL); + + model0.canonicalize (NULL); + + region_model model1 (model0); + ASSERT_EQ (model0, model1); + + /* They should be mergeable, and the result should be the same + (after canonicalization, at least). */ + region_model merged; + ASSERT_TRUE (model0.can_merge_with_p (model1, &merged)); + merged.canonicalize (NULL); + ASSERT_EQ (model0, merged); + } } /* Verify that constraints are correctly merged when merging region_model diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index ae146020aa8..f8051b44085 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2020-01-31 David Malcolm + + PR analyzer/93438 + * gcc.dg/analyzer/torture/pr93438.c: New test. + * gcc.dg/analyzer/torture/pr93438-2.c: New test. + 2020-01-31 Jakub Jelinek PR rtl-optimization/91838 diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c new file mode 100644 index 00000000000..218dc78138b --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c @@ -0,0 +1,26 @@ +/* A non-recursive example of state-merger of a pointer + from an old stack frame to a local in a newer stack frame. */ + +int newer (int **ptr_to_ow, int flag); + +int +older (int flag) +{ + int *ow; + return newer (&ow, flag); +} + +int +newer (int **ptr_to_ow, int flag) +{ + int pk; + *ptr_to_ow = &pk; + + if (flag) + pk = 3; + else + pk = 4; + /* State merger. */ + + return pk; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c new file mode 100644 index 00000000000..3a23770a02c --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c @@ -0,0 +1,13 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ + +void +tw (int **la, int pk) +{ + int *ow = *la; + int jo = !!pk; + + if (jo == 0) + *la = &pk; + + tw (&ow, pk); +} -- 2.30.2