GCC Middle and Back End API Reference
pta-andersen.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree-ssa-structalias.h"
#include "pta-andersen.h"
Include dependency graph for pta-andersen.cc:

Data Structures

struct  constraint_graph
class  scc_info
struct  equiv_class_label
struct  equiv_class_hasher

Namespaces

namespace  pointer_analysis

Macros

#define FIRST_REF_NODE   (varmap).length ()
#define LAST_REF_NODE   (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d)

Typedefs

typedef struct constraint_graphconstraint_graph_t
typedef struct equiv_class_labelequiv_class_label_t
typedef const struct equiv_class_labelconst_equiv_class_label_t

Functions

static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool)
static unsigned int find (unsigned int node)
static bool unite (unsigned int to, unsigned int from)
static void union_find_compress_all (void)
static void dump_constraint_graph (FILE *file)
DEBUG_FUNCTION void debug_constraint_graph (void)
static bool constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
static bool constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
static bool constraint_less (const constraint_t &a, const constraint_t &b)
static bool constraint_equal (const constraint &a, const constraint &b)
static constraint_t constraint_vec_find (vec< constraint_t > vec, constraint &lookfor)
static bool constraint_set_union (vec< constraint_t > *to, vec< constraint_t > *from)
static bitmap solution_set_expand (bitmap set, bitmap *expanded)
static bool set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc, bitmap *expanded_delta)
static void insert_into_complex (constraint_graph_t graph, unsigned int var, constraint_t c)
static bool merge_node_constraints (constraint_graph_t graph, unsigned int to, unsigned int from)
static void clear_edges_for_node (constraint_graph_t graph, unsigned int node)
static void merge_graph_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
static void add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, unsigned int from)
static void add_pred_graph_edge (constraint_graph_t graph, unsigned int to, unsigned int from)
static bool add_graph_edge (constraint_graph_t graph, unsigned int to, unsigned int from)
static void init_graph (unsigned int size)
static void build_pred_graph (void)
static void build_succ_graph (void)
static void scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
static bool solve_add_graph_edge (constraint_graph_t graph, unsigned int to, unsigned int from)
static void do_sd_constraint (constraint_graph_t graph, constraint_t c, bitmap delta, bitmap *expanded_delta)
static void do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
static void do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta, bitmap *expanded_delta)
static void find_indirect_cycles (constraint_graph_t graph)
static void topo_visit (constraint_graph_t graph, vec< unsigned > &topo_order, sbitmap visited, unsigned int n)
static auto_vec< unsigned > compute_topo_order (constraint_graph_t graph)
static equiv_class_labelequiv_class_lookup_or_add (hash_table< equiv_class_hasher > *table, bitmap labels)
static void condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
static void label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
static void dump_pred_graph (class scc_info *si, FILE *file)
static class scc_infoperform_var_substitution (constraint_graph_t graph)
static void free_var_substitution_info (class scc_info *si)
static unsigned int find_equivalent_node (constraint_graph_t graph, unsigned int node, unsigned int label)
static void unite_pointer_equivalences (constraint_graph_t graph)
static void move_complex_constraints (constraint_graph_t graph)
static void rewrite_constraints (constraint_graph_t graph, class scc_info *si)
static bool eliminate_indirect_cycles (unsigned int node)
static void solve_graph (constraint_graph_t graph)
void delete_graph (void)
static void remove_preds_and_fake_succs (constraint_graph_t graph)
void pointer_analysis::solve_constraints (void)

Variables

static bitmap_obstack predbitmap_obstack
static bitmap_obstack iteration_obstack
static constraint_graph_t graph
static bitmap changed
static hash_table< equiv_class_hasher > * pointer_equiv_class_table
static hash_table< equiv_class_hasher > * location_equiv_class_table
struct obstack equiv_class_obstack
static int pointer_equiv_class
static int location_equiv_class

Macro Definition Documentation

◆ EXECUTE_IF_IN_NONNULL_BITMAP

#define EXECUTE_IF_IN_NONNULL_BITMAP ( a,
b,
c,
d )
Value:
if (a) \
EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
Ca const poly_int< N, Cb > & b
Definition poly-int.h:771
Ca & a
Definition poly-int.h:770

