diff options
Diffstat (limited to 'gcc/tree-ssa-structalias.cc')
| -rw-r--r-- | gcc/tree-ssa-structalias.cc | 3370 |
1 files changed, 355 insertions, 3015 deletions
diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc index 0215243..0035e50 100644 --- a/gcc/tree-ssa-structalias.cc +++ b/gcc/tree-ssa-structalias.cc @@ -48,6 +48,9 @@ #include "ipa-modref.h" #include "attr-fnspec.h" +#include "tree-ssa-structalias.h" +#include "pta-andersen.h" + /* 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. @@ -201,172 +204,357 @@ And probably more. */ -static bool use_field_sensitive = true; -static int in_ipa_mode = 0; - -/* Used for predecessor bitmaps. */ -static bitmap_obstack predbitmap_obstack; +namespace pointer_analysis { /* Used for points-to sets. */ -static bitmap_obstack pta_obstack; +bitmap_obstack pta_obstack; -/* Used for oldsolution members of variables. */ -static bitmap_obstack oldpta_obstack; +/* Used for oldsolution members of variables. */ +bitmap_obstack oldpta_obstack; -/* Used for per-solver-iteration bitmaps. */ -static bitmap_obstack iteration_obstack; +/* Table of variable info structures for constraint variables. + Indexed directly by variable info id. */ +vec<varinfo_t> varmap; -static unsigned int create_variable_info_for (tree, const char *, bool); -typedef struct constraint_graph *constraint_graph_t; -static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); +/* List of constraints that we use to build the constraint graph from. */ +vec<constraint_t> constraints; + +/* Map from trees to variable infos. */ +static hash_map<tree, varinfo_t> *vi_for_tree; -struct constraint; -typedef struct constraint *constraint_t; +/* The representative variable for a variable. The points-to solution for a + var can be found in its rep. Trivially, a var can be its own rep. + The solver provides this array once it is done solving. */ +unsigned int *var_rep; -#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ - if (a) \ - EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) +struct constraint_stats stats; -static struct constraint_stats +/* Find the first varinfo in the same variable as START that overlaps with + OFFSET. Return NULL if we can't find one. */ + +varinfo_t +first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) { - unsigned int total_vars; - unsigned int nonpointer_vars; - unsigned int unified_vars_static; - unsigned int unified_vars_dynamic; - unsigned int iterations; - unsigned int num_edges; - unsigned int num_implicit_edges; - unsigned int num_avoided_edges; - unsigned int points_to_sets_created; -} stats; - -struct variable_info + /* If the offset is outside of the variable, bail out. */ + if (offset >= start->fullsize) + return NULL; + + /* If we cannot reach offset from start, lookup the first field + and start from there. */ + if (start->offset > offset) + start = get_varinfo (start->head); + + while (start) + { + /* We may not find a variable in the field list with the actual + offset when we have glommed a structure to a variable. + In that case, however, offset should still be within the size + of the variable. */ + if (offset >= start->offset + && (offset - start->offset) < start->size) + return start; + + start = vi_next (start); + } + + return NULL; +} + +/* 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. */ + +varinfo_t +first_or_preceding_vi_for_offset (varinfo_t start, + unsigned HOST_WIDE_INT offset) { - /* ID of this variable */ - unsigned int id; + /* If we cannot reach offset from start, lookup the first field + and start from there. */ + if (start->offset > offset) + start = get_varinfo (start->head); - /* True if this is a variable created by the constraint analysis, such as - heap variables and constraints we had to break up. */ - unsigned int is_artificial_var : 1; + /* We may not find a variable in the field list with the actual + offset when we have glommed a structure to a variable. + In that case, however, offset should still be within the size + of the variable. + If we got beyond the offset we look for return the field + directly preceding offset which may be the last field. */ + while (start->next + && offset >= start->offset + && !((offset - start->offset) < start->size)) + start = vi_next (start); - /* True if this is a special variable whose solution set should not be - changed. */ - unsigned int is_special_var : 1; + return start; +} - /* True for variables whose size is not known or variable. */ - unsigned int is_unknown_size_var : 1; +/* Print out constraint C to FILE. */ - /* True for (sub-)fields that represent a whole variable. */ - unsigned int is_full_var : 1; +void +dump_constraint (FILE *file, constraint_t c) +{ + if (c->lhs.type == ADDRESSOF) + fprintf (file, "&"); + else if (c->lhs.type == DEREF) + fprintf (file, "*"); + if (dump_file) + fprintf (file, "%s", get_varinfo (c->lhs.var)->name); + else + fprintf (file, "V%d", c->lhs.var); + if (c->lhs.offset == UNKNOWN_OFFSET) + fprintf (file, " + UNKNOWN"); + else if (c->lhs.offset != 0) + fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); + fprintf (file, " = "); + if (c->rhs.type == ADDRESSOF) + fprintf (file, "&"); + else if (c->rhs.type == DEREF) + fprintf (file, "*"); + if (dump_file) + fprintf (file, "%s", get_varinfo (c->rhs.var)->name); + else + fprintf (file, "V%d", c->rhs.var); + if (c->rhs.offset == UNKNOWN_OFFSET) + fprintf (file, " + UNKNOWN"); + else if (c->rhs.offset != 0) + fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); +} - /* True if this is a heap variable. */ - unsigned int is_heap_var : 1; +/* Print out constraint C to stderr. */ - /* True if this is a register variable. */ - unsigned int is_reg_var : 1; +DEBUG_FUNCTION void +debug_constraint (constraint_t c) +{ + dump_constraint (stderr, c); + fprintf (stderr, "\n"); +} - /* True if this field may contain pointers. */ - unsigned int may_have_pointers : 1; +/* Print out all constraints to FILE. */ - /* True if this field has only restrict qualified pointers. */ - unsigned int only_restrict_pointers : 1; +void +dump_constraints (FILE *file, int from) +{ + int i; + constraint_t c; + for (i = from; constraints.iterate (i, &c); i++) + if (c) + { + dump_constraint (file, c); + fprintf (file, "\n"); + } +} - /* True if this represents a heap var created for a restrict qualified - pointer. */ - unsigned int is_restrict_var : 1; +/* Print out all constraints to stderr. */ - /* True if this represents a global variable. */ - unsigned int is_global_var : 1; +DEBUG_FUNCTION void +debug_constraints (void) +{ + dump_constraints (stderr, 0); +} - /* True if this represents a module escape point for IPA analysis. */ - unsigned int is_ipa_escape_point : 1; +/* Print out the points-to solution for VAR to FILE. */ - /* True if this represents a IPA function info. */ - unsigned int is_fn_info : 1; +void +dump_solution_for_var (FILE *file, unsigned int var) +{ + varinfo_t vi = get_varinfo (var); + unsigned int i; + bitmap_iterator bi; - /* True if this appears as RHS in a ADDRESSOF constraint. */ - unsigned int address_taken : 1; + /* Dump the solution for unified vars anyway, this avoids difficulties + in scanning dumps in the testsuite. */ + fprintf (file, "%s = { ", vi->name); + vi = get_varinfo (var_rep[var]); + EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) + fprintf (file, "%s ", get_varinfo (i)->name); + fprintf (file, "}"); - /* ??? Store somewhere better. */ - unsigned short ruid; + /* But note when the variable was unified. */ + if (vi->id != var) + fprintf (file, " same as %s", vi->name); - /* The ID of the variable for the next field in this structure - or zero for the last field in this structure. */ - unsigned next; + fprintf (file, "\n"); +} - /* The ID of the variable for the first field in this structure. */ - unsigned head; +/* Print the points-to solution for VAR to stderr. */ - /* Offset of this variable, in bits, from the base variable */ - unsigned HOST_WIDE_INT offset; +DEBUG_FUNCTION void +debug_solution_for_var (unsigned int var) +{ + dump_solution_for_var (stderr, var); +} - /* Size of the variable, in bits. */ - unsigned HOST_WIDE_INT size; +/* Dump stats information to OUTFILE. */ - /* Full size of the base variable, in bits. */ - unsigned HOST_WIDE_INT fullsize; +void +dump_sa_stats (FILE *outfile) +{ + fprintf (outfile, "Points-to Stats:\n"); + fprintf (outfile, "Total vars: %d\n", stats.total_vars); + fprintf (outfile, "Non-pointer vars: %d\n", + stats.nonpointer_vars); + fprintf (outfile, "Statically unified vars: %d\n", + stats.unified_vars_static); + fprintf (outfile, "Dynamically unified vars: %d\n", + stats.unified_vars_dynamic); + fprintf (outfile, "Iterations: %d\n", stats.iterations); + fprintf (outfile, "Number of edges: %d\n", stats.num_edges); + fprintf (outfile, "Number of implicit edges: %d\n", + stats.num_implicit_edges); + fprintf (outfile, "Number of avoided edges: %d\n", + stats.num_avoided_edges); +} - /* In IPA mode the shadow UID in case the variable needs to be duplicated in - the final points-to solution because it reaches its containing - function recursively. Zero if none is needed. */ - unsigned int shadow_var_uid; +/* Dump points-to information to OUTFILE. */ - /* Name of this variable */ - const char *name; +void +dump_sa_points_to_info (FILE *outfile) +{ + fprintf (outfile, "\nPoints-to sets\n\n"); - /* Tree that this variable is associated with. */ - tree decl; + for (unsigned i = 1; i < varmap.length (); i++) + { + varinfo_t vi = get_varinfo (i); + if (!vi->may_have_pointers) + continue; + dump_solution_for_var (outfile, i); + } +} - /* Points-to set for this variable. */ - bitmap solution; - /* Old points-to set for this variable. */ - bitmap oldsolution; -}; -typedef struct variable_info *varinfo_t; +/* Debug points-to information to stderr. */ -static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); -static varinfo_t first_or_preceding_vi_for_offset (varinfo_t, - unsigned HOST_WIDE_INT); -static varinfo_t lookup_vi_for_tree (tree); -static inline bool type_can_have_subvars (const_tree); -static void make_param_constraints (varinfo_t); +DEBUG_FUNCTION void +debug_sa_points_to_info (void) +{ + dump_sa_points_to_info (stderr); +} -/* Pool of variable info structures. */ -static object_allocator<variable_info> variable_info_pool - ("Variable info pool"); +/* Dump varinfo VI to FILE. */ -/* Map varinfo to final pt_solution. */ -static hash_map<varinfo_t, pt_solution *> *final_solutions; -struct obstack final_solutions_obstack; +void +dump_varinfo (FILE *file, varinfo_t vi) +{ + if (vi == NULL) + return; -/* Table of variable info structures for constraint variables. - Indexed directly by variable info id. */ -static vec<varinfo_t> varmap; + fprintf (file, "%u: %s\n", vi->id, vi->name); -/* Return the varmap element N */ + const char *sep = " "; + if (vi->is_artificial_var) + fprintf (file, "%sartificial", sep); + if (vi->is_special_var) + fprintf (file, "%sspecial", sep); + if (vi->is_unknown_size_var) + fprintf (file, "%sunknown-size", sep); + if (vi->is_full_var) + fprintf (file, "%sfull", sep); + if (vi->is_heap_var) + fprintf (file, "%sheap", sep); + if (vi->may_have_pointers) + fprintf (file, "%smay-have-pointers", sep); + if (vi->only_restrict_pointers) + fprintf (file, "%sonly-restrict-pointers", sep); + if (vi->is_restrict_var) + fprintf (file, "%sis-restrict-var", sep); + if (vi->is_global_var) + fprintf (file, "%sglobal", sep); + if (vi->is_ipa_escape_point) + fprintf (file, "%sipa-escape-point", sep); + if (vi->is_fn_info) + fprintf (file, "%sfn-info", sep); + if (vi->ruid) + fprintf (file, "%srestrict-uid:%u", sep, vi->ruid); + if (vi->next) + fprintf (file, "%snext:%u", sep, vi->next); + if (vi->head != vi->id) + fprintf (file, "%shead:%u", sep, vi->head); + if (vi->offset) + fprintf (file, "%soffset:" HOST_WIDE_INT_PRINT_DEC, sep, vi->offset); + if (vi->size != ~HOST_WIDE_INT_0U) + fprintf (file, "%ssize:" HOST_WIDE_INT_PRINT_DEC, sep, vi->size); + if (vi->fullsize != ~HOST_WIDE_INT_0U && vi->fullsize != vi->size) + fprintf (file, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC, sep, + vi->fullsize); + fprintf (file, "\n"); -static inline varinfo_t -get_varinfo (unsigned int n) + if (vi->solution && !bitmap_empty_p (vi->solution)) + { + bitmap_iterator bi; + unsigned i; + fprintf (file, " solution: {"); + EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) + fprintf (file, " %u", i); + fprintf (file, " }\n"); + } + + if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution) + && !bitmap_equal_p (vi->solution, vi->oldsolution)) + { + bitmap_iterator bi; + unsigned i; + fprintf (file, " oldsolution: {"); + EXECUTE_IF_SET_IN_BITMAP (vi->oldsolution, 0, i, bi) + fprintf (file, " %u", i); + fprintf (file, " }\n"); + } +} + +/* Dump varinfo VI to stderr. */ + +DEBUG_FUNCTION void +debug_varinfo (varinfo_t vi) +{ + dump_varinfo (stderr, vi); +} + +/* Dump varmap to FILE. */ + +void +dump_varmap (FILE *file) { - return varmap[n]; + if (varmap.length () == 0) + return; + + fprintf (file, "variables:\n"); + + for (unsigned int i = 0; i < varmap.length (); ++i) + { + varinfo_t vi = get_varinfo (i); + dump_varinfo (file, vi); + } + + fprintf (file, "\n"); } -/* Return the next variable in the list of sub-variables of VI - or NULL if VI is the last sub-variable. */ +/* Dump varmap to stderr. */ -static inline varinfo_t -vi_next (varinfo_t vi) +DEBUG_FUNCTION void +debug_varmap (void) { - return get_varinfo (vi->next); + dump_varmap (stderr); } -/* Static IDs for the special variables. Variable ID zero is unused - and used as terminator for the sub-variable chain. */ -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 }; +} // namespace pointer_analysis + + +using namespace pointer_analysis; + +static bool use_field_sensitive = true; +static int in_ipa_mode = 0; + +static unsigned int create_variable_info_for (tree, const char *, bool); +static varinfo_t lookup_vi_for_tree (tree); +static inline bool type_can_have_subvars (const_tree); +static void make_param_constraints (varinfo_t); + +/* Pool of variable info structures. */ +static object_allocator<variable_info> variable_info_pool + ("Variable info pool"); + +/* Map varinfo to final pt_solution. */ +static hash_map<varinfo_t, pt_solution *> *final_solutions; +static struct obstack final_solutions_obstack; /* Return a new variable info structure consisting for a variable named NAME, and using constraint graph node NODE. Append it @@ -502,166 +690,15 @@ get_call_clobber_vi (gcall *call) } -enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF}; - -/* An expression that appears in a constraint. */ - -struct constraint_expr -{ - /* Constraint type. */ - constraint_expr_type type; - - /* Variable we are referring to in the constraint. */ - unsigned int var; - - /* Offset, in bits, of this constraint from the beginning of - variables it ends up referring to. - - IOW, in a deref constraint, we would deref, get the result set, - then add OFFSET to each member. */ - HOST_WIDE_INT offset; -}; - -/* Use 0x8000... as special unknown offset. */ -#define UNKNOWN_OFFSET HOST_WIDE_INT_MIN - -typedef struct constraint_expr ce_s; static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool); static void get_constraint_for (tree, vec<ce_s> *); static void get_constraint_for_rhs (tree, vec<ce_s> *); static void do_deref (vec<ce_s> *); -/* Our set constraints are made up of two constraint expressions, one - LHS, and one RHS. - - As described in the introduction, our set constraints each represent an - operation between set valued variables. -*/ -struct constraint -{ - struct constraint_expr lhs; - struct constraint_expr rhs; -}; +/* Allocator for 'constraints' vector. */ -/* List of constraints that we use to build the constraint graph from. */ - -static vec<constraint_t> constraints; static object_allocator<constraint> constraint_pool ("Constraint pool"); -/* The constraint graph is represented as an array of bitmaps - containing successor nodes. */ - -struct constraint_graph -{ - /* Size of this graph, which may be different than the number of - nodes in the variable map. */ - unsigned int size; - - /* Explicit successors of each node. */ - bitmap *succs; - - /* Implicit predecessors of each node (Used for variable - substitution). */ - bitmap *implicit_preds; - - /* Explicit predecessors of each node (Used for variable substitution). */ - bitmap *preds; - - /* Indirect cycle representatives, or -1 if the node has no indirect - cycles. */ - int *indirect_cycles; - - /* Representative node for a node. rep[a] == a unless the node has - been unified. */ - unsigned int *rep; - - /* Equivalence class representative for a label. This is used for - variable substitution. */ - int *eq_rep; - - /* Pointer equivalence label for a node. All nodes with the same - pointer equivalence label can be unified together at some point - (either during constraint optimization or after the constraint - graph is built). */ - unsigned int *pe; - - /* Pointer equivalence representative for a label. This is used to - handle nodes that are pointer equivalent but not location - equivalent. We can unite these once the addressof constraints - are transformed into initial points-to sets. */ - int *pe_rep; - - /* Pointer equivalence label for each node, used during variable - substitution. */ - unsigned int *pointer_label; - - /* Location equivalence label for each node, used during location - equivalence finding. */ - unsigned int *loc_label; - - /* Pointed-by set for each node, used during location equivalence - finding. This is pointed-by rather than pointed-to, because it - is constructed using the predecessor graph. */ - bitmap *pointed_by; - - /* Points to sets for pointer equivalence. This is *not* the actual - points-to sets for nodes. */ - bitmap *points_to; - - /* Bitmap of nodes where the bit is set if the node is a direct - node. Used for variable substitution. */ - sbitmap direct_nodes; - - /* Bitmap of nodes where the bit is set if the node is address - taken. Used for variable substitution. */ - bitmap address_taken; - - /* Vector of complex constraints for each graph node. Complex - constraints are those involving dereferences or offsets that are - not 0. */ - vec<constraint_t> *complex; -}; - -static constraint_graph_t graph; - -/* 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. */ -#define FIRST_REF_NODE (varmap).length () -#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) - -/* 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. */ - -static unsigned int -find (unsigned int node) -{ - gcc_checking_assert (node < graph->size); - if (graph->rep[node] != node) - return graph->rep[node] = find (graph->rep[node]); - return node; -} - -/* 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. */ - -static bool -unite (unsigned int to, unsigned int from) -{ - gcc_checking_assert (to < graph->size && from < graph->size); - if (to != from && graph->rep[from] != to) - { - graph->rep[from] = to; - return true; - } - return false; -} - /* Create a new constraint consisting of LHS and RHS expressions. */ static constraint_t @@ -674,2312 +711,6 @@ new_constraint (const struct constraint_expr lhs, return ret; } -/* Print out constraint C to FILE. */ - -static void -dump_constraint (FILE *file, constraint_t c) -{ - if (c->lhs.type == ADDRESSOF) - fprintf (file, "&"); - else if (c->lhs.type == DEREF) - fprintf (file, "*"); - if (dump_file) - fprintf (file, "%s", get_varinfo (c->lhs.var)->name); - else - fprintf (file, "V%d", c->lhs.var); - if (c->lhs.offset == UNKNOWN_OFFSET) - fprintf (file, " + UNKNOWN"); - else if (c->lhs.offset != 0) - fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); - fprintf (file, " = "); - if (c->rhs.type == ADDRESSOF) - fprintf (file, "&"); - else if (c->rhs.type == DEREF) - fprintf (file, "*"); - if (dump_file) - fprintf (file, "%s", get_varinfo (c->rhs.var)->name); - else - fprintf (file, "V%d", c->rhs.var); - if (c->rhs.offset == UNKNOWN_OFFSET) - fprintf (file, " + UNKNOWN"); - else if (c->rhs.offset != 0) - fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); -} - - -void debug_constraint (constraint_t); -void debug_constraints (void); -void debug_constraint_graph (void); -void debug_solution_for_var (unsigned int); -void debug_sa_points_to_info (void); -void debug_varinfo (varinfo_t); -void debug_varmap (void); - -/* Print out constraint C to stderr. */ - -DEBUG_FUNCTION void -debug_constraint (constraint_t c) -{ - dump_constraint (stderr, c); - fprintf (stderr, "\n"); -} - -/* Print out all constraints to FILE */ - -static void -dump_constraints (FILE *file, int from) -{ - int i; - constraint_t c; - for (i = from; constraints.iterate (i, &c); i++) - if (c) - { - dump_constraint (file, c); - fprintf (file, "\n"); - } -} - -/* Print out all constraints to stderr. */ - -DEBUG_FUNCTION void -debug_constraints (void) -{ - dump_constraints (stderr, 0); -} - -/* Print the constraint graph in dot format. */ - -static void -dump_constraint_graph (FILE *file) -{ - unsigned int i; - - /* Only print the graph if it has already been initialized: */ - if (!graph) - return; - - /* Prints the header of the dot file: */ - fprintf (file, "strict digraph {\n"); - fprintf (file, " node [\n shape = box\n ]\n"); - fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); - fprintf (file, "\n // List of nodes and complex constraints in " - "the constraint graph:\n"); - - /* The next lines print the nodes in the graph together with the - complex constraints attached to them. */ - for (i = 1; i < graph->size; i++) - { - if (i == FIRST_REF_NODE) - continue; - if (find (i) != i) - continue; - if (i < FIRST_REF_NODE) - fprintf (file, "\"%s\"", get_varinfo (i)->name); - else - fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); - if (graph->complex[i].exists ()) - { - unsigned j; - constraint_t c; - fprintf (file, " [label=\"\\N\\n"); - for (j = 0; graph->complex[i].iterate (j, &c); ++j) - { - dump_constraint (file, c); - fprintf (file, "\\l"); - } - fprintf (file, "\"]"); - } - fprintf (file, ";\n"); - } - - /* Go over the edges. */ - fprintf (file, "\n // Edges in the constraint graph:\n"); - for (i = 1; i < graph->size; i++) - { - unsigned j; - bitmap_iterator bi; - if (find (i) != i) - continue; - EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi) - { - unsigned to = find (j); - if (i == to) - continue; - if (i < FIRST_REF_NODE) - fprintf (file, "\"%s\"", get_varinfo (i)->name); - else - fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); - fprintf (file, " -> "); - if (to < FIRST_REF_NODE) - fprintf (file, "\"%s\"", get_varinfo (to)->name); - else - fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name); - fprintf (file, ";\n"); - } - } - - /* Prints the tail of the dot file. */ - fprintf (file, "}\n"); -} - -/* Print out the constraint graph to stderr. */ - -DEBUG_FUNCTION void -debug_constraint_graph (void) -{ - dump_constraint_graph (stderr); -} - -/* 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. */ - -static bool -constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) -{ - return a.type == b.type && a.var == b.var && a.offset == b.offset; -} - -/* 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. */ - -static bool -constraint_expr_less (struct constraint_expr a, struct constraint_expr b) -{ - if (a.type == b.type) - { - if (a.var == b.var) - return a.offset < b.offset; - else - return a.var < b.var; - } - else - return a.type < b.type; -} - -/* Return true if constraint A is less than constraint B. This is just - arbitrary, but consistent, in order to give them an ordering. */ - -static bool -constraint_less (const constraint_t &a, const constraint_t &b) -{ - if (constraint_expr_less (a->lhs, b->lhs)) - return true; - else if (constraint_expr_less (b->lhs, a->lhs)) - return false; - else - return constraint_expr_less (a->rhs, b->rhs); -} - -/* Return true if two constraints A and B are equal. */ - -static bool -constraint_equal (const constraint &a, const constraint &b) -{ - return constraint_expr_equal (a.lhs, b.lhs) - && constraint_expr_equal (a.rhs, b.rhs); -} - - -/* Find a constraint LOOKFOR in the sorted constraint vector VEC */ - -static constraint_t -constraint_vec_find (vec<constraint_t> vec, - constraint &lookfor) -{ - unsigned int place; - constraint_t found; - - if (!vec.exists ()) - return NULL; - - place = vec.lower_bound (&lookfor, constraint_less); - if (place >= vec.length ()) - return NULL; - found = vec[place]; - if (!constraint_equal (*found, lookfor)) - return NULL; - return found; -} - -/* Union two constraint vectors, TO and FROM. Put the result in TO. - Returns true of TO set is changed. */ - -static bool -constraint_set_union (vec<constraint_t> *to, - vec<constraint_t> *from) -{ - int i; - constraint_t c; - bool any_change = false; - - FOR_EACH_VEC_ELT (*from, i, c) - { - if (constraint_vec_find (*to, *c) == NULL) - { - unsigned int place = to->lower_bound (c, constraint_less); - to->safe_insert (place, c); - any_change = true; - } - } - return any_change; -} - -/* Expands the solution in SET to all sub-fields of variables included. */ - -static bitmap -solution_set_expand (bitmap set, bitmap *expanded) -{ - bitmap_iterator bi; - unsigned j; - - if (*expanded) - return *expanded; - - *expanded = BITMAP_ALLOC (&iteration_obstack); - - /* In a first pass expand variables, once for each head to avoid - quadratic behavior, to include all sub-fields. */ - unsigned prev_head = 0; - EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi) - { - varinfo_t v = get_varinfo (j); - if (v->is_artificial_var - || v->is_full_var) - continue; - if (v->head != prev_head) - { - varinfo_t head = get_varinfo (v->head); - unsigned num = 1; - for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n)) - { - if (n->id != head->id + num) - { - /* Usually sub variables are adjacent but since we - create pointed-to restrict representatives there - can be gaps as well. */ - bitmap_set_range (*expanded, head->id, num); - head = n; - num = 1; - } - else - num++; - } - - bitmap_set_range (*expanded, head->id, num); - prev_head = v->head; - } - } - - /* And finally set the rest of the bits from SET in an efficient way. */ - bitmap_ior_into (*expanded, set); - - return *expanded; -} - -/* Union solution sets TO and DELTA, and add INC to each member of DELTA in the - process. */ - -static bool -set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc, - bitmap *expanded_delta) -{ - bool changed = false; - bitmap_iterator bi; - unsigned int i; - - /* If the solution of DELTA contains anything it is good enough to transfer - this to TO. */ - if (bitmap_bit_p (delta, anything_id)) - return bitmap_set_bit (to, anything_id); - - /* If the offset is unknown we have to expand the solution to - all subfields. */ - if (inc == UNKNOWN_OFFSET) - { - delta = solution_set_expand (delta, expanded_delta); - changed |= bitmap_ior_into (to, delta); - return changed; - } - - /* For non-zero offset union the offsetted solution into the destination. */ - EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi) - { - varinfo_t vi = get_varinfo (i); - - /* If this is a variable with just one field just set its bit - in the result. */ - if (vi->is_artificial_var - || vi->is_unknown_size_var - || vi->is_full_var) - changed |= bitmap_set_bit (to, i); - else - { - HOST_WIDE_INT fieldoffset = vi->offset + inc; - unsigned HOST_WIDE_INT size = vi->size; - - /* If the offset makes the pointer point to before the - variable use offset zero for the field lookup. */ - if (fieldoffset < 0) - vi = get_varinfo (vi->head); - else - vi = first_or_preceding_vi_for_offset (vi, fieldoffset); - - do - { - changed |= bitmap_set_bit (to, vi->id); - if (vi->is_full_var - || vi->next == 0) - break; - - /* We have to include all fields that overlap the current field - shifted by inc. */ - vi = vi_next (vi); - } - while (vi->offset < fieldoffset + size); - } - } - - return changed; -} - -/* Insert constraint C into the list of complex constraints for graph - node VAR. */ - -static void -insert_into_complex (constraint_graph_t graph, - unsigned int var, constraint_t c) -{ - vec<constraint_t> complex = graph->complex[var]; - unsigned int place = complex.lower_bound (c, constraint_less); - - /* Only insert constraints that do not already exist. */ - if (place >= complex.length () - || !constraint_equal (*c, *complex[place])) - graph->complex[var].safe_insert (place, c); -} - - -/* 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. */ - -static bool -merge_node_constraints (constraint_graph_t graph, unsigned int to, - unsigned int from) -{ - unsigned int i; - constraint_t c; - bool any_change = false; - - gcc_checking_assert (find (from) == to); - - /* Move all complex constraints from src node into to node */ - FOR_EACH_VEC_ELT (graph->complex[from], i, c) - { - /* In complex constraints for node FROM, we may have either - a = *FROM, and *FROM = a, or an offseted constraint which are - always added to the rhs node's constraints. */ - - if (c->rhs.type == DEREF) - c->rhs.var = to; - else if (c->lhs.type == DEREF) - c->lhs.var = to; - else - c->rhs.var = to; - - } - any_change = constraint_set_union (&graph->complex[to], - &graph->complex[from]); - graph->complex[from].release (); - return any_change; -} - - -/* Remove edges involving NODE from GRAPH. */ - -static void -clear_edges_for_node (constraint_graph_t graph, unsigned int node) -{ - if (graph->succs[node]) - BITMAP_FREE (graph->succs[node]); -} - -/* Merge GRAPH nodes FROM and TO into node TO. */ - -static void -merge_graph_nodes (constraint_graph_t graph, unsigned int to, - unsigned int from) -{ - if (graph->indirect_cycles[from] != -1) - { - /* If we have indirect cycles with the from node, and we have - none on the to node, the to node has indirect cycles from the - from node now that they are unified. - If indirect cycles exist on both, unify the nodes that they - are in a cycle with, since we know they are in a cycle with - each other. */ - if (graph->indirect_cycles[to] == -1) - graph->indirect_cycles[to] = graph->indirect_cycles[from]; - } - - /* Merge all the successor edges. */ - if (graph->succs[from]) - { - if (!graph->succs[to]) - graph->succs[to] = BITMAP_ALLOC (&pta_obstack); - bitmap_ior_into (graph->succs[to], - graph->succs[from]); - } - - clear_edges_for_node (graph, from); -} - - -/* Add an indirect graph edge to GRAPH, going from TO to FROM if - it doesn't exist in the graph already. */ - -static void -add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, - unsigned int from) -{ - if (to == from) - return; - - if (!graph->implicit_preds[to]) - graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); - - if (bitmap_set_bit (graph->implicit_preds[to], from)) - stats.num_implicit_edges++; -} - -/* 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. */ - -static void -add_pred_graph_edge (constraint_graph_t graph, unsigned int to, - unsigned int from) -{ - if (!graph->preds[to]) - graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); - bitmap_set_bit (graph->preds[to], from); -} - -/* 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. */ - -static bool -add_graph_edge (constraint_graph_t graph, unsigned int to, - unsigned int from) -{ - if (to == from) - { - return false; - } - else - { - bool r = false; - - if (!graph->succs[from]) - graph->succs[from] = BITMAP_ALLOC (&pta_obstack); - - /* The graph solving process does not avoid "triangles", thus - there can be multiple paths from a node to another involving - intermediate other nodes. That causes extra copying which is - most difficult to avoid when the intermediate node is ESCAPED - because there are no edges added from ESCAPED. Avoid - adding the direct edge FROM -> TO when we have FROM -> ESCAPED - and TO contains ESCAPED. - ??? Note this is only a heuristic, it does not prevent the - situation from occuring. The heuristic helps PR38474 and - PR99912 significantly. */ - if (to < FIRST_REF_NODE - && bitmap_bit_p (graph->succs[from], find (escaped_id)) - && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id)) - { - stats.num_avoided_edges++; - return false; - } - - if (bitmap_set_bit (graph->succs[from], to)) - { - r = true; - if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) - stats.num_edges++; - } - return r; - } -} - - -/* Initialize the constraint graph structure to contain SIZE nodes. */ - -static void -init_graph (unsigned int size) -{ - unsigned int j; - - graph = XCNEW (struct constraint_graph); - graph->size = size; - graph->succs = XCNEWVEC (bitmap, graph->size); - graph->indirect_cycles = XNEWVEC (int, graph->size); - graph->rep = XNEWVEC (unsigned int, graph->size); - /* ??? Macros do not support template types with multiple arguments, - so we use a typedef to work around it. */ - typedef vec<constraint_t> vec_constraint_t_heap; - graph->complex = XCNEWVEC (vec_constraint_t_heap, size); - graph->pe = XCNEWVEC (unsigned int, graph->size); - graph->pe_rep = XNEWVEC (int, graph->size); - - for (j = 0; j < graph->size; j++) - { - graph->rep[j] = j; - graph->pe_rep[j] = -1; - graph->indirect_cycles[j] = -1; - } -} - -/* Build the constraint graph, adding only predecessor edges right now. */ - -static void -build_pred_graph (void) -{ - int i; - constraint_t c; - unsigned int j; - - graph->implicit_preds = XCNEWVEC (bitmap, graph->size); - graph->preds = XCNEWVEC (bitmap, graph->size); - graph->pointer_label = XCNEWVEC (unsigned int, graph->size); - graph->loc_label = XCNEWVEC (unsigned int, graph->size); - graph->pointed_by = XCNEWVEC (bitmap, graph->size); - graph->points_to = XCNEWVEC (bitmap, graph->size); - graph->eq_rep = XNEWVEC (int, graph->size); - graph->direct_nodes = sbitmap_alloc (graph->size); - graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack); - bitmap_clear (graph->direct_nodes); - - for (j = 1; j < FIRST_REF_NODE; j++) - { - if (!get_varinfo (j)->is_special_var) - bitmap_set_bit (graph->direct_nodes, j); - } - - for (j = 0; j < graph->size; j++) - graph->eq_rep[j] = -1; - - for (j = 0; j < varmap.length (); j++) - graph->indirect_cycles[j] = -1; - - FOR_EACH_VEC_ELT (constraints, i, c) - { - struct constraint_expr lhs = c->lhs; - struct constraint_expr rhs = c->rhs; - unsigned int lhsvar = lhs.var; - unsigned int rhsvar = rhs.var; - - if (lhs.type == DEREF) - { - /* *x = y. */ - if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) - { - if (lhs.var == anything_id) - add_pred_graph_edge (graph, storedanything_id, rhsvar); - else - add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); - } - } - else if (rhs.type == DEREF) - { - /* x = *y */ - if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) - add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); - else - bitmap_clear_bit (graph->direct_nodes, lhsvar); - } - else if (rhs.type == ADDRESSOF) - { - varinfo_t v; - - /* x = &y */ - if (graph->points_to[lhsvar] == NULL) - graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack); - bitmap_set_bit (graph->points_to[lhsvar], rhsvar); - - if (graph->pointed_by[rhsvar] == NULL) - graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack); - bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar); - - /* Implicitly, *x = y */ - add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); - - /* All related variables are no longer direct nodes. */ - bitmap_clear_bit (graph->direct_nodes, rhsvar); - v = get_varinfo (rhsvar); - if (!v->is_full_var) - { - v = get_varinfo (v->head); - do - { - bitmap_clear_bit (graph->direct_nodes, v->id); - v = vi_next (v); - } - while (v != NULL); - } - bitmap_set_bit (graph->address_taken, rhsvar); - } - else if (lhsvar > anything_id - && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) - { - /* x = y */ - add_pred_graph_edge (graph, lhsvar, rhsvar); - /* Implicitly, *x = *y */ - add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, - FIRST_REF_NODE + rhsvar); - } - else if (lhs.offset != 0 || rhs.offset != 0) - { - if (rhs.offset != 0) - bitmap_clear_bit (graph->direct_nodes, lhs.var); - else if (lhs.offset != 0) - bitmap_clear_bit (graph->direct_nodes, rhs.var); - } - } -} - -/* Build the constraint graph, adding successor edges. */ - -static void -build_succ_graph (void) -{ - unsigned i, t; - constraint_t c; - - FOR_EACH_VEC_ELT (constraints, i, c) - { - struct constraint_expr lhs; - struct constraint_expr rhs; - unsigned int lhsvar; - unsigned int rhsvar; - - if (!c) - continue; - - lhs = c->lhs; - rhs = c->rhs; - lhsvar = find (lhs.var); - rhsvar = find (rhs.var); - - if (lhs.type == DEREF) - { - if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) - { - if (lhs.var == anything_id) - add_graph_edge (graph, storedanything_id, rhsvar); - else - add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); - } - } - else if (rhs.type == DEREF) - { - if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) - add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); - } - else if (rhs.type == ADDRESSOF) - { - /* x = &y */ - gcc_checking_assert (find (rhs.var) == rhs.var); - bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); - } - else if (lhsvar > anything_id - && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) - { - add_graph_edge (graph, lhsvar, rhsvar); - } - } - - /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */ - t = find (storedanything_id); - for (i = integer_id + 1; i < FIRST_REF_NODE; ++i) - { - if (get_varinfo (i)->may_have_pointers) - add_graph_edge (graph, find (i), t); - } - - /* Everything stored to ANYTHING also potentially escapes. */ - add_graph_edge (graph, find (escaped_id), t); -} - - -/* Changed variables on the last iteration. */ -static bitmap changed; - -/* Strongly Connected Component visitation info. */ - -class scc_info -{ -public: - scc_info (size_t size); - ~scc_info (); - - auto_sbitmap visited; - auto_sbitmap deleted; - unsigned int *dfs; - unsigned int *node_mapping; - int current_index; - auto_vec<unsigned> scc_stack; -}; - - -/* 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. */ - -static void -scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) -{ - unsigned int i; - bitmap_iterator bi; - unsigned int my_dfs; - - bitmap_set_bit (si->visited, n); - si->dfs[n] = si->current_index ++; - my_dfs = si->dfs[n]; - - /* Visit all the successors. */ - EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) - { - unsigned int w; - - if (i > LAST_REF_NODE) - break; - - w = find (i); - if (bitmap_bit_p (si->deleted, w)) - continue; - - if (!bitmap_bit_p (si->visited, w)) - scc_visit (graph, si, w); - - unsigned int t = find (w); - gcc_checking_assert (find (n) == n); - if (si->dfs[t] < si->dfs[n]) - si->dfs[n] = si->dfs[t]; - } - - /* See if any components have been identified. */ - if (si->dfs[n] == my_dfs) - { - if (si->scc_stack.length () > 0 - && si->dfs[si->scc_stack.last ()] >= my_dfs) - { - bitmap scc = BITMAP_ALLOC (NULL); - unsigned int lowest_node; - bitmap_iterator bi; - - bitmap_set_bit (scc, n); - - while (si->scc_stack.length () != 0 - && si->dfs[si->scc_stack.last ()] >= my_dfs) - { - unsigned int w = si->scc_stack.pop (); - - bitmap_set_bit (scc, w); - } - - lowest_node = bitmap_first_set_bit (scc); - gcc_assert (lowest_node < FIRST_REF_NODE); - - /* Collapse the SCC nodes into a single node, and mark the - indirect cycles. */ - EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) - { - if (i < FIRST_REF_NODE) - { - if (unite (lowest_node, i)) - unify_nodes (graph, lowest_node, i, false); - } - else - { - unite (lowest_node, i); - graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; - } - } - bitmap_set_bit (si->deleted, lowest_node); - } - else - bitmap_set_bit (si->deleted, n); - } - else - si->scc_stack.safe_push (n); -} - -/* Unify node FROM into node TO, updating the changed count if - necessary when UPDATE_CHANGED is true. */ - -static void -unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, - bool update_changed) -{ - gcc_checking_assert (to != from && find (to) == to); - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Unifying %s to %s\n", - get_varinfo (from)->name, - get_varinfo (to)->name); - - if (update_changed) - stats.unified_vars_dynamic++; - else - stats.unified_vars_static++; - - merge_graph_nodes (graph, to, from); - if (merge_node_constraints (graph, to, from)) - { - if (update_changed) - bitmap_set_bit (changed, to); - } - - /* Mark TO as changed if FROM was changed. If TO was already marked - as changed, decrease the changed count. */ - - if (update_changed - && bitmap_clear_bit (changed, from)) - bitmap_set_bit (changed, to); - varinfo_t fromvi = get_varinfo (from); - if (fromvi->solution) - { - /* If the solution changes because of the merging, we need to mark - the variable as changed. */ - varinfo_t tovi = get_varinfo (to); - if (bitmap_ior_into (tovi->solution, fromvi->solution)) - { - if (update_changed) - bitmap_set_bit (changed, to); - } - - BITMAP_FREE (fromvi->solution); - if (fromvi->oldsolution) - BITMAP_FREE (fromvi->oldsolution); - - if (stats.iterations > 0 - && tovi->oldsolution) - BITMAP_FREE (tovi->oldsolution); - } - if (graph->succs[to]) - bitmap_clear_bit (graph->succs[to], to); -} - -/* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE - if the solution of TO changed. */ - -static bool -solve_add_graph_edge (constraint_graph_t graph, unsigned int to, - unsigned int from) -{ - /* Adding edges from the special vars is pointless. - They don't have sets that can change. */ - if (get_varinfo (from)->is_special_var) - return bitmap_ior_into (get_varinfo (to)->solution, - get_varinfo (from)->solution); - /* Merging the solution from ESCAPED needlessly increases - the set. Use ESCAPED as representative instead. */ - else if (from == find (escaped_id)) - return bitmap_set_bit (get_varinfo (to)->solution, escaped_id); - else if (get_varinfo (from)->may_have_pointers - && add_graph_edge (graph, to, from)) - return bitmap_ior_into (get_varinfo (to)->solution, - get_varinfo (from)->solution); - return false; -} - -/* Process a constraint C that represents x = *(y + off), using DELTA as the - starting solution for y. */ - -static void -do_sd_constraint (constraint_graph_t graph, constraint_t c, - bitmap delta, bitmap *expanded_delta) -{ - unsigned int lhs = c->lhs.var; - bool flag = false; - bitmap sol = get_varinfo (lhs)->solution; - unsigned int j; - bitmap_iterator bi; - HOST_WIDE_INT roffset = c->rhs.offset; - - /* Our IL does not allow this. */ - gcc_checking_assert (c->lhs.offset == 0); - - /* If the solution of Y contains anything it is good enough to transfer - this to the LHS. */ - if (bitmap_bit_p (delta, anything_id)) - { - flag |= bitmap_set_bit (sol, anything_id); - goto done; - } - - /* If we do not know at with offset the rhs is dereferenced compute - the reachability set of DELTA, conservatively assuming it is - dereferenced at all valid offsets. */ - if (roffset == UNKNOWN_OFFSET) - { - delta = solution_set_expand (delta, expanded_delta); - /* No further offset processing is necessary. */ - roffset = 0; - } - - /* For each variable j in delta (Sol(y)), add - an edge in the graph from j to x, and union Sol(j) into Sol(x). */ - EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) - { - varinfo_t v = get_varinfo (j); - HOST_WIDE_INT fieldoffset = v->offset + roffset; - unsigned HOST_WIDE_INT size = v->size; - unsigned int t; - - if (v->is_full_var) - ; - else if (roffset != 0) - { - if (fieldoffset < 0) - v = get_varinfo (v->head); - else - v = first_or_preceding_vi_for_offset (v, fieldoffset); - } - - /* We have to include all fields that overlap the current field - shifted by roffset. */ - do - { - t = find (v->id); - - flag |= solve_add_graph_edge (graph, lhs, t); - - if (v->is_full_var - || v->next == 0) - break; - - v = vi_next (v); - } - while (v->offset < fieldoffset + size); - } - -done: - /* If the LHS solution changed, mark the var as changed. */ - if (flag) - bitmap_set_bit (changed, lhs); -} - -/* Process a constraint C that represents *(x + off) = y using DELTA - as the starting solution for x. */ - -static void -do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta) -{ - unsigned int rhs = c->rhs.var; - bitmap sol = get_varinfo (rhs)->solution; - unsigned int j; - bitmap_iterator bi; - HOST_WIDE_INT loff = c->lhs.offset; - bool escaped_p = false; - - /* Our IL does not allow this. */ - gcc_checking_assert (c->rhs.offset == 0); - - /* If the solution of y contains ANYTHING simply use the ANYTHING - solution. This avoids needlessly increasing the points-to sets. */ - if (bitmap_bit_p (sol, anything_id)) - sol = get_varinfo (find (anything_id))->solution; - - /* If the solution for x contains ANYTHING we have to merge the - solution of y into all pointer variables which we do via - STOREDANYTHING. */ - if (bitmap_bit_p (delta, anything_id)) - { - unsigned t = find (storedanything_id); - if (solve_add_graph_edge (graph, t, rhs)) - bitmap_set_bit (changed, t); - return; - } - - /* If we do not know at with offset the rhs is dereferenced compute - the reachability set of DELTA, conservatively assuming it is - dereferenced at all valid offsets. */ - if (loff == UNKNOWN_OFFSET) - { - delta = solution_set_expand (delta, expanded_delta); - loff = 0; - } - - /* For each member j of delta (Sol(x)), add an edge from y to j and - union Sol(y) into Sol(j) */ - EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) - { - varinfo_t v = get_varinfo (j); - unsigned int t; - HOST_WIDE_INT fieldoffset = v->offset + loff; - unsigned HOST_WIDE_INT size = v->size; - - if (v->is_full_var) - ; - else if (loff != 0) - { - if (fieldoffset < 0) - v = get_varinfo (v->head); - else - v = first_or_preceding_vi_for_offset (v, fieldoffset); - } - - /* We have to include all fields that overlap the current field - shifted by loff. */ - do - { - if (v->may_have_pointers) - { - /* If v is a global variable then this is an escape point. */ - if (v->is_global_var - && !escaped_p) - { - t = find (escaped_id); - if (add_graph_edge (graph, t, rhs) - && bitmap_ior_into (get_varinfo (t)->solution, sol)) - bitmap_set_bit (changed, t); - /* Enough to let rhs escape once. */ - escaped_p = true; - } - - if (v->is_special_var) - break; - - t = find (v->id); - - if (solve_add_graph_edge (graph, t, rhs)) - bitmap_set_bit (changed, t); - } - - if (v->is_full_var - || v->next == 0) - break; - - v = vi_next (v); - } - while (v->offset < fieldoffset + size); - } -} - -/* Handle a non-simple (simple meaning requires no iteration), - constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ - -static void -do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta, - bitmap *expanded_delta) -{ - if (c->lhs.type == DEREF) - { - if (c->rhs.type == ADDRESSOF) - { - gcc_unreachable (); - } - else - { - /* *x = y */ - do_ds_constraint (c, delta, expanded_delta); - } - } - else if (c->rhs.type == DEREF) - { - /* x = *y */ - if (!(get_varinfo (c->lhs.var)->is_special_var)) - do_sd_constraint (graph, c, delta, expanded_delta); - } - else - { - bitmap tmp; - bool flag = false; - - gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR - && c->rhs.offset != 0 && c->lhs.offset == 0); - tmp = get_varinfo (c->lhs.var)->solution; - - flag = set_union_with_increment (tmp, delta, c->rhs.offset, - expanded_delta); - - if (flag) - bitmap_set_bit (changed, c->lhs.var); - } -} - -/* Initialize and return a new SCC info structure. */ - -scc_info::scc_info (size_t size) : - visited (size), deleted (size), current_index (0), scc_stack (1) -{ - bitmap_clear (visited); - bitmap_clear (deleted); - node_mapping = XNEWVEC (unsigned int, size); - dfs = XCNEWVEC (unsigned int, size); - - for (size_t i = 0; i < size; i++) - node_mapping[i] = i; -} - -/* Free an SCC info structure pointed to by SI */ - -scc_info::~scc_info () -{ - free (node_mapping); - free (dfs); -} - - -/* 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. */ - -static void -find_indirect_cycles (constraint_graph_t graph) -{ - unsigned int i; - unsigned int size = graph->size; - scc_info si (size); - - for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) - if (!bitmap_bit_p (si.visited, i) && find (i) == i) - scc_visit (graph, &si, i); -} - -/* Visit the graph in topological order starting at node N, and store the - order in TOPO_ORDER using VISITED to indicate visited nodes. */ - -static void -topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order, - sbitmap visited, unsigned int n) -{ - bitmap_iterator bi; - unsigned int j; - - bitmap_set_bit (visited, n); - - if (graph->succs[n]) - EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) - { - unsigned k = find (j); - if (!bitmap_bit_p (visited, k)) - topo_visit (graph, topo_order, visited, k); - } - - /* Also consider copy with offset complex constraints as implicit edges. */ - for (auto c : graph->complex[n]) - { - /* Constraints are ordered so that SCALAR = SCALAR appear first. */ - if (c->lhs.type != SCALAR || c->rhs.type != SCALAR) - break; - gcc_checking_assert (c->rhs.var == n); - unsigned k = find (c->lhs.var); - if (!bitmap_bit_p (visited, k)) - topo_visit (graph, topo_order, visited, k); - } - - topo_order.quick_push (n); -} - -/* Compute a topological ordering for GRAPH, and return the result. */ - -static auto_vec<unsigned> -compute_topo_order (constraint_graph_t graph) -{ - unsigned int i; - unsigned int size = graph->size; - - auto_sbitmap visited (size); - bitmap_clear (visited); - - /* For the heuristic in add_graph_edge to work optimally make sure to - first visit the connected component of the graph containing - ESCAPED. Do this by extracting the connected component - with ESCAPED and append that to all other components as solve_graph - pops from the order. */ - auto_vec<unsigned> tail (size); - topo_visit (graph, tail, visited, find (escaped_id)); - - auto_vec<unsigned> topo_order (size); - - for (i = 0; i != size; ++i) - if (!bitmap_bit_p (visited, i) && find (i) == i) - topo_visit (graph, topo_order, visited, i); - - topo_order.splice (tail); - return topo_order; -} - -/* Structure used to for hash value numbering of pointer equivalence - classes. */ - -typedef struct equiv_class_label -{ - hashval_t hashcode; - unsigned int equivalence_class; - bitmap labels; -} *equiv_class_label_t; -typedef const struct equiv_class_label *const_equiv_class_label_t; - -/* Equiv_class_label hashtable helpers. */ - -struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label> -{ - static inline hashval_t hash (const equiv_class_label *); - static inline bool equal (const equiv_class_label *, - const equiv_class_label *); -}; - -/* Hash function for a equiv_class_label_t */ - -inline hashval_t -equiv_class_hasher::hash (const equiv_class_label *ecl) -{ - return ecl->hashcode; -} - -/* Equality function for two equiv_class_label_t's. */ - -inline bool -equiv_class_hasher::equal (const equiv_class_label *eql1, - const equiv_class_label *eql2) -{ - return (eql1->hashcode == eql2->hashcode - && bitmap_equal_p (eql1->labels, eql2->labels)); -} - -/* A hashtable for mapping a bitmap of labels->pointer equivalence - classes. */ -static hash_table<equiv_class_hasher> *pointer_equiv_class_table; - -/* A hashtable for mapping a bitmap of labels->location equivalence - classes. */ -static hash_table<equiv_class_hasher> *location_equiv_class_table; - -struct obstack equiv_class_obstack; - -/* 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. */ - -static equiv_class_label * -equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table, - bitmap labels) -{ - equiv_class_label **slot; - equiv_class_label ecl; - - ecl.labels = labels; - ecl.hashcode = bitmap_hash (labels); - slot = table->find_slot (&ecl, INSERT); - if (!*slot) - { - *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label); - (*slot)->labels = labels; - (*slot)->hashcode = ecl.hashcode; - (*slot)->equivalence_class = 0; - } - - return *slot; -} - -/* 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. */ -static int pointer_equiv_class; - -/* Current maximum location equivalence class id. */ -static int location_equiv_class; - -/* Recursive routine to find strongly connected components in GRAPH, - and label it's nodes with DFS numbers. */ - -static void -condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) -{ - unsigned int i; - bitmap_iterator bi; - unsigned int my_dfs; - - gcc_checking_assert (si->node_mapping[n] == n); - bitmap_set_bit (si->visited, n); - si->dfs[n] = si->current_index ++; - my_dfs = si->dfs[n]; - - /* Visit all the successors. */ - EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) - { - unsigned int w = si->node_mapping[i]; - - if (bitmap_bit_p (si->deleted, w)) - continue; - - if (!bitmap_bit_p (si->visited, w)) - condense_visit (graph, si, w); - - unsigned int t = si->node_mapping[w]; - gcc_checking_assert (si->node_mapping[n] == n); - if (si->dfs[t] < si->dfs[n]) - si->dfs[n] = si->dfs[t]; - } - - /* Visit all the implicit predecessors. */ - EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) - { - unsigned int w = si->node_mapping[i]; - - if (bitmap_bit_p (si->deleted, w)) - continue; - - if (!bitmap_bit_p (si->visited, w)) - condense_visit (graph, si, w); - - unsigned int t = si->node_mapping[w]; - gcc_assert (si->node_mapping[n] == n); - if (si->dfs[t] < si->dfs[n]) - si->dfs[n] = si->dfs[t]; - } - - /* See if any components have been identified. */ - if (si->dfs[n] == my_dfs) - { - if (si->scc_stack.length () != 0 - && si->dfs[si->scc_stack.last ()] >= my_dfs) - { - /* Find the first node of the SCC and do non-bitmap work. */ - bool direct_p = true; - unsigned first = si->scc_stack.length (); - do - { - --first; - unsigned int w = si->scc_stack[first]; - si->node_mapping[w] = n; - if (!bitmap_bit_p (graph->direct_nodes, w)) - direct_p = false; - } - while (first > 0 - && si->dfs[si->scc_stack[first - 1]] >= my_dfs); - if (!direct_p) - bitmap_clear_bit (graph->direct_nodes, n); - - /* Want to reduce to node n, push that first. */ - si->scc_stack.reserve (1); - si->scc_stack.quick_push (si->scc_stack[first]); - si->scc_stack[first] = n; - - unsigned scc_size = si->scc_stack.length () - first; - unsigned split = scc_size / 2; - unsigned carry = scc_size - split * 2; - while (split > 0) - { - for (unsigned i = 0; i < split; ++i) - { - unsigned a = si->scc_stack[first + i]; - unsigned b = si->scc_stack[first + split + carry + i]; - - /* Unify our nodes. */ - if (graph->preds[b]) - { - if (!graph->preds[a]) - std::swap (graph->preds[a], graph->preds[b]); - else - bitmap_ior_into_and_free (graph->preds[a], - &graph->preds[b]); - } - if (graph->implicit_preds[b]) - { - if (!graph->implicit_preds[a]) - std::swap (graph->implicit_preds[a], - graph->implicit_preds[b]); - else - bitmap_ior_into_and_free (graph->implicit_preds[a], - &graph->implicit_preds[b]); - } - if (graph->points_to[b]) - { - if (!graph->points_to[a]) - std::swap (graph->points_to[a], graph->points_to[b]); - else - bitmap_ior_into_and_free (graph->points_to[a], - &graph->points_to[b]); - } - } - unsigned remain = split + carry; - split = remain / 2; - carry = remain - split * 2; - } - /* Actually pop the SCC. */ - si->scc_stack.truncate (first); - } - bitmap_set_bit (si->deleted, n); - } - else - si->scc_stack.safe_push (n); -} - -/* 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. */ - -static void -label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) -{ - unsigned int i, first_pred; - bitmap_iterator bi; - - bitmap_set_bit (si->visited, n); - - /* Label and union our incoming edges's points to sets. */ - first_pred = -1U; - EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) - { - unsigned int w = si->node_mapping[i]; - if (!bitmap_bit_p (si->visited, w)) - label_visit (graph, si, w); - - /* Skip unused edges */ - if (w == n || graph->pointer_label[w] == 0) - continue; - - if (graph->points_to[w]) - { - if (!graph->points_to[n]) - { - if (first_pred == -1U) - first_pred = w; - else - { - graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); - bitmap_ior (graph->points_to[n], - graph->points_to[first_pred], - graph->points_to[w]); - } - } - else - bitmap_ior_into (graph->points_to[n], graph->points_to[w]); - } - } - - /* Indirect nodes get fresh variables and a new pointer equiv class. */ - if (!bitmap_bit_p (graph->direct_nodes, n)) - { - if (!graph->points_to[n]) - { - graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); - if (first_pred != -1U) - bitmap_copy (graph->points_to[n], graph->points_to[first_pred]); - } - bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); - graph->pointer_label[n] = pointer_equiv_class++; - equiv_class_label_t ecl; - ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, - graph->points_to[n]); - ecl->equivalence_class = graph->pointer_label[n]; - return; - } - - /* If there was only a single non-empty predecessor the pointer equiv - class is the same. */ - if (!graph->points_to[n]) - { - if (first_pred != -1U) - { - graph->pointer_label[n] = graph->pointer_label[first_pred]; - graph->points_to[n] = graph->points_to[first_pred]; - } - return; - } - - if (!bitmap_empty_p (graph->points_to[n])) - { - equiv_class_label_t ecl; - ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, - graph->points_to[n]); - if (ecl->equivalence_class == 0) - ecl->equivalence_class = pointer_equiv_class++; - else - { - BITMAP_FREE (graph->points_to[n]); - graph->points_to[n] = ecl->labels; - } - graph->pointer_label[n] = ecl->equivalence_class; - } -} - -/* Print the pred graph in dot format. */ - -static void -dump_pred_graph (class scc_info *si, FILE *file) -{ - unsigned int i; - - /* Only print the graph if it has already been initialized: */ - if (!graph) - return; - - /* Prints the header of the dot file: */ - fprintf (file, "strict digraph {\n"); - fprintf (file, " node [\n shape = box\n ]\n"); - fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); - fprintf (file, "\n // List of nodes and complex constraints in " - "the constraint graph:\n"); - - /* The next lines print the nodes in the graph together with the - complex constraints attached to them. */ - for (i = 1; i < graph->size; i++) - { - if (i == FIRST_REF_NODE) - continue; - if (si->node_mapping[i] != i) - continue; - if (i < FIRST_REF_NODE) - fprintf (file, "\"%s\"", get_varinfo (i)->name); - else - fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); - if (graph->points_to[i] - && !bitmap_empty_p (graph->points_to[i])) - { - if (i < FIRST_REF_NODE) - fprintf (file, "[label=\"%s = {", get_varinfo (i)->name); - else - fprintf (file, "[label=\"*%s = {", - get_varinfo (i - FIRST_REF_NODE)->name); - unsigned j; - bitmap_iterator bi; - EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi) - fprintf (file, " %d", j); - fprintf (file, " }\"]"); - } - fprintf (file, ";\n"); - } - - /* Go over the edges. */ - fprintf (file, "\n // Edges in the constraint graph:\n"); - for (i = 1; i < graph->size; i++) - { - unsigned j; - bitmap_iterator bi; - if (si->node_mapping[i] != i) - continue; - EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi) - { - unsigned from = si->node_mapping[j]; - if (from < FIRST_REF_NODE) - fprintf (file, "\"%s\"", get_varinfo (from)->name); - else - fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name); - fprintf (file, " -> "); - if (i < FIRST_REF_NODE) - fprintf (file, "\"%s\"", get_varinfo (i)->name); - else - fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); - fprintf (file, ";\n"); - } - } - - /* Prints the tail of the dot file. */ - fprintf (file, "}\n"); -} - -/* Perform offline variable substitution, discovering equivalence - classes, and eliminating non-pointer variables. */ - -static class scc_info * -perform_var_substitution (constraint_graph_t graph) -{ - unsigned int i; - unsigned int size = graph->size; - scc_info *si = new scc_info (size); - - bitmap_obstack_initialize (&iteration_obstack); - gcc_obstack_init (&equiv_class_obstack); - pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511); - location_equiv_class_table - = new hash_table<equiv_class_hasher> (511); - pointer_equiv_class = 1; - location_equiv_class = 1; - - /* Condense the nodes, which means to find SCC's, count incoming - predecessors, and unite nodes in SCC's. */ - for (i = 1; i < FIRST_REF_NODE; i++) - if (!bitmap_bit_p (si->visited, si->node_mapping[i])) - condense_visit (graph, si, si->node_mapping[i]); - - if (dump_file && (dump_flags & TDF_GRAPH)) - { - fprintf (dump_file, "\n\n// The constraint graph before var-substitution " - "in dot format:\n"); - dump_pred_graph (si, dump_file); - fprintf (dump_file, "\n\n"); - } - - bitmap_clear (si->visited); - /* Actually the label the nodes for pointer equivalences */ - for (i = 1; i < FIRST_REF_NODE; i++) - if (!bitmap_bit_p (si->visited, si->node_mapping[i])) - label_visit (graph, si, si->node_mapping[i]); - - /* Calculate location equivalence labels. */ - for (i = 1; i < FIRST_REF_NODE; i++) - { - bitmap pointed_by; - bitmap_iterator bi; - unsigned int j; - - if (!graph->pointed_by[i]) - continue; - pointed_by = BITMAP_ALLOC (&iteration_obstack); - - /* Translate the pointed-by mapping for pointer equivalence - labels. */ - EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) - { - bitmap_set_bit (pointed_by, - graph->pointer_label[si->node_mapping[j]]); - } - /* The original pointed_by is now dead. */ - BITMAP_FREE (graph->pointed_by[i]); - - /* Look up the location equivalence label if one exists, or make - one otherwise. */ - equiv_class_label_t ecl; - ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by); - if (ecl->equivalence_class == 0) - ecl->equivalence_class = location_equiv_class++; - else - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Found location equivalence for node %s\n", - get_varinfo (i)->name); - BITMAP_FREE (pointed_by); - } - graph->loc_label[i] = ecl->equivalence_class; - - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - for (i = 1; i < FIRST_REF_NODE; i++) - { - unsigned j = si->node_mapping[i]; - if (j != i) - { - fprintf (dump_file, "%s node id %d ", - bitmap_bit_p (graph->direct_nodes, i) - ? "Direct" : "Indirect", i); - if (i < FIRST_REF_NODE) - fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); - else - fprintf (dump_file, "\"*%s\"", - get_varinfo (i - FIRST_REF_NODE)->name); - fprintf (dump_file, " mapped to SCC leader node id %d ", j); - if (j < FIRST_REF_NODE) - fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name); - else - fprintf (dump_file, "\"*%s\"\n", - get_varinfo (j - FIRST_REF_NODE)->name); - } - else - { - fprintf (dump_file, - "Equivalence classes for %s node id %d ", - bitmap_bit_p (graph->direct_nodes, i) - ? "direct" : "indirect", i); - if (i < FIRST_REF_NODE) - fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); - else - fprintf (dump_file, "\"*%s\"", - get_varinfo (i - FIRST_REF_NODE)->name); - fprintf (dump_file, - ": pointer %d, location %d\n", - graph->pointer_label[i], graph->loc_label[i]); - } - } - - /* Quickly eliminate our non-pointer variables. */ - - for (i = 1; i < FIRST_REF_NODE; i++) - { - unsigned int node = si->node_mapping[i]; - - if (graph->pointer_label[node] == 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "%s is a non-pointer variable, eliminating edges.\n", - get_varinfo (node)->name); - stats.nonpointer_vars++; - clear_edges_for_node (graph, node); - } - } - - return si; -} - -/* Free information that was only necessary for variable - substitution. */ - -static void -free_var_substitution_info (class scc_info *si) -{ - delete si; - free (graph->pointer_label); - free (graph->loc_label); - free (graph->pointed_by); - free (graph->points_to); - free (graph->eq_rep); - sbitmap_free (graph->direct_nodes); - delete pointer_equiv_class_table; - pointer_equiv_class_table = NULL; - delete location_equiv_class_table; - location_equiv_class_table = NULL; - obstack_free (&equiv_class_obstack, NULL); - bitmap_obstack_release (&iteration_obstack); -} - -/* Return an existing node that is equivalent to NODE, which has - equivalence class LABEL, if one exists. Return NODE otherwise. */ - -static unsigned int -find_equivalent_node (constraint_graph_t graph, - unsigned int node, unsigned int label) -{ - /* If the address version of this variable is unused, we can - substitute it for anything else with the same label. - Otherwise, we know the pointers are equivalent, but not the - locations, and we can unite them later. */ - - if (!bitmap_bit_p (graph->address_taken, node)) - { - gcc_checking_assert (label < graph->size); - - if (graph->eq_rep[label] != -1) - { - /* Unify the two variables since we know they are equivalent. */ - if (unite (graph->eq_rep[label], node)) - unify_nodes (graph, graph->eq_rep[label], node, false); - return graph->eq_rep[label]; - } - else - { - graph->eq_rep[label] = node; - graph->pe_rep[label] = node; - } - } - else - { - gcc_checking_assert (label < graph->size); - graph->pe[node] = label; - if (graph->pe_rep[label] == -1) - graph->pe_rep[label] = node; - } - - return node; -} - -/* Unite pointer equivalent but not location equivalent nodes in - GRAPH. This may only be performed once variable substitution is - finished. */ - -static void -unite_pointer_equivalences (constraint_graph_t graph) -{ - unsigned int i; - - /* Go through the pointer equivalences and unite them to their - representative, if they aren't already. */ - for (i = 1; i < FIRST_REF_NODE; i++) - { - unsigned int label = graph->pe[i]; - if (label) - { - int label_rep = graph->pe_rep[label]; - - if (label_rep == -1) - continue; - - label_rep = find (label_rep); - if (label_rep >= 0 && unite (label_rep, find (i))) - unify_nodes (graph, label_rep, i, false); - } - } -} - -/* Move complex constraints to the GRAPH nodes they belong to. */ - -static void -move_complex_constraints (constraint_graph_t graph) -{ - int i; - constraint_t c; - - FOR_EACH_VEC_ELT (constraints, i, c) - { - if (c) - { - struct constraint_expr lhs = c->lhs; - struct constraint_expr rhs = c->rhs; - - if (lhs.type == DEREF) - { - insert_into_complex (graph, lhs.var, c); - } - else if (rhs.type == DEREF) - { - if (!(get_varinfo (lhs.var)->is_special_var)) - insert_into_complex (graph, rhs.var, c); - } - else if (rhs.type != ADDRESSOF && lhs.var > anything_id - && (lhs.offset != 0 || rhs.offset != 0)) - { - insert_into_complex (graph, rhs.var, c); - } - } - } -} - - -/* Optimize and rewrite complex constraints while performing - collapsing of equivalent nodes. SI is the SCC_INFO that is the - result of perform_variable_substitution. */ - -static void -rewrite_constraints (constraint_graph_t graph, - class scc_info *si) -{ - int i; - constraint_t c; - - if (flag_checking) - { - for (unsigned int j = 0; j < graph->size; j++) - gcc_assert (find (j) == j); - } - - FOR_EACH_VEC_ELT (constraints, i, c) - { - struct constraint_expr lhs = c->lhs; - struct constraint_expr rhs = c->rhs; - unsigned int lhsvar = find (lhs.var); - unsigned int rhsvar = find (rhs.var); - unsigned int lhsnode, rhsnode; - unsigned int lhslabel, rhslabel; - - lhsnode = si->node_mapping[lhsvar]; - rhsnode = si->node_mapping[rhsvar]; - lhslabel = graph->pointer_label[lhsnode]; - rhslabel = graph->pointer_label[rhsnode]; - - /* See if it is really a non-pointer variable, and if so, ignore - the constraint. */ - if (lhslabel == 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - - fprintf (dump_file, "%s is a non-pointer variable, " - "ignoring constraint:", - get_varinfo (lhs.var)->name); - dump_constraint (dump_file, c); - fprintf (dump_file, "\n"); - } - constraints[i] = NULL; - continue; - } - - if (rhslabel == 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - - fprintf (dump_file, "%s is a non-pointer variable, " - "ignoring constraint:", - get_varinfo (rhs.var)->name); - dump_constraint (dump_file, c); - fprintf (dump_file, "\n"); - } - constraints[i] = NULL; - continue; - } - - lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); - rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); - c->lhs.var = lhsvar; - c->rhs.var = rhsvar; - } -} - -/* Eliminate indirect cycles involving NODE. Return true if NODE was - part of an SCC, false otherwise. */ - -static bool -eliminate_indirect_cycles (unsigned int node) -{ - if (graph->indirect_cycles[node] != -1 - && !bitmap_empty_p (get_varinfo (node)->solution)) - { - unsigned int i; - auto_vec<unsigned> queue; - int queuepos; - unsigned int to = find (graph->indirect_cycles[node]); - bitmap_iterator bi; - - /* We can't touch the solution set and call unify_nodes - at the same time, because unify_nodes is going to do - bitmap unions into it. */ - - EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) - { - if (find (i) == i && i != to) - { - if (unite (to, i)) - queue.safe_push (i); - } - } - - for (queuepos = 0; - queue.iterate (queuepos, &i); - queuepos++) - { - unify_nodes (graph, to, i, true); - } - return true; - } - return false; -} - -/* 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. */ - -static void -solve_graph (constraint_graph_t graph) -{ - unsigned int size = graph->size; - unsigned int i; - bitmap pts; - - changed = BITMAP_ALLOC (NULL); - - /* Mark all initial non-collapsed nodes as changed. */ - for (i = 1; i < size; i++) - { - varinfo_t ivi = get_varinfo (i); - if (find (i) == i && !bitmap_empty_p (ivi->solution) - && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) - || graph->complex[i].length () > 0)) - bitmap_set_bit (changed, i); - } - - /* Allocate a bitmap to be used to store the changed bits. */ - pts = BITMAP_ALLOC (&pta_obstack); - - while (!bitmap_empty_p (changed)) - { - unsigned int i; - stats.iterations++; - - bitmap_obstack_initialize (&iteration_obstack); - - auto_vec<unsigned> topo_order = compute_topo_order (graph); - while (topo_order.length () != 0) - { - i = topo_order.pop (); - - /* If this variable is not a representative, skip it. */ - if (find (i) != i) - continue; - - /* In certain indirect cycle cases, we may merge this - variable to another. */ - if (eliminate_indirect_cycles (i) && find (i) != i) - continue; - - /* If the node has changed, we need to process the - complex constraints and outgoing edges again. For complex - constraints that modify i itself, like the common group of - callarg = callarg + UNKNOWN; - callarg = *callarg + UNKNOWN; - *callarg = callescape; - make sure to iterate immediately because that maximizes - cache reuse and expands the graph quickest, leading to - better visitation order in the next iteration. */ - while (bitmap_clear_bit (changed, i)) - { - bitmap solution; - vec<constraint_t> &complex = graph->complex[i]; - varinfo_t vi = get_varinfo (i); - bool solution_empty; - - /* Compute the changed set of solution bits. If anything - is in the solution just propagate that. */ - if (bitmap_bit_p (vi->solution, anything_id)) - { - /* If anything is also in the old solution there is - nothing to do. - ??? But we shouldn't ended up with "changed" set ... */ - if (vi->oldsolution - && bitmap_bit_p (vi->oldsolution, anything_id)) - break; - bitmap_copy (pts, get_varinfo (find (anything_id))->solution); - } - else if (vi->oldsolution) - bitmap_and_compl (pts, vi->solution, vi->oldsolution); - else - bitmap_copy (pts, vi->solution); - - if (bitmap_empty_p (pts)) - break; - - if (vi->oldsolution) - bitmap_ior_into (vi->oldsolution, pts); - else - { - vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack); - bitmap_copy (vi->oldsolution, pts); - } - - solution = vi->solution; - solution_empty = bitmap_empty_p (solution); - - /* Process the complex constraints */ - hash_set<constraint_t> *cvisited = nullptr; - if (flag_checking) - cvisited = new hash_set<constraint_t>; - bitmap expanded_pts = NULL; - for (unsigned j = 0; j < complex.length (); ++j) - { - constraint_t c = complex[j]; - /* At unification time only the directly involved nodes - will get their complex constraints updated. Update - our complex constraints now but keep the constraint - vector sorted and clear of duplicates. Also make - sure to evaluate each prevailing constraint only once. */ - unsigned int new_lhs = find (c->lhs.var); - unsigned int new_rhs = find (c->rhs.var); - if (c->lhs.var != new_lhs || c->rhs.var != new_rhs) - { - constraint tem = *c; - tem.lhs.var = new_lhs; - tem.rhs.var = new_rhs; - unsigned int place - = complex.lower_bound (&tem, constraint_less); - c->lhs.var = new_lhs; - c->rhs.var = new_rhs; - if (place != j) - { - complex.ordered_remove (j); - if (j < place) - --place; - if (place < complex.length ()) - { - if (constraint_equal (*complex[place], *c)) - { - j--; - continue; - } - else - complex.safe_insert (place, c); - } - else - complex.quick_push (c); - if (place > j) - { - j--; - continue; - } - } - } - - /* The only complex constraint that can change our - solution to non-empty, given an empty solution, - is a constraint where the lhs side is receiving - some set from elsewhere. */ - if (cvisited && cvisited->add (c)) - gcc_unreachable (); - if (!solution_empty || c->lhs.type != DEREF) - do_complex_constraint (graph, c, pts, &expanded_pts); - } - if (cvisited) - { - /* When checking, verify the order of constraints is - maintained and each constraint is evaluated exactly - once. */ - for (unsigned j = 1; j < complex.length (); ++j) - gcc_assert (constraint_less (complex[j-1], complex[j])); - gcc_assert (cvisited->elements () == complex.length ()); - delete cvisited; - } - BITMAP_FREE (expanded_pts); - - solution_empty = bitmap_empty_p (solution); - - if (!solution_empty) - { - bitmap_iterator bi; - unsigned eff_escaped_id = find (escaped_id); - unsigned j; - - /* Propagate solution to all successors. */ - unsigned to_remove = ~0U; - EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], - 0, j, bi) - { - if (to_remove != ~0U) - { - bitmap_clear_bit (graph->succs[i], to_remove); - to_remove = ~0U; - } - unsigned int to = find (j); - if (to != j) - { - /* Update the succ graph, avoiding duplicate - work. */ - to_remove = j; - if (! bitmap_set_bit (graph->succs[i], to)) - continue; - /* We eventually end up processing 'to' twice - as it is undefined whether bitmap iteration - iterates over bits set during iteration. - Play safe instead of doing tricks. */ - } - /* Don't try to propagate to ourselves. */ - if (to == i) - { - to_remove = j; - continue; - } - /* Early node unification can lead to edges from - escaped - remove them. */ - if (i == eff_escaped_id) - { - to_remove = j; - if (bitmap_set_bit (get_varinfo (to)->solution, - escaped_id)) - bitmap_set_bit (changed, to); - continue; - } - - if (bitmap_ior_into (get_varinfo (to)->solution, pts)) - bitmap_set_bit (changed, to); - } - if (to_remove != ~0U) - bitmap_clear_bit (graph->succs[i], to_remove); - } - } - } - bitmap_obstack_release (&iteration_obstack); - } - - BITMAP_FREE (pts); - BITMAP_FREE (changed); - bitmap_obstack_release (&oldpta_obstack); -} - -/* Map from trees to variable infos. */ -static hash_map<tree, varinfo_t> *vi_for_tree; - - /* Insert ID as the variable id for tree T in the vi_for_tree map. */ static void @@ -3003,7 +734,7 @@ lookup_vi_for_tree (tree t) return *slot; } -/* Return a printable name for DECL */ +/* Return a printable name for DECL. */ static const char * alias_get_name (tree decl) @@ -3191,10 +922,10 @@ process_constraint (constraint_t t) if (!get_varinfo (lhs.var)->may_have_pointers) return; - /* This can happen in our IR with things like n->a = *p */ + /* This can happen in our IR with things like n->a = *p. */ if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) { - /* Split into tmp = *rhs, *lhs = tmp */ + /* Split into tmp = *rhs, *lhs = tmp. */ struct constraint_expr tmplhs; tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true); process_constraint (new_constraint (tmplhs, rhs)); @@ -3202,7 +933,7 @@ process_constraint (constraint_t t) } else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF) { - /* Split into tmp = &rhs, *lhs = tmp */ + /* Split into tmp = &rhs, *lhs = tmp. */ struct constraint_expr tmplhs; tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true); process_constraint (new_constraint (tmplhs, rhs)); @@ -3370,7 +1101,7 @@ get_constraint_for_component_ref (tree t, vec<ce_s> *results, tree forzero; /* Some people like to do cute things like take the address of - &0->a.b */ + &0->a.b. */ forzero = t; while (handled_component_p (forzero) || INDIRECT_REF_P (forzero) @@ -3444,7 +1175,7 @@ get_constraint_for_component_ref (tree t, vec<ce_s> *results, { /* In languages like C, you can access one past the end of an array. You aren't allowed to dereference it, so we can - ignore this constraint. When we handle pointer subtraction, + ignore this constraint. When we handle pointer subtraction, we may have to do something cute here. */ if (maybe_lt (poly_uint64 (bitpos), get_varinfo (result.var)->fullsize) @@ -3481,7 +1212,7 @@ get_constraint_for_component_ref (tree t, vec<ce_s> *results, results->safe_push (cexpr); } else if (results->length () == 0) - /* Assert that we found *some* field there. The user couldn't be + /* Assert that we found *some* field there. The user couldn't be accessing *only* padding. */ /* Still the user could access one past the end of an array embedded in a struct resulting in accessing *only* padding. */ @@ -3535,7 +1266,7 @@ get_constraint_for_component_ref (tree t, vec<ce_s> *results, /* Dereference the constraint expression CONS, and return the result. DEREF (ADDRESSOF) = SCALAR DEREF (SCALAR) = DEREF - DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) + DEREF (DEREF) = (temp = DEREF1; result = DEREF (temp)) This is needed so that we can handle dereferencing DEREF constraints. */ static void @@ -3594,7 +1325,7 @@ get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p, point to anything by itself. That is, of course, unless it is an integer constant being treated as a pointer, in which case, we will return that this is really the addressof anything. This - happens below, since it will fall into the default case. The only + happens below, since it will fall into the default case. The only case we know something about an integer treated like a pointer is when it is the NULL pointer, and then we just say it points to NULL. @@ -3745,7 +1476,7 @@ get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p, tmp.truncate (0); } /* We do not know whether the constructor was complete, - so technically we have to add &NOTHING or &ANYTHING + so technically we have to add &NOTHING or &ANYTHING like we do for an empty constructor as well. */ return; } @@ -4144,7 +1875,7 @@ get_function_part_constraint (varinfo_t fi, unsigned part) /* 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. */ + WRITES_GLOVEL_MEMORY is true if callee may write global memory. */ static void handle_call_arg (gcall *stmt, tree arg, vec<ce_s> *results, int flags, @@ -4510,7 +2241,7 @@ handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> &rhsc, rhsc.truncate (0); vi = make_heapvar ("HEAP", true); /* We are marking allocated storage local, we deal with it becoming - global by escaping and setting of vars_contains_escaped_heap. */ + global by escaping and setting of vars_contains_escaped_heap. */ DECL_EXTERNAL (vi->decl) = 0; vi->is_global_var = 0; /* If this is not a real malloc call assume the memory was @@ -4698,8 +2429,8 @@ find_func_aliases_for_builtin_call (struct function *fn, gcall *t) } case BUILT_IN_STACK_SAVE: case BUILT_IN_STACK_RESTORE: - /* Nothing interesting happens. */ - return true; + /* Nothing interesting happens. */ + return true; case BUILT_IN_ALLOCA: case BUILT_IN_ALLOCA_WITH_ALIGN: case BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX: @@ -4723,7 +2454,7 @@ find_func_aliases_for_builtin_call (struct function *fn, gcall *t) return true; } case BUILT_IN_POSIX_MEMALIGN: - { + { tree ptrptr = gimple_call_arg (t, 0); get_constraint_for (ptrptr, &lhsc); do_deref (&lhsc); @@ -4806,7 +2537,7 @@ find_func_aliases_for_builtin_call (struct function *fn, gcall *t) } break; /* String / character search functions return a pointer into the - source string or NULL. */ + source string or NULL. */ case BUILT_IN_INDEX: case BUILT_IN_STRCHR: case BUILT_IN_STRRCHR: @@ -4827,7 +2558,7 @@ find_func_aliases_for_builtin_call (struct function *fn, gcall *t) } return true; /* Pure functions that return something not based on any object and - that use the memory pointed to by their arguments (but not + that use the memory pointed to by their arguments (but not transitively). */ case BUILT_IN_STRCMP: case BUILT_IN_STRCMP_EQ: @@ -5192,7 +2923,7 @@ find_func_aliases (struct function *fn, gimple *origt) } } /* In IPA mode, we need to generate constraints to pass call - arguments through their calls. There are two cases, + arguments through their calls. There are two cases, either a GIMPLE_CALL returning a value, or just a plain GIMPLE_CALL when we are not. @@ -5337,7 +3068,7 @@ find_func_aliases (struct function *fn, gimple *origt) constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); oconstraints[i] = constraint; parse_output_constraint (&constraint, i, 0, 0, &allows_mem, - &allows_reg, &is_inout); + &allows_reg, &is_inout, nullptr); /* A memory constraint makes the address of the operand escape. */ if (!allows_reg && allows_mem) @@ -5370,7 +3101,7 @@ find_func_aliases (struct function *fn, gimple *origt) constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints, - &allows_mem, &allows_reg); + &allows_mem, &allows_reg, nullptr); /* A memory constraint makes the address of the operand escape. */ if (!allows_reg && allows_mem) @@ -5445,7 +3176,7 @@ find_func_clobbers (struct function *fn, gimple *origt) || (TREE_CODE (tem) == MEM_REF && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR && auto_var_in_fn_p - (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl)))) + (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl)))) { struct constraint_expr lhsc, *rhsp; unsigned i; @@ -5474,7 +3205,7 @@ find_func_clobbers (struct function *fn, gimple *origt) || (TREE_CODE (tem) == MEM_REF && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR && auto_var_in_fn_p - (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl)))) + (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl)))) { struct constraint_expr lhs, *rhsp; unsigned i; @@ -5786,65 +3517,6 @@ find_func_clobbers (struct function *fn, gimple *origt) } -/* Find the first varinfo in the same variable as START that overlaps with - OFFSET. Return NULL if we can't find one. */ - -static varinfo_t -first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) -{ - /* If the offset is outside of the variable, bail out. */ - if (offset >= start->fullsize) - return NULL; - - /* If we cannot reach offset from start, lookup the first field - and start from there. */ - if (start->offset > offset) - start = get_varinfo (start->head); - - while (start) - { - /* We may not find a variable in the field list with the actual - offset when we have glommed a structure to a variable. - In that case, however, offset should still be within the size - of the variable. */ - if (offset >= start->offset - && (offset - start->offset) < start->size) - return start; - - start = vi_next (start); - } - - return NULL; -} - -/* 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. */ - -static varinfo_t -first_or_preceding_vi_for_offset (varinfo_t start, - unsigned HOST_WIDE_INT offset) -{ - /* If we cannot reach offset from start, lookup the first field - and start from there. */ - if (start->offset > offset) - start = get_varinfo (start->head); - - /* We may not find a variable in the field list with the actual - offset when we have glommed a structure to a variable. - In that case, however, offset should still be within the size - of the variable. - If we got beyond the offset we look for return the field - directly preceding offset which may be the last field. */ - while (start->next - && offset >= start->offset - && !((offset - start->offset) < start->size)) - start = vi_next (start); - - return start; -} - - /* This structure is used during pushing fields onto the fieldstack to track the offset of the field, since bitpos_of_field gives it relative to its immediate containing type, and we want it relative @@ -5871,7 +3543,7 @@ struct fieldoff typedef struct fieldoff fieldoff_s; -/* qsort comparison function for two fieldoff's PA and PB */ +/* qsort comparison function for two fieldoff's PA and PB. */ static int fieldoff_compare (const void *pa, const void *pb) @@ -6599,38 +4271,6 @@ create_variable_info_for (tree decl, const char *name, bool add_id) return id; } -/* Print out the points-to solution for VAR to FILE. */ - -static void -dump_solution_for_var (FILE *file, unsigned int var) -{ - varinfo_t vi = get_varinfo (var); - unsigned int i; - bitmap_iterator bi; - - /* Dump the solution for unified vars anyway, this avoids difficulties - in scanning dumps in the testsuite. */ - fprintf (file, "%s = { ", vi->name); - vi = get_varinfo (find (var)); - EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) - fprintf (file, "%s ", get_varinfo (i)->name); - fprintf (file, "}"); - - /* But note when the variable was unified. */ - if (vi->id != var) - fprintf (file, " same as %s", vi->name); - - fprintf (file, "\n"); -} - -/* Print the points-to solution for VAR to stderr. */ - -DEBUG_FUNCTION void -debug_solution_for_var (unsigned int var) -{ - dump_solution_for_var (stderr, var); -} - /* Register the constraints for function parameter related VI. */ static void @@ -6718,7 +4358,7 @@ struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info> const shared_bitmap_info *); }; -/* Hash function for a shared_bitmap_info_t */ +/* Hash function for a shared_bitmap_info_t. */ inline hashval_t shared_bitmap_hasher::hash (const shared_bitmap_info *bi) @@ -6726,7 +4366,7 @@ shared_bitmap_hasher::hash (const shared_bitmap_info *bi) return bi->hashcode; } -/* Equality function for two shared_bitmap_info_t's. */ +/* Equality function for two shared_bitmap_info_t's. */ inline bool shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1, @@ -6784,8 +4424,8 @@ set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt, { unsigned int i; bitmap_iterator bi; - varinfo_t escaped_vi = get_varinfo (find (escaped_id)); - varinfo_t escaped_return_vi = get_varinfo (find (escaped_return_id)); + varinfo_t escaped_vi = get_varinfo (var_rep[escaped_id]); + varinfo_t escaped_return_vi = get_varinfo (var_rep[escaped_return_id]); bool everything_escaped = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id); @@ -6883,7 +4523,7 @@ find_what_var_points_to (tree fndecl, varinfo_t orig_vi) /* This variable may have been collapsed, let's get the real variable. */ - vi = get_varinfo (find (orig_vi->id)); + vi = get_varinfo (var_rep[orig_vi->id]); /* See if we have already computed the solution and return it. */ pt_solution **slot = &final_solutions->get_or_insert (vi); @@ -6910,7 +4550,7 @@ find_what_var_points_to (tree fndecl, varinfo_t orig_vi) else pt->escaped = 1; /* Expand some special vars of ESCAPED in-place here. */ - varinfo_t evi = get_varinfo (find (escaped_id)); + varinfo_t evi = get_varinfo (var_rep[escaped_id]); if (bitmap_bit_p (evi->solution, nonlocal_id)) pt->nonlocal = 1; } @@ -7137,7 +4777,7 @@ pt_solution_includes_global (struct pt_solution *pt, bool escaped_local_p) || pt->nonlocal || pt->vars_contains_nonlocal /* The following is a hack to make the malloc escape hack work. - In reality we'd need different sets for escaped-through-return + In reality we'd need different sets for escaped-through-return and escaped-to-callees and passes would need to be updated. */ || pt->vars_contains_escaped_heap) return true; @@ -7273,52 +4913,6 @@ pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2) return res; } -/* Dump stats information to OUTFILE. */ - -static void -dump_sa_stats (FILE *outfile) -{ - fprintf (outfile, "Points-to Stats:\n"); - fprintf (outfile, "Total vars: %d\n", stats.total_vars); - fprintf (outfile, "Non-pointer vars: %d\n", - stats.nonpointer_vars); - fprintf (outfile, "Statically unified vars: %d\n", - stats.unified_vars_static); - fprintf (outfile, "Dynamically unified vars: %d\n", - stats.unified_vars_dynamic); - fprintf (outfile, "Iterations: %d\n", stats.iterations); - fprintf (outfile, "Number of edges: %d\n", stats.num_edges); - fprintf (outfile, "Number of implicit edges: %d\n", - stats.num_implicit_edges); - fprintf (outfile, "Number of avoided edges: %d\n", - stats.num_avoided_edges); -} - -/* Dump points-to information to OUTFILE. */ - -static void -dump_sa_points_to_info (FILE *outfile) -{ - fprintf (outfile, "\nPoints-to sets\n\n"); - - for (unsigned i = 1; i < varmap.length (); i++) - { - varinfo_t vi = get_varinfo (i); - if (!vi->may_have_pointers) - continue; - dump_solution_for_var (outfile, i); - } -} - - -/* Debug points-to information to stderr. */ - -DEBUG_FUNCTION void -debug_sa_points_to_info (void) -{ - dump_sa_points_to_info (stderr); -} - /* Initialize the always-existing constraint variables for NULL ANYTHING, READONLY, and INTEGER */ @@ -7511,7 +5105,7 @@ init_base_vars (void) process_constraint (new_constraint (lhs, rhs)); } -/* Initialize things necessary to perform PTA */ +/* Initialize things necessary to perform PTA. */ static void init_alias_vars (void) @@ -7520,7 +5114,6 @@ init_alias_vars (void) bitmap_obstack_initialize (&pta_obstack); bitmap_obstack_initialize (&oldpta_obstack); - bitmap_obstack_initialize (&predbitmap_obstack); constraints.create (8); varmap.create (8); @@ -7537,144 +5130,6 @@ init_alias_vars (void) gcc_obstack_init (&final_solutions_obstack); } -/* Remove the REF and ADDRESS edges from GRAPH, as well as all the - predecessor edges. */ - -static void -remove_preds_and_fake_succs (constraint_graph_t graph) -{ - unsigned int i; - - /* Clear the implicit ref and address nodes from the successor - lists. */ - for (i = 1; i < FIRST_REF_NODE; i++) - { - if (graph->succs[i]) - bitmap_clear_range (graph->succs[i], FIRST_REF_NODE, - FIRST_REF_NODE * 2); - } - - /* Free the successor list for the non-ref nodes. */ - for (i = FIRST_REF_NODE + 1; i < graph->size; i++) - { - if (graph->succs[i]) - BITMAP_FREE (graph->succs[i]); - } - - /* Now reallocate the size of the successor list as, and blow away - the predecessor bitmaps. */ - graph->size = varmap.length (); - graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size); - - free (graph->implicit_preds); - graph->implicit_preds = NULL; - free (graph->preds); - graph->preds = NULL; - bitmap_obstack_release (&predbitmap_obstack); -} - -/* Solve the constraint set. */ - -static void -solve_constraints (void) -{ - class scc_info *si; - - /* Sort varinfos so that ones that cannot be pointed to are last. - This makes bitmaps more efficient. */ - unsigned int *map = XNEWVEC (unsigned int, varmap.length ()); - for (unsigned i = 0; i < integer_id + 1; ++i) - map[i] = i; - /* Start with address-taken vars, followed by not address-taken vars - to move vars never appearing in the points-to solution bitmaps last. */ - unsigned j = integer_id + 1; - for (unsigned i = integer_id + 1; i < varmap.length (); ++i) - if (varmap[varmap[i]->head]->address_taken) - map[i] = j++; - for (unsigned i = integer_id + 1; i < varmap.length (); ++i) - if (! varmap[varmap[i]->head]->address_taken) - map[i] = j++; - /* Shuffle varmap according to map. */ - for (unsigned i = integer_id + 1; i < varmap.length (); ++i) - { - while (map[varmap[i]->id] != i) - std::swap (varmap[i], varmap[map[varmap[i]->id]]); - gcc_assert (bitmap_empty_p (varmap[i]->solution)); - varmap[i]->id = i; - varmap[i]->next = map[varmap[i]->next]; - varmap[i]->head = map[varmap[i]->head]; - } - /* Finally rewrite constraints. */ - for (unsigned i = 0; i < constraints.length (); ++i) - { - constraints[i]->lhs.var = map[constraints[i]->lhs.var]; - constraints[i]->rhs.var = map[constraints[i]->rhs.var]; - } - free (map); - - if (dump_file) - fprintf (dump_file, - "\nCollapsing static cycles and doing variable " - "substitution\n"); - - init_graph (varmap.length () * 2); - - if (dump_file) - fprintf (dump_file, "Building predecessor graph\n"); - build_pred_graph (); - - if (dump_file) - fprintf (dump_file, "Detecting pointer and location " - "equivalences\n"); - si = perform_var_substitution (graph); - - if (dump_file) - fprintf (dump_file, "Rewriting constraints and unifying " - "variables\n"); - rewrite_constraints (graph, si); - - build_succ_graph (); - - free_var_substitution_info (si); - - /* Attach complex constraints to graph nodes. */ - move_complex_constraints (graph); - - if (dump_file) - fprintf (dump_file, "Uniting pointer but not location equivalent " - "variables\n"); - unite_pointer_equivalences (graph); - - if (dump_file) - fprintf (dump_file, "Finding indirect cycles\n"); - find_indirect_cycles (graph); - - /* Implicit nodes and predecessors are no longer necessary at this - point. */ - remove_preds_and_fake_succs (graph); - - if (dump_file && (dump_flags & TDF_GRAPH)) - { - fprintf (dump_file, "\n\n// The constraint graph before solve-graph " - "in dot format:\n"); - dump_constraint_graph (dump_file); - fprintf (dump_file, "\n\n"); - } - - if (dump_file) - fprintf (dump_file, "Solving graph\n"); - - solve_graph (graph); - - if (dump_file && (dump_flags & TDF_GRAPH)) - { - fprintf (dump_file, "\n\n// The constraint graph after solve-graph " - "in dot format:\n"); - dump_constraint_graph (dump_file); - fprintf (dump_file, "\n\n"); - } -} - /* Create points-to sets for the current function. See the comments at the start of the file for an algorithmic overview. */ @@ -7845,8 +5300,6 @@ compute_points_to_sets (void) static void delete_points_to_sets (void) { - unsigned int i; - delete shared_bitmap_table; shared_bitmap_table = NULL; if (dump_file && (dump_flags & TDF_STATS)) @@ -7858,16 +5311,7 @@ delete_points_to_sets (void) bitmap_obstack_release (&pta_obstack); constraints.release (); - for (i = 0; i < graph->size; i++) - graph->complex[i].release (); - free (graph->complex); - - free (graph->rep); - free (graph->succs); - free (graph->pe); - free (graph->pe_rep); - free (graph->indirect_cycles); - free (graph); + free (var_rep); varmap.release (); variable_info_pool.release (); @@ -7914,14 +5358,14 @@ visit_loadstore (gimple *, tree base, tree ref, void *data) if (! vi) return false; - vi = get_varinfo (find (vi->id)); + vi = get_varinfo (var_rep[vi->id]); if (bitmap_intersect_p (rvars, vi->solution) || (escaped_p && bitmap_bit_p (vi->solution, escaped_id))) return false; } /* Do not overwrite existing cliques (that includes clique, base - pairs we just set). */ + pairs we just set). */ if (MR_DEPENDENCE_CLIQUE (base) == 0) { MR_DEPENDENCE_CLIQUE (base) = clique; @@ -8050,7 +5494,7 @@ compute_dependence_clique (void) varinfo_t vi = lookup_vi_for_tree (p); if (!vi) continue; - vi = get_varinfo (find (vi->id)); + vi = get_varinfo (var_rep[vi->id]); bitmap_iterator bi; unsigned j; varinfo_t restrict_var = NULL; @@ -8101,11 +5545,11 @@ compute_dependence_clique (void) maybe_set_dependence_info); if (used) { - /* Add all subvars to the set of restrict pointed-to set. */ + /* Add all subvars to the set of restrict pointed-to set. */ for (unsigned sv = restrict_var->head; sv != 0; sv = get_varinfo (sv)->next) bitmap_set_bit (rvars, sv); - varinfo_t escaped = get_varinfo (find (escaped_id)); + varinfo_t escaped = get_varinfo (var_rep[escaped_id]); if (bitmap_bit_p (escaped->solution, restrict_var->id)) escaped_p = true; } @@ -8261,7 +5705,7 @@ struct pt_solution ipa_escaped_pt = { true, false, false, false, false, false, false, false, false, false, false, NULL }; -/* Associate node with varinfo DATA. Worker for +/* Associate node with varinfo DATA. Worker for cgraph_for_symbol_thunks_and_aliases. */ static bool associate_varinfo_to_alias (struct cgraph_node *node, void *data) @@ -8275,111 +5719,6 @@ associate_varinfo_to_alias (struct cgraph_node *node, void *data) return false; } -/* Dump varinfo VI to FILE. */ - -static void -dump_varinfo (FILE *file, varinfo_t vi) -{ - if (vi == NULL) - return; - - fprintf (file, "%u: %s\n", vi->id, vi->name); - - const char *sep = " "; - if (vi->is_artificial_var) - fprintf (file, "%sartificial", sep); - if (vi->is_special_var) - fprintf (file, "%sspecial", sep); - if (vi->is_unknown_size_var) - fprintf (file, "%sunknown-size", sep); - if (vi->is_full_var) - fprintf (file, "%sfull", sep); - if (vi->is_heap_var) - fprintf (file, "%sheap", sep); - if (vi->may_have_pointers) - fprintf (file, "%smay-have-pointers", sep); - if (vi->only_restrict_pointers) - fprintf (file, "%sonly-restrict-pointers", sep); - if (vi->is_restrict_var) - fprintf (file, "%sis-restrict-var", sep); - if (vi->is_global_var) - fprintf (file, "%sglobal", sep); - if (vi->is_ipa_escape_point) - fprintf (file, "%sipa-escape-point", sep); - if (vi->is_fn_info) - fprintf (file, "%sfn-info", sep); - if (vi->ruid) - fprintf (file, "%srestrict-uid:%u", sep, vi->ruid); - if (vi->next) - fprintf (file, "%snext:%u", sep, vi->next); - if (vi->head != vi->id) - fprintf (file, "%shead:%u", sep, vi->head); - if (vi->offset) - fprintf (file, "%soffset:" HOST_WIDE_INT_PRINT_DEC, sep, vi->offset); - if (vi->size != ~HOST_WIDE_INT_0U) - fprintf (file, "%ssize:" HOST_WIDE_INT_PRINT_DEC, sep, vi->size); - if (vi->fullsize != ~HOST_WIDE_INT_0U && vi->fullsize != vi->size) - fprintf (file, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC, sep, - vi->fullsize); - fprintf (file, "\n"); - - if (vi->solution && !bitmap_empty_p (vi->solution)) - { - bitmap_iterator bi; - unsigned i; - fprintf (file, " solution: {"); - EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) - fprintf (file, " %u", i); - fprintf (file, " }\n"); - } - - if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution) - && !bitmap_equal_p (vi->solution, vi->oldsolution)) - { - bitmap_iterator bi; - unsigned i; - fprintf (file, " oldsolution: {"); - EXECUTE_IF_SET_IN_BITMAP (vi->oldsolution, 0, i, bi) - fprintf (file, " %u", i); - fprintf (file, " }\n"); - } -} - -/* Dump varinfo VI to stderr. */ - -DEBUG_FUNCTION void -debug_varinfo (varinfo_t vi) -{ - dump_varinfo (stderr, vi); -} - -/* Dump varmap to FILE. */ - -static void -dump_varmap (FILE *file) -{ - if (varmap.length () == 0) - return; - - fprintf (file, "variables:\n"); - - for (unsigned int i = 0; i < varmap.length (); ++i) - { - varinfo_t vi = get_varinfo (i); - dump_varinfo (file, vi); - } - - fprintf (file, "\n"); -} - -/* Dump varmap to stderr. */ - -DEBUG_FUNCTION void -debug_varmap (void) -{ - dump_varmap (stderr); -} - /* Compute whether node is refered to non-locally. Worker for cgraph_for_symbol_thunks_and_aliases. */ static bool @@ -8493,7 +5832,7 @@ ipa_pta_execute (void) varinfo_t vi = get_vi_for_tree (var->decl); /* For the purpose of IPA PTA unit-local globals are not - escape points. */ + escape points. */ bool nonlocal_p = (DECL_EXTERNAL (var->decl) || TREE_PUBLIC (var->decl) || var->used_from_other_partition @@ -8592,7 +5931,7 @@ ipa_pta_execute (void) for (varinfo_t ai = first_vi_for_offset (fi, fi_parm_base); ai; ai = vi_next (ai)) { - varinfo_t vi = get_varinfo (find (ai->id)); + varinfo_t vi = get_varinfo (var_rep[ai->id]); bitmap_iterator bi; unsigned j; EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi) @@ -8608,12 +5947,12 @@ ipa_pta_execute (void) } } /* As well as global variables which are another way of passing - arguments to recursive invocations. */ + arguments to recursive invocations. */ else if (fi->is_global_var) { for (varinfo_t ai = fi; ai; ai = vi_next (ai)) { - varinfo_t vi = get_varinfo (find (ai->id)); + varinfo_t vi = get_varinfo (var_rep[ai->id]); bitmap_iterator bi; unsigned j; EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi) @@ -8708,10 +6047,10 @@ ipa_pta_execute (void) { *gimple_call_clobber_set (stmt) = find_what_var_points_to - (node->decl, first_vi_for_offset (fi, fi_clobbers)); + (node->decl, first_vi_for_offset (fi, fi_clobbers)); *gimple_call_use_set (stmt) = find_what_var_points_to - (node->decl, first_vi_for_offset (fi, fi_uses)); + (node->decl, first_vi_for_offset (fi, fi_uses)); } /* Handle direct calls to external functions. */ else if (decl && (!fi || fi->decl)) @@ -8738,7 +6077,8 @@ ipa_pta_execute (void) } pt = gimple_call_clobber_set (stmt); - if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS)) + if (gimple_call_flags (stmt) & + (ECF_CONST|ECF_PURE|ECF_NOVOPS)) memset (pt, 0, sizeof (struct pt_solution)); else if ((vi = lookup_call_clobber_vi (stmt)) != NULL) { @@ -8763,7 +6103,7 @@ ipa_pta_execute (void) { /* We need to accumulate all clobbers/uses of all possible callees. */ - fi = get_varinfo (find (fi->id)); + fi = get_varinfo (var_rep[fi->id]); /* If we cannot constrain the set of functions we'll end up calling we end up using/clobbering everything. */ if (bitmap_bit_p (fi->solution, anything_id) @@ -8823,7 +6163,7 @@ ipa_pta_execute (void) fn->gimple_df->ipa_pta = true; /* We have to re-set the final-solution cache after each function - because what is a "global" is dependent on function context. */ + because what is a "global" is dependent on function context. */ final_solutions->empty (); obstack_free (&final_solutions_obstack, NULL); gcc_obstack_init (&final_solutions_obstack); |