X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcgraph.c;h=32fbe3097391878eb90dd88f9a0c5e3dff92914d;hb=b78b6a05dc7a9bcf4c6c93f994f4c5f70b968172;hp=dacc70dfb30b026744972006a8ccca7f2e7111c8;hpb=5830087fdfb01e798d030e458afddbdec3c55550;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cgraph.c b/gcc/cgraph.c index dacc70dfb30..32fbe309739 100644 --- a/gcc/cgraph.c +++ b/gcc/cgraph.c @@ -16,8 +16,8 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ /* This file contains basic routines manipulating call graph and variable pool @@ -84,6 +84,7 @@ The varpool data structure: #include "coretypes.h" #include "tm.h" #include "tree.h" +#include "tree-inline.h" #include "langhooks.h" #include "hashtab.h" #include "toplev.h" @@ -91,10 +92,13 @@ The varpool data structure: #include "ggc.h" #include "debug.h" #include "target.h" +#include "basic-block.h" #include "cgraph.h" #include "varray.h" #include "output.h" #include "intl.h" +#include "tree-gimple.h" +#include "tree-dump.h" static void cgraph_node_remove_callers (struct cgraph_node *node); static inline void cgraph_edge_remove_caller (struct cgraph_edge *e); @@ -118,14 +122,21 @@ int cgraph_max_uid; /* Set when whole unit has been analyzed so we can access global info. */ bool cgraph_global_info_ready = false; +/* Set when the cgraph is fully build and the basic flags are computed. */ +bool cgraph_function_flags_ready = false; + /* Hash table used to convert declarations into nodes. */ static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash; /* Queue of cgraph nodes scheduled to be lowered and output. */ -struct cgraph_varpool_node *cgraph_varpool_nodes_queue; +struct cgraph_varpool_node *cgraph_varpool_nodes_queue, *cgraph_varpool_first_unanalyzed_node; + /* The linked list of cgraph varpool nodes. */ -static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes; +static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes; + +/* End of the varpool queue. Needs to be QTYed to work with PCH. */ +static GTY(()) struct cgraph_varpool_node *cgraph_varpool_last_needed_node; static hashval_t hash_node (const void *); static int eq_node (const void *, const void *); @@ -160,6 +171,7 @@ cgraph_create_node (void) if (cgraph_nodes) cgraph_nodes->previous = node; node->previous = NULL; + node->global.estimated_growth = INT_MIN; cgraph_nodes = node; cgraph_n_nodes++; return node; @@ -181,7 +193,12 @@ cgraph_node (tree decl) slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT); if (*slot) - return *slot; + { + node = *slot; + if (!node->master_clone) + node->master_clone = node; + return node; + } node = cgraph_create_node (); node->decl = decl; @@ -191,6 +208,7 @@ cgraph_node (tree decl) node->origin = cgraph_node (DECL_CONTEXT (decl)); node->next_nested = node->origin->nested; node->origin->nested = node; + node->master_clone = node; } return node; } @@ -245,9 +263,9 @@ cgraph_node_for_asm (tree asmname) return NULL; } -/* Return callgraph edge representing CALL_EXPR. */ +/* Return callgraph edge representing CALL_EXPR statement. */ struct cgraph_edge * -cgraph_edge (struct cgraph_node *node, tree call_expr) +cgraph_edge (struct cgraph_node *node, tree call_stmt) { struct cgraph_edge *e; @@ -257,7 +275,7 @@ cgraph_edge (struct cgraph_node *node, tree call_expr) because we want to make possible having multiple cgraph nodes representing different clones of the same body before the body is actually cloned. */ for (e = node->callees; e; e= e->next_callee) - if (e->call_expr == call_expr) + if (e->call_stmt == call_stmt) break; return e; } @@ -266,17 +284,17 @@ cgraph_edge (struct cgraph_node *node, tree call_expr) struct cgraph_edge * cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee, - tree call_expr) + tree call_stmt, gcov_type count, int nest) { struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge)); #ifdef ENABLE_CHECKING struct cgraph_edge *e; for (e = caller->callees; e; e = e->next_callee) - gcc_assert (e->call_expr != call_expr); + gcc_assert (e->call_stmt != call_stmt); #endif - gcc_assert (TREE_CODE (call_expr) == CALL_EXPR); + gcc_assert (get_call_expr_in (call_stmt)); if (!DECL_SAVED_TREE (callee->decl)) edge->inline_failed = N_("function body not available"); @@ -292,7 +310,7 @@ cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee, edge->caller = caller; edge->callee = callee; - edge->call_expr = call_expr; + edge->call_stmt = call_stmt; edge->prev_caller = NULL; edge->next_caller = callee->callers; if (callee->callers) @@ -303,6 +321,8 @@ cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee, caller->callees->prev_callee = edge; caller->callees = edge; callee->callers = edge; + edge->count = count; + edge->loop_nest = nest; return edge; } @@ -422,7 +442,17 @@ cgraph_remove_node (struct cgraph_node *node) if (*slot == node) { if (node->next_clone) - *slot = node->next_clone; + { + struct cgraph_node *new_node = node->next_clone; + struct cgraph_node *n; + + /* Make the next clone be the master clone */ + for (n = new_node; n; n = n->next_clone) + n->master_clone = new_node; + + *slot = new_node; + node->next_clone->prev_clone = NULL; + } else { htab_clear_slot (cgraph_hash, slot); @@ -431,11 +461,9 @@ cgraph_remove_node (struct cgraph_node *node) } else { - struct cgraph_node *n; - - for (n = *slot; n->next_clone != node; n = n->next_clone) - continue; - n->next_clone = node->next_clone; + node->prev_clone->next_clone = node->next_clone; + if (node->next_clone) + node->next_clone->prev_clone = node->prev_clone; } /* While all the clones are removed after being proceeded, the function @@ -446,7 +474,8 @@ cgraph_remove_node (struct cgraph_node *node) { struct cgraph_node *n = *slot; if (!n->next_clone && !n->global.inlined_to - && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))) + && (cgraph_global_info_ready + && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)))) kill_body = true; } @@ -469,6 +498,7 @@ cgraph_mark_reachable_node (struct cgraph_node *node) { notice_global_symbol (node->decl); node->reachable = 1; + gcc_assert (!cgraph_global_info_ready); node->next_needed = cgraph_nodes_queue; cgraph_nodes_queue = node; @@ -531,6 +561,17 @@ cgraph_node_name (struct cgraph_node *node) return lang_hooks.decl_printable_name (node->decl, 2); } +/* Return name of the node used in debug output. */ +static const char * +cgraph_varpool_node_name (struct cgraph_varpool_node *node) +{ + return lang_hooks.decl_printable_name (node->decl, 2); +} + +/* Names used to print out the availability enum. */ +static const char * const availability_names[] = + {"unset", "not_available", "overwrittable", "available", "local"}; + /* Dump given cgraph node. */ void dump_cgraph_node (FILE *f, struct cgraph_node *node) @@ -541,6 +582,14 @@ dump_cgraph_node (FILE *f, struct cgraph_node *node) fprintf (f, " (inline copy in %s/%i)", cgraph_node_name (node->global.inlined_to), node->global.inlined_to->uid); + if (cgraph_function_flags_ready) + fprintf (f, " availability:%s", + availability_names [cgraph_function_body_availability (node)]); + if (node->master_clone && node->master_clone->uid != node->uid) + fprintf (f, "(%i)", node->master_clone->uid); + if (node->count) + fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x", + (HOST_WIDEST_INT)node->count); if (node->local.self_insns) fprintf (f, " %i insns", node->local.self_insns); if (node->global.insns && node->global.insns != node->local.self_insns) @@ -557,10 +606,16 @@ dump_cgraph_node (FILE *f, struct cgraph_node *node) fprintf (f, " output"); if (node->local.local) fprintf (f, " local"); + if (node->local.externally_visible) + fprintf (f, " externally_visible"); + if (node->local.finalized) + fprintf (f, " finalized"); if (node->local.disregard_inline_limits) fprintf (f, " always_inline"); else if (node->local.inlinable) fprintf (f, " inlinable"); + if (node->local.redefined_extern_inline) + fprintf (f, " redefined_extern_inline"); if (TREE_ASM_WRITTEN (node->decl)) fprintf (f, " asm_written"); @@ -569,6 +624,9 @@ dump_cgraph_node (FILE *f, struct cgraph_node *node) { fprintf (f, "%s/%i ", cgraph_node_name (edge->caller), edge->caller->uid); + if (edge->count) + fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ", + (HOST_WIDEST_INT)edge->count); if (!edge->inline_failed) fprintf(f, "(inlined) "); } @@ -580,6 +638,11 @@ dump_cgraph_node (FILE *f, struct cgraph_node *node) edge->callee->uid); if (!edge->inline_failed) fprintf(f, "(inlined) "); + if (edge->count) + fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ", + (HOST_WIDEST_INT)edge->count); + if (edge->loop_nest) + fprintf (f, "(nested in %i loops) ", edge->loop_nest); } fprintf (f, "\n"); } @@ -596,6 +659,39 @@ dump_cgraph (FILE *f) dump_cgraph_node (f, node); } +/* Dump given cgraph node. */ +void +dump_cgraph_varpool_node (FILE *f, struct cgraph_varpool_node *node) +{ + fprintf (f, "%s:", cgraph_varpool_node_name (node)); + fprintf (f, " availability:%s", availability_names [cgraph_variable_initializer_availability (node)]); + if (DECL_INITIAL (node->decl)) + fprintf (f, " initialized"); + if (node->needed) + fprintf (f, " needed"); + if (node->analyzed) + fprintf (f, " analyzed"); + if (node->finalized) + fprintf (f, " finalized"); + if (node->output) + fprintf (f, " output"); + if (node->externally_visible) + fprintf (f, " externally_visible"); + fprintf (f, "\n"); +} + +/* Dump the callgraph. */ + +void +dump_varpool (FILE *f) +{ + struct cgraph_varpool_node *node; + + fprintf (f, "variable pool:\n\n"); + for (node = cgraph_varpool_nodes; node; node = node->next_needed) + dump_cgraph_varpool_node (f, node); +} + /* Returns a hash code for P. */ static hashval_t @@ -664,25 +760,88 @@ change_decl_assembler_name (tree decl, tree name) if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)) && DECL_RTL_SET_P (decl)) - warning ("%D renamed after being referenced in assembly", decl); + warning (0, "%D renamed after being referenced in assembly", decl); SET_DECL_ASSEMBLER_NAME (decl, name); } +/* Helper function for finalization code - add node into lists so it will + be analyzed and compiled. */ +void +cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *node) +{ + if (cgraph_varpool_last_needed_node) + cgraph_varpool_last_needed_node->next_needed = node; + cgraph_varpool_last_needed_node = node; + node->next_needed = NULL; + if (!cgraph_varpool_nodes_queue) + cgraph_varpool_nodes_queue = node; + if (!cgraph_varpool_first_unanalyzed_node) + cgraph_varpool_first_unanalyzed_node = node; + notice_global_symbol (node->decl); +} + +/* Reset the queue of needed nodes. */ +void +cgraph_varpool_reset_queue (void) +{ + cgraph_varpool_last_needed_node = NULL; + cgraph_varpool_nodes_queue = NULL; + cgraph_varpool_first_unanalyzed_node = NULL; +} + /* Notify finalize_compilation_unit that given node is reachable or needed. */ void cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node) { if (!node->needed && node->finalized) - { - node->next_needed = cgraph_varpool_nodes_queue; - cgraph_varpool_nodes_queue = node; - notice_global_symbol (node->decl); - } + cgraph_varpool_enqueue_needed_node (node); node->needed = 1; } +/* Determine if variable DECL is needed. That is, visible to something + either outside this translation unit, something magic in the system + configury, or (if not doing unit-at-a-time) to something we haven't + seen yet. */ + +bool +decide_is_variable_needed (struct cgraph_varpool_node *node, tree decl) +{ + /* If the user told us it is used, then it must be so. */ + if (node->externally_visible + || lookup_attribute ("used", DECL_ATTRIBUTES (decl))) + return true; + + /* ??? If the assembler name is set by hand, it is possible to assemble + the name later after finalizing the function and the fact is noticed + in assemble_name then. This is arguably a bug. */ + if (DECL_ASSEMBLER_NAME_SET_P (decl) + && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))) + return true; + + /* If we decided it was needed before, but at the time we didn't have + the definition available, then it's still needed. */ + if (node->needed) + return true; + + /* Externally visible variables must be output. The exception is + COMDAT variables that must be output only when they are needed. */ + if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)) + return true; + + if (flag_unit_at_a_time) + return false; + + /* If not doing unit at a time, then we'll only defer this function + if its marked for inlining. Otherwise we want to emit it now. */ + + /* We want to emit COMDAT variables only when absolutely necessary. */ + if (DECL_COMDAT (decl)) + return false; + return true; +} + void cgraph_varpool_finalize_decl (tree decl) { @@ -693,47 +852,24 @@ cgraph_varpool_finalize_decl (tree decl) or local (in C, has internal linkage). So do nothing more if this function has already run. */ if (node->finalized) - return; - if (node->needed) { - node->next_needed = cgraph_varpool_nodes_queue; - cgraph_varpool_nodes_queue = node; - notice_global_symbol (decl); + if (cgraph_global_info_ready || !flag_unit_at_a_time) + cgraph_varpool_assemble_pending_decls (); + return; } + if (node->needed) + cgraph_varpool_enqueue_needed_node (node); node->finalized = true; - if (/* Externally visible variables must be output. The exception are - COMDAT functions that must be output only when they are needed. */ - (TREE_PUBLIC (decl) && !DECL_COMDAT (decl)) - /* Function whose name is output to the assembler file must be produced. - It is possible to assemble the name later after finalizing the function - and the fact is noticed in assemble_name then. */ - || (DECL_ASSEMBLER_NAME_SET_P (decl) - && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))) - { - cgraph_varpool_mark_needed_node (node); - } -} - -bool -cgraph_varpool_assemble_pending_decls (void) -{ - bool changed = false; - - while (cgraph_varpool_nodes_queue) - { - tree decl = cgraph_varpool_nodes_queue->decl; - struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue; - - cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed; - if (!TREE_ASM_WRITTEN (decl)) - { - assemble_variable (decl, 0, 1, 0); - changed = true; - } - node->next_needed = NULL; - } - return changed; + if (decide_is_variable_needed (node, decl)) + cgraph_varpool_mark_needed_node (node); + /* Since we reclaim unreachable nodes at the end of every language + level unit, we need to be conservative about possible entry points + there. */ + else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)) + cgraph_varpool_mark_needed_node (node); + if (cgraph_global_info_ready || !flag_unit_at_a_time) + cgraph_varpool_assemble_pending_decls (); } /* Return true when the DECL can possibly be inlined. */ @@ -747,20 +883,35 @@ cgraph_function_possibly_inlined_p (tree decl) /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */ struct cgraph_edge * -cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, tree call_expr) +cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, + tree call_stmt, gcov_type count_scale, int loop_nest, + bool update_original) { - struct cgraph_edge *new = cgraph_create_edge (n, e->callee, call_expr); + struct cgraph_edge *new; + + new = cgraph_create_edge (n, e->callee, call_stmt, + e->count * count_scale / REG_BR_PROB_BASE, + e->loop_nest + loop_nest); new->inline_failed = e->inline_failed; + if (update_original) + e->count -= new->count; return new; } -/* Create node representing clone of N. */ +/* Create node representing clone of N executed COUNT times. Decrease + the execution counts from original node too. + + When UPDATE_ORIGINAL is true, the counts are subtracted from the original + function's profile to reflect the fact that part of execution is handled + by node. */ struct cgraph_node * -cgraph_clone_node (struct cgraph_node *n) +cgraph_clone_node (struct cgraph_node *n, gcov_type count, int loop_nest, + bool update_original) { struct cgraph_node *new = cgraph_create_node (); struct cgraph_edge *e; + gcov_type count_scale; new->decl = n->decl; new->origin = n->origin; @@ -773,16 +924,50 @@ cgraph_clone_node (struct cgraph_node *n) new->local = n->local; new->global = n->global; new->rtl = n->rtl; + new->master_clone = n->master_clone; + new->count = count; + if (n->count) + count_scale = new->count * REG_BR_PROB_BASE / n->count; + else + count_scale = 0; + if (update_original) + n->count -= count; for (e = n->callees;e; e=e->next_callee) - cgraph_clone_edge (e, new, e->call_expr); + cgraph_clone_edge (e, new, e->call_stmt, count_scale, loop_nest, + update_original); new->next_clone = n->next_clone; + new->prev_clone = n; n->next_clone = new; + if (new->next_clone) + new->next_clone->prev_clone = new; return new; } +/* Return true if N is an master_clone, (see cgraph_master_clone). */ + +bool +cgraph_is_master_clone (struct cgraph_node *n) +{ + return (n == cgraph_master_clone (n)); +} + +struct cgraph_node * +cgraph_master_clone (struct cgraph_node *n) +{ + enum availability avail = cgraph_function_body_availability (n); + + if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) + return NULL; + + if (!n->master_clone) + n->master_clone = cgraph_node (n->decl); + + return n->master_clone; +} + /* NODE is no longer nested function; update cgraph accordingly. */ void cgraph_unnest_node (struct cgraph_node *node) @@ -795,4 +980,60 @@ cgraph_unnest_node (struct cgraph_node *node) *node2 = node->next_nested; node->origin = NULL; } + +/* Return function availability. See cgraph.h for description of individual + return values. */ +enum availability +cgraph_function_body_availability (struct cgraph_node *node) +{ + enum availability avail; + gcc_assert (cgraph_function_flags_ready); + if (!node->analyzed) + avail = AVAIL_NOT_AVAILABLE; + else if (node->local.local) + avail = AVAIL_LOCAL; + else if (node->local.externally_visible) + avail = AVAIL_AVAILABLE; + + /* If the function can be overwritten, return OVERWRITABLE. Take + care at least of two notable extensions - the COMDAT functions + used to share template instantiations in C++ (this is symmetric + to code cp_cannot_inline_tree_fn and probably shall be shared and + the inlinability hooks completely eliminated). + + ??? Does the C++ one definition rule allow us to always return + AVAIL_AVAILABLE here? That would be good reason to preserve this + hook Similarly deal with extern inline functions - this is again + necessary to get C++ shared functions having keyed templates + right and in the C extension documentation we probably should + document the requirement of both versions of function (extern + inline and offline) having same side effect characteristics as + good optimization is what this optimization is about. */ + + else if (!(*targetm.binds_local_p) (node->decl) + && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)) + avail = AVAIL_OVERWRITABLE; + else avail = AVAIL_AVAILABLE; + + return avail; +} + +/* Return variable availability. See cgraph.h for description of individual + return values. */ +enum availability +cgraph_variable_initializer_availability (struct cgraph_varpool_node *node) +{ + gcc_assert (cgraph_function_flags_ready); + if (!node->finalized) + return AVAIL_NOT_AVAILABLE; + if (!TREE_PUBLIC (node->decl)) + return AVAIL_AVAILABLE; + /* If the variable can be overwritten, return OVERWRITABLE. Takes + care of at least two notable extensions - the COMDAT variables + used to share template instantiations in C++. */ + if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl)) + return AVAIL_OVERWRITABLE; + return AVAIL_AVAILABLE; +} + #include "gt-cgraph.h"