Referenced by condense_visit(), dump_constraint_graph(), dump_pred_graph(), label_visit(), scc_visit(), and solve_graph().

◆ FIRST_REF_NODE

#define FIRST_REF_NODE   (varmap).length ()
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/>.   
During variable substitution and the offline version of indirect
cycle finding, we create nodes to represent dereferences and
address taken constraints.  These represent where these start and
end.   

Referenced by add_graph_edge(), build_pred_graph(), build_succ_graph(), dump_constraint_graph(), dump_pred_graph(), label_visit(), perform_var_substitution(), remove_preds_and_fake_succs(), scc_visit(), and unite_pointer_equivalences().

◆ LAST_REF_NODE

#define LAST_REF_NODE   (FIRST_REF_NODE + (FIRST_REF_NODE - 1))

Referenced by find_indirect_cycles(), and scc_visit().

Typedef Documentation

◆ const_equiv_class_label_t

◆ constraint_graph_t

◆ equiv_class_label_t

Structure used to for hash value numbering of pointer equivalence
classes.   

Function Documentation

◆ add_graph_edge()

bool add_graph_edge ( constraint_graph_t graph,
unsigned int to,
unsigned int from )
static
Add a graph edge to GRAPH, going from FROM to TO if
it doesn't exist in the graph already.
Return false if the edge already existed, true otherwise.   

References BITMAP_ALLOC, bitmap_bit_p, bitmap_set_bit, pointer_analysis::escaped_id, find(), FIRST_REF_NODE, pointer_analysis::get_varinfo(), pointer_analysis::pta_obstack, and r.

Referenced by build_succ_graph(), do_ds_constraint(), and solve_add_graph_edge().

◆ add_implicit_graph_edge()

void add_implicit_graph_edge ( constraint_graph_t graph,
unsigned int to,
unsigned int from )
static
Add an indirect graph edge to GRAPH, going from TO to FROM if
it doesn't exist in the graph already.   

References BITMAP_ALLOC, bitmap_set_bit, and predbitmap_obstack.

Referenced by build_pred_graph().

◆ add_pred_graph_edge()

void add_pred_graph_edge ( constraint_graph_t graph,
unsigned int to,
unsigned int from )
static
Add a predecessor graph edge to GRAPH, going from TO to FROM if
it doesn't exist in the graph already.
Return false if the edge already existed, true otherwise.   

References BITMAP_ALLOC, bitmap_set_bit, and predbitmap_obstack.

Referenced by build_pred_graph().

◆ build_pred_graph()

◆ build_succ_graph()

◆ clear_edges_for_node()

void clear_edges_for_node ( constraint_graph_t graph,
unsigned int node )
static
Remove edges involving NODE from GRAPH.   

References BITMAP_FREE.

Referenced by merge_graph_nodes(), and perform_var_substitution().

◆ compute_topo_order()

auto_vec< unsigned > compute_topo_order ( constraint_graph_t graph)
static
Compute a topological ordering for GRAPH, and return the result.   

References bitmap_bit_p, bitmap_clear(), pointer_analysis::escaped_id, find(), i, topo_visit(), and visited.

Referenced by solve_graph().

◆ condense_visit()

void condense_visit ( constraint_graph_t graph,
class scc_info * si,
unsigned int n )
static
Recursive routine to find strongly connected components in GRAPH,
and label it's nodes with DFS numbers.   

References a, b, bitmap_bit_p, bitmap_clear_bit(), bitmap_ior_into_and_free(), bitmap_set_bit, condense_visit(), EXECUTE_IF_IN_NONNULL_BITMAP, gcc_assert, gcc_checking_assert, i, and si.

Referenced by condense_visit(), and perform_var_substitution().

◆ constraint_equal()

bool constraint_equal ( const constraint & a,
const constraint & b )
static
Return true if two constraints A and B are equal.   

References a, b, and constraint_expr_equal().

Referenced by constraint_vec_find(), insert_into_complex(), and solve_graph().

◆ constraint_expr_equal()

bool constraint_expr_equal ( struct constraint_expr a,
struct constraint_expr b )
static
SOLVER FUNCTIONS

The solver is a simple worklist solver, that works on the following
algorithm:

sbitmap changed_nodes = all zeroes;
changed_count = 0;
For each node that is not already collapsed:
    changed_count++;
    set bit in changed nodes

