#include "timevar.h"
#include "gimple.h"
#include "ggc.h"
+#include "flags.h"
+#include "pointer-set.h"
/* Fill array order with all nodes with output flag set in the reverse
topological order. */
}
}
+/* Add cgraph NODE to queue starting at FIRST.
+
+ The queue is linked via AUX pointers and terminated by pointer to 1.
+ We enqueue nodes at two occasions: when we find them reachable or when we find
+ their bodies needed for further clonning. In the second case we mark them
+ by pointer to 2 after processing so they are re-queue when they become
+ reachable. */
+
+static void
+enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first)
+{
+ /* Node is still in queue; do nothing. */
+ if (node->aux && node->aux != (void *) 2)
+ return;
+ /* Node was already processed as unreachable, re-enqueue
+ only if it became reachable now. */
+ if (node->aux == (void *)2 && !node->reachable)
+ return;
+ node->aux = *first;
+ *first = node;
+}
+
+/* Add varpool NODE to queue starting at FIRST. */
+
+static void
+enqueue_varpool_node (struct varpool_node *node, struct varpool_node **first)
+{
+ node->aux = *first;
+ *first = node;
+}
+
+/* Process references. */
+
+static void
+process_references (struct ipa_ref_list *list,
+ struct cgraph_node **first,
+ struct varpool_node **first_varpool,
+ bool before_inlining_p)
+{
+ int i;
+ struct ipa_ref *ref;
+ for (i = 0; ipa_ref_list_reference_iterate (list, i, ref); i++)
+ {
+ if (ref->refered_type == IPA_REF_CGRAPH)
+ {
+ struct cgraph_node *node = ipa_ref_node (ref);
+ if (!node->reachable
+ && (!DECL_EXTERNAL (node->decl)
+ || before_inlining_p))
+ {
+ node->reachable = true;
+ enqueue_cgraph_node (node, first);
+ }
+ }
+ else
+ {
+ struct varpool_node *node = ipa_ref_varpool_node (ref);
+ if (!node->needed)
+ {
+ varpool_mark_needed_node (node);
+ enqueue_varpool_node (node, first_varpool);
+ }
+ }
+ }
+}
+
+/* Return true when function NODE can be removed from callgraph
+ if all direct calls are eliminated. */
+
+static inline bool
+varpool_can_remove_if_no_refs (struct varpool_node *node)
+{
+ return (!node->force_output && !node->used_from_other_partition
+ && (DECL_COMDAT (node->decl) || !node->externally_visible));
+}
+
+/* Return true when function can be marked local. */
+
+static bool
+cgraph_local_node_p (struct cgraph_node *node)
+{
+ return (cgraph_only_called_directly_p (node)
+ && node->analyzed
+ && !DECL_EXTERNAL (node->decl)
+ && !node->local.externally_visible
+ && !node->reachable_from_other_partition
+ && !node->in_other_partition);
+}
+
/* Perform reachability analysis and reclaim all unreachable nodes.
If BEFORE_INLINING_P is true this function is called before inlining
decisions has been made. If BEFORE_INLINING_P is false this function also
cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
{
struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
- struct cgraph_node *processed = (struct cgraph_node *) (void *) 2;
+ struct varpool_node *first_varpool = (struct varpool_node *) (void *) 1;
struct cgraph_node *node, *next;
+ struct varpool_node *vnode, *vnext;
bool changed = false;
#ifdef ENABLE_CHECKING
#ifdef ENABLE_CHECKING
for (node = cgraph_nodes; node; node = node->next)
gcc_assert (!node->aux);
+ for (vnode = varpool_nodes; vnode; vnode = vnode->next)
+ gcc_assert (!vnode->aux);
#endif
+ varpool_reset_queue ();
for (node = cgraph_nodes; node; node = node->next)
- if (!cgraph_can_remove_if_no_direct_calls_p (node)
+ if (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node)
&& ((!DECL_EXTERNAL (node->decl))
- || !node->analyzed
|| before_inlining_p))
{
gcc_assert (!node->global.inlined_to);
- node->aux = first;
- first = node;
+ enqueue_cgraph_node (node, &first);
node->reachable = true;
}
else
gcc_assert (!node->aux);
node->reachable = false;
}
+ for (vnode = varpool_nodes; vnode; vnode = vnode->next)
+ {
+ vnode->next_needed = NULL;
+ vnode->prev_needed = NULL;
+ if (!varpool_can_remove_if_no_refs (vnode))
+ {
+ vnode->needed = false;
+ varpool_mark_needed_node (vnode);
+ enqueue_varpool_node (vnode, &first_varpool);
+ }
+ else
+ vnode->needed = false;
+ }
/* Perform reachability analysis. As a special case do not consider
extern inline functions not inlined as live because we won't output
- them at all. */
- while (first != (void *) 1)
+ them at all.
+
+ We maintain two worklist, one for cgraph nodes other for varpools and
+ are finished once both are empty. */
+
+ while (first != (struct cgraph_node *) (void *) 1
+ || first_varpool != (struct varpool_node *) (void *) 1)
{
- struct cgraph_edge *e;
- node = first;
- first = (struct cgraph_node *) first->aux;
- node->aux = processed;
-
- if (node->reachable)
- for (e = node->callees; e; e = e->next_callee)
- if (!e->callee->reachable
- && node->analyzed
- && (!e->inline_failed || !e->callee->analyzed
- || (!DECL_EXTERNAL (e->callee->decl))
- || before_inlining_p))
+ if (first != (struct cgraph_node *) (void *) 1)
+ {
+ struct cgraph_edge *e;
+ node = first;
+ first = (struct cgraph_node *) first->aux;
+ if (!node->reachable)
+ node->aux = (void *)2;
+
+ /* If we found this node reachable, first mark on the callees
+ reachable too, unless they are direct calls to extern inline functions
+ we decided to not inline. */
+ if (node->reachable)
{
- bool prev_reachable = e->callee->reachable;
- e->callee->reachable |= node->reachable;
- if (!e->callee->aux
- || (e->callee->aux == processed
- && prev_reachable != e->callee->reachable))
- {
- e->callee->aux = first;
- first = e->callee;
- }
+ for (e = node->callees; e; e = e->next_callee)
+ if (!e->callee->reachable
+ && node->analyzed
+ && (!e->inline_failed || !e->callee->analyzed
+ || (!DECL_EXTERNAL (e->callee->decl))
+ || before_inlining_p))
+ {
+ e->callee->reachable = true;
+ enqueue_cgraph_node (e->callee, &first);
+ }
+ process_references (&node->ref_list, &first, &first_varpool, before_inlining_p);
}
- /* If any function in a comdat group is reachable, force
- all other functions in the same comdat group to be
- also reachable. */
- if (node->same_comdat_group
- && node->reachable
- && !node->global.inlined_to)
- {
- for (next = node->same_comdat_group;
- next != node;
- next = next->same_comdat_group)
- if (!next->reachable)
- {
- next->aux = first;
- first = next;
- next->reachable = true;
- }
- }
+ /* If any function in a comdat group is reachable, force
+ all other functions in the same comdat group to be
+ also reachable. */
+ if (node->same_comdat_group
+ && node->reachable
+ && !node->global.inlined_to)
+ {
+ for (next = node->same_comdat_group;
+ next != node;
+ next = next->same_comdat_group)
+ if (!next->reachable)
+ {
+ next->reachable = true;
+ enqueue_cgraph_node (next, &first);
+ }
+ }
- /* We can freely remove inline clones even if they are cloned, however if
- function is clone of real clone, we must keep it around in order to
- make materialize_clones produce function body with the changes
- applied. */
- while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
- {
- bool noninline = node->clone_of->decl != node->decl;
- node = node->clone_of;
- if (noninline)
+ /* We can freely remove inline clones even if they are cloned, however if
+ function is clone of real clone, we must keep it around in order to
+ make materialize_clones produce function body with the changes
+ applied. */
+ while (node->clone_of && !node->clone_of->aux
+ && !gimple_has_body_p (node->decl))
{
- node->aux = first;
- first = node;
- break;
+ bool noninline = node->clone_of->decl != node->decl;
+ node = node->clone_of;
+ if (noninline && !node->reachable && !node->aux)
+ {
+ enqueue_cgraph_node (node, &first);
+ break;
+ }
+ }
+ }
+ if (first_varpool != (struct varpool_node *) (void *) 1)
+ {
+ vnode = first_varpool;
+ first_varpool = (struct varpool_node *)first_varpool->aux;
+ vnode->aux = NULL;
+ process_references (&vnode->ref_list, &first, &first_varpool, before_inlining_p);
+ /* If any function in a comdat group is reachable, force
+ all other functions in the same comdat group to be
+ also reachable. */
+ if (vnode->same_comdat_group)
+ {
+ struct varpool_node *next;
+ for (next = vnode->same_comdat_group;
+ next != vnode;
+ next = next->same_comdat_group)
+ if (!next->needed)
+ {
+ varpool_mark_needed_node (next);
+ enqueue_varpool_node (next, &first_varpool);
+ }
}
}
}
- /* Remove unreachable nodes. Extern inline functions need special care;
- Unreachable extern inline functions shall be removed.
- Reachable extern inline functions we never inlined shall get their bodies
- eliminated.
- Reachable extern inline functions we sometimes inlined will be turned into
- unanalyzed nodes so they look like for true extern functions to the rest
- of code. Body of such functions is released via remove_node once the
- inline clones are eliminated. */
+ /* Remove unreachable nodes.
+
+ Completely unreachable functions can be fully removed from the callgraph.
+ Extern inline functions that we decided to not inline need to become unanalyzed nodes of
+ callgraph (so we still have edges to them). We remove function body then.
+
+ Also we need to care functions that are unreachable but we need to keep them around
+ for later clonning. In this case we also turn them to unanalyzed nodes, but
+ keep the body around. */
for (node = cgraph_nodes; node; node = next)
{
next = node->next;
if (node->aux && !node->reachable)
{
cgraph_node_remove_callees (node);
+ ipa_remove_all_references (&node->ref_list);
node->analyzed = false;
node->local.inlinable = false;
}
/* See if there is reachable caller. */
for (e = node->callers; e; e = e->next_caller)
- if (e->caller->aux)
+ if (e->caller->reachable)
break;
/* If so, we need to keep node in the callgraph. */
else
gcc_assert (!clone->in_other_partition);
cgraph_node_remove_callees (node);
+ ipa_remove_all_references (&node->ref_list);
if (node->prev_sibling_clone)
node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
else if (node->clone_of)
}
node->aux = NULL;
}
+
+ if (file)
+ fprintf (file, "\n");
+
+ /* We must release unused extern inlines or sanity checking will fail. Rest of transformations
+ are undesirable at -O0 since we do not want to remove anything. */
+ if (!optimize)
+ return changed;
+
+ if (file)
+ fprintf (file, "Reclaiming variables:");
+ for (vnode = varpool_nodes; vnode; vnode = vnext)
+ {
+ vnext = vnode->next;
+ if (!vnode->needed)
+ {
+ if (file)
+ fprintf (file, " %s", varpool_node_name (vnode));
+ varpool_remove_node (vnode);
+ changed = true;
+ }
+ }
+
+ /* Now update address_taken flags and try to promote functions to be local. */
+
+ if (file)
+ fprintf (file, "\nClearing address taken flags:");
+ for (node = cgraph_nodes; node; node = node->next)
+ if (node->address_taken
+ && !node->reachable_from_other_partition)
+ {
+ int i;
+ struct ipa_ref *ref;
+ bool found = false;
+ for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref)
+ && !found; i++)
+ {
+ gcc_assert (ref->use == IPA_REF_ADDR);
+ found = true;
+ }
+ if (!found)
+ {
+ if (file)
+ fprintf (file, " %s", cgraph_node_name (node));
+ node->address_taken = false;
+ changed = true;
+ if (cgraph_local_node_p (node))
+ {
+ node->local.local = true;
+ if (file)
+ fprintf (file, " (local)");
+ }
+ }
+ }
+
#ifdef ENABLE_CHECKING
verify_cgraph ();
#endif
return changed;
}
+/* Discover variables that have no longer address taken or that are read only
+ and update their flags.
+
+ FIXME: This can not be done in between gimplify and omp_expand since
+ readonly flag plays role on what is shared and what is not. Currently we do
+ this transformation as part of whole program visibility and re-do at
+ ipa-reference pass (to take into account clonning), but it would
+ make sense to do it before early optimizations. */
+
+void
+ipa_discover_readonly_nonaddressable_vars (void)
+{
+ struct varpool_node *vnode;
+ if (dump_file)
+ fprintf (dump_file, "Clearing variable flags:");
+ for (vnode = varpool_nodes; vnode; vnode = vnode->next)
+ if (vnode->finalized && varpool_all_refs_explicit_p (vnode)
+ && (TREE_ADDRESSABLE (vnode->decl) || !TREE_READONLY (vnode->decl)))
+ {
+ bool written = false;
+ bool address_taken = false;
+ int i;
+ struct ipa_ref *ref;
+ for (i = 0; ipa_ref_list_refering_iterate (&vnode->ref_list, i, ref)
+ && (!written || !address_taken); i++)
+ switch (ref->use)
+ {
+ case IPA_REF_ADDR:
+ address_taken = true;
+ break;
+ case IPA_REF_LOAD:
+ break;
+ case IPA_REF_STORE:
+ written = true;
+ break;
+ }
+ if (TREE_ADDRESSABLE (vnode->decl) && !address_taken)
+ {
+ if (dump_file)
+ fprintf (dump_file, " %s (addressable)", varpool_node_name (vnode));
+ TREE_ADDRESSABLE (vnode->decl) = 0;
+ }
+ if (!TREE_READONLY (vnode->decl) && !address_taken && !written
+ /* Making variable in explicit section readonly can cause section
+ type conflict.
+ See e.g. gcc.c-torture/compile/pr23237.c */
+ && DECL_SECTION_NAME (vnode->decl) == NULL)
+ {
+ if (dump_file)
+ fprintf (dump_file, " %s (read-only)", varpool_node_name (vnode));
+ TREE_READONLY (vnode->decl) = 1;
+ }
+ }
+ if (dump_file)
+ fprintf (dump_file, "\n");
+}
+
+/* Return true when function NODE should be considered externally visible. */
+
static bool
-cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
+cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program, bool aliased)
{
if (!node->local.finalized)
return false;
if (!DECL_COMDAT (node->decl)
&& (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
return false;
- if (!whole_program)
+
+ /* Do not even try to be smart about aliased nodes. Until we properly
+ represent everything by same body alias, these are just evil. */
+ if (aliased)
return true;
- if (DECL_PRESERVE_P (node->decl))
+
+ /* When doing link time optimizations, hidden symbols become local. */
+ if (in_lto_p && DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
+ /* Be sure that node is defined in IR file, not in other object
+ file. In that case we don't set used_from_other_object_file. */
+ && node->analyzed)
+ ;
+ else if (!whole_program)
return true;
/* COMDAT functions must be shared only if they have address taken,
otherwise we can produce our own private implementation with
-fwhole-program. */
- if (DECL_COMDAT (node->decl))
+ else if (DECL_COMDAT (node->decl))
{
if (node->address_taken || !node->analyzed)
return true;
return true;
}
}
+ if (node->local.used_from_object_file)
+ return true;
+ if (DECL_PRESERVE_P (node->decl))
+ return true;
if (MAIN_NAME_P (DECL_NAME (node->decl)))
return true;
if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
{
struct cgraph_node *node;
struct varpool_node *vnode;
+ struct pointer_set_t *aliased_nodes = pointer_set_create ();
+ struct pointer_set_t *aliased_vnodes = pointer_set_create ();
+ unsigned i;
+ alias_pair *p;
+
+ /* Discover aliased nodes. */
+ FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Alias %s->%s",
+ IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (p->decl)),
+ IDENTIFIER_POINTER (p->target));
+
+ if ((node = cgraph_node_for_asm (p->target)) != NULL)
+ {
+ gcc_assert (node->needed);
+ pointer_set_insert (aliased_nodes, node);
+ if (dump_file)
+ fprintf (dump_file, " node %s/%i",
+ cgraph_node_name (node), node->uid);
+ }
+ else if ((vnode = varpool_node_for_asm (p->target)) != NULL)
+ {
+ gcc_assert (vnode->needed);
+ pointer_set_insert (aliased_vnodes, vnode);
+ if (dump_file)
+ fprintf (dump_file, " varpool node %s",
+ varpool_node_name (vnode));
+ }
+ if (dump_file)
+ fprintf (dump_file, "\n");
+ }
for (node = cgraph_nodes; node; node = node->next)
{
}
gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
|| TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
- if (cgraph_externally_visible_p (node, whole_program))
+ if (cgraph_externally_visible_p (node, whole_program,
+ pointer_set_contains (aliased_nodes,
+ node)))
{
gcc_assert (!node->global.inlined_to);
node->local.externally_visible = true;
if (!node->local.externally_visible && node->analyzed
&& !DECL_EXTERNAL (node->decl))
{
- gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
+ struct cgraph_node *alias;
+ gcc_assert (whole_program || in_lto_p || !TREE_PUBLIC (node->decl));
cgraph_make_decl_local (node->decl);
+ for (alias = node->same_body; alias; alias = alias->next)
+ cgraph_make_decl_local (alias->decl);
if (node->same_comdat_group)
/* cgraph_externally_visible_p has already checked all other nodes
in the group and they will all be made local. We need to
segfault though. */
dissolve_same_comdat_group_list (node);
}
- node->local.local = (cgraph_only_called_directly_p (node)
- && node->analyzed
- && !DECL_EXTERNAL (node->decl)
- && !node->local.externally_visible);
+ node->local.local = cgraph_local_node_p (node);
}
for (vnode = varpool_nodes; vnode; vnode = vnode->next)
{
continue;
if (vnode->needed
&& (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
- && (!whole_program
- /* We can privatize comdat readonly variables whose address is not taken,
- but doing so is not going to bring us optimization oppurtunities until
- we start reordering datastructures. */
- || DECL_COMDAT (vnode->decl)
- || DECL_WEAK (vnode->decl)
+ && (((!whole_program
+ /* We can privatize comdat readonly variables whose address is
+ not taken, but doing so is not going to bring us
+ optimization oppurtunities until we start reordering
+ datastructures. */
+ || DECL_COMDAT (vnode->decl)
+ || DECL_WEAK (vnode->decl))
+ /* When doing linktime optimizations, all hidden symbols will
+ become local. */
+ && (!in_lto_p
+ || DECL_VISIBILITY (vnode->decl) != VISIBILITY_HIDDEN
+ /* We can get prevailing decision in other object file.
+ In this case we do not sed used_from_object_file. */
+ || !vnode->finalized))
+ || DECL_PRESERVE_P (vnode->decl)
+ || vnode->used_from_object_file
+ || pointer_set_contains (aliased_vnodes, vnode)
|| lookup_attribute ("externally_visible",
DECL_ATTRIBUTES (vnode->decl))))
vnode->externally_visible = true;
vnode->externally_visible = false;
if (!vnode->externally_visible)
{
- gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
+ gcc_assert (in_lto_p || whole_program || !TREE_PUBLIC (vnode->decl));
cgraph_make_decl_local (vnode->decl);
}
gcc_assert (TREE_STATIC (vnode->decl));
}
+ pointer_set_destroy (aliased_nodes);
+ pointer_set_destroy (aliased_vnodes);
if (dump_file)
{
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
+ TODO_remove_functions | TODO_dump_cgraph
+ | TODO_ggc_collect /* todo_flags_finish */
}
};
fprintf (dump_file, " %s", varpool_node_name (vnode));
fprintf (dump_file, "\n\n");
}
+ if (optimize)
+ ipa_discover_readonly_nonaddressable_vars ();
return 0;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
+ TODO_remove_functions | TODO_dump_cgraph
+ | TODO_ggc_collect /* todo_flags_finish */
},
NULL, /* generate_summary */
NULL, /* write_summary */
{
cgraph_node_set new_node_set;
- new_node_set = GGC_NEW (struct cgraph_node_set_def);
+ new_node_set = ggc_alloc_cgraph_node_set_def ();
new_node_set->hashtab = htab_create_ggc (10,
hash_cgraph_node_set_element,
eq_cgraph_node_set_element,
}
/* Insert node into hash table. */
- element =
- (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
+ element = ggc_alloc_cgraph_node_set_element_def ();
element->node = node;
element->index = VEC_length (cgraph_node_ptr, set->nodes);
*slot = element;
for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
{
struct cgraph_node *node = csi_node (iter);
- dump_cgraph_node (f, node);
+ fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
}
+ fprintf (f, "\n");
}
/* Dump content of SET to stderr. */
-void
+DEBUG_FUNCTION void
debug_cgraph_node_set (cgraph_node_set set)
{
dump_cgraph_node_set (stderr, set);
{
varpool_node_set new_node_set;
- new_node_set = GGC_NEW (struct varpool_node_set_def);
+ new_node_set = ggc_alloc_varpool_node_set_def ();
new_node_set->hashtab = htab_create_ggc (10,
hash_varpool_node_set_element,
eq_varpool_node_set_element,
}
/* Insert node into hash table. */
- element =
- (varpool_node_set_element) GGC_NEW (struct varpool_node_set_element_def);
+ element = ggc_alloc_varpool_node_set_element_def ();
element->node = node;
element->index = VEC_length (varpool_node_ptr, set->nodes);
*slot = element;
for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
{
struct varpool_node *node = vsi_node (iter);
- dump_varpool_node (f, node);
+ fprintf (f, " %s", varpool_node_name (node));
}
+ fprintf (f, "\n");
}
/* Dump content of SET to stderr. */
-void
+DEBUG_FUNCTION void
debug_varpool_node_set (varpool_node_set set)
{
dump_varpool_node_set (stderr, set);
OSDN Git Service
