diff options
Diffstat (limited to 'gcc/pta-andersen.cc')
| -rw-r--r-- | gcc/pta-andersen.cc | 2565 |
1 files changed, 2565 insertions, 0 deletions
diff --git a/gcc/pta-andersen.cc b/gcc/pta-andersen.cc new file mode 100644 index 0000000..0253f05 --- /dev/null +++ b/gcc/pta-andersen.cc @@ -0,0 +1,2565 @@ +/* Andersen-style solver for tree based points-to analysis + Copyright (C) 2005-2025 Free Software Foundation, Inc. + Contributed by Daniel Berlin <dberlin@dberlin.org> + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify + under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + GCC is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + <http://www.gnu.org/licenses/>. */ + +#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<constraint_t> *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<constraint_t> vec, + constraint &lookfor) +{ + unsigned int place; + constraint_t found; + + if (!vec.exists ()) + return NULL; + + place = vec.lower_bound (&lookfor, constraint_less); + if (place >= vec.length ()) + return NULL; + found = vec[place]; + if (!constraint_equal (*found, lookfor)) + return NULL; + return found; +} + +/* Union two constraint vectors, TO and FROM. Put the result in TO. + Returns true of TO set is changed. */ + +static bool +constraint_set_union (vec<constraint_t> *to, + vec<constraint_t> *from) +{ + int i; + constraint_t c; + bool any_change = false; + + FOR_EACH_VEC_ELT (*from, i, c) + { + if (constraint_vec_find (*to, *c) == NULL) + { + unsigned int place = to->lower_bound (c, constraint_less); + to->safe_insert (place, c); + any_change = true; + } + } + return any_change; +} + +/* Expands the solution in SET to all sub-fields of variables included. */ + +static bitmap +solution_set_expand (bitmap set, bitmap *expanded) +{ + bitmap_iterator bi; + unsigned j; + + if (*expanded) + return *expanded; + + *expanded = BITMAP_ALLOC (&iteration_obstack); + + /* In a first pass expand variables, once for each head to avoid + quadratic behavior, to include all sub-fields. */ + unsigned prev_head = 0; + EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi) + { + varinfo_t v = get_varinfo (j); + if (v->is_artificial_var + || v->is_full_var) + continue; + if (v->head != prev_head) + { + varinfo_t head = get_varinfo (v->head); + unsigned num = 1; + for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n)) + { + if (n->id != head->id + num) + { + /* Usually sub variables are adjacent but since we + create pointed-to restrict representatives there + can be gaps as well. */ + bitmap_set_range (*expanded, head->id, num); + head = n; + num = 1; + } + else + num++; + } + + bitmap_set_range (*expanded, head->id, num); + prev_head = v->head; + } + } + + /* And finally set the rest of the bits from SET in an efficient way. */ + bitmap_ior_into (*expanded, set); + + return *expanded; +} + +/* Union solution sets TO and DELTA, and add INC to each member of DELTA in the + process. */ + +static bool +set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc, + bitmap *expanded_delta) +{ + bool changed = false; + bitmap_iterator bi; + unsigned int i; + + /* If the solution of DELTA contains anything it is good enough to transfer + this to TO. */ + if (bitmap_bit_p (delta, anything_id)) + return bitmap_set_bit (to, anything_id); + + /* If the offset is unknown we have to expand the solution to + all subfields. */ + if (inc == UNKNOWN_OFFSET) + { + delta = solution_set_expand (delta, expanded_delta); + changed |= bitmap_ior_into (to, delta); + return changed; + } + + /* For non-zero offset union the offsetted solution into the destination. */ + EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi) + { + varinfo_t vi = get_varinfo (i); + + /* If this is a variable with just one field just set its bit + in the result. */ + if (vi->is_artificial_var + || vi->is_unknown_size_var + || vi->is_full_var) + changed |= bitmap_set_bit (to, i); + else + { + HOST_WIDE_INT fieldoffset = vi->offset + inc; + unsigned HOST_WIDE_INT size = vi->size; + + /* If the offset makes the pointer point to before the + variable use offset zero for the field lookup. */ + if (fieldoffset < 0) + vi = get_varinfo (vi->head); + else + vi = first_or_preceding_vi_for_offset (vi, fieldoffset); + + do + { + changed |= bitmap_set_bit (to, vi->id); + if (vi->is_full_var + || vi->next == 0) + break; + + /* We have to include all fields that overlap the current field + shifted by inc. */ + vi = vi_next (vi); + } + while (vi->offset < fieldoffset + size); + } + } + + return changed; +} + +/* Insert constraint C into the list of complex constraints for graph + node VAR. */ + +static void +insert_into_complex (constraint_graph_t graph, + unsigned int var, constraint_t c) +{ + vec<constraint_t> complex = graph->complex[var]; + unsigned int place = complex.lower_bound (c, constraint_less); + + /* Only insert constraints that do not already exist. */ + if (place >= complex.length () + || !constraint_equal (*c, *complex[place])) + graph->complex[var].safe_insert (place, c); +} + + +/* Condense two variable nodes into a single variable node, by moving + all associated info from FROM to TO. Returns true if TO node's + constraint set changes after the merge. */ + +static bool +merge_node_constraints (constraint_graph_t graph, unsigned int to, + unsigned int from) +{ + unsigned int i; + constraint_t c; + bool any_change = false; + + gcc_checking_assert (find (from) == to); + + /* Move all complex constraints from src node into to node. */ + FOR_EACH_VEC_ELT (graph->complex[from], i, c) + { + /* In complex constraints for node FROM, we may have either + a = *FROM, and *FROM = a, or an offseted constraint which are + always added to the rhs node's constraints. */ + + if (c->rhs.type == DEREF) + c->rhs.var = to; + else if (c->lhs.type == DEREF) + c->lhs.var = to; + else + c->rhs.var = to; + + } + any_change = constraint_set_union (&graph->complex[to], + &graph->complex[from]); + graph->complex[from].release (); + return any_change; +} + +/* Remove edges involving NODE from GRAPH. */ + +static void +clear_edges_for_node (constraint_graph_t graph, unsigned int node) +{ + if (graph->succs[node]) + BITMAP_FREE (graph->succs[node]); +} + +/* Merge GRAPH nodes FROM and TO into node TO. */ + +static void +merge_graph_nodes (constraint_graph_t graph, unsigned int to, + unsigned int from) +{ + if (graph->indirect_cycles[from] != -1) + { + /* If we have indirect cycles with the from node, and we have + none on the to node, the to node has indirect cycles from the + from node now that they are unified. + If indirect cycles exist on both, unify the nodes that they + are in a cycle with, since we know they are in a cycle with + each other. */ + if (graph->indirect_cycles[to] == -1) + graph->indirect_cycles[to] = graph->indirect_cycles[from]; + } + + /* Merge all the successor edges. */ + if (graph->succs[from]) + { + if (!graph->succs[to]) + graph->succs[to] = BITMAP_ALLOC (&pta_obstack); + bitmap_ior_into (graph->succs[to], + graph->succs[from]); + } + + clear_edges_for_node (graph, from); +} + + +/* Add an indirect graph edge to GRAPH, going from TO to FROM if + it doesn't exist in the graph already. */ + +static void +add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, + unsigned int from) +{ + if (to == from) + return; + + if (!graph->implicit_preds[to]) + graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); + + if (bitmap_set_bit (graph->implicit_preds[to], from)) + stats.num_implicit_edges++; +} + +/* Add a predecessor graph edge to GRAPH, going from TO to FROM if + it doesn't exist in the graph already. + Return false if the edge already existed, true otherwise. */ + +static void +add_pred_graph_edge (constraint_graph_t graph, unsigned int to, + unsigned int from) +{ + if (!graph->preds[to]) + graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); + bitmap_set_bit (graph->preds[to], from); +} + +/* Add a graph edge to GRAPH, going from FROM to TO if + it doesn't exist in the graph already. + Return false if the edge already existed, true otherwise. */ + +static bool +add_graph_edge (constraint_graph_t graph, unsigned int to, + unsigned int from) +{ + if (to == from) + { + return false; + } + else + { + bool r = false; + + if (!graph->succs[from]) + graph->succs[from] = BITMAP_ALLOC (&pta_obstack); + + /* The graph solving process does not avoid "triangles", thus + there can be multiple paths from a node to another involving + intermediate other nodes. That causes extra copying which is + most difficult to avoid when the intermediate node is ESCAPED + because there are no edges added from ESCAPED. Avoid + adding the direct edge FROM -> TO when we have FROM -> ESCAPED + and TO contains ESCAPED. + ??? Note this is only a heuristic, it does not prevent the + situation from occuring. The heuristic helps PR38474 and + PR99912 significantly. */ + if (to < FIRST_REF_NODE + && bitmap_bit_p (graph->succs[from], find (escaped_id)) + && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id)) + { + stats.num_avoided_edges++; + return false; + } + + if (bitmap_set_bit (graph->succs[from], to)) + { + r = true; + if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) + stats.num_edges++; + } + return r; + } +} + +/* Initialize the constraint graph structure to contain SIZE nodes. */ + +static void +init_graph (unsigned int size) +{ + unsigned int j; + + 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<constraint_t> vec_constraint_t_heap; + graph->complex = XCNEWVEC (vec_constraint_t_heap, size); + graph->pe = XCNEWVEC (unsigned int, graph->size); + graph->pe_rep = XNEWVEC (int, graph->size); + + for (j = 0; j < graph->size; j++) + { + graph->rep[j] = j; + graph->pe_rep[j] = -1; + graph->indirect_cycles[j] = -1; + } +} + +/* Build the constraint graph, adding only predecessor edges right now. */ + +static void +build_pred_graph (void) +{ + int i; + constraint_t c; + unsigned int j; + + graph->implicit_preds = XCNEWVEC (bitmap, graph->size); + graph->preds = XCNEWVEC (bitmap, graph->size); + graph->pointer_label = XCNEWVEC (unsigned int, graph->size); + graph->loc_label = XCNEWVEC (unsigned int, graph->size); + graph->pointed_by = XCNEWVEC (bitmap, graph->size); + graph->points_to = XCNEWVEC (bitmap, graph->size); + graph->eq_rep = XNEWVEC (int, graph->size); + graph->direct_nodes = sbitmap_alloc (graph->size); + graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack); + bitmap_clear (graph->direct_nodes); + + for (j = 1; j < FIRST_REF_NODE; j++) + { + if (!get_varinfo (j)->is_special_var) + bitmap_set_bit (graph->direct_nodes, j); + } + + for (j = 0; j < graph->size; j++) + graph->eq_rep[j] = -1; + + for (j = 0; j < varmap.length (); j++) + graph->indirect_cycles[j] = -1; + + FOR_EACH_VEC_ELT (constraints, i, c) + { + struct constraint_expr lhs = c->lhs; + struct constraint_expr rhs = c->rhs; + unsigned int lhsvar = lhs.var; + unsigned int rhsvar = rhs.var; + + if (lhs.type == DEREF) + { + /* *x = y. */ + if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) + { + if (lhs.var == anything_id) + add_pred_graph_edge (graph, storedanything_id, rhsvar); + else + add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); + } + } + else if (rhs.type == DEREF) + { + /* x = *y */ + if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) + add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); + else + bitmap_clear_bit (graph->direct_nodes, lhsvar); + } + else if (rhs.type == ADDRESSOF) + { + varinfo_t v; + + /* x = &y */ + if (graph->points_to[lhsvar] == NULL) + graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack); + bitmap_set_bit (graph->points_to[lhsvar], rhsvar); + + if (graph->pointed_by[rhsvar] == NULL) + graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack); + bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar); + + /* Implicitly, *x = y */ + add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); + + /* All related variables are no longer direct nodes. */ + bitmap_clear_bit (graph->direct_nodes, rhsvar); + v = get_varinfo (rhsvar); + if (!v->is_full_var) + { + v = get_varinfo (v->head); + do + { + bitmap_clear_bit (graph->direct_nodes, v->id); + v = vi_next (v); + } + while (v != NULL); + } + bitmap_set_bit (graph->address_taken, rhsvar); + } + else if (lhsvar > anything_id + && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) + { + /* x = y */ + add_pred_graph_edge (graph, lhsvar, rhsvar); + /* Implicitly, *x = *y */ + add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, + FIRST_REF_NODE + rhsvar); + } + else if (lhs.offset != 0 || rhs.offset != 0) + { + if (rhs.offset != 0) + bitmap_clear_bit (graph->direct_nodes, lhs.var); + else if (lhs.offset != 0) + bitmap_clear_bit (graph->direct_nodes, rhs.var); + } + } +} + +/* Build the constraint graph, adding successor edges. */ + +static void +build_succ_graph (void) +{ + unsigned i, t; + constraint_t c; + + FOR_EACH_VEC_ELT (constraints, i, c) + { + struct constraint_expr lhs; + struct constraint_expr rhs; + unsigned int lhsvar; + unsigned int rhsvar; + + if (!c) + continue; + + lhs = c->lhs; + rhs = c->rhs; + lhsvar = find (lhs.var); + rhsvar = find (rhs.var); + + if (lhs.type == DEREF) + { + if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) + { + if (lhs.var == anything_id) + add_graph_edge (graph, storedanything_id, rhsvar); + else + add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); + } + } + else if (rhs.type == DEREF) + { + if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) + add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); + } + else if (rhs.type == ADDRESSOF) + { + /* x = &y */ + gcc_checking_assert (find (rhs.var) == rhs.var); + bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); + } + else if (lhsvar > anything_id + && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) + { + add_graph_edge (graph, lhsvar, rhsvar); + } + } + + /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */ + t = find (storedanything_id); + for (i = integer_id + 1; i < FIRST_REF_NODE; ++i) + { + if (get_varinfo (i)->may_have_pointers) + add_graph_edge (graph, find (i), t); + } + + /* Everything stored to ANYTHING also potentially escapes. */ + add_graph_edge (graph, find (escaped_id), t); +} + + +/* Changed variables on the last iteration. */ +static bitmap changed; + +/* Strongly Connected Component visitation info. */ + +class scc_info +{ +public: + scc_info (size_t size); + ~scc_info (); + + auto_sbitmap visited; + auto_sbitmap deleted; + unsigned int *dfs; + unsigned int *node_mapping; + int current_index; + auto_vec<unsigned> scc_stack; +}; + + +/* Recursive routine to find strongly connected components in GRAPH. + SI is the SCC info to store the information in, and N is the id of current + graph node we are processing. + + This is Tarjan's strongly connected component finding algorithm, as + modified by Nuutila to keep only non-root nodes on the stack. + The algorithm can be found in "On finding the strongly connected + connected components in a directed graph" by Esko Nuutila and Eljas + Soisalon-Soininen, in Information Processing Letters volume 49, + number 1, pages 9-14. */ + +static void +scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) +{ + unsigned int i; + bitmap_iterator bi; + unsigned int my_dfs; + + bitmap_set_bit (si->visited, n); + si->dfs[n] = si->current_index ++; + my_dfs = si->dfs[n]; + + /* Visit all the successors. */ + EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) + { + unsigned int w; + + if (i > LAST_REF_NODE) + break; + + w = find (i); + if (bitmap_bit_p (si->deleted, w)) + continue; + + if (!bitmap_bit_p (si->visited, w)) + scc_visit (graph, si, w); + + unsigned int t = find (w); + gcc_checking_assert (find (n) == n); + if (si->dfs[t] < si->dfs[n]) + si->dfs[n] = si->dfs[t]; + } + + /* See if any components have been identified. */ + if (si->dfs[n] == my_dfs) + { + if (si->scc_stack.length () > 0 + && si->dfs[si->scc_stack.last ()] >= my_dfs) + { + bitmap scc = BITMAP_ALLOC (NULL); + unsigned int lowest_node; + bitmap_iterator bi; + + bitmap_set_bit (scc, n); + + while (si->scc_stack.length () != 0 + && si->dfs[si->scc_stack.last ()] >= my_dfs) + { + unsigned int w = si->scc_stack.pop (); + + bitmap_set_bit (scc, w); + } + + lowest_node = bitmap_first_set_bit (scc); + gcc_assert (lowest_node < FIRST_REF_NODE); + + /* Collapse the SCC nodes into a single node, and mark the + indirect cycles. */ + EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) + { + if (i < FIRST_REF_NODE) + { + if (unite (lowest_node, i)) + unify_nodes (graph, lowest_node, i, false); + } + else + { + unite (lowest_node, i); + graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; + } + } + bitmap_set_bit (si->deleted, lowest_node); + } + else + bitmap_set_bit (si->deleted, n); + } + else + si->scc_stack.safe_push (n); +} + +/* Unify node FROM into node TO, updating the changed count if + necessary when UPDATE_CHANGED is true. */ + +static void +unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, + bool update_changed) +{ + gcc_checking_assert (to != from && find (to) == to); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Unifying %s to %s\n", + get_varinfo (from)->name, + get_varinfo (to)->name); + + if (update_changed) + stats.unified_vars_dynamic++; + else + stats.unified_vars_static++; + + merge_graph_nodes (graph, to, from); + if (merge_node_constraints (graph, to, from)) + { + if (update_changed) + bitmap_set_bit (changed, to); + } + + /* Mark TO as changed if FROM was changed. If TO was already marked + as changed, decrease the changed count. */ + + if (update_changed + && bitmap_clear_bit (changed, from)) + bitmap_set_bit (changed, to); + varinfo_t fromvi = get_varinfo (from); + if (fromvi->solution) + { + /* If the solution changes because of the merging, we need to mark + the variable as changed. */ + varinfo_t tovi = get_varinfo (to); + if (bitmap_ior_into (tovi->solution, fromvi->solution)) + { + if (update_changed) + bitmap_set_bit (changed, to); + } + + BITMAP_FREE (fromvi->solution); + if (fromvi->oldsolution) + BITMAP_FREE (fromvi->oldsolution); + + if (stats.iterations > 0 + && tovi->oldsolution) + BITMAP_FREE (tovi->oldsolution); + } + if (graph->succs[to]) + bitmap_clear_bit (graph->succs[to], to); +} + +/* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE + if the solution of TO changed. */ + +static bool +solve_add_graph_edge (constraint_graph_t graph, unsigned int to, + unsigned int from) +{ + /* Adding edges from the special vars is pointless. + They don't have sets that can change. */ + if (get_varinfo (from)->is_special_var) + return bitmap_ior_into (get_varinfo (to)->solution, + get_varinfo (from)->solution); + /* Merging the solution from ESCAPED needlessly increases + the set. Use ESCAPED as representative instead. */ + else if (from == find (escaped_id)) + return bitmap_set_bit (get_varinfo (to)->solution, escaped_id); + else if (get_varinfo (from)->may_have_pointers + && add_graph_edge (graph, to, from)) + return bitmap_ior_into (get_varinfo (to)->solution, + get_varinfo (from)->solution); + return false; +} + +/* Process a constraint C that represents x = *(y + off), using DELTA as the + starting solution for y. */ + +static void +do_sd_constraint (constraint_graph_t graph, constraint_t c, + bitmap delta, bitmap *expanded_delta) +{ + unsigned int lhs = c->lhs.var; + bool flag = false; + bitmap sol = get_varinfo (lhs)->solution; + unsigned int j; + bitmap_iterator bi; + HOST_WIDE_INT roffset = c->rhs.offset; + + /* Our IL does not allow this. */ + gcc_checking_assert (c->lhs.offset == 0); + + /* If the solution of Y contains anything it is good enough to transfer + this to the LHS. */ + if (bitmap_bit_p (delta, anything_id)) + { + flag |= bitmap_set_bit (sol, anything_id); + goto done; + } + + /* If we do not know at with offset the rhs is dereferenced compute + the reachability set of DELTA, conservatively assuming it is + dereferenced at all valid offsets. */ + if (roffset == UNKNOWN_OFFSET) + { + delta = solution_set_expand (delta, expanded_delta); + /* No further offset processing is necessary. */ + roffset = 0; + } + + /* For each variable j in delta (Sol(y)), add + an edge in the graph from j to x, and union Sol(j) into Sol(x). */ + EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) + { + varinfo_t v = get_varinfo (j); + HOST_WIDE_INT fieldoffset = v->offset + roffset; + unsigned HOST_WIDE_INT size = v->size; + unsigned int t; + + if (v->is_full_var) + ; + else if (roffset != 0) + { + if (fieldoffset < 0) + v = get_varinfo (v->head); + else + v = first_or_preceding_vi_for_offset (v, fieldoffset); + } + + /* We have to include all fields that overlap the current field + shifted by roffset. */ + do + { + t = find (v->id); + + flag |= solve_add_graph_edge (graph, lhs, t); + + if (v->is_full_var + || v->next == 0) + break; + + v = vi_next (v); + } + while (v->offset < fieldoffset + size); + } + +done: + /* If the LHS solution changed, mark the var as changed. */ + if (flag) + bitmap_set_bit (changed, lhs); +} + +/* Process a constraint C that represents *(x + off) = y using DELTA + as the starting solution for x. */ + +static void +do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta) +{ + unsigned int rhs = c->rhs.var; + bitmap sol = get_varinfo (rhs)->solution; + unsigned int j; + bitmap_iterator bi; + HOST_WIDE_INT loff = c->lhs.offset; + bool escaped_p = false; + + /* Our IL does not allow this. */ + gcc_checking_assert (c->rhs.offset == 0); + + /* If the solution of y contains ANYTHING simply use the ANYTHING + solution. This avoids needlessly increasing the points-to sets. */ + if (bitmap_bit_p (sol, anything_id)) + sol = get_varinfo (find (anything_id))->solution; + + /* If the solution for x contains ANYTHING we have to merge the + solution of y into all pointer variables which we do via + STOREDANYTHING. */ + if (bitmap_bit_p (delta, anything_id)) + { + unsigned t = find (storedanything_id); + if (solve_add_graph_edge (graph, t, rhs)) + bitmap_set_bit (changed, t); + return; + } + + /* If we do not know at with offset the rhs is dereferenced compute + the reachability set of DELTA, conservatively assuming it is + dereferenced at all valid offsets. */ + if (loff == UNKNOWN_OFFSET) + { + delta = solution_set_expand (delta, expanded_delta); + loff = 0; + } + + /* For each member j of delta (Sol(x)), add an edge from y to j and + union Sol(y) into Sol(j) */ + EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) + { + varinfo_t v = get_varinfo (j); + unsigned int t; + HOST_WIDE_INT fieldoffset = v->offset + loff; + unsigned HOST_WIDE_INT size = v->size; + + if (v->is_full_var) + ; + else if (loff != 0) + { + if (fieldoffset < 0) + v = get_varinfo (v->head); + else + v = first_or_preceding_vi_for_offset (v, fieldoffset); + } + + /* We have to include all fields that overlap the current field + shifted by loff. */ + do + { + if (v->may_have_pointers) + { + /* If v is a global variable then this is an escape point. */ + if (v->is_global_var + && !escaped_p) + { + t = find (escaped_id); + if (add_graph_edge (graph, t, rhs) + && bitmap_ior_into (get_varinfo (t)->solution, sol)) + bitmap_set_bit (changed, t); + /* Enough to let rhs escape once. */ + escaped_p = true; + } + + if (v->is_special_var) + break; + + t = find (v->id); + + if (solve_add_graph_edge (graph, t, rhs)) + bitmap_set_bit (changed, t); + } + + if (v->is_full_var + || v->next == 0) + break; + + v = vi_next (v); + } + while (v->offset < fieldoffset + size); + } +} + +/* Handle a non-simple (simple meaning requires no iteration), + constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ + +static void +do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta, + bitmap *expanded_delta) +{ + if (c->lhs.type == DEREF) + { + if (c->rhs.type == ADDRESSOF) + { + gcc_unreachable (); + } + else + { + /* *x = y */ + do_ds_constraint (c, delta, expanded_delta); + } + } + else if (c->rhs.type == DEREF) + { + /* x = *y */ + if (!(get_varinfo (c->lhs.var)->is_special_var)) + do_sd_constraint (graph, c, delta, expanded_delta); + } + else + { + bitmap tmp; + bool flag = false; + + gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR + && c->rhs.offset != 0 && c->lhs.offset == 0); + tmp = get_varinfo (c->lhs.var)->solution; + + flag = set_union_with_increment (tmp, delta, c->rhs.offset, + expanded_delta); + + if (flag) + bitmap_set_bit (changed, c->lhs.var); + } +} + +/* Initialize and return a new SCC info structure. */ + +scc_info::scc_info (size_t size) : + visited (size), deleted (size), current_index (0), scc_stack (1) +{ + bitmap_clear (visited); + bitmap_clear (deleted); + node_mapping = XNEWVEC (unsigned int, size); + dfs = XCNEWVEC (unsigned int, size); + + for (size_t i = 0; i < size; i++) + node_mapping[i] = i; +} + +/* Free an SCC info structure pointed to by SI. */ + +scc_info::~scc_info () +{ + free (node_mapping); + free (dfs); +} + + +/* Find indirect cycles in GRAPH that occur, using strongly connected + components, and note them in the indirect cycles map. + + This technique comes from Ben Hardekopf and Calvin Lin, + "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of + Lines of Code", submitted to PLDI 2007. */ + +static void +find_indirect_cycles (constraint_graph_t graph) +{ + unsigned int i; + unsigned int size = graph->size; + scc_info si (size); + + for (i = 0; i < MIN (LAST_REF_NODE, size); i++) + if (!bitmap_bit_p (si.visited, i) && find (i) == i) + scc_visit (graph, &si, i); +} + +/* Visit the graph in topological order starting at node N, and store the + order in TOPO_ORDER using VISITED to indicate visited nodes. */ + +static void +topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order, + sbitmap visited, unsigned int n) +{ + bitmap_iterator bi; + unsigned int j; + + bitmap_set_bit (visited, n); + + if (graph->succs[n]) + EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) + { + unsigned k = find (j); + if (!bitmap_bit_p (visited, k)) + topo_visit (graph, topo_order, visited, k); + } + + /* Also consider copy with offset complex constraints as implicit edges. */ + for (auto c : graph->complex[n]) + { + /* Constraints are ordered so that SCALAR = SCALAR appear first. */ + if (c->lhs.type != SCALAR || c->rhs.type != SCALAR) + break; + gcc_checking_assert (c->rhs.var == n); + unsigned k = find (c->lhs.var); + if (!bitmap_bit_p (visited, k)) + topo_visit (graph, topo_order, visited, k); + } + + topo_order.quick_push (n); +} + +/* Compute a topological ordering for GRAPH, and return the result. */ + +static auto_vec<unsigned> +compute_topo_order (constraint_graph_t graph) +{ + unsigned int i; + unsigned int size = graph->size; + + auto_sbitmap visited (size); + bitmap_clear (visited); + + /* For the heuristic in add_graph_edge to work optimally make sure to + first visit the connected component of the graph containing + ESCAPED. Do this by extracting the connected component + with ESCAPED and append that to all other components as solve_graph + pops from the order. */ + auto_vec<unsigned> tail (size); + topo_visit (graph, tail, visited, find (escaped_id)); + + auto_vec<unsigned> topo_order (size); + + for (i = 0; i != size; ++i) + if (!bitmap_bit_p (visited, i) && find (i) == i) + topo_visit (graph, topo_order, visited, i); + + topo_order.splice (tail); + return topo_order; +} + +/* Structure used to for hash value numbering of pointer equivalence + classes. */ + +typedef struct equiv_class_label +{ + hashval_t hashcode; + unsigned int equivalence_class; + bitmap labels; +} *equiv_class_label_t; +typedef const struct equiv_class_label *const_equiv_class_label_t; + +/* Equiv_class_label hashtable helpers. */ + +struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label> +{ + static inline hashval_t hash (const equiv_class_label *); + static inline bool equal (const equiv_class_label *, + const equiv_class_label *); +}; + +/* A hashtable for mapping a bitmap of labels->pointer equivalence + classes. */ +static hash_table<equiv_class_hasher> *pointer_equiv_class_table; + +/* A hashtable for mapping a bitmap of labels->location equivalence + classes. */ +static hash_table<equiv_class_hasher> *location_equiv_class_table; + +/* 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<equiv_class_hasher> *table, + bitmap labels) +{ + equiv_class_label **slot; + equiv_class_label ecl; + + ecl.labels = labels; + ecl.hashcode = bitmap_hash (labels); + slot = table->find_slot (&ecl, INSERT); + if (!*slot) + { + *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label); + (*slot)->labels = labels; + (*slot)->hashcode = ecl.hashcode; + (*slot)->equivalence_class = 0; + } + + return *slot; +} + + +/* Perform offline variable substitution. + + This is a worst case quadratic time way of identifying variables + that must have equivalent points-to sets, including those caused by + static cycles, and single entry subgraphs, in the constraint graph. + + The technique is described in "Exploiting Pointer and Location + Equivalence to Optimize Pointer Analysis. In the 14th International + Static Analysis Symposium (SAS), August 2007." It is known as the + "HU" algorithm, and is equivalent to value numbering the collapsed + constraint graph including evaluating unions. + + The general method of finding equivalence classes is as follows: + Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. + Initialize all non-REF nodes to be direct nodes. + For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh + variable} + For each constraint containing the dereference, we also do the same + thing. + + We then compute SCC's in the graph and unify nodes in the same SCC, + including pts sets. + + For each non-collapsed node x: + Visit all unvisited explicit incoming edges. + Ignoring all non-pointers, set pts(x) = Union of pts(a) for y + where y->x. + Lookup the equivalence class for pts(x). + If we found one, equivalence_class(x) = found class. + Otherwise, equivalence_class(x) = new class, and new_class is + added to the lookup table. + + All direct nodes with the same equivalence class can be replaced + with a single representative node. + All unlabeled nodes (label == 0) are not pointers and all edges + involving them can be eliminated. + We perform these optimizations during rewrite_constraints + + In addition to pointer equivalence class finding, we also perform + location equivalence class finding. This is the set of variables + that always appear together in points-to sets. We use this to + compress the size of the points-to sets. */ + +/* Current maximum pointer equivalence class id. */ +static int pointer_equiv_class; + +/* Current maximum location equivalence class id. */ +static int location_equiv_class; + +/* Recursive routine to find strongly connected components in GRAPH, + and label it's nodes with DFS numbers. */ + +static void +condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) +{ + unsigned int i; + bitmap_iterator bi; + unsigned int my_dfs; + + gcc_checking_assert (si->node_mapping[n] == n); + bitmap_set_bit (si->visited, n); + si->dfs[n] = si->current_index ++; + my_dfs = si->dfs[n]; + + /* Visit all the successors. */ + EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) + { + unsigned int w = si->node_mapping[i]; + + if (bitmap_bit_p (si->deleted, w)) + continue; + + if (!bitmap_bit_p (si->visited, w)) + condense_visit (graph, si, w); + + unsigned int t = si->node_mapping[w]; + gcc_checking_assert (si->node_mapping[n] == n); + if (si->dfs[t] < si->dfs[n]) + si->dfs[n] = si->dfs[t]; + } + + /* Visit all the implicit predecessors. */ + EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) + { + unsigned int w = si->node_mapping[i]; + + if (bitmap_bit_p (si->deleted, w)) + continue; + + if (!bitmap_bit_p (si->visited, w)) + condense_visit (graph, si, w); + + unsigned int t = si->node_mapping[w]; + gcc_assert (si->node_mapping[n] == n); + if (si->dfs[t] < si->dfs[n]) + si->dfs[n] = si->dfs[t]; + } + + /* See if any components have been identified. */ + if (si->dfs[n] == my_dfs) + { + if (si->scc_stack.length () != 0 + && si->dfs[si->scc_stack.last ()] >= my_dfs) + { + /* Find the first node of the SCC and do non-bitmap work. */ + bool direct_p = true; + unsigned first = si->scc_stack.length (); + do + { + --first; + unsigned int w = si->scc_stack[first]; + si->node_mapping[w] = n; + if (!bitmap_bit_p (graph->direct_nodes, w)) + direct_p = false; + } + while (first > 0 + && si->dfs[si->scc_stack[first - 1]] >= my_dfs); + if (!direct_p) + bitmap_clear_bit (graph->direct_nodes, n); + + /* Want to reduce to node n, push that first. */ + si->scc_stack.reserve (1); + si->scc_stack.quick_push (si->scc_stack[first]); + si->scc_stack[first] = n; + + unsigned scc_size = si->scc_stack.length () - first; + unsigned split = scc_size / 2; + unsigned carry = scc_size - split * 2; + while (split > 0) + { + for (unsigned i = 0; i < split; ++i) + { + unsigned a = si->scc_stack[first + i]; + unsigned b = si->scc_stack[first + split + carry + i]; + + /* Unify our nodes. */ + if (graph->preds[b]) + { + if (!graph->preds[a]) + std::swap (graph->preds[a], graph->preds[b]); + else + bitmap_ior_into_and_free (graph->preds[a], + &graph->preds[b]); + } + if (graph->implicit_preds[b]) + { + if (!graph->implicit_preds[a]) + std::swap (graph->implicit_preds[a], + graph->implicit_preds[b]); + else + bitmap_ior_into_and_free (graph->implicit_preds[a], + &graph->implicit_preds[b]); + } + if (graph->points_to[b]) + { + if (!graph->points_to[a]) + std::swap (graph->points_to[a], graph->points_to[b]); + else + bitmap_ior_into_and_free (graph->points_to[a], + &graph->points_to[b]); + } + } + unsigned remain = split + carry; + split = remain / 2; + carry = remain - split * 2; + } + /* Actually pop the SCC. */ + si->scc_stack.truncate (first); + } + bitmap_set_bit (si->deleted, n); + } + else + si->scc_stack.safe_push (n); +} + +/* Label pointer equivalences. + + This performs a value numbering of the constraint graph to + discover which variables will always have the same points-to sets + under the current set of constraints. + + The way it value numbers is to store the set of points-to bits + generated by the constraints and graph edges. This is just used as a + hash and equality comparison. The *actual set of points-to bits* is + completely irrelevant, in that we don't care about being able to + extract them later. + + The equality values (currently bitmaps) just have to satisfy a few + constraints, the main ones being: + 1. The combining operation must be order independent. + 2. The end result of a given set of operations must be unique iff the + combination of input values is unique + 3. Hashable. */ + +static void +label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) +{ + unsigned int i, first_pred; + bitmap_iterator bi; + + bitmap_set_bit (si->visited, n); + + /* Label and union our incoming edges's points to sets. */ + first_pred = -1U; + EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) + { + unsigned int w = si->node_mapping[i]; + if (!bitmap_bit_p (si->visited, w)) + label_visit (graph, si, w); + + /* Skip unused edges. */ + if (w == n || graph->pointer_label[w] == 0) + continue; + + if (graph->points_to[w]) + { + if (!graph->points_to[n]) + { + if (first_pred == -1U) + first_pred = w; + else + { + graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); + bitmap_ior (graph->points_to[n], + graph->points_to[first_pred], + graph->points_to[w]); + } + } + else + bitmap_ior_into (graph->points_to[n], graph->points_to[w]); + } + } + + /* Indirect nodes get fresh variables and a new pointer equiv class. */ + if (!bitmap_bit_p (graph->direct_nodes, n)) + { + if (!graph->points_to[n]) + { + graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); + if (first_pred != -1U) + bitmap_copy (graph->points_to[n], graph->points_to[first_pred]); + } + bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); + graph->pointer_label[n] = pointer_equiv_class++; + equiv_class_label_t ecl; + ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, + graph->points_to[n]); + ecl->equivalence_class = graph->pointer_label[n]; + return; + } + + /* If there was only a single non-empty predecessor the pointer equiv + class is the same. */ + if (!graph->points_to[n]) + { + if (first_pred != -1U) + { + graph->pointer_label[n] = graph->pointer_label[first_pred]; + graph->points_to[n] = graph->points_to[first_pred]; + } + return; + } + + if (!bitmap_empty_p (graph->points_to[n])) + { + equiv_class_label_t ecl; + ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, + graph->points_to[n]); + if (ecl->equivalence_class == 0) + ecl->equivalence_class = pointer_equiv_class++; + else + { + BITMAP_FREE (graph->points_to[n]); + graph->points_to[n] = ecl->labels; + } + graph->pointer_label[n] = ecl->equivalence_class; + } +} + +/* Print the pred graph in dot format. */ + +static void +dump_pred_graph (class scc_info *si, FILE *file) +{ + unsigned int i; + + /* Only print the graph if it has already been initialized: */ + if (!graph) + return; + + /* Prints the header of the dot file: */ + fprintf (file, "strict digraph {\n"); + fprintf (file, " node [\n shape = box\n ]\n"); + fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); + fprintf (file, "\n // List of nodes and complex constraints in " + "the constraint graph:\n"); + + /* The next lines print the nodes in the graph together with the + complex constraints attached to them. */ + for (i = 1; i < graph->size; i++) + { + if (i == FIRST_REF_NODE) + continue; + if (si->node_mapping[i] != i) + continue; + if (i < FIRST_REF_NODE) + fprintf (file, "\"%s\"", get_varinfo (i)->name); + else + fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); + if (graph->points_to[i] + && !bitmap_empty_p (graph->points_to[i])) + { + if (i < FIRST_REF_NODE) + fprintf (file, "[label=\"%s = {", get_varinfo (i)->name); + else + fprintf (file, "[label=\"*%s = {", + get_varinfo (i - FIRST_REF_NODE)->name); + unsigned j; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi) + fprintf (file, " %d", j); + fprintf (file, " }\"]"); + } + fprintf (file, ";\n"); + } + + /* Go over the edges. */ + fprintf (file, "\n // Edges in the constraint graph:\n"); + for (i = 1; i < graph->size; i++) + { + unsigned j; + bitmap_iterator bi; + if (si->node_mapping[i] != i) + continue; + EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi) + { + unsigned from = si->node_mapping[j]; + if (from < FIRST_REF_NODE) + fprintf (file, "\"%s\"", get_varinfo (from)->name); + else + fprintf (file, "\"*%s\"", + get_varinfo (from - FIRST_REF_NODE)->name); + fprintf (file, " -> "); + if (i < FIRST_REF_NODE) + fprintf (file, "\"%s\"", get_varinfo (i)->name); + else + fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); + fprintf (file, ";\n"); + } + } + + /* Prints the tail of the dot file. */ + fprintf (file, "}\n"); +} + +/* Perform offline variable substitution, discovering equivalence + classes, and eliminating non-pointer variables. */ + +static class scc_info * +perform_var_substitution (constraint_graph_t graph) +{ + unsigned int i; + unsigned int size = graph->size; + scc_info *si = new scc_info (size); + + bitmap_obstack_initialize (&iteration_obstack); + gcc_obstack_init (&equiv_class_obstack); + pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511); + location_equiv_class_table + = new hash_table<equiv_class_hasher> (511); + pointer_equiv_class = 1; + location_equiv_class = 1; + + /* Condense the nodes, which means to find SCC's, count incoming + predecessors, and unite nodes in SCC's. */ + for (i = 1; i < FIRST_REF_NODE; i++) + if (!bitmap_bit_p (si->visited, si->node_mapping[i])) + condense_visit (graph, si, si->node_mapping[i]); + + if (dump_file && (dump_flags & TDF_GRAPH)) + { + fprintf (dump_file, "\n\n// The constraint graph before var-substitution " + "in dot format:\n"); + dump_pred_graph (si, dump_file); + fprintf (dump_file, "\n\n"); + } + + bitmap_clear (si->visited); + /* Actually the label the nodes for pointer equivalences. */ + for (i = 1; i < FIRST_REF_NODE; i++) + if (!bitmap_bit_p (si->visited, si->node_mapping[i])) + label_visit (graph, si, si->node_mapping[i]); + + /* Calculate location equivalence labels. */ + for (i = 1; i < FIRST_REF_NODE; i++) + { + bitmap pointed_by; + bitmap_iterator bi; + unsigned int j; + + if (!graph->pointed_by[i]) + continue; + pointed_by = BITMAP_ALLOC (&iteration_obstack); + + /* Translate the pointed-by mapping for pointer equivalence + labels. */ + EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) + { + bitmap_set_bit (pointed_by, + graph->pointer_label[si->node_mapping[j]]); + } + /* The original pointed_by is now dead. */ + BITMAP_FREE (graph->pointed_by[i]); + + /* Look up the location equivalence label if one exists, or make + one otherwise. */ + equiv_class_label_t ecl; + ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by); + if (ecl->equivalence_class == 0) + ecl->equivalence_class = location_equiv_class++; + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Found location equivalence for node %s\n", + get_varinfo (i)->name); + BITMAP_FREE (pointed_by); + } + graph->loc_label[i] = ecl->equivalence_class; + + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + for (i = 1; i < FIRST_REF_NODE; i++) + { + unsigned j = si->node_mapping[i]; + if (j != i) + { + fprintf (dump_file, "%s node id %d ", + bitmap_bit_p (graph->direct_nodes, i) + ? "Direct" : "Indirect", i); + if (i < FIRST_REF_NODE) + fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); + else + fprintf (dump_file, "\"*%s\"", + get_varinfo (i - FIRST_REF_NODE)->name); + fprintf (dump_file, " mapped to SCC leader node id %d ", j); + if (j < FIRST_REF_NODE) + fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name); + else + fprintf (dump_file, "\"*%s\"\n", + get_varinfo (j - FIRST_REF_NODE)->name); + } + else + { + fprintf (dump_file, + "Equivalence classes for %s node id %d ", + bitmap_bit_p (graph->direct_nodes, i) + ? "direct" : "indirect", i); + if (i < FIRST_REF_NODE) + fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); + else + fprintf (dump_file, "\"*%s\"", + get_varinfo (i - FIRST_REF_NODE)->name); + fprintf (dump_file, + ": pointer %d, location %d\n", + graph->pointer_label[i], graph->loc_label[i]); + } + } + + /* Quickly eliminate our non-pointer variables. */ + + for (i = 1; i < FIRST_REF_NODE; i++) + { + unsigned int node = si->node_mapping[i]; + + if (graph->pointer_label[node] == 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "%s is a non-pointer variable, eliminating edges.\n", + get_varinfo (node)->name); + stats.nonpointer_vars++; + clear_edges_for_node (graph, node); + } + } + + return si; +} + +/* Free information that was only necessary for variable + substitution. */ + +static void +free_var_substitution_info (class scc_info *si) +{ + delete si; + free (graph->pointer_label); + free (graph->loc_label); + free (graph->pointed_by); + free (graph->points_to); + free (graph->eq_rep); + sbitmap_free (graph->direct_nodes); + delete pointer_equiv_class_table; + pointer_equiv_class_table = NULL; + delete location_equiv_class_table; + location_equiv_class_table = NULL; + obstack_free (&equiv_class_obstack, NULL); + bitmap_obstack_release (&iteration_obstack); +} + +/* Return an existing node that is equivalent to NODE, which has + equivalence class LABEL, if one exists. Return NODE otherwise. */ + +static unsigned int +find_equivalent_node (constraint_graph_t graph, + unsigned int node, unsigned int label) +{ + /* If the address version of this variable is unused, we can + substitute it for anything else with the same label. + Otherwise, we know the pointers are equivalent, but not the + locations, and we can unite them later. */ + + if (!bitmap_bit_p (graph->address_taken, node)) + { + gcc_checking_assert (label < graph->size); + + if (graph->eq_rep[label] != -1) + { + /* Unify the two variables since we know they are equivalent. */ + if (unite (graph->eq_rep[label], node)) + unify_nodes (graph, graph->eq_rep[label], node, false); + return graph->eq_rep[label]; + } + else + { + graph->eq_rep[label] = node; + graph->pe_rep[label] = node; + } + } + else + { + gcc_checking_assert (label < graph->size); + graph->pe[node] = label; + if (graph->pe_rep[label] == -1) + graph->pe_rep[label] = node; + } + + return node; +} + +/* Unite pointer equivalent but not location equivalent nodes in + GRAPH. This may only be performed once variable substitution is + finished. */ + +static void +unite_pointer_equivalences (constraint_graph_t graph) +{ + unsigned int i; + + /* Go through the pointer equivalences and unite them to their + representative, if they aren't already. */ + for (i = 1; i < FIRST_REF_NODE; i++) + { + unsigned int label = graph->pe[i]; + if (label) + { + int label_rep = graph->pe_rep[label]; + + if (label_rep == -1) + continue; + + label_rep = find (label_rep); + if (label_rep >= 0 && unite (label_rep, find (i))) + unify_nodes (graph, label_rep, i, false); + } + } +} + +/* Move complex constraints to the GRAPH nodes they belong to. */ + +static void +move_complex_constraints (constraint_graph_t graph) +{ + int i; + constraint_t c; + + FOR_EACH_VEC_ELT (constraints, i, c) + { + if (c) + { + struct constraint_expr lhs = c->lhs; + struct constraint_expr rhs = c->rhs; + + if (lhs.type == DEREF) + { + insert_into_complex (graph, lhs.var, c); + } + else if (rhs.type == DEREF) + { + if (!(get_varinfo (lhs.var)->is_special_var)) + insert_into_complex (graph, rhs.var, c); + } + else if (rhs.type != ADDRESSOF && lhs.var > anything_id + && (lhs.offset != 0 || rhs.offset != 0)) + { + insert_into_complex (graph, rhs.var, c); + } + } + } +} + +/* Optimize and rewrite complex constraints while performing + collapsing of equivalent nodes. SI is the SCC_INFO that is the + result of perform_variable_substitution. */ + +static void +rewrite_constraints (constraint_graph_t graph, + class scc_info *si) +{ + int i; + constraint_t c; + + if (flag_checking) + { + for (unsigned int j = 0; j < graph->size; j++) + gcc_assert (find (j) == j); + } + + FOR_EACH_VEC_ELT (constraints, i, c) + { + struct constraint_expr lhs = c->lhs; + struct constraint_expr rhs = c->rhs; + unsigned int lhsvar = find (lhs.var); + unsigned int rhsvar = find (rhs.var); + unsigned int lhsnode, rhsnode; + unsigned int lhslabel, rhslabel; + + lhsnode = si->node_mapping[lhsvar]; + rhsnode = si->node_mapping[rhsvar]; + lhslabel = graph->pointer_label[lhsnode]; + rhslabel = graph->pointer_label[rhsnode]; + + /* See if it is really a non-pointer variable, and if so, ignore + the constraint. */ + if (lhslabel == 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + + fprintf (dump_file, "%s is a non-pointer variable, " + "ignoring constraint:", + get_varinfo (lhs.var)->name); + dump_constraint (dump_file, c); + fprintf (dump_file, "\n"); + } + constraints[i] = NULL; + continue; + } + + if (rhslabel == 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + + fprintf (dump_file, "%s is a non-pointer variable, " + "ignoring constraint:", + get_varinfo (rhs.var)->name); + dump_constraint (dump_file, c); + fprintf (dump_file, "\n"); + } + constraints[i] = NULL; + continue; + } + + lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); + rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); + c->lhs.var = lhsvar; + c->rhs.var = rhsvar; + } +} + +/* Eliminate indirect cycles involving NODE. Return true if NODE was + part of an SCC, false otherwise. */ + +static bool +eliminate_indirect_cycles (unsigned int node) +{ + if (graph->indirect_cycles[node] != -1 + && !bitmap_empty_p (get_varinfo (node)->solution)) + { + unsigned int i; + auto_vec<unsigned> queue; + int queuepos; + unsigned int to = find (graph->indirect_cycles[node]); + bitmap_iterator bi; + + /* We can't touch the solution set and call unify_nodes + at the same time, because unify_nodes is going to do + bitmap unions into it. */ + + EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) + { + if (find (i) == i && i != to) + { + if (unite (to, i)) + queue.safe_push (i); + } + } + + for (queuepos = 0; + queue.iterate (queuepos, &i); + queuepos++) + { + unify_nodes (graph, to, i, true); + } + return true; + } + return false; +} + +/* Solve the constraint graph GRAPH using our worklist solver. + This is based on the PW* family of solvers from the "Efficient Field + Sensitive Pointer Analysis for C" paper. + It works by iterating over all the graph nodes, processing the complex + constraints and propagating the copy constraints, until everything stops + changed. This corresponds to steps 6-8 in the solving list given above. */ + +static void +solve_graph (constraint_graph_t graph) +{ + unsigned int size = graph->size; + unsigned int i; + bitmap pts; + + changed = BITMAP_ALLOC (NULL); + + /* Mark all initial non-collapsed nodes as changed. */ + for (i = 1; i < size; i++) + { + varinfo_t ivi = get_varinfo (i); + if (find (i) == i && !bitmap_empty_p (ivi->solution) + && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) + || graph->complex[i].length () > 0)) + bitmap_set_bit (changed, i); + } + + /* Allocate a bitmap to be used to store the changed bits. */ + pts = BITMAP_ALLOC (&pta_obstack); + + while (!bitmap_empty_p (changed)) + { + unsigned int i; + stats.iterations++; + + bitmap_obstack_initialize (&iteration_obstack); + + auto_vec<unsigned> topo_order = compute_topo_order (graph); + while (topo_order.length () != 0) + { + i = topo_order.pop (); + + /* If this variable is not a representative, skip it. */ + if (find (i) != i) + continue; + + /* In certain indirect cycle cases, we may merge this + variable to another. */ + if (eliminate_indirect_cycles (i) && find (i) != i) + continue; + + /* If the node has changed, we need to process the + complex constraints and outgoing edges again. For complex + constraints that modify i itself, like the common group of + callarg = callarg + UNKNOWN; + callarg = *callarg + UNKNOWN; + *callarg = callescape; + make sure to iterate immediately because that maximizes + cache reuse and expands the graph quickest, leading to + better visitation order in the next iteration. */ + while (bitmap_clear_bit (changed, i)) + { + bitmap solution; + vec<constraint_t> &complex = graph->complex[i]; + varinfo_t vi = get_varinfo (i); + bool solution_empty; + + /* Compute the changed set of solution bits. If anything + is in the solution just propagate that. */ + if (bitmap_bit_p (vi->solution, anything_id)) + { + /* If anything is also in the old solution there is + nothing to do. + ??? But we shouldn't ended up with "changed" set ... */ + if (vi->oldsolution + && bitmap_bit_p (vi->oldsolution, anything_id)) + break; + bitmap_copy (pts, get_varinfo (find (anything_id))->solution); + } + else if (vi->oldsolution) + bitmap_and_compl (pts, vi->solution, vi->oldsolution); + else + bitmap_copy (pts, vi->solution); + + if (bitmap_empty_p (pts)) + break; + + if (vi->oldsolution) + bitmap_ior_into (vi->oldsolution, pts); + else + { + vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack); + bitmap_copy (vi->oldsolution, pts); + } + + solution = vi->solution; + solution_empty = bitmap_empty_p (solution); + + /* Process the complex constraints. */ + hash_set<constraint_t> *cvisited = nullptr; + if (flag_checking) + cvisited = new hash_set<constraint_t>; + bitmap expanded_pts = NULL; + for (unsigned j = 0; j < complex.length (); ++j) + { + constraint_t c = complex[j]; + /* At unification time only the directly involved nodes + will get their complex constraints updated. Update + our complex constraints now but keep the constraint + vector sorted and clear of duplicates. Also make + sure to evaluate each prevailing constraint only once. */ + unsigned int new_lhs = find (c->lhs.var); + unsigned int new_rhs = find (c->rhs.var); + if (c->lhs.var != new_lhs || c->rhs.var != new_rhs) + { + constraint tem = *c; + tem.lhs.var = new_lhs; + tem.rhs.var = new_rhs; + unsigned int place + = complex.lower_bound (&tem, constraint_less); + c->lhs.var = new_lhs; + c->rhs.var = new_rhs; + if (place != j) + { + complex.ordered_remove (j); + if (j < place) + --place; + if (place < complex.length ()) + { + if (constraint_equal (*complex[place], *c)) + { + j--; + continue; + } + else + complex.safe_insert (place, c); + } + else + complex.quick_push (c); + if (place > j) + { + j--; + continue; + } + } + } + + /* The only complex constraint that can change our + solution to non-empty, given an empty solution, + is a constraint where the lhs side is receiving + some set from elsewhere. */ + if (cvisited && cvisited->add (c)) + gcc_unreachable (); + if (!solution_empty || c->lhs.type != DEREF) + do_complex_constraint (graph, c, pts, &expanded_pts); + } + if (cvisited) + { + /* When checking, verify the order of constraints is + maintained and each constraint is evaluated exactly + once. */ + for (unsigned j = 1; j < complex.length (); ++j) + gcc_assert (constraint_less (complex[j-1], complex[j])); + gcc_assert (cvisited->elements () == complex.length ()); + delete cvisited; + } + BITMAP_FREE (expanded_pts); + + solution_empty = bitmap_empty_p (solution); + + if (!solution_empty) + { + bitmap_iterator bi; + unsigned eff_escaped_id = find (escaped_id); + unsigned j; + + /* Propagate solution to all successors. */ + unsigned to_remove = ~0U; + EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], + 0, j, bi) + { + if (to_remove != ~0U) + { + bitmap_clear_bit (graph->succs[i], to_remove); + to_remove = ~0U; + } + unsigned int to = find (j); + if (to != j) + { + /* Update the succ graph, avoiding duplicate + work. */ + to_remove = j; + if (! bitmap_set_bit (graph->succs[i], to)) + continue; + /* We eventually end up processing 'to' twice + as it is undefined whether bitmap iteration + iterates over bits set during iteration. + Play safe instead of doing tricks. */ + } + /* Don't try to propagate to ourselves. */ + if (to == i) + { + to_remove = j; + continue; + } + /* Early node unification can lead to edges from + escaped - remove them. */ + if (i == eff_escaped_id) + { + to_remove = j; + if (bitmap_set_bit (get_varinfo (to)->solution, + escaped_id)) + bitmap_set_bit (changed, to); + continue; + } + + if (bitmap_ior_into (get_varinfo (to)->solution, pts)) + bitmap_set_bit (changed, to); + } + if (to_remove != ~0U) + bitmap_clear_bit (graph->succs[i], to_remove); + } + } + } + bitmap_obstack_release (&iteration_obstack); + } + + BITMAP_FREE (pts); + BITMAP_FREE (changed); + bitmap_obstack_release (&oldpta_obstack); +} + +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 |