+ if (si->dfs[t] < si->dfs[nnode])
+ 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 (TEST_BIT (si->deleted, w))
+ continue;
+
+ if (!TEST_BIT (si->visited, w))
+ condense_visit (graph, si, w);
+ {
+ unsigned int t = si->node_mapping[w];
+ unsigned int nnode = si->node_mapping[n];
+ gcc_assert (nnode == n);
+
+ if (si->dfs[t] < si->dfs[nnode])
+ si->dfs[n] = si->dfs[t];
+ }
+ }
+
+ /* See if any components have been identified. */
+ if (si->dfs[n] == my_dfs)
+ {
+ while (VEC_length (unsigned, si->scc_stack) != 0
+ && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
+ {
+ unsigned int w = VEC_pop (unsigned, si->scc_stack);
+ si->node_mapping[w] = n;
+
+ if (!TEST_BIT (graph->direct_nodes, w))
+ RESET_BIT (graph->direct_nodes, n);
+
+ /* Unify our nodes. */
+ if (graph->preds[w])
+ {
+ if (!graph->preds[n])
+ graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior_into (graph->preds[n], graph->preds[w]);
+ }
+ if (graph->implicit_preds[w])
+ {
+ if (!graph->implicit_preds[n])
+ graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior_into (graph->implicit_preds[n],
+ graph->implicit_preds[w]);
+ }
+ if (graph->points_to[w])
+ {
+ if (!graph->points_to[n])
+ graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior_into (graph->points_to[n],
+ graph->points_to[w]);
+ }
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
+ {
+ unsigned int rep = si->node_mapping[i];
+ graph->number_incoming[rep]++;
+ }
+ }
+ SET_BIT (si->deleted, n);
+ }
+ else
+ VEC_safe_push (unsigned, heap, si->scc_stack, n);
+}
+
+/* Label pointer equivalences. */
+
+static void
+label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+{
+ unsigned int i;
+ bitmap_iterator bi;
+ SET_BIT (si->visited, n);
+
+ if (!graph->points_to[n])
+ graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+
+ /* Label and union our incoming edges's points to sets. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
+ {
+ unsigned int w = si->node_mapping[i];
+ if (!TEST_BIT (si->visited, w))
+ label_visit (graph, si, w);
+
+ /* Skip unused edges */
+ if (w == n || graph->pointer_label[w] == 0)
+ {
+ graph->number_incoming[w]--;
+ continue;
+ }
+ if (graph->points_to[w])
+ bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
+
+ /* If all incoming edges to w have been processed and
+ graph->points_to[w] was not stored in the hash table, we can
+ free it. */
+ graph->number_incoming[w]--;
+ if (!graph->number_incoming[w] && !TEST_BIT (graph->pt_used, w))
+ {
+ BITMAP_FREE (graph->points_to[w]);
+ }
+ }
+ /* Indirect nodes get fresh variables. */
+ if (!TEST_BIT (graph->direct_nodes, n))
+ bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
+
+ if (!bitmap_empty_p (graph->points_to[n]))
+ {
+ unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
+ graph->points_to[n]);
+ if (!label)
+ {
+ SET_BIT (graph->pt_used, n);
+ label = pointer_equiv_class++;
+ equiv_class_add (pointer_equiv_class_table,
+ label, graph->points_to[n]);
+ }
+ graph->pointer_label[n] = label;
+ }
+}
+
+/* Perform offline variable substitution, discovering equivalence
+ classes, and eliminating non-pointer variables. */
+
+static struct scc_info *
+perform_var_substitution (constraint_graph_t graph)
+{
+ unsigned int i;
+ unsigned int size = graph->size;
+ struct scc_info *si = init_scc_info (size);
+
+ bitmap_obstack_initialize (&iteration_obstack);
+ pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
+ equiv_class_label_eq, free);
+ location_equiv_class_table = htab_create (511, equiv_class_label_hash,
+ equiv_class_label_eq, free);
+ 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 = 0; i < LAST_REF_NODE; i++)
+ if (!TEST_BIT (si->visited, si->node_mapping[i]))
+ condense_visit (graph, si, si->node_mapping[i]);
+
+ sbitmap_zero (si->visited);
+ /* Actually the label the nodes for pointer equivalences */
+ for (i = 0; i < LAST_REF_NODE; i++)
+ if (!TEST_BIT (si->visited, si->node_mapping[i]))
+ label_visit (graph, si, si->node_mapping[i]);
+
+ /* Calculate location equivalence labels. */
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ bitmap pointed_by;
+ bitmap_iterator bi;
+ unsigned int j;
+ unsigned int label;
+
+ 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. */
+ label = equiv_class_lookup (location_equiv_class_table,
+ pointed_by);
+ if (label == 0)
+ {
+ label = location_equiv_class++;
+ equiv_class_add (location_equiv_class_table,
+ label, pointed_by);
+ }
+ 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] = label;
+
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ bool direct_node = TEST_BIT (graph->direct_nodes, i);
+ fprintf (dump_file,
+ "Equivalence classes for %s node id %d:%s are pointer: %d"
+ ", location:%d\n",
+ direct_node ? "Direct node" : "Indirect node", i,
+ get_varinfo (i)->name,
+ graph->pointer_label[si->node_mapping[i]],
+ graph->loc_label[si->node_mapping[i]]);
+ }
+
+ /* Quickly eliminate our non-pointer variables. */
+
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ unsigned int node = si->node_mapping[i];
+
+ if (graph->pointer_label[node] == 0
+ && TEST_BIT (graph->direct_nodes, node))
+ {
+ 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 (struct scc_info *si)
+{
+ free_scc_info (si);
+ free (graph->pointer_label);
+ free (graph->loc_label);
+ free (graph->pointed_by);
+ free (graph->points_to);
+ free (graph->number_incoming);
+ free (graph->eq_rep);
+ sbitmap_free (graph->direct_nodes);
+ sbitmap_free (graph->pt_used);
+ htab_delete (pointer_equiv_class_table);
+ htab_delete (location_equiv_class_table);
+ 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_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_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 = 0; i < graph->size; i++)
+ {
+ unsigned int label = graph->pe[i];
+ int label_rep = graph->pe_rep[label];
+
+ if (label != i && unite (label_rep, 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 (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ {
+ 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,
+ struct scc_info *si)
+{
+ int i;
+ unsigned int j;
+ constraint_t c;
+
+ for (j = 0; j < graph->size; j++)
+ gcc_assert (find (j) == j);
+
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ {
+ struct constraint_expr lhs = c->lhs;
+ struct constraint_expr rhs = c->rhs;
+ unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
+ unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
+ 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 (!TEST_BIT (graph->direct_nodes, lhsnode))
+ lhslabel = graph->pointer_label[lhsnode] = pointer_equiv_class++;
+ else
+ {
+ 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);
+ }
+ VEC_replace (constraint_t, constraints, i, NULL);
+ continue;
+ }
+ }
+
+ if (rhslabel == 0)
+ {
+ if (!TEST_BIT (graph->direct_nodes, rhsnode))
+ rhslabel = graph->pointer_label[rhsnode] = pointer_equiv_class++;
+ else
+ {
+ 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);
+ }
+ VEC_replace (constraint_t, 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;
+ VEC(unsigned,heap) *queue = NULL;
+ 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))
+ VEC_safe_push (unsigned, heap, queue, i);
+ }
+ }
+
+ for (queuepos = 0;
+ VEC_iterate (unsigned, queue, queuepos, i);
+ queuepos++)
+ {
+ unify_nodes (graph, to, i, true);
+ }
+ VEC_free (unsigned, heap, queue);
+ 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_count = 0;
+ changed = sbitmap_alloc (size);
+ sbitmap_zero (changed);
+
+ /* Mark all initial non-collapsed nodes as changed. */
+ for (i = 0; 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]))
+ || VEC_length (constraint_t, graph->complex[i]) > 0))
+ {
+ SET_BIT (changed, i);
+ changed_count++;
+ }
+ }
+
+ /* Allocate a bitmap to be used to store the changed bits. */
+ pts = BITMAP_ALLOC (&pta_obstack);
+
+ while (changed_count > 0)
+ {
+ unsigned int i;
+ struct topo_info *ti = init_topo_info ();
+ stats.iterations++;
+
+ bitmap_obstack_initialize (&iteration_obstack);
+
+ compute_topo_order (graph, ti);