pointer_analysis Namespace Reference

Data Structures
struct	constraint
struct	constraint_expr
struct	constraint_stats
struct	variable_info

Typedefs
typedef struct constraint_expr	ce_s
typedef struct constraint *	constraint_t
typedef struct variable_info *	varinfo_t

Enumerations
enum	constraint_expr_type { SCALAR , DEREF , ADDRESSOF }
enum	{   nothing_id = 1 , anything_id = 2 , string_id = 3 , escaped_id = 4 ,   nonlocal_id = 5 , escaped_return_id = 6 , storedanything_id = 7 , integer_id = 8 }
enum	{   fi_clobbers = 1 , fi_uses = 2 , fi_static_chain = 3 , fi_result = 4 ,   fi_parm_base = 5 }

Functions
varinfo_t	lookup_vi_for_tree (tree t)
varinfo_t	lookup_call_use_vi (gcall *call)
varinfo_t	lookup_call_clobber_vi (gcall *call)
varinfo_t	get_fi_for_callee (gcall *call)
void	init_constraint_builder (void)
void	delete_constraint_builder (void)
void	intra_build_constraints (void)
void	ipa_build_constraints (void)
void	solve_constraints (void)
varinfo_t	first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
varinfo_t	first_or_preceding_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
void	determine_global_memory_access (gcall *stmt, bool *writes_global_memory, bool *reads_global_memory, bool *uses_global_memory)
bool	fndecl_maybe_in_other_partition (tree fndecl)
varinfo_t	new_var_info (tree t, const char *name, bool add_id)
void	dump_constraint (FILE *file, constraint_t c)
DEBUG_FUNCTION void	debug_constraint (constraint_t c)
void	dump_constraints (FILE *file, int from)
DEBUG_FUNCTION void	debug_constraints (void)
void	dump_solution_for_var (FILE *file, unsigned int var)
DEBUG_FUNCTION void	debug_solution_for_var (unsigned int var)
void	dump_sa_stats (FILE *outfile)
void	dump_sa_points_to_info (FILE *outfile)
DEBUG_FUNCTION void	debug_sa_points_to_info (void)
void	dump_varinfo (FILE *file, varinfo_t vi)
DEBUG_FUNCTION void	debug_varinfo (varinfo_t vi)
void	dump_varmap (FILE *file)
DEBUG_FUNCTION void	debug_varmap (void)
varinfo_t	get_varinfo (unsigned int n)
varinfo_t	vi_next (varinfo_t vi)

Variables
bool	use_field_sensitive = true
int	in_ipa_mode = 0
bitmap_obstack	pta_obstack
bitmap_obstack	oldpta_obstack
vec< varinfo_t >	varmap
vec< constraint_t >	constraints
unsigned int *	var_rep
struct constraint_stats	stats

Detailed Description

Constraint builder for tree based points-to analysis
Copyright (C) 2005-2025 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, 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/>.   

Andersen-style solver for tree based points-to analysis
Copyright (C) 2005-2025 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, 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/>.   

Tree based points-to analysis
Copyright (C) 2005-2025 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, 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/>.   

NOTE: This file declares the internal interface of the points-to analyzer.
Outward-facing function declarations can be found in tree-ssa-alias.h.   

Typedef Documentation

ce_s

typedef struct constraint_expr pointer_analysis::ce_s

constraint_t

typedef struct constraint* pointer_analysis::constraint_t

varinfo_t

typedef struct variable_info* pointer_analysis::varinfo_t

Enumeration Type Documentation

anonymous enum

anonymous enum

Static IDs for the special variables.  Variable ID zero is unused
and used as terminator for the sub-variable chain.   

Enumerator
nothing_id
anything_id
string_id
escaped_id
nonlocal_id
escaped_return_id
storedanything_id
integer_id

anonymous enum

anonymous enum

In IPA mode there are varinfos for different aspects of reach
function designator.  One for the points-to set of the return
value, one for the variables that are clobbered by the function,
one for its uses and one for each parameter (including a single
glob for remaining variadic arguments).   

Enumerator
fi_clobbers
fi_uses
fi_static_chain
fi_result
fi_parm_base

constraint_expr_type

enum pointer_analysis::constraint_expr_type

Enumerator
SCALAR
DEREF
ADDRESSOF

Function Documentation

