From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2209) id 101B13858D33; Wed, 1 Mar 2023 13:57:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 101B13858D33 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1677679020; bh=RZM1xETB7O15GQd493ALYscCrUeQUXRpyOWIKQKD1xE=; h=From:To:Subject:Date:From; b=R6J/v2lowVDQWL+kU6jOiTxOV+mFhU3Sy4VCp+q2OPEirrMPNwKem+noh+TkL47BW SgjwXTwlCMcjM0/iU6qhA9D6WQbCA30kfTkweo40twiC9GYn/CTwj+GzDf/rZ7O99Z ZuHfKcAfUsMBN1GLuIjzYGbzjLlvg4NELxntDYhw= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: David Malcolm To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-6393] analyzer: fix infinite recursion false +ves [PR108935] X-Act-Checkin: gcc X-Git-Author: David Malcolm X-Git-Refname: refs/heads/master X-Git-Oldrev: f769d22ab685671095525d09ef29eeeed0ae3cee X-Git-Newrev: 070523b9d4c6cfa69060255893006efaf39bf617 Message-Id: <20230301135700.101B13858D33@sourceware.org> Date: Wed, 1 Mar 2023 13:57:00 +0000 (GMT) List-Id: https://gcc.gnu.org/g:070523b9d4c6cfa69060255893006efaf39bf617 commit r13-6393-g070523b9d4c6cfa69060255893006efaf39bf617 Author: David Malcolm Date: Wed Mar 1 08:54:43 2023 -0500 analyzer: fix infinite recursion false +ves [PR108935] gcc/analyzer/ChangeLog: PR analyzer/108935 * infinite-recursion.cc (contains_unknown_p): New. (sufficiently_different_region_binding_p): New function, splitting out inner loop from... (sufficiently_different_p): ...here. Extend detection of unknown svalues to also include svalues that contain unknown. Treat changes in frames below the entry to the recursion as being sufficiently different to reject being an infinite recursion. gcc/testsuite/ChangeLog: PR analyzer/108935 * gcc.dg/analyzer/infinite-recursion-pr108935-1.c: New test. * gcc.dg/analyzer/infinite-recursion-pr108935-1a.c: New test. * gcc.dg/analyzer/infinite-recursion-pr108935-2.c: New test. Signed-off-by: David Malcolm Diff: --- gcc/analyzer/infinite-recursion.cc | 151 ++++++++++++++------- .../analyzer/infinite-recursion-pr108935-1.c | 17 +++ .../analyzer/infinite-recursion-pr108935-1a.c | 17 +++ .../analyzer/infinite-recursion-pr108935-2.c | 18 +++ 4 files changed, 152 insertions(+), 51 deletions(-) diff --git a/gcc/analyzer/infinite-recursion.cc b/gcc/analyzer/infinite-recursion.cc index 1886534313e..c262e391953 100644 --- a/gcc/analyzer/infinite-recursion.cc +++ b/gcc/analyzer/infinite-recursion.cc @@ -394,12 +394,108 @@ remap_enclosing_frame (const region *base_reg, } } +/* Return true iff SVAL is unknown, or contains an unknown svalue. */ + +static bool +contains_unknown_p (const svalue *sval) +{ + if (sval->get_kind () == SK_UNKNOWN) + return true; + if (const compound_svalue *compound_sval + = sval->dyn_cast_compound_svalue ()) + for (auto iter : *compound_sval) + if (iter.second->get_kind () == SK_UNKNOWN) + return true; + return false; +} + +/* Subroutine of sufficiently_different_p. Compare the store bindings + for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE. + + Return true if the state of NEW_ENTRY_ENODE is sufficiently different + from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is + being modified, and thus the recursion isn't infinite. + + Return false if the states for BASE_REG are effectively the same. */ + +static bool +sufficiently_different_region_binding_p (exploded_node *new_entry_enode, + exploded_node *prev_entry_enode, + const region *base_reg) +{ + /* Compare the stores of the two enodes. */ + const region_model &new_model + = *new_entry_enode->get_state ().m_region_model; + const region_model &prev_model + = *prev_entry_enode->get_state ().m_region_model; + + /* Get the value within the new frame. */ + const svalue *new_sval + = new_model.get_store_value (base_reg, NULL); + + /* If any part of the value is UNKNOWN (e.g. due to hitting + complexity limits) assume that it differs from the previous + value. */ + if (contains_unknown_p (new_sval)) + return true; + + /* Get the equivalent value within the old enode. */ + const svalue *prev_sval; + + if (const frame_region *enclosing_frame + = base_reg->maybe_get_frame_region ()) + { + /* We have a binding within a frame in the new entry enode. */ + + /* Consider changes in bindings below the original entry + to the recursion. */ + const int old_stack_depth = prev_entry_enode->get_stack_depth (); + if (enclosing_frame->get_stack_depth () < old_stack_depth) + prev_sval = prev_model.get_store_value (base_reg, NULL); + else + { + /* Ignore bindings within frames below the new entry node. */ + const int new_stack_depth = new_entry_enode->get_stack_depth (); + if (enclosing_frame->get_stack_depth () < new_stack_depth) + return false; + + /* We have a binding within the frame of the new entry node, + presumably a parameter. */ + + /* Get the value within the equivalent frame of + the old entrypoint; typically will be the initial_svalue + of the parameter. */ + const frame_region *equiv_prev_frame + = prev_model.get_current_frame (); + const region *equiv_prev_base_reg + = remap_enclosing_frame (base_reg, + enclosing_frame, + equiv_prev_frame, + new_model.get_manager ()); + prev_sval + = prev_model.get_store_value (equiv_prev_base_reg, NULL); + } + } + else + prev_sval = prev_model.get_store_value (base_reg, NULL); + + /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits) + assume that it will differ from any new value. */ + if (contains_unknown_p (prev_sval)) + return true; + + if (new_sval != prev_sval) + return true; + + return false; +} + /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE, both of which are entrypoints to the same function, where recursion has occurred. Return true if the state of NEW_ENTRY_ENODE is sufficiently different - from PREV_ENTRY_ENODE to suggests that some variant is being modified, + from PREV_ENTRY_ENODE to suggest that some variant is being modified, and thus the recursion isn't infinite. Return false if the states are effectively the same, suggesting that @@ -459,64 +555,17 @@ sufficiently_different_p (exploded_node *new_entry_enode, gcc_assert (is_entrypoint_p (new_entry_enode)); gcc_assert (is_entrypoint_p (prev_entry_enode)); - const int new_stack_depth = new_entry_enode->get_stack_depth (); - /* Compare the stores of the two enodes. */ const region_model &new_model = *new_entry_enode->get_state ().m_region_model; - const region_model &prev_model - = *prev_entry_enode->get_state ().m_region_model; const store &new_store = *new_model.get_store (); for (auto kv : new_store) { const region *base_reg = kv.first; - - /* Get the value within the new frame. */ - const svalue *new_sval - = new_model.get_store_value (base_reg, NULL); - - /* If the value is UNKNOWN (e.g. due to hitting complexity limits) - assume that it differs from the previous value. */ - if (new_sval->get_kind () == SK_UNKNOWN) - return true; - - /* Get the equivalent value within the old enode. */ - const svalue *prev_sval; - - if (const frame_region *enclosing_frame - = base_reg->maybe_get_frame_region ()) - { - /* We have a binding within a frame in the new entry enode. */ - - /* Ignore bindings within frames below the new entry node. */ - if (enclosing_frame->get_stack_depth () < new_stack_depth) - continue; - - /* We have a binding within the frame of the new entry node, - presumably a parameter. */ - - /* Get the value within the equivalent frame of - the old entrypoint; typically will be the initial_svalue - of the parameter. */ - const frame_region *equiv_prev_frame - = prev_model.get_current_frame (); - const region *equiv_prev_base_reg - = remap_enclosing_frame (base_reg, - enclosing_frame, - equiv_prev_frame, - new_model.get_manager ()); - prev_sval = prev_model.get_store_value (equiv_prev_base_reg, NULL); - } - else - prev_sval = prev_model.get_store_value (base_reg, NULL); - - /* If the prev_sval is UNKNOWN (e.g. due to hitting complexity limits) - assume that it will differ from any new value. */ - if (prev_sval->get_kind () == SK_UNKNOWN) - return true; - - if (new_sval != prev_sval) + if (sufficiently_different_region_binding_p (new_entry_enode, + prev_entry_enode, + base_reg)) return true; } diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c new file mode 100644 index 00000000000..83efe9bb7e0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c @@ -0,0 +1,17 @@ +typedef struct { + unsigned idx; + int vals[512]; +} foo_t; + +int ended(foo_t* f) { + return f->idx >= 512; +} +unsigned foo(foo_t* f) { + if (ended(f)) { + return f->idx; + } + do { + f->idx++; + } while(!ended(f) && !f->vals[f->idx]); + return foo(f); /* { dg-bogus "infinite recursion" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c new file mode 100644 index 00000000000..b3c4920b10d --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c @@ -0,0 +1,17 @@ +typedef struct { + unsigned idx; + int vals[512]; +} foo_t; + +int ended(foo_t* f) { + return f->idx >= 512; +} +unsigned foo(foo_t* f) { + if (ended(f)) { + return f->idx; + } + do { + f->idx += 1000; + } while(!ended(f) && !f->vals[f->idx]); + return foo(f); /* { dg-bogus "infinite recursion" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c new file mode 100644 index 00000000000..c46f1f8012c --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c @@ -0,0 +1,18 @@ +typedef struct { + unsigned done; +} foo_t; + +unsigned foo(foo_t* f) { + if (f->done) { + return f->done; + } + f->done = 1; + return foo(f); /* { dg-bogus "infinite recursion" } */ +} + +int main() { + foo_t f = (foo_t){ + .done = 0, + }; + foo(&f); +}