diff options
Diffstat (limited to 'gcc')
38 files changed, 1547 insertions, 86 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 7f2df4b..7228b79 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1324,6 +1324,7 @@ ANALYZER_OBJS = \ analyzer/engine.o \ analyzer/feasible-graph.o \ analyzer/function-set.o \ + analyzer/infinite-loop.o \ analyzer/infinite-recursion.o \ analyzer/kf.o \ analyzer/kf-analyzer.o \ diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt index 25df89d..fae2649 100644 --- a/gcc/analyzer/analyzer.opt +++ b/gcc/analyzer/analyzer.opt @@ -134,6 +134,10 @@ Wanalyzer-imprecise-fp-arithmetic Common Var(warn_analyzer_imprecise_fp_arithmetic) Init(1) Warning Warn about code paths in which floating-point arithmetic is used in locations where precise computation is needed. +Wanalyzer-infinite-loop +Common Var(warn_analyzer_infinite_loop) Init(1) Warning +Warn about code paths which appear to lead to an infinite loop. + Wanalyzer-infinite-recursion Common Var(warn_analyzer_infinite_recursion) Init(1) Warning Warn about code paths which appear to lead to infinite recursion. @@ -354,6 +358,10 @@ fdump-analyzer-feasibility Common RejectNegative Var(flag_dump_analyzer_feasibility) Dump various analyzer internals to SRCFILE.*.fg.dot and SRCFILE.*.tg.dot. +fdump-analyzer-infinite-loop +Common RejectNegative Var(flag_dump_analyzer_infinite_loop) +Dump various analyzer internals to SRCFILE.*.infinite-loop.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/checker-event.h b/gcc/analyzer/checker-event.h index 7ba92f1..dcb2e27 100644 --- a/gcc/analyzer/checker-event.h +++ b/gcc/analyzer/checker-event.h @@ -444,11 +444,12 @@ public: { } - label_text get_desc (bool can_colorize) const final override; + label_text get_desc (bool can_colorize) const override; - private: +protected: label_text maybe_describe_condition (bool can_colorize) const; +private: static label_text maybe_describe_condition (bool can_colorize, tree lhs, enum tree_code op, diff --git a/gcc/analyzer/checker-path.h b/gcc/analyzer/checker-path.h index 93c807c..055d5e3 100644 --- a/gcc/analyzer/checker-path.h +++ b/gcc/analyzer/checker-path.h @@ -65,6 +65,7 @@ public: void dump (pretty_printer *pp) const; void debug () const; + logger *get_logger () const { return m_logger; } void maybe_log (logger *logger, const char *desc) const; void add_event (std::unique_ptr<checker_event> event); diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index 972413a..a6755f2 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -517,7 +517,7 @@ process_worklist_item (feasible_worklist *worklist, feasibility_state succ_state (fnode->get_state ()); std::unique_ptr<rejected_constraint> rc; - if (succ_state.maybe_update_for_edge (logger, succ_eedge, &rc)) + if (succ_state.maybe_update_for_edge (logger, succ_eedge, nullptr, &rc)) { gcc_assert (rc == NULL); feasible_node *succ_fnode diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 4861ee5..041fe6a 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -85,7 +85,8 @@ impl_region_model_context (exploded_graph &eg, uncertainty_t *uncertainty, path_context *path_ctxt, const gimple *stmt, - stmt_finder *stmt_finder) + stmt_finder *stmt_finder, + bool *out_could_have_done_work) : m_eg (&eg), m_logger (eg.get_logger ()), m_enode_for_diag (enode_for_diag), m_old_state (old_state), @@ -94,7 +95,8 @@ impl_region_model_context (exploded_graph &eg, m_stmt_finder (stmt_finder), m_ext_state (eg.get_ext_state ()), m_uncertainty (uncertainty), - m_path_ctxt (path_ctxt) + m_path_ctxt (path_ctxt), + m_out_could_have_done_work (out_could_have_done_work) { } @@ -110,7 +112,8 @@ impl_region_model_context (program_state *state, m_stmt_finder (NULL), m_ext_state (ext_state), m_uncertainty (uncertainty), - m_path_ctxt (NULL) + m_path_ctxt (NULL), + m_out_could_have_done_work (nullptr) { } @@ -1024,6 +1027,17 @@ impl_region_model_context::on_unexpected_tree_code (tree t, m_new_state->m_valid = false; } +/* Implementation of region_model_context::maybe_did_work vfunc. + Mark that "externally visible work" has occurred, and thus we + shouldn't report an infinite loop here. */ + +void +impl_region_model_context::maybe_did_work () +{ + if (m_out_could_have_done_work) + *m_out_could_have_done_work = true; +} + /* struct point_and_state. */ /* Assert that this object is sane. */ @@ -1439,6 +1453,7 @@ exploded_node::on_stmt (exploded_graph &eg, const gimple *stmt, program_state *state, uncertainty_t *uncertainty, + bool *out_could_have_done_work, path_context *path_ctxt) { logger *logger = eg.get_logger (); @@ -1464,7 +1479,8 @@ exploded_node::on_stmt (exploded_graph &eg, impl_region_model_context ctxt (eg, this, &old_state, state, uncertainty, - path_ctxt, stmt); + path_ctxt, stmt, nullptr, + out_could_have_done_work); /* Handle call summaries here. */ if (cgraph_edge *cgedge @@ -1551,12 +1567,16 @@ exploded_node::on_stmt_pre (exploded_graph &eg, else if (is_setjmp_call_p (call)) { state->m_region_model->on_setjmp (call, this, ctxt); + if (ctxt) + ctxt->maybe_did_work (); return; } else if (is_longjmp_call_p (call)) { on_longjmp (eg, call, state, ctxt); *out_terminate_path = true; + if (ctxt) + ctxt->maybe_did_work (); return; } } @@ -1938,8 +1958,9 @@ exploded_node::on_longjmp (exploded_graph &eg, if (next) { exploded_edge *eedge - = eg.add_edge (const_cast<exploded_node *> (this), next, NULL, - make_unique<rewind_info_t> (tmp_setjmp_record, longjmp_call)); + = eg.add_edge (const_cast<exploded_node *> (this), next, NULL, true, + make_unique<rewind_info_t> (tmp_setjmp_record, + longjmp_call)); /* For any diagnostics that were queued here (such as leaks) we want the checker_path to show the rewinding events after the "final event" @@ -2161,10 +2182,11 @@ rewind_info_t::add_events_to_path (checker_path *emission_path, /* exploded_edge's ctor. */ exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, + const superedge *sedge, bool could_do_work, std::unique_ptr<custom_edge_info> custom_info) : dedge<eg_traits> (src, dest), m_sedge (sedge), - m_custom_info (std::move (custom_info)) + m_custom_info (std::move (custom_info)), + m_could_do_work_p (could_do_work) { } @@ -2228,6 +2250,9 @@ exploded_edge::dump_dot_label (pretty_printer *pp) const else if (m_custom_info) m_custom_info->print (pp); + pp_printf (pp, "%s", + could_do_work_p () ? "(could do work)" : "DOES NO WORK"); + //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false); pp_printf (pp, "\"];\n"); @@ -2790,7 +2815,7 @@ exploded_graph::add_function_entry (function *fun) if (!enode) return NULL; - add_edge (m_origin, enode, NULL, std::move (edge_info)); + add_edge (m_origin, enode, NULL, false, std::move (edge_info)); m_functions_with_enodes.add (fun); @@ -2988,19 +3013,20 @@ exploded_graph::get_or_create_node (const program_point &point, /* Add an exploded_edge from SRC to DEST, recording its association with SEDGE (which may be NULL), and, if non-NULL, taking ownership - of CUSTOM_INFO. + of CUSTOM_INFO. COULD_DO_WORK is used for detecting infinite loops. Return the newly-created eedge. */ exploded_edge * exploded_graph::add_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, - std::unique_ptr<custom_edge_info> custom_info) + const superedge *sedge, bool could_do_work, + std::unique_ptr<custom_edge_info> custom_info) { if (get_logger ()) get_logger ()->log ("creating edge EN: %i -> EN: %i", src->m_index, dest->m_index); - exploded_edge *e = new exploded_edge (src, dest, sedge, - std::move (custom_info)); + exploded_edge *e + = new exploded_edge (src, dest, sedge, could_do_work, + std::move (custom_info)); digraph<eg_traits>::add_edge (e); return e; } @@ -3249,7 +3275,7 @@ add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl, } } - eg->add_edge (eg->get_origin (), enode, NULL, + eg->add_edge (eg->get_origin (), enode, NULL, false, make_unique<tainted_args_call_info> (field, fndecl, loc)); } @@ -3403,7 +3429,7 @@ exploded_graph::process_worklist () if (merged_state == state) { /* Then merge node_2 into node by adding an edge. */ - add_edge (node_2, node, NULL); + add_edge (node_2, node, NULL, false); /* Remove node_2 from the worklist. */ m_worklist.take_next (); @@ -3416,7 +3442,7 @@ exploded_graph::process_worklist () /* Then merge node into node_2, and leave node_2 in the worklist, to be processed on the next iteration. */ - add_edge (node, node_2, NULL); + add_edge (node, node_2, NULL, false); node->set_status (exploded_node::STATUS_MERGER); continue; } @@ -3461,7 +3487,7 @@ exploded_graph::process_worklist () m_worklist.add_node (merged_enode); else { - add_edge (node, merged_enode, NULL); + add_edge (node, merged_enode, NULL, false); node->set_status (exploded_node::STATUS_MERGER); } @@ -3469,7 +3495,7 @@ exploded_graph::process_worklist () m_worklist.add_node (merged_enode); else { - add_edge (node_2, merged_enode, NULL); + add_edge (node_2, merged_enode, NULL, false); node_2->set_status (exploded_node::STATUS_MERGER); } @@ -3704,7 +3730,8 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode) { exploded_node *next = next_enodes[it->m_merger_idx]; if (next) - add_edge (it->m_input_enode, next, NULL); + add_edge (it->m_input_enode, next, NULL, + false); /* no "work" is done during merger. */ it->m_input_enode->set_status (exploded_node::STATUS_BULK_MERGED); } @@ -3847,6 +3874,7 @@ exploded_graph::maybe_create_dynamic_call (const gcall *call, node); if (enode) add_edge (node,enode, NULL, + false, /* No work is done by the call itself. */ make_unique<dynamic_call_info_t> (call)); return true; } @@ -4039,7 +4067,8 @@ exploded_graph::process_node (exploded_node *node) program_point next_point (point.get_next ()); exploded_node *next = get_or_create_node (next_point, next_state, node); if (next) - add_edge (node, next, NULL); + add_edge (node, next, NULL, + false); /* Assume no work is done at phi nodes. */ } break; case PK_BEFORE_STMT: @@ -4067,6 +4096,7 @@ exploded_graph::process_node (exploded_node *node) impl_path_context path_ctxt (&next_state, logger); + bool could_have_done_work = false; uncertainty_t uncertainty; const supernode *snode = point.get_supernode (); unsigned stmt_idx; @@ -4090,7 +4120,7 @@ exploded_graph::process_node (exploded_node *node) /* Process the stmt. */ exploded_node::on_stmt_flags flags = node->on_stmt (*this, snode, stmt, &next_state, &uncertainty, - &path_ctxt); + &could_have_done_work, &path_ctxt); node->m_num_processed_stmts++; /* If flags.m_terminate_path, stop analyzing; any nodes/edges @@ -4147,7 +4177,7 @@ exploded_graph::process_node (exploded_node *node) node->m_num_processed_stmts--; if (logger) logger->log ("creating edge to split_enode"); - add_edge (node, split_enode, NULL); + add_edge (node, split_enode, NULL, could_have_done_work); return; } else @@ -4174,7 +4204,7 @@ exploded_graph::process_node (exploded_node *node) exploded_node *next = get_or_create_node (next_point, next_state, node); if (next) - add_edge (node, next, NULL); + add_edge (node, next, NULL, could_have_done_work); } /* If we have custom edge infos, "bifurcate" the state @@ -4212,7 +4242,9 @@ exploded_graph::process_node (exploded_node *node) exploded_node *next2 = get_or_create_node (next_point, bifurcated_new_state, node); if (next2) - add_edge (node, next2, NULL, std::move (edge_info)); + add_edge (node, next2, NULL, + true /* assume that work could be done */, + std::move (edge_info)); } else { @@ -4327,7 +4359,8 @@ exploded_graph::process_node (exploded_node *node) next_state, node); if (next) - add_edge (node, next, succ); + add_edge (node, next, succ, + true /* assume that work is done */); } } @@ -4343,7 +4376,7 @@ exploded_graph::process_node (exploded_node *node) node); if (next) { - add_edge (node, next, succ); + add_edge (node, next, succ, false); /* We might have a function entrypoint. */ detect_infinite_recursion (next); @@ -4377,7 +4410,7 @@ exploded_graph::process_node (exploded_node *node) next_state, node); if (enode) - add_edge (node, enode, NULL, + add_edge (node, enode, NULL, false, make_unique<dynamic_call_info_t> (call, true)); } } @@ -4708,7 +4741,7 @@ exploded_path::feasible_p (logger *logger, eedge->m_dest->m_index); std::unique_ptr <rejected_constraint> rc; - if (!state.maybe_update_for_edge (logger, eedge, &rc)) + if (!state.maybe_update_for_edge (logger, eedge, nullptr, &rc)) { gcc_assert (rc); if (out) @@ -4835,6 +4868,21 @@ feasibility_state::feasibility_state (const feasibility_state &other) bitmap_copy (m_snodes_visited, other.m_snodes_visited); } +feasibility_state::feasibility_state (const region_model &model, + const supergraph &sg) +: m_model (model), + m_snodes_visited (sg.m_nodes.length ()) +{ +} + +feasibility_state & +feasibility_state::operator= (const feasibility_state &other) +{ + m_model = other.m_model; + bitmap_copy (m_snodes_visited, other.m_snodes_visited); + return *this; +} + /* The heart of feasibility-checking. Attempt to update this state in-place based on traversing EEDGE @@ -4849,6 +4897,7 @@ bool feasibility_state:: maybe_update_for_edge (logger *logger, const exploded_edge *eedge, + region_model_context *ctxt, std::unique_ptr<rejected_constraint> *out_rc) { const exploded_node &src_enode = *eedge->m_src; @@ -4887,12 +4936,14 @@ maybe_update_for_edge (logger *logger, } const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); - if (!m_model.maybe_update_for_edge (*sedge, last_stmt, NULL, out_rc)) + if (!m_model.maybe_update_for_edge (*sedge, last_stmt, ctxt, out_rc)) { if (logger) { - logger->log ("rejecting due to region model"); + logger->start_log_line (); + logger->log_partial ("rejecting due to region model: "); m_model.dump_to_pp (logger->get_printer (), true, false); + logger->end_log_line (); } return false; } @@ -4908,13 +4959,13 @@ maybe_update_for_edge (logger *logger, == PK_BEFORE_SUPERNODE); function *fun = eedge->m_dest->get_function (); gcc_assert (fun); - m_model.push_frame (fun, NULL, NULL); + m_model.push_frame (fun, NULL, ctxt); if (logger) logger->log (" pushing frame for %qD", fun->decl); } else if (eedge->m_custom_info) { - eedge->m_custom_info->update_model (&m_model, eedge, NULL); + eedge->m_custom_info->update_model (&m_model, eedge, ctxt); } } @@ -4933,7 +4984,7 @@ maybe_update_for_edge (logger *logger, logger->log (" update for phis"); m_model.update_for_phis (src_enode.get_supernode (), last_cfg_superedge, - NULL); + ctxt); /* If we've entering an snode that we've already visited on this epath, then we need do fix things up for loops; see the comment for store::loop_replay_fixup. @@ -6153,6 +6204,9 @@ impl_run_checkers (logger *logger) /* Now process the worklist, exploring the <point, state> graph. */ eg.process_worklist (); + if (warn_analyzer_infinite_loop) + eg.detect_infinite_loops (); + if (flag_dump_analyzer_exploded_graph) { auto_timevar tv (TV_ANALYZER_DUMP); diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index cb64c2a..45ee0d1 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -49,7 +49,9 @@ class impl_region_model_context : public region_model_context path_context *path_ctxt, const gimple *stmt, - stmt_finder *stmt_finder = NULL); + stmt_finder *stmt_finder = NULL, + + bool *out_could_have_done_work = nullptr); impl_region_model_context (program_state *state, const extrinsic_state &ext_state, @@ -110,6 +112,10 @@ class impl_region_model_context : public region_model_context const gimple *get_stmt () const override { return m_stmt; } const exploded_graph *get_eg () const override { return m_eg; } + void maybe_did_work () override; + bool checking_for_infinite_loop_p () const override { return false; } + void on_unusable_in_infinite_loop () override {} + exploded_graph *m_eg; log_user m_logger; exploded_node *m_enode_for_diag; @@ -120,6 +126,7 @@ class impl_region_model_context : public region_model_context const extrinsic_state &m_ext_state; uncertainty_t *m_uncertainty; path_context *m_path_ctxt; + bool *m_out_could_have_done_work; }; /* A <program_point, program_state> pair, used internally by @@ -260,6 +267,7 @@ class exploded_node : public dnode<eg_traits> const gimple *stmt, program_state *state, uncertainty_t *uncertainty, + bool *out_could_have_done_work, path_context *path_ctxt); void on_stmt_pre (exploded_graph &eg, const gimple *stmt, @@ -373,7 +381,7 @@ class exploded_edge : public dedge<eg_traits> { public: exploded_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, + const superedge *sedge, bool could_do_work, std::unique_ptr<custom_edge_info> custom_info); void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override; @@ -389,8 +397,25 @@ class exploded_edge : public dedge<eg_traits> a signal is delivered to a signal-handler. */ std::unique_ptr<custom_edge_info> m_custom_info; + bool could_do_work_p () const { return m_could_do_work_p; } + private: DISABLE_COPY_AND_ASSIGN (exploded_edge); + + /* For -Wanalyzer-infinite-loop. + Set to true during processing if any of the activity along + this edge is "externally-visible work" (and thus ruling this + out as being part of an infinite loop. + + For example, given: + + while (1) + do_something (); + + although it is an infinite loop, presumably the point of the + program is the loop body, and thus reporting this as an infinite + loop is likely to be unhelpful to the user. */ + bool m_could_do_work_p; }; /* Extra data for an exploded_edge that represents dynamic call info ( calls @@ -804,7 +829,7 @@ public: const program_state &state, exploded_node *enode_for_diag); exploded_edge *add_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, + const superedge *sedge, bool could_do_work, std::unique_ptr<custom_edge_info> custom = NULL); per_program_point_data * @@ -856,6 +881,9 @@ public: void on_escaped_function (tree fndecl); + /* In infinite-loop.cc */ + void detect_infinite_loops (); + /* In infinite-recursion.cc */ void detect_infinite_recursion (exploded_node *enode); exploded_node *find_previous_entry_to (function *top_of_stack_fun, @@ -970,10 +998,15 @@ class feasibility_state public: feasibility_state (region_model_manager *manager, const supergraph &sg); + feasibility_state (const region_model &model, + const supergraph &sg); feasibility_state (const feasibility_state &other); + feasibility_state &operator= (const feasibility_state &other); + bool maybe_update_for_edge (logger *logger, const exploded_edge *eedge, + region_model_context *ctxt, std::unique_ptr<rejected_constraint> *out_rc); void update_for_stmt (const gimple *stmt); diff --git a/gcc/analyzer/infinite-loop.cc b/gcc/analyzer/infinite-loop.cc new file mode 100644 index 0000000..771d698 --- /dev/null +++ b/gcc/analyzer/infinite-loop.cc @@ -0,0 +1,565 @@ +/* Detection of infinite loops. + Copyright (C) 2022-2023 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" +#define INCLUDE_MEMORY +#define INCLUDE_VECTOR +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "fold-const.h" +#include "gcc-rich-location.h" +#include "alloc-pool.h" +#include "fibonacci_heap.h" +#include "shortest-paths.h" +#include "diagnostic-core.h" +#include "diagnostic-event-id.h" +#include "diagnostic-path.h" +#include "diagnostic-metadata.h" +#include "function.h" +#include "pretty-print.h" +#include "sbitmap.h" +#include "bitmap.h" +#include "tristate.h" +#include "ordered-hash-map.h" +#include "selftest.h" +#include "json.h" +#include "analyzer/analyzer.h" +#include "analyzer/analyzer-logging.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 "analyzer/sm.h" +#include "analyzer/pending-diagnostic.h" +#include "analyzer/diagnostic-manager.h" +#include "cfg.h" +#include "basic-block.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "gimple-pretty-print.h" +#include "cgraph.h" +#include "digraph.h" +#include "analyzer/supergraph.h" +#include "analyzer/program-state.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/checker-path.h" +#include "analyzer/feasible-graph.h" +#include "make-unique.h" + +/* A bundle of data characterizing a particular infinite loop + identified within the exploded graph. */ + +struct infinite_loop +{ + infinite_loop (const exploded_node &enode, + location_t loc, + std::vector<const exploded_edge *> eedges, + logger *logger) + : m_enode (enode), + m_loc (loc), + m_eedge_vec (eedges) + { + LOG_SCOPE (logger); + if (logger) + { + logger->start_log_line (); + logger->log_partial ("infinite loop: EN: %i", m_enode.m_index); + for (auto eedge : m_eedge_vec) + { + logger->log_partial (" ->"); + if (const superedge *sedge = eedge->m_sedge) + { + sedge->dump_label_to_pp (logger->get_printer (), false); + } + logger->log_partial (" EN: %i", eedge->m_dest->m_index); + } + logger->end_log_line (); + } + } + + bool + operator== (const infinite_loop &other) const + { + /* Compare underlying supernode, rather than enodes, so that + we don't get duplicates in functions that are called from + elsewhere. */ + return (m_enode.get_supernode () == other.m_enode.get_supernode () + && m_loc == other.m_loc); + } + + const exploded_node &m_enode; + location_t m_loc; + std::vector<const exploded_edge *> m_eedge_vec; +}; + +/* A custom subclass of start_cfg_edge_event that rewords the + message to indicate that the CFG edge is *always* taken on + subsequent iterations, assuming it's been taken once. */ + +class perpetual_start_cfg_edge_event : public start_cfg_edge_event +{ +public: + perpetual_start_cfg_edge_event (const exploded_edge &eedge, + const event_loc_info &loc_info) + : start_cfg_edge_event (eedge, loc_info) + { + } + + label_text get_desc (bool can_colorize) const final override + { + bool user_facing = !flag_analyzer_verbose_edges; + label_text edge_desc (m_sedge->get_description (user_facing)); + if (user_facing) + { + if (edge_desc.get () && strlen (edge_desc.get ()) > 0) + { + label_text cond_desc = maybe_describe_condition (can_colorize); + label_text result; + if (cond_desc.get ()) + return make_label_text + (can_colorize, + "%s: always following %qs branch...", + cond_desc.get (), edge_desc.get ()); + else + return make_label_text + (can_colorize, + "if it ever follows %qs branch, it will always do so...", + edge_desc.get ()); + } + } + return start_cfg_edge_event::get_desc (can_colorize); + } +}; + +/* A subclass of pending_diagnostic for complaining about suspected + infinite loops. */ + +class infinite_loop_diagnostic +: public pending_diagnostic_subclass<infinite_loop_diagnostic> +{ +public: + infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop) + : m_inf_loop (std::move (inf_loop)) + { + gcc_assert (m_inf_loop != nullptr); + } + + const char *get_kind () const final override + { + return "infinite_loop_diagnostic"; + } + + bool operator== (const infinite_loop_diagnostic &other) const + { + return *m_inf_loop == *other.m_inf_loop; + } + + int get_controlling_option () const final override + { + return OPT_Wanalyzer_infinite_loop; + } + + bool emit (rich_location *rich_loc, logger *) final override + { + /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */ + diagnostic_metadata m; + m.add_cwe (835); + return warning_meta (rich_loc, m, get_controlling_option (), + "infinite loop"); + } + + bool maybe_add_custom_events_for_superedge (const exploded_edge &, + checker_path *) + final override + { + /* Don't add any regular events; instead we add them after pruning as + part of the "final" warning. */ + return true; + } + + label_text describe_final_event (const evdesc::final_event &ev) final override + { + return ev.formatted_print ("infinite loop here"); + } + + /* Customize the location where the warning_event appears. */ + void add_final_event (const state_machine *, + const exploded_node *enode, + const gimple *, + tree, + state_machine::state_t, + checker_path *emission_path) final override + { + emission_path->add_event + (make_unique<warning_event> + (event_loc_info (m_inf_loop->m_loc, + enode->get_function ()->decl, + enode->get_stack_depth ()), + enode, + NULL, NULL, NULL)); + + logger *logger = emission_path->get_logger (); + + /* EMISSION_PATH has the path to the entry of the infinite loop. + Add extra edges showing the loop itself. */ + for (auto eedge : m_inf_loop->m_eedge_vec) + { + if (logger) + logger->log ("EN: %i -> EN: %i", + eedge->m_src->m_index, + eedge->m_dest->m_index); + if (!eedge->m_sedge) + continue; + + const cfg_superedge *cfg_sedge + = eedge->m_sedge->dyn_cast_cfg_superedge (); + if (!cfg_sedge) + continue; + + const exploded_node *src_node = eedge->m_src; + const program_point &src_point = src_node->get_point (); + const exploded_node *dst_node = eedge->m_dest; + const program_point &dst_point = dst_node->get_point (); + const int src_stack_depth = src_point.get_stack_depth (); + const int dst_stack_depth = dst_point.get_stack_depth (); + const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); + + event_loc_info loc_info_from + (last_stmt ? last_stmt->location : cfg_sedge->get_goto_locus (), + src_point.get_fndecl (), + src_stack_depth); + event_loc_info loc_info_to + (dst_point.get_supernode ()->get_start_location (), + dst_point.get_fndecl (), + dst_stack_depth); + + if (const switch_cfg_superedge *switch_cfg_sedge + = cfg_sedge->dyn_cast_switch_cfg_superedge ()) + { + if (switch_cfg_sedge->implicitly_created_default_p ()) + { + emission_path->add_event + (make_unique<perpetual_start_cfg_edge_event> (*eedge, + loc_info_from)); + emission_path->add_event + (make_unique<end_cfg_edge_event> + (*eedge, + loc_info_to)); + } + } + + if (cfg_sedge->true_value_p ()) + { + emission_path->add_event + (make_unique<perpetual_start_cfg_edge_event> (*eedge, + loc_info_from)); + emission_path->add_event + (make_unique<end_cfg_edge_event> + (*eedge, + loc_info_to)); + } + else if (cfg_sedge->false_value_p ()) + { + emission_path->add_event + (make_unique<perpetual_start_cfg_edge_event> (*eedge, + loc_info_from)); + emission_path->add_event + (make_unique<end_cfg_edge_event> + (*eedge, + loc_info_to)); + } + else if (cfg_sedge->back_edge_p ()) + { + emission_path->add_event + (make_unique<precanned_custom_event> + (loc_info_from, "looping back...")); + emission_path->add_event + (make_unique<end_cfg_edge_event> + (*eedge, + loc_info_to)); + } + } + } + +private: + std::unique_ptr<infinite_loop> m_inf_loop; +}; + +/* If ENODE has an in-edge corresponding to a CFG backedge, return that + exploded in-edge. + Otherwise, return nullptr. */ + +static const exploded_edge * +get_in_edge_back_edge (const exploded_node &enode) +{ + for (auto in_edge : enode.m_preds) + { + const superedge *sedge = in_edge->m_sedge; + if (!sedge) + continue; + const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge (); + if (!cfg_sedge) + continue; + if (cfg_sedge->back_edge_p ()) + return in_edge; + } + return nullptr; +} + +/* Subclass of region_model_context that rejects conditional branches that + aren't known for definite. */ + +class infinite_loop_checking_context : public noop_region_model_context +{ +public: + infinite_loop_checking_context () : m_unusable (false) {} + + bool checking_for_infinite_loop_p () const override { return true; } + void on_unusable_in_infinite_loop () override { m_unusable = true; } + + bool unusable_p () const { return m_unusable; } + +private: + bool m_unusable; +}; + +/* Determine if an infinite loop starts at ENODE. + Return the loop if it is found, nullptr otherwise. + + Look for cycles in the exploded graph in which: + - no externally visible work occurs + - no escape from the cycle + - the program state is "sufficiently concrete" at each step: + - no unknown activity could be occurring + - the worklist was fully drained for each enode in the cycle + i.e. every enode in the cycle is processed. */ + +static std::unique_ptr<infinite_loop> +starts_infinite_loop_p (const exploded_node &enode, + const exploded_graph &eg, + logger *logger) +{ + LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index); + + /* Only consider enodes that have a CFG back edge as an in-edge. */ + if (const exploded_edge *back_edge = get_in_edge_back_edge (enode)) + { + if (logger) + logger->log ("got backedge from EN: %i", + back_edge->m_src->m_index); + } + else + { + if (logger) + logger->log ("rejecting: no backedge in in-edges"); + return nullptr; + } + + /* Support for dumping an .infinite-loop.dot file visualizing the + traversal for this enode. */ + std::unique_ptr<feasible_graph> fg; + feasible_node *curr_fnode = nullptr; + + if (flag_dump_analyzer_infinite_loop) + fg = ::make_unique<feasible_graph> (); + + location_t first_loc = UNKNOWN_LOCATION; + const exploded_node *iter = &enode; + feasibility_state state (*enode.get_state ().m_region_model, + eg.get_supergraph ()); + + if (fg) + curr_fnode = fg->add_node (&enode, state, 0); + + hash_set<const exploded_node *> visited; + std::vector<const exploded_edge *> eedges; + while (1) + { + if (logger) + logger->log ("iter: EN: %i", iter->m_index); + /* Analysis bailed out before processing this node. */ + if (iter->get_status () == exploded_node::STATUS_WORKLIST) + { + if (logger) + logger->log ("rejecting: EN: %i is still in worklist", + iter->m_index); + return nullptr; + } + if (visited.contains (iter)) + { + /* We've looped back on ourselves. ENODE is in the loop + itself if ENODE is the first place we looped back, + as opposed to being on a path to a loop. */ + if (iter == &enode) + { + if (logger) + logger->log ("accepting: looped back to EN: %i", + iter->m_index); + if (fg) + { + auto_timevar tv (TV_ANALYZER_DUMP); + pretty_printer pp; + pp_printf (&pp, "%s.en%i.infinite-loop.dot", + dump_base_name, enode.m_index); + char *filename = xstrdup (pp_formatted_text (&pp)); + feasible_graph::dump_args_t dump_args (eg); + fg->dump_dot (filename, nullptr, dump_args); + free (filename); + } + return ::make_unique<infinite_loop> (enode, + first_loc, + eedges, + logger); + } + else + { + if (logger) + logger->log ("rejecting: looped back to EN: %i, not to EN: %i", + iter->m_index, enode.m_index); + return nullptr; + } + } + visited.add (iter); + if (first_loc == UNKNOWN_LOCATION) + { + location_t enode_loc = iter->get_point ().get_location (); + if (enode_loc != UNKNOWN_LOCATION) + first_loc = enode_loc; + } + + /* Find the out-edges that are feasible, given the + constraints here. */ + typedef std::pair<feasibility_state, const exploded_edge *> pair_t; + std::vector<pair_t> succs; + for (auto out_edge : iter->m_succs) + { + log_scope s (logger, "considering out-edge", + "EN:%i -> EN:%i", + out_edge->m_src->m_index, + out_edge->m_dest->m_index); + feasibility_state next_state (state); + + /* Use this context to require edge conditions to be known, + rather than be merely "possible". */ + infinite_loop_checking_context ctxt; + if (next_state.maybe_update_for_edge (logger, + out_edge, + &ctxt, + nullptr)) + succs.push_back (pair_t (next_state, out_edge)); + if (ctxt.unusable_p ()) + { + /* If we get here, then we have e.g. a gcond where + the condition is UNKNOWN, or a condition + based on a widening_svalue. Reject such paths. */ + if (logger) + logger->log ("rejecting: unusable"); + return nullptr; + } + } + + if (succs.size () != 1) + { + if (logger) + logger->log ("rejecting: %i feasible successors", + (int)succs.size ()); + return nullptr; + } + const feasibility_state &next_state = succs[0].first; + const exploded_edge *out_eedge = succs[0].second; + if (out_eedge->could_do_work_p ()) + { + if (logger) + logger->log ("rejecting: edge could do work"); + return nullptr; + } + if (fg) + { + feasible_node *next_fnode = fg->add_node (out_eedge->m_dest, + next_state, + fg->m_nodes.length ()); + fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge)); + curr_fnode = next_fnode; + } + state = next_state; + eedges.push_back (out_eedge); + if (first_loc == UNKNOWN_LOCATION) + { + if (out_eedge->m_sedge) + if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ()) + if (cfg_edge->goto_locus > BUILTINS_LOCATION) + first_loc = cfg_edge->goto_locus; + } + iter = out_eedge->m_dest; + } +} + +/* Implementation of -Wanalyzer-infinite-loop. */ + +void +exploded_graph::detect_infinite_loops () +{ + LOG_FUNC (get_logger ()); + auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS); + + /* Track all enodes we've warned for; both the loop entrypoints + and all the enodes within those loops. */ + hash_set<const exploded_node *> warned_for; + + for (auto enode : m_nodes) + { + if (get_logger ()) + get_logger ()->log ("visited: %i out of %i", + (int)warned_for.elements (), m_nodes.length ()); + + /* Only warn about the first enode we encounter in each cycle. */ + if (warned_for.contains(enode)) + continue; + + if (std::unique_ptr<infinite_loop> inf_loop + = starts_infinite_loop_p (*enode, *this, get_logger ())) + { + const supernode *snode = enode->get_supernode (); + + if (get_logger ()) + get_logger ()->log ("EN: %i from starts_infinite_loop_p", + enode->m_index); + + for (auto iter : inf_loop->m_eedge_vec) + warned_for.add (iter->m_src); + gcc_assert (warned_for.contains(enode)); + + if (inf_loop->m_loc == UNKNOWN_LOCATION) + { + if (get_logger ()) + get_logger ()->log + ("no location available for reporting infinite loop"); + continue; + } + + pending_location ploc (enode, snode, inf_loop->m_loc); + auto d + = ::make_unique<infinite_loop_diagnostic> (std::move (inf_loop)); + get_diagnostic_manager ().add_diagnostic (ploc, std::move (d)); + } + } +} diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 8dade4b..9bb81e6 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -1145,15 +1145,22 @@ program_state::on_edge (exploded_graph &eg, this, uncertainty, &path_ctxt, last_stmt); + std::unique_ptr<rejected_constraint> rc; + logger * const logger = eg.get_logger (); if (!m_region_model->maybe_update_for_edge (*succ, last_stmt, - &ctxt, NULL)) + &ctxt, + logger ? &rc : nullptr)) { - logger * const logger = eg.get_logger (); if (logger) - logger->log ("edge to SN: %i is impossible" - " due to region_model constraints", - succ->m_dest->m_index); + { + logger->start_log_line (); + logger->log_partial ("edge to SN: %i is impossible" + " due to region_model constraint: ", + succ->m_dest->m_index); + rc->dump_to_pp (logger->get_printer ()); + logger->end_log_line (); + } return false; } if (terminated) diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index dc83440..052c47d 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -1179,6 +1179,15 @@ region_model::on_assignment (const gassign *assign, region_model_context *ctxt) const region *lhs_reg = get_lvalue (lhs, ctxt); + /* Any writes other than to the stack are treated + as externally visible. */ + if (ctxt) + { + enum memory_space memspace = lhs_reg->get_memory_space (); + if (memspace != MEMSPACE_STACK) + ctxt->maybe_did_work (); + } + /* Most assignments are handled by: set_value (lhs_reg, SVALUE, CTXT) for some SVALUE. */ @@ -1277,6 +1286,8 @@ region_model::on_stmt_pre (const gimple *stmt, { const gasm *asm_stmt = as_a <const gasm *> (stmt); on_asm_stmt (asm_stmt, ctxt); + if (ctxt) + ctxt->maybe_did_work (); } break; @@ -1701,7 +1712,11 @@ region_model::on_call_post (const gcall *call, } if (unknown_side_effects) - handle_unrecognized_call (call, ctxt); + { + handle_unrecognized_call (call, ctxt); + if (ctxt) + ctxt->maybe_did_work (); + } } /* Purge state involving SVAL from this region_model, using CTXT @@ -2236,6 +2251,7 @@ void region_model::handle_phi (const gphi *phi, tree lhs, tree rhs, const region_model &old_state, + hash_set<const svalue *> &svals_changing_meaning, region_model_context *ctxt) { /* For now, don't bother tracking the .MEM SSA names. */ @@ -2247,6 +2263,10 @@ region_model::handle_phi (const gphi *phi, const svalue *src_sval = old_state.get_rvalue (rhs, ctxt); const region *dst_reg = old_state.get_lvalue (lhs, ctxt); + const svalue *sval = old_state.get_rvalue (lhs, nullptr); + if (sval->get_kind () == SK_WIDENING) + svals_changing_meaning.add (sval); + set_value (dst_reg, src_sval, ctxt); if (ctxt) @@ -4661,6 +4681,14 @@ region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, return add_constraint (lhs_sval, op, rhs_sval, ctxt); } +static bool +unusable_in_infinite_loop_constraint_p (const svalue *sval) +{ + if (sval->get_kind () == SK_WIDENING) + return true; + return false; +} + /* Attempt to add the constraint "LHS OP RHS" to this region_model. If it is consistent with existing constraints, add it, and return true. Return false if it contradicts existing constraints. @@ -4672,6 +4700,20 @@ region_model::add_constraint (const svalue *lhs, const svalue *rhs, region_model_context *ctxt) { + const bool checking_for_infinite_loop + = ctxt ? ctxt->checking_for_infinite_loop_p () : false; + + if (checking_for_infinite_loop) + { + if (unusable_in_infinite_loop_constraint_p (lhs) + || unusable_in_infinite_loop_constraint_p (rhs)) + { + gcc_assert (ctxt); + ctxt->on_unusable_in_infinite_loop (); + return false; + } + } + tristate t_cond = eval_condition (lhs, op, rhs); /* If we already have the condition, do nothing. */ @@ -4683,6 +4725,15 @@ region_model::add_constraint (const svalue *lhs, if (t_cond.is_false ()) return false; + if (checking_for_infinite_loop) + { + /* Here, we don't have a definite true/false value, so bail out + when checking for infinite loops. */ + gcc_assert (ctxt); + ctxt->on_unusable_in_infinite_loop (); + return false; + } + bool out; if (add_constraints_from_binop (lhs, op, rhs, &out, ctxt)) return out; @@ -5068,6 +5119,8 @@ region_model::update_for_phis (const supernode *snode, are effectively handled simultaneously. */ const region_model old_state (*this); + hash_set<const svalue *> svals_changing_meaning; + for (gphi_iterator gpi = const_cast<supernode *>(snode)->start_phis (); !gsi_end_p (gpi); gsi_next (&gpi)) { @@ -5077,8 +5130,11 @@ region_model::update_for_phis (const supernode *snode, tree lhs = gimple_phi_result (phi); /* Update next_state based on phi and old_state. */ - handle_phi (phi, lhs, src, old_state, ctxt); + handle_phi (phi, lhs, src, old_state, svals_changing_meaning, ctxt); } + + for (auto iter : svals_changing_meaning) + m_constraints->purge_state_involving (iter); } /* Attempt to update this model for taking EDGE (where the last statement @@ -5246,6 +5302,9 @@ region_model::replay_call_summary (call_summary_replay &r, m_store.replay_call_summary (r, summary.m_store); + if (r.get_ctxt ()) + r.get_ctxt ()->maybe_did_work (); + if (!m_constraints->replay_call_summary (r, *summary.m_constraints)) return false; @@ -5807,6 +5866,9 @@ region_model::can_merge_with_p (const region_model &other_model, *other_model.m_constraints, out_model->m_constraints); + for (auto iter : m.m_svals_changing_meaning) + out_model->m_constraints->purge_state_involving (iter); + return true; } @@ -6658,6 +6720,14 @@ model_merger::mergeable_svalue_p (const svalue *sval) const return true; } +/* Mark WIDENING_SVAL as changing meaning during the merge. */ + +void +model_merger::on_widening_reuse (const widening_svalue *widening_sval) +{ + m_svals_changing_meaning.add (widening_sval); +} + } // namespace ana /* Dump RMODEL fully to stderr (i.e. without summarization). */ @@ -8364,7 +8434,6 @@ test_iteration_1 () tree int_0 = build_int_cst (integer_type_node, 0); tree int_1 = build_int_cst (integer_type_node, 1); tree int_256 = build_int_cst (integer_type_node, 256); - tree int_257 = build_int_cst (integer_type_node, 257); tree i = build_global_decl ("i", integer_type_node); test_region_model_context ctxt; @@ -8426,8 +8495,6 @@ test_iteration_1 () ASSERT_TRUE (model5.can_merge_with_p (model2, point, &model6)); const svalue *merged_widening = model6.get_rvalue (i, &ctxt); ASSERT_EQ (merged_widening->get_kind (), SK_WIDENING); - - ASSERT_CONDITION_TRUE (model6, i, LT_EXPR, int_257); } /* Verify that if we mark a pointer to a malloc-ed region as non-NULL, diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index 4d8480d..e26d187 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -328,6 +328,7 @@ class region_model void handle_phi (const gphi *phi, tree lhs, tree rhs, const region_model &old_state, + hash_set<const svalue *> &svals_changing_meaning, region_model_context *ctxt); bool maybe_update_for_edge (const superedge &edge, @@ -804,6 +805,11 @@ class region_model_context virtual const gimple *get_stmt () const = 0; virtual const exploded_graph *get_eg () const = 0; + + /* Hooks for detecting infinite loops. */ + virtual void maybe_did_work () = 0; + virtual bool checking_for_infinite_loop_p () const = 0; + virtual void on_unusable_in_infinite_loop () = 0; }; /* A "do nothing" subclass of region_model_context. */ @@ -861,6 +867,9 @@ public: const gimple *get_stmt () const override { return NULL; } const exploded_graph *get_eg () const override { return NULL; } + void maybe_did_work () override {} + bool checking_for_infinite_loop_p () const override { return false; } + void on_unusable_in_infinite_loop () override {} }; /* A subclass of region_model_context for determining if operations fail @@ -1036,6 +1045,24 @@ class region_model_context_decorator : public region_model_context return nullptr; } + void maybe_did_work () override + { + if (m_inner) + m_inner->maybe_did_work (); + } + + bool checking_for_infinite_loop_p () const override + { + if (m_inner) + return m_inner->checking_for_infinite_loop_p (); + return false; + } + void on_unusable_in_infinite_loop () override + { + if (m_inner) + m_inner->on_unusable_in_infinite_loop (); + } + protected: region_model_context_decorator (region_model_context *inner) : m_inner (inner) @@ -1108,6 +1135,8 @@ struct model_merger return m_point.get_function_point (); } + void on_widening_reuse (const widening_svalue *widening_sval); + const region_model *m_model_a; const region_model *m_model_b; const program_point &m_point; @@ -1116,6 +1145,8 @@ struct model_merger const extrinsic_state *m_ext_state; const program_state *m_state_a; const program_state *m_state_b; + + hash_set<const svalue *> m_svals_changing_meaning; }; /* A record that can (optionally) be written out when diff --git a/gcc/analyzer/sm-signal.cc b/gcc/analyzer/sm-signal.cc index e3f9092..9ebcbdb 100644 --- a/gcc/analyzer/sm-signal.cc +++ b/gcc/analyzer/sm-signal.cc @@ -279,6 +279,7 @@ public: src_enode); if (dst_enode) eg->add_edge (src_enode, dst_enode, NULL, /*state_change (),*/ + true, /* assume does work */ make_unique<signal_delivery_edge_info_t> ()); } diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc index 31707e7..52cb877 100644 --- a/gcc/analyzer/supergraph.cc +++ b/gcc/analyzer/supergraph.cc @@ -790,6 +790,13 @@ supernode::get_start_location () const if (return_p ()) return m_fun->function_end_locus; + /* We have no locations for stmts. If we have a single out-edge that's + a CFG edge, the goto_locus of that edge is a better location for this + than UNKNOWN_LOCATION. */ + if (m_succs.length () == 1) + if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ()) + return cfg_sedge->get_goto_locus (); + return UNKNOWN_LOCATION; } @@ -813,6 +820,12 @@ supernode::get_end_location () const if (return_p ()) return m_fun->function_end_locus; + /* If we have a single out-edge that's a CFG edge, use the goto_locus of + that edge. */ + if (m_succs.length () == 1) + if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ()) + return cfg_sedge->get_goto_locus (); + return UNKNOWN_LOCATION; } @@ -1063,6 +1076,9 @@ cfg_superedge::dump_label_to_pp (pretty_printer *pp, pp_string (pp, ")"); } + if (m_cfg_edge->goto_locus > BUILTINS_LOCATION) + pp_string (pp, " (has goto_locus)"); + /* Otherwise, no label. */ } diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h index 27ebd13..0cafbb5 100644 --- a/gcc/analyzer/supergraph.h +++ b/gcc/analyzer/supergraph.h @@ -532,6 +532,8 @@ class cfg_superedge : public superedge size_t get_phi_arg_idx () const; tree get_phi_arg (const gphi *phi) const; + location_t get_goto_locus () const { return m_cfg_edge->goto_locus; } + private: const ::edge m_cfg_edge; }; diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc index 35eb830..e5811bd 100644 --- a/gcc/analyzer/svalue.cc +++ b/gcc/analyzer/svalue.cc @@ -251,6 +251,7 @@ svalue::can_merge_p (const svalue *other, a descending chain of constraints. */ if (other == widen_arg0) { + merger->on_widening_reuse (widen_arg0); return widen_arg0; } @@ -606,6 +607,12 @@ public: m_found = true; } + void visit_widening_svalue (const widening_svalue *candidate) final override + { + if (candidate == m_needle) + m_found = true; + } + bool found_p () const { return m_found; } private: @@ -620,7 +627,8 @@ svalue::involves_p (const svalue *other) const { /* Currently only implemented for these kinds. */ gcc_assert (other->get_kind () == SK_INITIAL - || other->get_kind () == SK_CONJURED); + || other->get_kind () == SK_CONJURED + || other->get_kind () == SK_WIDENING); involvement_visitor v (other); accept (&v); diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1748afd..c0b5713 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -448,6 +448,7 @@ Objective-C and Objective-C++ Dialects}. -fdump-analyzer-exploded-nodes-3 -fdump-analyzer-exploded-paths -fdump-analyzer-feasibility +-fdump-analyzer-infinite-loop -fdump-analyzer-json -fdump-analyzer-state-purge -fdump-analyzer-stderr @@ -467,6 +468,7 @@ Objective-C and Objective-C++ Dialects}. -Wno-analyzer-file-leak -Wno-analyzer-free-of-non-heap -Wno-analyzer-imprecise-fp-arithmetic +-Wno-analyzer-infinite-loop -Wno-analyzer-infinite-recursion -Wno-analyzer-jump-through-null -Wno-analyzer-malloc-leak @@ -10401,6 +10403,7 @@ Enabling this option effectively enables the following warnings: -Wanalyzer-file-leak -Wanalyzer-free-of-non-heap -Wanalyzer-imprecise-fp-arithmetic +-Wanalyzer-infinite-loop -Wanalyzer-infinite-recursion -Wanalyzer-jump-through-null -Wanalyzer-malloc-leak @@ -10666,6 +10669,57 @@ arithmetic is used in locations where precise computation is needed. This diagnostic only warns on use of floating-point operands inside the calculation of an allocation size at the moment. +@opindex Wanalyzer-infinite-loop +@opindex Wno-analyzer-infinite-loop +@item -Wno-analyzer-infinite-loop +This warning requires @option{-fanalyzer}, which enables it; use +@option{-Wno-analyzer-infinite-loop} to disable it. + +This diagnostics warns for paths through the code which appear to +lead to an infinite loop. + +Specifically, the analyzer will issue this warning when it "sees" a loop +in which: +@itemize @bullet +@item +no externally-visible work could be being done within the loop +@item +there is no way to escape from the loop +@item +the analyzer is sufficiently confident about the program state +throughout the loop to know that the above are true +@end itemize + +One way for this warning to be emitted is when there is an execution +path through a loop for which taking the path on one iteration implies +that the same path will be taken on all subsequent iterations. + +For example, consider: + +@smallexample + while (1) + @{ + char opcode = *cpu_state.pc; + switch (opcode) + @{ + case OPCODE_FOO: + handle_opcode_foo (&cpu_state); + break; + case OPCODE_BAR: + handle_opcode_bar (&cpu_state); + break; + @} + @} +@end smallexample + +The analyzer will complain for the above case because if @code{opcode} +ever matches none of the cases, the @code{switch} will follow the +implicit @code{default} case, making the body of the loop be a ``no-op'' +with @code{cpu_state.pc} unchanged, and thus using the same value of +@code{opcode} on all subseqent iterations, leading to an infinite loop. + +See @uref{https://cwe.mitre.org/data/definitions/835.html, CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')}. + @opindex Wanalyzer-infinite-recursion @opindex Wno-analyzer-infinite-recursion @item -Wno-analyzer-infinite-recursion @@ -10690,6 +10744,8 @@ this diagnostic. Compare with @option{-Winfinite-recursion}, which provides a similar diagnostic, but is implemented in a different way. +See @uref{https://cwe.mitre.org/data/definitions/674.html, CWE-674: Uncontrolled Recursion}. + @opindex Wanalyzer-jump-through-null @opindex Wno-analyzer-jump-through-null @item -Wno-analyzer-jump-through-null @@ -11455,6 +11511,12 @@ The details are written in a form suitable for viewing with GraphViz to filenames of the form @file{@var{file}.*.fg.dot}, @file{@var{file}.*.tg.dot}, and @file{@var{file}.*.fpath.txt}. +@opindex dump-analyzer-infinite-loop +@item -fdump-analyzer-infinite-loop +Dump internal details about the analyzer's search for infinite loops. +The details are written in a form suitable for viewing with GraphViz +to filenames of the form @file{@var{file}.*.infinite-loop.dot}. + @opindex fdump-analyzer-json @item -fdump-analyzer-json Dump a compressed JSON representation of analyzer internals to diff --git a/gcc/testsuite/c-c++-common/analyzer/gzio-2.c b/gcc/testsuite/c-c++-common/analyzer/gzio-2.c index 855ecc8..a0dd112 100644 --- a/gcc/testsuite/c-c++-common/analyzer/gzio-2.c +++ b/gcc/testsuite/c-c++-common/analyzer/gzio-2.c @@ -6,6 +6,6 @@ void gzseek (long offset, int whence) offset -= 1; if (offset < 0) return; - while (offset > 0) { + while (offset > 0) { /* { dg-warning "infinite loop" "" { xfail *-*-* } } */ } } diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c new file mode 100644 index 0000000..f2825d6 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c @@ -0,0 +1,34 @@ +extern int do_stuff (void); + +/* Various misleading "while" loops that look like do-whiles due + to proximity to another clause, but are actually empty. */ + +void not_a_do_while_1 (int flag) +{ + if (flag) { + do_stuff (); + flag = 0; + } while (flag); // TODO: should we complain here? +} + +void not_a_do_while_2 (int flag) +{ + if (!flag) { + do_stuff (); + flag = 1; + } while (flag); // TODO: should we complain here? +} + +void not_a_do_while_3 (int flag) +{ + while (!flag) { + flag = do_stuff (); + } while (flag); // TODO: should we complain here? +} + +void not_a_do_while_4 (int flag) +{ + while (flag) { + flag = do_stuff (); + } while (flag); // TODO: should we complain here? +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c new file mode 100644 index 0000000..032f7fd --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c @@ -0,0 +1,71 @@ +/* Various tests for loops that aren't infinite, strictly speaking, + but look bogus. */ + +// TODO: should we complain about these? + +extern int maybe_useful_work (); + +/* Loop iteration going the wrong way, with a signed iterator + + Not infinite, as will eventually overflow and bail out, but probably + not what the user intended. */ + +void test_wrong_way_signed_1 (int n) +{ + for (int i = 0; i < n; i--) + { + } +} + +void test_wrong_way_signed_2 (int n) +{ + for (int i = 0; i < n; i--) + maybe_useful_work (); +} + +int test_wrong_way_signed_3 (int *arr, int n) +{ + int sum = 0; + for (int i = 0; i < n; i--) + sum += arr[i]; + return sum; +} + + +/* As above, but with an unsigned iterator. + + Not infinite, as will immediately overflow and bail out, but probably + not what the user intended. */ + +void test_wrong_way_unsigned_1 (unsigned n) +{ + for (unsigned i = 0; i < n; i--) + { + } +} + +void test_wrong_way_unsigned_2 (unsigned n) +{ + for (unsigned i = 0; i < n; i--) + maybe_useful_work (); +} + +int test_wrong_way_unsigned_3 (int *arr, unsigned n) +{ + int sum = 0; + for (unsigned i = 0; i < n; i--) + sum += arr[i]; + return sum; +} + +/* BUG: "n" never changes, so loop is never entered. */ + +void test_1 (void) +{ + int n = 0; + + /* [...snip...] */ + + for (int i = 0; i < n; i++) + maybe_useful_work (); +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c new file mode 100644 index 0000000..01d4e4d --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c @@ -0,0 +1,14 @@ +/* Based on qemu's util/crc32c.c, in turn based on the + Linux kernel cryptographic crc32c module. */ + +#include <stdint.h> + +extern const uint32_t crc32c_table[256]; + +uint32_t crc32c(uint32_t crc, const uint8_t *data, unsigned int length) +{ + while (length--) { /* { dg-bogus "infinite loop" } */ + crc = crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8); + } + return crc^0xffffffff; +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c new file mode 100644 index 0000000..166d6da --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c @@ -0,0 +1,26 @@ +/* Reduced from a -Wanalyzer-infinite-loop false positive seen in Doom's + d_main.c, which is under the GPLv2 or later. */ + +extern char* wadfiles[20]; + +void +D_AddFile(const char* file) +{ + int numwadfiles; + char* newfile; + + for (numwadfiles = 0; wadfiles[numwadfiles]; numwadfiles++) /* { dg-bogus "infinite loop" } */ + ; + + newfile = (char *)__builtin_malloc(__builtin_strlen(file) + 1); + __builtin_strcpy(newfile, file); /* { dg-warning "possibly-NULL" } */ + + wadfiles[numwadfiles] = newfile; +} + +void +IdentifyVersion(void) +{ + D_AddFile("doom1.wad"); + D_AddFile("data_se/texture1.lmp"); +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c new file mode 100644 index 0000000..35f4206 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c @@ -0,0 +1,31 @@ +/* Reduced from a -Wanalyzer-infinite-loop false positive seen in Doom's + v_video.c, which is under the GPLv2 or later. */ + +typedef unsigned char byte; + +byte* screens[5]; + +#define SCREENWIDTH 320 + +void +V_DrawBlock +( int x, + int y, + int scrn, + int width, + int height, + byte* src ) +{ + byte* dest; + + /* [...snip...] */ + + dest = screens[scrn] + y*SCREENWIDTH+x; + + while (height--) /* { dg-bogus "infinite loop" } */ + { + __builtin_memcpy (dest, src, width); + src += width; + dest += SCREENWIDTH; + } +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c new file mode 100644 index 0000000..5a267be --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c @@ -0,0 +1,19 @@ +/* Reduced from glib, which has a g_error macro with this infinite + loop in it: + for (;;) ; + + Make sure we provide a readable warning for this case. */ + +extern void g_log_structured_standard (const char *); + +#define g_error(MSG) \ + do { \ + g_log_structured_standard (MSG); \ + for (;;) ; \ + } while (0) +/* { dg-message "5: infinite loop" "" { target *-*-* } .-2 } */ + +void test_g_error (void) +{ + g_error ("something went wrong"); /* { dg-message "in expansion of macro 'g_error'" } */ +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c new file mode 100644 index 0000000..aaa387f --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c @@ -0,0 +1,131 @@ +/* Various correct and incorrect ways to walk a linked list, accumulating + a value. */ + +/* { dg-additional-options "-O0" } */ + +extern int maybe_useful_work (); + +struct node +{ + struct node *next; + int val; +}; + +/* Various "while" loops. */ + +int correct_while_loop (struct node *n) +{ + int sum = 0; + while (n) + { + sum += n->val; + n = n->next; + } + return sum; +} + +int while_loop_missing_next (struct node *n) +{ + int sum = 0; + while (n) /* { dg-line "while_loop_missing_next_WHILE_LINE" } */ + { + sum += n->val; /* { dg-line "while_loop_missing_next_LOOP_BODY" } */ + /* We're missing: "n = n->next;", so n does not change */ + } + return sum; + + /* { dg-warning "10: infinite loop" "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */ + /* { dg-message "10: \\(2\\) when 'n' is non-NULL: always following 'true' branch\.\.\." "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */ + /* { dg-message "\\(3\\) \.\.\.to here" "" { target *-*-* } while_loop_missing_next_LOOP_BODY } */ + /* { dg-message "\\(4\\) looping back\.\.\." "" { target *-*-* } while_loop_missing_next_LOOP_BODY } */ + /* { dg-message "\\(5\\) \.\.\.to here" "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */ +} + +int while_loop_missing_next_with_work (struct node *n) +{ + int sum = 0; + while (n) /* { dg-bogus "infinite loop" } */ + { + sum += n->val; + /* We're missing: "n = n->next;", so n does not change */ + /* But here we do something that could be doing useful work. */ + maybe_useful_work (); + } + return sum; +} + +/* BUG: missing: "sum += ", so sum does not change. */ + +int while_loop_missing_add (struct node *n) +{ + int sum = 0; + while (n) /* { dg-warning "infinite loop" } */ + n->val; + return sum; +} + +/* Various "for" loops. */ + +int correct_for_loop (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter = iter->next) + sum += n->val; + return sum; +} + +int for_loop_missing_condition (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; ; iter = iter->next) + sum += n->val; /* { dg-warning "infinite loop" } */ + return sum; +} + +int for_loop_missing_next (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; ) /* { dg-warning "infinite loop" } */ + sum += n->val; + return sum; +} + +/* BUG: missing: "sum += ", so sum does not change. + Not an infinite loop though, as we do iterate to the + end of the list. */ + +int for_loop_missing_add (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter = iter->next) + n->val; /* { dg-bogus "infinite loop" } */ + return sum; +} + +/* BUG: "iter->next" should be "iter = iter->next". */ + +int for_loop_noop_next (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter->next) /* { dg-line for_loop_noop_next_FOR_LINE } */ + sum += n->val; /* { dg-line for_loop_noop_next_LOOP_BODY } */ + return sum; + + /* { dg-warning "31: infinite loop" "" { target *-*-* } for_loop_noop_next_FOR_LINE } */ + /* { dg-message "31: \\(2\\) when 'iter' is non-NULL: always following 'true' branch\.\.\." "" { target *-*-* } for_loop_noop_next_FOR_LINE } */ + /* { dg-message "\\(3\\) \.\.\.to here" "" { target *-*-* } for_loop_noop_next_LOOP_BODY } */ + /* { dg-message "\\(4\\) looping back\.\.\." "" { target *-*-* } for_loop_noop_next_LOOP_BODY } */ + /* { dg-message "\\(5\\) \.\.\.to here" "" { target *-*-* } for_loop_noop_next_FOR_LINE } */ +} + +/* BUG: "iter = n->next" should be "iter = iter->next" + and so it becomes an infinite loop at the 2nd element. */ + +int for_loop_wrong_next (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter = n->next) /* { dg-warning "infinite loop" "" { xfail *-*-* } } */ + /* TODO: xfail. */ + sum += n->val; + return sum; +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c b/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c index c885c92..9dd5590 100644 --- a/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c @@ -11,13 +11,13 @@ void test_direct (void) { - test_direct (); /* Ideally would warn here, but it becomes an infinite loop. */ -} + test_direct (); +} /* { dg-warning "infinite-loop" } */ void test_guarded (int flag) { - if (flag) - test_guarded (flag); /* Ideally would warn here, but it becomes an infinite loop. */ + if (flag) /* { dg-warning "infinite-loop" } */ + test_guarded (flag); } void test_flipped_guard (int flag) @@ -34,7 +34,7 @@ void test_param_variant (int depth) void test_unguarded_param_variant (int depth) { - test_unguarded_param_variant (depth - 1); /* Ideally would warn here, but it becomes an infinite loop. */ + test_unguarded_param_variant (depth - 1); /* { dg-warning "infinite-loop" } */ } int g; @@ -90,27 +90,23 @@ int test_do_while_postdecrement_param (int n) /* Various cases of decrementing "n" as the recursion proceeds where not every path recurses, but we're not actually checking "n", so - if "flag" is true it's an infinite recursion. */ + if "flag" is true it's an infinite recursion (which looks like an + infinite loop after inlining). */ void test_partially_guarded_postdecrement (int flag, int n) { - /* Ideally we'd catch this, but it becomes an infinite loop. */ - if (flag) + if (flag) /* { dg-warning "infinite loop" } */ test_partially_guarded_postdecrement (flag, n--); } void test_partially_guarded_predecrement (int flag, int n) { - /* We fail to report this; we see that "n" is changing, - though it isn't relevant to whether we recurse. */ - if (flag) - test_partially_guarded_predecrement (flag, --n); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */ + if (flag) /* { dg-warning "infinite loop" } */ + test_partially_guarded_predecrement (flag, --n); } void test_partially_guarded_subtract (int flag, int n) { - /* We fail to report this; we see that "n" is changing, - though it isn't relevant to whether we recurse. */ - if (flag) - test_partially_guarded_subtract (flag, n - 1); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */ + if (flag) /* { dg-warning "infinite loop" } */ + test_partially_guarded_subtract (flag, n - 1); } diff --git a/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c b/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c index c870a9f..5c971c5 100644 --- a/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c +++ b/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c @@ -56,13 +56,20 @@ outer (int flag) | | | (4) following 'true' branch (when 'flag != 0')... | + 'inner': event 5 (depth 3) + | + | + | #define NULL ((void *)0) + | ^ + | | + | (5) ...to here + { dg-end-multiline-output "" { target c } } */ +/* { dg-begin-multiline-output "" } + | return NULL; + | ^~~~ + | <-------------+ | - 'outer': event 5 (depth 1) - | - |cc1: - | (5): ...to here - | 'outer': event 6 (depth 1) | | return *middle (flag); @@ -100,13 +107,20 @@ outer (int flag) | | | (4) following 'true' branch (when 'flag != 0')... | + 'const char* inner(int)': event 5 (depth 3) + | + | + | #define NULL + | + | | + | (5) ...to here + { dg-end-multiline-output "" { target c++ } } */ +/* { dg-begin-multiline-output "" } + | return NULL; + | ^~~~ + | <-------------+ | - 'char outer(int)': event 5 (depth 1) - | - |cc1plus: - | (5): ...to here - | 'char outer(int)': event 6 (depth 1) | | return *middle (flag); diff --git a/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c b/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c index 435fb4f..6b6bba3 100644 --- a/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c @@ -141,7 +141,7 @@ void test_12 (void) while (1) { - free (ptr.value); + free (ptr.value); /* { dg-warning "infinite loop" } */ free (ptr.value); /* { dg-warning "double-'free' of 'ptr.value'" } */ } } diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-20.c b/gcc/testsuite/gcc.dg/analyzer/data-model-20.c index ff65883..59f6285 100644 --- a/gcc/testsuite/gcc.dg/analyzer/data-model-20.c +++ b/gcc/testsuite/gcc.dg/analyzer/data-model-20.c @@ -14,7 +14,11 @@ test (int n) { for (i = 0; i < n; i++) { if ((arr[i] = (struct foo *)malloc(sizeof(struct foo))) == NULL) { - for (; i >= 0; i++) { + for (; i >= 0; i++) { /* { dg-warning "infinite loop" } */ + /* This loop is in the wrong direction, so not technically an + infinite loop ("i" will eventually wrap around), but the + analyzer's condition handling treats the overflow as such. + In any case, the code is suspect and warrants a warning. */ free(arr[i]); /* { dg-bogus "double-'free'" } */ } free(arr); /* { dg-warning "leak" } */ diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-20a.c b/gcc/testsuite/gcc.dg/analyzer/data-model-20a.c new file mode 100644 index 0000000..767b991 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/data-model-20a.c @@ -0,0 +1,25 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ + +#include <stdlib.h> + +struct foo { int dummy; }; + +struct foo ** +test (int n) { + struct foo **arr; + int i; + + if ((arr = (struct foo **)malloc(n * sizeof(struct foo *))) == NULL) + return NULL; + + for (i = 0; i < n; i++) { + if ((arr[i] = (struct foo *)malloc(sizeof(struct foo))) == NULL) { + for (; i >= 0; i--) { + free(arr[i]); /* { dg-bogus "double-'free'" } */ + } + free(arr); /* { dg-bogus "leak" "" { xfail *-*-* } } */ + return NULL; + } + } + return arr; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/edges-1.c b/gcc/testsuite/gcc.dg/analyzer/edges-1.c index f08a614..644a2df 100644 --- a/gcc/testsuite/gcc.dg/analyzer/edges-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/edges-1.c @@ -15,6 +15,8 @@ void test_1 (const char *path, int flag) if (!fp) /* { dg-message "when 'fp' is non-NULL" } */ return; + bar (); + /* We shouldn't report this control flow. */ while (foo ()) /* { dg-bogus "" } */ bar (); diff --git a/gcc/testsuite/gcc.dg/analyzer/explode-2a.c b/gcc/testsuite/gcc.dg/analyzer/explode-2a.c index 32c71ca..d07ce5b 100644 --- a/gcc/testsuite/gcc.dg/analyzer/explode-2a.c +++ b/gcc/testsuite/gcc.dg/analyzer/explode-2a.c @@ -14,7 +14,7 @@ void test (void) explode-2.c as this code. */ int a = get (); int b = get (); - while (a) + while (a) /* { dg-warning "infinite loop" } */ { switch (b) { diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c b/gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c new file mode 100644 index 0000000..c3515bb --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c @@ -0,0 +1,235 @@ +/* { dg-additional-options "-O0" } */ + +extern int maybe_useful_work (); + +int global_var; +volatile int volatile_global_var; + +struct st +{ + int x; + int y; +}; + +static void __attribute__((noinline)) +do_nothing (void) +{ +} + +void test_empty_while_true () +{ + while (1) {} /* { dg-warning "infinite loop" } */ + /* { dg-message "looping back\.\.\." "" { target *-*-* } .-1 } */ + /* { dg-message "\.\.\.to here" "" { target *-*-* } .-2 } */ +} + +void test_empty_do_while () +{ + do {} while (1); /* { dg-warning "infinite loop" } */ + /* { dg-message "looping back\.\.\." "" { target *-*-* } .-1 } */ + /* { dg-message "\.\.\.to here" "" { target *-*-* } .-2 } */ +} + +void test_empty_for () +{ + for (;;) {} /* { dg-warning "infinite loop" } */ + /* { dg-message "looping back\.\.\." "" { target *-*-* } .-1 } */ + /* { dg-message "\.\.\.to here" "" { target *-*-* } .-2 } */ +} + +void test_while_true_maybe_useful_work () +{ + while (1) + maybe_useful_work (); +} + +void test_while_true_interproc_empty () +{ + /* Depending on optimization level, location is sometimes + on "while", sometimes on "do_nothing", and sometimes the + unknown location. */ + while (1) + do_nothing (); /* { dg-warning "infinite loop" } */ +} + +void test_while_true_increment_local () +{ + int i = 0; + while (1) + i++; /* { dg-warning "infinite loop" } */ +} + +void test_while_true_increment_global () +{ + while (1) + global_var++; +} + +void test_guarded_while_true_increment_local (int flag) +{ + if (flag) + { + int i = 0; + while (1) + i++; /* { dg-warning "infinite loop" } */ + } +} + +void test_while_local_flag_increment_local (int flag) +{ + int i = 0; + while (flag) /* { dg-warning "infinite loop" } */ + i++; +} + +extern int check_flag (void); + +void test_while_calling_fn (void) +{ + while (check_flag ()) + do_nothing (); +} + +void test_missing_parens_on_call (void) +{ + while (check_flag) + do_nothing (); /* { dg-warning "infinite loop" } */ +} + +void test_iteration_copy_and_paste_error (int m, int n) +{ + /* Wrong variable is incremented in inner "for" loop, thus + effectively an infinite loop. */ + float arr[m][n]; + for (int i = 0; i < m; i++) + for (int j = 0; j < n; i++) /* { dg-warning "infinite loop" } */ + arr[i][j] = 0.f; +} + +void test_missing_comparison_in_for_condition_1 (int n) +{ + /* Should have been "i < n", rather than just "n". */ + for (int i = 0; n; i++) /* { dg-warning "infinite loop" } */ + { + } +} + +int test_missing_comparison_in_for_condition_2 (int val, int *arr, int n) +{ + /* Should have been "i < n", rather than just "n". */ + int acc = 0; + for (int i = 0; n; i++) /* { dg-warning "infinite loop" } */ + acc += arr[i]; + return acc; +} + +void test_non_volatile_local_1 (void) +{ + int flag = 0; + while (!flag) /* { dg-warning "infinite loop" } */ + { + } +} + +void test_non_volatile_local_2a (void) +{ + int flag = 0; + + /* Perhaps should complain about this. + Although the infinite loop might be doing useful work, + "while (!flag)" is a misleading way to spell "infinite loop". */ + while (!flag) + maybe_useful_work (); +} + +void test_non_volatile_local_2b (void) +{ + int flag = 0; + + while (!flag) + flag = maybe_useful_work (); +} + +void test_non_volatile_local_3a (int n) +{ + int i = 0; + + /* Perhaps should complain about this. + Although the infinite loop might be doing useful work, + "while (i < n)" is a misleading way to spell "infinite loop". */ + while (i < n) + maybe_useful_work (); +} + +void test_non_volatile_local_3b (int n) +{ + int i = 0; + + while (i < n) + { + maybe_useful_work (); + i++; + } +} + +void test_volatile_local (void) +{ + volatile int flag = 0; + while (!flag) /* { dg-bogus "infinite loop" } */ + { + } +} + +void test_non_volatile_global (void) +{ + /* Not sure if we should warn here. */ + while (!global_var) /* { dg-warning "infinite loop" } */ + { + } +} + +void test_volatile_global (void) +{ + while (!volatile_global_var) /* { dg-bogus "infinite loop" } */ + { + } +} + +void test_field_1 (struct st *p) +{ + /* Not sure if we should warn here. */ + while (!p->x) /* { dg-warning "infinite loop" } */ + { + } +} + +void test_field_2 (struct st *p) +{ + while (!p->x) /* { dg-bogus "infinite loop" } */ + maybe_useful_work (); +} + + +int missing_init_of_i (int *arr, unsigned n) +{ + int sum = 0; + for (int i; i < n; i--) /* { dg-warning "use of uninitialized value 'i'" } */ + sum += arr[i]; + return sum; +} + +void test_switch (char *pc) +{ + while (1) + { + char opcode = *pc; /* { dg-warning "infinite loop" } */ + switch (opcode) /* { dg-message "if it ever follows 'default:' branch, it will always do so\.\.\." } */ + { + case 'A': + pc++; + break; + case 'B': + return; + } + } +} diff --git a/gcc/testsuite/gcc.dg/analyzer/malloc-1.c b/gcc/testsuite/gcc.dg/analyzer/malloc-1.c index 6b5590a..2a42a05 100644 --- a/gcc/testsuite/gcc.dg/analyzer/malloc-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/malloc-1.c @@ -124,7 +124,7 @@ void test_12 (void) while (1) { - free (ptr); + free (ptr); /* { dg-warning "infinite loop" } */ free (ptr); /* { dg-warning "double-'free' of 'ptr'" } */ } } diff --git a/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c b/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c index cd0f4b7..7af4c37 100644 --- a/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c +++ b/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c @@ -3,7 +3,7 @@ void add_zero_terminator (char *buf) { char *end = buf; - while (end++); + while (end++); /* TODO: arguably we should report this. */ if (buf < end) end[-1] = '\0'; } diff --git a/gcc/testsuite/gcc.dg/analyzer/paths-4.c b/gcc/testsuite/gcc.dg/analyzer/paths-4.c index b72e658..60b3a0c 100644 --- a/gcc/testsuite/gcc.dg/analyzer/paths-4.c +++ b/gcc/testsuite/gcc.dg/analyzer/paths-4.c @@ -26,9 +26,10 @@ int test_2 (struct state *s) while (1) { __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */ + /* { dg-warning "infinite loop" "" { target *-*-* } .-1 } */ __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */ /* TODO: why does the above need an extra stmt to merge state? */ - switch (s->mode) + switch (s->mode) /* { dg-message "if it ever follows 'default:' branch, it will always do so\.\.\." } */ { case 0: __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */ diff --git a/gcc/testsuite/gcc.dg/analyzer/pr103892.c b/gcc/testsuite/gcc.dg/analyzer/pr103892.c index 95d4b17..d16cd83 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr103892.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr103892.c @@ -38,7 +38,7 @@ typedef struct pipecmd_sequence pipecmd_sequence_t; static char *argstr_get_word (const char **argstr) { - while (**argstr) { + while (**argstr) { /* { dg-warning "infinite loop" } */ switch (**argstr) { case ' ': case '\t': diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93546.c b/gcc/testsuite/gcc.dg/analyzer/pr93546.c index 66f6805..07898e9 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr93546.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr93546.c @@ -5,7 +5,7 @@ void ch (int x1) { ({ bx: &&bx; }); - while (x1 == 0) + while (x1 == 0) /* { dg-warning "infinite loop" } */ { } } diff --git a/gcc/timevar.def b/gcc/timevar.def index d21b08c..9628223 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -342,6 +342,7 @@ DEFTIMEVAR (TV_ANALYZER_STATE_PURGE , "analyzer: state purge") DEFTIMEVAR (TV_ANALYZER_PLAN , "analyzer: planning") DEFTIMEVAR (TV_ANALYZER_SCC , "analyzer: scc") DEFTIMEVAR (TV_ANALYZER_WORKLIST , "analyzer: processing worklist") +DEFTIMEVAR (TV_ANALYZER_INFINITE_LOOPS, "analyzer: finding infinite loops") DEFTIMEVAR (TV_ANALYZER_DUMP , "analyzer: dump") DEFTIMEVAR (TV_ANALYZER_DIAGNOSTICS , "analyzer: emitting diagnostics") DEFTIMEVAR (TV_ANALYZER_SHORTEST_PATHS, "analyzer: shortest paths") |