From bb110e974e58d667991b9757f44822b58f160435 Mon Sep 17 00:00:00 2001 From: Filip Kastl Date: Thu, 17 Jul 2025 13:29:50 +0200 Subject: [PATCH] tree-ssa-structalias: Put solver into its own file This patch cuts out the points-to solver from tree-ssa-structalias.cc and places it into a new file pta-andersen.cc. It is the first part of my effort to split tree-ssa-structalias.cc into smaller parts. I had to give external linkage to some static functions and variables. I put those in the new header files tree-ssa-structalias.h and pta-andersen.h. Those header files are meant as an internal interface between parts of the points-to analyzer. Some functions and variables already had external linkage and were declared in tree-ssa-alias.h. I considered moving the declarations to tree-ssa-structalias.h but decided to leave them as is. I see those functions and variables as an external interface -- facing outwards to the rest of the compiler. For the internal interface, I made a new namespace "pointer_analysis". I didn't want to clutter the global namespace and possibly run into ODR problems. I wanted to encapsulate the constraint graph within the solver. To achieve that, I had to make some changes beyond just moving things around. They were only very small changes, though: - Add delete_graph() which gets called at the end of solve_constraints() - Problem: The solver assigns representatives to variables (union-find). To then get the solution for variable v, one has to look up the representative of v. The information needed to look up the representative is part of the graph. - Solution: Let the solver output an array that maps variables to their representatives and let this array outlive the graph (array var_rep). - Constructing the array means doing find() for every variable. That should amortize to O(size of the union-find structure). So this won't hurt the asymptotic time complexity. - We replace all calls to find(var) in tree-ssa-structalias.cc with just an array lookup var_rep[var]. - predbitmap_obstack gets initialized in init_graph(). gcc/ChangeLog: * Makefile.in: Add pta-andersen.o. * tree-ssa-structalias.cc (create_variable_info_for): Just move around. (unify_nodes): Move to pta-andersen.cc. (struct constraint): Move to tree-ssa-structalias.h. (EXECUTE_IF_IN_NONNULL_BITMAP): Move to pta-andersen.cc. (struct variable_info): Move to tree-ssa-structalias.h. (struct constraint_stats): Move to tree-ssa-structalias.h. (first_vi_for_offset): External linkage, move to namespace pointer_analysis. (first_or_preceding_vi_for_offset): External linkage, move to namespace pointer_analysis. (dump_constraint): External linkage, move to namespace pointer_analysis. (debug_constraint): External linkage, move to namespace pointer_analysis. (dump_constraints): External linkage, move to namespace pointer_analysis. (debug_constraints): External linkage, move to namespace pointer_analysis. (lookup_vi_for_tree): Move around inside tree-ssa-structalias.cc. (type_can_have_subvars): Move around inside tree-ssa-structalias.cc. (make_param_constraints): Move around inside tree-ssa-structalias.cc. (dump_solution_for_var): External linkage, move to namespace pointer_analysis. find (...) -> var_rep[...]. (get_varinfo): Move to tree-ssa-structalias.h. (debug_solution_for_var): External linkage, move to namespace pointer_analysis. (vi_next): Move to tree-ssa-structalias.h. (dump_sa_stats): External linkage, move to namespace pointer_analysis. (new_var_info): Just move around. (dump_sa_points_to_info): External linkage, move to namespace pointer_analysis. (debug_sa_points_to_info): External linkage, move to namespace pointer_analysis. (get_call_vi): Just move around. (dump_varinfo): External linkage, move to namespace pointer_analysis. (lookup_call_use_vi): Just move around. (lookup_call_clobber_vi): Just move around. (get_call_use_vi): Just move around. (get_call_clobber_vi): Just move around. (enum constraint_expr_type): Move to tree-ssa-structalias.h. (struct constraint_expr): Move to tree-ssa-structalias.h. (UNKNOWN_OFFSET): Move to tree-ssa-structalias.h. (get_constraint_for_1): Just move around. (get_constraint_for): Just move around. (get_constraint_for_rhs): Just move around. (do_deref): Just move around. (constraint_pool): Just move around. (struct constraint_graph): Move to pta-andersen.h. (FIRST_REF_NODE): Move to pta-andersen.cc. (LAST_REF_NODE): Move to pta-andersen.cc. (find): Move to pta-andersen.cc. (unite): Move to pta-andersen.cc. (new_constraint): Just move around. (debug_constraint_graph): External linkage, move to namespace pointer_analysis. (debug_varinfo): External linkage, move to namespace pointer_analysis. (debug_varmap): External linkage, move to namespace pointer_analysis. (dump_constraint_graph): External linkage, move to namespace pointer_analysis. (constraint_expr_equal): Move to pta-andersen.cc. (constraint_expr_less): Move to pta-andersen.cc. (constraint_less): Move to pta-andersen.cc. (constraint_equal): Move to pta-andersen.cc. (constraint_vec_find): Move to pta-andersen.cc. (constraint_set_union): Move to pta-andersen.cc. (solution_set_expand): Move to pta-andersen.cc. (set_union_with_increment): Move to pta-andersen.cc. (insert_into_complex): Move to pta-andersen.cc. (merge_node_constraints): Move to pta-andersen.cc. (clear_edges_for_node): Move to pta-andersen.cc. (merge_graph_nodes): Move to pta-andersen.cc. (add_implicit_graph_edge): Move to pta-andersen.cc. (add_pred_graph_edge): Move to pta-andersen.cc. (add_graph_edge): Move to pta-andersen.cc. (init_graph): Move to pta-andersen.cc. Initialize predbitmap_obstack here. (build_pred_graph): Move to pta-andersen.cc. (build_succ_graph): Move to pta-andersen.cc. (class scc_info): Move to pta-andersen.cc. (scc_visit): Move to pta-andersen.cc. (solve_add_graph_edge): Move to pta-andersen.cc. (do_sd_constraint): Move to pta-andersen.cc. (do_ds_constraint): Move to pta-andersen.cc. (do_complex_constraint): Move to pta-andersen.cc. (scc_info::scc_info): Move to pta-andersen.cc. (scc_info::~scc_info): Move to pta-andersen.cc. (find_indirect_cycles): Move to pta-andersen.cc. (topo_visit): Move to pta-andersen.cc. (compute_topo_order): Move to pta-andersen.cc. (struct equiv_class_hasher): Move to pta-andersen.cc. (equiv_class_hasher::hash): Move to pta-andersen.cc. (equiv_class_hasher::equal): Move to pta-andersen.cc. (equiv_class_lookup_or_add): Move to pta-andersen.cc. (condense_visit): Move to pta-andersen.cc. (label_visit): Move to pta-andersen.cc. (dump_pred_graph): External linkage, move to namespace pointer_analysis. (dump_varmap): External linkage, move to namespace pointer_analysis. (perform_var_substitution): Move to pta-andersen.cc. (free_var_substitution_info): Move to pta-andersen.cc. (find_equivalent_node): Move to pta-andersen.cc. (unite_pointer_equivalences): Move to pta-andersen.cc. (move_complex_constraints): Move to pta-andersen.cc. (rewrite_constraints): Move to pta-andersen.cc. (eliminate_indirect_cycles): Move to pta-andersen.cc. (solve_graph): Move to pta-andersen.cc. (set_uids_in_ptset): find (...) -> var_rep[...]. (find_what_var_points_to): find (...) -> var_rep[...]. (init_alias_vars): Don't initialize predbitmap_obstack here. (remove_preds_and_fake_succs): Move to pta-andersen.cc. (solve_constraints): Move to pta-andersen.cc. Call delete_graph() at the end. (delete_points_to_sets): Don't delete graph here. Delete var_rep here. (visit_loadstore): find (...) -> var_rep[...]. (compute_dependence_clique): find (...) -> var_rep[...]. (ipa_pta_execute): find (...) -> var_rep[...]. * pta-andersen.cc: New file. * pta-andersen.h: New file. * tree-ssa-structalias.h: New file. Signed-off-by: Filip Kastl --- gcc/Makefile.in | 1 + gcc/pta-andersen.cc | 2564 +++++++++++++++++++++++++ gcc/pta-andersen.h | 31 + gcc/tree-ssa-structalias.cc | 3489 +++++------------------------------ gcc/tree-ssa-structalias.h | 217 +++ 5 files changed, 3227 insertions(+), 3075 deletions(-) create mode 100644 gcc/pta-andersen.cc create mode 100644 gcc/pta-andersen.h create mode 100644 gcc/tree-ssa-structalias.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index bdb52925bfe..05dfa0871be 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1796,6 +1796,7 @@ OBJS = \ tree-ssa-sink.o \ tree-ssa-strlen.o \ tree-ssa-structalias.o \ + pta-andersen.o \ tree-ssa-tail-merge.o \ tree-ssa-ter.o \ tree-ssa-threadbackward.o \ diff --git a/gcc/pta-andersen.cc b/gcc/pta-andersen.cc new file mode 100644 index 00000000000..e4cc3af1471 --- /dev/null +++ b/gcc/pta-andersen.cc @@ -0,0 +1,2564 @@ +/* Andersen-style solver for tree based points-to analysis + Copyright (C) 2005-2025 Free Software Foundation, Inc. + Contributed by Daniel Berlin + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify + under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + GCC is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + . */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" + +#include "tree-ssa-structalias.h" +#include "pta-andersen.h" + +/* 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)) + +#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ + if (a) \ + EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) + +using namespace pointer_analysis; + +/* Used for predecessor bitmaps. */ +static bitmap_obstack predbitmap_obstack; + +/* Used for per-solver-iteration bitmaps. */ +static bitmap_obstack iteration_obstack; + +typedef struct constraint_graph *constraint_graph_t; + +/* 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 *complex; +}; + +static constraint_graph_t graph; + +static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); + + +/* 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; +} + +/* Perform path compression for all nodes in the node representatives + union-find structure. */ + +static void +union_find_compress_all (void) +{ + unsigned int i; + for (i = 0; i < graph->size; i++) + find (i); +} + +/* 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 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 *to, + vec *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 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; + + bitmap_obstack_initialize (&predbitmap_obstack); + + 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 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 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 &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 +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 tail (size); + topo_visit (graph, tail, visited, find (escaped_id)); + + auto_vec 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 +{ + static inline hashval_t hash (const equiv_class_label *); + static inline bool equal (const equiv_class_label *, + const equiv_class_label *); +}; + +/* A hashtable for mapping a bitmap of labels->pointer equivalence + classes. */ +static hash_table *pointer_equiv_class_table; + +/* A hashtable for mapping a bitmap of labels->location equivalence + classes. */ +static hash_table *location_equiv_class_table; + +/* 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)); +} + +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 *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 (511); + location_equiv_class_table + = new hash_table (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 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 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 &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 *cvisited = nullptr; + if (flag_checking) + cvisited = new hash_set; + 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); +} + +void +delete_graph (void) +{ + unsigned int i; + for (i = 0; i < graph->size; i++) + graph->complex[i].release (); + free (graph->complex); + + free (graph->succs); + free (graph->pe); + free (graph->pe_rep); + free (graph->indirect_cycles); + /* We are not doing free (graph->rep) since the representatives mapping is + needed outside of the solver too. */ + free (graph); +} + +/* 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); +} + +namespace pointer_analysis { + +/* Solve the constraint set. The entry function of the solver. */ + +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"); + } + + /* The mapping node -> representative is one of the outputs of the + solver. */ + union_find_compress_all (); + var_rep = graph->rep; + + delete_graph (); +} + +} // namespace pointer_analysis diff --git a/gcc/pta-andersen.h b/gcc/pta-andersen.h new file mode 100644 index 00000000000..190a273979d --- /dev/null +++ b/gcc/pta-andersen.h @@ -0,0 +1,31 @@ +/* Andersen-style solver for tree based points-to analysis + Copyright (C) 2005-2025 Free Software Foundation, Inc. + Contributed by Daniel Berlin + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify + under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + GCC is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + . */ + +#ifndef PTA_ANDERSEN_H +#define PTA_ANDERSEN_H + +namespace pointer_analysis { + +/* Solve the constraint set. */ +void solve_constraints (void); + +} // namespace pointer_analysis + +#endif /* PTA_ANDERSEN_H */ diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc index 0215243d5be..05a2e40500a 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,2785 +204,513 @@ 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 per-solver-iteration bitmaps. */ -static bitmap_obstack iteration_obstack; - -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); - -struct constraint; -typedef struct constraint *constraint_t; +bitmap_obstack oldpta_obstack; +/* Table of variable info structures for constraint variables. + Indexed directly by variable info id. */ +vec varmap; -#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ - if (a) \ - EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) - -static struct constraint_stats -{ - 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 -{ - /* ID of this variable */ - unsigned int id; - - /* 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; +/* List of constraints that we use to build the constraint graph from. */ +vec constraints; - /* True if this is a special variable whose solution set should not be - changed. */ - unsigned int is_special_var : 1; +/* Map from trees to variable infos. */ +static hash_map *vi_for_tree; - /* True for variables whose size is not known or variable. */ - unsigned int is_unknown_size_var : 1; +/* 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. - /* True for (sub-)fields that represent a whole variable. */ - unsigned int is_full_var : 1; + The solver provides this array once it is done solving. */ +unsigned int *var_rep; - /* True if this is a heap variable. */ - unsigned int is_heap_var : 1; +struct constraint_stats stats; - /* True if this is a register variable. */ - unsigned int is_reg_var : 1; +/* Find the first varinfo in the same variable as START that overlaps with + OFFSET. Return NULL if we can't find one. */ - /* True if this field may contain pointers. */ - unsigned int may_have_pointers : 1; +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; - /* True if this field has only restrict qualified pointers. */ - unsigned int only_restrict_pointers : 1; + /* 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 represents a heap var created for a restrict qualified - pointer. */ - unsigned int is_restrict_var : 1; + 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; - /* True if this represents a global variable. */ - unsigned int is_global_var : 1; + start = vi_next (start); + } - /* True if this represents a module escape point for IPA analysis. */ - unsigned int is_ipa_escape_point : 1; + return NULL; +} - /* True if this represents a IPA function info. */ - unsigned int is_fn_info : 1; +/* 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. */ - /* True if this appears as RHS in a ADDRESSOF constraint. */ - unsigned int address_taken : 1; +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); - /* ??? Store somewhere better. */ - unsigned short ruid; + /* 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); - /* The ID of the variable for the next field in this structure - or zero for the last field in this structure. */ - unsigned next; + return start; +} - /* The ID of the variable for the first field in this structure. */ - unsigned head; +/* Print out constraint C to FILE. */ - /* Offset of this variable, in bits, from the base variable */ - unsigned HOST_WIDE_INT offset; +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); +} - /* Size of the variable, in bits. */ - unsigned HOST_WIDE_INT size; +/* Print out constraint C to stderr. */ - /* Full size of the base variable, in bits. */ - unsigned HOST_WIDE_INT fullsize; +DEBUG_FUNCTION void +debug_constraint (constraint_t c) +{ + dump_constraint (stderr, c); + fprintf (stderr, "\n"); +} - /* 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; +/* Print out all constraints to FILE */ - /* Name of this variable */ - const char *name; +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"); + } +} - /* Tree that this variable is associated with. */ - tree decl; +/* Print out all constraints to stderr. */ - /* Points-to set for this variable. */ - bitmap solution; +DEBUG_FUNCTION void +debug_constraints (void) +{ + dump_constraints (stderr, 0); +} - /* Old points-to set for this variable. */ - bitmap oldsolution; -}; -typedef struct variable_info *varinfo_t; +/* Print out the points-to solution for VAR to FILE. */ -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); +void +dump_solution_for_var (FILE *file, unsigned int var) +{ + varinfo_t vi = get_varinfo (var); + unsigned int i; + bitmap_iterator bi; -/* Pool of variable info structures. */ -static object_allocator variable_info_pool - ("Variable info pool"); + /* 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, "}"); -/* Map varinfo to final pt_solution. */ -static hash_map *final_solutions; -struct obstack final_solutions_obstack; + /* But note when the variable was unified. */ + if (vi->id != var) + fprintf (file, " same as %s", vi->name); -/* Table of variable info structures for constraint variables. - Indexed directly by variable info id. */ -static vec varmap; + fprintf (file, "\n"); +} -/* Return the varmap element N */ +/* Print the points-to solution for VAR to stderr. */ -static inline varinfo_t -get_varinfo (unsigned int n) +DEBUG_FUNCTION void +debug_solution_for_var (unsigned int var) { - return varmap[n]; + dump_solution_for_var (stderr, var); } -/* Return the next variable in the list of sub-variables of VI - or NULL if VI is the last sub-variable. */ +/* Dump stats information to OUTFILE. */ -static inline varinfo_t -vi_next (varinfo_t vi) +void +dump_sa_stats (FILE *outfile) { - return get_varinfo (vi->next); + 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); } -/* 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 }; - -/* Return a new variable info structure consisting for a variable - named NAME, and using constraint graph node NODE. Append it - to the vector of variable info structures. */ +/* Dump points-to information to OUTFILE. */ -static varinfo_t -new_var_info (tree t, const char *name, bool add_id) +void +dump_sa_points_to_info (FILE *outfile) { - unsigned index = varmap.length (); - varinfo_t ret = variable_info_pool.allocate (); + fprintf (outfile, "\nPoints-to sets\n\n"); - if (dump_file && add_id) + for (unsigned i = 1; i < varmap.length (); i++) { - char *tempname = xasprintf ("%s(%d)", name, index); - name = ggc_strdup (tempname); - free (tempname); + varinfo_t vi = get_varinfo (i); + if (!vi->may_have_pointers) + continue; + dump_solution_for_var (outfile, i); } +} - ret->id = index; - ret->name = name; - ret->decl = t; - /* Vars without decl are artificial and do not have sub-variables. */ - ret->is_artificial_var = (t == NULL_TREE); - ret->is_special_var = false; - ret->is_unknown_size_var = false; - ret->is_full_var = (t == NULL_TREE); - ret->is_heap_var = false; - ret->may_have_pointers = true; - ret->only_restrict_pointers = false; - ret->is_restrict_var = false; - ret->ruid = 0; - ret->is_global_var = (t == NULL_TREE); - ret->is_ipa_escape_point = false; - ret->is_fn_info = false; - ret->address_taken = false; - if (t && DECL_P (t)) - ret->is_global_var = (is_global_var (t) - /* We have to treat even local register variables - as escape points. */ - || (VAR_P (t) && DECL_HARD_REGISTER (t))); - ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME); - ret->solution = BITMAP_ALLOC (&pta_obstack); - ret->oldsolution = NULL; - ret->next = 0; - ret->shadow_var_uid = 0; - ret->head = ret->id; - - stats.total_vars++; - varmap.safe_push (ret); +/* Debug points-to information to stderr. */ - return ret; +DEBUG_FUNCTION void +debug_sa_points_to_info (void) +{ + dump_sa_points_to_info (stderr); } -/* A map mapping call statements to per-stmt variables for uses - and clobbers specific to the call. */ -static hash_map *call_stmt_vars; - -/* Lookup or create the variable for the call statement CALL. */ +/* Dump varinfo VI to FILE. */ -static varinfo_t -get_call_vi (gcall *call) +void +dump_varinfo (FILE *file, varinfo_t vi) { - varinfo_t vi, vi2; - - bool existed; - varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed); - if (existed) - return *slot_p; + if (vi == NULL) + return; - vi = new_var_info (NULL_TREE, "CALLUSED", true); - vi->offset = 0; - vi->size = 1; - vi->fullsize = 2; - vi->is_full_var = true; - vi->is_reg_var = true; + fprintf (file, "%u: %s\n", vi->id, vi->name); - vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true); - vi2->offset = 1; - vi2->size = 1; - vi2->fullsize = 2; - vi2->is_full_var = true; - vi2->is_reg_var = true; - - vi->next = vi2->id; - - *slot_p = vi; - return vi; -} - -/* Lookup the variable for the call statement CALL representing - the uses. Returns NULL if there is nothing special about this call. */ - -static varinfo_t -lookup_call_use_vi (gcall *call) -{ - varinfo_t *slot_p = call_stmt_vars->get (call); - if (slot_p) - return *slot_p; - - return NULL; -} - -/* Lookup the variable for the call statement CALL representing - the clobbers. Returns NULL if there is nothing special about this call. */ - -static varinfo_t -lookup_call_clobber_vi (gcall *call) -{ - varinfo_t uses = lookup_call_use_vi (call); - if (!uses) - return NULL; - - return vi_next (uses); -} - -/* Lookup or create the variable for the call statement CALL representing - the uses. */ - -static varinfo_t -get_call_use_vi (gcall *call) -{ - return get_call_vi (call); -} - -/* Lookup or create the variable for the call statement CALL representing - the clobbers. */ - -static varinfo_t ATTRIBUTE_UNUSED -get_call_clobber_vi (gcall *call) -{ - return vi_next (get_call_vi (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 *, bool, bool); -static void get_constraint_for (tree, vec *); -static void get_constraint_for_rhs (tree, vec *); -static void do_deref (vec *); - -/* 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; -}; - -/* List of constraints that we use to build the constraint graph from. */ - -static vec constraints; -static object_allocator 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 *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 -new_constraint (const struct constraint_expr lhs, - const struct constraint_expr rhs) -{ - constraint_t ret = constraint_pool.allocate (); - ret->lhs = lhs; - ret->rhs = rhs; - 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 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 *to, - vec *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 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 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 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 &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 -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 tail (size); - topo_visit (graph, tail, visited, find (escaped_id)); - - auto_vec 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 -{ - 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 *pointer_equiv_class_table; - -/* A hashtable for mapping a bitmap of labels->location equivalence - classes. */ -static hash_table *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 *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]; - } + 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"); - /* Visit all the implicit predecessors. */ - EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) + if (vi->solution && !bitmap_empty_p (vi->solution)) { - 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]; + 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"); } - /* See if any components have been identified. */ - if (si->dfs[n] == my_dfs) + if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution) + && !bitmap_equal_p (vi->solution, vi->oldsolution)) { - 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); + 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"); } - 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. */ +/* Dump varinfo VI to stderr. */ -static void -label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) +DEBUG_FUNCTION void +debug_varinfo (varinfo_t vi) { - 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; - } + dump_varinfo (stderr, vi); } -/* Print the pred graph in dot format. */ +/* Dump varmap to FILE. */ -static void -dump_pred_graph (class scc_info *si, FILE *file) +void +dump_varmap (FILE *file) { - unsigned int i; - - /* Only print the graph if it has already been initialized: */ - if (!graph) + if (varmap.length () == 0) 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"); - } + fprintf (file, "variables:\n"); - /* Go over the edges. */ - fprintf (file, "\n // Edges in the constraint graph:\n"); - for (i = 1; i < graph->size; i++) + for (unsigned int i = 0; i < varmap.length (); ++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"); - } + varinfo_t vi = get_varinfo (i); + dump_varinfo (file, vi); } - /* Prints the tail of the dot file. */ - fprintf (file, "}\n"); + fprintf (file, "\n"); } -/* Perform offline variable substitution, discovering equivalence - classes, and eliminating non-pointer variables. */ +/* Dump varmap to stderr. */ -static class scc_info * -perform_var_substitution (constraint_graph_t graph) +DEBUG_FUNCTION void +debug_varmap (void) { - 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 (511); - location_equiv_class_table - = new hash_table (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; + dump_varmap (stderr); } -/* Free information that was only necessary for variable - substitution. */ +} // namespace pointer_analysis -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. */ +using namespace pointer_analysis; -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. */ +static bool use_field_sensitive = true; +static int in_ipa_mode = 0; - if (!bitmap_bit_p (graph->address_taken, node)) - { - gcc_checking_assert (label < graph->size); +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); - 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; - } +/* Pool of variable info structures. */ +static object_allocator variable_info_pool + ("Variable info pool"); - return node; -} +/* Map varinfo to final pt_solution. */ +static hash_map *final_solutions; +static struct obstack final_solutions_obstack; -/* Unite pointer equivalent but not location equivalent nodes in - GRAPH. This may only be performed once variable substitution is - finished. */ +/* Return a new variable info structure consisting for a variable + named NAME, and using constraint graph node NODE. Append it + to the vector of variable info structures. */ -static void -unite_pointer_equivalences (constraint_graph_t graph) +static varinfo_t +new_var_info (tree t, const char *name, bool add_id) { - unsigned int i; + unsigned index = varmap.length (); + varinfo_t ret = variable_info_pool.allocate (); - /* Go through the pointer equivalences and unite them to their - representative, if they aren't already. */ - for (i = 1; i < FIRST_REF_NODE; i++) + if (dump_file && add_id) { - 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); - } + char *tempname = xasprintf ("%s(%d)", name, index); + name = ggc_strdup (tempname); + free (tempname); } -} -/* Move complex constraints to the GRAPH nodes they belong to. */ - -static void -move_complex_constraints (constraint_graph_t graph) -{ - int i; - constraint_t c; + ret->id = index; + ret->name = name; + ret->decl = t; + /* Vars without decl are artificial and do not have sub-variables. */ + ret->is_artificial_var = (t == NULL_TREE); + ret->is_special_var = false; + ret->is_unknown_size_var = false; + ret->is_full_var = (t == NULL_TREE); + ret->is_heap_var = false; + ret->may_have_pointers = true; + ret->only_restrict_pointers = false; + ret->is_restrict_var = false; + ret->ruid = 0; + ret->is_global_var = (t == NULL_TREE); + ret->is_ipa_escape_point = false; + ret->is_fn_info = false; + ret->address_taken = false; + if (t && DECL_P (t)) + ret->is_global_var = (is_global_var (t) + /* We have to treat even local register variables + as escape points. */ + || (VAR_P (t) && DECL_HARD_REGISTER (t))); + ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME); + ret->solution = BITMAP_ALLOC (&pta_obstack); + ret->oldsolution = NULL; + ret->next = 0; + ret->shadow_var_uid = 0; + ret->head = ret->id; - FOR_EACH_VEC_ELT (constraints, i, c) - { - if (c) - { - struct constraint_expr lhs = c->lhs; - struct constraint_expr rhs = c->rhs; + stats.total_vars++; - 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); - } - } - } + varmap.safe_push (ret); + + return ret; } +/* A map mapping call statements to per-stmt variables for uses + and clobbers specific to the call. */ +static hash_map *call_stmt_vars; -/* Optimize and rewrite complex constraints while performing - collapsing of equivalent nodes. SI is the SCC_INFO that is the - result of perform_variable_substitution. */ +/* Lookup or create the variable for the call statement CALL. */ -static void -rewrite_constraints (constraint_graph_t graph, - class scc_info *si) +static varinfo_t +get_call_vi (gcall *call) { - int i; - constraint_t c; - - if (flag_checking) - { - for (unsigned int j = 0; j < graph->size; j++) - gcc_assert (find (j) == j); - } + varinfo_t vi, vi2; - 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)) - { + bool existed; + varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed); + if (existed) + return *slot_p; - 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; - } + vi = new_var_info (NULL_TREE, "CALLUSED", true); + vi->offset = 0; + vi->size = 1; + vi->fullsize = 2; + vi->is_full_var = true; + vi->is_reg_var = true; - if (rhslabel == 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { + vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true); + vi2->offset = 1; + vi2->size = 1; + vi2->fullsize = 2; + vi2->is_full_var = true; + vi2->is_reg_var = true; - 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; - } + vi->next = vi2->id; - lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); - rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); - c->lhs.var = lhsvar; - c->rhs.var = rhsvar; - } + *slot_p = vi; + return vi; } -/* Eliminate indirect cycles involving NODE. Return true if NODE was - part of an SCC, false otherwise. */ +/* Lookup the variable for the call statement CALL representing + the uses. Returns NULL if there is nothing special about this call. */ -static bool -eliminate_indirect_cycles (unsigned int node) +static varinfo_t +lookup_call_use_vi (gcall *call) { - if (graph->indirect_cycles[node] != -1 - && !bitmap_empty_p (get_varinfo (node)->solution)) - { - unsigned int i; - auto_vec 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); - } - } + varinfo_t *slot_p = call_stmt_vars->get (call); + if (slot_p) + return *slot_p; - for (queuepos = 0; - queue.iterate (queuepos, &i); - queuepos++) - { - unify_nodes (graph, to, i, true); - } - return true; - } - return false; + return NULL; } -/* 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. */ +/* Lookup the variable for the call statement CALL representing + the clobbers. Returns NULL if there is nothing special about this call. */ -static void -solve_graph (constraint_graph_t graph) +static varinfo_t +lookup_call_clobber_vi (gcall *call) { - 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 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; + varinfo_t uses = lookup_call_use_vi (call); + if (!uses) + return NULL; - /* 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 &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); + return vi_next (uses); +} - if (bitmap_empty_p (pts)) - break; +/* Lookup or create the variable for the call statement CALL representing + the uses. */ - if (vi->oldsolution) - bitmap_ior_into (vi->oldsolution, pts); - else - { - vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack); - bitmap_copy (vi->oldsolution, pts); - } +static varinfo_t +get_call_use_vi (gcall *call) +{ + return get_call_vi (call); +} - solution = vi->solution; - solution_empty = bitmap_empty_p (solution); +/* Lookup or create the variable for the call statement CALL representing + the clobbers. */ - /* Process the complex constraints */ - hash_set *cvisited = nullptr; - if (flag_checking) - cvisited = new hash_set; - 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; - } - } - } +static varinfo_t ATTRIBUTE_UNUSED +get_call_clobber_vi (gcall *call) +{ + return vi_next (get_call_vi (call)); +} - /* 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); +static void get_constraint_for_1 (tree, vec *, bool, bool); +static void get_constraint_for (tree, vec *); +static void get_constraint_for_rhs (tree, vec *); +static void do_deref (vec *); - if (!solution_empty) - { - bitmap_iterator bi; - unsigned eff_escaped_id = find (escaped_id); - unsigned j; +/* Allocator for 'constraints' vector. */ - /* 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; - } +static object_allocator constraint_pool ("Constraint pool"); - 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); - } +/* Create a new constraint consisting of LHS and RHS expressions. */ - BITMAP_FREE (pts); - BITMAP_FREE (changed); - bitmap_obstack_release (&oldpta_obstack); +static constraint_t +new_constraint (const struct constraint_expr lhs, + const struct constraint_expr rhs) +{ + constraint_t ret = constraint_pool.allocate (); + ret->lhs = lhs; + ret->rhs = rhs; + return ret; } -/* Map from trees to variable infos. */ -static hash_map *vi_for_tree; - - /* Insert ID as the variable id for tree T in the vi_for_tree map. */ static void @@ -5761,87 +3492,28 @@ find_func_clobbers (struct function *fn, gimple *origt) return; } - /* Otherwise the caller clobbers and uses what the callee does. - ??? This should use a new complex constraint that filters - local variables of the callee. */ - if (gimple_vdef (t)) - { - lhs = get_function_part_constraint (fi, fi_clobbers); - rhs = get_function_part_constraint (cfi, fi_clobbers); - process_constraint (new_constraint (lhs, rhs)); - } - lhs = get_function_part_constraint (fi, fi_uses); - rhs = get_function_part_constraint (cfi, fi_uses); - process_constraint (new_constraint (lhs, rhs)); - } - else if (gimple_code (t) == GIMPLE_ASM) - { - /* ??? Ick. We can do better. */ - if (gimple_vdef (t)) - make_constraint_from (first_vi_for_offset (fi, fi_clobbers), - anything_id); - make_constraint_from (first_vi_for_offset (fi, fi_uses), - anything_id); - } -} - - -/* 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; + /* Otherwise the caller clobbers and uses what the callee does. + ??? This should use a new complex constraint that filters + local variables of the callee. */ + if (gimple_vdef (t)) + { + lhs = get_function_part_constraint (fi, fi_clobbers); + rhs = get_function_part_constraint (cfi, fi_clobbers); + process_constraint (new_constraint (lhs, rhs)); + } + lhs = get_function_part_constraint (fi, fi_uses); + rhs = get_function_part_constraint (cfi, fi_uses); + process_constraint (new_constraint (lhs, rhs)); + } + else if (gimple_code (t) == GIMPLE_ASM) + { + /* ??? Ick. We can do better. */ + if (gimple_vdef (t)) + make_constraint_from (first_vi_for_offset (fi, fi_clobbers), + anything_id); + make_constraint_from (first_vi_for_offset (fi, fi_uses), + anything_id); + } } @@ -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 @@ -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; } @@ -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 */ @@ -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,7 +5358,7 @@ 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; @@ -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; @@ -8105,7 +5549,7 @@ compute_dependence_clique (void) 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; } @@ -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 @@ -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) @@ -8613,7 +5952,7 @@ ipa_pta_execute (void) { 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) @@ -8763,7 +6102,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) diff --git a/gcc/tree-ssa-structalias.h b/gcc/tree-ssa-structalias.h new file mode 100644 index 00000000000..21676d6c655 --- /dev/null +++ b/gcc/tree-ssa-structalias.h @@ -0,0 +1,217 @@ +/* Tree based points-to analysis + Copyright (C) 2005-2025 Free Software Foundation, Inc. + Contributed by Daniel Berlin + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify + under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + GCC is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + . */ + +/* NOTE: This file declares the internal interface of the points-to analyzer. + Outward-facing function declarations can be found in tree-ssa-alias.h. */ + +#ifndef TREE_SSA_STRUCTALIAS_H +#define TREE_SSA_STRUCTALIAS_H + +namespace pointer_analysis { + +enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF}; + +/* 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 }; + +/* Use 0x8000... as special unknown offset. */ +#define UNKNOWN_OFFSET HOST_WIDE_INT_MIN + +/* 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; +}; +typedef struct constraint_expr ce_s; + +/* Our set constraints are made up of two constraint expressions, one + LHS, and one RHS. + + As described in the introduction in tree-ssa-structalias.cc, our set + constraints each represent an operation between set valued variables. +*/ +struct constraint +{ + struct constraint_expr lhs; + struct constraint_expr rhs; +}; +typedef struct constraint *constraint_t; + +struct variable_info +{ + /* ID of this variable */ + unsigned int id; + + /* 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; + + /* True if this is a special variable whose solution set should not be + changed. */ + unsigned int is_special_var : 1; + + /* True for variables whose size is not known or variable. */ + unsigned int is_unknown_size_var : 1; + + /* True for (sub-)fields that represent a whole variable. */ + unsigned int is_full_var : 1; + + /* True if this is a heap variable. */ + unsigned int is_heap_var : 1; + + /* True if this is a register variable. */ + unsigned int is_reg_var : 1; + + /* True if this field may contain pointers. */ + unsigned int may_have_pointers : 1; + + /* True if this field has only restrict qualified pointers. */ + unsigned int only_restrict_pointers : 1; + + /* True if this represents a heap var created for a restrict qualified + pointer. */ + unsigned int is_restrict_var : 1; + + /* True if this represents a global variable. */ + unsigned int is_global_var : 1; + + /* True if this represents a module escape point for IPA analysis. */ + unsigned int is_ipa_escape_point : 1; + + /* True if this represents a IPA function info. */ + unsigned int is_fn_info : 1; + + /* True if this appears as RHS in a ADDRESSOF constraint. */ + unsigned int address_taken : 1; + + /* ??? Store somewhere better. */ + unsigned short ruid; + + /* The ID of the variable for the next field in this structure + or zero for the last field in this structure. */ + unsigned next; + + /* The ID of the variable for the first field in this structure. */ + unsigned head; + + /* Offset of this variable, in bits, from the base variable */ + unsigned HOST_WIDE_INT offset; + + /* Size of the variable, in bits. */ + unsigned HOST_WIDE_INT size; + + /* Full size of the base variable, in bits. */ + unsigned HOST_WIDE_INT fullsize; + + /* 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; + + /* Name of this variable */ + const char *name; + + /* Tree that this variable is associated with. */ + tree decl; + + /* Points-to set for this variable. */ + bitmap solution; + + /* Old points-to set for this variable. */ + bitmap oldsolution; +}; +typedef struct variable_info *varinfo_t; + +struct constraint_stats +{ + 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; +}; + +extern struct constraint_stats stats; + +extern bitmap_obstack pta_obstack; +extern bitmap_obstack oldpta_obstack; + +extern vec varmap; +extern vec constraints; +extern unsigned int *var_rep; + + +/* Return the varmap element N */ + +inline varinfo_t +get_varinfo (unsigned int n) +{ + return varmap[n]; +} + +/* Return the next variable in the list of sub-variables of VI + or NULL if VI is the last sub-variable. */ + +inline varinfo_t +vi_next (varinfo_t vi) +{ + return get_varinfo (vi->next); +} + +varinfo_t first_vi_for_offset (varinfo_t start, + unsigned HOST_WIDE_INT offset); +varinfo_t first_or_preceding_vi_for_offset (varinfo_t start, + unsigned HOST_WIDE_INT offset); +void dump_constraint (FILE *file, constraint_t c); +void dump_constraints (FILE *file, int from); +void dump_solution_for_var (FILE *file, unsigned int var); +void dump_sa_stats (FILE *outfile); +void dump_sa_points_to_info (FILE *outfile); +void dump_varinfo (FILE *file, varinfo_t vi); +void dump_varmap (FILE *file); +void debug_constraint (constraint_t); +void debug_constraints (void); +void debug_solution_for_var (unsigned int); +void debug_sa_points_to_info (void); +void debug_varinfo (varinfo_t); +void debug_varmap (void); + +} // namespace pointer_analysis + +#endif /* TREE_SSA_STRUCTALIAS_H */ -- 2.47.2