while (changed_count > 0)
{
  compute topological ordering for constraint graph

  find and collapse cycles in the constraint graph (updating
  changed if necessary)

  for each node (n) in the graph in topological order:
    changed_count--;

    Process each complex constraint associated with the node,
    updating changed if necessary.

    For each outgoing edge from n, propagate the solution from n to
    the destination of the edge, updating changed as necessary.

}   
Return true if two constraint expressions A and B are equal.   

References a, and b.

Referenced by constraint_equal().

◆ constraint_expr_less()

bool constraint_expr_less ( struct constraint_expr a,
struct constraint_expr b )
static
Return true if constraint expression A is less than constraint expression
B.  This is just arbitrary, but consistent, in order to give them an
ordering.   

References a, and b.

Referenced by constraint_less().

◆ constraint_less()

bool constraint_less ( const constraint_t & a,
const constraint_t & b )
static
Return true if constraint A is less than constraint B.  This is just
arbitrary, but consistent, in order to give them an ordering.   

References a, b, and constraint_expr_less().

Referenced by constraint_set_union(), constraint_vec_find(), insert_into_complex(), and solve_graph().

◆ constraint_set_union()

bool constraint_set_union ( vec< constraint_t > * to,
vec< constraint_t > * from )
static
Union two constraint vectors, TO and FROM.  Put the result in TO.
Returns true of TO set is changed.   

References constraint_less(), constraint_vec_find(), FOR_EACH_VEC_ELT, i, and NULL.

Referenced by merge_node_constraints().

◆ constraint_vec_find()

constraint_t constraint_vec_find ( vec< constraint_t > vec,
constraint & lookfor )
static
Find a constraint LOOKFOR in the sorted constraint vector VEC.   

References constraint_equal(), constraint_less(), and NULL.

Referenced by constraint_set_union().

◆ debug_constraint_graph()

DEBUG_FUNCTION void debug_constraint_graph ( void )
Print out the constraint graph to stderr.   

References dump_constraint_graph().

◆ delete_graph()

void delete_graph ( void )

References free(), and i.

Referenced by pointer_analysis::solve_constraints().

◆ do_complex_constraint()

void do_complex_constraint ( constraint_graph_t graph,
constraint_t c,
bitmap delta,
bitmap * expanded_delta )
static
Handle a non-simple (simple meaning requires no iteration),
constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved).   

References pointer_analysis::ADDRESSOF, bitmap_set_bit, changed, pointer_analysis::DEREF, do_ds_constraint(), do_sd_constraint(), gcc_checking_assert, gcc_unreachable, pointer_analysis::get_varinfo(), SCALAR, set_union_with_increment(), and pointer_analysis::variable_info::solution.

Referenced by solve_graph().

◆ do_ds_constraint()

◆ do_sd_constraint()

◆ dump_constraint_graph()

void dump_constraint_graph ( FILE * file)
static

◆ dump_pred_graph()

void dump_pred_graph ( class scc_info * si,
FILE * file )
static

◆ eliminate_indirect_cycles()

bool eliminate_indirect_cycles ( unsigned int node)
static
Eliminate indirect cycles involving NODE.  Return true if NODE was
part of an SCC, false otherwise.   

References bitmap_empty_p(), EXECUTE_IF_SET_IN_BITMAP, find(), pointer_analysis::get_varinfo(), i, queue, unify_nodes(), and unite().

Referenced by solve_graph().

◆ equiv_class_lookup_or_add()

equiv_class_label * equiv_class_lookup_or_add ( hash_table< equiv_class_hasher > * table,
bitmap labels )
static
Lookup a equivalence class in TABLE by the bitmap of LABELS with
hash HAS it contains.  Sets *REF_LABELS to the bitmap LABELS
is equivalent to.   

References bitmap_hash(), equiv_class_obstack, equiv_class_label::hashcode, equiv_class_label::labels, and table.

Referenced by label_visit(), and perform_var_substitution().

◆ find()

unsigned int find ( unsigned int node)
static

◆ find_equivalent_node()

unsigned int find_equivalent_node ( constraint_graph_t graph,
unsigned int node,
unsigned int label )
static
Return an existing node that is equivalent to NODE, which has
equivalence class LABEL, if one exists.  Return NODE otherwise.   

