- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | constraint_stats |
| struct | variable_info |
| struct | constraint_expr |
| struct | constraint |
| struct | constraint_graph |
| struct | scc_info |
| struct | topo_info |
| struct | equiv_class_label |
| struct | equiv_class_hasher |
| struct | fieldoff |
| struct | shared_bitmap_info |
| struct | shared_bitmap_hasher |
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 struct equiv_class_label * | const_equiv_class_label_t |
| typedef struct fieldoff | fieldoff_s |
| typedef struct shared_bitmap_info * | shared_bitmap_info_t |
| typedef struct shared_bitmap_info * | const_shared_bitmap_info_t |
Enumerations | |
| enum | { nothing_id = 1, anything_id = 2, readonly_id = 3, escaped_id = 4, nonlocal_id = 5, storedanything_id = 6, integer_id = 7 } |
| 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 } |
| typedef struct constraint_expr ce_s |
| typedef struct equiv_class_label* const_equiv_class_label_t |
| typedef struct shared_bitmap_info* const_shared_bitmap_info_t |
| typedef struct constraint_graph* constraint_graph_t |
| typedef struct constraint* constraint_t |
| typedef struct equiv_class_label * equiv_class_label_t |
Structure used to for hash value numbering of pointer equivalence classes.
| typedef struct fieldoff fieldoff_s |
| 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.
| typedef struct variable_info* varinfo_t |
| 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).
| enum constraint_expr_type |
|
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_set_bit(), constraint_stats::num_edges, stats, and constraint_graph::succs.
Referenced by build_succ_graph(), do_ds_constraint(), and do_sd_constraint().
|
static |
Add an indirect graph edge to GRAPH, going from TO to FROM if it doesn't exist in the graph already.
References bitmap_set_bit(), constraint_graph::implicit_preds, constraint_stats::num_implicit_edges, and stats.
Referenced by build_pred_graph().
|
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_set_bit(), and constraint_graph::preds.
Referenced by build_pred_graph().
|
static |
Return a printable name for DECL
References dump_file, free(), and get_name().
Referenced by get_vi_for_tree(), and ipa_pta_execute().
|
static |
Associate node with varinfo DATA. Worker for cgraph_for_node_and_aliases.
References symtab_node_base::alias, symtab_node_base::analyzed, symtab_node_base::decl, insert_vi_for_tree(), cgraph_node::symbol, cgraph_node::thunk, and cgraph_thunk_info::thunk_p.
Referenced by ipa_pta_execute().
|
static |
Return the position, in bits, of FIELD_DECL from the beginning of its structure.
References host_integerp().
Referenced by push_fields_onto_fieldstack().
|
static |
Build a fake VAR_DECL acting as referrer to a DECL_UID.
References allocate_decl_uid(), fake_var_decl_obstack, layout_decl(), memset(), and type().
Referenced by create_function_info_for(), intra_create_variable_infos(), and make_heapvar().
|
static |
Build the constraint graph, adding only predecessor edges right now.
References add_implicit_graph_edge(), add_pred_graph_edge(), constraint_graph::address_taken, ADDRESSOF, anything_id, bitmap_clear(), bitmap_clear_bit(), bitmap_set_bit(), DEREF, constraint_graph::direct_nodes, constraint_graph::eq_rep, get_varinfo(), variable_info::head, variable_info::id, constraint_graph::implicit_preds, constraint_graph::indirect_cycles, variable_info::is_full_var, constraint::lhs, constraint_graph::loc_label, constraint_expr::offset, constraint_graph::pointed_by, constraint_graph::pointer_label, constraint_graph::points_to, constraint_graph::preds, constraint::rhs, sbitmap_alloc(), SCALAR, constraint_graph::size, constraint_expr::type, constraint_expr::var, and vi_next().
Referenced by solve_constraints().
|
static |
Build the constraint graph, adding successor edges.
References add_graph_edge(), ADDRESSOF, anything_id, bitmap_bit_p(), bitmap_set_bit(), DEREF, constraint_graph::direct_nodes, escaped_id, find(), get_varinfo(), integer_id, constraint::lhs, constraint_expr::offset, constraint::rhs, SCALAR, storedanything_id, constraint_expr::type, and constraint_expr::var.
Referenced by solve_constraints().
|
static |
Return true if FIELDSTACK contains fields that overlap. FIELDSTACK is assumed to be sorted by offset.
References HOST_WIDE_INT, and fieldoff::offset.
Referenced by create_variable_info_for_1().
|
static |
Remove edges involving NODE from GRAPH.
References constraint_graph::succs.
Referenced by merge_graph_nodes(), and perform_var_substitution().
| 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_points_to_sets(), delete_points_to_sets(), dump_alias_info(), dump_file, function::gimple_df, gimple_df::ipa_pta, and need_ssa_update_p().
Referenced by execute_function_todo().
|
static |
Create points-to sets for the current function. See the comments at the start of the file for an algorithmic overview.
References cfun, variable_info::decl, dump_constraints(), dump_file, pt_solution::escaped, gimple_df::escaped, escaped_id, find_func_aliases(), find_what_p_points_to(), find_what_var_points_to(), get_varinfo(), gimple_call_clobber_set(), gimple_call_flags(), gimple_call_use_set(), function::gimple_df, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), init_alias_vars(), intra_create_variable_infos(), is_gimple_call(), variable_info::is_global_var, variable_info::is_heap_var, lookup_call_clobber_vi(), lookup_call_use_vi(), memset(), pt_solution::nonlocal, pt_solution_includes(), solve_constraints(), timevar_pop(), timevar_push(), and virtual_operand_p().
Referenced by compute_may_aliases().
|
static |
Compute a topological ordering for GRAPH, and store the result in the topo_info structure TI.
References bitmap_bit_p(), find(), constraint_graph::size, topo_visit(), and topo_info::visited.
Referenced by solve_graph().
|
static |
Recursive routine to find strongly connected components in GRAPH, and label it's nodes with DFS numbers.
References bitmap_bit_p(), bitmap_clear_bit(), bitmap_ior_into(), bitmap_set_bit(), scc_info::current_index, scc_info::deleted, scc_info::dfs, constraint_graph::direct_nodes, constraint_graph::implicit_preds, scc_info::node_mapping, constraint_graph::points_to, constraint_graph::preds, scc_info::scc_stack, and scc_info::visited.
Referenced by perform_var_substitution().
|
static |
Return true if two constraints A and B are equal.
References constraint_expr_equal(), constraint::lhs, and constraint::rhs.
Referenced by constraint_vec_find(), and insert_into_complex().
|
static |
SOLVER FUNCTIONS
The solver is a simple worklist solver, that works on the following
algorithm:
sbitmap changed_nodes = all zeroes;
changed_count = 0;
For each node that is not already collapsed:
changed_count++;
set bit in changed nodes
while (changed_count > 0)
{
compute topological ordering for constraint graph
find and collapse cycles in the constraint graph (updating
changed if necessary)
for each node (n) in the graph in topological order:
changed_count--;
Process each complex constraint associated with the node,
updating changed if necessary.
For each outgoing edge from n, propagate the solution from n to
the destination of the edge, updating changed as necessary.
} Return true if two constraint expressions A and B are equal.
References constraint_expr::offset, constraint_expr::type, and constraint_expr::var.
Referenced by constraint_equal().
|
static |
Return true if constraint expression A is less than constraint expression B. This is just arbitrary, but consistent, in order to give them an ordering.
References constraint_expr::offset, constraint_expr::type, and constraint_expr::var.
Referenced by 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 constraint_expr_less(), constraint::lhs, and constraint::rhs.
Referenced by constraint_set_union(), constraint_vec_find(), and insert_into_complex().
|
static |
Union two constraint vectors, TO and FROM. Put the result in TO.
References constraint_less(), and constraint_vec_find().
Referenced by merge_node_constraints().
|
static |
Find a constraint LOOKFOR in the sorted constraint vector VEC
References constraint_equal(), and constraint_less().
Referenced by constraint_set_union().
|
static |
Count the number of arguments DECL has, and set IS_VARARGS to true if it is a varargs function.
Referenced by 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.
References build_fake_var_decl(), count_num_arguments(), variable_info::decl, function::decl, fi_clobbers, fi_parm_base, fi_result, fi_static_chain, fi_uses, free(), variable_info::fullsize, 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::may_have_pointers, new_var_info(), variable_info::next, variable_info::offset, variable_info::size, and function::static_chain_decl.
Referenced by ipa_pta_execute().
|
static |
Referenced by get_vi_for_tree().
|
static |
References create_variable_info_for_1(), symtab_node_base::definition, escaped_id, get_constraint_for_rhs(), variable_info::id, in_ipa_mode, insert_vi_for_tree(), variable_info::is_global_var, make_constraint_from_global_restrict(), make_copy_constraint(), variable_info::may_have_pointers, new_constraint(), nonlocal_id, constraint_expr::offset, variable_info::only_restrict_pointers, process_constraint(), SCALAR, varpool_node::symbol, constraint_expr::type, constraint_expr::var, varpool_all_refs_explicit_p(), varpool_get_node(), vi_next(), and vNULL.
|
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.
References check_for_overlaps(), dump_file, free(), variable_info::fullsize, fieldoff::has_unknown_size, variable_info::head, host_integerp(), HOST_WIDE_INT_PRINT_DEC, variable_info::id, in_ipa_mode, variable_info::is_full_var, is_global_var(), variable_info::is_unknown_size_var, variable_info::may_have_pointers, fieldoff::may_have_pointers, new_var_info(), variable_info::offset, fieldoff::offset, fieldoff::only_restrict_pointers, push_fields_onto_fieldstack(), variable_info::size, fieldoff::size, sort_fieldstack(), use_field_sensitive, var_can_have_subvars(), vi_next(), and vNULL.
Referenced by create_variable_info_for(), and intra_create_variable_infos().
| void debug_constraint | ( | constraint_t | ) |
| DEBUG_FUNCTION void debug_constraint | ( | ) |
Print out constraint C to stderr.
References dump_constraint().
| DEBUG_FUNCTION void debug_constraint_graph | ( | ) |
Print out the constraint graph to stderr.
References dump_constraint_graph().
| DEBUG_FUNCTION void debug_constraints | ( | ) |
Print out all constraints to stderr.
References dump_constraints().
| DEBUG_FUNCTION void debug_sa_points_to_info | ( | ) |
Debug points-to information to stderr.
References dump_sa_points_to_info().
| void debug_solution_for_var | ( | unsigned | int | ) |
| DEBUG_FUNCTION void debug_solution_for_var | ( | ) |
Print the points-to solution for VAR to stdout.
References dump_solution_for_var().
|
static |
Delete created points-to sets.
References bitmap_obstack_release(), constraint_graph::complex, hash_table< Descriptor, Allocator >::dispose(), dump_file, dump_flags, fake_var_decl_obstack, final_solutions_obstack, free(), free_alloc_pool(), constraint_graph::indirect_cycles, constraint_graph::pe, constraint_graph::pe_rep, pointer_map_destroy(), constraint_stats::points_to_sets_created, constraint_graph::rep, constraint_graph::size, stats, and constraint_graph::succs.
Referenced by compute_may_aliases(), and ipa_pta_execute().
|
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(), DEREF, do_ds_constraint(), do_sd_constraint(), 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().
Referenced by find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), and get_constraint_for_1().
|
static |
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, DEREF, new_constraint(), new_scalar_tmp_constraint_exp(), process_constraint(), SCALAR, constraint_expr::type, and constraint_expr::var.
|
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(), escaped_id, find(), first_vi_for_offset(), get_varinfo(), HOST_WIDE_INT, 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, variable_info::offset, constraint_expr::offset, constraint::rhs, variable_info::solution, solution_set_expand(), storedanything_id, constraint_expr::var, and vi_next().
Referenced by do_complex_constraint().
|
static |
Process a constraint C that represents x = *(y + off), using DELTA as the starting solution for y.
References add_graph_edge(), anything_id, bitmap_bit_p(), bitmap_ior_into(), bitmap_set_bit(), escaped_id, find(), first_vi_for_offset(), get_varinfo(), HOST_WIDE_INT, variable_info::id, variable_info::is_full_var, constraint::lhs, variable_info::may_have_pointers, variable_info::next, variable_info::offset, constraint_expr::offset, constraint::rhs, variable_info::solution, solution_set_expand(), constraint_expr::var, and vi_next().
Referenced by do_complex_constraint().
|
static |
Handle aggregate copies by expanding into copies of the respective fields of the structures.
References ADDRESSOF, anything_id, DEREF, get_constraint_for(), get_constraint_for_rhs(), get_ref_base_and_extent(), get_varinfo(), HOST_WIDE_INT, variable_info::is_full_var, variable_info::may_have_pointers, new_constraint(), variable_info::offset, constraint_expr::offset, process_all_all_constraints(), process_constraint(), ranges_overlap_p(), SCALAR, variable_info::size, constraint_expr::type, constraint_expr::var, and vNULL.
Referenced by find_func_aliases().
|
static |
Print out constraint C to FILE.
References ADDRESSOF, DEREF, get_varinfo(), HOST_WIDE_INT_PRINT_DEC, constraint::lhs, variable_info::name, constraint_expr::offset, constraint::rhs, constraint_expr::type, and constraint_expr::var.
Referenced by debug_constraint(), dump_constraint_graph(), dump_constraints(), and rewrite_constraints().
|
static |
Print the constraint graph in dot format.
References constraint_graph::complex, dump_constraint(), find(), get_varinfo(), constraint_graph::size, and constraint_graph::succs.
Referenced by debug_constraint_graph(), and solve_constraints().
|
static |
Print out all constraints to FILE
References dump_constraint().
Referenced by compute_points_to_sets(), debug_constraints(), and ipa_pta_execute().
|
static |
Print the pred graph in dot format.
References bitmap_empty_p(), get_varinfo(), scc_info::node_mapping, constraint_graph::points_to, constraint_graph::preds, and constraint_graph::size.
Referenced by perform_var_substitution().
| void dump_pta_stats | ( | ) |
References HOST_WIDE_INT_PRINT_DEC, and pta_stats.
|
static |
Dump points-to information to OUTFILE.
References dump_flags, dump_solution_for_var(), get_varinfo(), constraint_stats::iterations, variable_info::may_have_pointers, constraint_stats::nonpointer_vars, constraint_stats::num_edges, constraint_stats::num_implicit_edges, stats, constraint_stats::total_vars, constraint_stats::unified_vars_dynamic, and constraint_stats::unified_vars_static.
Referenced by debug_sa_points_to_info(), and solve_constraints().
|
static |
Print out the points-to solution for VAR to FILE.
References find(), get_varinfo(), variable_info::id, variable_info::name, and variable_info::solution.
Referenced by debug_solution_for_var(), and dump_sa_points_to_info().
|
static |
Eliminate indirect cycles involving NODE. Return true if NODE was part of an SCC, false otherwise.
References bitmap_empty_p(), find(), get_varinfo(), constraint_graph::indirect_cycles, queue, unify_nodes(), unite(), and vNULL.
Referenced by solve_graph().
|
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(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), equiv_class_label::hashcode, and equiv_class_label::labels.
Referenced by label_visit(), and perform_var_substitution().
|
static |
References type_must_have_pointers().
Referenced by push_fields_onto_fieldstack().
|
static |
qsort comparison function for two fieldoff's PA and PB
References HOST_WIDE_INT, fieldoff::offset, and fieldoff::size.
Referenced by sort_fieldstack().
|
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 constraint_graph::rep.
Referenced by build_succ_graph(), compute_topo_order(), count_occurrences(), do_ds_constraint(), do_sd_constraint(), dump_constraint_graph(), dump_solution_for_var(), eliminate_indirect_cycles(), find_indirect_cycles(), find_what_var_points_to(), has_mem_ref_been_instrumented(), ipa_pta_execute(), merge_node_constraints(), rewrite_constraints(), scc_visit(), solve_graph(), unify_nodes(), and unite_pointer_equivalences().
|
static |
Return an existing node that is equivalent to NODE, which has equivalence class LABEL, if one exists. Return NODE otherwise.
References constraint_graph::address_taken, bitmap_bit_p(), constraint_graph::eq_rep, constraint_graph::pe, constraint_graph::pe_rep, unify_nodes(), and unite().
Referenced by rewrite_constraints().
|
static |
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 cfun, function::decl, do_structure_copy(), fi_result, find_func_aliases_for_call(), get_base_address(), get_constraint_for(), 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_expr_type(), gimple_num_ops(), gimple_op(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), gimple_return_retval(), in_ipa_mode, is_gimple_assign(), is_gimple_call(), is_global_var(), make_escape_constraint(), new_constraint(), nonlocal_id, constraint_expr::offset, parse_input_constraint(), parse_output_constraint(), process_all_all_constraints(), process_constraint(), SCALAR, truth_value_p(), constraint_expr::type, constraint_expr::var, and vNULL.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
|
static |
Create constraints for the builtin call T. Return true if the call was handled, otherwise false.
References ADDRESSOF, anything_id, BUILT_IN_NORMAL, cfun, function::decl, do_deref(), escaped_id, fi_result, fi_static_chain, get_call_clobber_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_flags(), gimple_call_fndecl(), gimple_call_lhs(), handle_lhs_call(), in_ipa_mode, integer_id, integer_zerop(), lookup_vi_for_tree(), make_constraint_from(), make_constraint_to(), new_constraint(), nonlocal_id, nothing_id, constraint_expr::offset, process_all_all_constraints(), process_constraint(), SCALAR, constraint_expr::type, constraint_expr::var, and vNULL.
Referenced by find_func_aliases_for_call().
|
static |
Create constraints for the call T.
References do_deref(), fi_parm_base, fi_result, fi_static_chain, find_func_aliases_for_builtin_call(), get_constraint_for(), get_constraint_for_address_of(), get_constraint_for_rhs(), get_fi_for_callee(), get_function_part_constraint(), gimple_call_arg(), gimple_call_chain(), gimple_call_flags(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_num_args(), handle_const_call(), handle_lhs_call(), handle_pure_call(), handle_rhs_call(), in_ipa_mode, variable_info::is_fn_info, new_constraint(), process_constraint(), and vNULL.
Referenced by find_func_aliases().
|
static |
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, auto_var_in_fn_p(), BUILT_IN_NORMAL, cfun, function::decl, escaped_id, fi_clobbers, fi_uses, first_vi_for_offset(), get_constraint_for_address_of(), get_constraint_for_ptr_offset(), get_fi_for_callee(), get_function_part_constraint(), 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(), variable_info::id, in_ipa_mode, variable_info::is_fn_info, is_gimple_call(), is_gimple_min_invariant(), lookup_call_clobber_vi(), lookup_call_use_vi(), lookup_vi_for_tree(), make_constraint_from(), make_copy_constraint(), new_constraint(), process_constraint(), process_ipa_clobber(), and vNULL.
Referenced by ipa_pta_execute().
|
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(), free_scc_info(), init_scc_info(), scc_visit(), si, constraint_graph::size, and scc_info::visited.
Referenced by solve_constraints().
|
static |
Given a pointer variable P, fill in its points-to set.
References find_what_var_points_to(), get_ptr_info(), lookup_vi_for_tree(), and ptr_info_def::pt.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
|
staticread |
Compute the points-to solution *PT for the variable VI.
References anything_id, bitmap_clear(), escaped_id, final_solutions_obstack, find(), get_varinfo(), variable_info::id, in_ipa_mode, integer_id, variable_info::is_artificial_var, variable_info::is_heap_var, memset(), nonlocal_id, nothing_id, pointer_map_insert(), constraint_stats::points_to_sets_created, readonly_id, set_uids_in_ptset(), shared_bitmap_add(), shared_bitmap_lookup(), and stats.
Referenced by compute_points_to_sets(), find_what_p_points_to(), and ipa_pta_execute().
|
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(), variable_info::head, variable_info::next, variable_info::offset, variable_info::size, and vi_next().
Referenced by get_constraint_for_ptr_offset(), and set_union_with_increment().
Referenced by do_ds_constraint(), do_sd_constraint(), find_func_clobbers(), get_function_part_constraint(), and ipa_pta_execute().
|
static |
Find the first varinfo in the same variable as START that overlaps with OFFSET. Return NULL if we can't find one.
References variable_info::fullsize, get_varinfo(), variable_info::head, variable_info::offset, variable_info::size, and vi_next().
|
static |
Free an SCC info structure pointed to by SI
References scc_info::deleted, scc_info::dfs, free(), scc_info::node_mapping, sbitmap_free(), scc_info::scc_stack, and scc_info::visited.
Referenced by find_indirect_cycles(), and free_var_substitution_info().
|
static |
Free the topological sort info pointed to by TI.
References free(), sbitmap_free(), topo_info::topo_order, and topo_info::visited.
Referenced by solve_graph().
|
static |
Free information that was only necessary for variable substitution.
References bitmap_obstack_release(), constraint_graph::direct_nodes, hash_table< Descriptor, Allocator >::dispose(), constraint_graph::eq_rep, free(), free_scc_info(), constraint_graph::loc_label, constraint_graph::pointed_by, constraint_graph::pointer_label, constraint_graph::points_to, and sbitmap_free().
Referenced by solve_constraints().
|
static |
Return true if we should execute IPA PTA.
References seen_error().
|
static |
|
static |
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_rhs_call().
|
static |
Lookup or create the variable for the call statement CALL representing the uses.
References get_call_vi().
Referenced by handle_const_call(), handle_pure_call(), and handle_rhs_call().
|
static |
Lookup or create the variable for the call statement CALL.
References variable_info::fullsize, variable_info::id, variable_info::is_full_var, new_var_info(), variable_info::next, variable_info::offset, pointer_map_insert(), and variable_info::size.
Referenced by get_call_clobber_vi(), and get_call_use_vi().
|
static |
Given a gimple tree T, return the constraint expression vector for it.
References get_constraint_for_1().
|
static |
Given a tree T, return the constraint expression for it.
References ADDRESSOF, anything_id, DEREF, do_deref(), get_constraint_for_address_of(), get_constraint_for_component_ref(), get_constraint_for_ptr_offset(), get_constraint_for_ssa_var(), get_varinfo(), host_integerp(), HOST_WIDE_INT, integer_zerop(), nonlocal_id, nothing_id, constraint_expr::offset, readonly_id, SCALAR, tcc_constant, tcc_declaration, tcc_exceptional, tcc_expression, tcc_reference, constraint_expr::type, type_can_have_subvars(), constraint_expr::var, vi_next(), and vNULL.
Referenced by get_constraint_for(), get_constraint_for_address_of(), get_constraint_for_component_ref(), and get_constraint_for_rhs().
|
static |
Given a tree T, return the constraint expression for taking the address of it.
References ADDRESSOF, DEREF, get_constraint_for_1(), SCALAR, and constraint_expr::type.
Referenced by find_func_aliases_for_call(), find_func_clobbers(), get_constraint_for_1(), and handle_rhs_call().
|
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 ADDRESSOF, anything_id, DEREF, dump_file, dump_flags, variable_info::fullsize, get_constraint_for_1(), get_ref_base_and_extent(), get_varinfo(), handled_component_p(), HOST_WIDE_INT, variable_info::id, integer_id, integer_zerop(), variable_info::is_full_var, variable_info::next, variable_info::offset, constraint_expr::offset, ranges_overlap_p(), SCALAR, variable_info::size, constraint_expr::type, constraint_expr::var, and vi_next().
Referenced by get_constraint_for_1().
Get constraint expressions for offsetting PTR by OFFSET. Stores the resulting constraint expressions in *RESULTS.
References ADDRESSOF, first_or_preceding_vi_for_offset(), double_int::fits_shwi(), get_constraint_for_rhs(), get_varinfo(), variable_info::head, HOST_WIDE_INT, variable_info::id, variable_info::is_full_var, double_int::low, variable_info::next, variable_info::offset, constraint_expr::offset, double_int::sext(), tree_to_double_int(), constraint_expr::type, 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().
|
static |
Given a gimple tree T, return the constraint expression vector for it to be used as the rhs of a constraint.
References get_constraint_for_1().
|
static |
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 ADDRESSOF, symtab_node_base::alias, symtab_node_base::analyzed, anything_id, symtab_node_base::decl, get_vi_for_tree(), constraint_expr::offset, readonly_id, SCALAR, varpool_node::symbol, constraint_expr::type, constraint_expr::var, varpool_get_node(), varpool_variable_node(), and vi_next().
Referenced by get_constraint_for_1().
|
static |
Return the varinfo for the callee of CALL.
References anything_id, get_varinfo(), get_vi_for_tree(), gimple_call_addr_fndecl(), and gimple_call_fn().
Referenced by find_func_aliases_for_call(), find_func_clobbers(), and ipa_pta_execute().
|
staticread |
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(), variable_info::id, in_ipa_mode, constraint_expr::offset, SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by find_func_aliases(), find_func_aliases_for_builtin_call(), find_func_aliases_for_call(), find_func_clobbers(), and process_ipa_clobber().
|
inlinestatic |
Return the varmap element N
Referenced by build_pred_graph(), build_succ_graph(), compute_points_to_sets(), 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(), 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_graph(), unify_nodes(), and vi_next().
|
static |
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(), and pointer_map_contains().
Referenced by find_func_aliases(), find_func_aliases_for_builtin_call(), get_constraint_for_ssa_var(), get_fi_for_callee(), intra_create_variable_infos(), and ipa_pta_execute().
|
static |
For non-IPA mode, generate constraints necessary for a call of a const function that returns a pointer in the statement STMT.
References ADDRESSOF, get_call_use_vi(), get_constraint_for_rhs(), gimple_call_arg(), gimple_call_chain(), gimple_call_num_args(), variable_info::id, make_constraint_to(), make_transitive_closure_constraints(), nonlocal_id, constraint_expr::offset, SCALAR, constraint_expr::type, constraint_expr::var, and vNULL.
Referenced by find_func_aliases_for_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, escaped_id, get_base_address(), get_constraint_for(), gimple_call_arg(), gimple_call_num_args(), gimple_call_return_flags(), variable_info::id, variable_info::is_global_var, is_global_var(), make_constraint_from(), make_heapvar(), nonlocal_id, constraint_expr::offset, process_all_all_constraints(), SCALAR, constraint_expr::type, constraint_expr::var, and vNULL.
Referenced by find_func_aliases_for_builtin_call(), and find_func_aliases_for_call().
|
static |
For non-IPA mode, generate constraints necessary for a call to a pure function in statement STMT.
References get_call_use_vi(), gimple_call_arg(), gimple_call_chain(), gimple_call_num_args(), variable_info::id, make_constraint_to(), make_transitive_closure_constraints(), nonlocal_id, constraint_expr::offset, SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by find_func_aliases_for_call().
|
static |
For non-IPA mode, generate constraints necessary for a call on the RHS.
References DEREF, escaped_id, get_call_clobber_vi(), 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_return_slot_opt_p(), variable_info::id, make_constraint_to(), make_copy_constraint(), make_escape_constraint(), make_transitive_closure_constraints(), new_constraint(), new_var_info(), nonlocal_id, constraint_expr::offset, process_constraint(), SCALAR, constraint_expr::type, constraint_expr::var, and vNULL.
Referenced by find_func_aliases_for_call().
|
static |
Initialize things necessary to perform PTA
References bitmap_obstack_initialize(), hash_table< Descriptor, Allocator >::create(), create_alloc_pool(), fake_var_decl_obstack, final_solutions_obstack, init_base_vars(), memset(), pointer_map_create(), stats, and use_field_sensitive.
Referenced by compute_points_to_sets(), and ipa_pta_execute().
|
static |
Initialize the always-existing constraint variables for NULL ANYTHING, READONLY, and INTEGER
References ADDRESSOF, anything_id, DEREF, escaped_id, variable_info::fullsize, 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, variable_info::offset, constraint_expr::offset, process_constraint(), readonly_id, SCALAR, variable_info::size, storedanything_id, constraint_expr::type, and constraint_expr::var.
Referenced by init_alias_vars().
|
static |
Initialize the constraint graph structure to contain SIZE nodes.
References constraint_graph::complex, constraint_graph::indirect_cycles, constraint_graph::pe, constraint_graph::pe_rep, constraint_graph::rep, constraint_graph::size, and constraint_graph::succs.
Referenced by solve_constraints().
|
staticread |
Initialize and return a new SCC info structure.
References bitmap_clear(), scc_info::current_index, scc_info::deleted, scc_info::dfs, scc_info::node_mapping, sbitmap_alloc(), scc_info::scc_stack, si, and scc_info::visited.
Referenced by find_indirect_cycles(), and perform_var_substitution().
|
staticread |
Initialize and return a topological info structure.
References bitmap_clear(), sbitmap_alloc(), constraint_graph::size, topo_info::topo_order, and topo_info::visited.
Referenced by solve_graph().
|
static |
Insert constraint C into the list of complex constraints for graph node VAR.
References constraint_graph::complex, constraint_equal(), and constraint_less().
Referenced by move_complex_constraints().
|
static |
Insert ID as the variable id for tree T in the vi_for_tree map.
References pointer_map_insert().
Referenced by associate_varinfo_to_alias(), create_function_info_for(), create_variable_info_for(), intra_create_variable_infos(), and make_heapvar().
|
static |
Create varinfo structures for all of the variables in the function for intraprocedural mode.
References ADDRESSOF, build_fake_var_decl(), cfun, create_variable_info_for_1(), current_function_decl, function::decl, get_vi_for_tree(), variable_info::id, insert_vi_for_tree(), make_constraint_from(), make_constraint_from_global_restrict(), make_copy_constraint(), variable_info::may_have_pointers, new_constraint(), nonlocal_id, constraint_expr::offset, variable_info::only_restrict_pointers, process_constraint(), SCALAR, function::static_chain_decl, constraint_expr::type, type_contains_placeholder_p(), constraint_expr::var, and vi_next().
Referenced by compute_points_to_sets(), and ipa_pta_execute().
|
static |
Execute the driver for IPA PTA.
References symtab_node_base::alias, alias_get_name(), symtab_node_base::analyzed, pt_solution::anything, anything_id, associate_varinfo_to_alias(), bitmap_bit_p(), cgraph_edge::call_stmt, cgraph_node::callers, cgraph_for_node_and_aliases(), cgraph_function_with_gimple_body_p(), cgraph_get_body(), cgraph_node_name(), cgraph_node::clone_of, create_function_info_for(), symtab_node_base::decl, delete_points_to_sets(), dump_constraints(), dump_file, dump_flags, dump_symtab(), escaped_id, symtab_node_base::externally_visible, fi_clobbers, fi_result, fi_uses, find(), find_func_aliases(), find_func_clobbers(), find_what_p_points_to(), find_what_var_points_to(), first_vi_for_offset(), symtab_node_base::force_output, get_fi_for_callee(), get_varinfo(), get_vi_for_tree(), 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(), variable_info::id, in_ipa_mode, init_alias_vars(), intra_create_variable_infos(), pt_solution::ipa_escaped, ipa_escaped_pt, gimple_df::ipa_pta, variable_info::is_fn_info, is_gimple_call(), lookup_call_clobber_vi(), lookup_call_use_vi(), lookup_vi_for_tree(), memset(), new_constraint(), cgraph_edge::next_caller, pt_solution::nonlocal, nonlocal_id, variable_info::offset, constraint_expr::offset, pop_cfun(), process_constraint(), pt_solution_ior_into(), pt_solution_reset(), push_cfun(), SCALAR, variable_info::solution, solve_constraints(), gimple_df::ssa_names, cgraph_node::symbol, varpool_node::symbol, constraint_expr::type, symtab_node_base::used_from_other_partition, constraint_expr::var, and virtual_operand_p().
|
static |
Label pointer equivalences.
References bitmap_bit_p(), bitmap_copy(), bitmap_empty_p(), bitmap_ior(), bitmap_ior_into(), bitmap_set_bit(), constraint_graph::direct_nodes, equiv_class_lookup_or_add(), equiv_class_label::equivalence_class, equiv_class_label::labels, scc_info::node_mapping, pointer_equiv_class, constraint_graph::pointer_label, constraint_graph::points_to, constraint_graph::preds, and scc_info::visited.
Referenced by perform_var_substitution().
|
static |
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(), and vi_next().
Referenced by compute_points_to_sets(), find_func_clobbers(), and ipa_pta_execute().
|
static |
Lookup the variable for the call statement CALL representing the uses. Returns NULL if there is nothing special about this call.
References pointer_map_contains().
Referenced by compute_points_to_sets(), find_func_clobbers(), ipa_pta_execute(), and lookup_call_clobber_vi().
Referenced by find_func_aliases_for_builtin_call(), find_func_clobbers(), find_what_p_points_to(), and ipa_pta_execute().
|
static |
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 pointer_map_contains().
|
static |
Create a constraint ID = &FROM.
References ADDRESSOF, variable_info::id, new_constraint(), constraint_expr::offset, process_constraint(), SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by find_func_aliases_for_builtin_call(), find_func_clobbers(), handle_lhs_call(), intra_create_variable_infos(), and 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 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(), and intra_create_variable_infos().
|
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, make_constraint_from(), make_heapvar(), and variable_info::may_have_pointers.
Referenced by make_constraint_from_global_restrict().
|
static |
Create a constraint ID = OP.
References get_constraint_for_rhs(), make_constraints_to(), and vNULL.
Referenced by find_func_aliases_for_builtin_call(), handle_const_call(), handle_pure_call(), handle_rhs_call(), and make_escape_constraint().
|
static |
Create constraints ID = { rhsc }.
References new_constraint(), constraint_expr::offset, process_constraint(), SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by make_constraint_to().
|
static |
Create a constraint ID = FROM.
References variable_info::id, new_constraint(), constraint_expr::offset, process_constraint(), SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by create_variable_info_for(), find_func_clobbers(), handle_rhs_call(), intra_create_variable_infos(), and make_constraint_from_global_restrict().
|
static |
Make constraints necessary to make OP escape.
References escaped_id, and make_constraint_to().
Referenced by find_func_aliases(), and handle_rhs_call().
|
static |
Create a new artificial heap variable with NAME. Return the created variable.
References build_fake_var_decl(), variable_info::fullsize, insert_vi_for_tree(), variable_info::is_artificial_var, variable_info::is_full_var, variable_info::is_heap_var, variable_info::is_unknown_size_var, new_var_info(), variable_info::offset, and variable_info::size.
Referenced by handle_lhs_call(), and make_constraint_from_restrict().
| gimple_opt_pass* make_pass_build_alias | ( | ) |
| gimple_opt_pass* make_pass_build_ealias | ( | ) |
| simple_ipa_opt_pass* make_pass_ipa_pta | ( | ) |
|
static |
Add constraints to that the solution of VI is transitively closed.
References DEREF, variable_info::id, new_constraint(), constraint_expr::offset, process_constraint(), SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by handle_const_call(), handle_pure_call(), and handle_rhs_call().
|
static |
Merge GRAPH nodes FROM and TO into node TO.
References bitmap_ior_into(), clear_edges_for_node(), constraint_graph::indirect_cycles, and constraint_graph::succs.
Referenced by unify_nodes().
|
static |
Condense two variable nodes into a single variable node, by moving all associated info from SRC to TO.
References constraint_graph::complex, constraint_set_union(), DEREF, find(), constraint::lhs, constraint::rhs, constraint_expr::type, and constraint_expr::var.
Referenced by unify_nodes().
|
static |
Move complex constraints to the GRAPH nodes they belong to.
References ADDRESSOF, anything_id, DEREF, get_varinfo(), insert_into_complex(), variable_info::is_special_var, constraint::lhs, constraint_expr::offset, constraint::rhs, constraint_expr::type, and constraint_expr::var.
Referenced by solve_constraints().
|
static |
Create a new constraint consisting of LHS and RHS expressions.
References constraint::lhs, pool_alloc(), 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_clobbers(), handle_rhs_call(), init_base_vars(), intra_create_variable_infos(), ipa_pta_execute(), make_constraint_from(), make_constraints_to(), make_copy_constraint(), make_transitive_closure_constraints(), process_all_all_constraints(), process_constraint(), and process_ipa_clobber().
|
staticread |
Get a scalar constraint expression for a new temporary variable.
References new_var_info(), constraint_expr::offset, SCALAR, constraint_expr::type, and constraint_expr::var.
Referenced by do_deref(), process_all_all_constraints(), and process_constraint().
|
static |
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::decl, variable_info::head, variable_info::id, variable_info::is_artificial_var, variable_info::is_fn_info, variable_info::is_full_var, variable_info::is_global_var, is_global_var(), variable_info::is_heap_var, variable_info::is_special_var, variable_info::is_unknown_size_var, variable_info::may_have_pointers, variable_info::name, variable_info::next, variable_info::oldsolution, variable_info::only_restrict_pointers, pool_alloc(), variable_info::solution, stats, and constraint_stats::total_vars.
Referenced by create_function_info_for(), create_variable_info_for_1(), get_call_vi(), handle_rhs_call(), init_base_vars(), make_heapvar(), and new_scalar_tmp_constraint_exp().
|
staticread |
Perform offline variable substitution, discovering equivalence classes, and eliminating non-pointer variables.
References bitmap_bit_p(), bitmap_clear(), bitmap_obstack_initialize(), bitmap_set_bit(), clear_edges_for_node(), condense_visit(), hash_table< Descriptor, Allocator >::create(), constraint_graph::direct_nodes, dump_file, dump_flags, dump_pred_graph(), equiv_class_lookup_or_add(), equiv_class_label::equivalence_class, get_varinfo(), init_scc_info(), label_visit(), constraint_graph::loc_label, location_equiv_class, scc_info::node_mapping, constraint_stats::nonpointer_vars, constraint_graph::pointed_by, pointer_equiv_class, constraint_graph::pointer_label, si, constraint_graph::size, stats, and scc_info::visited.
Referenced by solve_constraints().
Efficiently generates constraints from all entries in *RHSC to all entries in *LHSC.
References 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().
|
static |
Process constraint T, performing various simplifications and then adding it to our list of overall constraints.
References ADDRESSOF, anything_id, DEREF, get_varinfo(), constraint::lhs, variable_info::may_have_pointers, new_constraint(), new_scalar_tmp_constraint_exp(), constraint_expr::offset, constraint::rhs, constraint_expr::type, and constraint_expr::var.
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_clobbers(), handle_rhs_call(), init_base_vars(), intra_create_variable_infos(), ipa_pta_execute(), make_constraint_from(), make_constraints_to(), make_copy_constraint(), make_transitive_closure_constraints(), process_all_all_constraints(), and process_ipa_clobber().
|
static |
Create a constraint adding to the clobber set of FI the memory pointed to by PTR.
References fi_clobbers, get_constraint_for_rhs(), get_function_part_constraint(), new_constraint(), process_constraint(), and vNULL.
Referenced by find_func_clobbers().
| bool pt_solution_empty_p | ( | ) |
Return true if the points-to solution *PT is empty.
References pt_solution::anything, bitmap_empty_p(), cfun, pt_solution::escaped, gimple_df::escaped, function::gimple_df, pt_solution::ipa_escaped, ipa_escaped_pt, pt_solution::nonlocal, pt_solution_empty_p(), and pt_solution::vars.
| bool pt_solution_includes | ( | ) |
References pt_solution_includes_1(), and pta_stats.
|
static |
Return true if the points-to solution *PT includes the variable declaration DECL.
References pt_solution::anything, bitmap_bit_p(), cfun, pt_solution::escaped, gimple_df::escaped, function::gimple_df, pt_solution::ipa_escaped, ipa_escaped_pt, is_global_var(), pt_solution::nonlocal, and pt_solution::vars.
Referenced by pt_solution_includes().
| bool pt_solution_includes_global | ( | ) |
Return true if the points-to solution *PT includes global memory.
References pt_solution::anything, cfun, pt_solution::escaped, gimple_df::escaped, function::gimple_df, pt_solution::ipa_escaped, ipa_escaped_pt, gimple_df::ipa_pta, pt_solution::nonlocal, pt_solution_includes_global(), and pt_solution::vars_contains_global.
|
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_ior_into(), pt_solution::escaped, pt_solution::ipa_escaped, pt_solution::nonlocal, pt_solution::null, pt_solution_reset(), pt_solution::vars, and pt_solution::vars_contains_global.
Referenced by ipa_pta_execute().
| void pt_solution_reset | ( | ) |
Reset the points-to solution *PT to a conservative default (point to anything).
References pt_solution::anything, and memset().
| void pt_solution_set | ( | ) |
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 memset(), pt_solution::vars, and pt_solution::vars_contains_global.
| void pt_solution_set_var | ( | ) |
Set the points-to solution *PT to point only to the variable VAR.
References bitmap_set_bit(), is_global_var(), memset(), pt_solution::vars, and pt_solution::vars_contains_global.
| bool pt_solution_singleton_p | ( | ) |
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, pt_solution::null, and pt_solution::vars.
| bool pt_solutions_intersect | ( | ) |
References pt_solutions_intersect_1(), and pta_stats.
|
static |
Return true if both points-to solutions PT1 and PT2 have a non-empty intersection.
References pt_solution::anything, bitmap_intersect_p(), cfun, pt_solution::escaped, gimple_df::escaped, function::gimple_df, pt_solution::ipa_escaped, ipa_escaped_pt, pt_solution::nonlocal, pt_solution_empty_p(), pt_solution::vars, and pt_solution::vars_contains_global.
Referenced by pt_solutions_intersect().
|
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(), field_must_have_pointers(), fieldoff::has_unknown_size, host_integerp(), HOST_WIDE_INT, integer_zerop(), fieldoff::may_have_pointers, fieldoff::must_have_pointers, fieldoff::offset, fieldoff::only_restrict_pointers, fieldoff::size, and var_can_have_subvars().
Referenced by create_variable_info_for_1().
|
static |
Remove the REF and ADDRESS edges from GRAPH, as well as all the predecessor edges.
References bitmap_clear_range(), bitmap_obstack_release(), free(), constraint_graph::implicit_preds, constraint_graph::preds, constraint_graph::size, and constraint_graph::succs.
Referenced by solve_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 dump_constraint(), dump_file, dump_flags, find(), find_equivalent_node(), get_varinfo(), constraint::lhs, variable_info::name, scc_info::node_mapping, constraint_graph::pointer_label, constraint::rhs, constraint_graph::size, and constraint_expr::var.
Referenced by solve_constraints().
|
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_bit_p(), bitmap_first_set_bit(), bitmap_set_bit(), scc_info::current_index, scc_info::deleted, scc_info::dfs, find(), constraint_graph::indirect_cycles, scc_info::scc_stack, constraint_graph::succs, unify_nodes(), unite(), and scc_info::visited.
Referenced by find_indirect_cycles().
|
static |
Set bits in INTO corresponding to the variable uids in solution set FROM.
References bitmap_set_bit(), variable_info::decl, get_varinfo(), in_ipa_mode, variable_info::is_artificial_var, variable_info::is_global_var, variable_info::is_heap_var, and pt_solution::vars_contains_global.
Referenced by find_what_var_points_to().
|
static |
Union solution sets TO and FROM, and add INC to each member of FROM in the process.
References anything_id, bitmap_bit_p(), bitmap_copy(), bitmap_ior_into(), bitmap_set_bit(), changed, first_or_preceding_vi_for_offset(), get_varinfo(), HOST_WIDE_INT, 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, and solution_set_expand().
Referenced by do_complex_constraint().
|
static |
Add a bitmap to the shared bitmap hashtable.
References bitmap_hash(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), shared_bitmap_info::hashcode, and shared_bitmap_info::pt_vars.
Referenced by find_what_var_points_to().
|
static |
Lookup a bitmap in the shared bitmap hashtable, and return an already existing instance if there is one, NULL otherwise.
References bitmap_hash(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), shared_bitmap_info::hashcode, and shared_bitmap_info::pt_vars.
Referenced by find_what_var_points_to().
|
static |
Expands the solution in SET to all sub-fields of variables included.
References bitmap_set_bit(), get_varinfo(), variable_info::head, variable_info::id, variable_info::is_artificial_var, variable_info::is_full_var, and vi_next().
Referenced by do_ds_constraint(), do_sd_constraint(), and set_union_with_increment().
|
static |
Solve the constraint set.
References build_pred_graph(), build_succ_graph(), dump_constraint_graph(), dump_file, dump_flags, dump_sa_points_to_info(), find_indirect_cycles(), free_var_substitution_info(), init_graph(), move_complex_constraints(), perform_var_substitution(), remove_preds_and_fake_succs(), rewrite_constraints(), si, solve_graph(), and unite_pointer_equivalences().
Referenced by compute_points_to_sets(), and ipa_pta_execute().
|
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 anything_id, bitmap_and_compl(), bitmap_bit_p(), bitmap_clear_bit(), bitmap_copy(), bitmap_empty_p(), bitmap_ior_into(), bitmap_obstack_initialize(), bitmap_obstack_release(), bitmap_set_bit(), constraint_graph::complex, compute_topo_order(), DEREF, do_complex_constraint(), eliminate_indirect_cycles(), escaped_id, find(), free_topo_info(), get_varinfo(), init_topo_info(), constraint_stats::iterations, constraint::lhs, variable_info::oldsolution, constraint::rhs, constraint_graph::size, variable_info::solution, stats, constraint_graph::succs, topo_info::topo_order, constraint_expr::type, and constraint_expr::var.
Referenced by solve_constraints().
|
static |
Sort a fieldstack according to the field offset and sizes.
References fieldoff_compare().
Referenced by create_variable_info_for_1().
|
static |
Visit the graph in topological order, and store the order in the topo_info structure.
References bitmap_bit_p(), bitmap_set_bit(), constraint_graph::succs, topo_info::topo_order, and topo_info::visited.
Referenced by compute_topo_order().
|
inlinestatic |
Referenced by get_constraint_for_1(), and var_can_have_subvars().
|
inlinestatic |
Return true if T is a type that can have subvars.
|
static |
Return true if T is a type that does contain pointers.
Referenced by field_must_have_pointers().
|
static |
Unify node FROM into node TO, updating the changed count if necessary when UPDATE_CHANGED is true.
References bitmap_clear_bit(), bitmap_ior_into(), bitmap_set_bit(), dump_file, dump_flags, find(), get_varinfo(), constraint_stats::iterations, merge_graph_nodes(), merge_node_constraints(), variable_info::oldsolution, variable_info::solution, stats, constraint_graph::succs, constraint_stats::unified_vars_dynamic, and constraint_stats::unified_vars_static.
Referenced by eliminate_indirect_cycles(), find_equivalent_node(), scc_visit(), and unite_pointer_equivalences().
|
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 constraint_graph::rep.
Referenced by eliminate_indirect_cycles(), find_equivalent_node(), scc_visit(), and 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(), constraint_graph::pe, constraint_graph::pe_rep, unify_nodes(), and unite().
Referenced by solve_constraints().
|
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 type_can_have_subvars().
Referenced by create_variable_info_for_1(), and push_fields_onto_fieldstack().
|
inlinestatic |
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(), lookup_call_clobber_vi(), and solution_set_expand().
|
static |
A map mapping call statements to per-stmt variables for uses and clobbers specific to the call.
|
static |
Changed variables on the last iteration.
Referenced by add_scope_conflicts(), analyze_functions(), associate_plusminus(), 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_and_compl(), bitmap_ior_and_compl_into(), bitmap_ior_and_into(), bitmap_ior_into(), bitmap_or_and(), bitmap_xor(), bypass_conditional_jumps(), canonicalize_induction_variables(), ccp_fold_stmt(), cgraph_propagate_frequency(), cleanup_all_empty_eh(), cleanup_cfg(), cleanup_subreg_operands(), cleanup_tree_cfg(), cleanup_tree_cfg_noloop(), combine_cond_exprs(), compute_antic(), compute_antic_aux(), compute_bb_dataflow(), compute_code_hoist_vbeinout(), compute_out(), compute_partial_antic_aux(), copyprop_hardreg_forward_1(), cprop_insn(), cse_extended_basic_block(), dataflow_set_preserve_mem_locs(), dataflow_set_remove_mem_locs(), 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(), drop_overlapping_mem_locs(), execute_cleanup_eh_1(), execute_optimize_bswap(), execute_rtl_cprop(), execute_rtl_hoist(), execute_rtl_pre(), expand_omp_taskreg(), fixup_noreturn_call(), fold_rtx(), fold_stmt_1(), fold_stmt_inplace(), fold_ternary_loc(), 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(), graphds_domtree(), hoist_code(), init_alias_analysis(), instantiate_virtual_regs_in_insn(), instantiate_virtual_regs_in_rtx(), ipa_propagate_indirect_call_infos(), local_cprop_pass(), local_pure_const(), main_tree_if_conversion(), mark_regno_dead(), mark_regno_live(), match_asm_constraints_1(), maybe_fold_tmr(), mention_regs(), merge_phi_nodes(), move2add_use_add2_insn(), move2add_use_add3_insn(), one_code_hoisting_pass(), one_cprop_pass(), one_pre_gcse_pass(), output_address(), output_min_issue_delay_table(), parallelize_loops(), peel_loops_completely(), phi_translate_1(), pre_delete(), pre_gcse(), process_scc(), reload_cse_move2add(), remove_exits_and_undefined_stmts(), remove_redundant_iv_tests(), rename_uses(), replace_oldest_value_addr(), rewrite_commutative_reductions_out_of_ssa(), rewrite_commutative_reductions_out_of_ssa_loop(), rewrite_cross_bb_scalar_deps_out_of_ssa(), set_union_with_increment(), shrink_wrap_conditional_dead_built_in_calls(), simplify_comparison(), simplify_plus_minus(), simplify_using_outer_evolutions(), split_all_insns(), split_bbs_on_noreturn_calls(), ssa_forward_propagate_and_combine(), symtab_remove_unreachable_nodes(), tail_duplicate(), tm_memopt_compute_available(), tracer(), tree_if_conversion(), tree_loop_distribution(), tree_optimize_tail_calls_1(), tree_simplify_using_condition_1(), tree_ssa_iv_optimize_loop(), tree_ssa_unswitch_loops(), tree_unroll_loops_completely(), tree_unroll_loops_completely_1(), tree_unswitch_single_loop(), try_crossjump_bb(), try_forward_edges(), try_head_merge_bb(), try_optimize_cfg(), undistribute_ops_list(), unroll_and_peel_loops(), unsplit_all_eh(), unswitch_loops(), varpool_output_variables(), visit_nary_op(), visit_phi(), visit_reference_op_call(), visit_reference_op_load(), visit_reference_op_store(), visit_use(), and vt_find_locations().
|
static |
|
static |
List of constraints that we use to build the constraint graph from.
Referenced by check_asm_operands(), constrain_operands(), expand_asm_operands(), find_reloads(), lra_set_insn_recog_data(), lra_update_insn_recog_data(), maybe_fix_stack_asms(), record_operand_costs(), reload_cse_simplify_operands(), and single_reg_class().
| 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().
|
static |
Map varinfo to final pt_solution.
| struct obstack final_solutions_obstack |
Referenced by delete_points_to_sets(), find_what_var_points_to(), and init_alias_vars().
|
static |
Referenced by build_ssa_conflict_graph(), and coalesce_ssa_name().
|
static |
| struct pt_solution ipa_escaped_pt = { true, false, false, false, false, false, NULL } |
IPA PTA solutions for ESCAPED.
Referenced by ipa_pta_execute(), pt_solution_empty_p(), pt_solution_includes_1(), pt_solution_includes_global(), and pt_solutions_intersect_1().
|
static |
Used for per-solver-iteration bitmaps.
|
static |
Current maximum location equivalence class id.
Referenced by perform_var_substitution().
|
static |
A hashtable for mapping a bitmap of labels->location equivalence classes.
|
static |
Used for oldsolution members of variables.
|
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().
|
static |
A hashtable for mapping a bitmap of labels->pointer equivalence classes.
|
static |
Used for predecessor bitmaps.
| unsigned HOST_WIDE_INT pt_solution_includes_may_alias |
| unsigned HOST_WIDE_INT pt_solution_includes_no_alias |
| unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias |
| unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias |
|
static |
Used for points-to sets.
| struct { ... } pta_stats |
Query statistics for points-to solutions.
Referenced by dump_pta_stats(), pt_solution_includes(), and pt_solutions_intersect().
|
static |
Shared_bitmap hashtable.
|
static |
|
static |
Tree based points-to analysis Copyright (C) 2005-2013 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. This is also needed to fix the pt_solution_includes_global predicate (and thus ptr_deref_may_alias_global_p). 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 espaced solution and be used to query which vars escape the unit through a function. 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().
|
static |
Pool of variable info structures.
Table of variable info structures for constraint variables. Indexed directly by variable info id.
|
static |
Map from trees to variable infos.
1.8.1.1