From 04142cc3bdcc6277e8ba16d15851c7270cc351dc Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Thu, 10 May 2012 22:17:36 +0200 Subject: cgraph.h (cgraph_remove_unreachable_nodes): Rename to ... * cgraph.h (cgraph_remove_unreachable_nodes): Rename to ... (symtab_remove_unreachable_nodes): ... this one. * ipa-cp.c (ipcp_driver): Do not remove unreachable nodes. * cgraphunit.c (ipa_passes): Update. * cgraphclones.c (cgraph_materialize_all_clones): Update. * cgraph.c (cgraph_release_function_body): Only turn initial into error mark when initial was previously set. * ipa-inline.c (ipa_inline): Update. * ipa.c: Include ipa-inline.h (enqueue_cgraph_node, enqueue_varpool_node): Remove. (enqueue_node): New function. (process_references): Update. (symtab_remove_unreachable_nodes): Cleanup. * passes.c (execute_todo, execute_one_pass): Update. From-SVN: r187375 --- gcc/ipa.c | 353 +++++++++++++++++++++++++++++--------------------------------- 1 file changed, 166 insertions(+), 187 deletions(-) (limited to 'gcc/ipa.c') diff --git a/gcc/ipa.c b/gcc/ipa.c index 42e9061..766b26f 100644 --- a/gcc/ipa.c +++ b/gcc/ipa.c @@ -33,6 +33,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-iterator.h" #include "ipa-utils.h" #include "pointer-set.h" +#include "ipa-inline.h" /* Look for all functions inlined to NODE and update their inlined_to pointers to INLINED_TO. */ @@ -49,7 +50,7 @@ update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined } } -/* Add cgraph NODE to queue starting at FIRST. +/* Add symtab 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 @@ -58,8 +59,8 @@ update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined reachable. */ static void -enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first, - struct pointer_set_t *reachable) +enqueue_node (symtab_node node, symtab_node *first, + struct pointer_set_t *reachable) { /* Node is still in queue; do nothing. */ if (node->symbol.aux && node->symbol.aux != (void *) 2) @@ -72,21 +73,11 @@ enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **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->symbol.aux = *first; - *first = node; -} - /* Process references. */ static void process_references (struct ipa_ref_list *list, - struct cgraph_node **first, - struct varpool_node **first_varpool, + symtab_node *first, bool before_inlining_p, struct pointer_set_t *reachable) { @@ -97,18 +88,21 @@ process_references (struct ipa_ref_list *list, if (symtab_function_p (ref->referred)) { struct cgraph_node *node = ipa_ref_node (ref); + if (node->analyzed && (!DECL_EXTERNAL (node->symbol.decl) || node->alias || before_inlining_p)) pointer_set_insert (reachable, node); - enqueue_cgraph_node (node, first, reachable); + enqueue_node ((symtab_node) node, first, reachable); } else { struct varpool_node *node = ipa_ref_varpool_node (ref); - if (!pointer_set_insert (reachable, node)) - enqueue_varpool_node (node, first_varpool); + + if (node->analyzed) + pointer_set_insert (reachable, node); + enqueue_node ((symtab_node) node, first, reachable); } } } @@ -162,19 +156,63 @@ has_addr_references_p (struct cgraph_node *node, } /* 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 - removes unneeded bodies of extern inline functions. */ + + The algorithm is basically mark&sweep but with some extra refinements: + + - reachable extern inline functions needs special handling; the bodies needs + to stay in memory until inlining in hope that they will be inlined. + After inlining we release their bodies and turn them into unanalyzed + nodes even when they are reachable. + + BEFORE_INLINING_P specify whether we are before or after inlining. + + - virtual functions are kept in callgraph even if they seem unreachable in + hope calls to them will be devirtualized. + + Again we remove them after inlining. In late optimization some + devirtualization may happen, but it is not importnat since we won't inline + the call. In theory early opts and IPA should work out all important cases. + + - virtual clones needs bodies of their origins for later materialization; + this means that we want to keep the body even if the origin is unreachable + otherwise. To avoid origin from sitting in the callgraph and being + walked by IPA passes, we turn them into unanalyzed nodes with body + defined. + + We maintain set of function declaration where body needs to stay in + body_needed_for_clonning + + Inline clones represent special case: their declaration match the + declaration of origin and cgraph_remove_node already knows how to + reshape callgraph and preserve body when offline copy of function or + inline clone is being removed. + + We maintain queue of both reachable symbols (i.e. defined symbols that needs + to stay) and symbols that are in boundary (i.e. external symbols referenced + by reachable symbols or origins of clones). The queue is represented + as linked list by AUX pointer terminated by 1. + + A the end we keep all reachable symbols. For symbols in boundary we always + turn definition into a declaration, but we may keep function body around + based on body_needed_for_clonning + + All symbols that enter the queue have AUX pointer non-zero and are in the + boundary. Pointer set REACHABLE is used to track reachable symbols. + + Every symbol can be visited twice - once as part of boundary and once + as real reachable symbol. enqueue_node needs to decide whether the + node needs to be re-queued for second processing. For this purpose + we set AUX pointer of processed symbols in the boundary to constant 2. */ bool -cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) +symtab_remove_unreachable_nodes (bool before_inlining_p, FILE *file) { - struct cgraph_node *first = (struct cgraph_node *) (void *) 1; - struct varpool_node *first_varpool = (struct varpool_node *) (void *) 1; + symtab_node first = (symtab_node) (void *) 1; struct cgraph_node *node, *next; struct varpool_node *vnode, *vnext; bool changed = false; struct pointer_set_t *reachable = pointer_set_create (); + struct pointer_set_t *body_needed_for_clonning = pointer_set_create (); #ifdef ENABLE_CHECKING verify_symtab (); @@ -191,8 +229,8 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) This is mostly when they can be referenced externally. Inline clones are special since their declarations are shared with master clone and thus cgraph_can_remove_if_no_direct_calls_and_refs_p should not be called on them. */ - FOR_EACH_FUNCTION (node) - if (node->analyzed && !node->global.inlined_to + FOR_EACH_DEFINED_FUNCTION (node) + if (!node->global.inlined_to && (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node) /* Keep around virtual functions for possible devirtualization. */ || (before_inlining_p @@ -200,198 +238,126 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) && (DECL_COMDAT (node->symbol.decl) || DECL_EXTERNAL (node->symbol.decl))))) { gcc_assert (!node->global.inlined_to); - enqueue_cgraph_node (node, &first, reachable); pointer_set_insert (reachable, node); + enqueue_node ((symtab_node)node, &first, reachable); } else gcc_assert (!node->symbol.aux); /* Mark variables that are obviously needed. */ - FOR_EACH_VARIABLE (vnode) + FOR_EACH_DEFINED_VARIABLE (vnode) + if (!varpool_can_remove_if_no_refs (vnode)) + { + pointer_set_insert (reachable, vnode); + enqueue_node ((symtab_node)vnode, &first, reachable); + } + + /* Perform reachability analysis. */ + while (first != (symtab_node) (void *) 1) { - if ((vnode->analyzed || vnode->symbol.force_output) - && !varpool_can_remove_if_no_refs (vnode)) - { - pointer_set_insert (reachable, vnode); - enqueue_varpool_node (vnode, &first_varpool); - } - } + bool in_boundary_p = !pointer_set_contains (reachable, first); + symtab_node node = first; - /* 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. + first = (symtab_node)first->symbol.aux; - We maintain two worklist, one for cgraph nodes other for varpools and - are finished once both are empty. */ + /* If we are processing symbol in boundary, mark its AUX pointer for + possible later re-processing in enqueue_node. */ + if (in_boundary_p) + node->symbol.aux = (void *)2; + else + { + /* If any symbol in a comdat group is reachable, force + all other in the same comdat group to be also reachable. */ + if (node->symbol.same_comdat_group) + { + symtab_node next; + for (next = node->symbol.same_comdat_group; + next != node; + next = next->symbol.same_comdat_group) + if (!pointer_set_insert (reachable, next)) + enqueue_node ((symtab_node) next, &first, reachable); + } + /* Mark references as reachable. */ + process_references (&node->symbol.ref_list, &first, + before_inlining_p, reachable); + } - while (first != (struct cgraph_node *) (void *) 1 - || first_varpool != (struct varpool_node *) (void *) 1) - { - if (first != (struct cgraph_node *) (void *) 1) + if (symtab_function_p (node)) { - struct cgraph_edge *e; - node = first; - first = (struct cgraph_node *) first->symbol.aux; - if (!pointer_set_contains (reachable, node)) - node->symbol.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. */ - else + struct cgraph_node *cnode = cgraph (node); + + /* Mark the callees reachable unless they are direct calls to extern + inline functions we decided to not inline. */ + if (!in_boundary_p) { - for (e = node->callees; e; e = e->next_callee) + struct cgraph_edge *e; + for (e = cnode->callees; e; e = e->next_callee) { - if (node->analyzed + if (e->callee->analyzed && (!e->inline_failed || !DECL_EXTERNAL (e->callee->symbol.decl) - || node->alias + || cnode->alias || before_inlining_p)) pointer_set_insert (reachable, e->callee); - enqueue_cgraph_node (e->callee, &first, reachable); - } - process_references (&node->symbol.ref_list, &first, - &first_varpool, before_inlining_p, - reachable); - - /* If any function in a comdat group is reachable, force - all other functions in the same comdat group to be - also reachable. */ - if (node->symbol.same_comdat_group - && !node->global.inlined_to) - { - for (next = cgraph (node->symbol.same_comdat_group); - next != node; - next = cgraph (next->symbol.same_comdat_group)) - if (!pointer_set_insert (reachable, next)) - enqueue_cgraph_node (next, &first, reachable); + enqueue_node ((symtab_node) e->callee, &first, reachable); } + + /* When inline clone exists, mark body to be preserved so when removing + offline copy of the function we don't kill it. */ + if (!cnode->alias && cnode->global.inlined_to) + pointer_set_insert (body_needed_for_clonning, cnode->symbol.decl); } - /* 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->symbol.aux - && !gimple_has_body_p (node->symbol.decl)) + /* For non-inline clones, force their origins to the boundary and ensure + that body is not removed. */ + while (cnode->clone_of && !cnode->clone_of->symbol.aux + && !gimple_has_body_p (cnode->symbol.decl)) { - bool noninline = node->clone_of->symbol.decl != node->symbol.decl; - node = node->clone_of; - if (noninline && !pointer_set_contains (reachable, node) && !node->symbol.aux) + bool noninline = cnode->clone_of->symbol.decl != cnode->symbol.decl; + cnode = cnode->clone_of; + if (noninline && !cnode->symbol.aux) { - enqueue_cgraph_node (node, &first, reachable); + pointer_set_insert (body_needed_for_clonning, cnode->symbol.decl); + enqueue_node ((symtab_node)cnode, &first, reachable); break; } } } - if (first_varpool != (struct varpool_node *) (void *) 1) - { - vnode = first_varpool; - first_varpool = (struct varpool_node *)first_varpool->symbol.aux; - vnode->symbol.aux = NULL; - process_references (&vnode->symbol.ref_list, &first, - &first_varpool, before_inlining_p, - reachable); - /* If any function in a comdat group is reachable, force - all other functions in the same comdat group to be - also reachable. */ - if (vnode->symbol.same_comdat_group) - { - struct varpool_node *next; - for (next = varpool (vnode->symbol.same_comdat_group); - next != vnode; - next = varpool (next->symbol.same_comdat_group)) - if (!pointer_set_insert (reachable, next)) - enqueue_varpool_node (next, &first_varpool); - } - } } - /* 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. */ + /* Remove unreachable functions. */ for (node = cgraph_first_function (); node; node = next) { next = cgraph_next_function (node); - if (node->symbol.aux && !pointer_set_contains (reachable, node)) - { - cgraph_node_remove_callees (node); - ipa_remove_all_references (&node->symbol.ref_list); - node->analyzed = false; - } if (!node->symbol.aux) { - struct cgraph_edge *e; - bool found = false; - int i; - struct ipa_ref *ref; - - node->global.inlined_to = NULL; if (file) fprintf (file, " %s", cgraph_node_name (node)); - /* See if there is reachable caller. */ - for (e = node->callers; e && !found; e = e->next_caller) - if (pointer_set_contains (reachable, e->caller)) - found = true; - for (i = 0; (ipa_ref_list_referring_iterate (&node->symbol.ref_list, - i, ref) - && !found); i++) - if (pointer_set_contains (reachable, ref->referring)) - found = true; - - /* If so, we need to keep node in the callgraph. */ - if (found) - { - if (node->analyzed) - { - struct cgraph_node *clone; - - /* If there are still clones, we must keep body around. - Otherwise we can just remove the body but keep the clone. */ - for (clone = node->clones; clone; - clone = clone->next_sibling_clone) - if (clone->symbol.aux) - break; - if (!clone) - { - cgraph_release_function_body (node); - if (node->prev_sibling_clone) - node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone; - else if (node->clone_of) - node->clone_of->clones = node->next_sibling_clone; - if (node->next_sibling_clone) - node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone; - if (node->clone_of) - node->former_clone_of = node->clone_of->symbol.decl; - node->clone_of = NULL; - node->next_sibling_clone = NULL; - node->prev_sibling_clone = NULL; - } - else - gcc_assert (!clone->symbol.in_other_partition); - node->analyzed = false; - changed = true; - cgraph_node_remove_callees (node); - ipa_remove_all_references (&node->symbol.ref_list); - } - } - else + cgraph_remove_node (node); + changed = true; + } + else if (!pointer_set_contains (reachable, node)) + { + if (node->analyzed) { - cgraph_remove_node (node); + if (file) + fprintf (file, " %s", cgraph_node_name (node)); + cgraph_node_remove_callees (node); + ipa_remove_all_references (&node->symbol.ref_list); changed = true; } + if (!pointer_set_contains (body_needed_for_clonning, node->symbol.decl) + && !DECL_ARTIFICIAL (node->symbol.decl)) + cgraph_release_function_body (node); + node->analyzed = false; } } + + /* Inline clones might be kept around so their materializing allows further + cloning. If the function the clone is inlined into is removed, we need + to turn it into normal cone. */ FOR_EACH_FUNCTION (node) { - /* Inline clones might be kept around so their materializing allows further - cloning. If the function the clone is inlined into is removed, we need - to turn it into normal cone. */ if (node->global.inlined_to && !node->callers) { @@ -402,25 +368,38 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) node->symbol.aux = NULL; } + /* Remove unreachable variables. */ if (file) - fprintf (file, "\n"); - - if (file) - fprintf (file, "Reclaiming variables:"); + fprintf (file, "\nReclaiming variables:"); for (vnode = varpool_first_variable (); vnode; vnode = vnext) { vnext = varpool_next_variable (vnode); - if (!pointer_set_contains (reachable, vnode)) - { + if (!vnode->symbol.aux) + { if (file) fprintf (file, " %s", varpool_node_name (vnode)); varpool_remove_node (vnode); changed = true; } + else if (!pointer_set_contains (reachable, vnode)) + { + if (vnode->analyzed) + { + if (file) + fprintf (file, " %s", varpool_node_name (vnode)); + changed = true; + } + vnode->analyzed = false; + vnode->symbol.aux = NULL; + } + else + vnode->symbol.aux = NULL; } - /* Now update address_taken flags and try to promote functions to be local. */ + pointer_set_destroy (reachable); + pointer_set_destroy (body_needed_for_clonning); + /* Now update address_taken flags and try to promote functions to be local. */ if (file) fprintf (file, "\nClearing address taken flags:"); FOR_EACH_DEFINED_FUNCTION (node) @@ -444,18 +423,18 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) if (file) fprintf (file, "\n"); - /* Rest of transformations are undesirable at -O0. */ - if (!optimize) - return changed; - #ifdef ENABLE_CHECKING verify_symtab (); #endif + /* If we removed something, perhaps profile could be improved. */ + if (changed && optimize && inline_edge_summary_vec) + FOR_EACH_DEFINED_FUNCTION (node) + cgraph_propagate_frequency (node); + /* Reclaim alias pairs for functions that have disappeared from the call graph. */ remove_unreachable_alias_pairs (); - pointer_set_destroy (reachable); return changed; } -- cgit v1.1