References bitmap_bit_p, gcc_checking_assert, unify_nodes(), and unite().

Referenced by rewrite_constraints().

◆ find_indirect_cycles()

void find_indirect_cycles ( constraint_graph_t graph)
static
Find indirect cycles in GRAPH that occur, using strongly connected
components, and note them in the indirect cycles map.

This technique comes from Ben Hardekopf and Calvin Lin,
"It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
Lines of Code", submitted to PLDI 2007.   

References bitmap_bit_p, find(), i, LAST_REF_NODE, MIN, scc_visit(), and si.

Referenced by pointer_analysis::solve_constraints().

◆ free_var_substitution_info()

void free_var_substitution_info ( class scc_info * si)
static
Free information that was only necessary for variable
substitution.   

References bitmap_obstack_release(), equiv_class_obstack, free(), iteration_obstack, location_equiv_class_table, NULL, pointer_equiv_class_table, sbitmap_free(), and si.

Referenced by pointer_analysis::solve_constraints().

◆ init_graph()

void init_graph ( unsigned int size)
static
Initialize the constraint graph structure to contain SIZE nodes.   

References bitmap_obstack_initialize(), and predbitmap_obstack.

Referenced by pointer_analysis::solve_constraints().

◆ insert_into_complex()

void insert_into_complex ( constraint_graph_t graph,
unsigned int var,
constraint_t c )
static
Insert constraint C into the list of complex constraints for graph
node VAR.   

References constraint_equal(), and constraint_less().

Referenced by move_complex_constraints().

◆ label_visit()

void label_visit ( constraint_graph_t graph,
class scc_info * si,
unsigned int n )
static
Label pointer equivalences.

This performs a value numbering of the constraint graph to
discover which variables will always have the same points-to sets
under the current set of constraints.

The way it value numbers is to store the set of points-to bits
generated by the constraints and graph edges.  This is just used as a
hash and equality comparison.  The *actual set of points-to bits* is
completely irrelevant, in that we don't care about being able to
extract them later.

The equality values (currently bitmaps) just have to satisfy a few
constraints, the main ones being:
1. The combining operation must be order independent.
2. The end result of a given set of operations must be unique iff the
   combination of input values is unique
3. Hashable.   

References BITMAP_ALLOC, bitmap_bit_p, bitmap_copy(), bitmap_empty_p(), BITMAP_FREE, bitmap_ior(), bitmap_ior_into(), bitmap_set_bit, equiv_class_lookup_or_add(), equiv_class_label::equivalence_class, EXECUTE_IF_IN_NONNULL_BITMAP, FIRST_REF_NODE, i, label_visit(), equiv_class_label::labels, pointer_equiv_class, pointer_equiv_class_table, predbitmap_obstack, and si.

Referenced by label_visit(), and perform_var_substitution().

◆ merge_graph_nodes()

void merge_graph_nodes ( constraint_graph_t graph,
unsigned int to,
unsigned int from )
static
Merge GRAPH nodes FROM and TO into node TO.   

References BITMAP_ALLOC, bitmap_ior_into(), clear_edges_for_node(), and pointer_analysis::pta_obstack.

Referenced by unify_nodes().

◆ merge_node_constraints()

bool merge_node_constraints ( constraint_graph_t graph,
unsigned int to,
unsigned int from )
static
Condense two variable nodes into a single variable node, by moving
all associated info from FROM to TO.  Returns true if TO node's
constraint set changes after the merge.   

References constraint_set_union(), pointer_analysis::DEREF, find(), FOR_EACH_VEC_ELT, gcc_checking_assert, and i.

Referenced by unify_nodes().

◆ move_complex_constraints()

void move_complex_constraints ( constraint_graph_t graph)
static

◆ perform_var_substitution()

◆ remove_preds_and_fake_succs()

void remove_preds_and_fake_succs ( constraint_graph_t graph)
static
Remove the REF and ADDRESS edges from GRAPH, as well as all the
predecessor edges.   

References bitmap_clear_range(), BITMAP_FREE, bitmap_obstack_release(), FIRST_REF_NODE, free(), i, NULL, predbitmap_obstack, and pointer_analysis::varmap.

Referenced by pointer_analysis::solve_constraints().

