From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2209) id 7D010383D827; Fri, 11 Jun 2021 13:33:30 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7D010383D827 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 r12-1389] analyzer: tweak priority of callstrings in worklist::key_t::cmp X-Act-Checkin: gcc X-Git-Author: David Malcolm X-Git-Refname: refs/heads/master X-Git-Oldrev: b9ec5ebb605936684e95b8dcc12e43ba7d8f2cb4 X-Git-Newrev: 9d20ec97475b1102d6ca005ad165056d34615a3d Message-Id: <20210611133330.7D010383D827@sourceware.org> Date: Fri, 11 Jun 2021 13:33:30 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 11 Jun 2021 13:33:30 -0000 https://gcc.gnu.org/g:9d20ec97475b1102d6ca005ad165056d34615a3d commit r12-1389-g9d20ec97475b1102d6ca005ad165056d34615a3d Author: David Malcolm Date: Fri Jun 11 09:30:33 2021 -0400 analyzer: tweak priority of callstrings in worklist::key_t::cmp While debugging another issue I noticed that the analyzer could fail to merge nodes for control flow in which one path had called a function and another path hadn't: BB / \ / \ fn call no fn call \ / \ / join BB The root cause was that the worklist sort function wasn't prioritizing call strings, and thus it was fully exploring the "no function called" path to the exit BB, and only then exploring the "within the function call" parts of the "funcion called" path. This patch prioritizes call strings when sorting the worklist so that the nodes with deeper call strings are processed before those with shallower call strings, thus allowing such nodes to be merged at the joinpoint. gcc/analyzer/ChangeLog: * engine.cc (worklist::key_t::cmp): Move sort by call_string to before SCC. gcc/testsuite/ChangeLog: * gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c: Update expected number of enodes after the loop. * gcc.dg/analyzer/paths-8.c: New test. Signed-off-by: David Malcolm Diff: --- gcc/analyzer/engine.cc | 25 ++++++++++++++++------ .../analyzer/loop-0-up-to-n-by-1-with-iter-obj.c | 3 +-- gcc/testsuite/gcc.dg/analyzer/paths-8.c | 17 +++++++++++++++ 3 files changed, 37 insertions(+), 8 deletions(-) diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 5b519fdf385..48320bc062e 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -2004,7 +2004,25 @@ worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) return cmp; } - /* First, order by SCC. */ + /* Sort by callstring, so that nodes with deeper call strings are processed + before those with shallower call strings. + If we have + splitting BB + / \ + / \ + fn call no fn call + \ / + \ / + join BB + then we want the path inside the function call to be fully explored up + to the return to the join BB before we explore on the "no fn call" path, + so that both enodes at the join BB reach the front of the worklist at + the same time and thus have a chance of being merged. */ + int cs_cmp = call_string::cmp (call_string_a, call_string_b); + if (cs_cmp) + return cs_cmp; + + /* Order by SCC. */ int scc_id_a = ka.get_scc_id (ka.m_enode); int scc_id_b = kb.get_scc_id (kb.m_enode); if (scc_id_a != scc_id_b) @@ -2033,11 +2051,6 @@ worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) gcc_assert (snode_a == snode_b); - /* The points might vary by callstring; try sorting by callstring. */ - int cs_cmp = call_string::cmp (call_string_a, call_string_b); - if (cs_cmp) - return cs_cmp; - /* Order within supernode via program point. */ int within_snode_cmp = function_point::cmp_within_supernode (point_a.get_function_point (), diff --git a/gcc/testsuite/gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c b/gcc/testsuite/gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c index 2b0352711ae..0172c9b324c 100644 --- a/gcc/testsuite/gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c +++ b/gcc/testsuite/gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c @@ -69,6 +69,5 @@ void test(int n) free (it); - __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enodes" } */ - // TODO: why 2 enodes here, rather than 1 + __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */ } diff --git a/gcc/testsuite/gcc.dg/analyzer/paths-8.c b/gcc/testsuite/gcc.dg/analyzer/paths-8.c new file mode 100644 index 00000000000..b350d4d7dbd --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/paths-8.c @@ -0,0 +1,17 @@ +#include "analyzer-decls.h" + +static void __attribute__((noinline)) +__analyzer_callee_1 (void) +{ + /* empty. */ +} + +void +test_1 (int flag) +{ + if (flag) + __analyzer_callee_1 (); + + /* Verify that we merge state, whether or not the call happens. */ + __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */ +}