OSDN Git Service

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