◆ rewrite_constraints()

void rewrite_constraints ( constraint_graph_t graph,
class scc_info * si )
static
Optimize and rewrite complex constraints while performing
collapsing of equivalent nodes.  SI is the SCC_INFO that is the
result of perform_variable_substitution.   

References pointer_analysis::constraints, pointer_analysis::dump_constraint(), dump_file, dump_flags, find(), find_equivalent_node(), FOR_EACH_VEC_ELT, gcc_assert, pointer_analysis::get_varinfo(), i, NULL, si, and TDF_DETAILS.

Referenced by pointer_analysis::solve_constraints().

◆ scc_visit()

void scc_visit ( constraint_graph_t graph,
class scc_info * si,
unsigned int n )
static
Recursive routine to find strongly connected components in GRAPH.
SI is the SCC info to store the information in, and N is the id of current
graph node we are processing.

This is Tarjan's strongly connected component finding algorithm, as
modified by Nuutila to keep only non-root nodes on the stack.
The algorithm can be found in "On finding the strongly connected
connected components in a directed graph" by Esko Nuutila and Eljas
Soisalon-Soininen, in Information Processing Letters volume 49,
number 1, pages 9-14.   

References BITMAP_ALLOC, bitmap_bit_p, bitmap_first_set_bit(), bitmap_set_bit, EXECUTE_IF_IN_NONNULL_BITMAP, EXECUTE_IF_SET_IN_BITMAP, find(), FIRST_REF_NODE, gcc_assert, gcc_checking_assert, i, LAST_REF_NODE, NULL, scc_visit(), si, unify_nodes(), and unite().

Referenced by find_indirect_cycles(), and scc_visit().

◆ set_union_with_increment()

◆ solution_set_expand()

◆ solve_add_graph_edge()

bool solve_add_graph_edge ( constraint_graph_t graph,
unsigned int to,
unsigned int from )
static
Add a copy edge FROM -> TO, optimizing special cases.  Returns TRUE
if the solution of TO changed.   

References add_graph_edge(), bitmap_ior_into(), bitmap_set_bit, pointer_analysis::escaped_id, find(), and pointer_analysis::get_varinfo().

Referenced by do_ds_constraint(), and do_sd_constraint().

◆ solve_graph()

◆ topo_visit()

void topo_visit ( constraint_graph_t graph,
vec< unsigned > & topo_order,
sbitmap visited,
unsigned int n )
static
Visit the graph in topological order starting at node N, and store the
order in TOPO_ORDER using VISITED to indicate visited nodes.   

References bitmap_bit_p, bitmap_set_bit, EXECUTE_IF_SET_IN_BITMAP, find(), gcc_checking_assert, SCALAR, topo_visit(), and visited.

Referenced by compute_topo_order(), and topo_visit().

◆ unify_nodes()

◆ union_find_compress_all()

void union_find_compress_all ( void )
static
Perform path compression for all nodes in the node representatives
union-find structure.   

References find(), and i.

Referenced by pointer_analysis::solve_constraints().

◆ unite()

bool unite ( unsigned int to,
unsigned int from )
static
Union the TO and FROM nodes to the TO nodes.
Note that at some point in the future, we may want to do
union-by-rank, in which case we are going to have to return the
node we unified to.   

References gcc_checking_assert.

Referenced by eliminate_indirect_cycles(), find_equivalent_node(), scc_visit(), and unite_pointer_equivalences().

◆ unite_pointer_equivalences()

void unite_pointer_equivalences ( constraint_graph_t graph)
static
Unite pointer equivalent but not location equivalent nodes in
GRAPH.  This may only be performed once variable substitution is
finished.   

References find(), FIRST_REF_NODE, i, unify_nodes(), and unite().

Referenced by pointer_analysis::solve_constraints().

Variable Documentation

◆ changed

bitmap changed
static
Changed variables on the last iteration.   