debug_constraint()

void pointer_analysis::debug_constraint

(

constraint_t

c

)

Print out constraint C to stderr.   

References dump_constraint().

debug_constraints()

void pointer_analysis::debug_constraints

(

void

)

Print out all constraints to stderr.   

References dump_constraints().

debug_sa_points_to_info()

void pointer_analysis::debug_sa_points_to_info

(

void

)

Debug points-to information to stderr.   

References dump_sa_points_to_info().

debug_solution_for_var()

void pointer_analysis::debug_solution_for_var

(

unsigned int

var

)

Print the points-to solution for VAR to stderr.   

References dump_solution_for_var().

debug_varinfo()

void pointer_analysis::debug_varinfo

(

varinfo_t

vi

)

Dump varinfo VI to stderr.   

References dump_varinfo().

debug_varmap()

void pointer_analysis::debug_varmap

(

void

)

Dump varmap to stderr.   

References dump_varmap().

delete_constraint_builder()

void pointer_analysis::delete_constraint_builder

(

void

)

Deallocate constraint builder globals.   

References call_stmt_vars, constraint_pool, fake_var_decl_obstack, NULL, and vi_for_tree.

Referenced by delete_points_to_sets().

determine_global_memory_access()

void pointer_analysis::determine_global_memory_access	(	gcall *	stmt,
		bool *	writes_global_memory,
		bool *	reads_global_memory,
		bool *	uses_global_memory )

Determine global memory access of call STMT and update
WRITES_GLOBAL_MEMORY, READS_GLOBAL_MEMORY and USES_GLOBAL_MEMORY.   

References symtab_node::binds_to_current_def_p(), modref_summary::calls_interposable, gcc_assert, cgraph_node::get(), get_modref_function_summary(), gimple_call_fndecl(), gimple_call_fnspec(), modref_summary::global_memory_read, attr_fnspec::global_memory_read_p(), modref_summary::global_memory_written, attr_fnspec::global_memory_written_p(), attr_fnspec::known_p(), NULL, and NULL_TREE.

Referenced by compute_points_to_sets(), and handle_rhs_call().

dump_constraint()

void pointer_analysis::dump_constraint	(	FILE *	file,
		constraint_t	c )

Print out constraint C to FILE.   

References ADDRESSOF, DEREF, dump_file, get_varinfo(), HOST_WIDE_INT_PRINT_DEC, and UNKNOWN_OFFSET.

Referenced by debug_constraint(), dump_constraint_graph(), dump_constraints(), and rewrite_constraints().

dump_constraints()

void pointer_analysis::dump_constraints	(	FILE *	file,
		int	from )

Print out all constraints to FILE.   

References constraints, dump_constraint(), and i.

Referenced by debug_constraints(), intra_build_constraints(), ipa_build_constraints(), ipa_create_function_infos(), ipa_create_global_variable_infos(), and ipa_pta_execute().

dump_sa_points_to_info()

void pointer_analysis::dump_sa_points_to_info

(

FILE *

outfile

)

Dump points-to information to OUTFILE.   

References dump_solution_for_var(), get_varinfo(), i, pointer_analysis::variable_info::may_have_pointers, and varmap.

Referenced by compute_points_to_sets(), debug_sa_points_to_info(), and ipa_pta_execute().

dump_sa_stats()

void pointer_analysis::dump_sa_stats

(

FILE *

outfile

)

Dump stats information to OUTFILE.   

References stats.

Referenced by compute_points_to_sets(), and ipa_pta_execute().

dump_solution_for_var()

void pointer_analysis::dump_solution_for_var	(	FILE *	file,
		unsigned int	var )

Print out the points-to solution for VAR to FILE.   

References EXECUTE_IF_SET_IN_BITMAP, get_varinfo(), i, pointer_analysis::variable_info::id, pointer_analysis::variable_info::name, pointer_analysis::variable_info::solution, and var_rep.

Referenced by debug_solution_for_var(), and dump_sa_points_to_info().

dump_varinfo()

void pointer_analysis::dump_varinfo	(	FILE *	file,
		varinfo_t	vi )

Dump varinfo VI to FILE.   

