[Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path

["cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96374

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:a505fad4dd4d93b6d642995d7df320aa40949568

commit r11-7410-ga505fad4dd4d93b6d642995d7df320aa40949568
Author: David Malcolm <dmalcolm@redhat.com>
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 were
    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.  Finding
    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 needs to
    happen after the egraph is fully explored.  I backed up the earlier patch
    kit to:
     
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 optional.
            (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_paths
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 implementation.
            (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.