OSDN Git Service

* bb-reorder.c, c-pch.c, c-pragma.c, c.opt, cfghooks.c, cfgloop.c,
[pf3gnuchains/gcc-fork.git] / gcc / cgraphunit.c
1 /* Callgraph based intraprocedural optimizations.
2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3    Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /* This module implements main driver of compilation process as well as
23    few basic intraprocedural optimizers.
24
25    The main scope of this file is to act as an interface in between
26    tree based frontends and the backend (and middle end)
27
28    The front-end is supposed to use following functionality:
29
30     - cgraph_finalize_function
31
32       This function is called once front-end has parsed whole body of function
33       and it is certain that the function body nor the declaration will change.
34
35       (There is one exception needed for implementing GCC extern inline function.)
36
37     - cgraph_varpool_finalize_variable
38
39       This function has same behavior as the above but is used for static
40       variables.
41
42     - cgraph_finalize_compilation_unit
43
44       This function is called once compilation unit is finalized and it will
45       no longer change.
46
47       In the unit-at-a-time the call-graph construction and local function
48       analysis takes place here.  Bodies of unreachable functions are released
49       to conserve memory usage.
50
51       ???  The compilation unit in this point of view should be compilation
52       unit as defined by the language - for instance C frontend allows multiple
53       compilation units to be parsed at once and it should call function each
54       time parsing is done so we save memory.
55
56     - cgraph_optimize
57
58       In this unit-at-a-time compilation the intra procedural analysis takes
59       place here.  In particular the static functions whose address is never
60       taken are marked as local.  Backend can then use this information to
61       modify calling conventions, do better inlining or similar optimizations.
62
63     - cgraph_assemble_pending_functions
64     - cgraph_varpool_assemble_pending_variables
65
66       In non-unit-at-a-time mode these functions can be used to force compilation
67       of functions or variables that are known to be needed at given stage
68       of compilation
69
70     - cgraph_mark_needed_node
71     - cgraph_varpool_mark_needed_node
72
73       When function or variable is referenced by some hidden way (for instance
74       via assembly code and marked by attribute "used"), the call-graph data structure
75       must be updated accordingly by this function.
76
77     - analyze_expr callback
78
79       This function is responsible for lowering tree nodes not understood by
80       generic code into understandable ones or alternatively marking
81       callgraph and varpool nodes referenced by the as needed.
82
83       ??? On the tree-ssa genericizing should take place here and we will avoid
84       need for these hooks (replacing them by genericizing hook)
85
86     - expand_function callback
87
88       This function is used to expand function and pass it into RTL back-end.
89       Front-end should not make any assumptions about when this function can be
90       called.  In particular cgraph_assemble_pending_functions,
91       cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,
92       cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily
93       previously finalized functions to be expanded.
94
95     We implement two compilation modes.
96
97       - unit-at-a-time:  In this mode analyzing of all functions is deferred
98         to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
99
100         In cgraph_finalize_compilation_unit the reachable functions are
101         analyzed.  During analysis the call-graph edges from reachable
102         functions are constructed and their destinations are marked as
103         reachable.  References to functions and variables are discovered too
104         and variables found to be needed output to the assembly file.  Via
105         mark_referenced call in assemble_variable functions referenced by
106         static variables are noticed too.
107
108         The intra-procedural information is produced and its existence
109         indicated by global_info_ready.  Once this flag is set it is impossible
110         to change function from !reachable to reachable and thus
111         assemble_variable no longer call mark_referenced.
112
113         Finally the call-graph is topologically sorted and all reachable functions
114         that has not been completely inlined or are not external are output.
115
116         ??? It is possible that reference to function or variable is optimized
117         out.  We can not deal with this nicely because topological order is not
118         suitable for it.  For tree-ssa we may consider another pass doing
119         optimization and re-discovering reachable functions.
120
121         ??? Reorganize code so variables are output very last and only if they
122         really has been referenced by produced code, so we catch more cases
123         where reference has been optimized out.
124
125       - non-unit-at-a-time
126
127         All functions are variables are output as early as possible to conserve
128         memory consumption.  This may or may not result in less memory used but
129         it is still needed for some legacy code that rely on particular ordering
130         of things output from the compiler.
131
132         Varpool data structures are not used and variables are output directly.
133
134         Functions are output early using call of
135         cgraph_assemble_pending_function from cgraph_finalize_function.  The
136         decision on whether function is needed is made more conservative so
137         uninlininable static functions are needed too.  During the call-graph
138         construction the edge destinations are not marked as reachable and it
139         is completely relied upn assemble_variable to mark them.  */
140
141
142 #include "config.h"
143 #include "system.h"
144 #include "coretypes.h"
145 #include "tm.h"
146 #include "tree.h"
147 #include "rtl.h"
148 #include "tree-flow.h"
149 #include "tree-inline.h"
150 #include "langhooks.h"
151 #include "pointer-set.h"
152 #include "toplev.h"
153 #include "flags.h"
154 #include "ggc.h"
155 #include "debug.h"
156 #include "target.h"
157 #include "cgraph.h"
158 #include "diagnostic.h"
159 #include "timevar.h"
160 #include "params.h"
161 #include "fibheap.h"
162 #include "c-common.h"
163 #include "intl.h"
164 #include "function.h"
165 #include "tree-gimple.h"
166 #include "tree-pass.h"
167 #include "output.h"
168
169 static void cgraph_expand_all_functions (void);
170 static void cgraph_mark_functions_to_output (void);
171 static void cgraph_expand_function (struct cgraph_node *);
172 static tree record_reference (tree *, int *, void *);
173 static void cgraph_analyze_function (struct cgraph_node *node);
174
175 /* Records tree nodes seen in record_reference.  Simply using
176    walk_tree_without_duplicates doesn't guarantee each node is visited
177    once because it gets a new htab upon each recursive call from
178    record_reference itself.  */
179 static struct pointer_set_t *visited_nodes;
180
181 static FILE *cgraph_dump_file;
182
183 /* Determine if function DECL is needed.  That is, visible to something
184    either outside this translation unit, something magic in the system
185    configury, or (if not doing unit-at-a-time) to something we havn't
186    seen yet.  */
187
188 static bool
189 decide_is_function_needed (struct cgraph_node *node, tree decl)
190 {
191   tree origin;
192   if (MAIN_NAME_P (DECL_NAME (decl))
193       && TREE_PUBLIC (decl))
194     {
195       node->local.externally_visible = true;
196       return true;
197     }
198
199   /* If the user told us it is used, then it must be so.  */
200   if (node->local.externally_visible
201       || lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
202     return true;
203
204   /* ??? If the assembler name is set by hand, it is possible to assemble
205      the name later after finalizing the function and the fact is noticed
206      in assemble_name then.  This is arguably a bug.  */
207   if (DECL_ASSEMBLER_NAME_SET_P (decl)
208       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
209     return true;
210
211   /* If we decided it was needed before, but at the time we didn't have
212      the body of the function available, then it's still needed.  We have
213      to go back and re-check its dependencies now.  */
214   if (node->needed)
215     return true;
216
217   /* Externally visible functions must be output.  The exception is
218      COMDAT functions that must be output only when they are needed.  */
219   if ((TREE_PUBLIC (decl) && !flag_whole_program)
220       && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
221     return true;
222
223   /* Constructors and destructors are reachable from the runtime by
224      some mechanism.  */
225   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
226     return true;
227
228   if (flag_unit_at_a_time)
229     return false;
230
231   /* If not doing unit at a time, then we'll only defer this function
232      if its marked for inlining.  Otherwise we want to emit it now.  */
233
234   /* "extern inline" functions are never output locally.  */
235   if (DECL_EXTERNAL (decl))
236     return false;
237   /* Nested functions of extern inline function shall not be emit unless
238      we inlined the origin.  */
239   for (origin = decl_function_context (decl); origin;
240        origin = decl_function_context (origin))
241     if (DECL_EXTERNAL (origin))
242       return false;
243   /* We want to emit COMDAT functions only when absolutely necessary.  */
244   if (DECL_COMDAT (decl))
245     return false;
246   if (!DECL_INLINE (decl)
247       || (!node->local.disregard_inline_limits
248           /* When declared inline, defer even the uninlinable functions.
249              This allows them to be eliminated when unused.  */
250           && !DECL_DECLARED_INLINE_P (decl) 
251           && (!node->local.inlinable || !cgraph_default_inline_p (node))))
252     return true;
253
254   return false;
255 }
256
257 /* Walk the decls we marked as necessary and see if they reference new
258    variables or functions and add them into the worklists.  */
259 static bool
260 cgraph_varpool_analyze_pending_decls (void)
261 {
262   bool changed = false;
263   timevar_push (TV_CGRAPH);
264
265   while (cgraph_varpool_first_unanalyzed_node)
266     {
267       tree decl = cgraph_varpool_first_unanalyzed_node->decl;
268
269       cgraph_varpool_first_unanalyzed_node->analyzed = true;
270
271       cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;
272
273       if (DECL_INITIAL (decl))
274         {
275           visited_nodes = pointer_set_create ();
276           walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
277           pointer_set_destroy (visited_nodes);
278           visited_nodes = NULL;
279         }
280       changed = true;
281     }
282   timevar_pop (TV_CGRAPH);
283   return changed;
284 }
285
286 /* Optimization of function bodies might've rendered some variables as
287    unnecessary so we want to avoid these from being compiled.
288
289    This is done by pruning the queue and keeping only the variables that
290    really appear needed (ie they are either externally visible or referenced
291    by compiled function). Re-doing the reachability analysis on variables
292    brings back the remaining variables referenced by these.  */
293 static void
294 cgraph_varpool_remove_unreferenced_decls (void)
295 {
296   struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;
297
298   cgraph_varpool_reset_queue ();
299
300   if (errorcount || sorrycount)
301     return;
302
303   while (node)
304     {
305       tree decl = node->decl;
306       next = node->next_needed;
307       node->needed = 0;
308
309       if (node->finalized
310           && ((DECL_ASSEMBLER_NAME_SET_P (decl)
311                && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
312               || node->force_output
313               || decide_is_variable_needed (node, decl)))
314         cgraph_varpool_mark_needed_node (node);
315
316       node = next;
317     }
318   cgraph_varpool_analyze_pending_decls ();
319 }
320
321
322 /* When not doing unit-at-a-time, output all functions enqueued.
323    Return true when such a functions were found.  */
324
325 bool
326 cgraph_assemble_pending_functions (void)
327 {
328   bool output = false;
329
330   if (flag_unit_at_a_time)
331     return false;
332
333   while (cgraph_nodes_queue)
334     {
335       struct cgraph_node *n = cgraph_nodes_queue;
336
337       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
338       n->next_needed = NULL;
339       if (!n->global.inlined_to
340           && !n->alias
341           && !DECL_EXTERNAL (n->decl))
342         {
343           cgraph_expand_function (n);
344           output = true;
345         }
346     }
347
348   return output;
349 }
350 /* As an GCC extension we allow redefinition of the function.  The
351    semantics when both copies of bodies differ is not well defined.
352    We replace the old body with new body so in unit at a time mode
353    we always use new body, while in normal mode we may end up with
354    old body inlined into some functions and new body expanded and
355    inlined in others.
356
357    ??? It may make more sense to use one body for inlining and other
358    body for expanding the function but this is difficult to do.  */
359
360 static void
361 cgraph_reset_node (struct cgraph_node *node)
362 {
363   /* If node->output is set, then this is a unit-at-a-time compilation
364      and we have already begun whole-unit analysis.  This is *not*
365      testing for whether we've already emitted the function.  That
366      case can be sort-of legitimately seen with real function 
367      redefinition errors.  I would argue that the front end should
368      never present us with such a case, but don't enforce that for now.  */
369   gcc_assert (!node->output);
370
371   /* Reset our data structures so we can analyze the function again.  */
372   memset (&node->local, 0, sizeof (node->local));
373   memset (&node->global, 0, sizeof (node->global));
374   memset (&node->rtl, 0, sizeof (node->rtl));
375   node->analyzed = false;
376   node->local.redefined_extern_inline = true;
377   node->local.finalized = false;
378
379   if (!flag_unit_at_a_time)
380     {
381       struct cgraph_node *n;
382
383       for (n = cgraph_nodes; n; n = n->next)
384         if (n->global.inlined_to == node)
385           cgraph_remove_node (n);
386     }
387
388   cgraph_node_remove_callees (node);
389
390   /* We may need to re-queue the node for assembling in case
391      we already proceeded it and ignored as not needed.  */
392   if (node->reachable && !flag_unit_at_a_time)
393     {
394       struct cgraph_node *n;
395
396       for (n = cgraph_nodes_queue; n; n = n->next_needed)
397         if (n == node)
398           break;
399       if (!n)
400         node->reachable = 0;
401     }
402 }
403
404 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
405    logic in effect.  If NESTED is true, then our caller cannot stand to have
406    the garbage collector run at the moment.  We would need to either create
407    a new GC context, or just not compile right now.  */
408
409 void
410 cgraph_finalize_function (tree decl, bool nested)
411 {
412   struct cgraph_node *node = cgraph_node (decl);
413
414   if (node->local.finalized)
415     cgraph_reset_node (node);
416
417   notice_global_symbol (decl);
418   node->decl = decl;
419   node->local.finalized = true;
420   node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
421   if (node->nested)
422     lower_nested_functions (decl);
423   gcc_assert (!node->nested);
424
425   /* If not unit at a time, then we need to create the call graph
426      now, so that called functions can be queued and emitted now.  */
427   if (!flag_unit_at_a_time)
428     {
429       cgraph_analyze_function (node);
430       cgraph_decide_inlining_incrementally (node, false);
431     }
432
433   if (decide_is_function_needed (node, decl))
434     cgraph_mark_needed_node (node);
435
436   /* Since we reclaim unreachable nodes at the end of every language
437      level unit, we need to be conservative about possible entry points
438      there.  */
439   if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
440     cgraph_mark_reachable_node (node);
441
442   /* If not unit at a time, go ahead and emit everything we've found
443      to be reachable at this time.  */
444   if (!nested)
445     {
446       if (!cgraph_assemble_pending_functions ())
447         ggc_collect ();
448     }
449
450   /* If we've not yet emitted decl, tell the debug info about it.  */
451   if (!TREE_ASM_WRITTEN (decl))
452     (*debug_hooks->deferred_inline_function) (decl);
453
454   /* Possibly warn about unused parameters.  */
455   if (warn_unused_parameter)
456     do_warn_unused_parameter (decl);
457 }
458
459 void
460 cgraph_lower_function (struct cgraph_node *node)
461 {
462   if (node->lowered)
463     return;
464   tree_lowering_passes (node->decl);
465   node->lowered = true;
466 }
467
468 /* Walk tree and record all calls.  Called via walk_tree.  */
469 static tree
470 record_reference (tree *tp, int *walk_subtrees, void *data)
471 {
472   tree t = *tp;
473
474   switch (TREE_CODE (t))
475     {
476     case VAR_DECL:
477       /* ??? Really, we should mark this decl as *potentially* referenced
478          by this function and re-examine whether the decl is actually used
479          after rtl has been generated.  */
480       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
481         {
482           cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
483           if (lang_hooks.callgraph.analyze_expr)
484             return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, 
485                                                       data);
486         }
487       break;
488
489     case FDESC_EXPR:
490     case ADDR_EXPR:
491       if (flag_unit_at_a_time)
492         {
493           /* Record dereferences to the functions.  This makes the
494              functions reachable unconditionally.  */
495           tree decl = TREE_OPERAND (*tp, 0);
496           if (TREE_CODE (decl) == FUNCTION_DECL)
497             cgraph_mark_needed_node (cgraph_node (decl));
498         }
499       break;
500
501     default:
502       /* Save some cycles by not walking types and declaration as we
503          won't find anything useful there anyway.  */
504       if (IS_TYPE_OR_DECL_P (*tp))
505         {
506           *walk_subtrees = 0;
507           break;
508         }
509
510       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
511         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);
512       break;
513     }
514
515   return NULL;
516 }
517
518 /* Create cgraph edges for function calls inside BODY from NODE.  */
519
520 static void
521 cgraph_create_edges (struct cgraph_node *node, tree body)
522 {
523   basic_block bb;
524
525   struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
526   block_stmt_iterator bsi;
527   tree step;
528   visited_nodes = pointer_set_create ();
529
530   /* Reach the trees by walking over the CFG, and note the 
531      enclosing basic-blocks in the call edges.  */
532   FOR_EACH_BB_FN (bb, this_cfun)
533     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
534       {
535         tree stmt = bsi_stmt (bsi);
536         tree call = get_call_expr_in (stmt);
537         tree decl;
538
539         if (call && (decl = get_callee_fndecl (call)))
540           {
541             cgraph_create_edge (node, cgraph_node (decl), stmt,
542                                 bb->count,
543                                 bb->loop_depth);
544             walk_tree (&TREE_OPERAND (call, 1),
545                        record_reference, node, visited_nodes);
546             if (TREE_CODE (stmt) == MODIFY_EXPR)
547               walk_tree (&TREE_OPERAND (stmt, 0),
548                          record_reference, node, visited_nodes);
549           }
550         else 
551           walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes);
552       }
553
554   /* Look for initializers of constant variables and private statics.  */
555   for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list;
556        step;
557        step = TREE_CHAIN (step))
558     {
559       tree decl = TREE_VALUE (step);
560       if (TREE_CODE (decl) == VAR_DECL
561           && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
562           && flag_unit_at_a_time)
563         cgraph_varpool_finalize_decl (decl);
564       else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))
565         walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
566     }
567     
568   pointer_set_destroy (visited_nodes);
569   visited_nodes = NULL;
570 }
571
572 /* Give initial reasons why inlining would fail.  Those gets
573    either NULLified or usually overwritten by more precise reason
574    later.  */
575 static void
576 initialize_inline_failed (struct cgraph_node *node)
577 {
578   struct cgraph_edge *e;
579
580   for (e = node->callers; e; e = e->next_caller)
581     {
582       gcc_assert (!e->callee->global.inlined_to);
583       gcc_assert (e->inline_failed);
584       if (node->local.redefined_extern_inline)
585         e->inline_failed = N_("redefined extern inline functions are not "
586                            "considered for inlining");
587       else if (!node->local.inlinable)
588         e->inline_failed = N_("function not inlinable");
589       else
590         e->inline_failed = N_("function not considered for inlining");
591     }
592 }
593
594 /* Rebuild call edges from current function after a passes not aware
595    of cgraph updating.  */
596 static void
597 rebuild_cgraph_edges (void)
598 {
599   basic_block bb;
600   struct cgraph_node *node = cgraph_node (current_function_decl);
601   block_stmt_iterator bsi;
602
603   cgraph_node_remove_callees (node);
604
605   node->count = ENTRY_BLOCK_PTR->count;
606
607   FOR_EACH_BB (bb)
608     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
609       {
610         tree stmt = bsi_stmt (bsi);
611         tree call = get_call_expr_in (stmt);
612         tree decl;
613
614         if (call && (decl = get_callee_fndecl (call)))
615           cgraph_create_edge (node, cgraph_node (decl), stmt,
616                               bb->count,
617                               bb->loop_depth);
618       }
619   initialize_inline_failed (node);
620   gcc_assert (!node->global.inlined_to);
621 }
622
623 struct tree_opt_pass pass_rebuild_cgraph_edges =
624 {
625   NULL,                                 /* name */
626   NULL,                                 /* gate */
627   rebuild_cgraph_edges,                 /* execute */
628   NULL,                                 /* sub */
629   NULL,                                 /* next */
630   0,                                    /* static_pass_number */
631   0,                                    /* tv_id */
632   PROP_cfg,                             /* properties_required */
633   0,                                    /* properties_provided */
634   0,                                    /* properties_destroyed */
635   0,                                    /* todo_flags_start */
636   0,                                    /* todo_flags_finish */
637   0                                     /* letter */
638 };
639
640 /* Verify cgraph nodes of given cgraph node.  */
641 void
642 verify_cgraph_node (struct cgraph_node *node)
643 {
644   struct cgraph_edge *e;
645   struct cgraph_node *main_clone;
646   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
647   basic_block this_block;
648   block_stmt_iterator bsi;
649   bool error_found = false;
650
651   timevar_push (TV_CGRAPH_VERIFY);
652   for (e = node->callees; e; e = e->next_callee)
653     if (e->aux)
654       {
655         error ("aux field set for edge %s->%s",
656                cgraph_node_name (e->caller), cgraph_node_name (e->callee));
657         error_found = true;
658       }
659   for (e = node->callers; e; e = e->next_caller)
660     {
661       if (!e->inline_failed)
662         {
663           if (node->global.inlined_to
664               != (e->caller->global.inlined_to
665                   ? e->caller->global.inlined_to : e->caller))
666             {
667               error ("inlined_to pointer is wrong");
668               error_found = true;
669             }
670           if (node->callers->next_caller)
671             {
672               error ("multiple inline callers");
673               error_found = true;
674             }
675         }
676       else
677         if (node->global.inlined_to)
678           {
679             error ("inlined_to pointer set for noninline callers");
680             error_found = true;
681           }
682     }
683   if (!node->callers && node->global.inlined_to)
684     {
685       error ("inlined_to pointer is set but no predecesors found");
686       error_found = true;
687     }
688   if (node->global.inlined_to == node)
689     {
690       error ("inlined_to pointer refers to itself");
691       error_found = true;
692     }
693
694   for (main_clone = cgraph_node (node->decl); main_clone;
695        main_clone = main_clone->next_clone)
696     if (main_clone == node)
697       break;
698   if (!node)
699     {
700       error ("node not found in DECL_ASSEMBLER_NAME hash");
701       error_found = true;
702     }
703   
704   if (node->analyzed
705       && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
706       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
707     {
708       if (this_cfun->cfg)
709         {
710           /* The nodes we're interested in are never shared, so walk
711              the tree ignoring duplicates.  */
712           visited_nodes = pointer_set_create ();
713           /* Reach the trees by walking over the CFG, and note the
714              enclosing basic-blocks in the call edges.  */
715           FOR_EACH_BB_FN (this_block, this_cfun)
716             for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
717               {
718                 tree stmt = bsi_stmt (bsi);
719                 tree call = get_call_expr_in (stmt);
720                 tree decl;
721                 if (call && (decl = get_callee_fndecl (call)))
722                   {
723                     struct cgraph_edge *e = cgraph_edge (node, stmt);
724                     if (e)
725                       {
726                         if (e->aux)
727                           {
728                             error ("shared call_stmt:");
729                             debug_generic_stmt (stmt);
730                             error_found = true;
731                           }
732                         if (e->callee->decl != cgraph_node (decl)->decl)
733                           {
734                             error ("edge points to wrong declaration:");
735                             debug_tree (e->callee->decl);
736                             fprintf (stderr," Instead of:");
737                             debug_tree (decl);
738                           }
739                         e->aux = (void *)1;
740                       }
741                     else
742                       {
743                         error ("missing callgraph edge for call stmt:");
744                         debug_generic_stmt (stmt);
745                         error_found = true;
746                       }
747                   }
748               }
749           pointer_set_destroy (visited_nodes);
750           visited_nodes = NULL;
751         }
752       else
753         /* No CFG available?!  */
754         gcc_unreachable ();
755
756       for (e = node->callees; e; e = e->next_callee)
757         {
758           if (!e->aux)
759             {
760               error ("edge %s->%s has no corresponding call_stmt",
761                      cgraph_node_name (e->caller),
762                      cgraph_node_name (e->callee));
763               debug_generic_stmt (e->call_stmt);
764               error_found = true;
765             }
766           e->aux = 0;
767         }
768     }
769   if (error_found)
770     {
771       dump_cgraph_node (stderr, node);
772       internal_error ("verify_cgraph_node failed");
773     }
774   timevar_pop (TV_CGRAPH_VERIFY);
775 }
776
777 /* Verify whole cgraph structure.  */
778 void
779 verify_cgraph (void)
780 {
781   struct cgraph_node *node;
782
783   if (sorrycount || errorcount)
784     return;
785
786   for (node = cgraph_nodes; node; node = node->next)
787     verify_cgraph_node (node);
788 }
789
790
791 /* Output all variables enqueued to be assembled.  */
792 bool
793 cgraph_varpool_assemble_pending_decls (void)
794 {
795   bool changed = false;
796
797   if (errorcount || sorrycount)
798     return false;
799  
800   /* EH might mark decls as needed during expansion.  This should be safe since
801      we don't create references to new function, but it should not be used
802      elsewhere.  */
803   cgraph_varpool_analyze_pending_decls ();
804
805   while (cgraph_varpool_nodes_queue)
806     {
807       tree decl = cgraph_varpool_nodes_queue->decl;
808       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
809
810       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
811       if (!TREE_ASM_WRITTEN (decl) && !node->alias && !DECL_EXTERNAL (decl))
812         {
813           assemble_variable (decl, 0, 1, 0);
814           /* Local static variables are never seen by check_global_declarations
815              so we need to output debug info by hand.  */
816           if (decl_function_context (decl) && errorcount == 0 && sorrycount == 0)
817             {
818               timevar_push (TV_SYMOUT);
819               (*debug_hooks->global_decl) (decl);
820               timevar_pop (TV_SYMOUT);
821             }
822           changed = true;
823         }
824       node->next_needed = NULL;
825     }
826   return changed;
827 }
828
829 /* Analyze the function scheduled to be output.  */
830 static void
831 cgraph_analyze_function (struct cgraph_node *node)
832 {
833   tree decl = node->decl;
834
835   current_function_decl = decl;
836   push_cfun (DECL_STRUCT_FUNCTION (decl));
837   cgraph_lower_function (node);
838
839   /* First kill forward declaration so reverse inlining works properly.  */
840   cgraph_create_edges (node, decl);
841
842   node->local.inlinable = tree_inlinable_function_p (decl);
843   node->local.self_insns = estimate_num_insns (decl);
844   if (node->local.inlinable)
845     node->local.disregard_inline_limits
846       = lang_hooks.tree_inlining.disregard_inline_limits (decl);
847   initialize_inline_failed (node);
848   if (flag_really_no_inline && !node->local.disregard_inline_limits)
849     node->local.inlinable = 0;
850   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
851   node->global.insns = node->local.self_insns;
852
853   node->analyzed = true;
854   pop_cfun ();
855   current_function_decl = NULL;
856 }
857
858 /* Analyze the whole compilation unit once it is parsed completely.  */
859
860 void
861 cgraph_finalize_compilation_unit (void)
862 {
863   struct cgraph_node *node;
864   /* Keep track of already processed nodes when called multiple times for
865      intermodule optimization.  */
866   static struct cgraph_node *first_analyzed;
867
868   finish_aliases_1 ();
869
870   if (!flag_unit_at_a_time)
871     {
872       cgraph_assemble_pending_functions ();
873       return;
874     }
875
876   if (!quiet_flag)
877     {
878       fprintf (stderr, "\nAnalyzing compilation unit");
879       fflush (stderr);
880     }
881
882   timevar_push (TV_CGRAPH);
883   cgraph_varpool_analyze_pending_decls ();
884   if (cgraph_dump_file)
885     {
886       fprintf (cgraph_dump_file, "Initial entry points:");
887       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
888         if (node->needed && DECL_SAVED_TREE (node->decl))
889           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
890       fprintf (cgraph_dump_file, "\n");
891     }
892
893   /* Propagate reachability flag and lower representation of all reachable
894      functions.  In the future, lowering will introduce new functions and
895      new entry points on the way (by template instantiation and virtual
896      method table generation for instance).  */
897   while (cgraph_nodes_queue)
898     {
899       struct cgraph_edge *edge;
900       tree decl = cgraph_nodes_queue->decl;
901
902       node = cgraph_nodes_queue;
903       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
904       node->next_needed = NULL;
905
906       /* ??? It is possible to create extern inline function and later using
907          weak alias attribute to kill its body. See
908          gcc.c-torture/compile/20011119-1.c  */
909       if (!DECL_SAVED_TREE (decl))
910         {
911           cgraph_reset_node (node);
912           continue;
913         }
914
915       gcc_assert (!node->analyzed && node->reachable);
916       gcc_assert (DECL_SAVED_TREE (decl));
917
918       cgraph_analyze_function (node);
919
920       for (edge = node->callees; edge; edge = edge->next_callee)
921         if (!edge->callee->reachable)
922           cgraph_mark_reachable_node (edge->callee);
923
924       cgraph_varpool_analyze_pending_decls ();
925     }
926
927   /* Collect entry points to the unit.  */
928
929   if (cgraph_dump_file)
930     {
931       fprintf (cgraph_dump_file, "Unit entry points:");
932       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
933         if (node->needed && DECL_SAVED_TREE (node->decl))
934           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
935       fprintf (cgraph_dump_file, "\n\nInitial ");
936       dump_cgraph (cgraph_dump_file);
937     }
938
939   if (cgraph_dump_file)
940     fprintf (cgraph_dump_file, "\nReclaiming functions:");
941
942   for (node = cgraph_nodes; node != first_analyzed; node = node->next)
943     {
944       tree decl = node->decl;
945
946       if (node->local.finalized && !DECL_SAVED_TREE (decl))
947         cgraph_reset_node (node);
948
949       if (!node->reachable && DECL_SAVED_TREE (decl))
950         {
951           if (cgraph_dump_file)
952             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
953           cgraph_remove_node (node);
954           continue;
955         }
956       else
957         node->next_needed = NULL;
958       gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl));
959       gcc_assert (node->analyzed == node->local.finalized);
960     }
961   if (cgraph_dump_file)
962     {
963       fprintf (cgraph_dump_file, "\n\nReclaimed ");
964       dump_cgraph (cgraph_dump_file);
965     }
966   first_analyzed = cgraph_nodes;
967   ggc_collect ();
968   timevar_pop (TV_CGRAPH);
969 }
970 /* Figure out what functions we want to assemble.  */
971
972 static void
973 cgraph_mark_functions_to_output (void)
974 {
975   struct cgraph_node *node;
976
977   for (node = cgraph_nodes; node; node = node->next)
978     {
979       tree decl = node->decl;
980       struct cgraph_edge *e;
981       
982       gcc_assert (!node->output);
983
984       for (e = node->callers; e; e = e->next_caller)
985         if (e->inline_failed)
986           break;
987
988       /* We need to output all local functions that are used and not
989          always inlined, as well as those that are reachable from
990          outside the current compilation unit.  */
991       if (DECL_SAVED_TREE (decl)
992           && !node->global.inlined_to
993           && (node->needed
994               || (e && node->reachable))
995           && !TREE_ASM_WRITTEN (decl)
996           && !DECL_EXTERNAL (decl))
997         node->output = 1;
998       else
999         {
1000           /* We should've reclaimed all functions that are not needed.  */
1001 #ifdef ENABLE_CHECKING
1002           if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
1003               && !DECL_EXTERNAL (decl))
1004             {
1005               dump_cgraph_node (stderr, node);
1006               internal_error ("failed to reclaim unneeded function");
1007             }
1008 #endif
1009           gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
1010                       || DECL_EXTERNAL (decl));
1011
1012         }
1013       
1014     }
1015 }
1016
1017 /* Expand function specified by NODE.  */
1018
1019 static void
1020 cgraph_expand_function (struct cgraph_node *node)
1021 {
1022   tree decl = node->decl;
1023
1024   /* We ought to not compile any inline clones.  */
1025   gcc_assert (!node->global.inlined_to);
1026
1027   if (flag_unit_at_a_time)
1028     announce_function (decl);
1029
1030   cgraph_lower_function (node);
1031
1032   /* Generate RTL for the body of DECL.  */
1033   lang_hooks.callgraph.expand_function (decl);
1034
1035   /* Make sure that BE didn't give up on compiling.  */
1036   /* ??? Can happen with nested function of extern inline.  */
1037   gcc_assert (TREE_ASM_WRITTEN (node->decl));
1038
1039   current_function_decl = NULL;
1040   if (!cgraph_preserve_function_body_p (node->decl))
1041     {
1042       DECL_SAVED_TREE (node->decl) = NULL;
1043       DECL_STRUCT_FUNCTION (node->decl) = NULL;
1044       DECL_INITIAL (node->decl) = error_mark_node;
1045       /* Eliminate all call edges.  This is important so the call_expr no longer
1046          points to the dead function body.  */
1047       cgraph_node_remove_callees (node);
1048     }
1049
1050   cgraph_function_flags_ready = true;
1051 }
1052
1053 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1054
1055 bool
1056 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
1057 {
1058   *reason = e->inline_failed;
1059   return !e->inline_failed;
1060 }
1061
1062
1063
1064 /* Expand all functions that must be output.
1065
1066    Attempt to topologically sort the nodes so function is output when
1067    all called functions are already assembled to allow data to be
1068    propagated across the callgraph.  Use a stack to get smaller distance
1069    between a function and its callees (later we may choose to use a more
1070    sophisticated algorithm for function reordering; we will likely want
1071    to use subsections to make the output functions appear in top-down
1072    order).  */
1073
1074 static void
1075 cgraph_expand_all_functions (void)
1076 {
1077   struct cgraph_node *node;
1078   struct cgraph_node **order =
1079     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1080   int order_pos = 0, new_order_pos = 0;
1081   int i;
1082
1083   order_pos = cgraph_postorder (order);
1084   gcc_assert (order_pos == cgraph_n_nodes);
1085
1086   /* Garbage collector may remove inline clones we eliminate during
1087      optimization.  So we must be sure to not reference them.  */
1088   for (i = 0; i < order_pos; i++)
1089     if (order[i]->output)
1090       order[new_order_pos++] = order[i];
1091
1092   for (i = new_order_pos - 1; i >= 0; i--)
1093     {
1094       node = order[i];
1095       if (node->output)
1096         {
1097           gcc_assert (node->reachable);
1098           node->output = 0;
1099           cgraph_expand_function (node);
1100         }
1101     }
1102   free (order);
1103 }
1104
1105 /* Mark visibility of all functions.
1106    
1107    A local function is one whose calls can occur only in the current
1108    compilation unit and all its calls are explicit, so we can change
1109    its calling convention.  We simply mark all static functions whose
1110    address is not taken as local.
1111
1112    We also change the TREE_PUBLIC flag of all declarations that are public
1113    in language point of view but we want to overwrite this default
1114    via visibilities for the backend point of view.  */
1115
1116 static void
1117 cgraph_function_and_variable_visibility (void)
1118 {
1119   struct cgraph_node *node;
1120   struct cgraph_varpool_node *vnode;
1121
1122   for (node = cgraph_nodes; node; node = node->next)
1123     {
1124       if (node->reachable
1125           && (DECL_COMDAT (node->decl)
1126               || (TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
1127         node->local.externally_visible = true;
1128       if (!node->local.externally_visible && node->analyzed
1129           && !DECL_EXTERNAL (node->decl))
1130         {
1131           gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
1132           TREE_PUBLIC (node->decl) = 0;
1133         }
1134       node->local.local = (!node->needed
1135                            && node->analyzed
1136                            && !DECL_EXTERNAL (node->decl)
1137                            && !node->local.externally_visible);
1138     }
1139   for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
1140     {
1141       if (vnode->needed
1142           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
1143         vnode->externally_visible = 1;
1144       if (!vnode->externally_visible)
1145         {
1146           gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
1147           TREE_PUBLIC (vnode->decl) = 0;
1148         }
1149      gcc_assert (TREE_STATIC (vnode->decl));
1150     }
1151
1152   /* Because we have to be conservative on the boundaries of source
1153      level units, it is possible that we marked some functions in
1154      reachable just because they might be used later via external
1155      linkage, but after making them local they are really unreachable
1156      now.  */
1157   cgraph_remove_unreachable_nodes (true, cgraph_dump_file);
1158
1159   if (cgraph_dump_file)
1160     {
1161       fprintf (cgraph_dump_file, "\nMarking local functions:");
1162       for (node = cgraph_nodes; node; node = node->next)
1163         if (node->local.local)
1164           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1165       fprintf (cgraph_dump_file, "\n\n");
1166       fprintf (cgraph_dump_file, "\nMarking externally visible functions:");
1167       for (node = cgraph_nodes; node; node = node->next)
1168         if (node->local.externally_visible)
1169           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1170       fprintf (cgraph_dump_file, "\n\n");
1171     }
1172   cgraph_function_flags_ready = true;
1173 }
1174
1175 /* Return true when function body of DECL still needs to be kept around
1176    for later re-use.  */
1177 bool
1178 cgraph_preserve_function_body_p (tree decl)
1179 {
1180   struct cgraph_node *node;
1181   /* Keep the body; we're going to dump it.  */
1182   if (dump_enabled_p (TDI_tree_all))
1183     return true;
1184   if (!cgraph_global_info_ready)
1185     return (DECL_INLINE (decl) && !flag_really_no_inline);
1186   /* Look if there is any clone around.  */
1187   for (node = cgraph_node (decl); node; node = node->next_clone)
1188     if (node->global.inlined_to)
1189       return true;
1190   return false;
1191 }
1192
1193 /* Perform simple optimizations based on callgraph.  */
1194
1195 void
1196 cgraph_optimize (void)
1197 {
1198 #ifdef ENABLE_CHECKING
1199   verify_cgraph ();
1200 #endif
1201   if (!flag_unit_at_a_time)
1202     {
1203       cgraph_varpool_assemble_pending_decls ();
1204       return;
1205     }
1206
1207   process_pending_assemble_externals ();
1208   
1209   /* Frontend may output common variables after the unit has been finalized.
1210      It is safe to deal with them here as they are always zero initialized.  */
1211   cgraph_varpool_analyze_pending_decls ();
1212
1213   timevar_push (TV_CGRAPHOPT);
1214   if (!quiet_flag)
1215     fprintf (stderr, "Performing intraprocedural optimizations\n");
1216
1217   cgraph_function_and_variable_visibility ();
1218   if (cgraph_dump_file)
1219     {
1220       fprintf (cgraph_dump_file, "Marked ");
1221       dump_cgraph (cgraph_dump_file);
1222     }
1223   ipa_passes ();
1224   /* This pass remove bodies of extern inline functions we never inlined.
1225      Do this later so other IPA passes see what is really going on.  */
1226   cgraph_remove_unreachable_nodes (false, dump_file);
1227   cgraph_global_info_ready = true;
1228   if (cgraph_dump_file)
1229     {
1230       fprintf (cgraph_dump_file, "Optimized ");
1231       dump_cgraph (cgraph_dump_file);
1232       dump_varpool (cgraph_dump_file);
1233     }
1234   timevar_pop (TV_CGRAPHOPT);
1235
1236   /* Output everything.  */
1237   if (!quiet_flag)
1238     fprintf (stderr, "Assembling functions:\n");
1239 #ifdef ENABLE_CHECKING
1240   verify_cgraph ();
1241 #endif
1242   
1243   cgraph_mark_functions_to_output ();
1244   cgraph_expand_all_functions ();
1245   cgraph_varpool_remove_unreferenced_decls ();
1246
1247   cgraph_varpool_assemble_pending_decls ();
1248
1249   if (cgraph_dump_file)
1250     {
1251       fprintf (cgraph_dump_file, "\nFinal ");
1252       dump_cgraph (cgraph_dump_file);
1253     }
1254 #ifdef ENABLE_CHECKING
1255   verify_cgraph ();
1256   /* Double check that all inline clones are gone and that all
1257      function bodies have been released from memory.  */
1258   if (flag_unit_at_a_time
1259       && !dump_enabled_p (TDI_tree_all)
1260       && !(sorrycount || errorcount))
1261     {
1262       struct cgraph_node *node;
1263       bool error_found = false;
1264
1265       for (node = cgraph_nodes; node; node = node->next)
1266         if (node->analyzed
1267             && (node->global.inlined_to
1268                 || DECL_SAVED_TREE (node->decl)))
1269           {
1270             error_found = true;
1271             dump_cgraph_node (stderr, node);
1272           }
1273       if (error_found)
1274         internal_error ("nodes with no released memory found");
1275     }
1276 #endif
1277 }
1278
1279 /* Generate and emit a static constructor or destructor.  WHICH must be
1280    one of 'I' or 'D'.  BODY should be a STATEMENT_LIST containing 
1281    GENERIC statements.  */
1282
1283 void
1284 cgraph_build_static_cdtor (char which, tree body, int priority)
1285 {
1286   static int counter = 0;
1287   char which_buf[16];
1288   tree decl, name, resdecl;
1289
1290   sprintf (which_buf, "%c_%d", which, counter++);
1291   name = get_file_function_name_long (which_buf);
1292
1293   decl = build_decl (FUNCTION_DECL, name,
1294                      build_function_type (void_type_node, void_list_node));
1295   current_function_decl = decl;
1296
1297   resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1298   DECL_ARTIFICIAL (resdecl) = 1;
1299   DECL_IGNORED_P (resdecl) = 1;
1300   DECL_RESULT (decl) = resdecl;
1301
1302   allocate_struct_function (decl);
1303
1304   TREE_STATIC (decl) = 1;
1305   TREE_USED (decl) = 1;
1306   DECL_ARTIFICIAL (decl) = 1;
1307   DECL_IGNORED_P (decl) = 1;
1308   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1309   DECL_SAVED_TREE (decl) = body;
1310   TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1311   DECL_UNINLINABLE (decl) = 1;
1312
1313   DECL_INITIAL (decl) = make_node (BLOCK);
1314   TREE_USED (DECL_INITIAL (decl)) = 1;
1315
1316   DECL_SOURCE_LOCATION (decl) = input_location;
1317   cfun->function_end_locus = input_location;
1318
1319   switch (which)
1320     {
1321     case 'I':
1322       DECL_STATIC_CONSTRUCTOR (decl) = 1;
1323       break;
1324     case 'D':
1325       DECL_STATIC_DESTRUCTOR (decl) = 1;
1326       break;
1327     default:
1328       gcc_unreachable ();
1329     }
1330
1331   gimplify_function_tree (decl);
1332
1333   /* ??? We will get called LATE in the compilation process.  */
1334   if (cgraph_global_info_ready)
1335     {
1336       tree_lowering_passes (decl);
1337       tree_rest_of_compilation (decl);
1338     }
1339   else
1340     cgraph_finalize_function (decl, 0);
1341   
1342   if (targetm.have_ctors_dtors)
1343     {
1344       void (*fn) (rtx, int);
1345
1346       if (which == 'I')
1347         fn = targetm.asm_out.constructor;
1348       else
1349         fn = targetm.asm_out.destructor;
1350       fn (XEXP (DECL_RTL (decl), 0), priority);
1351     }
1352 }
1353
1354 void
1355 init_cgraph (void)
1356 {
1357   cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1358 }