References bitmap_empty_p(), bitmap_equal_p(), EXECUTE_IF_SET_IN_BITMAP, pointer_analysis::variable_info::fullsize, pointer_analysis::variable_info::head, HOST_WIDE_INT_0U, HOST_WIDE_INT_PRINT_DEC, i, pointer_analysis::variable_info::id, pointer_analysis::variable_info::is_artificial_var, pointer_analysis::variable_info::is_fn_info, pointer_analysis::variable_info::is_full_var, pointer_analysis::variable_info::is_global_var, pointer_analysis::variable_info::is_heap_var, pointer_analysis::variable_info::is_ipa_escape_point, pointer_analysis::variable_info::is_restrict_var, pointer_analysis::variable_info::is_special_var, pointer_analysis::variable_info::is_unknown_size_var, pointer_analysis::variable_info::may_have_pointers, pointer_analysis::variable_info::name, pointer_analysis::variable_info::next, NULL, pointer_analysis::variable_info::offset, pointer_analysis::variable_info::oldsolution, pointer_analysis::variable_info::only_restrict_pointers, pointer_analysis::variable_info::ruid, pointer_analysis::variable_info::size, and pointer_analysis::variable_info::solution.

Referenced by debug_varinfo(), and dump_varmap().

dump_varmap()

void pointer_analysis::dump_varmap

(

FILE *

file

)

Dump varmap to FILE.   

References dump_varinfo(), get_varinfo(), i, and varmap.

Referenced by debug_varmap().

first_or_preceding_vi_for_offset()

varinfo_t pointer_analysis::first_or_preceding_vi_for_offset	(	varinfo_t	start,
		unsigned HOST_WIDE_INT	offset )

Find the first varinfo in the same variable as START that overlaps with
OFFSET.  If there is no such varinfo the varinfo directly preceding
OFFSET is returned.   

References get_varinfo(), and vi_next().

Referenced by do_ds_constraint(), do_sd_constraint(), get_constraint_for_ptr_offset(), and set_union_with_increment().

first_vi_for_offset()

varinfo_t pointer_analysis::first_vi_for_offset	(	varinfo_t	start,
		unsigned HOST_WIDE_INT	offset )

Find the first varinfo in the same variable as START that overlaps with
OFFSET.  Return NULL if we can't find one.   

References get_varinfo(), NULL, and vi_next().

Referenced by create_function_info_for(), find_func_clobbers(), get_function_part_constraint(), and ipa_pta_execute().

fndecl_maybe_in_other_partition()

bool pointer_analysis::fndecl_maybe_in_other_partition

(

tree

fndecl

)

Return true if FNDECL may be part of another lto partition.   

References cgraph_node::get(), symtab_node::in_other_partition, and NULL.

Referenced by find_func_aliases_for_builtin_call(), find_func_clobbers(), and ipa_pta_execute().

get_fi_for_callee()

varinfo_t pointer_analysis::get_fi_for_callee

(

gcall *

call

)

Return the varinfo for the callee of CALL.   

References anything_id, get_varinfo(), get_vi_for_tree(), gimple_call_addr_fndecl(), gimple_call_fn(), OBJ_TYPE_REF_EXPR, SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, and TREE_CODE.

Referenced by find_func_aliases_for_call(), find_func_clobbers(), and ipa_pta_execute().

get_varinfo()

varinfo_t pointer_analysis::get_varinfo ( unsigned int n )

inline

Return the varmap element N.   

References varmap.

Referenced by add_graph_edge(), build_pred_graph(), build_succ_graph(), compute_dependence_clique(), compute_points_to_sets(), create_function_info_for(), do_complex_constraint(), do_ds_constraint(), do_sd_constraint(), do_structure_copy(), dump_constraint(), dump_constraint_graph(), dump_pred_graph(), dump_sa_points_to_info(), dump_solution_for_var(), dump_varmap(), eliminate_indirect_cycles(), find_func_aliases_for_builtin_call(), find_what_var_points_to(), first_or_preceding_vi_for_offset(), first_vi_for_offset(), get_constraint_for_1(), get_constraint_for_component_ref(), get_constraint_for_ptr_offset(), get_fi_for_callee(), get_vi_for_tree(), ipa_pta_execute(), move_complex_constraints(), perform_var_substitution(), process_constraint(), rewrite_constraints(), set_uids_in_ptset(), set_union_with_increment(), solution_set_expand(), solve_add_graph_edge(), solve_graph(), unify_nodes(), vi_next(), and visit_loadstore().

