@@ -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 \
@@ -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.
@@ -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,
@@ -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);
@@ -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
@@ -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);
@@ -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);
new file mode 100644
@@ -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));
+ }
+ }
+}
@@ -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)
@@ -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,
@@ -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
@@ -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> ());
}
@@ -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. */
}
@@ -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;
};
@@ -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);
@@ -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
@@ -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 *-*-* } } */
}
}
new file mode 100644
@@ -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?
+}
new file mode 100644
@@ -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 ();
+}
new file mode 100644
@@ -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;
+}
new file mode 100644
@@ -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");
+}
new file mode 100644
@@ -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;
+ }
+}
new file mode 100644
@@ -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'" } */
+}
new file mode 100644
@@ -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;
+}
@@ -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);
}
@@ -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);
@@ -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'" } */
}
}
@@ -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" } */
new file mode 100644
@@ -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;
+}
@@ -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 ();
@@ -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)
{
new file mode 100644
@@ -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;
+ }
+ }
+}
@@ -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'" } */
}
}
@@ -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';
}
@@ -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" } */
@@ -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':
@@ -5,7 +5,7 @@ void
ch (int x1)
{
({ bx: &&bx; });
- while (x1 == 0)
+ while (x1 == 0) /* { dg-warning "infinite loop" } */
{
}
}
@@ -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")