Referenced by cgraph_node::add_detected_attribute(), add_detected_attribute_1(), add_scope_conflicts(), autofdo::afdo_propagate(), autofdo::afdo_propagate_edge(), afdo_vpt_for_early_inline(), analyze_functions(), bitmap_and(), bitmap_and_compl(), bitmap_and_compl_into(), bitmap_and_into(), bitmap_and_or(), bitmap_elt_copy(), bitmap_elt_ior(), bitmap_ior(), bitmap_ior(), bitmap_ior_and_compl(), bitmap_ior_and_compl(), bitmap_ior_and_compl_into(), bitmap_ior_and_into(), bitmap_ior_into(), bitmap_ior_into_and_free(), bitmap_or_and(), bitmap_xor(), bypass_conditional_jumps(), canonicalize_induction_variables(), change_zero_ext(), cleanup_all_empty_eh(), cleanup_cfg(), cleanup_subreg_operands(), cleanup_tree_cfg(), cleanup_tree_cfg_noloop(), frange::combine_zeros(), compute_antic(), compute_antic_aux(), compute_bb_dataflow(), compute_code_hoist_vbeinout(), compute_live_vars(), copyprop_hardreg_forward_1(), cprop_insn(), cse_extended_basic_block(), dataflow_set_preserve_mem_locs(), dataflow_set_remove_mem_locs(), default_goacc_validate_dims(), defs_to_varying(), delete_slot_part(), delete_unreachable_blocks(), delete_unreachable_blocks_update_callgraph(), df_compute_regs_ever_live(), df_lr_confluence_n(), df_rd_confluence_n(), df_rd_transfer_function(), df_update_entry_block_defs(), df_update_exit_block_uses(), df_word_lr_mark_ref(), df_word_lr_simulate_defs(), df_worklist_dataflow_doublequeue(), df_worklist_propagate_backward(), df_worklist_propagate_forward(), loop_distribution::distribute_loop(), do_complex_constraint(), do_ds_constraint(), do_sd_constraint(), drop_overlapping_mem_locs(), duplicate_computed_gotos(), loop_distribution::execute(), execute_cleanup_eh_1(), execute_early_expand_coro_ifns(), execute_hardreg_pre(), execute_rtl_cprop(), execute_rtl_hoist(), execute_rtl_pre(), execute_split_paths(), expand_changed_pseudos(), expand_omp_target(), expand_omp_taskreg(), extract_writebacks(), fini_copy_prop(), fixup_noreturn_call(), fold_rtx(), ccp_folder::fold_stmt(), fold_stmt_1(), fold_stmt_inplace(), gimple_fold_call(), gimple_purge_all_dead_abnormal_call_edges(), gimple_purge_all_dead_eh_edges(), gimple_purge_dead_abnormal_call_edges(), gimple_purge_dead_eh_edges(), gimple_value_profile_transformations(), gimplify_modify_expr_rhs(), gimplify_size_expressions(), graphds_domtree(), group_case_labels(), hoist_code(), hoist_memory_references(), init_alias_analysis(), insert(), modref_tree< tree >::insert(), modref_tree< tree >::insert_base(), modref_base_node< T >::insert_ref(), instantiate_virtual_regs_in_rtx(), frange::intersect(), ipa_propagate_frequency(), ipa_propagate_indirect_call_infos(), local_cprop_pass(), match_asm_constraints_1(), match_asm_constraints_2(), maybe_duplicate_computed_goto(), maybe_fold_tmr(), mention_regs(), autofdo::function_instance::merge(), modref_tree< tree >::merge(), move2add_use_add2_insn(), move2add_use_add3_insn(), oacc_entry_exit_ok(), oacc_entry_exit_single_gang(), oacc_validate_dims(), object_sizes_set(), one_code_hoisting_pass(), one_cprop_pass(), one_pre_gcse_pass(), vars_ssa_cache::operator()(), optimize_aggr_zeroprop(), optimize_agr_copyprop(), optimize_agr_copyprop_arg(), output_address(), output_min_issue_delay_table(), symbol_table::output_variables(), parallelize_loops(), phi_translate_1(), pre_delete(), pre_gcse(), gimple_ranger::prefill_stmt_dependencies(), propagate_malloc(), propagate_with_phi(), gimple_ranger::range_of_stmt(), recog_for_combine(), reload_cse_move2add(), remove_exits_and_undefined_stmts(), remove_redundant_iv_tests(), symbol_table::remove_unreachable_nodes(), replace_oldest_value_addr(), rewrite_expr_tree(), cgraph_node::set_const_flag(), set_const_flag_1(), ranger_cache::set_global_range(), cgraph_node::set_malloc_flag(), set_malloc_flag_1(), cgraph_node::set_noreturn_flag(), set_noreturn_flag_1(), cgraph_node::set_nothrow_flag(), set_nothrow_flag_1(), set_parm_default_def_partition(), set_parm_rtl(), irange::set_range_from_bitmask(), set_union_with_increment(), predicate::simplify(), simplify_comparison(), simplify_loop_version(), simplify_context::simplify_plus_minus(), simplify_using_outer_evolutions(), irange::snap_subranges(), solve_graph(), split_all_insns(), split_loop(), split_paths(), strip_predict_hints(), tail_duplicate(), back_threader::thread_blocks(), tm_memopt_compute_available(), transform_add_to_multiply(), tree_optimize_tail_calls_1(), tree_predictive_commoning(), tree_simplify_using_condition_1(), tree_ssa_ifcombine_bb(), tree_ssa_iv_optimize_loop(), tree_ssa_split_loops(), tree_unroll_loops_completely(), tree_unroll_loops_completely_1(), tree_unswitch_outer_loop(), tree_unswitch_single_loop(), try_crossjump_bb(), try_forward_edges(), try_head_merge_bb(), try_optimize_cfg(), undistribute_ops_list(), unify_nodes(), frange::union_(), frange::union_nans(), unroll_loops(), unsplit_all_eh(), unsplit_eh_edges(), visit_nary_op(), visit_reference_op_call(), visit_reference_op_load(), visit_reference_op_store(), visit_stmt(), vn_reference_maybe_forwprop_address(), vt_find_locations(), and walk_alter_subreg().

