X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fipa.c;h=fb3c74992f63c7174d8a3e4c436698596c6bb4d1;hb=eb3880ea6a8829d5f6e35107dae891eafadbf0a3;hp=16023be2dee237333bef2a3215be890503eefba6;hpb=20099e352f87c3265c44cd3341fd3aec25cb0fb4;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/ipa.c b/gcc/ipa.c index 16023be2dee..fb3c74992f6 100644 --- a/gcc/ipa.c +++ b/gcc/ipa.c @@ -1,5 +1,6 @@ /* Basic IPA optimizations and utilities. - Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, + Inc. This file is part of GCC. @@ -24,6 +25,8 @@ along with GCC; see the file COPYING3. If not see #include "cgraph.h" #include "tree-pass.h" #include "timevar.h" +#include "gimple.h" +#include "ggc.h" /* Fill array order with all nodes with output flag set in the reverse topological order. */ @@ -35,6 +38,7 @@ cgraph_postorder (struct cgraph_node **order) int stack_size = 0; int order_pos = 0; struct cgraph_edge *edge, last; + int pass; struct cgraph_node **stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); @@ -42,53 +46,70 @@ cgraph_postorder (struct cgraph_node **order) /* We have to deal with cycles nicely, so use a depth first traversal output algorithm. Ignore the fact that some functions won't need to be output and put them into order as well, so we get dependencies - right through intline functions. */ + right through inline functions. */ for (node = cgraph_nodes; node; node = node->next) node->aux = NULL; - for (node = cgraph_nodes; node; node = node->next) - if (!node->aux) - { - node2 = node; - if (!node->callers) - node->aux = &last; - else - node->aux = node->callers; - while (node2) - { - while (node2->aux != &last) - { - edge = (struct cgraph_edge *) node2->aux; - if (edge->next_caller) - node2->aux = edge->next_caller; - else - node2->aux = &last; - if (!edge->caller->aux) - { - if (!edge->caller->callers) - edge->caller->aux = &last; - else - edge->caller->aux = edge->caller->callers; - stack[stack_size++] = node2; - node2 = edge->caller; - break; - } - } - if (node2->aux == &last) - { - order[order_pos++] = node2; - if (stack_size) - node2 = stack[--stack_size]; - else - node2 = NULL; - } - } - } + for (pass = 0; pass < 2; pass++) + for (node = cgraph_nodes; node; node = node->next) + if (!node->aux + && (pass || (node->needed && !node->address_taken))) + { + node2 = node; + if (!node->callers) + node->aux = &last; + else + node->aux = node->callers; + while (node2) + { + while (node2->aux != &last) + { + edge = (struct cgraph_edge *) node2->aux; + if (edge->next_caller) + node2->aux = edge->next_caller; + else + node2->aux = &last; + if (!edge->caller->aux) + { + if (!edge->caller->callers) + edge->caller->aux = &last; + else + edge->caller->aux = edge->caller->callers; + stack[stack_size++] = node2; + node2 = edge->caller; + break; + } + } + if (node2->aux == &last) + { + order[order_pos++] = node2; + if (stack_size) + node2 = stack[--stack_size]; + else + node2 = NULL; + } + } + } free (stack); for (node = cgraph_nodes; node; node = node->next) node->aux = NULL; return order_pos; } +/* Look for all functions inlined to NODE and update their inlined_to pointers + to INLINED_TO. */ + +static void +update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to) +{ + struct cgraph_edge *e; + for (e = node->callees; e; e = e->next_callee) + if (e->callee->global.inlined_to) + { + e->callee->global.inlined_to = inlined_to; + update_inlined_to_pointer (e->callee, inlined_to); + } +} + /* 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 @@ -100,7 +121,6 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) struct cgraph_node *first = (struct cgraph_node *) (void *) 1; struct cgraph_node *node, *next; bool changed = false; - int insns = 0; #ifdef ENABLE_CHECKING verify_cgraph (); @@ -142,6 +162,12 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) e->callee->aux = first; first = e->callee; } + while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl)) + { + node = node->clone_of; + node->aux = first; + first = node; + } } /* Remove unreachable nodes. Extern inline functions need special care; @@ -157,14 +183,7 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) next = node->next; if (!node->aux) { - int local_insns; - tree decl = node->decl; - node->global.inlined_to = NULL; - if (DECL_STRUCT_FUNCTION (decl)) - local_insns = node->local.self_insns; - else - local_insns = 0; if (file) fprintf (file, " %s", cgraph_node_name (node)); if (!node->analyzed || !DECL_EXTERNAL (node->decl) @@ -174,38 +193,50 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) { struct cgraph_edge *e; + /* See if there is reachable caller. */ for (e = node->callers; e; e = e->next_caller) if (e->caller->aux) break; + + /* If so, we need to keep node in the callgraph. */ if (e || node->needed) { struct cgraph_node *clone; - for (clone = node->next_clone; clone; - clone = clone->next_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->aux) break; if (!clone) { cgraph_release_function_body (node); + cgraph_node_remove_callees (node); node->analyzed = false; + node->local.inlinable = false; } - cgraph_node_remove_callees (node); - node->analyzed = false; - node->local.inlinable = false; } else cgraph_remove_node (node); } - if (!DECL_SAVED_TREE (decl)) - insns += local_insns; changed = true; } } for (node = cgraph_nodes; node; node = node->next) - node->aux = NULL; - if (file) - fprintf (file, "\nReclaimed %i insns", insns); + { + /* 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) + { + gcc_assert (node->clones); + node->global.inlined_to = NULL; + update_inlined_to_pointer (node, node); + } + node->aux = NULL; + } #ifdef ENABLE_CHECKING verify_cgraph (); #endif @@ -296,3 +327,162 @@ struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility = TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */ } }; + + +/* Hash a cgraph node set element. */ + +static hashval_t +hash_cgraph_node_set_element (const void *p) +{ + const_cgraph_node_set_element element = (const_cgraph_node_set_element) p; + return htab_hash_pointer (element->node); +} + +/* Compare two cgraph node set elements. */ + +static int +eq_cgraph_node_set_element (const void *p1, const void *p2) +{ + const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1; + const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2; + + return e1->node == e2->node; +} + +/* Create a new cgraph node set. */ + +cgraph_node_set +cgraph_node_set_new (void) +{ + cgraph_node_set new_node_set; + + new_node_set = GGC_NEW (struct cgraph_node_set_def); + new_node_set->hashtab = htab_create_ggc (10, + hash_cgraph_node_set_element, + eq_cgraph_node_set_element, + NULL); + 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; + cgraph_node_set_element element; + struct cgraph_node_set_element_def dummy; + + dummy.node = node; + slot = htab_find_slot (set->hashtab, &dummy, INSERT); + + if (*slot != HTAB_EMPTY_ENTRY) + { + element = (cgraph_node_set_element) *slot; + gcc_assert (node == element->node + && (VEC_index (cgraph_node_ptr, set->nodes, element->index) + == node)); + return; + } + + /* Insert node into hash table. */ + element = + (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def); + element->node = node; + element->index = VEC_length (cgraph_node_ptr, set->nodes); + *slot = element; + + /* Insert into node vector. */ + VEC_safe_push (cgraph_node_ptr, gc, 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; + cgraph_node_set_element element, last_element; + struct cgraph_node *last_node; + struct cgraph_node_set_element_def dummy; + + dummy.node = node; + slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT); + if (slot == NULL) + return; + + element = (cgraph_node_set_element) *slot; + gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->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) + { + dummy.node = last_node; + last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT); + last_element = (cgraph_node_set_element) *last_slot; + gcc_assert (last_element); + + /* Move the last element to the original spot of NODE. */ + last_element->index = element->index; + VEC_replace (cgraph_node_ptr, set->nodes, last_element->index, + last_node); + } + + /* Remove element from hash table. */ + htab_clear_slot (set->hashtab, slot); + ggc_free (element); +} + +/* 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; + struct cgraph_node_set_element_def dummy; + cgraph_node_set_element element; + cgraph_node_set_iterator csi; + + dummy.node = node; + slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT); + if (slot == NULL) + csi.index = (unsigned) ~0; + else + { + element = (cgraph_node_set_element) *slot; + gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index) + == node); + csi.index = element->index; + } + 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); + dump_cgraph_node (f, node); + } +} + +/* Dump content of SET to stderr. */ + +void +debug_cgraph_node_set (cgraph_node_set set) +{ + dump_cgraph_node_set (stderr, set); +} +