OSDN Git Service

Fix numerous IA-64 C++ failures, IA-64 bootstrap trouble.
[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, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, 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      Inlining decision heuristics
142         ??? Move this to separate file after tree-ssa merge.
143
144         We separate inlining decisions from the inliner itself and store it
145         inside callgraph as so called inline plan.  Refer to cgraph.c
146         documentation about particular representation of inline plans in the
147         callgraph
148
149         The implementation of particular heuristics is separated from
150         the rest of code to make it easier to replace it with more complicated
151         implementation in the future.  The rest of inlining code acts as a
152         library aimed to modify the callgraph and verify that the parameters
153         on code size growth fits.
154
155         To mark given call inline, use cgraph_mark_inline function, the
156         verification is performed by cgraph_default_inline_p and
157         cgraph_check_inline_limits.
158
159         The heuristics implements simple knapsack style algorithm ordering
160         all functions by their "profitability" (estimated by code size growth)
161         and inlining them in priority order.
162
163         cgraph_decide_inlining implements heuristics taking whole callgraph
164         into account, while cgraph_decide_inlining_incrementally considers
165         only one function at a time and is used in non-unit-at-a-time mode.  */
166
167
168 #include "config.h"
169 #include "system.h"
170 #include "coretypes.h"
171 #include "tm.h"
172 #include "tree.h"
173 #include "rtl.h"
174 #include "tree-flow.h"
175 #include "tree-inline.h"
176 #include "langhooks.h"
177 #include "pointer-set.h"
178 #include "toplev.h"
179 #include "flags.h"
180 #include "ggc.h"
181 #include "debug.h"
182 #include "target.h"
183 #include "cgraph.h"
184 #include "diagnostic.h"
185 #include "timevar.h"
186 #include "params.h"
187 #include "fibheap.h"
188 #include "c-common.h"
189 #include "intl.h"
190 #include "function.h"
191 #include "tree-gimple.h"
192 #include "output.h"
193
194 #define INSNS_PER_CALL 10
195
196 static void cgraph_expand_all_functions (void);
197 static void cgraph_mark_functions_to_output (void);
198 static void cgraph_expand_function (struct cgraph_node *);
199 static tree record_call_1 (tree *, int *, void *);
200 static void cgraph_mark_local_functions (void);
201 static bool cgraph_default_inline_p (struct cgraph_node *n);
202 static void cgraph_analyze_function (struct cgraph_node *node);
203 static void cgraph_decide_inlining_incrementally (struct cgraph_node *);
204
205 /* Statistics we collect about inlining algorithm.  */
206 static int ncalls_inlined;
207 static int nfunctions_inlined;
208 static int initial_insns;
209 static int overall_insns;
210
211 /* Records tree nodes seen in cgraph_create_edges.  Simply using
212    walk_tree_without_duplicates doesn't guarantee each node is visited
213    once because it gets a new htab upon each recursive call from
214    record_calls_1.  */
215 static struct pointer_set_t *visited_nodes;
216
217 static FILE *cgraph_dump_file;
218
219 /* Determine if function DECL is needed.  That is, visible to something
220    either outside this translation unit, something magic in the system
221    configury, or (if not doing unit-at-a-time) to something we havn't
222    seen yet.  */
223
224 static bool
225 decide_is_function_needed (struct cgraph_node *node, tree decl)
226 {
227   tree origin;
228
229   /* If we decided it was needed before, but at the time we didn't have
230      the body of the function available, then it's still needed.  We have
231      to go back and re-check its dependencies now.  */
232   if (node->needed)
233     return true;
234
235   /* Externally visible functions must be output.  The exception is
236      COMDAT functions that must be output only when they are needed.  */
237   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
238     return true;
239
240   /* Constructors and destructors are reachable from the runtime by
241      some mechanism.  */
242   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
243     return true;
244
245   /* If the user told us it is used, then it must be so.  */
246   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
247     return true;
248
249   /* ??? If the assembler name is set by hand, it is possible to assemble
250      the name later after finalizing the function and the fact is noticed
251      in assemble_name then.  This is arguably a bug.  */
252   if (DECL_ASSEMBLER_NAME_SET_P (decl)
253       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
254     return true;
255
256   if (flag_unit_at_a_time)
257     return false;
258
259   /* If not doing unit at a time, then we'll only defer this function
260      if its marked for inlining.  Otherwise we want to emit it now.  */
261
262   /* "extern inline" functions are never output locally.  */
263   if (DECL_EXTERNAL (decl))
264     return false;
265   /* Nested functions of extern inline function shall not be emit unless
266      we inlined the origin.  */
267   for (origin = decl_function_context (decl); origin;
268        origin = decl_function_context (origin))
269     if (DECL_EXTERNAL (origin))
270       return false;
271   /* We want to emit COMDAT functions only when absolutely necessary.  */
272   if (DECL_COMDAT (decl))
273     return false;
274   if (!DECL_INLINE (decl)
275       || (!node->local.disregard_inline_limits
276           /* When declared inline, defer even the uninlinable functions.
277              This allows them to be eliminated when unused.  */
278           && !DECL_DECLARED_INLINE_P (decl) 
279           && (!node->local.inlinable || !cgraph_default_inline_p (node))))
280     return true;
281
282   return false;
283 }
284
285 /* Walk the decls we marked as necessary and see if they reference new
286    variables or functions and add them into the worklists.  */
287 static bool
288 cgraph_varpool_analyze_pending_decls (void)
289 {
290   bool changed = false;
291   timevar_push (TV_CGRAPH);
292
293   while (cgraph_varpool_first_unanalyzed_node)
294     {
295       tree decl = cgraph_varpool_first_unanalyzed_node->decl;
296
297       cgraph_varpool_first_unanalyzed_node->analyzed = true;
298
299       cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;
300
301       if (DECL_INITIAL (decl))
302         cgraph_create_edges (NULL, DECL_INITIAL (decl));
303       changed = true;
304     }
305   timevar_pop (TV_CGRAPH);
306   return changed;
307 }
308
309 /* Optimization of function bodies might've rendered some variables as
310    unnecessary so we want to avoid these from being compiled.
311
312    This is done by prunning the queue and keeping only the variables that
313    really appear needed (ie they are either externally visible or referenced
314    by compiled function). Re-doing the reachability analysis on variables
315    brings back the remaining variables referenced by these.  */
316 static void
317 cgraph_varpool_remove_unreferenced_decls (void)
318 {
319   struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;
320
321   cgraph_varpool_reset_queue ();
322
323   if (errorcount || sorrycount)
324     return;
325
326   while (node)
327     {
328       tree decl = node->decl;
329       next = node->next_needed;
330       node->needed = 0;
331
332       if (node->finalized
333           && ((DECL_ASSEMBLER_NAME_SET_P (decl)
334                && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
335               || node->force_output
336               || decide_is_variable_needed (node, decl)))
337         cgraph_varpool_mark_needed_node (node);
338
339       node = next;
340     }
341   cgraph_varpool_analyze_pending_decls ();
342 }
343
344
345 /* When not doing unit-at-a-time, output all functions enqueued.
346    Return true when such a functions were found.  */
347
348 bool
349 cgraph_assemble_pending_functions (void)
350 {
351   bool output = false;
352
353   if (flag_unit_at_a_time)
354     return false;
355
356   while (cgraph_nodes_queue)
357     {
358       struct cgraph_node *n = cgraph_nodes_queue;
359
360       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
361       n->next_needed = NULL;
362       if (!n->global.inlined_to
363           && !n->alias
364           && !DECL_EXTERNAL (n->decl))
365         {
366           cgraph_expand_function (n);
367           output = true;
368         }
369     }
370
371   return output;
372 }
373
374 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
375    logic in effect.  If NESTED is true, then our caller cannot stand to have
376    the garbage collector run at the moment.  We would need to either create
377    a new GC context, or just not compile right now.  */
378
379 void
380 cgraph_finalize_function (tree decl, bool nested)
381 {
382   struct cgraph_node *node = cgraph_node (decl);
383
384   if (node->local.finalized)
385     {
386       /* As an GCC extension we allow redefinition of the function.  The
387          semantics when both copies of bodies differ is not well defined.
388          We replace the old body with new body so in unit at a time mode
389          we always use new body, while in normal mode we may end up with
390          old body inlined into some functions and new body expanded and
391          inlined in others.
392          
393          ??? It may make more sense to use one body for inlining and other
394          body for expanding the function but this is difficult to do.  */
395
396       /* If node->output is set, then this is a unit-at-a-time compilation
397          and we have already begun whole-unit analysis.  This is *not*
398          testing for whether we've already emitted the function.  That
399          case can be sort-of legitimately seen with real function 
400          redefinition errors.  I would argue that the front end should
401          never present us with such a case, but don't enforce that for now.  */
402       gcc_assert (!node->output);
403
404       /* Reset our data structures so we can analyze the function again.  */
405       memset (&node->local, 0, sizeof (node->local));
406       memset (&node->global, 0, sizeof (node->global));
407       memset (&node->rtl, 0, sizeof (node->rtl));
408       node->analyzed = false;
409       node->local.redefined_extern_inline = true;
410
411       if (!flag_unit_at_a_time)
412         {
413           struct cgraph_node *n;
414
415           for (n = cgraph_nodes; n; n = n->next)
416             if (n->global.inlined_to == node)
417               cgraph_remove_node (n);
418         }
419
420       cgraph_node_remove_callees (node);
421
422       /* We may need to re-queue the node for assembling in case
423          we already proceeded it and ignored as not needed.  */
424       if (node->reachable && !flag_unit_at_a_time)
425         {
426           struct cgraph_node *n;
427
428           for (n = cgraph_nodes_queue; n; n = n->next_needed)
429             if (n == node)
430               break;
431           if (!n)
432             node->reachable = 0;
433         }
434     }
435
436   notice_global_symbol (decl);
437   node->decl = decl;
438   node->local.finalized = true;
439   if (node->nested)
440     lower_nested_functions (decl);
441   gcc_assert (!node->nested);
442
443   /* If not unit at a time, then we need to create the call graph
444      now, so that called functions can be queued and emitted now.  */
445   if (!flag_unit_at_a_time)
446     {
447       cgraph_analyze_function (node);
448       cgraph_decide_inlining_incrementally (node);
449     }
450
451   if (decide_is_function_needed (node, decl))
452     cgraph_mark_needed_node (node);
453
454   /* If not unit at a time, go ahead and emit everything we've found
455      to be reachable at this time.  */
456   if (!nested)
457     {
458       if (!cgraph_assemble_pending_functions ())
459         ggc_collect ();
460     }
461
462   /* If we've not yet emitted decl, tell the debug info about it.  */
463   if (!TREE_ASM_WRITTEN (decl))
464     (*debug_hooks->deferred_inline_function) (decl);
465
466   /* Possibly warn about unused parameters.  */
467   if (warn_unused_parameter)
468     do_warn_unused_parameter (decl);
469 }
470
471 /* Walk tree and record all calls.  Called via walk_tree.  */
472 static tree
473 record_call_1 (tree *tp, int *walk_subtrees, void *data)
474 {
475   tree t = *tp;
476
477   switch (TREE_CODE (t))
478     {
479     case VAR_DECL:
480       /* ??? Really, we should mark this decl as *potentially* referenced
481          by this function and re-examine whether the decl is actually used
482          after rtl has been generated.  */
483       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
484         {
485           cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
486           if (lang_hooks.callgraph.analyze_expr)
487             return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, 
488                                                       data);
489         }
490       break;
491
492     case FDESC_EXPR:
493     case ADDR_EXPR:
494       if (flag_unit_at_a_time)
495         {
496           /* Record dereferences to the functions.  This makes the
497              functions reachable unconditionally.  */
498           tree decl = TREE_OPERAND (*tp, 0);
499           if (TREE_CODE (decl) == FUNCTION_DECL)
500             cgraph_mark_needed_node (cgraph_node (decl));
501         }
502       break;
503
504     case CALL_EXPR:
505       {
506         tree decl = get_callee_fndecl (*tp);
507         if (decl && TREE_CODE (decl) == FUNCTION_DECL)
508           {
509             cgraph_create_edge (data, cgraph_node (decl), *tp);
510
511             /* When we see a function call, we don't want to look at the
512                function reference in the ADDR_EXPR that is hanging from
513                the CALL_EXPR we're examining here, because we would
514                conclude incorrectly that the function's address could be
515                taken by something that is not a function call.  So only
516                walk the function parameter list, skip the other subtrees.  */
517
518             walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
519                        visited_nodes);
520             *walk_subtrees = 0;
521           }
522         break;
523       }
524
525     default:
526       /* Save some cycles by not walking types and declaration as we
527          won't find anything useful there anyway.  */
528       if (IS_TYPE_OR_DECL_P (*tp))
529         {
530           *walk_subtrees = 0;
531           break;
532         }
533
534       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
535         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);
536       break;
537     }
538
539   return NULL;
540 }
541
542 /* Create cgraph edges for function calls inside BODY from NODE.  */
543
544 void
545 cgraph_create_edges (struct cgraph_node *node, tree body)
546 {
547   /* The nodes we're interested in are never shared, so walk
548      the tree ignoring duplicates.  */
549   visited_nodes = pointer_set_create ();
550   walk_tree (&body, record_call_1, node, visited_nodes);
551   pointer_set_destroy (visited_nodes);
552   visited_nodes = NULL;
553 }
554
555 static bool error_found;
556
557 /* Callback of verify_cgraph_node.  Check that all call_exprs have
558    cgraph nodes.  */
559
560 static tree
561 verify_cgraph_node_1 (tree *tp, int *walk_subtrees, void *data)
562 {
563   tree t = *tp;
564   tree decl;
565
566   if (TREE_CODE (t) == CALL_EXPR && (decl = get_callee_fndecl (t)))
567     {
568       struct cgraph_edge *e = cgraph_edge (data, t);
569       if (e)
570         {
571           if (e->aux)
572             {
573               error ("Shared call_expr:");
574               debug_tree (t);
575               error_found = true;
576             }
577           if (e->callee->decl != cgraph_node (decl)->decl)
578             {
579               error ("Edge points to wrong declaration:");
580               debug_tree (e->callee->decl);
581               fprintf (stderr," Instead of:");
582               debug_tree (decl);
583             }
584           e->aux = (void *)1;
585         }
586       else
587         {
588           error ("Missing callgraph edge for call expr:");
589           debug_tree (t);
590           error_found = true;
591         }
592     }
593
594   /* Save some cycles by not walking types and declaration as we
595      won't find anything useful there anyway.  */
596   if (IS_TYPE_OR_DECL_P (*tp))
597     *walk_subtrees = 0;
598
599   return NULL_TREE;
600 }
601
602 /* Verify cgraph nodes of given cgraph node.  */
603 void
604 verify_cgraph_node (struct cgraph_node *node)
605 {
606   struct cgraph_edge *e;
607   struct cgraph_node *main_clone;
608
609   timevar_push (TV_CGRAPH_VERIFY);
610   error_found = false;
611   for (e = node->callees; e; e = e->next_callee)
612     if (e->aux)
613       {
614         error ("Aux field set for edge %s->%s",
615                cgraph_node_name (e->caller), cgraph_node_name (e->callee));
616         error_found = true;
617       }
618   for (e = node->callers; e; e = e->next_caller)
619     {
620       if (!e->inline_failed)
621         {
622           if (node->global.inlined_to
623               != (e->caller->global.inlined_to
624                   ? e->caller->global.inlined_to : e->caller))
625             {
626               error ("Inlined_to pointer is wrong");
627               error_found = true;
628             }
629           if (node->callers->next_caller)
630             {
631               error ("Multiple inline callers");
632               error_found = true;
633             }
634         }
635       else
636         if (node->global.inlined_to)
637           {
638             error ("Inlined_to pointer set for noninline callers");
639             error_found = true;
640           }
641     }
642   if (!node->callers && node->global.inlined_to)
643     {
644       error ("Inlined_to pointer is set but no predecesors found");
645       error_found = true;
646     }
647   if (node->global.inlined_to == node)
648     {
649       error ("Inlined_to pointer reffers to itself");
650       error_found = true;
651     }
652
653   for (main_clone = cgraph_node (node->decl); main_clone;
654        main_clone = main_clone->next_clone)
655     if (main_clone == node)
656       break;
657   if (!node)
658     {
659       error ("Node not found in DECL_ASSEMBLER_NAME hash");
660       error_found = true;
661     }
662   
663   if (node->analyzed
664       && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
665       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
666     {
667       walk_tree_without_duplicates (&DECL_SAVED_TREE (node->decl),
668                                     verify_cgraph_node_1, node);
669       for (e = node->callees; e; e = e->next_callee)
670         {
671           if (!e->aux)
672             {
673               error ("Edge %s->%s has no corresponding call_expr",
674                      cgraph_node_name (e->caller),
675                      cgraph_node_name (e->callee));
676               error_found = true;
677             }
678           e->aux = 0;
679         }
680     }
681   if (error_found)
682     {
683       dump_cgraph_node (stderr, node);
684       internal_error ("verify_cgraph_node failed.");
685     }
686   timevar_pop (TV_CGRAPH_VERIFY);
687 }
688
689 /* Verify whole cgraph structure.  */
690 void
691 verify_cgraph (void)
692 {
693   struct cgraph_node *node;
694
695   if (sorrycount || errorcount)
696     return;
697
698   for (node = cgraph_nodes; node; node = node->next)
699     verify_cgraph_node (node);
700 }
701
702
703 /* Output all variables enqueued to be assembled.  */
704 bool
705 cgraph_varpool_assemble_pending_decls (void)
706 {
707   bool changed = false;
708
709   if (errorcount || sorrycount)
710     return false;
711  
712   /* EH might mark decls as needed during expansion.  This should be safe since
713      we don't create references to new function, but it should not be used
714      elsewhere.  */
715   cgraph_varpool_analyze_pending_decls ();
716
717   while (cgraph_varpool_nodes_queue)
718     {
719       tree decl = cgraph_varpool_nodes_queue->decl;
720       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
721
722       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
723       if (!TREE_ASM_WRITTEN (decl) && !node->alias && !DECL_EXTERNAL (decl))
724         {
725           assemble_variable (decl, 0, 1, 0);
726           changed = true;
727         }
728       node->next_needed = NULL;
729     }
730   return changed;
731 }
732
733 /* Analyze the function scheduled to be output.  */
734 static void
735 cgraph_analyze_function (struct cgraph_node *node)
736 {
737   tree decl = node->decl;
738   struct cgraph_edge *e;
739
740   current_function_decl = decl;
741
742   /* First kill forward declaration so reverse inlining works properly.  */
743   cgraph_create_edges (node, DECL_SAVED_TREE (decl));
744
745   node->local.inlinable = tree_inlinable_function_p (decl);
746   node->local.self_insns = estimate_num_insns (DECL_SAVED_TREE (decl));
747   if (node->local.inlinable)
748     node->local.disregard_inline_limits
749       = lang_hooks.tree_inlining.disregard_inline_limits (decl);
750   for (e = node->callers; e; e = e->next_caller)
751     {
752       if (node->local.redefined_extern_inline)
753         e->inline_failed = N_("redefined extern inline functions are not "
754                            "considered for inlining");
755       else if (!node->local.inlinable)
756         e->inline_failed = N_("function not inlinable");
757       else
758         e->inline_failed = N_("function not considered for inlining");
759     }
760   if (flag_really_no_inline && !node->local.disregard_inline_limits)
761     node->local.inlinable = 0;
762   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
763   node->global.insns = node->local.self_insns;
764
765   node->analyzed = true;
766   current_function_decl = NULL;
767 }
768
769 /* Analyze the whole compilation unit once it is parsed completely.  */
770
771 void
772 cgraph_finalize_compilation_unit (void)
773 {
774   struct cgraph_node *node;
775   /* Keep track of already processed nodes when called multiple times for
776      intermodule optimization.  */
777   static struct cgraph_node *first_analyzed;
778
779   finish_aliases_1 ();
780
781   if (!flag_unit_at_a_time)
782     {
783       cgraph_assemble_pending_functions ();
784       return;
785     }
786
787   if (!quiet_flag)
788     {
789       fprintf (stderr, "\nAnalyzing compilation unit");
790       fflush (stderr);
791     }
792
793   timevar_push (TV_CGRAPH);
794   cgraph_varpool_analyze_pending_decls ();
795   if (cgraph_dump_file)
796     {
797       fprintf (cgraph_dump_file, "Initial entry points:");
798       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
799         if (node->needed && DECL_SAVED_TREE (node->decl))
800           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
801       fprintf (cgraph_dump_file, "\n");
802     }
803
804   /* Propagate reachability flag and lower representation of all reachable
805      functions.  In the future, lowering will introduce new functions and
806      new entry points on the way (by template instantiation and virtual
807      method table generation for instance).  */
808   while (cgraph_nodes_queue)
809     {
810       struct cgraph_edge *edge;
811       tree decl = cgraph_nodes_queue->decl;
812
813       node = cgraph_nodes_queue;
814       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
815       node->next_needed = NULL;
816
817       /* ??? It is possible to create extern inline function and later using
818          weak alas attribute to kill its body. See
819          gcc.c-torture/compile/20011119-1.c  */
820       if (!DECL_SAVED_TREE (decl))
821         continue;
822
823       gcc_assert (!node->analyzed && node->reachable);
824       gcc_assert (DECL_SAVED_TREE (decl));
825
826       cgraph_analyze_function (node);
827
828       for (edge = node->callees; edge; edge = edge->next_callee)
829         if (!edge->callee->reachable)
830           cgraph_mark_reachable_node (edge->callee);
831
832       cgraph_varpool_analyze_pending_decls ();
833     }
834
835   /* Collect entry points to the unit.  */
836
837   if (cgraph_dump_file)
838     {
839       fprintf (cgraph_dump_file, "Unit entry points:");
840       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
841         if (node->needed && DECL_SAVED_TREE (node->decl))
842           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
843       fprintf (cgraph_dump_file, "\n\nInitial ");
844       dump_cgraph (cgraph_dump_file);
845     }
846
847   if (cgraph_dump_file)
848     fprintf (cgraph_dump_file, "\nReclaiming functions:");
849
850   for (node = cgraph_nodes; node != first_analyzed; node = node->next)
851     {
852       tree decl = node->decl;
853
854       if (!node->reachable && DECL_SAVED_TREE (decl))
855         {
856           if (cgraph_dump_file)
857             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
858           cgraph_remove_node (node);
859         }
860       else
861         node->next_needed = NULL;
862     }
863   if (cgraph_dump_file)
864     {
865       fprintf (cgraph_dump_file, "\n\nReclaimed ");
866       dump_cgraph (cgraph_dump_file);
867     }
868   first_analyzed = cgraph_nodes;
869   ggc_collect ();
870   timevar_pop (TV_CGRAPH);
871 }
872 /* Figure out what functions we want to assemble.  */
873
874 static void
875 cgraph_mark_functions_to_output (void)
876 {
877   struct cgraph_node *node;
878
879   for (node = cgraph_nodes; node; node = node->next)
880     {
881       tree decl = node->decl;
882       struct cgraph_edge *e;
883       
884       gcc_assert (!node->output);
885
886       for (e = node->callers; e; e = e->next_caller)
887         if (e->inline_failed)
888           break;
889
890       /* We need to output all local functions that are used and not
891          always inlined, as well as those that are reachable from
892          outside the current compilation unit.  */
893       if (DECL_SAVED_TREE (decl)
894           && !node->global.inlined_to
895           && (node->needed
896               || (e && node->reachable))
897           && !TREE_ASM_WRITTEN (decl)
898           && !DECL_EXTERNAL (decl))
899         node->output = 1;
900       else
901         {
902           /* We should've reclaimed all functions that are not needed.  */
903 #ifdef ENABLE_CHECKING
904           if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
905               && !DECL_EXTERNAL (decl))
906             {
907               dump_cgraph_node (stderr, node);
908               internal_error ("failed to reclaim unneeded function");
909             }
910 #endif
911           gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
912                       || DECL_EXTERNAL (decl));
913
914         }
915       
916     }
917 }
918
919 /* Expand function specified by NODE.  */
920
921 static void
922 cgraph_expand_function (struct cgraph_node *node)
923 {
924   tree decl = node->decl;
925
926   /* We ought to not compile any inline clones.  */
927   gcc_assert (!node->global.inlined_to);
928
929   if (flag_unit_at_a_time)
930     announce_function (decl);
931
932   /* Generate RTL for the body of DECL.  */
933   lang_hooks.callgraph.expand_function (decl);
934
935   /* Make sure that BE didn't give up on compiling.  */
936   /* ??? Can happen with nested function of extern inline.  */
937   gcc_assert (TREE_ASM_WRITTEN (node->decl));
938
939   current_function_decl = NULL;
940   if (!cgraph_preserve_function_body_p (node->decl))
941     {
942       DECL_SAVED_TREE (node->decl) = NULL;
943       DECL_STRUCT_FUNCTION (node->decl) = NULL;
944       DECL_INITIAL (node->decl) = error_mark_node;
945       /* Eliminate all call edges.  This is important so the call_expr no longer
946          points to the dead function body.  */
947       cgraph_node_remove_callees (node);
948     }
949 }
950
951 /* Fill array order with all nodes with output flag set in the reverse
952    topological order.  */
953
954 static int
955 cgraph_postorder (struct cgraph_node **order)
956 {
957   struct cgraph_node *node, *node2;
958   int stack_size = 0;
959   int order_pos = 0;
960   struct cgraph_edge *edge, last;
961
962   struct cgraph_node **stack =
963     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
964
965   /* We have to deal with cycles nicely, so use a depth first traversal
966      output algorithm.  Ignore the fact that some functions won't need
967      to be output and put them into order as well, so we get dependencies
968      right through intline functions.  */
969   for (node = cgraph_nodes; node; node = node->next)
970     node->aux = NULL;
971   for (node = cgraph_nodes; node; node = node->next)
972     if (!node->aux)
973       {
974         node2 = node;
975         if (!node->callers)
976           node->aux = &last;
977         else
978           node->aux = node->callers;
979         while (node2)
980           {
981             while (node2->aux != &last)
982               {
983                 edge = node2->aux;
984                 if (edge->next_caller)
985                   node2->aux = edge->next_caller;
986                 else
987                   node2->aux = &last;
988                 if (!edge->caller->aux)
989                   {
990                     if (!edge->caller->callers)
991                       edge->caller->aux = &last;
992                     else
993                       edge->caller->aux = edge->caller->callers;
994                     stack[stack_size++] = node2;
995                     node2 = edge->caller;
996                     break;
997                   }
998               }
999             if (node2->aux == &last)
1000               {
1001                 order[order_pos++] = node2;
1002                 if (stack_size)
1003                   node2 = stack[--stack_size];
1004                 else
1005                   node2 = NULL;
1006               }
1007           }
1008       }
1009   free (stack);
1010   return order_pos;
1011 }
1012
1013
1014 /* Perform reachability analysis and reclaim all unreachable nodes.
1015    This function also remove unneeded bodies of extern inline functions
1016    and thus needs to be done only after inlining decisions has been made.  */
1017 static bool
1018 cgraph_remove_unreachable_nodes (void)
1019 {
1020   struct cgraph_node *first = (void *) 1;
1021   struct cgraph_node *node;
1022   bool changed = false;
1023   int insns = 0;
1024
1025 #ifdef ENABLE_CHECKING
1026   verify_cgraph ();
1027 #endif
1028   if (cgraph_dump_file)
1029     fprintf (cgraph_dump_file, "\nReclaiming functions:");
1030 #ifdef ENABLE_CHECKING
1031   for (node = cgraph_nodes; node; node = node->next)
1032     gcc_assert (!node->aux);
1033 #endif
1034   for (node = cgraph_nodes; node; node = node->next)
1035     if (node->needed && !node->global.inlined_to
1036         && (!DECL_EXTERNAL (node->decl) || !node->analyzed))
1037       {
1038         node->aux = first;
1039         first = node;
1040       }
1041     else
1042       gcc_assert (!node->aux);
1043
1044   /* Perform reachability analysis.  As a special case do not consider
1045      extern inline functions not inlined as live because we won't output
1046      them at all.  */
1047   while (first != (void *) 1)
1048     {
1049       struct cgraph_edge *e;
1050       node = first;
1051       first = first->aux;
1052
1053       for (e = node->callees; e; e = e->next_callee)
1054         if (!e->callee->aux
1055             && node->analyzed
1056             && (!e->inline_failed || !e->callee->analyzed
1057                 || !DECL_EXTERNAL (e->callee->decl)))
1058           {
1059             e->callee->aux = first;
1060             first = e->callee;
1061           }
1062     }
1063
1064   /* Remove unreachable nodes.  Extern inline functions need special care;
1065      Unreachable extern inline functions shall be removed.
1066      Reachable extern inline functions we never inlined shall get their bodies
1067      eliminated.
1068      Reachable extern inline functions we sometimes inlined will be turned into
1069      unanalyzed nodes so they look like for true extern functions to the rest
1070      of code.  Body of such functions is released via remove_node once the
1071      inline clones are eliminated.  */
1072   for (node = cgraph_nodes; node; node = node->next)
1073     {
1074       if (!node->aux)
1075         {
1076           int local_insns;
1077           tree decl = node->decl;
1078
1079           node->global.inlined_to = NULL;
1080           if (DECL_STRUCT_FUNCTION (decl))
1081             local_insns = node->local.self_insns;
1082           else
1083             local_insns = 0;
1084           if (cgraph_dump_file)
1085             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1086           if (!node->analyzed || !DECL_EXTERNAL (node->decl))
1087             cgraph_remove_node (node);
1088           else
1089             {
1090               struct cgraph_edge *e;
1091
1092               for (e = node->callers; e; e = e->next_caller)
1093                 if (e->caller->aux)
1094                   break;
1095               if (e || node->needed)
1096                 {
1097                   struct cgraph_node *clone;
1098
1099                   for (clone = node->next_clone; clone;
1100                        clone = clone->next_clone)
1101                     if (clone->aux)
1102                       break;
1103                   if (!clone)
1104                     {
1105                       DECL_SAVED_TREE (node->decl) = NULL;
1106                       DECL_STRUCT_FUNCTION (node->decl) = NULL;
1107                       DECL_INITIAL (node->decl) = error_mark_node;
1108                     }
1109                   cgraph_node_remove_callees (node);
1110                   node->analyzed = false;
1111                 }
1112               else
1113                 cgraph_remove_node (node);
1114             }
1115           if (!DECL_SAVED_TREE (decl))
1116             insns += local_insns;
1117           changed = true;
1118         }
1119     }
1120   for (node = cgraph_nodes; node; node = node->next)
1121     node->aux = NULL;
1122   if (cgraph_dump_file)
1123     fprintf (cgraph_dump_file, "\nReclaimed %i insns", insns);
1124   return changed;
1125 }
1126
1127 /* Estimate size of the function after inlining WHAT into TO.  */
1128
1129 static int
1130 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
1131                                      struct cgraph_node *what)
1132 {
1133   tree fndecl = what->decl;
1134   tree arg;
1135   int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
1136   for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
1137     call_insns += estimate_move_cost (TREE_TYPE (arg));
1138   return (what->global.insns - call_insns) * times + to->global.insns;
1139 }
1140
1141 /* Estimate the growth caused by inlining NODE into all callees.  */
1142
1143 static int
1144 cgraph_estimate_growth (struct cgraph_node *node)
1145 {
1146   int growth = 0;
1147   struct cgraph_edge *e;
1148
1149   for (e = node->callers; e; e = e->next_caller)
1150     if (e->inline_failed)
1151       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
1152                  - e->caller->global.insns);
1153
1154   /* ??? Wrong for self recursive functions or cases where we decide to not
1155      inline for different reasons, but it is not big deal as in that case
1156      we will keep the body around, but we will also avoid some inlining.  */
1157   if (!node->needed && !DECL_EXTERNAL (node->decl))
1158     growth -= node->global.insns;
1159
1160   return growth;
1161 }
1162
1163 /* E is expected to be an edge being inlined.  Clone destination node of
1164    the edge and redirect it to the new clone.
1165    DUPLICATE is used for bookkeeping on whether we are actually creating new
1166    clones or re-using node originally representing out-of-line function call.
1167    */
1168 void
1169 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
1170 {
1171   struct cgraph_node *n;
1172
1173   /* We may eliminate the need for out-of-line copy to be output.  In that
1174      case just go ahead and re-use it.  */
1175   if (!e->callee->callers->next_caller
1176       && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
1177       && duplicate
1178       && flag_unit_at_a_time)
1179     {
1180       gcc_assert (!e->callee->global.inlined_to);
1181       if (!DECL_EXTERNAL (e->callee->decl))
1182         overall_insns -= e->callee->global.insns, nfunctions_inlined++;
1183       duplicate = 0;
1184     }
1185    else if (duplicate)
1186     {
1187       n = cgraph_clone_node (e->callee);
1188       cgraph_redirect_edge_callee (e, n);
1189     }
1190
1191   if (e->caller->global.inlined_to)
1192     e->callee->global.inlined_to = e->caller->global.inlined_to;
1193   else
1194     e->callee->global.inlined_to = e->caller;
1195
1196   /* Recursively clone all bodies.  */
1197   for (e = e->callee->callees; e; e = e->next_callee)
1198     if (!e->inline_failed)
1199       cgraph_clone_inlined_nodes (e, duplicate);
1200 }
1201
1202 /* Mark edge E as inlined and update callgraph accordingly.  */
1203
1204 void
1205 cgraph_mark_inline_edge (struct cgraph_edge *e)
1206 {
1207   int old_insns = 0, new_insns = 0;
1208   struct cgraph_node *to = NULL, *what;
1209
1210   gcc_assert (e->inline_failed);
1211   e->inline_failed = NULL;
1212
1213   if (!e->callee->global.inlined && flag_unit_at_a_time)
1214     DECL_POSSIBLY_INLINED (e->callee->decl) = true;
1215   e->callee->global.inlined = true;
1216
1217   cgraph_clone_inlined_nodes (e, true);
1218
1219   what = e->callee;
1220
1221   /* Now update size of caller and all functions caller is inlined into.  */
1222   for (;e && !e->inline_failed; e = e->caller->callers)
1223     {
1224       old_insns = e->caller->global.insns;
1225       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
1226                                                        what);
1227       gcc_assert (new_insns >= 0);
1228       to = e->caller;
1229       to->global.insns = new_insns;
1230     }
1231   gcc_assert (what->global.inlined_to == to);
1232   if (new_insns > old_insns)
1233     overall_insns += new_insns - old_insns;
1234   ncalls_inlined++;
1235 }
1236
1237 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
1238    Return following unredirected edge in the list of callers
1239    of EDGE->CALLEE  */
1240
1241 static struct cgraph_edge *
1242 cgraph_mark_inline (struct cgraph_edge *edge)
1243 {
1244   struct cgraph_node *to = edge->caller;
1245   struct cgraph_node *what = edge->callee;
1246   struct cgraph_edge *e, *next;
1247   int times = 0;
1248
1249   /* Look for all calls, mark them inline and clone recursively
1250      all inlined functions.  */
1251   for (e = what->callers; e; e = next)
1252     {
1253       next = e->next_caller;
1254       if (e->caller == to && e->inline_failed)
1255         {
1256           cgraph_mark_inline_edge (e);
1257           if (e == edge)
1258             edge = next;
1259           times++;
1260         }
1261     }
1262   gcc_assert (times);
1263   return edge;
1264 }
1265
1266 /* Return false when inlining WHAT into TO is not good idea
1267    as it would cause too large growth of function bodies.  */
1268
1269 static bool
1270 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
1271                             const char **reason)
1272 {
1273   int times = 0;
1274   struct cgraph_edge *e;
1275   int newsize;
1276   int limit;
1277
1278   if (to->global.inlined_to)
1279     to = to->global.inlined_to;
1280
1281   for (e = to->callees; e; e = e->next_callee)
1282     if (e->callee == what)
1283       times++;
1284
1285   /* When inlining large function body called once into small function,
1286      take the inlined function as base for limiting the growth.  */
1287   if (to->local.self_insns > what->local.self_insns)
1288     limit = to->local.self_insns;
1289   else
1290     limit = what->local.self_insns;
1291
1292   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
1293
1294   newsize = cgraph_estimate_size_after_inlining (times, to, what);
1295   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
1296       && newsize > limit)
1297     {
1298       if (reason)
1299         *reason = N_("--param large-function-growth limit reached");
1300       return false;
1301     }
1302   return true;
1303 }
1304
1305 /* Return true when function N is small enough to be inlined.  */
1306
1307 static bool
1308 cgraph_default_inline_p (struct cgraph_node *n)
1309 {
1310   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
1311     return false;
1312   if (DECL_DECLARED_INLINE_P (n->decl))
1313     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
1314   else
1315     return n->global.insns < MAX_INLINE_INSNS_AUTO;
1316 }
1317
1318 /* Return true when inlining WHAT would create recursive inlining.
1319    We call recursive inlining all cases where same function appears more than
1320    once in the single recursion nest path in the inline graph.  */
1321
1322 static bool
1323 cgraph_recursive_inlining_p (struct cgraph_node *to,
1324                              struct cgraph_node *what,
1325                              const char **reason)
1326 {
1327   bool recursive;
1328   if (to->global.inlined_to)
1329     recursive = what->decl == to->global.inlined_to->decl;
1330   else
1331     recursive = what->decl == to->decl;
1332   /* Marking recursive function inline has sane semantic and thus we should
1333      not warn on it.  */
1334   if (recursive && reason)
1335     *reason = (what->local.disregard_inline_limits
1336                ? N_("recursive inlining") : "");
1337   return recursive;
1338 }
1339
1340 /* Recompute heap nodes for each of callees.  */
1341 static void
1342 update_callee_keys (fibheap_t heap, struct fibnode **heap_node,
1343                     struct cgraph_node *node)
1344 {
1345   struct cgraph_edge *e;
1346
1347   for (e = node->callees; e; e = e->next_callee)
1348     if (e->inline_failed && heap_node[e->callee->uid])
1349       fibheap_replace_key (heap, heap_node[e->callee->uid],
1350                            cgraph_estimate_growth (e->callee));
1351     else if (!e->inline_failed)
1352       update_callee_keys (heap, heap_node, e->callee);
1353 }
1354
1355 /* Enqueue all recursive calls from NODE into queue linked via aux pointers
1356    in between FIRST and LAST.  WHERE is used for bookkeeping while looking
1357    int calls inlined within NODE.  */
1358 static void
1359 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
1360                         struct cgraph_edge **first, struct cgraph_edge **last)
1361 {
1362   struct cgraph_edge *e;
1363   for (e = where->callees; e; e = e->next_callee)
1364     if (e->callee == node)
1365       {
1366         if (!*first)
1367           *first = e;
1368         else
1369           (*last)->aux = e;
1370         *last = e;
1371       }
1372   for (e = where->callees; e; e = e->next_callee)
1373     if (!e->inline_failed)
1374       lookup_recursive_calls (node, e->callee, first, last);
1375 }
1376
1377 /* Decide on recursive inlining: in the case function has recursive calls,
1378    inline until body size reaches given argument.  */
1379 static void
1380 cgraph_decide_recursive_inlining (struct cgraph_node *node)
1381 {
1382   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
1383   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
1384   struct cgraph_edge *first_call = NULL, *last_call = NULL;
1385   struct cgraph_edge *last_in_current_depth;
1386   struct cgraph_edge *e;
1387   struct cgraph_node *master_clone;
1388   int depth = 0;
1389   int n = 0;
1390
1391   if (DECL_DECLARED_INLINE_P (node->decl))
1392     {
1393       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
1394       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
1395     }
1396
1397   /* Make sure that function is small enough to be considered for inlining.  */
1398   if (!max_depth
1399       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
1400     return;
1401   lookup_recursive_calls (node, node, &first_call, &last_call);
1402   if (!first_call)
1403     return;
1404
1405   if (cgraph_dump_file)
1406     fprintf (cgraph_dump_file, 
1407              "\nPerforming recursive inlining on %s\n",
1408              cgraph_node_name (node));
1409
1410   /* We need original clone to copy around.  */
1411   master_clone = cgraph_clone_node (node);
1412   master_clone->needed = true;
1413   for (e = master_clone->callees; e; e = e->next_callee)
1414     if (!e->inline_failed)
1415       cgraph_clone_inlined_nodes (e, true);
1416
1417   /* Do the inlining and update list of recursive call during process.  */
1418   last_in_current_depth = last_call;
1419   while (first_call
1420          && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
1421     {
1422       struct cgraph_edge *curr = first_call;
1423
1424       first_call = first_call->aux;
1425       curr->aux = NULL;
1426
1427       cgraph_redirect_edge_callee (curr, master_clone);
1428       cgraph_mark_inline_edge (curr);
1429       lookup_recursive_calls (node, curr->callee, &first_call, &last_call);
1430
1431       if (last_in_current_depth
1432           && ++depth >= max_depth)
1433         break;
1434       n++;
1435     }
1436
1437   /* Cleanup queue pointers.  */
1438   while (first_call)
1439     {
1440       struct cgraph_edge *next = first_call->aux;
1441       first_call->aux = NULL;
1442       first_call = next;
1443     }
1444   if (cgraph_dump_file)
1445     fprintf (cgraph_dump_file, 
1446              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
1447              master_clone->global.insns, node->global.insns);
1448
1449   /* Remove master clone we used for inlining.  We rely that clones inlined
1450      into master clone gets queued just before master clone so we don't
1451      need recursion.  */
1452   for (node = cgraph_nodes; node != master_clone;
1453        node = node->next)
1454     if (node->global.inlined_to == master_clone)
1455       cgraph_remove_node (node);
1456   cgraph_remove_node (master_clone);
1457 }
1458
1459 /* Set inline_failed for all callers of given function to REASON.  */
1460
1461 static void
1462 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
1463 {
1464   struct cgraph_edge *e;
1465
1466   if (cgraph_dump_file)
1467     fprintf (cgraph_dump_file, "Inlining failed: %s\n", reason);
1468   for (e = node->callers; e; e = e->next_caller)
1469     if (e->inline_failed)
1470       e->inline_failed = reason;
1471 }
1472
1473 /* We use greedy algorithm for inlining of small functions:
1474    All inline candidates are put into prioritized heap based on estimated
1475    growth of the overall number of instructions and then update the estimates.
1476
1477    INLINED and INLINED_CALEES are just pointers to arrays large enough
1478    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
1479
1480 static void
1481 cgraph_decide_inlining_of_small_functions (void)
1482 {
1483   struct cgraph_node *node;
1484   fibheap_t heap = fibheap_new ();
1485   struct fibnode **heap_node =
1486     xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
1487   int max_insns = ((HOST_WIDEST_INT) initial_insns
1488                    * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1489
1490   /* Put all inline candidates into the heap.  */
1491
1492   for (node = cgraph_nodes; node; node = node->next)
1493     {
1494       if (!node->local.inlinable || !node->callers
1495           || node->local.disregard_inline_limits)
1496         continue;
1497
1498       if (!cgraph_default_inline_p (node))
1499         {
1500           cgraph_set_inline_failed (node,
1501             N_("--param max-inline-insns-single limit reached"));
1502           continue;
1503         }
1504       heap_node[node->uid] =
1505         fibheap_insert (heap, cgraph_estimate_growth (node), node);
1506     }
1507
1508   if (cgraph_dump_file)
1509     fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
1510   while (overall_insns <= max_insns && (node = fibheap_extract_min (heap)))
1511     {
1512       struct cgraph_edge *e, *next;
1513       int old_insns = overall_insns;
1514
1515       heap_node[node->uid] = NULL;
1516       if (cgraph_dump_file)
1517         fprintf (cgraph_dump_file, 
1518                  "\nConsidering %s with %i insns\n"
1519                  " Estimated growth is %+i insns.\n",
1520                  cgraph_node_name (node), node->global.insns,
1521                  cgraph_estimate_growth (node));
1522       if (!cgraph_default_inline_p (node))
1523         {
1524           cgraph_set_inline_failed (node,
1525             N_("--param max-inline-insns-single limit reached after inlining into the callee"));
1526           continue;
1527         }
1528       for (e = node->callers; e; e = next)
1529         {
1530           next = e->next_caller;
1531           if (e->inline_failed)
1532             {
1533               struct cgraph_node *where;
1534
1535               if (cgraph_recursive_inlining_p (e->caller, e->callee,
1536                                                &e->inline_failed)
1537                   || !cgraph_check_inline_limits (e->caller, e->callee,
1538                                                   &e->inline_failed))
1539                 {
1540                   if (cgraph_dump_file)
1541                     fprintf (cgraph_dump_file, " Not inlining into %s:%s.\n",
1542                              cgraph_node_name (e->caller), e->inline_failed);
1543                   continue;
1544                 }
1545               next = cgraph_mark_inline (e);
1546               where = e->caller;
1547               if (where->global.inlined_to)
1548                 where = where->global.inlined_to;
1549
1550               if (heap_node[where->uid])
1551                 fibheap_replace_key (heap, heap_node[where->uid],
1552                                      cgraph_estimate_growth (where));
1553
1554               if (cgraph_dump_file)
1555                 fprintf (cgraph_dump_file, 
1556                          " Inlined into %s which now has %i insns.\n",
1557                          cgraph_node_name (e->caller),
1558                          e->caller->global.insns);
1559             }
1560         }
1561
1562       cgraph_decide_recursive_inlining (node);
1563
1564       /* Similarly all functions called by the function we just inlined
1565          are now called more times; update keys.  */
1566       update_callee_keys (heap, heap_node, node);
1567
1568       if (cgraph_dump_file)
1569         fprintf (cgraph_dump_file, 
1570                  " Inlined for a net change of %+i insns.\n",
1571                  overall_insns - old_insns);
1572     }
1573   while ((node = fibheap_extract_min (heap)) != NULL)
1574     if (!node->local.disregard_inline_limits)
1575       cgraph_set_inline_failed (node, N_("--param inline-unit-growth limit reached"));
1576   fibheap_delete (heap);
1577   free (heap_node);
1578 }
1579
1580 /* Decide on the inlining.  We do so in the topological order to avoid
1581    expenses on updating data structures.  */
1582
1583 static void
1584 cgraph_decide_inlining (void)
1585 {
1586   struct cgraph_node *node;
1587   int nnodes;
1588   struct cgraph_node **order =
1589     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1590   int old_insns = 0;
1591   int i;
1592
1593   for (node = cgraph_nodes; node; node = node->next)
1594     initial_insns += node->local.self_insns;
1595   overall_insns = initial_insns;
1596
1597   nnodes = cgraph_postorder (order);
1598
1599   if (cgraph_dump_file)
1600     fprintf (cgraph_dump_file,
1601              "\nDeciding on inlining.  Starting with %i insns.\n",
1602              initial_insns);
1603
1604   for (node = cgraph_nodes; node; node = node->next)
1605     node->aux = 0;
1606
1607   if (cgraph_dump_file)
1608     fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
1609
1610   /* In the first pass mark all always_inline edges.  Do this with a priority
1611      so none of our later choices will make this impossible.  */
1612   for (i = nnodes - 1; i >= 0; i--)
1613     {
1614       struct cgraph_edge *e, *next;
1615
1616       node = order[i];
1617
1618       if (!node->local.disregard_inline_limits)
1619         continue;
1620       if (cgraph_dump_file)
1621         fprintf (cgraph_dump_file,
1622                  "\nConsidering %s %i insns (always inline)\n",
1623                  cgraph_node_name (node), node->global.insns);
1624       old_insns = overall_insns;
1625       for (e = node->callers; e; e = next)
1626         {
1627           next = e->next_caller;
1628           if (!e->inline_failed)
1629             continue;
1630           if (cgraph_recursive_inlining_p (e->caller, e->callee,
1631                                            &e->inline_failed))
1632             continue;
1633           cgraph_mark_inline_edge (e);
1634           if (cgraph_dump_file)
1635             fprintf (cgraph_dump_file, 
1636                      " Inlined into %s which now has %i insns.\n",
1637                      cgraph_node_name (e->caller),
1638                      e->caller->global.insns);
1639         }
1640       if (cgraph_dump_file)
1641         fprintf (cgraph_dump_file, 
1642                  " Inlined for a net change of %+i insns.\n",
1643                  overall_insns - old_insns);
1644     }
1645
1646   if (!flag_really_no_inline)
1647     {
1648       cgraph_decide_inlining_of_small_functions ();
1649
1650       if (cgraph_dump_file)
1651         fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
1652
1653       /* And finally decide what functions are called once.  */
1654
1655       for (i = nnodes - 1; i >= 0; i--)
1656         {
1657           node = order[i];
1658
1659           if (node->callers && !node->callers->next_caller && !node->needed
1660               && node->local.inlinable && node->callers->inline_failed
1661               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1662             {
1663               bool ok = true;
1664               struct cgraph_node *node1;
1665
1666               /* Verify that we won't duplicate the caller.  */
1667               for (node1 = node->callers->caller;
1668                    node1->callers && !node1->callers->inline_failed
1669                    && ok; node1 = node1->callers->caller)
1670                 if (node1->callers->next_caller || node1->needed)
1671                   ok = false;
1672               if (ok)
1673                 {
1674                   if (cgraph_dump_file)
1675                     fprintf (cgraph_dump_file,
1676                              "\nConsidering %s %i insns.\n"
1677                              " Called once from %s %i insns.\n",
1678                              cgraph_node_name (node), node->global.insns,
1679                              cgraph_node_name (node->callers->caller),
1680                              node->callers->caller->global.insns);
1681
1682                   old_insns = overall_insns;
1683
1684                   if (cgraph_check_inline_limits (node->callers->caller, node,
1685                                                   NULL))
1686                     {
1687                       cgraph_mark_inline (node->callers);
1688                       if (cgraph_dump_file)
1689                         fprintf (cgraph_dump_file,
1690                                  " Inlined into %s which now has %i insns"
1691                                  " for a net change of %+i insns.\n",
1692                                  cgraph_node_name (node->callers->caller),
1693                                  node->callers->caller->global.insns,
1694                                  overall_insns - old_insns);
1695                     }
1696                   else
1697                     {
1698                       if (cgraph_dump_file)
1699                         fprintf (cgraph_dump_file,
1700                                  " Inline limit reached, not inlined.\n");
1701                     }
1702                 }
1703             }
1704         }
1705     }
1706
1707   /* We will never output extern functions we didn't inline. 
1708      ??? Perhaps we can prevent accounting of growth of external
1709      inline functions.  */
1710   cgraph_remove_unreachable_nodes ();
1711
1712   if (cgraph_dump_file)
1713     fprintf (cgraph_dump_file,
1714              "\nInlined %i calls, eliminated %i functions, "
1715              "%i insns turned to %i insns.\n\n",
1716              ncalls_inlined, nfunctions_inlined, initial_insns,
1717              overall_insns);
1718   free (order);
1719 }
1720
1721 /* Decide on the inlining.  We do so in the topological order to avoid
1722    expenses on updating data structures.  */
1723
1724 static void
1725 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
1726 {
1727   struct cgraph_edge *e;
1728
1729   /* First of all look for always inline functions.  */
1730   for (e = node->callees; e; e = e->next_callee)
1731     if (e->callee->local.disregard_inline_limits
1732         && e->inline_failed
1733         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1734         /* ??? It is possible that renaming variable removed the function body
1735            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
1736         && DECL_SAVED_TREE (e->callee->decl))
1737       cgraph_mark_inline (e);
1738
1739   /* Now do the automatic inlining.  */
1740   if (!flag_really_no_inline)
1741     for (e = node->callees; e; e = e->next_callee)
1742       if (e->callee->local.inlinable
1743           && e->inline_failed
1744           && !e->callee->local.disregard_inline_limits
1745           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1746           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1747           && DECL_SAVED_TREE (e->callee->decl))
1748         {
1749           if (cgraph_default_inline_p (e->callee))
1750             cgraph_mark_inline (e);
1751           else
1752             e->inline_failed
1753               = N_("--param max-inline-insns-single limit reached");
1754         }
1755 }
1756
1757
1758 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1759
1760 bool
1761 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
1762 {
1763   *reason = e->inline_failed;
1764   return !e->inline_failed;
1765 }
1766
1767
1768
1769 /* Expand all functions that must be output.
1770
1771    Attempt to topologically sort the nodes so function is output when
1772    all called functions are already assembled to allow data to be
1773    propagated across the callgraph.  Use a stack to get smaller distance
1774    between a function and its callees (later we may choose to use a more
1775    sophisticated algorithm for function reordering; we will likely want
1776    to use subsections to make the output functions appear in top-down
1777    order).  */
1778
1779 static void
1780 cgraph_expand_all_functions (void)
1781 {
1782   struct cgraph_node *node;
1783   struct cgraph_node **order =
1784     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1785   int order_pos = 0, new_order_pos = 0;
1786   int i;
1787
1788   order_pos = cgraph_postorder (order);
1789   gcc_assert (order_pos == cgraph_n_nodes);
1790
1791   /* Garbage collector may remove inline clones we eliminate during
1792      optimization.  So we must be sure to not reference them.  */
1793   for (i = 0; i < order_pos; i++)
1794     if (order[i]->output)
1795       order[new_order_pos++] = order[i];
1796
1797   for (i = new_order_pos - 1; i >= 0; i--)
1798     {
1799       node = order[i];
1800       if (node->output)
1801         {
1802           gcc_assert (node->reachable);
1803           node->output = 0;
1804           cgraph_expand_function (node);
1805         }
1806     }
1807   free (order);
1808 }
1809
1810 /* Mark all local functions.
1811    
1812    A local function is one whose calls can occur only in the current
1813    compilation unit and all its calls are explicit, so we can change
1814    its calling convention.  We simply mark all static functions whose
1815    address is not taken as local.  */
1816
1817 static void
1818 cgraph_mark_local_functions (void)
1819 {
1820   struct cgraph_node *node;
1821
1822   /* Figure out functions we want to assemble.  */
1823   for (node = cgraph_nodes; node; node = node->next)
1824     {
1825       node->local.local = (!node->needed
1826                            && DECL_SAVED_TREE (node->decl)
1827                            && !TREE_PUBLIC (node->decl));
1828     }
1829
1830   if (cgraph_dump_file)
1831     {
1832       fprintf (cgraph_dump_file, "\nMarking local functions:");
1833       for (node = cgraph_nodes; node; node = node->next)
1834         if (node->local.local)
1835           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1836       fprintf (cgraph_dump_file, "\n\n");
1837     }
1838 }
1839
1840 /* Return true when function body of DECL still needs to be kept around
1841    for later re-use.  */
1842 bool
1843 cgraph_preserve_function_body_p (tree decl)
1844 {
1845   struct cgraph_node *node;
1846   /* Keep the body; we're going to dump it.  */
1847   if (dump_enabled_p (TDI_tree_all))
1848     return true;
1849   if (!cgraph_global_info_ready)
1850     return (DECL_INLINE (decl) && !flag_really_no_inline);
1851   /* Look if there is any clone around.  */
1852   for (node = cgraph_node (decl); node; node = node->next_clone)
1853     if (node->global.inlined_to)
1854       return true;
1855   return false;
1856 }
1857
1858 /* Perform simple optimizations based on callgraph.  */
1859
1860 void
1861 cgraph_optimize (void)
1862 {
1863 #ifdef ENABLE_CHECKING
1864   verify_cgraph ();
1865 #endif
1866   if (!flag_unit_at_a_time)
1867     {
1868       cgraph_varpool_assemble_pending_decls ();
1869       return;
1870     }
1871
1872   process_pending_assemble_externals ();
1873   
1874   /* Frontend may output common variables after the unit has been finalized.
1875      It is safe to deal with them here as they are always zero initialized.  */
1876   cgraph_varpool_analyze_pending_decls ();
1877
1878   timevar_push (TV_CGRAPHOPT);
1879   if (!quiet_flag)
1880     fprintf (stderr, "Performing intraprocedural optimizations\n");
1881
1882   cgraph_mark_local_functions ();
1883   if (cgraph_dump_file)
1884     {
1885       fprintf (cgraph_dump_file, "Marked ");
1886       dump_cgraph (cgraph_dump_file);
1887     }
1888
1889   if (flag_inline_trees)
1890     cgraph_decide_inlining ();
1891   cgraph_global_info_ready = true;
1892   if (cgraph_dump_file)
1893     {
1894       fprintf (cgraph_dump_file, "Optimized ");
1895       dump_cgraph (cgraph_dump_file);
1896       dump_varpool (cgraph_dump_file);
1897     }
1898   timevar_pop (TV_CGRAPHOPT);
1899
1900   /* Output everything.  */
1901   if (!quiet_flag)
1902     fprintf (stderr, "Assembling functions:\n");
1903 #ifdef ENABLE_CHECKING
1904   verify_cgraph ();
1905 #endif
1906   
1907   cgraph_mark_functions_to_output ();
1908   cgraph_expand_all_functions ();
1909   cgraph_varpool_remove_unreferenced_decls ();
1910
1911   cgraph_varpool_assemble_pending_decls ();
1912
1913   if (cgraph_dump_file)
1914     {
1915       fprintf (cgraph_dump_file, "\nFinal ");
1916       dump_cgraph (cgraph_dump_file);
1917     }
1918 #ifdef ENABLE_CHECKING
1919   verify_cgraph ();
1920   /* Double check that all inline clones are gone and that all
1921      function bodies have been released from memory.  */
1922   if (flag_unit_at_a_time
1923       && !dump_enabled_p (TDI_tree_all)
1924       && !(sorrycount || errorcount))
1925     {
1926       struct cgraph_node *node;
1927       bool error_found = false;
1928
1929       for (node = cgraph_nodes; node; node = node->next)
1930         if (node->analyzed
1931             && (node->global.inlined_to
1932                 || DECL_SAVED_TREE (node->decl)))
1933           {
1934             error_found = true;
1935             dump_cgraph_node (stderr, node);
1936           }
1937       if (error_found)
1938         internal_error ("Nodes with no released memory found.");
1939     }
1940 #endif
1941 }
1942
1943 /* Generate and emit a static constructor or destructor.  WHICH must be
1944    one of 'I' or 'D'.  BODY should be a STATEMENT_LIST containing 
1945    GENERIC statements.  */
1946
1947 void
1948 cgraph_build_static_cdtor (char which, tree body, int priority)
1949 {
1950   static int counter = 0;
1951   char which_buf[16];
1952   tree decl, name, resdecl;
1953
1954   sprintf (which_buf, "%c_%d", which, counter++);
1955   name = get_file_function_name_long (which_buf);
1956
1957   decl = build_decl (FUNCTION_DECL, name,
1958                      build_function_type (void_type_node, void_list_node));
1959   current_function_decl = decl;
1960
1961   resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1962   DECL_ARTIFICIAL (resdecl) = 1;
1963   DECL_IGNORED_P (resdecl) = 1;
1964   DECL_RESULT (decl) = resdecl;
1965
1966   allocate_struct_function (decl);
1967
1968   TREE_STATIC (decl) = 1;
1969   TREE_USED (decl) = 1;
1970   DECL_ARTIFICIAL (decl) = 1;
1971   DECL_IGNORED_P (decl) = 1;
1972   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1973   DECL_SAVED_TREE (decl) = body;
1974   TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1975   DECL_UNINLINABLE (decl) = 1;
1976
1977   DECL_INITIAL (decl) = make_node (BLOCK);
1978   TREE_USED (DECL_INITIAL (decl)) = 1;
1979
1980   DECL_SOURCE_LOCATION (decl) = input_location;
1981   cfun->function_end_locus = input_location;
1982
1983   switch (which)
1984     {
1985     case 'I':
1986       DECL_STATIC_CONSTRUCTOR (decl) = 1;
1987       break;
1988     case 'D':
1989       DECL_STATIC_DESTRUCTOR (decl) = 1;
1990       break;
1991     default:
1992       gcc_unreachable ();
1993     }
1994
1995   gimplify_function_tree (decl);
1996
1997   /* ??? We will get called LATE in the compilation process.  */
1998   if (cgraph_global_info_ready)
1999     tree_rest_of_compilation (decl);
2000   else
2001     cgraph_finalize_function (decl, 0);
2002   
2003   if (targetm.have_ctors_dtors)
2004     {
2005       void (*fn) (rtx, int);
2006
2007       if (which == 'I')
2008         fn = targetm.asm_out.constructor;
2009       else
2010         fn = targetm.asm_out.destructor;
2011       fn (XEXP (DECL_RTL (decl), 0), priority);
2012     }
2013 }
2014
2015 void
2016 init_cgraph (void)
2017 {
2018   cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
2019 }