init_constraint_builder()

void pointer_analysis::init_constraint_builder

(

void

)

Initialize constraint builder.   

References call_stmt_vars, fake_var_decl_obstack, gcc_obstack_init, init_base_vars(), and vi_for_tree.

Referenced by init_alias_vars().

intra_build_constraints()

void pointer_analysis::intra_build_constraints

(

void

)

Build constraints for intraprocedural mode.   

References cfun, dump_constraints(), dump_file, dump_flags, find_func_aliases(), FOR_EACH_BB_FN, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), intra_create_variable_infos(), TDF_DETAILS, and virtual_operand_p().

Referenced by compute_points_to_sets().

ipa_build_constraints()

void pointer_analysis::ipa_build_constraints

(

void

)

Build constraints for ipa mode.   

References cfun, cgraph_node::clone_of, constraints, symtab_node::decl, DECL_ASSEMBLER_NAME, DECL_ASSEMBLER_NAME_SET_P, DECL_STRUCT_FUNCTION, dump_constraints(), dump_file, dump_flags, symtab_node::dump_name(), find_func_aliases(), find_func_clobbers(), FOR_EACH_BB_FN, FOR_EACH_DEFINED_FUNCTION, gcc_assert, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), cgraph_node::has_gimple_body_p(), IDENTIFIER_POINTER, symtab_node::in_other_partition, ipa_create_function_infos(), ipa_create_global_variable_infos(), NULL, TDF_DETAILS, and virtual_operand_p().

Referenced by ipa_pta_execute().

lookup_call_clobber_vi()

varinfo_t pointer_analysis::lookup_call_clobber_vi

(

gcall *

call

)

Lookup the variable for the call statement CALL representing
the clobbers.  Returns NULL if there is nothing special about this call.   

References lookup_call_use_vi(), NULL, and vi_next().

Referenced by compute_points_to_sets(), find_func_clobbers(), and ipa_pta_execute().

lookup_call_use_vi()

varinfo_t pointer_analysis::lookup_call_use_vi

(

gcall *

call

)

Lookup the variable for the call statement CALL representing
the uses.  Returns NULL if there is nothing special about this call.   

References call_stmt_vars, and NULL.

Referenced by compute_points_to_sets(), find_func_clobbers(), ipa_pta_execute(), and lookup_call_clobber_vi().

lookup_vi_for_tree()

varinfo_t pointer_analysis::lookup_vi_for_tree

(

tree

t

)

Find the variable info for tree T in VI_FOR_TREE.  If T does not
exist in the map, return NULL, otherwise, return the varinfo we found.   

References NULL, and vi_for_tree.

