From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 7DE9A3857022; Fri, 26 Feb 2021 01:00:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7DE9A3857022 From: "cvs-commit at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path Date: Fri, 26 Feb 2021 01:00:49 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: analyzer X-Bugzilla-Version: 11.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: cvs-commit at gcc dot gnu.org X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: dmalcolm at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: gcc-bugs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-bugs mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 26 Feb 2021 01:00:49 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D96374 --- Comment #4 from CVS Commits --- The master branch has been updated by David Malcolm : https://gcc.gnu.org/g:a505fad4dd4d93b6d642995d7df320aa40949568 commit r11-7410-ga505fad4dd4d93b6d642995d7df320aa40949568 Author: David Malcolm Date: Thu Feb 25 20:00:12 2021 -0500 analyzer: eliminate dedupe_candidate [PR96374] In gcc/analyzer/diagnostic-manager.cc the code partitions saved_diagnostic instances by dedupe_key, and tries to find the "best" saved_diagnostic for each dedupe_key. Ideally we would find the shortest feasible path for each saved_diagnostic and pick the winner in each deduplication set. Currently we merely approximate that by finding the shortest path for each saved_diagnostic, and checking to see if it feasible, rejecting the saved_diagnostic if it is not. The "shortest path, or nothing if it's infeasible" is not the same as the "shortest feasible path", and this leads to false negatives, where we reject valid diagnostics, tracked as PR analyzer/96374. I have been attempting various fixes for this, but in doing so I found that the existing structure of the code makes things unnecessarily awkward: each dedupe_set had a a dedupe_candidate which stored the best epath for that set, creating it from the shortest path when that dedupe_candidate was constructed. This patch eliminates the dedupe_candidate, instead storing the best epath for each saved_diagnostic within the saved_diagnostic itself, along with any feasibility_problem, and eliminating a redundant "status" field. The logic for finding the best epath is moved to a new epath_finder::get_best_epath subroutine, introducing an epath_finder class to give a place to cache state. This patch merely copies over the existing logic to epath_finder::get_best_epath, so no functional change is intended, but the patch simplifies the logic and makes it much easier to experiment with alternate implementations as I try to fix PR analyzer/96374. I attempted another version of this patch in which I added a dedupe_set class and partitioned saved_diagnostics into them as the diagnostics we= re added, but in this earlier iteration of the patch there were regressions e.g. from gcc.dg/analyzer/zlib-4.c where 4 deduplication sets became 3. The issue was that the deduplication logic needs source locations, which need gimple statements, and the stmt_finder needs epaths to run. Findi= ng the epaths needs the full egraph (as opposed to the egraph in its state at the time when the diagnostic is saved). Hence the partitioning need= s to happen after the egraph is fully explored. I backed up the earlier pat= ch kit to: =20=20=20=20=20 https://dmalcolm.fedorapeople.org/gcc/2021-02-23/feasibility-v0.3-relative-= to-72d78655a91bb2f89ac4432cfd6374380d6f9987/ gcc/analyzer/ChangeLog: PR analyzer/96374 * diagnostic-manager.cc (class epath_finder): New. (epath_finder::get_best_epath): New. (saved_diagnostic::saved_diagnostic): Update for replacement of m_state and m_epath_length with m_best_epath. (saved_diagnostic::~saved_diagnostic): Delete m_best_epath. (saved_diagnostic::to_json): Update "path_length" to be optiona= l. (saved_diagnostic::calc_best_epath): New, based on dedupe_winners::add and parts of dedupe_key::dedupe_key. (saved_diagnostic::get_epath_length): New. (saved_diagnostic::add_duplicate): New. (dedupe_key::dedupe_key): Drop epath param. Move invocation of stmt_finder to saved_diagnostic::calc_best_epath. (class dedupe_candidate): Delete. (class dedupe_hash_map_traits): Update to use saved_diagnotic * rather than dedupe_candidate * as the value_type/compare_type. (dedupe_winners::~dedupe_winners): Don't delete the values. (dedupe_winners::add): Convert param from shortest_exploded_pat= hs to epath_finder. Drop "eg" param. Drop dedupe_candidate, moving path generation and feasiblity checking to epath_finder::get_best_epath. Update winner-selection for move of epaths from dedupe_candidate to saved_diagnostic. (dedupe_winners::emit_best): Update for removal of class dedupe_candidate. (dedupe_winners::map_t): Update to use saved_diagnotic * rather than dedupe_candidate * as the value_type/compare_type. (diagnostic_manager::emit_saved_diagnostics): Move shortest_exploded_paths instance into epath_finder and pass that around instead. (diagnostic_manager::emit_saved_diagnostic): Drop epath, stmt and num_dupes params, instead getting these from the saved_diagnostic. Use correct location in inform_n call. * diagnostic-manager.h (class epath_finder): New forward decl. (saved_diagnostic::status): Drop enum. (saved_diagnostic::set_feasible): Drop. (saved_diagnostic::set_infeasible): Drop. (saved_diagnostic::get_status): Drop. (saved_diagnostic::calc_best_epath): New decl. (saved_diagnostic::get_best_epath): New decl. (saved_diagnostic::get_epath_length): New decl. (saved_diagnostic::set_epath_length): Drop. (saved_diagnostic::get_epath_length): Drop inline implementatio= n. (saved_diagnostic::add_duplicate): New. (saved_diagnostic::get_num_dupes): New. (saved_diagnostic::m_d): Document ownership. (saved_diagnostic::m_trailing_eedge): Make const. (saved_diagnostic::m_status): Drop field. (saved_diagnostic::m_epath_length): Drop field. (saved_diagnostic::m_best_epath): New field. (saved_diagnostic::m_problem): Document ownership. (saved_diagnostic::m_duplicates): New field. (diagnostic_manager::emit_saved_diagnostic): Drop params epath, stmt, and num_dupes. * engine.cc (exploded_graph_annotator::print_saved_diagnostic): Update for changes to saved_diagnostic class. * exploded-graph.h (exploded_path::feasible_p): Drop unused overloaded decl.=