diff options
| -rw-r--r-- | gcc/Makefile.in | 4 | ||||
| -rw-r--r-- | gcc/analyzer/analyzer.opt | 8 | ||||
| -rw-r--r-- | gcc/analyzer/diagnostic-manager.cc | 490 | ||||
| -rw-r--r-- | gcc/analyzer/diagnostic-manager.h | 6 | ||||
| -rw-r--r-- | gcc/analyzer/engine.cc | 99 | ||||
| -rw-r--r-- | gcc/analyzer/exploded-graph.h | 8 | ||||
| -rw-r--r-- | gcc/analyzer/feasible-graph.cc | 235 | ||||
| -rw-r--r-- | gcc/analyzer/feasible-graph.h | 213 | ||||
| -rw-r--r-- | gcc/analyzer/trimmed-graph.cc | 172 | ||||
| -rw-r--r-- | gcc/analyzer/trimmed-graph.h | 122 | ||||
| -rw-r--r-- | gcc/doc/analyzer.texi | 56 | ||||
| -rw-r--r-- | gcc/doc/invoke.texi | 8 | ||||
| -rw-r--r-- | gcc/shortest-paths.h | 13 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/dot-output.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/feasibility-1.c | 16 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c | 8 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c | 2 |
20 files changed, 1366 insertions, 106 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index a63c5d9c..8a5fb3f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1254,6 +1254,7 @@ ANALYZER_OBJS = \ analyzer/constraint-manager.o \ analyzer/diagnostic-manager.o \ analyzer/engine.o \ + analyzer/feasible-graph.o \ analyzer/function-set.o \ analyzer/pending-diagnostic.o \ analyzer/program-point.o \ @@ -1273,7 +1274,8 @@ ANALYZER_OBJS = \ analyzer/state-purge.o \ analyzer/store.o \ analyzer/supergraph.o \ - analyzer/svalue.o + analyzer/svalue.o \ + analyzer/trimmed-graph.o # Language-independent object files. # We put the *-match.o and insn-*.o files first so that a parallel make diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt index 089d71e..dd34495 100644 --- a/gcc/analyzer/analyzer.opt +++ b/gcc/analyzer/analyzer.opt @@ -34,6 +34,10 @@ The maximum number of exploded nodes per program point within the analyzer, befo 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. @@ -206,6 +210,10 @@ 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. diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index e84953e..1a3535c 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -57,6 +57,8 @@ along with GCC; see the file COPYING3. If not see #include "analyzer/supergraph.h" #include "analyzer/program-state.h" #include "analyzer/exploded-graph.h" +#include "analyzer/trimmed-graph.h" +#include "analyzer/feasible-graph.h" #include "analyzer/checker-path.h" #include "analyzer/reachability.h" @@ -64,6 +66,8 @@ along with GCC; see the file COPYING3. If not see namespace ana { +class feasible_worklist; + /* State for finding the shortest feasible exploded_path for a saved_diagnostic. This is shared between all diagnostics, so that we avoid repeating work. */ @@ -73,19 +77,42 @@ class epath_finder public: epath_finder (const exploded_graph &eg) : m_eg (eg), - m_sep (eg, eg.get_origin (), SPS_FROM_GIVEN_ORIGIN) + m_sep (NULL) { + /* This is shared by all diagnostics, but only needed if + !flag_analyzer_feasibility. */ + if (!flag_analyzer_feasibility) + m_sep = new shortest_exploded_paths (eg, eg.get_origin (), + SPS_FROM_GIVEN_ORIGIN); } + ~epath_finder () { delete m_sep; } + logger *get_logger () const { return m_eg.get_logger (); } - exploded_path *get_best_epath (const exploded_node *enode, - const char *desc, + exploded_path *get_best_epath (const exploded_node *target_enode, + const char *desc, unsigned diag_idx, feasibility_problem **out_problem); private: + exploded_path *explore_feasible_paths (const exploded_node *target_enode, + const char *desc, unsigned diag_idx); + bool process_worklist_item (feasible_worklist *worklist, + const trimmed_graph &tg, + feasible_graph *fg, + const exploded_node *target_enode, + unsigned diag_idx, + exploded_path **out_best_path) const; + void dump_trimmed_graph (const exploded_node *target_enode, + const char *desc, unsigned diag_idx, + const trimmed_graph &tg, + const shortest_paths<eg_traits, exploded_path> &sep); + void dump_feasible_graph (const exploded_node *target_enode, + const char *desc, unsigned diag_idx, + const feasible_graph &fg); + const exploded_graph &m_eg; - shortest_exploded_paths m_sep; + shortest_exploded_paths *m_sep; }; /* class epath_finder. */ @@ -100,13 +127,13 @@ private: If flag_analyzer_feasibility is false, then simply return the shortest path. - Use DESC when logging. + Use DESC and DIAG_IDX when logging. - Write any feasiblity_problem to *OUT_PROBLEM. */ + Write any feasibility_problem to *OUT_PROBLEM. */ exploded_path * epath_finder::get_best_epath (const exploded_node *enode, - const char *desc, + const char *desc, unsigned diag_idx, feasibility_problem **out_problem) { logger *logger = get_logger (); @@ -114,52 +141,434 @@ epath_finder::get_best_epath (const exploded_node *enode, unsigned snode_idx = enode->get_supernode ()->m_index; if (logger) - logger->log ("considering %qs at EN: %i, SN: %i", - desc, enode->m_index, snode_idx); + logger->log ("considering %qs at EN: %i, SN: %i (sd: %i)", + desc, enode->m_index, snode_idx, diag_idx); /* State-merging means that not every path in the egraph corresponds to a feasible one w.r.t. states. We want to find the shortest feasible path from the origin to ENODE - in the egraph. + in the egraph. */ - As a crude approximation to this, we find the shortest path, and - determine if it is feasible. This could introduce false negatives, - as there could be longer feasible paths within the egraph. - (PR analyzer/96374). */ - - exploded_path *epath = new exploded_path (m_sep.get_shortest_path (enode)); - if (epath->feasible_p (logger, out_problem, m_eg.get_engine (), &m_eg)) + if (flag_analyzer_feasibility) { + /* Attempt to find the shortest feasible path using feasible_graph. */ if (logger) - logger->log ("accepting %qs at EN: %i, SN: %i with feasible path", - desc, enode->m_index, - snode_idx); + logger->log ("trying to find shortest feasible path"); + if (exploded_path *epath = explore_feasible_paths (enode, desc, diag_idx)) + { + if (logger) + logger->log ("accepting %qs at EN: %i, SN: %i (sd: %i)" + " with feasible path (length: %i)", + desc, enode->m_index, snode_idx, diag_idx, + epath->length ()); + return epath; + } + else + { + if (logger) + logger->log ("rejecting %qs at EN: %i, SN: %i (sd: %i)" + " due to not finding feasible path", + desc, enode->m_index, snode_idx, diag_idx); + return NULL; + } } else { - if (flag_analyzer_feasibility) + /* As a crude approximation to shortest feasible path, simply find + the shortest path, and note whether it is feasible. + There could be longer feasible paths within the egraph, so this + approach would lead to diagnostics being falsely rejected + (PR analyzer/96374). */ + if (logger) + logger->log ("trying to find shortest path ignoring feasibility"); + gcc_assert (m_sep); + exploded_path *epath + = new exploded_path (m_sep->get_shortest_path (enode)); + if (epath->feasible_p (logger, out_problem, m_eg.get_engine (), &m_eg)) { if (logger) - logger->log ("rejecting %qs at EN: %i, SN: %i" - " due to infeasible path", - desc, enode->m_index, - snode_idx); - delete epath; - return NULL; + logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i)" + " with feasible path (length: %i)", + desc, enode->m_index, snode_idx, diag_idx, + epath->length ()); } else { if (logger) - logger->log ("accepting %qs at EN: %i, SN: %i" + logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i) (length: %i)" " despite infeasible path (due to %qs)", - desc, enode->m_index, - snode_idx, + desc, enode->m_index, snode_idx, diag_idx, + epath->length (), "-fno-analyzer-feasibility"); } + return epath; + } +} + +/* A class for managing the worklist of feasible_nodes in + epath_finder::explore_feasible_paths, prioritizing them + so that shorter paths appear earlier in the queue. */ + +class feasible_worklist +{ +public: + feasible_worklist (const shortest_paths<eg_traits, exploded_path> &sep) + : m_queue (key_t (*this, NULL)), + m_sep (sep) + { + } + + feasible_node *take_next () { return m_queue.extract_min (); } + + void add_node (feasible_node *fnode) + { + m_queue.insert (key_t (*this, fnode), fnode); + } + +private: + struct key_t + { + key_t (const feasible_worklist &w, feasible_node *fnode) + : m_worklist (w), m_fnode (fnode) + {} + + bool operator< (const key_t &other) const + { + return cmp (*this, other) < 0; + } + + bool operator== (const key_t &other) const + { + return cmp (*this, other) == 0; + } + + bool operator> (const key_t &other) const + { + return !(*this == other || *this < other); + } + + private: + static int cmp (const key_t &ka, const key_t &kb) + { + /* Choose the node for which if the remaining path were feasible, + it would be the shortest path (summing the length of the + known-feasible path so far with that of the remaining + possibly-feasible path). */ + int ca = ka.m_worklist.get_estimated_cost (ka.m_fnode); + int cb = kb.m_worklist.get_estimated_cost (kb.m_fnode); + return ca - cb; + } + + const feasible_worklist &m_worklist; + feasible_node *m_fnode; + }; + + /* Get the estimated length of a path involving FNODE from + the origin to the target enode. + Sum the length of the known-feasible path so far with + that of the remaining possibly-feasible path. */ + + int get_estimated_cost (const feasible_node *fnode) const + { + unsigned length_so_far = fnode->get_path_length (); + int shortest_remaining_path + = m_sep.get_shortest_distance (fnode->get_inner_node ()); + + gcc_assert (shortest_remaining_path >= 0); + /* This should be true since we're only exploring nodes within + the trimmed graph (and we anticipate it being much smaller + than this, and thus not overflowing the sum). */ + gcc_assert (shortest_remaining_path < INT_MAX); + + return length_so_far + shortest_remaining_path; + } + + /* Priority queue, backed by a fibonacci_heap. */ + typedef fibonacci_heap<key_t, feasible_node> queue_t; + queue_t m_queue; + const shortest_paths<eg_traits, exploded_path> &m_sep; +}; + +/* Attempt to find the shortest feasible path from the origin to + TARGET_ENODE by iteratively building a feasible_graph, in which + every path to a feasible_node is feasible by construction. + + We effectively explore the tree of feasible paths in order of shortest + path until we either find a feasible path to TARGET_ENODE, or hit + a limit and give up. + + Preliminaries: + - Find the shortest path from each node to the TARGET_ENODE (without + checking feasibility), so that we can prioritize our worklist. + - Construct a trimmed_graph: the subset of nodes/edges that + are on a path that eventually reaches TARGET_ENODE. We will only need + to consider these when considering the shortest feasible path. + + Build a feasible_graph, in which every path to a feasible_node + is feasible by construction. + We use a worklist to flatten the exploration into an iteration. + Starting at the origin, find feasible out-edges within the trimmed graph. + At each stage, choose the node for which if the remaining path were feasible, + it would be the shortest path (summing the length of the known-feasible path + so far with that of the remaining possibly-feasible path). + This way, the first feasible path we find to TARGET_ENODE is the shortest. + We start by trying the shortest possible path, but if that fails, + we explore progressively longer paths, eventually trying iterations through + loops. The exploration is captured in the feasible_graph, which can be + dumped as a .dot file to visualize the exploration. The indices of the + feasible_nodes show the order in which they were created. + + This is something of a brute-force approach, but the trimmed_graph + hopefully keeps the complexity manageable. + + Terminate with failure when the number of infeasible edges exceeds + a threshold (--param=analyzer-max-infeasible-edges=). + This is guaranteed to eventually lead to terminatation, as + we can't keep creating feasible nodes without eventually + either reaching an infeasible edge, or reaching the + TARGET_ENODE. Specifically, there can't be a cycle of + feasible edges that doesn't reach the target_enode without + an out-edge that either fails feasibility or gets closer + to the TARGET_ENODE: on each iteration we are either: + - effectively getting closer to the TARGET_ENODE (which can't + continue forever without reaching the target), or + - getting monotonically closer to the termination threshold. */ + +exploded_path * +epath_finder::explore_feasible_paths (const exploded_node *target_enode, + const char *desc, unsigned diag_idx) +{ + logger *logger = get_logger (); + LOG_SCOPE (logger); + + /* Determine the shortest path to TARGET_ENODE from each node in + the exploded graph. */ + shortest_paths<eg_traits, exploded_path> sep + (m_eg, target_enode, SPS_TO_GIVEN_TARGET); + + /* Construct a trimmed_graph: the subset of nodes/edges that + are on a path that eventually reaches TARGET_ENODE. + We only need to consider these when considering the shortest + feasible path. */ + trimmed_graph tg (m_eg, target_enode); + + if (flag_dump_analyzer_feasibility) + dump_trimmed_graph (target_enode, desc, diag_idx, tg, sep); + + feasible_graph fg; + feasible_worklist worklist (sep); + + /* Populate the worklist with the origin node. */ + { + feasibility_state init_state (m_eg.get_engine ()->get_model_manager (), + m_eg.get_supergraph ()); + feasible_node *origin = fg.add_node (m_eg.get_origin (), init_state, 0); + worklist.add_node (origin); + } + + /* Iteratively explore the tree of feasible paths in order of shortest + path until we either find a feasible path to TARGET_ENODE, or hit + a limit. */ + + /* Set this if we find a feasible path to TARGET_ENODE. */ + exploded_path *best_path = NULL; + + while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx, + &best_path)) + { + /* Empty; the work is done within process_worklist_item. */ } - return epath; + if (logger) + { + logger->log ("tg for sd: %i:", diag_idx); + logger->inc_indent (); + tg.log_stats (logger); + logger->dec_indent (); + + logger->log ("fg for sd: %i:", diag_idx); + logger->inc_indent (); + fg.log_stats (logger); + logger->dec_indent (); + } + + /* Dump the feasible_graph. */ + if (flag_dump_analyzer_feasibility) + dump_feasible_graph (target_enode, desc, diag_idx, fg); + + return best_path; +} + +/* Process the next item in WORKLIST, potentially adding new items + based on feasible out-edges, and extending FG accordingly. + Use TG to ignore out-edges that don't lead to TARGET_ENODE. + Return true if the worklist processing should continue. + Return false if the processing of the worklist should stop + (either due to reaching TARGET_ENODE, or hitting a limit). + Write to *OUT_BEST_PATH if stopping due to finding a feasible path + to TARGET_ENODE. */ + +bool +epath_finder::process_worklist_item (feasible_worklist *worklist, + const trimmed_graph &tg, + feasible_graph *fg, + const exploded_node *target_enode, + unsigned diag_idx, + exploded_path **out_best_path) const +{ + logger *logger = get_logger (); + + feasible_node *fnode = worklist->take_next (); + if (!fnode) + { + if (logger) + logger->log ("drained worklist for sd: %i" + " without finding feasible path", + diag_idx); + return false; + } + + log_scope s (logger, "fg worklist item", + "considering FN: %i (EN: %i) for sd: %i", + fnode->get_index (), fnode->get_inner_node ()->m_index, + diag_idx); + + /* Iterate through all out-edges from this item. */ + unsigned i; + exploded_edge *succ_eedge; + FOR_EACH_VEC_ELT (fnode->get_inner_node ()->m_succs, i, succ_eedge) + { + log_scope s (logger, "edge", "considering edge: EN:%i -> EN:%i", + succ_eedge->m_src->m_index, + succ_eedge->m_dest->m_index); + /* Reject edges that aren't in the trimmed graph. */ + if (!tg.contains_p (succ_eedge)) + { + if (logger) + logger->log ("rejecting: not in trimmed graph"); + continue; + } + + feasibility_state succ_state (fnode->get_state ()); + rejected_constraint *rc = NULL; + if (succ_state.maybe_update_for_edge (logger, succ_eedge, &rc)) + { + gcc_assert (rc == NULL); + feasible_node *succ_fnode + = fg->add_node (succ_eedge->m_dest, + succ_state, + fnode->get_path_length () + 1); + if (logger) + logger->log ("accepting as FN: %i", succ_fnode->get_index ()); + fg->add_edge (new feasible_edge (fnode, succ_fnode, succ_eedge)); + + /* Have we reached TARGET_ENODE? */ + if (succ_fnode->get_inner_node () == target_enode) + { + if (logger) + logger->log ("success: got feasible path to EN: %i (sd: %i)" + " (length: %i)", + target_enode->m_index, diag_idx, + succ_fnode->get_path_length ()); + *out_best_path = fg->make_epath (succ_fnode); + /* Success: stop the worklist iteration. */ + return false; + } + else + worklist->add_node (succ_fnode); + } + else + { + if (logger) + logger->log ("infeasible"); + gcc_assert (rc); + fg->add_feasibility_problem (fnode, + succ_eedge, + *rc); + delete rc; + + /* Give up if there have been too many infeasible edges. */ + if (fg->get_num_infeasible () + > (unsigned)param_analyzer_max_infeasible_edges) + { + if (logger) + logger->log ("too many infeasible edges (%i); giving up", + fg->get_num_infeasible ()); + return false; + } + } + } + + /* Continue the worklist iteration. */ + return true; +} + +/* Helper class for epath_finder::dump_trimmed_graph + to dump extra per-node information. + Use SEP to add the length of the shortest path from each + node to the target node to each node's dump. */ + +class dump_eg_with_shortest_path : public eg_traits::dump_args_t +{ +public: + dump_eg_with_shortest_path + (const exploded_graph &eg, + const shortest_paths<eg_traits, exploded_path> &sep) + : dump_args_t (eg), + m_sep (sep) + { + } + + void dump_extra_info (const exploded_node *enode, + pretty_printer *pp) const FINAL OVERRIDE + { + pp_printf (pp, "sp: %i", m_sep.get_shortest_path (enode).length ()); + pp_newline (pp); + } + +private: + const shortest_paths<eg_traits, exploded_path> &m_sep; +}; + +/* Dump TG to "BASE_NAME.DESC.DIAG_IDX.to-enN.tg.dot", + annotating each node with the length of the shortest path + from that node to TARGET_ENODE (using SEP). */ + +void +epath_finder:: +dump_trimmed_graph (const exploded_node *target_enode, + const char *desc, unsigned diag_idx, + const trimmed_graph &tg, + const shortest_paths<eg_traits, exploded_path> &sep) +{ + auto_timevar tv (TV_ANALYZER_DUMP); + dump_eg_with_shortest_path inner_args (m_eg, sep); + trimmed_graph::dump_args_t args (inner_args); + pretty_printer pp; + pp_printf (&pp, "%s.%s.%i.to-en%i.tg.dot", + dump_base_name, desc, diag_idx, target_enode->m_index); + char *filename = xstrdup (pp_formatted_text (&pp)); + tg.dump_dot (filename, NULL, args); + free (filename); +} + +/* Dump FG to "BASE_NAME.DESC.DIAG_IDX.to-enN.fg.dot". */ + +void +epath_finder::dump_feasible_graph (const exploded_node *target_enode, + const char *desc, unsigned diag_idx, + const feasible_graph &fg) +{ + auto_timevar tv (TV_ANALYZER_DUMP); + exploded_graph::dump_args_t inner_args (m_eg); + feasible_graph::dump_args_t args (inner_args); + pretty_printer pp; + pp_printf (&pp, "%s.%s.%i.to-en%i.fg.dot", + dump_base_name, desc, diag_idx, target_enode->m_index); + char *filename = xstrdup (pp_formatted_text (&pp)); + fg.dump_dot (filename, NULL, args); + free (filename); } /* class saved_diagnostic. */ @@ -174,13 +583,15 @@ saved_diagnostic::saved_diagnostic (const state_machine *sm, tree var, const svalue *sval, state_machine::state_t state, - pending_diagnostic *d) + pending_diagnostic *d, + unsigned idx) : m_sm (sm), m_enode (enode), m_snode (snode), m_stmt (stmt), /* stmt_finder could be on-stack; we want our own copy that can outlive that. */ m_stmt_finder (stmt_finder ? stmt_finder->clone () : NULL), m_var (var), m_sval (sval), m_state (state), m_d (d), m_trailing_eedge (NULL), + m_idx (idx), m_best_epath (NULL), m_problem (NULL) { gcc_assert (m_stmt || m_stmt_finder); @@ -221,7 +632,8 @@ saved_diagnostic::operator== (const saved_diagnostic &other) const "sval": optional str, "state": optional str, "path_length": optional int, - "pending_diagnostic": str}. */ + "pending_diagnostic": str, + "idx": int}. */ json::object * saved_diagnostic::to_json () const @@ -239,6 +651,7 @@ saved_diagnostic::to_json () const if (m_best_epath) sd_obj->set ("path_length", new json::integer_number (get_epath_length ())); sd_obj->set ("pending_diagnostic", new json::string (m_d->get_kind ())); + sd_obj->set ("idx", new json::integer_number (m_idx)); /* We're not yet JSONifying the following fields: const gimple *m_stmt; @@ -267,15 +680,12 @@ saved_diagnostic::calc_best_epath (epath_finder *pf) delete m_problem; m_problem = NULL; - m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (), + m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (), m_idx, &m_problem); /* Handle failure to find a feasible path. */ if (m_best_epath == NULL) - { - gcc_assert (m_problem); - return false; - } + return false; gcc_assert (m_best_epath); if (m_stmt == NULL) @@ -395,11 +805,11 @@ diagnostic_manager::add_diagnostic (const state_machine *sm, saved_diagnostic *sd = new saved_diagnostic (sm, enode, snode, stmt, finder, var, sval, - state, d); + state, d, m_saved_diagnostics.length ()); m_saved_diagnostics.safe_push (sd); if (get_logger ()) log ("adding saved diagnostic %i at SN %i: %qs", - m_saved_diagnostics.length () - 1, + sd->get_index (), snode->m_index, d->get_kind ()); } diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h index c558078..1454977 100644 --- a/gcc/analyzer/diagnostic-manager.h +++ b/gcc/analyzer/diagnostic-manager.h @@ -36,7 +36,8 @@ public: stmt_finder *stmt_finder, tree var, const svalue *sval, state_machine::state_t state, - pending_diagnostic *d); + pending_diagnostic *d, + unsigned idx); ~saved_diagnostic (); bool operator== (const saved_diagnostic &other) const; @@ -55,6 +56,8 @@ public: void add_duplicate (saved_diagnostic *other); unsigned get_num_dupes () const { return m_duplicates.length (); } + unsigned get_index () const { return m_idx; } + //private: const state_machine *m_sm; const exploded_node *m_enode; @@ -70,6 +73,7 @@ public: private: DISABLE_COPY_AND_ASSIGN (saved_diagnostic); + unsigned m_idx; exploded_path *m_best_epath; // owned feasibility_problem *m_problem; // owned diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index fef4823..5792c14 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -946,41 +946,12 @@ exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const state.dump_to_pp (ext_state, false, true, pp); pp_newline (pp); - /* Show any stmts that were processed within this enode, - and their index within the supernode. */ - if (m_num_processed_stmts > 0) - { - const program_point &point = get_point (); - gcc_assert (point.get_kind () == PK_BEFORE_STMT); - const supernode *snode = get_supernode (); - const unsigned int point_stmt_idx = point.get_stmt_idx (); - - pp_printf (pp, "stmts: %i", m_num_processed_stmts); - pp_newline (pp); - for (unsigned i = 0; i < m_num_processed_stmts; i++) - { - const unsigned int idx_within_snode = point_stmt_idx + i; - const gimple *stmt = snode->m_stmts[idx_within_snode]; - pp_printf (pp, " %i: ", idx_within_snode); - pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0); - pp_newline (pp); - } - } + dump_processed_stmts (pp); } - /* Dump any saved_diagnostics at this enode. */ - { - const diagnostic_manager &dm = args.m_eg.get_diagnostic_manager (); - for (unsigned i = 0; i < dm.get_num_diagnostics (); i++) - { - const saved_diagnostic *sd = dm.get_saved_diagnostic (i); - if (sd->m_enode == this) - { - pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ()); - pp_newline (pp); - } - } - } + dump_saved_diagnostics (pp, args.m_eg.get_diagnostic_manager ()); + + args.dump_extra_info (this, pp); pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true); @@ -988,6 +959,49 @@ exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const pp_flush (pp); } +/* Show any stmts that were processed within this enode, + and their index within the supernode. */ +void +exploded_node::dump_processed_stmts (pretty_printer *pp) const +{ + if (m_num_processed_stmts > 0) + { + const program_point &point = get_point (); + gcc_assert (point.get_kind () == PK_BEFORE_STMT); + const supernode *snode = get_supernode (); + const unsigned int point_stmt_idx = point.get_stmt_idx (); + + pp_printf (pp, "stmts: %i", m_num_processed_stmts); + pp_newline (pp); + for (unsigned i = 0; i < m_num_processed_stmts; i++) + { + const unsigned int idx_within_snode = point_stmt_idx + i; + const gimple *stmt = snode->m_stmts[idx_within_snode]; + pp_printf (pp, " %i: ", idx_within_snode); + pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0); + pp_newline (pp); + } + } +} + +/* Dump any saved_diagnostics at this enode to PP. */ + +void +exploded_node::dump_saved_diagnostics (pretty_printer *pp, + const diagnostic_manager &dm) const +{ + for (unsigned i = 0; i < dm.get_num_diagnostics (); i++) + { + const saved_diagnostic *sd = dm.get_saved_diagnostic (i); + if (sd->m_enode == this) + { + pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)", + sd->m_d->get_kind (), sd->get_index ()); + pp_newline (pp); + } + } +} + /* Dump this to PP in a form suitable for use as an id in .dot output. */ void @@ -1639,6 +1653,18 @@ exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const { pretty_printer *pp = gv->get_pp (); + m_src->dump_dot_id (pp); + pp_string (pp, " -> "); + m_dest->dump_dot_id (pp); + dump_dot_label (pp); +} + +/* Second half of exploded_edge::dump_dot. This is split out + for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */ + +void +exploded_edge::dump_dot_label (pretty_printer *pp) const +{ const char *style = "\"solid,bold\""; const char *color = "black"; int weight = 10; @@ -1669,9 +1695,6 @@ exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const style = "\"dotted\""; } - m_src->dump_dot_id (pp); - pp_string (pp, " -> "); - m_dest->dump_dot_id (pp); pp_printf (pp, (" [style=%s, color=%s, weight=%d, constraint=%s," " headlabel=\""), @@ -3352,6 +3375,10 @@ exploded_graph::to_json () const return egraph_obj; } +/* class exploded_path. */ + +/* Copy ctor. */ + exploded_path::exploded_path (const exploded_path &other) : m_edges (other.m_edges.length ()) { diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index da1cebb..deb739f 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -135,6 +135,9 @@ struct eg_traits bool show_enode_details_p (const exploded_node &enode) const; + virtual void + dump_extra_info (const exploded_node *, pretty_printer *) const {} + const exploded_graph &m_eg; }; typedef exploded_cluster cluster_t; @@ -182,6 +185,10 @@ class exploded_node : public dnode<eg_traits> void dump (FILE *fp, const extrinsic_state &ext_state) const; void dump (const extrinsic_state &ext_state) const; + void dump_processed_stmts (pretty_printer *pp) const; + void dump_saved_diagnostics (pretty_printer *pp, + const diagnostic_manager &dm) const; + json::object *to_json (const extrinsic_state &ext_state) const; /* The result of on_stmt. */ @@ -311,6 +318,7 @@ class exploded_edge : public dedge<eg_traits> ~exploded_edge (); void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE; + void dump_dot_label (pretty_printer *pp) const; json::object *to_json () const; diff --git a/gcc/analyzer/feasible-graph.cc b/gcc/analyzer/feasible-graph.cc new file mode 100644 index 0000000..bb409d6 --- /dev/null +++ b/gcc/analyzer/feasible-graph.cc @@ -0,0 +1,235 @@ +/* A graph for exploring trees of feasible paths through the egraph. + Copyright (C) 2021 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +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/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "pretty-print.h" +#include "gcc-rich-location.h" +#include "gimple-pretty-print.h" +#include "function.h" +#include "diagnostic-core.h" +#include "diagnostic-event-id.h" +#include "diagnostic-path.h" +#include "alloc-pool.h" +#include "fibonacci_heap.h" +#include "shortest-paths.h" +#include "sbitmap.h" +#include "bitmap.h" +#include "tristate.h" +#include "selftest.h" +#include "ordered-hash-map.h" +#include "json.h" +#include "analyzer/analyzer.h" +#include "analyzer/analyzer-logging.h" +#include "analyzer/sm.h" +#include "analyzer/pending-diagnostic.h" +#include "analyzer/diagnostic-manager.h" +#include "analyzer/call-string.h" +#include "analyzer/program-point.h" +#include "analyzer/store.h" +#include "analyzer/region-model.h" +#include "analyzer/constraint-manager.h" +#include "cfg.h" +#include "basic-block.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "cgraph.h" +#include "digraph.h" +#include "analyzer/supergraph.h" +#include "analyzer/program-state.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/feasible-graph.h" + +#if ENABLE_ANALYZER + +namespace ana { + +/* class base_feasible_node : public dnode<fg_traits>. */ + +/* Print an id to PP for this node suitable for use in .dot dumps. */ + +void +base_feasible_node::dump_dot_id (pretty_printer *pp) const +{ + pp_printf (pp, "fnode_%i", m_index); +} + +/* class feasible_node : public base_feasible_node. */ + +/* Implementation of dump_dot vfunc for feasible_node. */ + +void +feasible_node::dump_dot (graphviz_out *gv, + const dump_args_t &args) const +{ + pretty_printer *pp = gv->get_pp (); + + dump_dot_id (pp); + pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"", + m_inner_node->get_dot_fillcolor ()); + pp_write_text_to_stream (pp); + + pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index, + m_path_length); + pp_newline (pp); + + format f (true); + m_inner_node->get_point ().print (pp, f); + pp_newline (pp); + + /* Show the model at this point along expansion of the feasible path, + rather than the model within the enode. */ + m_state.get_model ().dump_to_pp (pp, true, true); + pp_newline (pp); + + m_inner_node->dump_processed_stmts (pp); + m_inner_node->dump_saved_diagnostics + (pp, args.m_inner_args.m_eg.get_diagnostic_manager ()); + + pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true); + + pp_string (pp, "\"];\n\n"); + pp_flush (pp); +} + +/* Implementation of dump_dot vfunc for infeasible_node. + In particular, show the rejected constraint. */ + +void +infeasible_node::dump_dot (graphviz_out *gv, + const dump_args_t &) const +{ + pretty_printer *pp = gv->get_pp (); + + dump_dot_id (pp); + pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"", + m_inner_node->get_dot_fillcolor ()); + pp_write_text_to_stream (pp); + + pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index); + pp_newline (pp); + + pp_string (pp, "rejected constraint:"); + pp_newline (pp); + m_rc.dump_to_pp (pp); + + pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true); + + pp_string (pp, "\"];\n\n"); + pp_flush (pp); +} + +/* class base_feasible_edge : public dedge<fg_traits>. */ + +/* Implementation of dump_dot vfunc for base_easible_edge. */ + +void +base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const +{ + pretty_printer *pp = gv->get_pp (); + + m_src->dump_dot_id (pp); + pp_string (pp, " -> "); + m_dest->dump_dot_id (pp); + + m_inner_edge->dump_dot_label (pp); +} + +/* class feasible_graph : public digraph <fg_traits>. */ + +/* Ctor for feasible_graph. */ + +feasible_graph::feasible_graph () +: m_num_infeasible (0) +{ +} + +/* Add a feasible_node to this graph for ENODE, STATE with the + given PATH_LENGTH. */ + +feasible_node * +feasible_graph::add_node (const exploded_node *enode, + const feasibility_state &state, + unsigned path_length) +{ + /* We don't attempt get_or_create here. */ + feasible_node *fnode = new feasible_node (enode, m_nodes.length (), + state, path_length); + digraph<fg_traits>::add_node (fnode); + return fnode; +} + +/* Add an infeasible_node to this graph and an infeasible_edge connecting + to it from SRC_FNODE, capturing a failure of RC along EEDGE. */ + +void +feasible_graph::add_feasibility_problem (feasible_node *src_fnode, + const exploded_edge *eedge, + const rejected_constraint &rc) +{ + infeasible_node *dst_fnode + = new infeasible_node (eedge->m_dest, m_nodes.length (), rc); + digraph<fg_traits>::add_node (dst_fnode); + add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge)); + m_num_infeasible++; +} + +/* Make an exploded_path from the origin to FNODE's exploded_node, + following the edges in the feasible_graph. */ + +exploded_path * +feasible_graph::make_epath (feasible_node *fnode) const +{ + exploded_path *epath = new exploded_path (); + + /* FG is actually a tree. Built the path backwards, by walking + backwards from FNODE until we reach the origin. */ + while (fnode->get_inner_node ()->m_index != 0) + { + gcc_assert (fnode->m_preds.length () == 1); + feasible_edge *pred_fedge + = static_cast <feasible_edge *> (fnode->m_preds[0]); + epath->m_edges.safe_push (pred_fedge->get_inner_edge ()); + fnode = static_cast <feasible_node *> (pred_fedge->m_src); + } + + /* Now reverse it. */ + epath->m_edges.reverse (); + + return epath; +} + +/* Dump stats about this graph to LOGGER. */ + +void +feasible_graph::log_stats (logger *logger) const +{ + logger->log ("#nodes: %i", m_nodes.length ()); + logger->log ("#edges: %i", m_edges.length ()); + logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible); + logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible); + logger->log ("#infeasible nodes/edges: %i", m_num_infeasible); +} + +} // namespace ana + +#endif /* #if ENABLE_ANALYZER */ diff --git a/gcc/analyzer/feasible-graph.h b/gcc/analyzer/feasible-graph.h new file mode 100644 index 0000000..5a580f4 --- /dev/null +++ b/gcc/analyzer/feasible-graph.h @@ -0,0 +1,213 @@ +/* A graph for exploring trees of feasible paths through the egraph. + Copyright (C) 2021 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +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/>. */ + +#ifndef GCC_ANALYZER_FEASIBLE_GRAPH_H +#define GCC_ANALYZER_FEASIBLE_GRAPH_H + +namespace ana { + +/* Forward decls. */ + +class base_feasible_node; + class feasible_node; + class infeasible_node; +class base_feasible_edge; + class feasible_edge; + class infeasible_edge; +class feasible_graph; +class feasible_cluster; + +/* A traits class for feasible_graph. */ + +struct fg_traits +{ + typedef base_feasible_node node_t; + typedef base_feasible_edge edge_t; + typedef feasible_graph graph_t; + struct dump_args_t + { + typedef typename eg_traits::dump_args_t inner_args_t; + + dump_args_t (const inner_args_t &inner_args) + : m_inner_args (inner_args) + { + } + + const inner_args_t &m_inner_args; + }; + typedef feasible_cluster cluster_t; +}; + +/* Base class of node within a feasible_graph. + There can be 0 or more base_feasible_nodes per exploded_node. */ + +class base_feasible_node : public dnode<fg_traits> +{ + public: + void dump_dot_id (pretty_printer *pp) const; + + const exploded_node *get_inner_node () const { return m_inner_node; } + unsigned get_index () const { return m_index; } + + protected: + base_feasible_node (const exploded_node *inner_node, unsigned index) + : m_inner_node (inner_node), m_index (index) + {} + + const exploded_node *m_inner_node; + unsigned m_index; +}; + +/* Subclass of base_feasible_node for a node that is reachable via a + feasible path, with a particular state. */ + +class feasible_node : public base_feasible_node +{ +public: + feasible_node (const exploded_node *inner_node, unsigned index, + const feasibility_state &state, + unsigned path_length) + : base_feasible_node (inner_node, index), + m_state (state), + m_path_length (path_length) + { + } + + void dump_dot (graphviz_out *gv, + const dump_args_t &args) const FINAL OVERRIDE; + + const feasibility_state &get_state () const { return m_state; } + const region_model &get_model () const { return m_state.get_model (); } + const auto_sbitmap &get_snodes_visited () const + { + return m_state.get_snodes_visited (); + } + + unsigned get_path_length () const { return m_path_length; } + +private: + feasibility_state m_state; + unsigned m_path_length; +}; + +/* Subclass of base_feasible_node for a node that requires following + an infeasible edge to reach (and thus terminating this part of the + exploration). */ + +class infeasible_node : public base_feasible_node +{ +public: + infeasible_node (const exploded_node *inner_node, unsigned index, + const rejected_constraint &rc) + : base_feasible_node (inner_node, index), + m_rc (rc) + { + } + + void dump_dot (graphviz_out *gv, + const dump_args_t &args) const FINAL OVERRIDE; + +private: + rejected_constraint m_rc; +}; + +/* Base class of edge within a feasible_graph. */ + +class base_feasible_edge : public dedge<fg_traits> +{ + public: + void dump_dot (graphviz_out *gv, + const dump_args_t &args) const FINAL OVERRIDE; + + const exploded_edge *get_inner_edge () const { return m_inner_edge; } + + protected: + base_feasible_edge (base_feasible_node *src, base_feasible_node *dest, + const exploded_edge *inner_edge) + : dedge<fg_traits> (src, dest), m_inner_edge (inner_edge) + { + } + + const exploded_edge *m_inner_edge; +}; + +/* Subclass of base_feasible_edge for connecting two feasible_nodes. */ + +class feasible_edge : public base_feasible_edge +{ + public: + feasible_edge (feasible_node *src, feasible_node *dest, + const exploded_edge *inner_edge) + : base_feasible_edge (src, dest, inner_edge) + { + } +}; + +/* Subclass of base_feasible_edge for connecting a feasible_node + to an infeasible_node (and thus terminating this part of the + exploration). */ + +class infeasible_edge : public base_feasible_edge +{ + public: + infeasible_edge (feasible_node *src, infeasible_node *dest, + const exploded_edge *inner_edge) + : base_feasible_edge (src, dest, inner_edge) + { + } +}; + +/* A digraph subclass for exploring trees of feasible paths through + the egraph. This is actually a tree. + + The paths within the graph of feasible_nodes express feasible paths + through the graph, and it also captures known infeasible edges, + which is invaluable for debugging. */ + +class feasible_graph : public digraph <fg_traits> +{ + public: + feasible_graph (); + + feasible_node *add_node (const exploded_node *enode, + const feasibility_state &state, + unsigned path_length); + + void add_feasibility_problem (feasible_node *src_fnode, + const exploded_edge *eedge, + const rejected_constraint &rc); + + exploded_path *make_epath (feasible_node *fnode) const; + + unsigned get_num_infeasible () const { return m_num_infeasible; } + + void log_stats (logger *logger) const; + +private: + unsigned m_num_infeasible; +}; + +class feasible_cluster : public cluster <fg_traits> +{ +}; + +} // namespace ana + +#endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */ diff --git a/gcc/analyzer/trimmed-graph.cc b/gcc/analyzer/trimmed-graph.cc new file mode 100644 index 0000000..2e23a09 --- /dev/null +++ b/gcc/analyzer/trimmed-graph.cc @@ -0,0 +1,172 @@ +/* Trimming an exploded graph to a subset of nodes and edges. + Copyright (C) 2021 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +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/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "pretty-print.h" +#include "gcc-rich-location.h" +#include "gimple-pretty-print.h" +#include "function.h" +#include "diagnostic-core.h" +#include "diagnostic-event-id.h" +#include "diagnostic-path.h" +#include "alloc-pool.h" +#include "fibonacci_heap.h" +#include "shortest-paths.h" +#include "sbitmap.h" +#include "bitmap.h" +#include "tristate.h" +#include "selftest.h" +#include "ordered-hash-map.h" +#include "json.h" +#include "analyzer/analyzer.h" +#include "analyzer/analyzer-logging.h" +#include "analyzer/sm.h" +#include "analyzer/pending-diagnostic.h" +#include "analyzer/diagnostic-manager.h" +#include "analyzer/call-string.h" +#include "analyzer/program-point.h" +#include "analyzer/store.h" +#include "analyzer/region-model.h" +#include "analyzer/constraint-manager.h" +#include "cfg.h" +#include "basic-block.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "cgraph.h" +#include "digraph.h" +#include "analyzer/supergraph.h" +#include "analyzer/program-state.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/trimmed-graph.h" + +#if ENABLE_ANALYZER + +namespace ana { + +/* class trimmed_node : public dnode<tg_traits>. */ + +/* Implementation of dump_dot vfunc, delegating to the inner node. */ + +void +trimmed_node::dump_dot (graphviz_out *gv, + const dump_args_t &args) const +{ + m_inner_node->dump_dot (gv, args.m_inner_args); +} + +/* class trimmed_edge : public dedge<tg_traits>. */ + +/* trimmed_edge's ctor. */ + +trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest, + const exploded_edge *inner_edge) +: dedge<tg_traits> (src, dest), m_inner_edge (inner_edge) +{ +} + +/* Implementation of dump_dot vfunc, delegating to the inner edge. */ + +void +trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const +{ + m_inner_edge->dump_dot (gv, args.m_inner_args); +} + +/* class trimmed_graph : public digraph <tg_traits>. */ + +/* Ctor for trimmed_graph: construct a graph equivalent to trimming + INNER_GRAPH to all nodes that can reach INNER_DST_NODE. */ + +trimmed_graph::trimmed_graph (const exploded_graph &inner_graph, + const exploded_node *inner_dst_node) +: m_enodes (), m_eedges () +{ + /* Determine what subset of nodes and edges to include in the + trimmed graph. + Walk backwards from INNER_DST_NODE, finding nodes that reach it, + iteratively building the set of nodes and edges. */ + auto_vec <const exploded_node *> worklist; + worklist.safe_push (inner_dst_node); + m_enodes.add (inner_dst_node); + while (worklist.length () > 0) + { + const exploded_node *inner_node = worklist.pop (); + exploded_edge *inner_pred; + unsigned i; + FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred) + { + if (!m_enodes.contains (inner_pred->m_src)) + { + worklist.safe_push (inner_pred->m_src); + m_enodes.add (inner_pred->m_src); + } + m_eedges.add (inner_pred); + } + } + + /* Create trimmed nodes for all enodes in the set. */ + { + /* Iterate over the vec rather than the hash_set + to ensure deterministic order. */ + exploded_node *inner_node; + unsigned i; + FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node) + if (m_enodes.contains (inner_node)) + { + trimmed_node *tnode = new trimmed_node (inner_node); + add_node (tnode); + m_map_from_enode_to_tnode.put (inner_node, tnode); + } + } + + /* Create trimmed edges for all edges in the set. */ + { + /* Iterate over the vec rather than the hash_set + to ensure deterministic order. */ + exploded_edge *inner_edge; + unsigned i; + FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge) + if (m_eedges.contains (inner_edge)) + { + const exploded_node *inner_src = inner_edge->m_src; + const exploded_node *inner_dest = inner_edge->m_dest; + trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src); + trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest); + trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge); + add_edge (tedge); + } + } +} + +/* Dump stats about this graph to LOGGER. */ + +void +trimmed_graph::log_stats (logger *logger) const +{ + logger->log ("#nodes: %i", m_nodes.length ()); + logger->log ("#edges: %i", m_edges.length ()); +} + +} // namespace ana + +#endif /* #if ENABLE_ANALYZER */ diff --git a/gcc/analyzer/trimmed-graph.h b/gcc/analyzer/trimmed-graph.h new file mode 100644 index 0000000..bfe243a --- /dev/null +++ b/gcc/analyzer/trimmed-graph.h @@ -0,0 +1,122 @@ +/* Trimming an exploded graph to a subset of nodes and edges. + Copyright (C) 2021 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +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/>. */ + +#ifndef GCC_ANALYZER_TRIMMED_GRAPH_H +#define GCC_ANALYZER_TRIMMED_GRAPH_H + +namespace ana { + +/* Forward decls. */ + +class trimmed_node; +class trimmed_edge; +class trimmed_graph; +class trimmed_cluster; + +/* A traits class for trimming a digraph to a subset of nodes and edges. */ + +struct tg_traits +{ + typedef trimmed_node node_t; + typedef trimmed_edge edge_t; + typedef trimmed_graph graph_t; + struct dump_args_t + { + typedef typename eg_traits::dump_args_t inner_args_t; + + dump_args_t (const inner_args_t &inner_args) + : m_inner_args (inner_args) + { + } + + const inner_args_t &m_inner_args; + }; + typedef trimmed_cluster cluster_t; +}; + +/* A node within the trimmed_graph, corresponding to an "inner node" + within the original exploded_graph. */ + +class trimmed_node : public dnode<tg_traits> +{ +public: + trimmed_node (const exploded_node *inner_node) + : m_inner_node (inner_node) {} + + void dump_dot (graphviz_out *gv, + const dump_args_t &args) const FINAL OVERRIDE; + +private: + const exploded_node *m_inner_node; +}; + +/* An edge within the trimmed_graph, corresponding to an "inner edge" + within the original exploded_graph. */ + +class trimmed_edge : public dedge<tg_traits> +{ + public: + trimmed_edge (trimmed_node *src, trimmed_node *dest, + const exploded_edge *inner_edge); + + void dump_dot (graphviz_out *gv, + const dump_args_t &args) const FINAL OVERRIDE; + + private: + const exploded_edge *m_inner_edge; +}; + +/* A digraph for trimming an exploded_graph to the subset of nodes and edges + from which paths reach INNER_DST_NODE (along with a precanned way to print + these in .dot form). */ + +class trimmed_graph : public digraph <tg_traits> +{ + public: + trimmed_graph (const exploded_graph &inner_graph, + const exploded_node *inner_dst_node); + + bool contains_p (const exploded_edge *eedge) const + { + hash_set <const exploded_edge *> & mut + = const_cast <hash_set <const exploded_edge *> &> (m_eedges); + return mut.contains (eedge); + } + + void log_stats (logger *logger) const; + + private: + /* The subset of nodes in the inner graph that are in the + trimmed graph. */ + hash_set <const exploded_node *> m_enodes; + /* Likewise for edges. */ + hash_set <const exploded_edge *> m_eedges; + + typedef hash_map<const exploded_node *, trimmed_node *> map_t; + map_t m_map_from_enode_to_tnode; +}; + +class trimmed_cluster : public cluster <tg_traits> +{ +}; + +} // namespace ana + +#endif /* GCC_ANALYZER_TRIMMED_GRAPH_H */ diff --git a/gcc/doc/analyzer.texi b/gcc/doc/analyzer.texi index 0059231..3f7bcf3 100644 --- a/gcc/doc/analyzer.texi +++ b/gcc/doc/analyzer.texi @@ -320,22 +320,56 @@ feasible @end itemize Without state-merging, all paths in the exploded graph are feasible -(in terms of constraints being satisified). +(in terms of constraints being satisfied). With state-merging, paths in the exploded graph can be infeasible. We collate warnings and only emit them for the simplest path e.g. for a bug in a utility function, with lots of routes to calling it, 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). 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 -@code{diagnostic_path} (a list of events for the diagnostic subsystem) - -specifically a @code{checker_path}. +it can be reproduced without a caller). + +We thus want to find the shortest feasible path through the exploded +graph from the origin to the exploded node at which the diagnostic was +saved. Unfortunately, if we simply find the shortest such path and +check if it's feasible we might falsely reject the diagnostic, as there +might be a longer path that is feasible. Examples include the cases +where the diagnostic requires us to go at least once around a loop for a +later condition to be satisfied, or where for a later condition to be +satisfied we need to enter a suite of code that the simpler path skips. + +We attempt to find the shortest feasible path to each diagnostic by +first constructing a ``trimmed graph'' from the exploded graph, +containing only those nodes and edges from which there are paths to +the target node, and using Dijkstra's algorithm to order the trimmed +nodes by minimal distance to the target. + +We then use a worklist to iteratively build a ``feasible graph'' +(actually a tree), capturing the pertinent state along each path, in +which every path to a ``feasible node'' is feasible by construction, +restricting ourselves to the trimmed graph to ensure we stay on target, +and ordering the worklist so that the first feasible path we find to the +target node is the shortest possible path. Hence we start by trying the +shortest possible path, but if that fails, we explore progressively +longer paths, eventually trying iterations through loops. The +exploration is captured in the feasible_graph, which can be dumped as a +.dot file via @option{-fdump-analyzer-feasibility} to visualize the +exploration. The indices of the feasible nodes show the order in which +they were created. We effectively explore the tree of feasible paths in +order of shortest path until we either find a feasible path to the +target node, or hit a limit and give up. + +This is something of a brute-force approach, but the trimmed graph +hopefully keeps the complexity manageable. + +This algorithm can be disabled (for debugging purposes) via +@option{-fno-analyzer-feasibility}, which simply uses the shortest path, +and notes if it is infeasible. + +The above gives us a shortest feasible @code{exploded_path} through the +@code{exploded_graph} (a list of @code{exploded_edge *}). We use this +@code{exploded_path} to build a @code{diagnostic_path} (a list of +@strong{events} for the diagnostic subsystem) - specifically a +@code{checker_path}. Having built the @code{checker_path}, we prune it to try to eliminate events that aren't relevant, to minimize how much the user has to read. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 4bd4f39..4a3c1e2 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -424,6 +424,7 @@ Objective-C and Objective-C++ Dialects}. -fdump-analyzer-exploded-nodes @gol -fdump-analyzer-exploded-nodes-2 @gol -fdump-analyzer-exploded-nodes-3 @gol +-fdump-analyzer-feasibility @gol -fdump-analyzer-json @gol -fdump-analyzer-state-purge @gol -fdump-analyzer-supergraph @gol @@ -9566,6 +9567,13 @@ Dump a textual representation of the ``exploded graph'' to one dump file per node, to @file{@var{file}.eg-@var{id}.txt}. This is typically a large number of dump files. +@item -fdump-analyzer-feasibility +@opindex dump-analyzer-feasibility +Dump internal details about the analyzer's search for feasible paths. +The details are written in a form suitable for viewing with GraphViz +to filenames of the form @file{@var{file}.*.fg.dot} and +@file{@var{file}.*.tg.dot}. + @item -fdump-analyzer-json @opindex fdump-analyzer-json Dump a compressed JSON representation of analyzer internals to diff --git a/gcc/shortest-paths.h b/gcc/shortest-paths.h index 40d2c2a..f544d7d 100644 --- a/gcc/shortest-paths.h +++ b/gcc/shortest-paths.h @@ -57,6 +57,7 @@ public: enum shortest_path_sense sense); path_t get_shortest_path (const node_t *other_node) const; + int get_shortest_distance (const node_t *other_node) const; private: const graph_t &m_graph; @@ -199,4 +200,16 @@ get_shortest_path (const node_t *other_node) const return result; } +/* Get the shortest distance... + SPS_FROM_GIVEN_ORIGIN: ...from given origin node to OTHER_NODE + SPS_TO_GIVEN_TARGET: ...from OTHER_NODE to given target node. */ + +template <typename GraphTraits, typename Path_t> +inline int +shortest_paths<GraphTraits, Path_t>:: +get_shortest_distance (const node_t *other_node) const +{ + return m_dist[other_node->m_index]; +} + #endif /* GCC_SHORTEST_PATHS_H */ diff --git a/gcc/testsuite/gcc.dg/analyzer/dot-output.c b/gcc/testsuite/gcc.dg/analyzer/dot-output.c index ff418b1..03405cd 100644 --- a/gcc/testsuite/gcc.dg/analyzer/dot-output.c +++ b/gcc/testsuite/gcc.dg/analyzer/dot-output.c @@ -2,7 +2,7 @@ by .dot. */ /* { dg-require-dot "" } */ -/* { dg-additional-options "-fdump-analyzer-callgraph -fdump-analyzer-exploded-graph -fdump-analyzer-state-purge -fdump-analyzer-supergraph" } */ +/* { dg-additional-options "-fdump-analyzer-callgraph -fdump-analyzer-exploded-graph -fdump-analyzer-state-purge -fdump-analyzer-supergraph -fdump-analyzer-feasibility" } */ #include <stdlib.h> diff --git a/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c b/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c index c968444..83ec1ca 100644 --- a/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c @@ -55,8 +55,7 @@ int test_6 (int a, int b) { if (!problem) problem = 2; - __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */ - /* XFAIL is PR analyzer/96374. */ + __analyzer_dump_path (); /* { dg-message "path" } */ } return problem; } @@ -86,3 +85,16 @@ int test_6a (int a, int b, void *ptr) } return problem; } + +/* After state-merging, the shortest path skips the loop, + but the shortest feasible path enters it. */ + +void test_7 (int n) +{ + int entered_loop = 0; + int i; + for (i = 0; i < n; i++) + entered_loop = 1; + if (entered_loop) + __analyzer_dump_path (); /* { dg-message "path" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c index 1afc6df..1484297 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c @@ -25,7 +25,5 @@ _nl_expand_alias (void) ++locale_alias_path; if (start < locale_alias_path) - __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */ - /* XFAIL: PR analyzer/96374 - Use -fno-analyzer-feasibility to see the path. */ + __analyzer_dump_path (); /* { dg-message "path" } */ } diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c index a864831..50d3388 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c @@ -41,9 +41,7 @@ read_alias_file (const char *fname, char *cp) { FILE *fp; - fp = fopen (fname, "r"); /* { dg-message "opened here" "" { xfail *-*-* } } */ - /* XFAIL: PR analyzer/96374 - Use -fno-analyzer-feasibility to see the path. */ + fp = fopen (fname, "r"); /* { dg-message "opened here" } */ if (fp == NULL) return 0; @@ -54,9 +52,7 @@ read_alias_file (const char *fname, char *cp) ++cp; if (cp[0] != '\0') - return 42; /* { dg-warning "leak of FILE 'fp'" "" { xfail *-*-* } } */ - /* XFAIL: PR analyzer/96374 - Use -fno-analyzer-feasibility to see the path. */ + return 42; /* { dg-warning "leak of FILE 'fp'" } */ fclose(fp); diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c index 0d470d6..1a34d05 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c @@ -3,8 +3,6 @@ Adapted from intl/localealias.c, with all #includes removed. */ /* { dg-do "compile" } */ -/* { dg-additional-options "-fno-analyzer-feasibility" } */ -/* TODO: remove the need for this option. */ /* Handle aliases for locale names. Copyright (C) 1995-1999, 2000-2001, 2003 Free Software Foundation, Inc. diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c index 043e45f..88d0fc1 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c @@ -3,8 +3,8 @@ Adapted from intl/localealias.c, with all #includes removed. */ /* { dg-do "compile" } */ -/* { dg-additional-options "-Wno-analyzer-too-complex -fno-analyzer-feasibility" } */ -/* TODO: remove the need for these options. */ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ +/* TODO: remove the need for this option. */ /* { dg-require-effective-target alloca } */ /* Handle aliases for locale names. diff --git a/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c b/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c index 3d8f82e..bd1ab1e 100644 --- a/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c +++ b/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c @@ -10,6 +10,6 @@ void test (void) got = 1; else if (got) - __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */ + __analyzer_dump_path (); /* { dg-message "path" } */ } } |