diff options
-rw-r--r-- | gcc/analyzer/analyzer.h | 1 | ||||
-rw-r--r-- | gcc/analyzer/analyzer.opt | 4 | ||||
-rw-r--r-- | gcc/analyzer/diagnostic-manager.cc | 69 | ||||
-rw-r--r-- | gcc/analyzer/engine.cc | 25 | ||||
-rw-r--r-- | gcc/analyzer/exploded-graph.h | 13 | ||||
-rw-r--r-- | gcc/analyzer/program-point.cc | 8 | ||||
-rw-r--r-- | gcc/analyzer/program-state.cc | 2 | ||||
-rw-r--r-- | gcc/analyzer/region-model.cc | 78 | ||||
-rw-r--r-- | gcc/analyzer/region-model.h | 33 | ||||
-rw-r--r-- | gcc/doc/analyzer.texi | 3 | ||||
-rw-r--r-- | gcc/doc/invoke.texi | 12 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/feasibility-2.c | 20 |
12 files changed, 219 insertions, 49 deletions
diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h index b85edb1..aa43b7f 100644 --- a/gcc/analyzer/analyzer.h +++ b/gcc/analyzer/analyzer.h @@ -71,6 +71,7 @@ class region_model; class region_model_context; class impl_region_model_context; class call_details; +struct rejected_constraint; class constraint_manager; class equiv_class; diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt index 872fb31..a4d3842 100644 --- a/gcc/analyzer/analyzer.opt +++ b/gcc/analyzer/analyzer.opt @@ -126,6 +126,10 @@ 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. diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index 8d7e508..13dd3da 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -160,10 +160,12 @@ class path_builder { public: path_builder (const exploded_graph &eg, - const exploded_path &epath) + const exploded_path &epath, + const feasibility_problem *problem) : m_eg (eg), m_diag_enode (epath.get_final_enode ()), - m_reachability (eg, m_diag_enode) + m_reachability (eg, m_diag_enode), + m_feasibility_problem (problem) {} const exploded_node *get_diag_node () const { return m_diag_enode; } @@ -175,6 +177,11 @@ public: const extrinsic_state &get_ext_state () const { return m_eg.get_ext_state (); } + const feasibility_problem *get_feasibility_problem () const + { + return m_feasibility_problem; + } + private: typedef reachability<eg_traits> enode_reachability; @@ -185,6 +192,8 @@ private: /* Precompute all enodes from which the diagnostic is reachable. */ enode_reachability m_reachability; + + const feasibility_problem *m_feasibility_problem; }; /* class diagnostic_manager. */ @@ -436,24 +445,38 @@ public: sd->m_snode->m_index); feasibility_problem *p = NULL; - if (!dc->get_path ().feasible_p (logger, &p, m_engine, eg)) + if (dc->get_path ().feasible_p (logger, &p, m_engine, eg)) { if (logger) - logger->log ("rejecting %qs at EN: %i, SN: %i" - " due to infeasible path", + logger->log ("accepting %qs at EN: %i, SN: %i with feasible path", sd->m_d->get_kind (), sd->m_enode->m_index, sd->m_snode->m_index); - sd->set_infeasible (p); - delete dc; - return; + sd->set_feasible (); } else - if (logger) - logger->log ("accepting %qs at EN: %i, SN: %i with feasible path", - sd->m_d->get_kind (), sd->m_enode->m_index, - sd->m_snode->m_index); - - sd->set_feasible (); + { + if (flag_analyzer_feasibility) + { + if (logger) + logger->log ("rejecting %qs at EN: %i, SN: %i" + " due to infeasible path", + sd->m_d->get_kind (), sd->m_enode->m_index, + sd->m_snode->m_index); + sd->set_infeasible (p); + delete dc; + return; + } + else + { + if (logger) + logger->log ("accepting %qs at EN: %i, SN: %i" + " despite infeasible path (due to %qs)", + sd->m_d->get_kind (), sd->m_enode->m_index, + sd->m_snode->m_index, + "-fno-analyzer-feasibility"); + sd->set_infeasible (p); + } + } dedupe_key *key = new dedupe_key (*sd, dc->get_path ()); if (dedupe_candidate **slot = m_map.get (key)) @@ -598,7 +621,7 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg, pretty_printer *pp = global_dc->printer->clone (); /* Precompute all enodes from which the diagnostic is reachable. */ - path_builder pb (eg, epath); + path_builder pb (eg, epath, sd.get_feasibility_problem ()); /* This is the diagnostic_path subclass that will be built for the diagnostic. */ @@ -1043,6 +1066,22 @@ diagnostic_manager::add_events_for_eedge (const path_builder &pb, } break; } + + if (pb.get_feasibility_problem () + && &pb.get_feasibility_problem ()->m_eedge == &eedge) + { + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + pp_string (&pp, + "this path would have been rejected as infeasible" + " at this edge: "); + pb.get_feasibility_problem ()->dump_to_pp (&pp); + emission_path->add_event (new custom_event + (dst_point.get_location (), + dst_point.get_fndecl (), + dst_stack_depth, + pp_formatted_text (&pp))); + } } /* Return true if EEDGE is a significant edge in the path to the diagnostic diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index b36c198..aa43e4c 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -3284,7 +3284,8 @@ exploded_path::feasible_p (logger *logger, feasibility_problem **out, sedge->get_description (false)); const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); - if (!model.maybe_update_for_edge (*sedge, last_stmt, NULL)) + rejected_constraint *rc = NULL; + if (!model.maybe_update_for_edge (*sedge, last_stmt, NULL, &rc)) { if (logger) { @@ -3292,8 +3293,10 @@ exploded_path::feasible_p (logger *logger, feasibility_problem **out, model.dump_to_pp (logger->get_printer (), true, false); } if (out) - *out = new feasibility_problem (edge_idx, model, *eedge, - last_stmt); + *out = new feasibility_problem (edge_idx, *eedge, + last_stmt, rc); + else + delete rc; return false; } } @@ -3399,6 +3402,22 @@ exploded_path::dump () const dump (stderr); } +/* class feasibility_problem. */ + +void +feasibility_problem::dump_to_pp (pretty_printer *pp) const +{ + pp_printf (pp, "edge from EN: %i to EN: %i", + m_eedge.m_src->m_index, m_eedge.m_dest->m_index); + if (m_rc) + { + pp_string (pp, "; rejected constraint: "); + m_rc->dump_to_pp (pp); + pp_string (pp, "; rmodel: "); + m_rc->m_model.dump_to_pp (pp, true, false); + } +} + /* A family of cluster subclasses for use when generating .dot output for exploded graphs (-fdump-analyzer-exploded-graph), for grouping the enodes into hierarchical boxes. diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index f723d52b..a6ca4b9 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -880,17 +880,20 @@ class feasibility_problem { public: feasibility_problem (unsigned eedge_idx, - const region_model &model, const exploded_edge &eedge, - const gimple *last_stmt) - : m_eedge_idx (eedge_idx), m_model (model), m_eedge (eedge), - m_last_stmt (last_stmt) + const gimple *last_stmt, + rejected_constraint *rc) + : m_eedge_idx (eedge_idx), m_eedge (eedge), + m_last_stmt (last_stmt), m_rc (rc) {} + ~feasibility_problem () { delete m_rc; } + + void dump_to_pp (pretty_printer *pp) const; unsigned m_eedge_idx; - region_model m_model; const exploded_edge &m_eedge; const gimple *m_last_stmt; + rejected_constraint *m_rc; }; /* Finding the shortest exploded_path within an exploded_graph. */ diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc index 429d6ec..0aadd73 100644 --- a/gcc/analyzer/program-point.cc +++ b/gcc/analyzer/program-point.cc @@ -199,8 +199,12 @@ function_point::get_location () const const gimple *stmt = get_stmt (); if (stmt) return stmt->location; - - return UNKNOWN_LOCATION; + if (m_kind == PK_BEFORE_SUPERNODE) + return m_supernode->get_start_location (); + else if (m_kind == PK_AFTER_SUPERNODE) + return m_supernode->get_end_location (); + else + return UNKNOWN_LOCATION; } /* Create a function_point representing the entrypoint of function FUN. */ diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 188fec0..78b87d5 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -872,7 +872,7 @@ program_state::on_edge (exploded_graph &eg, last_stmt); if (!m_region_model->maybe_update_for_edge (*succ, last_stmt, - &ctxt)) + &ctxt, NULL)) { logger * const logger = eg.get_logger (); if (logger) diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 74a96b0..981fb77 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -1810,6 +1810,20 @@ region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, return true; } +/* As above, but when returning false, if OUT is non-NULL, write a + new rejected_constraint to *OUT. */ + +bool +region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, + region_model_context *ctxt, + rejected_constraint **out) +{ + bool sat = add_constraint (lhs, op, rhs, ctxt); + if (!sat && out) + *out = new rejected_constraint (*this, lhs, op, rhs); + return sat; +} + /* Subroutine of region_model::add_constraint for handling optimized && and || conditionals. @@ -2188,6 +2202,8 @@ region_model::update_for_phis (const supernode *snode, /* Attempt to update this model for taking EDGE (where the last statement was LAST_STMT), returning true if the edge can be taken, false otherwise. + When returning false, if OUT is non-NULL, write a new rejected_constraint + to it. For CFG superedges where LAST_STMT is a conditional or a switch statement, attempt to add the relevant conditions for EDGE to this @@ -2207,7 +2223,8 @@ region_model::update_for_phis (const supernode *snode, bool region_model::maybe_update_for_edge (const superedge &edge, const gimple *last_stmt, - region_model_context *ctxt) + region_model_context *ctxt, + rejected_constraint **out) { /* Handle frame updates for interprocedural edges. */ switch (edge.m_kind) @@ -2247,20 +2264,21 @@ region_model::maybe_update_for_edge (const superedge &edge, if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt)) { const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (&edge); - return apply_constraints_for_gcond (*cfg_sedge, cond_stmt, ctxt); + return apply_constraints_for_gcond (*cfg_sedge, cond_stmt, ctxt, out); } if (const gswitch *switch_stmt = dyn_cast <const gswitch *> (last_stmt)) { const switch_cfg_superedge *switch_sedge = as_a <const switch_cfg_superedge *> (&edge); - return apply_constraints_for_gswitch (*switch_sedge, switch_stmt, ctxt); + return apply_constraints_for_gswitch (*switch_sedge, switch_stmt, + ctxt, out); } /* Apply any constraints due to an exception being thrown. */ if (const cfg_superedge *cfg_sedge = dyn_cast <const cfg_superedge *> (&edge)) if (cfg_sedge->get_flags () & EDGE_EH) - return apply_constraints_for_exception (last_stmt, ctxt); + return apply_constraints_for_exception (last_stmt, ctxt, out); return true; } @@ -2338,12 +2356,15 @@ region_model::update_for_call_summary (const callgraph_superedge &cg_sedge, If they are feasible, add the constraints and return true. Return false if the constraints contradict existing knowledge - (and so the edge should not be taken). */ + (and so the edge should not be taken). + When returning false, if OUT is non-NULL, write a new rejected_constraint + to it. */ bool region_model::apply_constraints_for_gcond (const cfg_superedge &sedge, const gcond *cond_stmt, - region_model_context *ctxt) + region_model_context *ctxt, + rejected_constraint **out) { ::edge cfg_edge = sedge.get_cfg_edge (); gcc_assert (cfg_edge != NULL); @@ -2354,7 +2375,7 @@ region_model::apply_constraints_for_gcond (const cfg_superedge &sedge, tree rhs = gimple_cond_rhs (cond_stmt); if (cfg_edge->flags & EDGE_FALSE_VALUE) op = invert_tree_comparison (op, false /* honor_nans */); - return add_constraint (lhs, op, rhs, ctxt); + return add_constraint (lhs, op, rhs, ctxt, out); } /* Given an EDGE guarded by SWITCH_STMT, determine appropriate constraints @@ -2363,12 +2384,15 @@ region_model::apply_constraints_for_gcond (const cfg_superedge &sedge, If they are feasible, add the constraints and return true. Return false if the constraints contradict existing knowledge - (and so the edge should not be taken). */ + (and so the edge should not be taken). + When returning false, if OUT is non-NULL, write a new rejected_constraint + to it. */ bool region_model::apply_constraints_for_gswitch (const switch_cfg_superedge &edge, const gswitch *switch_stmt, - region_model_context *ctxt) + region_model_context *ctxt, + rejected_constraint **out) { tree index = gimple_switch_index (switch_stmt); tree case_label = edge.get_case_label (); @@ -2380,13 +2404,13 @@ region_model::apply_constraints_for_gswitch (const switch_cfg_superedge &edge, if (upper_bound) { /* Range. */ - if (!add_constraint (index, GE_EXPR, lower_bound, ctxt)) + if (!add_constraint (index, GE_EXPR, lower_bound, ctxt, out)) return false; - return add_constraint (index, LE_EXPR, upper_bound, ctxt); + return add_constraint (index, LE_EXPR, upper_bound, ctxt, out); } else /* Single-value. */ - return add_constraint (index, EQ_EXPR, lower_bound, ctxt); + return add_constraint (index, EQ_EXPR, lower_bound, ctxt, out); } else { @@ -2406,14 +2430,16 @@ region_model::apply_constraints_for_gswitch (const switch_cfg_superedge &edge, /* Exclude this range-valued case. For now, we just exclude the boundary values. TODO: exclude the values within the region. */ - if (!add_constraint (index, NE_EXPR, other_lower_bound, ctxt)) + if (!add_constraint (index, NE_EXPR, other_lower_bound, + ctxt, out)) return false; - if (!add_constraint (index, NE_EXPR, other_upper_bound, ctxt)) + if (!add_constraint (index, NE_EXPR, other_upper_bound, + ctxt, out)) return false; } else /* Exclude this single-valued case. */ - if (!add_constraint (index, NE_EXPR, other_lower_bound, ctxt)) + if (!add_constraint (index, NE_EXPR, other_lower_bound, ctxt, out)) return false; } return true; @@ -2425,11 +2451,14 @@ region_model::apply_constraints_for_gswitch (const switch_cfg_superedge &edge, If they are feasible, add the constraints and return true. Return false if the constraints contradict existing knowledge - (and so the edge should not be taken). */ + (and so the edge should not be taken). + When returning false, if OUT is non-NULL, write a new rejected_constraint + to it. */ bool region_model::apply_constraints_for_exception (const gimple *last_stmt, - region_model_context *ctxt) + region_model_context *ctxt, + rejected_constraint **out) { gcc_assert (last_stmt); if (const gcall *call = dyn_cast <const gcall *> (last_stmt)) @@ -2442,7 +2471,7 @@ region_model::apply_constraints_for_exception (const gimple *last_stmt, leak report due to the result being lost when following the EH edge. */ if (tree lhs = gimple_call_lhs (call)) - return add_constraint (lhs, EQ_EXPR, null_pointer_node, ctxt); + return add_constraint (lhs, EQ_EXPR, null_pointer_node, ctxt, out); return true; } return true; @@ -2862,6 +2891,19 @@ debug (const region_model &rmodel) rmodel.dump (false); } +/* struct rejected_constraint. */ + +void +rejected_constraint::dump_to_pp (pretty_printer *pp) const +{ + region_model m (m_model); + const svalue *lhs_sval = m.get_rvalue (m_lhs, NULL); + const svalue *rhs_sval = m.get_rvalue (m_rhs, NULL); + lhs_sval->dump_to_pp (pp, true); + pp_printf (pp, " %s ", op_symbol_code (m_op)); + rhs_sval->dump_to_pp (pp, true); +} + /* class engine. */ /* Dump the managed objects by class to LOGGER, and the per-class totals. */ diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index 1e8a517..a61aff2 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -2586,7 +2586,8 @@ class region_model bool maybe_update_for_edge (const superedge &edge, const gimple *last_stmt, - region_model_context *ctxt); + region_model_context *ctxt, + rejected_constraint **out); const region *push_frame (function *fun, const vec<const svalue *> *arg_sids, region_model_context *ctxt); @@ -2630,6 +2631,9 @@ class region_model region_model_context *ctxt); bool add_constraint (tree lhs, enum tree_code op, tree rhs, region_model_context *ctxt); + bool add_constraint (tree lhs, enum tree_code op, tree rhs, + region_model_context *ctxt, + rejected_constraint **out); const region *create_region_for_heap_alloc (const svalue *size_in_bytes); const region *create_region_for_alloca (const svalue *size_in_bytes); @@ -2699,12 +2703,15 @@ class region_model region_model_context *ctxt); bool apply_constraints_for_gcond (const cfg_superedge &edge, const gcond *cond_stmt, - region_model_context *ctxt); + region_model_context *ctxt, + rejected_constraint **out); bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge, const gswitch *switch_stmt, - region_model_context *ctxt); + region_model_context *ctxt, + rejected_constraint **out); bool apply_constraints_for_exception (const gimple *last_stmt, - region_model_context *ctxt); + region_model_context *ctxt, + rejected_constraint **out); int poison_any_pointers_to_descendents (const region *reg, enum poison_kind pkind); @@ -2851,6 +2858,24 @@ struct model_merger region_model *m_merged_model; }; +/* A record that can (optionally) be written out when + region_model::add_constraint fails. */ + +struct rejected_constraint +{ + rejected_constraint (const region_model &model, + tree lhs, enum tree_code op, tree rhs) + : m_model (model), m_lhs (lhs), m_op (op), m_rhs (rhs) + {} + + void dump_to_pp (pretty_printer *pp) const; + + region_model m_model; + tree m_lhs; + enum tree_code m_op; + tree m_rhs; +}; + /* A bundle of state. */ class engine diff --git a/gcc/doc/analyzer.texi b/gcc/doc/analyzer.texi index 6b7d70c..96fe9bb 100644 --- a/gcc/doc/analyzer.texi +++ b/gcc/doc/analyzer.texi @@ -329,7 +329,8 @@ we only emit the simplest path (which could be intraprocedural, if it can be reproduced without a caller). We apply a check that each duplicate warning's shortest path is feasible, rejecting any warnings for which the shortest path is infeasible (which could lead to -false negatives). +false negatives). This check can be suppressed (for debugging purposes) +using @option{-fno-analyzer-feasibility}. We use the shortest feasible @code{exploded_path} through the @code{exploded_graph} (a list of @code{exploded_edge *}) to build a diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index c17e5c6..75203ba 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -393,6 +393,7 @@ Objective-C and Objective-C++ Dialects}. -fanalyzer @gol -fanalyzer-call-summaries @gol -fanalyzer-checker=@var{name} @gol +-fno-analyzer-feasibility @gol -fanalyzer-fine-grained @gol -fanalyzer-state-merge @gol -fanalyzer-state-purge @gol @@ -8993,6 +8994,17 @@ such as the @code{taint} checker that implements @option{-Wanalyzer-tainted-array-index}, and this option is required to enable them. +@item -fno-analyzer-feasibility +@opindex fanalyzer-feasibility +@opindex fno-analyzer-feasibility +This option is intended for analyzer developers. + +By default the analyzer verifies that there is a feasible control flow path +for each diagnostic it emits: that the conditions that hold are not mutually +exclusive. Diagnostics for which no feasible path can be found are rejected. +This filtering can be suppressed with @option{-fno-analyzer-feasibility}, for +debugging issues in this code. + @item -fanalyzer-fine-grained @opindex fanalyzer-fine-grained @opindex fno-analyzer-fine-grained diff --git a/gcc/testsuite/gcc.dg/analyzer/feasibility-2.c b/gcc/testsuite/gcc.dg/analyzer/feasibility-2.c new file mode 100644 index 0000000..9fe62d2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/feasibility-2.c @@ -0,0 +1,20 @@ +/* Verify that -fno-analyzer-feasibility works. */ +/* { dg-additional-options "-fno-analyzer-feasibility" } */ + +#include "analyzer-decls.h" + +void test_1 (int flag) +{ + int a; + if (flag) + a = 1; + else + a = 2; + + if (a == 1) /* (can only be the case when "flag" was true above). */ + if (!flag) + { + __analyzer_dump_path (); /* { dg-message "note: path" "path diag" } */ + /* { dg-message "infeasible" "infeasibility event" { target *-*-* } .-1 } */ + } +} |