MatCat.OpenSource/8sa1-gcc
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
master
8sa1-gcc/gcc/analyzer/analyzer.opt
David Malcolm 3857edb5d3 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.
2021-03-11 17:46:37 -05:00

230 lines
9.1 KiB
Plaintext
Raw Permalink Blame History

; analyzer.opt -- Options for the analyzer.
; Copyright (C) 2019-2021 Free Software Foundation, Inc.
;
; This file is part of GCC.
;
; GCC is free software; you can redistribute it and/or modify it under
; the terms of the GNU General Public License as published by the Free
; Software Foundation; either version 3, or (at your option) any later
; version.
;
; GCC is distributed in the hope that it will be useful, but WITHOUT ANY
; WARRANTY; without even the implied warranty of MERCHANTABILITY or
; FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
; for more details.
;
; You should have received a copy of the GNU General Public License
; along with GCC; see the file COPYING3. If not see
; <http://www.gnu.org/licenses/>.
; See the GCC internals manual for a description of this file's format.
; Please try to keep this file in ASCII collating order.
-param=analyzer-bb-explosion-factor=
Common Joined UInteger Var(param_analyzer_bb_explosion_factor) Init(5) Param
The maximum number of 'after supernode' exploded nodes within the analyzer per supernode, before terminating analysis.
-param=analyzer-max-enodes-per-program-point=
Common Joined UInteger Var(param_analyzer_max_enodes_per_program_point) Init(8) Param
The maximum number of exploded nodes per program point within the analyzer, before terminating analysis of that point.
-param=analyzer-max-constraints=
Common Joined UInteger Var(param_analyzer_max_constraints) Init(20) Param
The maximum number of constraints per state.
-param=analyzer-max-infeasible-edges=
Common Joined UInteger Var(param_analyzer_max_infeasible_edges) Init(10) Param
The maximum number of infeasible edges to reject before declaring a diagnostic as infeasible.
-param=analyzer-max-recursion-depth=
Common Joined UInteger Var(param_analyzer_max_recursion_depth) Init(2) Param
The maximum number of times a callsite can appear in a call stack within the analyzer, before terminating analysis of a call that would recurse deeper.
-param=analyzer-max-svalue-depth=
Common Joined UInteger Var(param_analyzer_max_svalue_depth) Init(13) Param
The maximum depth of a symbolic value, before approximating the value as unknown.
-param=analyzer-min-snodes-for-call-summary=
Common Joined UInteger Var(param_analyzer_min_snodes_for_call_summary) Init(10) Param
The minimum number of supernodes within a function for the analyzer to consider summarizing its effects at call sites.
-param=analyzer-max-enodes-for-full-dump=
Common Joined UInteger Var(param_analyzer_max_enodes_for_full_dump) Init(200) Param
The maximum depth of exploded nodes that should appear in a dot dump before switching to a less verbose format.
Wanalyzer-double-fclose
Common Var(warn_analyzer_double_fclose) Init(1) Warning
Warn about code paths in which a stdio FILE can be closed more than once.
Wanalyzer-double-free
Common Var(warn_analyzer_double_free) Init(1) Warning
Warn about code paths in which a pointer can be freed more than once.
Wanalyzer-exposure-through-output-file
Common Var(warn_analyzer_exposure_through_output_file) Init(1) Warning
Warn about code paths in which sensitive data is written to a file.
Wanalyzer-file-leak
Common Var(warn_analyzer_file_leak) Init(1) Warning
Warn about code paths in which a stdio FILE is not closed.
Wanalyzer-free-of-non-heap
Common Var(warn_analyzer_free_of_non_heap) Init(1) Warning
Warn about code paths in which a non-heap pointer is freed.
Wanalyzer-malloc-leak
Common Var(warn_analyzer_malloc_leak) Init(1) Warning
Warn about code paths in which a heap-allocated pointer leaks.
Wanalyzer-mismatching-deallocation
Common Var(warn_analyzer_mismatching_deallocation) Init(1) Warning
Warn about code paths in which the wrong deallocation function is called.
Wanalyzer-possible-null-argument
Common Var(warn_analyzer_possible_null_argument) Init(1) Warning
Warn about code paths in which a possibly-NULL value is passed to a must-not-be-NULL function argument.
Wanalyzer-possible-null-dereference
Common Var(warn_analyzer_possible_null_dereference) Init(1) Warning
Warn about code paths in which a possibly-NULL pointer is dereferenced.
Wanalyzer-unsafe-call-within-signal-handler
Common Var(warn_analyzer_unsafe_call_within_signal_handler) Init(1) Warning
Warn about code paths in which an async-signal-unsafe function is called from a signal handler.
Wanalyzer-null-argument
Common Var(warn_analyzer_null_argument) Init(1) Warning
Warn about code paths in which NULL is passed to a must-not-be-NULL function argument.
Wanalyzer-null-dereference
Common Var(warn_analyzer_null_dereference) Init(1) Warning
Warn about code paths in which a NULL pointer is dereferenced.
Wanalyzer-shift-count-negative
Common Var(warn_analyzer_shift_count_negative) Init(1) Warning
Warn about code paths in which a shift with negative count is attempted.
Wanalyzer-shift-count-overflow
Common Var(warn_analyzer_shift_count_overflow) Init(1) Warning
Warn about code paths in which a shift with count >= width of type is attempted.
Wanalyzer-stale-setjmp-buffer
Common Var(warn_analyzer_stale_setjmp_buffer) Init(1) Warning
Warn about code paths in which a longjmp rewinds to a jmp_buf saved in a stack frame that has returned.
Wanalyzer-tainted-array-index
Common Var(warn_analyzer_tainted_array_index) Init(1) Warning
Warn about code paths in which an unsanitized value is used as an array index.
Wanalyzer-use-after-free
Common Var(warn_analyzer_use_after_free) Init(1) Warning
Warn about code paths in which a freed value is used.
Wanalyzer-use-of-pointer-in-stale-stack-frame
Common Var(warn_analyzer_use_of_pointer_in_stale_stack_frame) Init(1) Warning
Warn about code paths in which a pointer to a stale stack frame is used.
Wanalyzer-write-to-const
Common Var(warn_analyzer_write_to_const) Init(1) Warning
Warn about code paths which attempt to write to a const object.
Wanalyzer-write-to-string-literal
Common Var(warn_analyzer_write_to_string_literal) Init(1) Warning
Warn about code paths which attempt to write to a string literal.
Wanalyzer-too-complex
Common Var(warn_analyzer_too_complex) Init(0) Warning
Warn if the code is too complicated for the analyzer to fully explore.
fanalyzer-checker=
Common Joined RejectNegative Var(flag_analyzer_checker)
Restrict the analyzer to run just the named checker.
fanalyzer-fine-grained
Common Var(flag_analyzer_fine_grained) Init(0)
Avoid combining multiple statements into one exploded edge.
fanalyzer-feasibility
Common Var(flag_analyzer_feasibility) Init(1)
Verify that paths are feasible when emitting diagnostics.
fanalyzer-show-duplicate-count
Common Var(flag_analyzer_show_duplicate_count) Init(0)
Issue a note when diagnostics are deduplicated.
fanalyzer-state-purge
Common Var(flag_analyzer_state_purge) Init(1)
Purge unneeded state during analysis.
fanalyzer-state-merge
Common Var(flag_analyzer_state_merge) Init(1)
Merge similar-enough states during analysis.
fanalyzer-transitivity
Common Var(flag_analyzer_transitivity) Init(0)
Enable transitivity of constraints during analysis.
fanalyzer-call-summaries
Common Var(flag_analyzer_call_summaries) Init(0)
Approximate the effect of function calls to simplify analysis.
fanalyzer-verbose-edges
Common Var(flag_analyzer_verbose_edges) Init(0)
Emit more verbose descriptions of control flow in diagnostics.
fanalyzer-verbose-state-changes
Common Var(flag_analyzer_verbose_state_changes) Init(0)
Emit more verbose descriptions of state changes in diagnostics.
fanalyzer-verbosity=
Common Joined UInteger Var(analyzer_verbosity) Init(2)
Control which events are displayed in diagnostic paths.
fdump-analyzer
Common RejectNegative Var(flag_dump_analyzer)
Dump various analyzer internals to SRCFILE.analyzer.txt.
fdump-analyzer-stderr
Common RejectNegative Var(flag_dump_analyzer_stderr)
Dump various analyzer internals to stderr.
fdump-analyzer-callgraph
Common RejectNegative Var(flag_dump_analyzer_callgraph)
Dump analyzer-specific call graph information to a SRCFILE.callgraph.dot file.
fdump-analyzer-exploded-graph
Common RejectNegative Var(flag_dump_analyzer_exploded_graph)
Dump the analyzer exploded graph to a SRCFILE.eg.dot file.
fdump-analyzer-exploded-nodes
Common RejectNegative Var(flag_dump_analyzer_exploded_nodes)
Emit diagnostics showing the location of nodes in the exploded graph.
fdump-analyzer-exploded-nodes-2
Common RejectNegative Var(flag_dump_analyzer_exploded_nodes_2)
Dump a textual representation of the exploded graph to SRCFILE.eg.txt.
fdump-analyzer-exploded-nodes-3
Common RejectNegative Var(flag_dump_analyzer_exploded_nodes_3)
Dump a textual representation of the exploded graph to SRCFILE.eg-ID.txt.
fdump-analyzer-feasibility
Common RejectNegative Var(flag_dump_analyzer_feasibility)
Dump various analyzer internals to SRCFILE.*.fg.dot and SRCFILE.*.tg.dot.
fdump-analyzer-json
Common RejectNegative Var(flag_dump_analyzer_json)
Dump analyzer-specific data to a SRCFILE.analyzer.json.gz file.
fdump-analyzer-state-purge
Common RejectNegative Var(flag_dump_analyzer_state_purge)
Dump state-purging information to a SRCFILE.state-purge.dot file.
fdump-analyzer-supergraph
Common RejectNegative Var(flag_dump_analyzer_supergraph)
Dump the analyzer supergraph to a SRCFILE.supergraph.dot file.
; This comment is to ensure we retain the blank line above.
Reference in New Issue View Git Blame Copy Permalink