/* 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