int order_pos;
splay_tree nodes_marked_new;
bool reduce;
+ bool allow_overwritable;
int count;
};
for (edge = v->callees; edge; edge = edge->next_callee)
{
struct ipa_dfs_info * w_info;
- struct cgraph_node *w = edge->callee;
+ enum availability avail;
+ struct cgraph_node *w = cgraph_function_or_thunk_node (edge->callee, &avail);
- if (ignore_edge && ignore_edge (edge))
+ if (!w || (ignore_edge && ignore_edge (edge)))
continue;
- if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE)
+ if (w->aux
+ && (avail > AVAIL_OVERWRITABLE
+ || (env->allow_overwritable && avail == AVAIL_OVERWRITABLE)))
{
w_info = (struct ipa_dfs_info *) w->aux;
if (w_info->new_node)
x = env->stack[--(env->stack_size)];
x_info = (struct ipa_dfs_info *) x->aux;
x_info->on_stack = false;
+ x_info->scc_no = v_info->dfn_number;
if (env->reduce)
{
env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
env.count = 1;
env.reduce = reduce;
+ env.allow_overwritable = allow_overwritable;
for (node = cgraph_nodes; node; node = node->next)
{
}
}
+struct postorder_stack
+{
+ struct cgraph_node *node;
+ struct cgraph_edge *edge;
+ int ref;
+};
+
/* Fill array order with all nodes with output flag set in the reverse
- topological order. Return the number of elements in the array. */
+ topological order. Return the number of elements in the array.
+ FIXME: While walking, consider aliases, too. */
int
ipa_reverse_postorder (struct cgraph_node **order)
struct cgraph_node *node, *node2;
int stack_size = 0;
int order_pos = 0;
- struct cgraph_edge *edge, last;
+ struct cgraph_edge *edge;
int pass;
+ struct ipa_ref *ref;
- struct cgraph_node **stack =
- XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
+ struct postorder_stack *stack =
+ XCNEWVEC (struct postorder_stack, cgraph_n_nodes);
/* We have to deal with cycles nicely, so use a depth first traversal
output algorithm. Ignore the fact that some functions won't need
&& (pass
|| (!node->address_taken
&& !node->global.inlined_to
+ && !node->alias && !node->thunk.thunk_p
&& !cgraph_only_called_directly_p (node))))
{
- node2 = node;
- if (!node->callers)
- node->aux = &last;
- else
- node->aux = node->callers;
- while (node2)
+ stack_size = 0;
+ stack[stack_size].node = node;
+ stack[stack_size].edge = node->callers;
+ stack[stack_size].ref = 0;
+ node->aux = (void *)(size_t)1;
+ while (stack_size >= 0)
{
- while (node2->aux != &last)
+ while (true)
{
- edge = (struct cgraph_edge *) node2->aux;
- if (edge->next_caller)
- node2->aux = edge->next_caller;
- else
- node2->aux = &last;
- /* Break possible cycles involving always-inline
- functions by ignoring edges from always-inline
- functions to non-always-inline functions. */
- if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
- && !DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl))
- continue;
- if (!edge->caller->aux)
+ node2 = NULL;
+ while (stack[stack_size].edge && !node2)
{
- if (!edge->caller->callers)
- edge->caller->aux = &last;
- else
- edge->caller->aux = edge->caller->callers;
- stack[stack_size++] = node2;
+ edge = stack[stack_size].edge;
node2 = edge->caller;
- break;
+ stack[stack_size].edge = edge->next_caller;
+ /* Break possible cycles involving always-inline
+ functions by ignoring edges from always-inline
+ functions to non-always-inline functions. */
+ if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
+ && !DECL_DISREGARD_INLINE_LIMITS
+ (cgraph_function_node (edge->callee, NULL)->decl))
+ node2 = NULL;
+ }
+ for (;ipa_ref_list_refering_iterate (&stack[stack_size].node->ref_list,
+ stack[stack_size].ref,
+ ref) && !node2;
+ stack[stack_size].ref++)
+ {
+ if (ref->use == IPA_REF_ALIAS)
+ node2 = ipa_ref_refering_node (ref);
+ }
+ if (!node2)
+ break;
+ if (!node2->aux)
+ {
+ stack[++stack_size].node = node2;
+ stack[stack_size].edge = node2->callers;
+ stack[stack_size].ref = 0;
+ node2->aux = (void *)(size_t)1;
}
}
- if (node2->aux == &last)
- {
- order[order_pos++] = node2;
- if (stack_size)
- node2 = stack[--stack_size];
- else
- node2 = NULL;
- }
+ order[order_pos++] = stack[stack_size--].node;
}
}
free (stack);
return t;
}
+
+/* Create a new cgraph node set. */
+
+cgraph_node_set
+cgraph_node_set_new (void)
+{
+ cgraph_node_set new_node_set;
+
+ new_node_set = XCNEW (struct cgraph_node_set_def);
+ new_node_set->map = pointer_map_create ();
+ new_node_set->nodes = NULL;
+ return new_node_set;
+}
+
+
+/* Add cgraph_node NODE to cgraph_node_set SET. */
+
+void
+cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
+{
+ void **slot;
+
+ slot = pointer_map_insert (set->map, node);
+
+ if (*slot)
+ {
+ int index = (size_t) *slot - 1;
+ gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
+ == node));
+ return;
+ }
+
+ *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
+
+ /* Insert into node vector. */
+ VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);
+}
+
+
+/* Remove cgraph_node NODE from cgraph_node_set SET. */
+
+void
+cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
+{
+ void **slot, **last_slot;
+ int index;
+ struct cgraph_node *last_node;
+
+ slot = pointer_map_contains (set->map, node);
+ if (slot == NULL || !*slot)
+ return;
+
+ index = (size_t) *slot - 1;
+ gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index)
+ == node);
+
+ /* Remove from vector. We do this by swapping node with the last element
+ of the vector. */
+ last_node = VEC_pop (cgraph_node_ptr, set->nodes);
+ if (last_node != node)
+ {
+ last_slot = pointer_map_contains (set->map, last_node);
+ gcc_checking_assert (last_slot && *last_slot);
+ *last_slot = (void *)(size_t) (index + 1);
+
+ /* Move the last element to the original spot of NODE. */
+ VEC_replace (cgraph_node_ptr, set->nodes, index, last_node);
+ }
+
+ /* Remove element from hash table. */
+ *slot = NULL;
+}
+
+
+/* Find NODE in SET and return an iterator to it if found. A null iterator
+ is returned if NODE is not in SET. */
+
+cgraph_node_set_iterator
+cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
+{
+ void **slot;
+ cgraph_node_set_iterator csi;
+
+ slot = pointer_map_contains (set->map, node);
+ if (slot == NULL || !*slot)
+ csi.index = (unsigned) ~0;
+ else
+ csi.index = (size_t)*slot - 1;
+ csi.set = set;
+
+ return csi;
+}
+
+
+/* Dump content of SET to file F. */
+
+void
+dump_cgraph_node_set (FILE *f, cgraph_node_set set)
+{
+ cgraph_node_set_iterator iter;
+
+ for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
+ {
+ struct cgraph_node *node = csi_node (iter);
+ fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
+ }
+ fprintf (f, "\n");
+}
+
+
+/* Dump content of SET to stderr. */
+
+DEBUG_FUNCTION void
+debug_cgraph_node_set (cgraph_node_set set)
+{
+ dump_cgraph_node_set (stderr, set);
+}
+
+
+/* Free varpool node set. */
+
+void
+free_cgraph_node_set (cgraph_node_set set)
+{
+ VEC_free (cgraph_node_ptr, heap, set->nodes);
+ pointer_map_destroy (set->map);
+ free (set);
+}
+
+
+/* Create a new varpool node set. */
+
+varpool_node_set
+varpool_node_set_new (void)
+{
+ varpool_node_set new_node_set;
+
+ new_node_set = XCNEW (struct varpool_node_set_def);
+ new_node_set->map = pointer_map_create ();
+ new_node_set->nodes = NULL;
+ return new_node_set;
+}
+
+
+/* Add varpool_node NODE to varpool_node_set SET. */
+
+void
+varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
+{
+ void **slot;
+
+ slot = pointer_map_insert (set->map, node);
+
+ if (*slot)
+ {
+ int index = (size_t) *slot - 1;
+ gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index)
+ == node));
+ return;
+ }
+
+ *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1);
+
+ /* Insert into node vector. */
+ VEC_safe_push (varpool_node_ptr, heap, set->nodes, node);
+}
+
+
+/* Remove varpool_node NODE from varpool_node_set SET. */
+
+void
+varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
+{
+ void **slot, **last_slot;
+ int index;
+ struct varpool_node *last_node;
+
+ slot = pointer_map_contains (set->map, node);
+ if (slot == NULL || !*slot)
+ return;
+
+ index = (size_t) *slot - 1;
+ gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index)
+ == node);
+
+ /* Remove from vector. We do this by swapping node with the last element
+ of the vector. */
+ last_node = VEC_pop (varpool_node_ptr, set->nodes);
+ if (last_node != node)
+ {
+ last_slot = pointer_map_contains (set->map, last_node);
+ gcc_checking_assert (last_slot && *last_slot);
+ *last_slot = (void *)(size_t) (index + 1);
+
+ /* Move the last element to the original spot of NODE. */
+ VEC_replace (varpool_node_ptr, set->nodes, index, last_node);
+ }
+
+ /* Remove element from hash table. */
+ *slot = NULL;
+}
+
+
+/* Find NODE in SET and return an iterator to it if found. A null iterator
+ is returned if NODE is not in SET. */
+
+varpool_node_set_iterator
+varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
+{
+ void **slot;
+ varpool_node_set_iterator vsi;
+
+ slot = pointer_map_contains (set->map, node);
+ if (slot == NULL || !*slot)
+ vsi.index = (unsigned) ~0;
+ else
+ vsi.index = (size_t)*slot - 1;
+ vsi.set = set;
+
+ return vsi;
+}
+
+
+/* Dump content of SET to file F. */
+
+void
+dump_varpool_node_set (FILE *f, varpool_node_set set)
+{
+ varpool_node_set_iterator iter;
+
+ for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
+ {
+ struct varpool_node *node = vsi_node (iter);
+ fprintf (f, " %s", varpool_node_name (node));
+ }
+ fprintf (f, "\n");
+}
+
+
+/* Free varpool node set. */
+
+void
+free_varpool_node_set (varpool_node_set set)
+{
+ VEC_free (varpool_node_ptr, heap, set->nodes);
+ pointer_map_destroy (set->map);
+ free (set);
+}
+
+
+/* Dump content of SET to stderr. */
+
+DEBUG_FUNCTION void
+debug_varpool_node_set (varpool_node_set set)
+{
+ dump_varpool_node_set (stderr, set);
+}
OSDN Git Service
