#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "tree-ssa-structalias.h"#include "pta-andersen.h"
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_graph * | constraint_graph_t |
| typedef struct equiv_class_label * | equiv_class_label_t |
| typedef const struct equiv_class_label * | const_equiv_class_label_t |
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
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
| typedef const struct equiv_class_label* const_equiv_class_label_t |
◆ constraint_graph_t
| typedef struct constraint_graph* constraint_graph_t |
◆ equiv_class_label_t
| typedef struct equiv_class_label * equiv_class_label_t |
Structure used to for hash value numbering of pointer equivalence classes.
Function Documentation
◆ add_graph_edge()
|
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()
|
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()
|
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()
|
static |
Build the constraint graph, adding only predecessor edges right now.
References add_implicit_graph_edge(), add_pred_graph_edge(), pointer_analysis::ADDRESSOF, pointer_analysis::anything_id, BITMAP_ALLOC, bitmap_clear(), bitmap_clear_bit(), bitmap_set_bit, pointer_analysis::constraints, pointer_analysis::DEREF, FIRST_REF_NODE, FOR_EACH_VEC_ELT, pointer_analysis::get_varinfo(), pointer_analysis::variable_info::head, i, pointer_analysis::variable_info::id, pointer_analysis::variable_info::is_full_var, NULL, predbitmap_obstack, sbitmap_alloc(), SCALAR, pointer_analysis::storedanything_id, pointer_analysis::varmap, and pointer_analysis::vi_next().
Referenced by pointer_analysis::solve_constraints().
◆ build_succ_graph()
|
static |
Build the constraint graph, adding successor edges.
References add_graph_edge(), pointer_analysis::ADDRESSOF, pointer_analysis::anything_id, bitmap_set_bit, pointer_analysis::constraints, pointer_analysis::DEREF, pointer_analysis::escaped_id, find(), FIRST_REF_NODE, FOR_EACH_VEC_ELT, gcc_checking_assert, pointer_analysis::get_varinfo(), i, pointer_analysis::integer_id, SCALAR, and pointer_analysis::storedanything_id.
Referenced by pointer_analysis::solve_constraints().
◆ clear_edges_for_node()
|
static |
Remove edges involving NODE from GRAPH.
References BITMAP_FREE.
Referenced by merge_graph_nodes(), and perform_var_substitution().
◆ compute_topo_order()
|
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()
|
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()
|
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()
|
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.
Referenced by constraint_equal().
◆ constraint_expr_less()
|
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.
Referenced by constraint_less().
◆ constraint_less()
|
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()
|
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()
|
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 | ) |
Referenced by pointer_analysis::solve_constraints().
◆ do_complex_constraint()
|
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()
|
static |
Process a constraint C that represents *(x + off) = y using DELTA as the starting solution for x.
References add_graph_edge(), pointer_analysis::anything_id, bitmap_bit_p, bitmap_ior_into(), bitmap_set_bit, changed, pointer_analysis::escaped_id, EXECUTE_IF_SET_IN_BITMAP, find(), pointer_analysis::first_or_preceding_vi_for_offset(), gcc_checking_assert, pointer_analysis::get_varinfo(), pointer_analysis::variable_info::head, pointer_analysis::variable_info::id, pointer_analysis::variable_info::is_full_var, pointer_analysis::variable_info::is_global_var, pointer_analysis::variable_info::is_special_var, pointer_analysis::variable_info::may_have_pointers, pointer_analysis::variable_info::next, pointer_analysis::variable_info::offset, pointer_analysis::variable_info::size, pointer_analysis::variable_info::solution, solution_set_expand(), solve_add_graph_edge(), pointer_analysis::storedanything_id, UNKNOWN_OFFSET, and pointer_analysis::vi_next().
Referenced by do_complex_constraint().
◆ do_sd_constraint()
|
static |
Process a constraint C that represents x = *(y + off), using DELTA as the starting solution for y.
References pointer_analysis::anything_id, bitmap_bit_p, bitmap_set_bit, changed, EXECUTE_IF_SET_IN_BITMAP, find(), pointer_analysis::first_or_preceding_vi_for_offset(), gcc_checking_assert, pointer_analysis::get_varinfo(), pointer_analysis::variable_info::head, pointer_analysis::variable_info::id, pointer_analysis::variable_info::is_full_var, pointer_analysis::variable_info::next, pointer_analysis::variable_info::offset, pointer_analysis::variable_info::size, pointer_analysis::variable_info::solution, solution_set_expand(), solve_add_graph_edge(), UNKNOWN_OFFSET, and pointer_analysis::vi_next().
Referenced by do_complex_constraint().
◆ dump_constraint_graph()
|
static |
Print the constraint graph in dot format.
References pointer_analysis::dump_constraint(), EXECUTE_IF_IN_NONNULL_BITMAP, find(), FIRST_REF_NODE, pointer_analysis::get_varinfo(), and i.
Referenced by debug_constraint_graph(), and pointer_analysis::solve_constraints().
◆ dump_pred_graph()
|
static |
Print the pred graph in dot format.
References bitmap_empty_p(), EXECUTE_IF_IN_NONNULL_BITMAP, EXECUTE_IF_SET_IN_BITMAP, FIRST_REF_NODE, pointer_analysis::get_varinfo(), i, and si.
Referenced by perform_var_substitution().
◆ eliminate_indirect_cycles()
|
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()
|
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()
|
static |
Return the representative node for NODE, if NODE has been unioned with another NODE. This function performs path compression along the way to finding the representative.
References find(), and gcc_checking_assert.
Referenced by add_graph_edge(), build_succ_graph(), circuit(), compute_topo_order(), count_occurrences(), do_ds_constraint(), do_sd_constraint(), dump_constraint_graph(), eliminate_indirect_cycles(), find(), find_indirect_cycles(), merge_node_constraints(), rewrite_constraints(), scc_visit(), solve_add_graph_edge(), solve_graph(), topo_visit(), unblock(), unify_nodes(), union_find_compress_all(), and unite_pointer_equivalences().
◆ find_equivalent_node()
|
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()
|
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()
|
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()
|
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()
|
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()
|
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()
|
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()
|
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()
|
static |
Move complex constraints to the GRAPH nodes they belong to.
References pointer_analysis::ADDRESSOF, pointer_analysis::anything_id, pointer_analysis::constraints, pointer_analysis::DEREF, FOR_EACH_VEC_ELT, pointer_analysis::get_varinfo(), i, and insert_into_complex().
Referenced by pointer_analysis::solve_constraints().
◆ perform_var_substitution()
|
static |
Perform offline variable substitution, discovering equivalence classes, and eliminating non-pointer variables.
References BITMAP_ALLOC, bitmap_bit_p, bitmap_clear(), BITMAP_FREE, bitmap_obstack_initialize(), bitmap_set_bit, clear_edges_for_node(), condense_visit(), dump_file, dump_flags, dump_pred_graph(), equiv_class_lookup_or_add(), equiv_class_obstack, equiv_class_label::equivalence_class, EXECUTE_IF_SET_IN_BITMAP, FIRST_REF_NODE, gcc_obstack_init, pointer_analysis::get_varinfo(), i, iteration_obstack, label_visit(), location_equiv_class, location_equiv_class_table, pointer_equiv_class, pointer_equiv_class_table, scc_info::scc_info(), si, TDF_DETAILS, and TDF_GRAPH.
Referenced by pointer_analysis::solve_constraints().
◆ remove_preds_and_fake_succs()
|
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()
|
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()
|
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()
|
static |
Union solution sets TO and DELTA, and add INC to each member of DELTA in the process.
References pointer_analysis::anything_id, bitmap_bit_p, bitmap_ior_into(), bitmap_set_bit, changed, EXECUTE_IF_SET_IN_BITMAP, pointer_analysis::first_or_preceding_vi_for_offset(), pointer_analysis::get_varinfo(), pointer_analysis::variable_info::head, i, pointer_analysis::variable_info::id, pointer_analysis::variable_info::is_artificial_var, pointer_analysis::variable_info::is_full_var, pointer_analysis::variable_info::is_unknown_size_var, pointer_analysis::variable_info::next, pointer_analysis::variable_info::offset, pointer_analysis::variable_info::size, solution_set_expand(), UNKNOWN_OFFSET, and pointer_analysis::vi_next().
Referenced by do_complex_constraint().
◆ solution_set_expand()
Expands the solution in SET to all sub-fields of variables included.
References BITMAP_ALLOC, bitmap_ior_into(), bitmap_set_range(), EXECUTE_IF_SET_IN_BITMAP, pointer_analysis::get_varinfo(), pointer_analysis::variable_info::head, pointer_analysis::variable_info::is_artificial_var, pointer_analysis::variable_info::is_full_var, iteration_obstack, NULL, and pointer_analysis::vi_next().
Referenced by do_ds_constraint(), do_sd_constraint(), and set_union_with_increment().
◆ solve_add_graph_edge()
|
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()
|
static |
Solve the constraint graph GRAPH using our worklist solver. This is based on the PW* family of solvers from the "Efficient Field Sensitive Pointer Analysis for C" paper. It works by iterating over all the graph nodes, processing the complex constraints and propagating the copy constraints, until everything stops changed. This corresponds to steps 6-8 in the solving list given above.
References hash_set< KeyId, Lazy, Traits >::add(), pointer_analysis::anything_id, BITMAP_ALLOC, bitmap_and_compl(), bitmap_bit_p, bitmap_clear_bit(), bitmap_copy(), bitmap_empty_p(), BITMAP_FREE, bitmap_ior_into(), bitmap_obstack_initialize(), bitmap_obstack_release(), bitmap_set_bit, changed, compute_topo_order(), constraint_equal(), constraint_less(), pointer_analysis::DEREF, do_complex_constraint(), hash_set< KeyId, Lazy, Traits >::elements(), eliminate_indirect_cycles(), pointer_analysis::escaped_id, EXECUTE_IF_IN_NONNULL_BITMAP, find(), gcc_assert, gcc_unreachable, pointer_analysis::get_varinfo(), i, iteration_obstack, pointer_analysis::constraint::lhs, NULL, pointer_analysis::oldpta_obstack, pointer_analysis::variable_info::oldsolution, pointer_analysis::pta_obstack, pointer_analysis::constraint::rhs, pointer_analysis::variable_info::solution, and pointer_analysis::constraint_expr::var.
Referenced by pointer_analysis::solve_constraints().
◆ topo_visit()
|
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()
|
static |
Unify node FROM into node TO, updating the changed count if necessary when UPDATE_CHANGED is true.
References bitmap_clear_bit(), BITMAP_FREE, bitmap_ior_into(), bitmap_set_bit, changed, dump_file, dump_flags, find(), gcc_checking_assert, pointer_analysis::get_varinfo(), merge_graph_nodes(), merge_node_constraints(), pointer_analysis::variable_info::oldsolution, pointer_analysis::variable_info::solution, and TDF_DETAILS.
Referenced by eliminate_indirect_cycles(), find_equivalent_node(), scc_visit(), and unite_pointer_equivalences().
◆ union_find_compress_all()
|
static |
Perform path compression for all nodes in the node representatives union-find structure.
Referenced by pointer_analysis::solve_constraints().
◆ unite()
|
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()
|
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
|
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_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
| struct obstack equiv_class_obstack |
Referenced by equiv_class_lookup_or_add(), free_var_substitution_info(), and perform_var_substitution().
◆ graph
|
static |
◆ 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
|
static |
Current maximum location equivalence class id.
Referenced by perform_var_substitution().
◆ 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
|
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
|
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
|
static |
Used for predecessor bitmaps.
Referenced by add_implicit_graph_edge(), add_pred_graph_edge(), build_pred_graph(), init_graph(), label_visit(), and remove_preds_and_fake_succs().
