public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
@ 2020-07-29 15:33 dmalcolm at gcc dot gnu.org
  2020-07-29 15:42 ` [Bug analyzer/96374] " dmalcolm at gcc dot gnu.org
                   ` (8 more replies)
  0 siblings, 9 replies; 10+ messages in thread
From: dmalcolm at gcc dot gnu.org @ 2020-07-29 15:33 UTC (permalink / raw)
  To: gcc-bugs

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

            Bug ID: 96374
           Summary: Analyzer erroneously rejects certain diagnostics due
                    to path-feasibility being used on shortest path
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: dmalcolm at gcc dot gnu.org
  Target Milestone: ---

Analyzer fails to find a path to the __analyzer_dump_path call:

#include "analyzer-decls.h"

int test_6 (int a, int b)
{
  int problem = 0;
  if (a)
    problem = 1;
  if (b)
    {
      if (!problem)
        problem = 2;
      __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */
    }
  return problem;
}

It's rejecting the path due to picking the shortest path, and then a bad
interaction with feasibility-checking.

If feasibility-checking is hacked out, it picks this path (with
-fanalyzer-verbosity=3 for clarity):

  ‘test_6’: events 1-7
    |
    |    6 |   if (a)
    |      |      ^
    |      |      |
    |      |      (1) following ‘false’ branch (when ‘a == 0’)...
    |    7 |     problem = 1;
    |    8 |   if (b)
    |      |      ~
    |      |      |
    |      |      (2) ...to here
    |      |      (3) following ‘true’ branch (when ‘b != 0’)...
    |    9 |     {
    |   10 |       if (!problem)
    |      |          ~
    |      |          |
    |      |          (4) ...to here
    |      |          (5) following ‘false’ branch (when ‘problem != 0’)...
    |   11 |  problem = 2;
    |   12 |       __analyzer_dump_path ();
    |      |       ~~~~~~~~~~~~~~~~~~~~~~~
    |      |       |
    |      |       (6) ...to here
    |      |       (7) here
    |

However, with feasibility-checking, "problem" is still 0 at event (5) (due to
the shortest path skipping the "problem = 1" suite), and hance the "problem !=
0" edge is invalid, and the edge from (5) to (6) is rejected, and the
diagnostic rejected.

We want the shortest feasible path if one exists, and are currently
approximating this by picking the shortest path, and checking if it's feasible,
which isn't the same thing.

Am not sure how best to fix this, but need a PR to mark this as XFAIL.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
@ 2020-07-29 15:42 ` dmalcolm at gcc dot gnu.org
  2021-02-02  2:53 ` cvs-commit at gcc dot gnu.org
                   ` (7 subsequent siblings)
  8 siblings, 0 replies; 10+ messages in thread
From: dmalcolm at gcc dot gnu.org @ 2020-07-29 15:42 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #1 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
This is likely to be associated with "merger" exploded_nodes (where we have
merged state to help the exploded graph converge).  Perhaps if we fail to find
a feasible path on the first try we could retry, finding the shortest path that
doesn't include each merger node in turn, and if any of those are feasible,
find the shortest one.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
  2020-07-29 15:42 ` [Bug analyzer/96374] " dmalcolm at gcc dot gnu.org
@ 2021-02-02  2:53 ` cvs-commit at gcc dot gnu.org
  2021-02-02  2:55 ` cvs-commit at gcc dot gnu.org
                   ` (6 subsequent siblings)
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-02-02  2:53 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #2 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:f2f639c4a781016ad146d44f463714fe4295cb6e

commit r11-7028-gf2f639c4a781016ad146d44f463714fe4295cb6e
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Mon Feb 1 21:52:41 2021 -0500

    analyzer: add more feasibility test cases [PR93355,PR96374]

    This patch adds a couple more reduced test cases derived from the
    integration test for PR analyzer/93355.  In both cases, the analyzer
    falsely rejects the buggy code paths as being infeasible due to
    PR analyzer/96374, and so the tests are marked as XFAIL for now.

    gcc/testsuite/ChangeLog:
            PR analyzer/93355
            PR analyzer/96374
            * gcc.dg/analyzer/pr93355-localealias-feasibility-2.c: New test.
            * gcc.dg/analyzer/pr93355-localealias-feasibility-3.c: New test.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
  2020-07-29 15:42 ` [Bug analyzer/96374] " dmalcolm at gcc dot gnu.org
  2021-02-02  2:53 ` cvs-commit at gcc dot gnu.org
@ 2021-02-02  2:55 ` cvs-commit at gcc dot gnu.org
  2021-02-26  1:00 ` cvs-commit at gcc dot gnu.org
                   ` (5 subsequent siblings)
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-02-02  2:55 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #3 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:8a2750086d57d1a2251d9239fa4e6c2dc9ec3a86

commit r11-7029-g8a2750086d57d1a2251d9239fa4e6c2dc9ec3a86
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Mon Feb 1 21:54:11 2021 -0500

    analyzer: directly explore within static functions [PR93355,PR96374]

    PR analyzer/93355 tracks that -fanalyzer fails to report the FILE *
    leak in read_alias_file in intl/localealias.c.

    One reason for the failure is that read_alias_file is marked as
    "static", and the path leading to the single call of
    read_alias_file is falsely rejected as infeasible due to
    PR analyzer/96374.  I have been attempting to fix that bug, but
    don't have a good solution yet.

    Previously, -fanalyzer only directly explored "static" functions
    if they were needed for call summaries, instead forcing them to
    be indirectly explored, but if we have a feasibility bug like
    above, we will fail to report any issues in a function that's
    only called by such a falsely infeasible path.

    It now seems wrong to me to reject directly exploring static
    functions: even if there is currently no way to call a function,
    it seems reasonable to warn about bugs within them, since
    otherwise these latent bugs are a timebomb in the code.

    Hence this patch reworks toplevel_function_p to directly explore
    almost all functions, working around these feasiblity issues.
    It introduces a naming convention that "__analyzer_"-prefixed
    function names don't get directly explored, since this is
    useful in the analyzer's DejaGnu-based tests.

    This workaround gets PR analyzer/93355 closer to working, but
    unfortunately there is a second instance of PR analyzer/96374
    within read_alias_file itself which means even with this patch
    -fanalyzer falsely rejects the path as infeasible.

    Still, this ought to help in other cases, and simplifies the
    implementation.

    gcc/analyzer/ChangeLog:
            PR analyzer/93355
            PR analyzer/96374
            * engine.cc (toplevel_function_p): Simplify so that
            we only reject functions with a "__analyzer_" prefix.
            (add_any_callbacks): Delete.
            (exploded_graph::build_initial_worklist): Update for
            dropped param of toplevel_function_p.
            (exploded_graph::build_initial_worklist): Don't bother
            looking for callbacks that are reachable from global
            initializers.

    gcc/testsuite/ChangeLog:
            PR analyzer/93355
            PR analyzer/96374
            * gcc.dg/analyzer/conditionals-3.c: Add "__analyzer_"
            prefix to support subroutines where necessary.
            * gcc.dg/analyzer/data-model-1.c: Likewise.
            * gcc.dg/analyzer/feasibility-1.c (called_by_test_6a): New.
            (test_6a): New.
            * gcc.dg/analyzer/params.c: Add "__analyzer_" prefix to support
            subroutines where necessary.
            * gcc.dg/analyzer/pr96651-2.c: Likewise.
            * gcc.dg/analyzer/signal-4b.c: Likewise.
            * gcc.dg/analyzer/single-field.c: Likewise.
            * gcc.dg/analyzer/torture/conditionals-2.c: Likewise.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
                   ` (2 preceding siblings ...)
  2021-02-02  2:55 ` cvs-commit at gcc dot gnu.org
@ 2021-02-26  1:00 ` cvs-commit at gcc dot gnu.org
  2021-03-10 17:03 ` cvs-commit at gcc dot gnu.org
                   ` (4 subsequent siblings)
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-02-26  1:00 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
                   ` (3 preceding siblings ...)
  2021-02-26  1:00 ` cvs-commit at gcc dot gnu.org
@ 2021-03-10 17:03 ` cvs-commit at gcc dot gnu.org
  2021-03-11 22:44 ` cvs-commit at gcc dot gnu.org
                   ` (3 subsequent siblings)
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-03-10 17:03 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #5 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:44fd4dc0b684e06c6c6d08b3994df23135bf2fbc

commit r11-7609-g44fd4dc0b684e06c6c6d08b3994df23135bf2fbc
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Wed Mar 10 12:02:07 2021 -0500

    analyzer: factor out new class feasibility_state

    As preparatory work for a fix to PR analyzer/96374, this patch
    moves the core state-update logic from the loop in
    exploded_path::feasible_p into a new class feasibility_state.

    No functional change intended.

    gcc/analyzer/ChangeLog:
            PR analyzer/96374
            * engine.cc (exploded_path::feasible_p): Move "snodes_visited" and
            "model" locals into a new class feasibility_state.  Move heart
            of per-edge processing into
            feasibility_state::maybe_update_for_edge.
            (feasibility_state::feasibility_state): New.
            (feasibility_state::maybe_update_for_edge): New, based on loop
            body in exploded_path::feasible_p.
            * exploded-graph.h (class feasibility_state): New.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
                   ` (4 preceding siblings ...)
  2021-03-10 17:03 ` cvs-commit at gcc dot gnu.org
@ 2021-03-11 22:44 ` cvs-commit at gcc dot gnu.org
  2021-03-11 22:45 ` cvs-commit at gcc dot gnu.org
                   ` (2 subsequent siblings)
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-03-11 22:44 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #6 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:3f958348e78f38d91f0611618bb909182170c0f3

commit r11-7638-g3f958348e78f38d91f0611618bb909182170c0f3
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Mar 11 17:43:39 2021 -0500

    analyzer: gracefully handle impossible paths in shortest-paths.h

    This bulletproofs the shortest_paths code against unreachable nodes,
    gracefully handling them, rather than failing an assertion.

    I've marked this as "analyzer" as this is the only code using
    shortest-paths.h.

    This patch is required by followup work to fix PR analyzer/96374.

    gcc/ChangeLog:
            * digraph.cc (selftest::test_shortest_paths): Add test coverage
            for paths from B and C.
            * shortest-paths.h (shortest_paths::shortest_paths): Handle
            unreachable nodes, rather than asserting.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
                   ` (5 preceding siblings ...)
  2021-03-11 22:44 ` cvs-commit at gcc dot gnu.org
@ 2021-03-11 22:45 ` cvs-commit at gcc dot gnu.org
  2021-03-11 22:48 ` cvs-commit at gcc dot gnu.org
  2021-03-11 23:16 ` dmalcolm at gcc dot gnu.org
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-03-11 22:45 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #7 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:5e33e5b042a6a830c40cee3d0a925bc49dcfe069

commit r11-7639-g5e33e5b042a6a830c40cee3d0a925bc49dcfe069
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Mar 11 17:45:10 2021 -0500

    analyzer: support reverse direction in shortest-paths.h

    This patch generalizes shortest-path.h so that it can be used to
    find the shortest path from each node to a given target node (on top
    of the existing support for finding the shortest path from a given
    origin node to each node).

    I've marked this as "analyzer" as this is the only code using
    shortest-paths.h.

    This patch is required by followup work to fix PR analyzer/96374.

    gcc/analyzer/ChangeLog:
            * diagnostic-manager.cc (epath_finder::epath_finder):
            Update shortest_paths init for new param.

    gcc/ChangeLog:
            * digraph.cc (selftest::test_shortest_paths): Update
            shortest_paths init for new param.  Add test of
            SPS_TO_GIVEN_TARGET.
            * shortest-paths.h (enum shortest_path_sense): New.
            (shortest_paths::shortest_paths): Add "sense" param.
            Update for renamings.  Generalize to use "sense" param.
            (shortest_paths::get_shortest_path): Rename param.
            (shortest_paths::m_sense): New field.
            (shortest_paths::m_prev): Rename...
            (shortest_paths::m_best_edge): ...to this.
            (shortest_paths::get_shortest_path): Update for renamings.
            Conditionalize flipping of path on sense of traversal.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
                   ` (6 preceding siblings ...)
  2021-03-11 22:45 ` cvs-commit at gcc dot gnu.org
@ 2021-03-11 22:48 ` cvs-commit at gcc dot gnu.org
  2021-03-11 23:16 ` dmalcolm at gcc dot gnu.org
  8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-03-11 22:48 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #8 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:3857edb5d32dcdc11d9a2fe3ad7c156c52a1ec7f

commit r11-7640-g3857edb5d32dcdc11d9a2fe3ad7c156c52a1ec7f
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Mar 11 17:46:37 2021 -0500

    analyzer: new implementation of shortest feasible path [PR96374]

    The analyzer builds an exploded graph of (point,state) pairs and when
    it finds a problem, records a diagnostic at the relevant exploded node.
    Once it has finished exploring the graph, the analyzer needs to generate
    the shortest feasible path through the graph to each diagnostic's node.
    This is used:
    - for rejecting diagnostics that are infeasible (due to impossible sets
      of constraints),
    - for use in determining which diagnostic to use in each deduplication
      set (the one with the shortest path), and
    - for building checker_paths for the "winning" diagnostics, giving a
      list of events

    Prior to this patch the analyzer simply found the shortest path to the
    node, and then checked it for feasibility, which could lead to falsely
    rejecting diagnostics: "the shortest path, if feasible" is not the same
    as "the shortest feasible path" (PR analyzer/96374).
    An example is PR analyzer/93355, where this issue causes the analyzer
    to fail to emit a leak warning for a missing fclose on an error-handling
    path in intl/localealias.c.

    This patch implements a new algorithm for finding the shortest feasible
    path to an exploded node: instead of simply finding the shortest path,
    the new algorithm uses a worklist to iteratively build a tree of path
    prefixes, which are feasible paths by construction, until a path to the
    target node is found.  The worklist is prioritized, so that the first
    feasible path discovered is the shortest possible feasible path.  The
    algorithm continues trying paths until the target node is reached or a
    limit is exceeded, in which case the diagnostic is treated as being
    infeasible (which could still be a false negative, but is much less
    likely to happen than before).  Iteratively building a tree of paths
    allows for work to be reused, and the tree can be dumped in .dot form
    (via a new -fdump-analyzer-feasibility option), making it much easier to
    debug compared to other approaches I tried.

    Doing so fixes the missing leak warning for PR analyzer/93355 and
    various other test cases.

    Testing:
    - I manually verified that the behavior is determistic using 50 builds
      of pr93355-localealias.c.  All dumps were identical.
    - I manually verified that it still builds with --disable-analyzer.
    - Lightly tested with valgrind; no additional issues.
    - Lightly performance tested, showing a slight speed regression to the
      analyzer relative to before the patch, but correctness for this issue
      is more important than the slight performance hit for the analyzer.

    gcc/ChangeLog:
            PR analyzer/96374
            * Makefile.in (ANALYZER_OBJS): Add analyzer/feasible-graph.o and
            analyzer/trimmed-graph.o.
            * doc/analyzer.texi (Analyzer Paths): Rewrite description of
            feasibility checking to reflect new implementation.
            * doc/invoke.texi (-fdump-analyzer-feasibility): Document new
            option.
            * shortest-paths.h (shortest_paths::get_shortest_distance): New.

    gcc/analyzer/ChangeLog:
            PR analyzer/96374
            * analyzer.opt (-param=analyzer-max-infeasible-edges=): New param.
            (fdump-analyzer-feasibility): New flag.
            * diagnostic-manager.cc: Include "analyzer/trimmed-graph.h" and
            "analyzer/feasible-graph.h".
            (epath_finder::epath_finder): Convert m_sep to a pointer and
            only create it if !flag_analyzer_feasibility.
            (epath_finder::~epath_finder): New.
            (epath_finder::m_sep): Convert to a pointer.
            (epath_finder::get_best_epath): Add param "diag_idx" and use it
            when logging.  Rather than finding the shortest path and then
            checking feasibility, instead use explore_feasible_paths unless
            !flag_analyzer_feasibility, in which case simply use the shortest
            path, and note if it is infeasible.  Update for m_sep becoming a
            pointer.
            (class feasible_worklist): New.
            (epath_finder::explore_feasible_paths): New.
            (epath_finder::process_worklist_item): New.
            (class dump_eg_with_shortest_path): New.
            (epath_finder::dump_trimmed_graph): New.
            (epath_finder::dump_feasible_graph): New.
            (saved_diagnostic::saved_diagnostic): Add "idx" param, using it
            on new field m_idx.
            (saved_diagnostic::to_json): Dump m_idx.
            (saved_diagnostic::calc_best_epath): Pass m_idx to get_best_epath.
            Remove assertion that m_problem was set when m_best_epath is NULL.
            (diagnostic_manager::add_diagnostic): Pass an index when created
            saved_diagnostic instances.
            * diagnostic-manager.h (saved_diagnostic::saved_diagnostic): Add
            "idx" param.
            (saved_diagnostic::get_index): New accessor.
            (saved_diagnostic::m_idx): New field.
            * engine.cc (exploded_node::dump_dot): Call args.dump_extra_info.
            Move code to...
            (exploded_node::dump_processed_stmts): ...this new function and...
            (exploded_node::dump_saved_diagnostics): ...this new function.
            Add index of each diagnostic.
            (exploded_edge::dump_dot):  Move bulk of code to...
            (exploded_edge::dump_dot_label): ...this new function.
            * exploded-graph.h (eg_traits::dump_args_t::dump_extra_info): New
            vfunc.
            (exploded_node::dump_processed_stmts): New decl.
            (exploded_node::dump_saved_diagnostics): New decl.
            (exploded_edge::dump_dot_label): New decl.
            * feasible-graph.cc: New file.
            * feasible-graph.h: New file.
            * trimmed-graph.cc: New file.
            * trimmed-graph.h: New file.

    gcc/testsuite/ChangeLog:
            PR analyzer/96374
            * gcc.dg/analyzer/dot-output.c: Add -fdump-analyzer-feasibility
            to options.
            * gcc.dg/analyzer/feasibility-1.c (test_6): Remove xfail.
            (test_7): New.
            * gcc.dg/analyzer/pr93355-localealias-feasibility-2.c: Remove
xfail.
            * gcc.dg/analyzer/pr93355-localealias-feasibility-3.c: Remove
xfails.
            * gcc.dg/analyzer/pr93355-localealias-feasibility.c: Remove
            -fno-analyzer-feasibility from options.
            * gcc.dg/analyzer/pr93355-localealias.c: Likewise.
            * gcc.dg/analyzer/unknown-fns-4.c: Remove xfail.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [Bug analyzer/96374] Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path
  2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
                   ` (7 preceding siblings ...)
  2021-03-11 22:48 ` cvs-commit at gcc dot gnu.org
@ 2021-03-11 23:16 ` dmalcolm at gcc dot gnu.org
  8 siblings, 0 replies; 10+ messages in thread
From: dmalcolm at gcc dot gnu.org @ 2021-03-11 23:16 UTC (permalink / raw)
  To: gcc-bugs

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

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #9 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Should be fixed by the above commit.

^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2021-03-11 23:16 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-07-29 15:33 [Bug analyzer/96374] New: Analyzer erroneously rejects certain diagnostics due to path-feasibility being used on shortest path dmalcolm at gcc dot gnu.org
2020-07-29 15:42 ` [Bug analyzer/96374] " dmalcolm at gcc dot gnu.org
2021-02-02  2:53 ` cvs-commit at gcc dot gnu.org
2021-02-02  2:55 ` cvs-commit at gcc dot gnu.org
2021-02-26  1:00 ` cvs-commit at gcc dot gnu.org
2021-03-10 17:03 ` cvs-commit at gcc dot gnu.org
2021-03-11 22:44 ` cvs-commit at gcc dot gnu.org
2021-03-11 22:45 ` cvs-commit at gcc dot gnu.org
2021-03-11 22:48 ` cvs-commit at gcc dot gnu.org
2021-03-11 23:16 ` dmalcolm at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).