Referenced by compute_dependence_clique(), create_function_info_for(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_clobbers(), find_what_p_points_to(), ipa_pta_execute(), and visit_loadstore().

new_var_info()

varinfo_t pointer_analysis::new_var_info	(	tree	t,
		const char *	name,
		bool	add_id )

Return a new variable info structure consisting for a variable
named NAME, and using constraint graph node NODE.  Append it
to the vector of variable info structures.   

References pointer_analysis::variable_info::address_taken, BITMAP_ALLOC, pointer_analysis::variable_info::decl, DECL_HARD_REGISTER, DECL_P, dump_file, free(), ggc_strdup, pointer_analysis::variable_info::head, pointer_analysis::variable_info::id, pointer_analysis::variable_info::is_artificial_var, pointer_analysis::variable_info::is_fn_info, pointer_analysis::variable_info::is_full_var, is_global_var(), pointer_analysis::variable_info::is_global_var, pointer_analysis::variable_info::is_heap_var, pointer_analysis::variable_info::is_ipa_escape_point, pointer_analysis::variable_info::is_reg_var, pointer_analysis::variable_info::is_restrict_var, pointer_analysis::variable_info::is_special_var, pointer_analysis::variable_info::is_unknown_size_var, pointer_analysis::variable_info::may_have_pointers, pointer_analysis::variable_info::name, pointer_analysis::variable_info::next, NULL, NULL_TREE, pointer_analysis::variable_info::oldsolution, pointer_analysis::variable_info::only_restrict_pointers, pta_obstack, pointer_analysis::variable_info::ruid, pointer_analysis::variable_info::shadow_var_uid, pointer_analysis::variable_info::solution, stats, TREE_CODE, VAR_P, variable_info_pool, and varmap.

Referenced by create_function_info_for(), create_variable_info_for(), create_variable_info_for_1(), get_call_vi(), handle_call_arg(), handle_rhs_call(), init_base_vars(), make_heapvar(), and new_scalar_tmp_constraint_exp().

solve_constraints()

void pointer_analysis::solve_constraints

(

void

)

Solve the constraint set.  The entry function of the solver.   

Solve the constraint set.   

References bitmap_empty_p(), build_pred_graph(), build_succ_graph(), constraints, delete_graph(), dump_constraint_graph(), dump_file, dump_flags, find_indirect_cycles(), free(), free_var_substitution_info(), gcc_assert, i, init_graph(), integer_id, map, move_complex_constraints(), perform_var_substitution(), remove_preds_and_fake_succs(), rewrite_constraints(), si, solve_graph(), TDF_GRAPH, union_find_compress_all(), unite_pointer_equivalences(), var_rep, and varmap.

Referenced by compute_points_to_sets(), and ipa_pta_execute().

vi_next()

varinfo_t pointer_analysis::vi_next ( varinfo_t vi )

inline

Return the next variable in the list of sub-variables of VI
or NULL if VI is the last sub-variable.   

References get_varinfo(), and pointer_analysis::variable_info::next.

Referenced by build_pred_graph(), create_variable_info_for(), create_variable_info_for_1(), do_ds_constraint(), do_sd_constraint(), first_or_preceding_vi_for_offset(), first_vi_for_offset(), get_call_clobber_vi(), get_constraint_for_1(), get_constraint_for_component_ref(), get_constraint_for_ptr_offset(), get_constraint_for_ssa_var(), intra_create_variable_infos(), ipa_pta_execute(), lookup_call_clobber_vi(), make_param_constraints(), set_union_with_increment(), and solution_set_expand().

Variable Documentation

constraints

vec< constraint_t > pointer_analysis::constraints

List of constraints that we use to build the constraint graph from.   

Referenced by build_pred_graph(), build_succ_graph(), delete_points_to_sets(), do_deref(), dump_constraints(), init_alias_vars(), init_base_vars(), ipa_build_constraints(), ipa_create_function_infos(), ipa_create_global_variable_infos(), move_complex_constraints(), process_constraint(), rewrite_constraints(), and solve_constraints().

in_ipa_mode

int pointer_analysis::in_ipa_mode = 0

Referenced by create_variable_info_for(), create_variable_info_for_1(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), find_func_clobbers(), find_what_var_points_to(), get_function_part_constraint(), ipa_pta_execute(), and set_uids_in_ptset().

oldpta_obstack

bitmap_obstack pointer_analysis::oldpta_obstack

Used for oldsolution members of variables.   

Referenced by init_alias_vars(), and solve_graph().

pta_obstack

bitmap_obstack pointer_analysis::pta_obstack

Used for points-to sets.   

Referenced by add_graph_edge(), delete_points_to_sets(), init_alias_vars(), merge_graph_nodes(), new_var_info(), and solve_graph().

stats

struct constraint_stats pointer_analysis::stats

Referenced by dump_sa_stats(), and new_var_info().

use_field_sensitive

bool pointer_analysis::use_field_sensitive = true

Referenced by create_variable_info_for_1(), get_constraint_for_ptr_offset(), and init_alias_vars().

var_rep

unsigned int * pointer_analysis::var_rep

The representative variable for a variable.  The points-to solution for a
var can be found in its rep.  Trivially, a var can be its own rep.

The solver provides this array once it is done solving.   

Referenced by compute_dependence_clique(), delete_points_to_sets(), dump_solution_for_var(), find_what_var_points_to(), ipa_pta_execute(), set_uids_in_ptset(), solve_constraints(), and visit_loadstore().

varmap

vec< varinfo_t > pointer_analysis::varmap

Table of variable info structures for constraint variables.
Indexed directly by variable info id.   

Referenced by build_pred_graph(), delete_points_to_sets(), dump_sa_points_to_info(), dump_varmap(), get_varinfo(), init_alias_vars(), init_base_vars(), ipa_pta_execute(), new_var_info(), process_constraint(), remove_preds_and_fake_succs(), and solve_constraints().