◆ equiv_class_obstack

◆ graph

constraint_graph_t graph
static

◆ iteration_obstack

bitmap_obstack iteration_obstack
static
Used for per-solver-iteration bitmaps.   

Referenced by free_var_substitution_info(), perform_var_substitution(), solution_set_expand(), and solve_graph().

◆ location_equiv_class

int location_equiv_class
static
Current maximum location equivalence class id.   

Referenced by perform_var_substitution().

◆ location_equiv_class_table

hash_table<equiv_class_hasher>* location_equiv_class_table
static
A hashtable for mapping a bitmap of labels->location equivalence
classes.   

Referenced by free_var_substitution_info(), and perform_var_substitution().

◆ pointer_equiv_class

int pointer_equiv_class
static
Perform offline variable substitution.

This is a worst case quadratic time way of identifying variables
that must have equivalent points-to sets, including those caused by
static cycles, and single entry subgraphs, in the constraint graph.

The technique is described in "Exploiting Pointer and Location
Equivalence to Optimize Pointer Analysis.  In the 14th International
Static Analysis Symposium (SAS), August 2007."  It is known as the
"HU" algorithm, and is equivalent to value numbering the collapsed
constraint graph including evaluating unions.

The general method of finding equivalence classes is as follows:
Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
Initialize all non-REF nodes to be direct nodes.
For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
variable}
For each constraint containing the dereference, we also do the same
thing.

We then compute SCC's in the graph and unify nodes in the same SCC,
including pts sets.

For each non-collapsed node x:
 Visit all unvisited explicit incoming edges.
 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
 where y->x.
 Lookup the equivalence class for pts(x).
  If we found one, equivalence_class(x) = found class.
  Otherwise, equivalence_class(x) = new class, and new_class is
 added to the lookup table.

All direct nodes with the same equivalence class can be replaced
with a single representative node.
All unlabeled nodes (label == 0) are not pointers and all edges
involving them can be eliminated.
We perform these optimizations during rewrite_constraints

In addition to pointer equivalence class finding, we also perform
location equivalence class finding.  This is the set of variables
that always appear together in points-to sets.  We use this to
compress the size of the points-to sets.   
Current maximum pointer equivalence class id.   

Referenced by label_visit(), and perform_var_substitution().

◆ pointer_equiv_class_table

hash_table<equiv_class_hasher>* pointer_equiv_class_table
static
A hashtable for mapping a bitmap of labels->pointer equivalence
classes.   

Referenced by free_var_substitution_info(), label_visit(), and perform_var_substitution().

◆ predbitmap_obstack

bitmap_obstack predbitmap_obstack
static