#include "config.h"
#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 "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"
#include "diagnostic-format-sarif.h"

Include dependency graph for infinite-loop.cc:

Data Structures
struct	infinite_loop

class	perpetual_start_cfg_edge_event

class	looping_back_event

class	infinite_loop_diagnostic

class	infinite_loop_checking_context

Macros
#define	INCLUDE_VECTOR

#define	PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"

Functions
static const exploded_edge *	get_in_edge_back_edge (const exploded_node &enode)

static std::unique_ptr< infinite_loop >	starts_infinite_loop_p (const exploded_node &enode, const exploded_graph &eg, logger *logger)

Macro Definition Documentation

◆ INCLUDE_VECTOR

#define INCLUDE_VECTOR

Detection of infinite loops.
   Copyright (C) 2022-2024 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/>.

◆ PROPERTY_PREFIX

#define PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"

Referenced by infinite_loop_diagnostic::maybe_add_sarif_properties().

Function Documentation

◆ get_in_edge_back_edge()

static const exploded_edge * get_in_edge_back_edge ( const exploded_node & enode )

static

If ENODE has an in-edge corresponding to a CFG backedge, return that
exploded in-edge.
Otherwise, return nullptr.

References ana::cfg_superedge::back_edge_p(), ana::superedge::dyn_cast_cfg_superedge(), and dnode< GraphTraits >::m_preds.

Referenced by starts_infinite_loop_p().

◆ starts_infinite_loop_p()

static std::unique_ptr< infinite_loop > starts_infinite_loop_p	(	const exploded_node &	enode,
		const exploded_graph &	eg,
		logger *	logger )

static

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.

References BUILTINS_LOCATION, ana::exploded_edge::could_do_work_p(), free(), ana::superedge::get_any_cfg_edge(), get_in_edge_back_edge(), ana::program_point::get_location(), ana::exploded_node::get_point(), ana::exploded_node::get_state(), ana::exploded_node::get_status(), ana::exploded_graph::get_supergraph(), ana::logger::log(), LOG_FUNC_1, dedge< GraphTraits >::m_dest, ana::exploded_node::m_index, ana::program_state::m_region_model, ana::exploded_edge::m_sedge, dnode< GraphTraits >::m_succs, make_unique(), ana::feasibility_state::maybe_update_for_edge(), pp_formatted_text(), pp_printf(), ana::exploded_node::STATUS_WORKLIST, UNKNOWN_LOCATION, infinite_loop_checking_context::unusable_p(), and visited.

Referenced by ana::exploded_graph::detect_infinite_loops().

Data Structures