#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "rtl.h"#include "tree.h"#include "gimple.h"#include "alloc-pool.h"#include "tree-pass.h"#include "ssa.h"#include "cgraph.h"#include "tree-pretty-print.h"#include "diagnostic-core.h"#include "fold-const.h"#include "stor-layout.h"#include "stmt.h"#include "gimple-iterator.h"#include "tree-into-ssa.h"#include "tree-dfa.h"#include "gimple-walk.h"#include "varasm.h"#include "stringpool.h"#include "attribs.h"#include "tree-ssa.h"#include "tree-cfg.h"#include "gimple-range.h"#include "ipa-modref-tree.h"#include "ipa-modref.h"#include "attr-fnspec.h"
Data Structures | |
| struct | constraint_stats |
| struct | variable_info |
| struct | constraint_expr |
| struct | constraint |
| struct | constraint_graph |
| class | scc_info |
| struct | equiv_class_label |
| struct | equiv_class_hasher |
| struct | fieldoff |
| struct | shared_bitmap_info |
| struct | shared_bitmap_hasher |
| struct | vls_data |
| struct | msdi_data |
Macros | |
| #define | EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) |
| #define | UNKNOWN_OFFSET HOST_WIDE_INT_MIN |
| #define | FIRST_REF_NODE (varmap).length () |
| #define | LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) |
Typedefs | |
| typedef struct constraint_graph * | constraint_graph_t |
| typedef struct constraint * | constraint_t |
| typedef struct variable_info * | varinfo_t |
| typedef struct constraint_expr | ce_s |
| typedef struct equiv_class_label * | equiv_class_label_t |
| typedef const struct equiv_class_label * | const_equiv_class_label_t |
| typedef struct fieldoff | fieldoff_s |
| typedef struct shared_bitmap_info * | shared_bitmap_info_t |
| typedef const struct shared_bitmap_info * | const_shared_bitmap_info_t |
Enumerations | |
| 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 | constraint_expr_type { SCALAR , DEREF , ADDRESSOF } |
| enum | { fi_clobbers = 1 , fi_uses = 2 , fi_static_chain = 3 , fi_result = 4 , fi_parm_base = 5 } |
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 () |
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().
◆ UNKNOWN_OFFSET
| #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN |
Use 0x8000... as special unknown offset.
Referenced by do_ds_constraint(), do_sd_constraint(), do_structure_copy(), dump_constraint(), get_constraint_for_1(), get_constraint_for_component_ref(), get_constraint_for_ptr_offset(), handle_call_arg(), init_base_vars(), make_any_offset_constraints(), make_indirect_escape_constraint(), make_transitive_closure_constraints(), and set_union_with_increment().
Typedef Documentation
◆ ce_s
| typedef struct constraint_expr ce_s |
◆ const_equiv_class_label_t
| typedef const struct equiv_class_label* const_equiv_class_label_t |
◆ const_shared_bitmap_info_t
| typedef const struct shared_bitmap_info* const_shared_bitmap_info_t |
◆ constraint_graph_t
| typedef struct constraint_graph* constraint_graph_t |
◆ constraint_t
| typedef struct constraint* constraint_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.
◆ fieldoff_s
| typedef struct fieldoff fieldoff_s |
◆ shared_bitmap_info_t
| typedef struct shared_bitmap_info * shared_bitmap_info_t |
Structure used to put solution bitmaps in a hashtable so they can be shared among variables with the same points-to set.
◆ varinfo_t
| typedef struct variable_info* varinfo_t |
Enumeration Type Documentation
◆ anonymous enum
| anonymous enum |
◆ 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 constraint_expr_type |
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, escaped_id, find(), FIRST_REF_NODE, get_varinfo(), 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().
◆ alias_get_name()
|
static |
Return a printable name for DECL
References DECL_ASSEMBLER_NAME_RAW, DECL_ASSEMBLER_NAME_SET_P, DECL_P, DECL_UID, dump_file, free(), get_name(), ggc_strdup, HAS_DECL_ASSEMBLER_NAME_P, IDENTIFIER_POINTER, NULL, SSA_NAME_VERSION, and TREE_CODE.
Referenced by get_vi_for_tree(), intra_create_variable_infos(), and ipa_pta_execute().
◆ associate_varinfo_to_alias()
|
static |
Associate node with varinfo DATA. Worker for cgraph_for_symbol_thunks_and_aliases.
References symtab_node::alias, symtab_node::analyzed, symtab_node::decl, symtab_node::ifunc_resolver, cgraph_node::inlined_to, insert_vi_for_tree(), and cgraph_node::thunk.
Referenced by ipa_pta_execute().
◆ bitpos_of_field()
|
static |
Return the position, in bits, of FIELD_DECL from the beginning of its structure.
References DECL_FIELD_BIT_OFFSET, DECL_FIELD_OFFSET, tree_fits_uhwi_p(), and tree_to_uhwi().
Referenced by push_fields_onto_fieldstack().
◆ build_fake_var_decl()
Build a fake VAR_DECL acting as referrer to a DECL_UID.
References allocate_decl_uid(), DECL_UID, fake_var_decl_obstack, layout_decl(), SET_DECL_PT_UID, TREE_SET_CODE, TREE_TYPE, and type().
Referenced by create_function_info_for(), create_variable_info_for_1(), and make_heapvar().
◆ build_pred_graph()
|
static |
Build the constraint graph, adding only predecessor edges right now.
References add_implicit_graph_edge(), add_pred_graph_edge(), ADDRESSOF, anything_id, BITMAP_ALLOC, bitmap_clear(), bitmap_clear_bit(), bitmap_set_bit, constraints, DEREF, FIRST_REF_NODE, FOR_EACH_VEC_ELT, get_varinfo(), variable_info::head, i, variable_info::id, variable_info::is_full_var, constraint::lhs, NULL, predbitmap_obstack, constraint::rhs, sbitmap_alloc(), SCALAR, storedanything_id, varmap, and vi_next().
Referenced by solve_constraints().
◆ build_succ_graph()
|
static |
Build the constraint graph, adding successor edges.
References add_graph_edge(), ADDRESSOF, anything_id, bitmap_set_bit, constraints, DEREF, escaped_id, find(), FIRST_REF_NODE, FOR_EACH_VEC_ELT, gcc_checking_assert, get_varinfo(), i, integer_id, constraint::lhs, constraint::rhs, SCALAR, and storedanything_id.
Referenced by solve_constraints().
◆ check_for_overlaps()
|
static |
Return true if FIELDSTACK contains fields that overlap. FIELDSTACK is assumed to be sorted by offset.
References FOR_EACH_VEC_ELT, i, NULL, and fieldoff::offset.
Referenced by create_variable_info_for_1().
◆ clear_dependence_clique()
Clear dependence info for the clique DATA.
References MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, and TREE_CODE.
Referenced by compute_dependence_clique().
◆ clear_edges_for_node()
|
static |
Remove edges involving NODE from GRAPH.
References BITMAP_FREE.
Referenced by merge_graph_nodes(), and perform_var_substitution().
◆ compute_dependence_clique()
|
static |
Compute the set of independend memory references based on restrict tags and their conservative propagation to the points-to sets.
References BITMAP_ALLOC, bitmap_bit_p, BITMAP_FREE, bitmap_set_bit, cfun, clear_dependence_clique(), dump_file, dump_flags, escaped_id, EXECUTE_IF_SET_IN_BITMAP, find(), FOR_EACH_BB_FN, FOR_EACH_IMM_USE_STMT, get_varinfo(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), variable_info::head, i, variable_info::id, variable_info::is_restrict_var, lookup_vi_for_tree(), maybe_set_dependence_info(), nothing_id, NULL, num_ssa_names, POINTER_TYPE_P, print_generic_expr(), variable_info::solution, ssa_name, SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, TDF_DETAILS, TREE_CODE, TREE_TYPE, ui, visit_loadstore(), and walk_stmt_load_store_ops().
Referenced by compute_may_aliases().
◆ compute_may_aliases()
| unsigned int compute_may_aliases | ( | void | ) |
Compute points-to information for every SSA_NAME pointer in the current function and compute the transitive closure of escaped variables to re-initialize the call-clobber states of local variables.
References cfun, compute_dependence_clique(), compute_points_to_sets(), delete_points_to_sets(), dump_alias_info(), dump_file, dump_flags, gcc_assert, need_ssa_update_p(), TDF_ALIAS, and TDF_DETAILS.
Referenced by execute_function_todo().
◆ compute_points_to_sets()
|
static |
Create points-to sets for the current function. See the comments at the start of the file for an algorithmic overview.
References cfun, determine_global_memory_access(), dump_constraints(), dump_file, dump_flags, dump_sa_points_to_info(), dump_sa_stats(), dyn_cast(), ECF_CONST, ECF_NOVOPS, ECF_PURE, pt_solution::escaped, escaped_id, escaped_return_id, find_func_aliases(), find_what_p_points_to(), find_what_var_points_to(), FOR_EACH_BB_FN, FOR_EACH_SSA_NAME, get_varinfo(), gimple_call_clobber_set(), gimple_call_flags(), gimple_call_use_set(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, init_alias_vars(), intra_create_variable_infos(), lookup_call_clobber_vi(), lookup_call_use_vi(), pt_solution::nonlocal, NULL, POINTER_TYPE_P, solve_constraints(), TDF_DETAILS, TDF_STATS, timevar_pop(), timevar_push(), TREE_TYPE, and virtual_operand_p().
Referenced by compute_may_aliases().
◆ compute_topo_order()
|
static |
Compute a topological ordering for GRAPH, and return the result.
References bitmap_bit_p, bitmap_clear(), 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().
◆ count_num_arguments()
Count the number of arguments DECL has, and set IS_VARARGS to true if it is a varargs function.
References DECL_ARGUMENTS, DECL_CHAIN, TREE_CHAIN, TREE_TYPE, TREE_VALUE, TYPE_ARG_TYPES, and void_type_node.
Referenced by create_function_info_for().
◆ create_function_info_for()
|
static |
Creation function node for DECL, using NAME, and return the index of the variable we've created for the function. If NONLOCAL_p, create initial constraints.
References build_fake_var_decl(), count_num_arguments(), function::decl, variable_info::decl, DECL_ARGUMENTS, DECL_BY_REFERENCE, DECL_CHAIN, DECL_NAME, DECL_RESULT, DECL_STRUCT_FUNCTION, escaped_id, fi_clobbers, fi_parm_base, fi_result, fi_static_chain, fi_uses, first_vi_for_offset(), free(), variable_info::fullsize, gcc_assert, get_varinfo(), ggc_strdup, i, variable_info::id, insert_vi_for_tree(), variable_info::is_fn_info, variable_info::is_full_var, variable_info::is_global_var, variable_info::is_heap_var, variable_info::is_reg_var, lookup_vi_for_tree(), MAIN_NAME_P, make_constraint_from(), make_copy_constraint(), variable_info::may_have_pointers, new_var_info(), variable_info::next, nonlocal_id, NULL, NULL_TREE, variable_info::offset, ptr_type_node, variable_info::size, function::static_chain_decl, TREE_TYPE, and VOID_TYPE_P.
Referenced by ipa_pta_execute().
◆ create_variable_info_for()
References varpool_node::all_refs_explicit_p(), create_variable_info_for_1(), symtab_node::decl, DECL_HARD_REGISTER, escaped_id, fi_result, FOR_EACH_VEC_ELT, cgraph_node::get(), varpool_node::get(), cgraph_node::get_alias_target(), get_constraint_for_address_of(), get_function_part_constraint(), get_vi_for_tree(), i, variable_info::id, symtab_node::ifunc_resolver, in_ipa_mode, insert_vi_for_tree(), variable_info::is_global_var, variable_info::is_reg_var, variable_info::is_restrict_var, symtab_node::iterate_reference(), make_constraint_from_global_restrict(), make_copy_constraint(), variable_info::may_have_pointers, new_constraint(), new_var_info(), nonlocal_id, NULL, NULL_TREE, variable_info::only_restrict_pointers, POINTER_TYPE_P, process_constraint(), ipa_ref::referred, SCALAR, TREE_CODE, TREE_TYPE, TYPE_RESTRICT, VAR_P, and vi_next().
Referenced by get_vi_for_tree().
◆ create_variable_info_for_1()
|
static |
Create a varinfo structure for NAME and DECL, and add it to VARMAP. This will also create any varinfo structures necessary for fields of DECL. DECL is a function parameter if HANDLE_PARAM is set. HANDLED_STRUCT_TYPE is used to register struct types reached by following restrict pointers. This is needed to prevent infinite recursion. If ADD_RESTRICT, pretend that the pointer NAME is restrict even if DECL does not advertise it.
References bitmap_bit_p, bitmap_clear_bit(), bitmap_set_bit, build_fake_var_decl(), check_for_overlaps(), create_variable_info_for_1(), DECL_EXTERNAL, DECL_P, DECL_SIZE, dump_file, free(), variable_info::fullsize, ggc_strdup, fieldoff::has_unknown_size, variable_info::head, HOST_WIDE_INT_PRINT_DEC, i, variable_info::id, in_ipa_mode, insert_vi_for_tree(), variable_info::is_full_var, is_global_var(), variable_info::is_restrict_var, variable_info::is_unknown_size_var, make_constraint_from(), make_param_constraints(), fieldoff::may_have_pointers, variable_info::may_have_pointers, variable_info::name, new_var_info(), variable_info::next, NULL, fieldoff::offset, variable_info::offset, fieldoff::only_restrict_pointers, variable_info::only_restrict_pointers, POINTER_TYPE_P, push_fields_onto_fieldstack(), fieldoff::restrict_pointed_type, fieldoff::size, variable_info::size, sort_fieldstack(), tree_fits_uhwi_p(), tree_to_uhwi(), TREE_TYPE, type_contains_placeholder_p(), TYPE_RESTRICT, TYPE_SIZE, TYPE_UID, use_field_sensitive, var_can_have_subvars(), and vi_next().
Referenced by create_variable_info_for(), create_variable_info_for_1(), and intra_create_variable_infos().
◆ debug_constraint()
| DEBUG_FUNCTION void debug_constraint | ( | constraint_t | c | ) |
Print out constraint C to stderr.
References dump_constraint().
◆ debug_constraint_graph()
| DEBUG_FUNCTION void debug_constraint_graph | ( | void | ) |
Print out the constraint graph to stderr.
References dump_constraint_graph().
◆ debug_constraints()
| DEBUG_FUNCTION void debug_constraints | ( | void | ) |
Print out all constraints to stderr.
References dump_constraints().
◆ debug_sa_points_to_info()
| DEBUG_FUNCTION void debug_sa_points_to_info | ( | void | ) |
Debug points-to information to stderr.
References dump_sa_points_to_info().
◆ debug_solution_for_var()
| DEBUG_FUNCTION void debug_solution_for_var | ( | unsigned int | var | ) |
Print the points-to solution for VAR to stderr.
References dump_solution_for_var(), and constraint_expr::var.
◆ debug_varinfo()
| DEBUG_FUNCTION void debug_varinfo | ( | varinfo_t | vi | ) |
Dump varinfo VI to stderr.
References dump_varinfo().
◆ debug_varmap()
| DEBUG_FUNCTION void debug_varmap | ( | void | ) |
Dump varmap to stderr.
References dump_varmap().
◆ delete_points_to_sets()
|
static |
Delete created points-to sets.
References bitmap_obstack_release(), call_stmt_vars, constraint_pool, constraints, dump_file, dump_flags, fake_var_decl_obstack, final_solutions, final_solutions_obstack, free(), i, NULL, pta_obstack, shared_bitmap_table, TDF_STATS, variable_info_pool, varmap, and vi_for_tree.
Referenced by compute_may_aliases(), and ipa_pta_execute().
◆ determine_global_memory_access()
|
static |
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().
◆ 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 ADDRESSOF, bitmap_set_bit, changed, DEREF, do_ds_constraint(), do_sd_constraint(), gcc_checking_assert, gcc_unreachable, get_varinfo(), variable_info::is_special_var, constraint::lhs, constraint_expr::offset, constraint::rhs, SCALAR, set_union_with_increment(), variable_info::solution, constraint_expr::type, and constraint_expr::var.
Referenced by solve_graph().
◆ do_deref()
Dereference the constraint expression CONS, and return the result. DEREF (ADDRESSOF) = SCALAR DEREF (SCALAR) = DEREF DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) This is needed so that we can handle dereferencing DEREF constraints.
References ADDRESSOF, constraints, DEREF, FOR_EACH_VEC_ELT, gcc_unreachable, i, new_constraint(), new_scalar_tmp_constraint_exp(), process_constraint(), SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), get_constraint_for_1(), and get_constraint_for_component_ref().
◆ 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(), anything_id, bitmap_bit_p, bitmap_ior_into(), bitmap_set_bit, changed, escaped_id, EXECUTE_IF_SET_IN_BITMAP, find(), first_or_preceding_vi_for_offset(), gcc_checking_assert, get_varinfo(), variable_info::head, variable_info::id, variable_info::is_full_var, variable_info::is_global_var, variable_info::is_special_var, constraint::lhs, variable_info::may_have_pointers, variable_info::next, constraint_expr::offset, variable_info::offset, constraint::rhs, variable_info::size, variable_info::solution, solution_set_expand(), solve_add_graph_edge(), storedanything_id, UNKNOWN_OFFSET, constraint_expr::var, and 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 anything_id, bitmap_bit_p, bitmap_set_bit, changed, EXECUTE_IF_SET_IN_BITMAP, find(), first_or_preceding_vi_for_offset(), gcc_checking_assert, get_varinfo(), variable_info::head, variable_info::id, variable_info::is_full_var, constraint::lhs, variable_info::next, constraint_expr::offset, variable_info::offset, constraint::rhs, variable_info::size, variable_info::solution, solution_set_expand(), solve_add_graph_edge(), UNKNOWN_OFFSET, constraint_expr::var, and vi_next().
Referenced by do_complex_constraint().
◆ do_structure_copy()
Handle aggregate copies by expanding into copies of the respective fields of the structures.
References ADDRESSOF, anything_id, DEREF, gcc_assert, gcc_unreachable, get_constraint_for(), get_constraint_for_rhs(), get_ref_base_and_extent_hwi(), get_varinfo(), variable_info::is_full_var, variable_info::may_have_pointers, new_constraint(), constraint_expr::offset, variable_info::offset, process_all_all_constraints(), process_constraint(), ranges_overlap_p(), SCALAR, variable_info::size, constraint_expr::type, UNKNOWN_OFFSET, and constraint_expr::var.
Referenced by find_func_aliases().
◆ dump_constraint()
|
static |
Print out constraint C to FILE.
References ADDRESSOF, DEREF, dump_file, get_varinfo(), HOST_WIDE_INT_PRINT_DEC, constraint::lhs, variable_info::name, constraint_expr::offset, constraint::rhs, constraint_expr::type, UNKNOWN_OFFSET, and constraint_expr::var.
Referenced by debug_constraint(), dump_constraint_graph(), dump_constraints(), and rewrite_constraints().
◆ dump_constraint_graph()
|
static |
Print the constraint graph in dot format.
References dump_constraint(), EXECUTE_IF_IN_NONNULL_BITMAP, find(), FIRST_REF_NODE, get_varinfo(), and i.
Referenced by debug_constraint_graph(), and solve_constraints().
◆ dump_constraints()
|
static |
Print out all constraints to FILE
References constraints, dump_constraint(), and i.
Referenced by compute_points_to_sets(), debug_constraints(), and ipa_pta_execute().
◆ 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, get_varinfo(), i, and si.
Referenced by perform_var_substitution().
◆ dump_pta_stats()
| void dump_pta_stats | ( | FILE * | s | ) |
References HOST_WIDE_INT_PRINT_DEC, and pta_stats.
Referenced by dump_memory_report().
◆ dump_sa_points_to_info()
|
static |
Dump points-to information to OUTFILE.
References dump_solution_for_var(), get_varinfo(), i, 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()
|
static |
Dump stats information to OUTFILE.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
◆ dump_solution_for_var()
|
static |
Print out the points-to solution for VAR to FILE.
References EXECUTE_IF_SET_IN_BITMAP, find(), get_varinfo(), i, variable_info::id, variable_info::name, variable_info::solution, and constraint_expr::var.
Referenced by debug_solution_for_var(), and dump_sa_points_to_info().
◆ dump_varinfo()
|
static |
Dump varinfo VI to FILE.
References bitmap_empty_p(), bitmap_equal_p(), EXECUTE_IF_SET_IN_BITMAP, variable_info::fullsize, variable_info::head, HOST_WIDE_INT_0U, HOST_WIDE_INT_PRINT_DEC, i, variable_info::id, variable_info::is_artificial_var, variable_info::is_fn_info, variable_info::is_full_var, variable_info::is_global_var, variable_info::is_heap_var, variable_info::is_ipa_escape_point, variable_info::is_restrict_var, variable_info::is_special_var, variable_info::is_unknown_size_var, variable_info::may_have_pointers, variable_info::name, variable_info::next, NULL, variable_info::offset, variable_info::oldsolution, variable_info::only_restrict_pointers, variable_info::ruid, variable_info::size, and variable_info::solution.
Referenced by debug_varinfo(), and dump_varmap().
◆ dump_varmap()
|
static |
Dump varmap to FILE.
References dump_varinfo(), get_varinfo(), i, and varmap.
Referenced by debug_varmap().
◆ 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(), 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().
◆ field_must_have_pointers()
References TREE_TYPE, and type_must_have_pointers().
Referenced by push_fields_onto_fieldstack().
◆ fieldoff_compare()
|
static |
qsort comparison function for two fieldoff's PA and PB
References fieldoff::offset, and fieldoff::size.
Referenced by sort_fieldstack().
◆ 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_dependence_clique(), compute_topo_order(), count_occurrences(), do_ds_constraint(), do_sd_constraint(), dump_constraint_graph(), dump_solution_for_var(), eliminate_indirect_cycles(), find(), find_indirect_cycles(), find_what_var_points_to(), autofdo::get_original_name(), ipa_pta_execute(), merge_node_constraints(), rewrite_constraints(), scc_visit(), set_uids_in_ptset(), solve_add_graph_edge(), solve_graph(), topo_visit(), unblock(), unify_nodes(), unite_pointer_equivalences(), and visit_loadstore().
◆ 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_func_aliases()
Walk statement T setting up aliasing constraints according to the references found in T. This function is the main part of the constraint builder. AI points to auxiliary alias information used when building alias sets and computing alias grouping heuristics.
References AGGREGATE_TYPE_P, as_a(), CONVERT_EXPR_CODE_P, function::decl, DECL_P, do_structure_copy(), dyn_cast(), escaped_id, escaped_return_id, fi_result, find_func_aliases_for_call(), FOR_EACH_VEC_ELT, get_base_address(), get_constraint_for(), get_constraint_for_address_of(), get_constraint_for_ptr_offset(), get_constraint_for_rhs(), get_function_part_constraint(), get_vi_for_tree(), gimple_asm_input_op(), gimple_asm_ninputs(), gimple_asm_noutputs(), gimple_asm_output_op(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs3(), gimple_assign_rhs_code(), gimple_assign_single_p(), gimple_num_ops(), gimple_op(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), gimple_return_retval(), i, in_ipa_mode, is_gimple_assign(), is_gimple_call(), variable_info::is_global_var, variable_info::is_ipa_escape_point, lookup_vi_for_tree(), make_constraint_to(), make_constraints_to(), make_escape_constraint(), new_constraint(), nonlocal_id, NULL, NULL_TREE, constraint_expr::offset, parse_input_constraint(), parse_output_constraint(), process_all_all_constraints(), process_constraint(), SCALAR, TREE_CLOBBER_P, TREE_CODE, TREE_PURPOSE, TREE_STRING_POINTER, TREE_TYPE, TREE_VALUE, truth_value_p(), constraint_expr::type, and constraint_expr::var.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
◆ find_func_aliases_for_builtin_call()
Create constraints for the builtin call T. Return true if the call was handled, otherwise false.
References ADDRESSOF, anything_id, BUILT_IN_NORMAL, CASE_BUILT_IN_TM_LOAD, CASE_BUILT_IN_TM_STORE, function::decl, variable_info::decl, DECL_EXTERNAL, DECL_FUNCTION_CODE(), do_deref(), ERF_NOALIAS, escaped_id, fi_result, fi_static_chain, find_func_aliases_for_call_arg(), fndecl_maybe_in_other_partition(), FOR_EACH_VEC_ELT, gcc_assert, gcc_unreachable, get_call_clobber_vi(), get_call_use_vi(), get_constraint_for(), get_constraint_for_ptr_offset(), get_function_part_constraint(), get_varinfo(), get_vi_for_tree(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_return_flags(), handle_lhs_call(), i, variable_info::id, in_ipa_mode, integer_id, integer_zerop(), variable_info::is_global_var, variable_info::is_heap_var, lookup_vi_for_tree(), make_any_offset_constraints(), make_constraint_from(), make_constraint_to(), make_heapvar(), new_constraint(), nonlocal_id, nothing_id, NULL, NULL_TREE, constraint_expr::offset, process_all_all_constraints(), process_constraint(), SCALAR, TREE_CODE, TREE_OPERAND, constraint_expr::type, and constraint_expr::var.
Referenced by find_func_aliases_for_call().
◆ find_func_aliases_for_call()
Create constraints for the call T.
References aggregate_value_p(), variable_info::decl, DECL_IS_OPERATOR_DELETE_P, do_deref(), ECF_CONST, ECF_LOOPING_CONST_OR_PURE, ECF_NOVOPS, ECF_PURE, fi_result, fi_static_chain, find_func_aliases_for_builtin_call(), find_func_aliases_for_call_arg(), fndecl_built_in_p(), FOR_EACH_VEC_ELT, gcc_checking_assert, get_constraint_for(), get_constraint_for_address_of(), get_fi_for_callee(), get_function_part_constraint(), gimple_call_arg(), gimple_call_chain(), gimple_call_flags(), gimple_call_fndecl(), gimple_call_fntype(), gimple_call_from_new_or_delete(), gimple_call_internal_p(), gimple_call_lhs(), gimple_call_num_args(), gimple_call_return_flags(), handle_lhs_call(), handle_rhs_call(), implicit_const_eaf_flags, implicit_pure_eaf_flags, in_ipa_mode, variable_info::is_fn_info, new_constraint(), NULL_TREE, and process_constraint().
Referenced by find_func_aliases().
◆ find_func_aliases_for_call_arg()
Create constraints for assigning call argument ARG to the incoming parameter INDEX of function FI.
References fi_parm_base, FOR_EACH_VEC_ELT, get_constraint_for_rhs(), get_function_part_constraint(), new_constraint(), and process_constraint().
Referenced by find_func_aliases_for_builtin_call(), and find_func_aliases_for_call().
◆ find_func_clobbers()
Walk statement T setting up clobber and use constraints according to the references found in T. This function is a main part of the IPA constraint builder.
References anything_id, as_a(), auto_var_in_fn_p(), BUILT_IN_NORMAL, function::decl, variable_info::decl, DECL_FUNCTION_CODE(), DECL_P, dyn_cast(), escaped_id, fi_clobbers, fi_uses, first_vi_for_offset(), fndecl_maybe_in_other_partition(), FOR_EACH_VEC_ELT, gcc_assert, gcc_unreachable, get_constraint_for(), get_constraint_for_address_of(), get_constraint_for_ptr_offset(), get_fi_for_callee(), get_function_part_constraint(), get_vi_for_tree(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_call_num_args(), gimple_get_lhs(), gimple_has_lhs(), gimple_return_retval(), gimple_vdef(), gimple_vuse(), handled_component_p(), i, variable_info::id, in_ipa_mode, INDIRECT_REF_P, variable_info::is_fn_info, is_gimple_min_invariant(), lookup_call_clobber_vi(), lookup_call_use_vi(), lookup_vi_for_tree(), make_constraint_from(), make_copy_constraint(), new_constraint(), NULL, NULL_TREE, process_constraint(), process_ipa_clobber(), TREE_CODE, and TREE_OPERAND.
Referenced by ipa_pta_execute().
◆ 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 solve_constraints().
◆ find_what_p_points_to()
Given a pointer variable P, fill in its points-to set.
References DECL_STRUCT_FUNCTION, find_what_var_points_to(), get_ptr_info(), get_range_query(), lookup_vi_for_tree(), prange::nonzero_p(), pt_solution::null, ptr_info_def::pt, path_range_query::range_of_expr(), set_ptr_nonnull(), SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, and TREE_CODE.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
◆ find_what_var_points_to()
|
static |
Compute the points-to solution *PT for the variable VI.
References pt_solution::anything, anything_id, bitmap_bit_p, bitmap_clear(), BITMAP_GGC_ALLOC, pt_solution::const_pool, pt_solution::escaped, escaped_id, EXECUTE_IF_SET_IN_BITMAP, final_solutions, final_solutions_obstack, find(), get_varinfo(), i, variable_info::id, in_ipa_mode, integer_id, pt_solution::ipa_escaped, variable_info::is_artificial_var, pt_solution::nonlocal, nonlocal_id, nothing_id, NULL, pt_solution::null, set_uids_in_ptset(), shared_bitmap_add(), shared_bitmap_lookup(), variable_info::solution, string_id, and pt_solution::vars.
Referenced by compute_points_to_sets(), find_what_p_points_to(), and ipa_pta_execute().
◆ first_or_preceding_vi_for_offset()
|
static |
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(), offset, 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()
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, offset, 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()
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().
◆ 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 solve_constraints().
◆ get_call_clobber_vi()
Lookup or create the variable for the call statement CALL representing the clobbers.
References get_call_vi(), and vi_next().
Referenced by find_func_aliases_for_builtin_call(), and handle_call_arg().
◆ get_call_use_vi()
Lookup or create the variable for the call statement CALL representing the uses.
References get_call_vi().
Referenced by find_func_aliases_for_builtin_call(), handle_call_arg(), and handle_rhs_call().
◆ get_call_vi()
Lookup or create the variable for the call statement CALL.
References call_stmt_vars, variable_info::fullsize, variable_info::id, variable_info::is_full_var, variable_info::is_reg_var, new_var_info(), variable_info::next, NULL_TREE, variable_info::offset, and variable_info::size.
Referenced by get_call_clobber_vi(), and get_call_use_vi().
◆ get_constraint_for()
Given a gimple tree T, return the constraint expression vector for it.
References gcc_assert, and get_constraint_for_1().
Referenced by do_structure_copy(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), find_func_clobbers(), and handle_lhs_call().
◆ get_constraint_for_1()
|
static |
Given a tree T, return the constraint expression for it.
References address_p(), ADDRESSOF, anything_id, CONSTRUCTOR_ELTS, CONSTRUCTOR_NELTS, DEREF, do_deref(), FOR_EACH_CONSTRUCTOR_VALUE, FOR_EACH_VEC_ELT, get_constraint_for_1(), get_constraint_for_address_of(), get_constraint_for_component_ref(), get_constraint_for_ptr_offset(), get_constraint_for_ssa_var(), get_varinfo(), i, integer_zerop(), nonlocal_id, nothing_id, constraint_expr::offset, SCALAR, string_id, tcc_constant, tcc_declaration, tcc_exceptional, tcc_expression, tcc_reference, TREE_CODE, TREE_CODE_CLASS, tree_fits_uhwi_p(), TREE_OPERAND, TREE_THIS_VOLATILE, tree_to_uhwi(), TREE_TYPE, constraint_expr::type, type_can_have_subvars(), TYPE_SIZE, UNKNOWN_OFFSET, constraint_expr::var, VAR_P, and vi_next().
Referenced by get_constraint_for(), get_constraint_for_1(), get_constraint_for_address_of(), get_constraint_for_component_ref(), and get_constraint_for_rhs().
◆ get_constraint_for_address_of()
Given a tree T, return the constraint expression for taking the address of it.
References ADDRESSOF, DEREF, FOR_EACH_VEC_ELT, get_constraint_for_1(), i, SCALAR, and constraint_expr::type.
Referenced by create_variable_info_for(), find_func_aliases(), find_func_aliases_for_call(), find_func_clobbers(), get_constraint_for_1(), and handle_rhs_call().
◆ get_constraint_for_component_ref()
|
static |
Given a COMPONENT_REF T, return the constraint_expr vector for it. If address_p is true the result will be taken its address of. If lhs_p is true then the constraint expression is assumed to be used as the lhs.
References address_p(), ADDRESSOF, AGGREGATE_TYPE_P, anything_id, CONSTANT_CLASS_P, DEREF, do_deref(), dump_file, dump_flags, variable_info::fullsize, gcc_assert, gcc_unreachable, get_constraint_for_1(), get_ref_base_and_extent(), get_varinfo(), handled_component_p(), variable_info::id, INDIRECT_REF_P, integer_id, integer_zerop(), poly_int< N, C >::is_constant(), variable_info::is_full_var, known_eq, mem_ref_offset(), variable_info::next, nothing_id, constraint_expr::offset, variable_info::offset, SCALAR, variable_info::size, TDF_DETAILS, poly_int< N, C >::to_shwi(), TREE_CODE, TREE_OPERAND, TREE_TYPE, constraint_expr::type, UNKNOWN_OFFSET, constraint_expr::var, and vi_next().
Referenced by get_constraint_for_1().
◆ get_constraint_for_ptr_offset()
Get constraint expressions for offsetting PTR by OFFSET. Stores the resulting constraint expressions in *RESULTS.
References ADDRESSOF, first_or_preceding_vi_for_offset(), wi::fits_shwi_p(), gcc_assert, gcc_unreachable, get_constraint_for_rhs(), get_varinfo(), variable_info::head, variable_info::id, variable_info::is_full_var, NULL_TREE, constraint_expr::offset, offset, variable_info::offset, SCALAR, SIGNED, variable_info::size, wi::to_wide(), TREE_CODE, constraint_expr::type, UNKNOWN_OFFSET, use_field_sensitive, constraint_expr::var, and vi_next().
Referenced by find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_clobbers(), and get_constraint_for_1().
◆ get_constraint_for_rhs()
Given a gimple tree T, return the constraint expression vector for it to be used as the rhs of a constraint.
References gcc_assert, and get_constraint_for_1().
Referenced by do_structure_copy(), find_func_aliases(), find_func_aliases_for_call_arg(), get_constraint_for_ptr_offset(), make_constraint_to(), and process_ipa_clobber().
◆ get_constraint_for_ssa_var()
Get a constraint expression vector from an SSA_VAR_P node. If address_p is true, the result will be taken its address of.
References address_p(), symtab_node::alias, symtab_node::analyzed, symtab_node::decl, DECL_EXTERNAL, DECL_P, DECL_PT_UID, DECL_PT_UID_SET_P, DECL_UID, gcc_assert, varpool_node::get(), get_constraint_for_ssa_var(), get_vi_for_tree(), symtab_node::nonzero_address(), nothing_id, constraint_expr::offset, SCALAR, ssa_defined_default_def_p(), SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, TREE_CODE, TREE_STATIC, constraint_expr::type, varpool_node::ultimate_alias_target(), constraint_expr::var, VAR_P, and vi_next().
Referenced by get_constraint_for_1(), and get_constraint_for_ssa_var().
◆ get_fi_for_callee()
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_function_part_constraint()
|
static |
Get a constraint for the requested part of a function designator FI when operating in IPA mode.
References anything_id, DEREF, first_vi_for_offset(), gcc_assert, variable_info::id, in_ipa_mode, constraint_expr::offset, SCALAR, TREE_CODE, constraint_expr::type, and constraint_expr::var.
Referenced by create_variable_info_for(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), find_func_aliases_for_call_arg(), find_func_clobbers(), and process_ipa_clobber().
◆ get_varinfo()
|
inlinestatic |
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().
◆ get_vi_for_tree()
Find the variable id for tree T in the map. If T doesn't exist in the map, create an entry for it and return it.
References alias_get_name(), create_variable_info_for(), get_varinfo(), NULL, and vi_for_tree.
Referenced by create_variable_info_for(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_clobbers(), get_constraint_for_ssa_var(), get_fi_for_callee(), intra_create_variable_infos(), and ipa_pta_execute().
◆ handle_call_arg()
|
static |
Produce constraints for argument ARG of call STMT with eaf flags FLAGS. RESULTS is array holding constraints for return value. CALLESCAPE_ID is variable where call loocal escapes are added. WRITES_GLOVEL_MEMORY is true if callee may write global memory.
References DEREF, EAF_NO_DIRECT_CLOBBER, EAF_NO_DIRECT_ESCAPE, EAF_NO_DIRECT_READ, EAF_NO_INDIRECT_CLOBBER, EAF_NO_INDIRECT_ESCAPE, EAF_NO_INDIRECT_READ, EAF_NOT_RETURNED_DIRECTLY, EAF_NOT_RETURNED_INDIRECTLY, EAF_UNUSED, gcc_checking_assert, get_call_clobber_vi(), get_call_use_vi(), gimple_call_lhs(), variable_info::id, variable_info::is_reg_var, make_any_offset_constraints(), make_constraint_to(), make_copy_constraint(), make_escape_constraint(), make_indirect_escape_constraint(), make_transitive_closure_constraints(), new_constraint(), new_var_info(), NULL, NULL_TREE, constraint_expr::offset, process_constraint(), SCALAR, constraint_expr::type, UNKNOWN_OFFSET, and constraint_expr::var.
Referenced by handle_rhs_call().
◆ handle_lhs_call()
|
static |
For non-IPA mode, generate constraints necessary for a call that returns a pointer and assigns it to LHS. This simply makes the LHS point to global and escaped variables.
References ADDRESSOF, BUILT_IN_NORMAL, variable_info::decl, DECL_EXTERNAL, DECL_P, ERF_NOALIAS, ERF_RETURN_ARG_MASK, ERF_RETURNS_ARG, escaped_id, fndecl_built_in_p(), get_base_address(), get_constraint_for(), gimple_call_arg(), gimple_call_num_args(), variable_info::id, is_global_var(), variable_info::is_global_var, make_constraint_from(), make_heapvar(), nonlocal_id, constraint_expr::offset, process_all_all_constraints(), SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by find_func_aliases_for_builtin_call(), and find_func_aliases_for_call().
◆ handle_rhs_call()
|
static |
For non-IPA mode, generate constraints necessary for a call on the RHS and collect return value constraint to RESULTS to be used later in handle_lhs_call. IMPLICIT_EAF_FLAGS are added to each function argument. If WRITES_GLOBAL_MEMORY is true function is assumed to possibly write to global memory. Similar for READS_GLOBAL_MEMORY.
References ADDRESSOF, determine_global_memory_access(), EAF_NO_DIRECT_ESCAPE, EAF_NOT_RETURNED_DIRECTLY, EAF_UNUSED, escaped_id, FOR_EACH_VEC_ELT, get_call_use_vi(), get_constraint_for_address_of(), gimple_call_arg(), gimple_call_arg_flags(), gimple_call_chain(), gimple_call_lhs(), gimple_call_num_args(), gimple_call_retslot_flags(), gimple_call_return_slot_opt_p(), gimple_call_static_chain_flags(), handle_call_arg(), i, variable_info::id, make_constraints_to(), make_copy_constraint(), new_constraint(), new_var_info(), nonlocal_id, NULL, NULL_TREE, process_constraint(), SCALAR, TREE_ADDRESSABLE, and TREE_TYPE.
Referenced by find_func_aliases_for_call().
◆ init_alias_vars()
|
static |
Initialize things necessary to perform PTA
References bitmap_obstack_initialize(), call_stmt_vars, constraints, fake_var_decl_obstack, final_solutions, final_solutions_obstack, gcc_obstack_init, init_base_vars(), oldpta_obstack, predbitmap_obstack, pta_obstack, shared_bitmap_table, use_field_sensitive, varmap, and vi_for_tree.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
◆ init_base_vars()
|
static |
Initialize the always-existing constraint variables for NULL ANYTHING, READONLY, and INTEGER
References ADDRESSOF, anything_id, constraints, DEREF, escaped_id, escaped_return_id, variable_info::fullsize, gcc_assert, variable_info::id, integer_id, variable_info::is_artificial_var, variable_info::is_global_var, variable_info::is_special_var, variable_info::may_have_pointers, new_constraint(), new_var_info(), nonlocal_id, nothing_id, NULL, NULL_TREE, variable_info::offset, process_constraint(), SCALAR, variable_info::size, storedanything_id, string_id, UNKNOWN_OFFSET, and varmap.
Referenced by init_alias_vars().
◆ init_graph()
|
static |
Initialize the constraint graph structure to contain SIZE nodes.
Referenced by 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().
◆ insert_vi_for_tree()
Insert ID as the variable id for tree T in the vi_for_tree map.
References gcc_assert, and vi_for_tree.
Referenced by associate_varinfo_to_alias(), create_function_info_for(), create_variable_info_for(), create_variable_info_for_1(), intra_create_variable_infos(), and make_heapvar().
◆ intra_create_variable_infos()
|
static |
Create varinfo structures for all of the variables in the function for intraprocedural mode.
References alias_get_name(), BITMAP_ALLOC, BITMAP_FREE, create_variable_info_for_1(), function::decl, DECL_ARGUMENTS, DECL_BY_REFERENCE, DECL_CHAIN, DECL_CXX_CONSTRUCTOR_P, DECL_RESULT, get_vi_for_tree(), insert_vi_for_tree(), make_constraint_from(), make_param_constraints(), nonlocal_id, NULL, NULL_TREE, function::static_chain_decl, and vi_next().
Referenced by compute_points_to_sets().
◆ ipa_pta_execute()
|
static |
Execute the driver for IPA PTA.
References symtab_node::alias, alias_get_name(), allocate_decl_uid(), symtab_node::analyzed, pt_solution::anything, anything_id, associate_varinfo_to_alias(), auto_var_in_fn_p(), auto_var_p(), bitmap_bit_p, varpool_node::call_for_symbol_and_aliases(), cgraph_node::call_for_symbol_thunks_and_aliases(), cfun, cgraph_node::clone_of, constraints, create_function_info_for(), symtab_node::decl, variable_info::decl, DECL_ASSEMBLER_NAME, DECL_ASSEMBLER_NAME_SET_P, DECL_ATTRIBUTES, DECL_EXTERNAL, DECL_STRUCT_FUNCTION, delete_points_to_sets(), symbol_table::dump(), dump_constraints(), dump_file, dump_flags, symtab_node::dump_name(), dump_sa_points_to_info(), dump_sa_stats(), dyn_cast(), ECF_CONST, ECF_NOVOPS, ECF_PURE, escaped_id, EXECUTE_IF_SET_IN_BITMAP, fi_clobbers, fi_parm_base, fi_uses, final_solutions, final_solutions_obstack, find(), find_func_aliases(), find_func_clobbers(), find_what_p_points_to(), find_what_var_points_to(), first_vi_for_offset(), fndecl_maybe_in_other_partition(), FOR_EACH_BB_FN, FOR_EACH_DEFINED_FUNCTION, FOR_EACH_VARIABLE, FOR_EACH_VEC_ELT, symtab_node::force_output, gcc_assert, gcc_obstack_init, gcc_unreachable, cgraph_node::get_body(), get_fi_for_callee(), get_varinfo(), get_vi_for_tree(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_clobber_set(), gimple_call_flags(), gimple_call_fndecl(), gimple_call_use_set(), function::gimple_df, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), cgraph_node::has_gimple_body_p(), i, variable_info::id, IDENTIFIER_POINTER, in_ipa_mode, symtab_node::in_other_partition, init_alias_vars(), cgraph_node::inlined_to, pt_solution::ipa_escaped, ipa_escaped_pt, gimple_df::ipa_pta, variable_info::is_fn_info, variable_info::is_global_var, variable_info::is_ipa_escape_point, lookup_attribute(), lookup_call_clobber_vi(), lookup_call_use_vi(), lookup_vi_for_tree(), pt_solution::nonlocal, nonlocal_id, NULL, NULL_TREE, POINTER_TYPE_P, pt_solution_ior_into(), pt_solution_reset(), refered_from_nonlocal_fn(), refered_from_nonlocal_var(), variable_info::shadow_var_uid, variable_info::solution, solve_constraints(), gimple_df::ssa_names, symtab, TDF_DETAILS, TDF_STATS, TREE_OPERAND, TREE_PUBLIC, TREE_TYPE, symtab_node::used_from_other_partition, varmap, vi_next(), and virtual_operand_p().
◆ 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().
◆ lookup_call_clobber_vi()
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()
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()
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().
◆ make_any_offset_constraints()
|
static |
Add constraints to that the solution of VI has all subvariables added.
References variable_info::id, new_constraint(), process_constraint(), SCALAR, and UNKNOWN_OFFSET.
Referenced by find_func_aliases_for_builtin_call(), and handle_call_arg().
◆ make_constraint_from()
|
static |
Create a constraint ID = &FROM.
References ADDRESSOF, variable_info::id, new_constraint(), process_constraint(), and SCALAR.
Referenced by create_function_info_for(), create_variable_info_for_1(), find_func_aliases_for_builtin_call(), find_func_clobbers(), handle_lhs_call(), intra_create_variable_infos(), make_constraint_from_restrict(), and make_param_constraints().
◆ make_constraint_from_global_restrict()
|
static |
Create a new artificial heap variable with NAME and make a constraint from it to LHS. Set flags according to a tag used for tracking restrict pointers and make the artificial heap point to global memory.
References make_constraint_from_restrict(), make_copy_constraint(), and nonlocal_id.
Referenced by create_variable_info_for().
◆ make_constraint_from_restrict()
|
static |
Create a new artificial heap variable with NAME and make a constraint from it to LHS. Set flags according to a tag used for tracking restrict pointers.
References variable_info::id, variable_info::is_global_var, variable_info::is_restrict_var, make_constraint_from(), make_heapvar(), and variable_info::may_have_pointers.
Referenced by make_constraint_from_global_restrict().
◆ make_constraint_to()
|
static |
Create a constraint ID = OP.
References get_constraint_for_rhs(), and make_constraints_to().
Referenced by find_func_aliases(), find_func_aliases_for_builtin_call(), handle_call_arg(), and make_escape_constraint().
◆ make_constraints_to()
Create constraints ID = { rhsc }.
References FOR_EACH_VEC_ELT, includes, new_constraint(), process_constraint(), SCALAR, and constraint_expr::var.
Referenced by find_func_aliases(), handle_rhs_call(), and make_constraint_to().
◆ make_copy_constraint()
|
static |
Create a constraint ID = FROM.
References variable_info::id, new_constraint(), process_constraint(), and SCALAR.
Referenced by create_function_info_for(), create_variable_info_for(), find_func_clobbers(), handle_call_arg(), handle_rhs_call(), and make_constraint_from_global_restrict().
◆ make_escape_constraint()
|
static |
Make constraints necessary to make OP escape.
References escaped_id, and make_constraint_to().
Referenced by find_func_aliases(), and handle_call_arg().
◆ make_heapvar()
Create a new artificial heap variable with NAME. Return the created variable.
References build_fake_var_decl(), DECL_EXTERNAL, variable_info::fullsize, insert_vi_for_tree(), variable_info::is_full_var, variable_info::is_heap_var, variable_info::is_unknown_size_var, new_var_info(), variable_info::offset, ptr_type_node, and variable_info::size.
Referenced by find_func_aliases_for_builtin_call(), handle_lhs_call(), and make_constraint_from_restrict().
◆ make_indirect_escape_constraint()
|
static |
Make constraint necessary to make all indirect references from VI escape.
References DEREF, escaped_id, variable_info::id, new_constraint(), process_constraint(), SCALAR, and UNKNOWN_OFFSET.
Referenced by handle_call_arg().
◆ make_param_constraints()
|
static |
Register the constraints for function parameter related VI.
References variable_info::is_full_var, make_constraint_from(), variable_info::may_have_pointers, nonlocal_id, variable_info::only_restrict_pointers, and vi_next().
Referenced by create_variable_info_for_1(), and intra_create_variable_infos().
◆ make_pass_build_alias()
| gimple_opt_pass * make_pass_build_alias | ( | gcc::context * | ctxt | ) |
◆ make_pass_build_ealias()
| gimple_opt_pass * make_pass_build_ealias | ( | gcc::context * | ctxt | ) |
◆ make_pass_ipa_pta()
| simple_ipa_opt_pass * make_pass_ipa_pta | ( | gcc::context * | ctxt | ) |
◆ make_transitive_closure_constraints()
|
static |
Add constraints to that the solution of VI is transitively closed.
References DEREF, variable_info::id, new_constraint(), process_constraint(), SCALAR, and UNKNOWN_OFFSET.
Referenced by handle_call_arg().
◆ maybe_set_dependence_info()
If BASE is a MEM_REF then assign a clique, base pair to it, updating CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA. Return whether dependence info was assigned to BASE.
References cfun, MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, variable_info::ruid, TREE_CODE, and TREE_OPERAND.
Referenced by compute_dependence_clique().
◆ merge_graph_nodes()
|
static |
Merge GRAPH nodes FROM and TO into node TO.
References BITMAP_ALLOC, bitmap_ior_into(), clear_edges_for_node(), and 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(), DEREF, find(), FOR_EACH_VEC_ELT, gcc_checking_assert, i, constraint::lhs, constraint::rhs, constraint_expr::type, and constraint_expr::var.
Referenced by unify_nodes().
◆ move_complex_constraints()
|
static |
Move complex constraints to the GRAPH nodes they belong to.
References ADDRESSOF, anything_id, constraints, DEREF, FOR_EACH_VEC_ELT, get_varinfo(), i, insert_into_complex(), variable_info::is_special_var, constraint::lhs, and constraint::rhs.
Referenced by solve_constraints().
◆ new_constraint()
|
static |
Create a new constraint consisting of LHS and RHS expressions.
References constraint_pool, constraint::lhs, and constraint::rhs.
Referenced by create_variable_info_for(), do_deref(), do_structure_copy(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), find_func_aliases_for_call_arg(), find_func_clobbers(), handle_call_arg(), handle_rhs_call(), init_base_vars(), make_any_offset_constraints(), make_constraint_from(), make_constraints_to(), make_copy_constraint(), make_indirect_escape_constraint(), make_transitive_closure_constraints(), process_all_all_constraints(), process_constraint(), and process_ipa_clobber().
◆ new_scalar_tmp_constraint_exp()
|
static |
Get a scalar constraint expression for a new temporary variable.
References new_var_info(), NULL_TREE, constraint_expr::offset, SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by do_deref(), process_all_all_constraints(), and process_constraint().
◆ new_var_info()
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 variable_info::address_taken, BITMAP_ALLOC, variable_info::decl, DECL_HARD_REGISTER, DECL_P, dump_file, free(), ggc_strdup, variable_info::head, variable_info::id, variable_info::is_artificial_var, variable_info::is_fn_info, variable_info::is_full_var, is_global_var(), variable_info::is_global_var, variable_info::is_heap_var, variable_info::is_ipa_escape_point, variable_info::is_reg_var, variable_info::is_restrict_var, variable_info::is_special_var, variable_info::is_unknown_size_var, variable_info::may_have_pointers, variable_info::name, variable_info::next, NULL, NULL_TREE, variable_info::oldsolution, variable_info::only_restrict_pointers, pta_obstack, variable_info::ruid, variable_info::shadow_var_uid, variable_info::solution, 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().
◆ 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, 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 solve_constraints().
◆ process_all_all_constraints()
|
static |
Efficiently generates constraints from all entries in *RHSC to all entries in *LHSC.
References FOR_EACH_VEC_ELT, i, new_constraint(), new_scalar_tmp_constraint_exp(), and process_constraint().
Referenced by do_structure_copy(), find_func_aliases(), find_func_aliases_for_builtin_call(), and handle_lhs_call().
◆ process_constraint()
|
static |
Process constraint T, performing various simplifications and then adding it to our list of overall constraints.
References variable_info::address_taken, ADDRESSOF, anything_id, constraints, DEREF, gcc_assert, get_varinfo(), variable_info::head, constraint::lhs, variable_info::may_have_pointers, new_constraint(), new_scalar_tmp_constraint_exp(), process_constraint(), constraint::rhs, SCALAR, constraint_expr::type, and varmap.
Referenced by create_variable_info_for(), do_deref(), do_structure_copy(), find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), find_func_aliases_for_call_arg(), find_func_clobbers(), handle_call_arg(), handle_rhs_call(), init_base_vars(), make_any_offset_constraints(), make_constraint_from(), make_constraints_to(), make_copy_constraint(), make_indirect_escape_constraint(), make_transitive_closure_constraints(), process_all_all_constraints(), process_constraint(), and process_ipa_clobber().
◆ process_ipa_clobber()
Create a constraint adding to the clobber set of FI the memory pointed to by PTR.
References fi_clobbers, FOR_EACH_VEC_ELT, get_constraint_for_rhs(), get_function_part_constraint(), i, new_constraint(), process_constraint(), and vNULL.
Referenced by find_func_clobbers().
◆ pt_solution_empty_p()
| bool pt_solution_empty_p | ( | const pt_solution * | pt | ) |
Return true if the points-to solution *PT is empty.
References pt_solution::anything, bitmap_empty_p(), cfun, pt_solution::escaped, pt_solution::ipa_escaped, ipa_escaped_pt, pt_solution::nonlocal, pt_solution_empty_p(), and pt_solution::vars.
Referenced by dump_gimple_call(), pt_solution_empty_p(), and pt_solutions_intersect_1().
◆ pt_solution_includes()
| bool pt_solution_includes | ( | struct pt_solution * | pt, |
| const_tree | decl ) |
◆ pt_solution_includes_1()
|
static |
Return true if the points-to solution *PT includes the variable declaration DECL.
References pt_solution::anything, bitmap_bit_p, cfun, DECL_PT_UID, pt_solution::escaped, pt_solution::ipa_escaped, ipa_escaped_pt, is_global_var(), pt_solution::nonlocal, pt_solution_includes_1(), and pt_solution::vars.
Referenced by pt_solution_includes(), and pt_solution_includes_1().
◆ pt_solution_includes_const_pool()
| bool pt_solution_includes_const_pool | ( | struct pt_solution * | pt | ) |
Return true if the points-to solution *PT contains a reference to a constant pool entry.
References cfun, pt_solution::const_pool, pt_solution::escaped, pt_solution::ipa_escaped, ipa_escaped_pt, and pt_solution::nonlocal.
Referenced by ptrs_compare_unequal().
◆ pt_solution_includes_global()
| bool pt_solution_includes_global | ( | struct pt_solution * | pt, |
| bool | escaped_local_p ) |
Return true if the points-to solution *PT includes global memory. If ESCAPED_LOCAL_P is true then escaped local variables are also considered global.
References pt_solution::anything, cfun, pt_solution::escaped, pt_solution::ipa_escaped, ipa_escaped_pt, pt_solution::nonlocal, pt_solution_includes_global(), pt_solution::vars_contains_escaped, pt_solution::vars_contains_escaped_heap, and pt_solution::vars_contains_nonlocal.
Referenced by pt_solution_includes_global(), and ptr_deref_may_alias_global_p().
◆ pt_solution_ior_into()
|
static |
Computes the union of the points-to solutions *DEST and *SRC and stores the result in *DEST. This changes the points-to bitmap of *DEST and thus may not be used if that might be shared. The points-to bitmap of *SRC and *DEST will not be shared after this function if they were not before.
References pt_solution::anything, BITMAP_GGC_ALLOC, bitmap_ior_into(), pt_solution::const_pool, pt_solution::escaped, pt_solution::ipa_escaped, pt_solution::nonlocal, pt_solution::null, pt_solution_reset(), pt_solution::vars, pt_solution::vars_contains_escaped, pt_solution::vars_contains_escaped_heap, and pt_solution::vars_contains_nonlocal.
Referenced by ipa_pta_execute().
◆ pt_solution_reset()
| void pt_solution_reset | ( | struct pt_solution * | pt | ) |
Reset the points-to solution *PT to a conservative default (point to anything).
References pt_solution::anything, and pt_solution::null.
Referenced by delete_tree_ssa(), expand_call_inline(), get_ptr_info(), gimple_call_reset_alias_info(), init_tree_ssa(), ipa_pta_execute(), parallelize_loops(), and pt_solution_ior_into().
◆ pt_solution_set()
| void pt_solution_set | ( | struct pt_solution * | pt, |
| bitmap | vars, | ||
| bool | vars_contains_nonlocal ) |
Set the points-to solution *PT to point only to the variables in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains global variables and VARS_CONTAINS_RESTRICT specifies whether it contains restrict tag variables.
References bitmap_intersect_p(), cfun, pt_solution::vars, pt_solution::vars_contains_escaped, and pt_solution::vars_contains_nonlocal.
Referenced by update_alias_info_with_stack_vars().
◆ pt_solution_set_var()
| void pt_solution_set_var | ( | struct pt_solution * | pt, |
| tree | var ) |
Set the points-to solution *PT to point only to the variable VAR.
References bitmap_bit_p, BITMAP_GGC_ALLOC, bitmap_set_bit, cfun, DECL_PT_UID, is_global_var(), pt_solution::vars, pt_solution::vars_contains_escaped, and pt_solution::vars_contains_nonlocal.
Referenced by copy_ref_info().
◆ pt_solution_singleton_or_null_p()
| bool pt_solution_singleton_or_null_p | ( | struct pt_solution * | pt, |
| unsigned * | uid ) |
Return true if the points-to solution *PT only point to a single var, and return the var uid in *UID.
References pt_solution::anything, bitmap_first_set_bit(), bitmap_single_bit_set_p(), pt_solution::escaped, pt_solution::ipa_escaped, pt_solution::nonlocal, NULL, and pt_solution::vars.
Referenced by fold_builtin_alloca_with_align(), and same_addr_size_stores_p().
◆ pt_solutions_intersect()
| bool pt_solutions_intersect | ( | struct pt_solution * | pt1, |
| struct pt_solution * | pt2 ) |
References pt_solutions_intersect_1(), and pta_stats.
Referenced by call_may_clobber_ref_p_1(), ptr_derefs_may_alias_p(), ptrs_compare_unequal(), and ref_maybe_used_by_call_p_1().
◆ pt_solutions_intersect_1()
|
static |
Return true if both points-to solutions PT1 and PT2 have a non-empty intersection.
References pt_solution::anything, bitmap_intersect_p(), pt_solution::escaped, pt_solution::ipa_escaped, ipa_escaped_pt, pt_solution::nonlocal, pt_solution_empty_p(), pt_solutions_intersect_1(), pt_solution::vars, pt_solution::vars_contains_escaped, and pt_solution::vars_contains_nonlocal.
Referenced by pt_solutions_intersect(), and pt_solutions_intersect_1().
◆ push_fields_onto_fieldstack()
|
static |
Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields of TYPE onto fieldstack, recording their offsets along the way. OFFSET is used to keep track of the offset in this entire structure, rather than just the immediately containing structure. Returns false if the caller is supposed to handle the field we recursed for.
References bitpos_of_field(), DECL_CHAIN, DECL_SIZE, empty_p(), field_must_have_pointers(), field_type(), fieldoff::has_unknown_size, integer_zerop(), fieldoff::may_have_pointers, fieldoff::must_have_pointers, NULL, NULL_TREE, fieldoff::offset, offset, fieldoff::only_restrict_pointers, POINTER_TYPE_P, push_fields_onto_fieldstack(), fieldoff::restrict_pointed_type, fieldoff::size, TREE_CODE, tree_fits_uhwi_p(), tree_to_uhwi(), TREE_TYPE, TYPE_FIELDS, TYPE_RESTRICT, and var_can_have_subvars().
Referenced by create_variable_info_for_1(), and push_fields_onto_fieldstack().
◆ refered_from_nonlocal_fn()
|
static |
Compute whether node is refered to non-locally. Worker for cgraph_for_symbol_thunks_and_aliases.
References symtab_node::decl, DECL_ATTRIBUTES, DECL_EXTERNAL, symtab_node::force_output, lookup_attribute(), TREE_PUBLIC, and symtab_node::used_from_other_partition.
Referenced by ipa_pta_execute().
◆ refered_from_nonlocal_var()
|
static |
Same for varpool nodes.
References symtab_node::decl, DECL_EXTERNAL, symtab_node::force_output, TREE_PUBLIC, and symtab_node::used_from_other_partition.
Referenced by ipa_pta_execute().
◆ 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 varmap.
Referenced by 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 constraints, dump_constraint(), dump_file, dump_flags, find(), find_equivalent_node(), FOR_EACH_VEC_ELT, gcc_assert, get_varinfo(), i, constraint::lhs, variable_info::name, NULL, constraint::rhs, si, TDF_DETAILS, and constraint_expr::var.
Referenced by 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_uids_in_ptset()
|
static |
Set bits in INTO corresponding to the variable uids in solution set FROM.
References anything_id, auto_var_in_fn_p(), bitmap_bit_p, bitmap_set_bit, variable_info::decl, decl_binds_to_current_def_p(), DECL_EXTERNAL, DECL_PT_UID, DECL_PT_UID_SET_P, DECL_UID, escaped_id, escaped_return_id, EXECUTE_IF_SET_IN_BITMAP, find(), get_varinfo(), i, in_ipa_mode, variable_info::is_artificial_var, variable_info::is_global_var, variable_info::is_heap_var, variable_info::is_restrict_var, SET_DECL_PT_UID, variable_info::shadow_var_uid, variable_info::solution, TREE_CODE, TREE_STATIC, VAR_P, pt_solution::vars_contains_escaped, pt_solution::vars_contains_escaped_heap, pt_solution::vars_contains_interposable, pt_solution::vars_contains_nonlocal, and pt_solution::vars_contains_restrict.
Referenced by find_what_var_points_to().
◆ set_union_with_increment()
|
static |
Union solution sets TO and DELTA, and add INC to each member of DELTA in the process.
References anything_id, bitmap_bit_p, bitmap_ior_into(), bitmap_set_bit, changed, EXECUTE_IF_SET_IN_BITMAP, first_or_preceding_vi_for_offset(), get_varinfo(), variable_info::head, i, variable_info::id, variable_info::is_artificial_var, variable_info::is_full_var, variable_info::is_unknown_size_var, variable_info::next, variable_info::offset, variable_info::size, solution_set_expand(), UNKNOWN_OFFSET, and vi_next().
Referenced by do_complex_constraint().
◆ shared_bitmap_add()
|
static |
Add a bitmap to the shared bitmap hashtable.
References bitmap_hash(), gcc_assert, shared_bitmap_info::hashcode, shared_bitmap_info::pt_vars, and shared_bitmap_table.
Referenced by find_what_var_points_to().
◆ shared_bitmap_lookup()
Lookup a bitmap in the shared bitmap hashtable, and return an already existing instance if there is one, NULL otherwise.
References bitmap_hash(), shared_bitmap_info::hashcode, NULL, shared_bitmap_info::pt_vars, and shared_bitmap_table.
Referenced by find_what_var_points_to().
◆ 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, get_varinfo(), variable_info::head, variable_info::is_artificial_var, variable_info::is_full_var, iteration_obstack, NULL, and 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, escaped_id, find(), and get_varinfo().
Referenced by do_ds_constraint(), and do_sd_constraint().
◆ solve_constraints()
|
static |
Solve the constraint set.
References bitmap_empty_p(), build_pred_graph(), build_succ_graph(), constraints, 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, unite_pointer_equivalences(), and varmap.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
◆ 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(), 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(), DEREF, do_complex_constraint(), hash_set< KeyId, Lazy, Traits >::elements(), eliminate_indirect_cycles(), escaped_id, EXECUTE_IF_IN_NONNULL_BITMAP, find(), gcc_assert, gcc_unreachable, get_varinfo(), i, iteration_obstack, constraint::lhs, NULL, oldpta_obstack, variable_info::oldsolution, pta_obstack, constraint::rhs, variable_info::solution, constraint_expr::type, and constraint_expr::var.
Referenced by solve_constraints().
◆ sort_fieldstack()
|
static |
Sort a fieldstack according to the field offset and sizes.
References fieldoff_compare().
Referenced by create_variable_info_for_1().
◆ 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().
◆ type_can_have_subvars()
|
inlinestatic |
Return true if T is a type that can have subvars.
References TREE_CODE.
Referenced by get_constraint_for_1(), and var_can_have_subvars().
◆ type_must_have_pointers()
Return true if T is a type that does contain pointers.
References FUNC_OR_METHOD_TYPE_P, POINTER_TYPE_P, TREE_CODE, TREE_TYPE, and type_must_have_pointers().
Referenced by field_must_have_pointers(), and type_must_have_pointers().
◆ 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, get_varinfo(), merge_graph_nodes(), merge_node_constraints(), variable_info::oldsolution, variable_info::solution, and TDF_DETAILS.
Referenced by eliminate_indirect_cycles(), find_equivalent_node(), scc_visit(), and unite_pointer_equivalences().
◆ 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 solve_constraints().
◆ var_can_have_subvars()
|
inlinestatic |
Return true if V is a tree that we can have subvars for. Normally, this is any aggregate type. Also complex types which are not gimple registers can have subvars.
References DECL_P, TREE_THIS_VOLATILE, TREE_TYPE, and type_can_have_subvars().
Referenced by create_variable_info_for_1(), and push_fields_onto_fieldstack().
◆ vi_next()
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 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().
◆ visit_loadstore()
Mark "other" loads and stores as belonging to CLIQUE and with base zero.
References bitmap_bit_p, bitmap_intersect_p(), build2(), build_fold_addr_expr, build_int_cst(), escaped_id, find(), gcc_assert, get_varinfo(), handled_component_p(), variable_info::id, is_global_var(), lookup_vi_for_tree(), MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, variable_info::solution, SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, TREE_CODE, TREE_OPERAND, TREE_TYPE, and VAR_P.
Referenced by compute_dependence_clique().
Variable Documentation
◆ call_stmt_vars
A map mapping call statements to per-stmt variables for uses and clobbers specific to the call.
Referenced by delete_points_to_sets(), get_call_vi(), init_alias_vars(), and lookup_call_use_vi().
◆ 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(), 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_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< T >::insert(), modref_tree< T >::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(), maybe_duplicate_computed_goto(), maybe_fold_tmr(), mention_regs(), modref_tree< T >::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()(), 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(), set_union_with_increment(), predicate::simplify(), simplify_comparison(), simplify_loop_version(), simplify_context::simplify_plus_minus(), simplify_using_outer_evolutions(), 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().
◆ constraint_pool
|
static |
Referenced by delete_points_to_sets(), and new_constraint().
◆ constraints
|
static |
List of constraints that we use to build the constraint graph from.
Referenced by asm_operand_ok(), assemble_asm(), build_pred_graph(), build_succ_graph(), check_asm_operands(), check_operand_nalternatives(), constrain_operands(), decode_asm_operands(), delete_points_to_sets(), do_deref(), dump_constraints(), expand_asm_loc(), expand_asm_stmt(), find_reloads(), init_alias_vars(), init_base_vars(), ipa_pta_execute(), lra_set_insn_recog_data(), lra_update_insn_recog_data(), maybe_fix_stack_asms(), move_complex_constraints(), parse_input_constraint(), preprocess_constraints(), preprocess_insn_constraints(), process_constraint(), record_operand_costs(), record_reg_classes(), reload_cse_simplify_operands(), rewrite_constraints(), single_reg_class(), solve_constraints(), and validate_pattern().
◆ equiv_class_obstack
| struct obstack equiv_class_obstack |
Referenced by equiv_class_lookup_or_add(), free_var_substitution_info(), and perform_var_substitution().
◆ fake_var_decl_obstack
| struct obstack fake_var_decl_obstack |
Temporary storage for fake var decls.
Referenced by build_fake_var_decl(), delete_points_to_sets(), and init_alias_vars().
◆ final_solutions
|
static |
Map varinfo to final pt_solution.
Referenced by delete_points_to_sets(), find_what_var_points_to(), init_alias_vars(), and ipa_pta_execute().
◆ final_solutions_obstack
| struct obstack final_solutions_obstack |
Referenced by delete_points_to_sets(), find_what_var_points_to(), init_alias_vars(), and ipa_pta_execute().
◆ graph
|
static |
Referenced by build_ssa_conflict_graph(), and coalesce_ssa_name().
◆ in_ipa_mode
|
static |
◆ ipa_escaped_pt
| struct pt_solution ipa_escaped_pt |
IPA PTA solutions for ESCAPED.
Referenced by ipa_pta_execute(), pt_solution_empty_p(), pt_solution_includes_1(), pt_solution_includes_const_pool(), pt_solution_includes_global(), and pt_solutions_intersect_1().
◆ 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().
◆ oldpta_obstack
|
static |
Used for oldsolution members of variables.
Referenced by init_alias_vars(), and solve_graph().
◆ 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_alias_vars(), label_visit(), and remove_preds_and_fake_succs().
◆ pt_solution_includes_may_alias
| unsigned HOST_WIDE_INT pt_solution_includes_may_alias |
◆ pt_solution_includes_no_alias
| unsigned HOST_WIDE_INT pt_solution_includes_no_alias |
◆ pt_solutions_intersect_may_alias
| unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias |
◆ pt_solutions_intersect_no_alias
| unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias |
◆ pta_obstack
|
static |
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().
◆ [struct]
| struct { ... } pta_stats |
Query statistics for points-to solutions.
Referenced by dump_pta_stats(), pt_solution_includes(), and pt_solutions_intersect().
◆ shared_bitmap_table
|
static |
Shared_bitmap hashtable.
Referenced by delete_points_to_sets(), init_alias_vars(), shared_bitmap_add(), and shared_bitmap_lookup().
◆ stats
|
static |
◆ use_field_sensitive
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/>.
The idea behind this analyzer is to generate set constraints from the
program, then solve the resulting constraints in order to generate the
points-to sets.
Set constraints are a way of modeling program analysis problems that
involve sets. They consist of an inclusion constraint language,
describing the variables (each variable is a set) and operations that
are involved on the variables, and a set of rules that derive facts
from these operations. To solve a system of set constraints, you derive
all possible facts under the rules, which gives you the correct sets
as a consequence.
See "Efficient Field-sensitive pointer analysis for C" by "David
J. Pearce and Paul H. J. Kelly and Chris Hankin", at
http://citeseer.ist.psu.edu/pearce04efficient.html
Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
of C Code in a Second" by "Nevin Heintze and Olivier Tardieu" at
http://citeseer.ist.psu.edu/heintze01ultrafast.html
There are three types of real constraint expressions, DEREF,
ADDRESSOF, and SCALAR. Each constraint expression consists
of a constraint type, a variable, and an offset.
SCALAR is a constraint expression type used to represent x, whether
it appears on the LHS or the RHS of a statement.
DEREF is a constraint expression type used to represent *x, whether
it appears on the LHS or the RHS of a statement.
ADDRESSOF is a constraint expression used to represent &x, whether
it appears on the LHS or the RHS of a statement.
Each pointer variable in the program is assigned an integer id, and
each field of a structure variable is assigned an integer id as well.
Structure variables are linked to their list of fields through a "next
field" in each variable that points to the next field in offset
order.
Each variable for a structure field has
1. "size", that tells the size in bits of that field.
2. "fullsize", that tells the size in bits of the entire structure.
3. "offset", that tells the offset in bits from the beginning of the
structure to this field.
Thus,
struct f
{
int a;
int b;
} foo;
int *bar;
looks like
foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
bar -> id 3, size 32, offset 0, fullsize 32, next NULL
In order to solve the system of set constraints, the following is
done:
1. Each constraint variable x has a solution set associated with it,
Sol(x).
2. Constraints are separated into direct, copy, and complex.
Direct constraints are ADDRESSOF constraints that require no extra
processing, such as P = &Q
Copy constraints are those of the form P = Q.
Complex constraints are all the constraints involving dereferences
and offsets (including offsetted copies).
3. All direct constraints of the form P = &Q are processed, such
that Q is added to Sol(P)
4. All complex constraints for a given constraint variable are stored in a
linked list attached to that variable's node.
5. A directed graph is built out of the copy constraints. Each
constraint variable is a node in the graph, and an edge from
Q to P is added for each copy constraint of the form P = Q
6. The graph is then walked, and solution sets are
propagated along the copy edges, such that an edge from Q to P
causes Sol(P) <- Sol(P) union Sol(Q).
7. As we visit each node, all complex constraints associated with
that node are processed by adding appropriate copy edges to the graph, or the
appropriate variables to the solution set.
8. The process of walking the graph is iterated until no solution
sets change.
Prior to walking the graph in steps 6 and 7, We perform static
cycle elimination on the constraint graph, as well
as off-line variable substitution.
TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
on and turned into anything), but isn't. You can just see what offset
inside the pointed-to struct it's going to access.
TODO: Constant bounded arrays can be handled as if they were structs of the
same number of elements.
TODO: Modeling heap and incoming pointers becomes much better if we
add fields to them as we discover them, which we could do.
TODO: We could handle unions, but to be honest, it's probably not
worth the pain or slowdown. IPA-PTA optimizations possible. When the indirect function called is ANYTHING we can add disambiguation based on the function signatures (or simply the parameter count which is the varinfo size). We also do not need to consider functions that do not have their address taken. The is_global_var bit which marks escape points is overly conservative in IPA mode. Split it to is_escape_point and is_global_var - only externally visible globals are escape points in IPA mode. There is now is_ipa_escape_point but this is only used in a few selected places. The way we introduce DECL_PT_UID to avoid fixing up all points-to sets in the translation unit when we copy a DECL during inlining pessimizes precision. The advantage is that the DECL_PT_UID keeps compile-time and memory usage overhead low - the points-to sets do not grow or get unshared as they would during a fixup phase. An alternative solution is to delay IPA PTA until after all inlining transformations have been applied. The way we propagate clobber/use information isn't optimized. It should use a new complex constraint that properly filters out local variables of the callee (though that would make the sets invalid after inlining). OTOH we might as well admit defeat to WHOPR and simply do all the clobber/use analysis and propagation after PTA finished but before we threw away points-to information for memory variables. WHOPR and PTA do not play along well anyway - the whole constraint solving would need to be done in WPA phase and it will be very interesting to apply the results to local SSA names during LTRANS phase. We probably should compute a per-function unit-ESCAPE solution propagating it simply like the clobber / uses solutions. The solution can go alongside the non-IPA escaped solution and be used to query which vars escape the unit through a function. This is also required to make the escaped-HEAP trick work in IPA mode. We never put function decls in points-to sets so we do not keep the set of called functions for indirect calls. And probably more.
Referenced by create_variable_info_for_1(), get_constraint_for_ptr_offset(), and init_alias_vars().
◆ variable_info_pool
|
static |
Pool of variable info structures.
Referenced by delete_points_to_sets(), and new_var_info().
◆ 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().
◆ vi_for_tree
Map from trees to variable infos.
Referenced by delete_points_to_sets(), get_vi_for_tree(), init_alias_vars(), insert_vi_for_tree(), and lookup_vi_for_tree().
