OSDN Git Service

37e1ac889953af5b7b65fffbb00adcb9666d9499
[pf3gnuchains/gcc-fork.git] / gcc / cgraphunit.c
1 /* Callgraph based interprocedural optimizations.
2    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
3    Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /* This module implements main driver of compilation process as well as
23    few basic interprocedural 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
36         function.)
37
38     - varpool_finalize_variable
39
40       This function has same behavior as the above but is used for static
41       variables.
42
43     - cgraph_finalize_compilation_unit
44
45       This function is called once (source level) compilation unit is finalized
46       and it will no longer change.
47
48       In the unit-at-a-time the call-graph construction and local function
49       analysis takes place here.  Bodies of unreachable functions are released
50       to conserve memory usage.
51
52       The function can be called multiple times when multiple source level
53       compilation units are combined (such as in C frontend)
54
55     - cgraph_optimize
56
57       In this unit-at-a-time compilation the intra procedural analysis takes
58       place here.  In particular the static functions whose address is never
59       taken are marked as local.  Backend can then use this information to
60       modify calling conventions, do better inlining or similar optimizations.
61
62     - cgraph_mark_needed_node
63     - varpool_mark_needed_node
64
65       When function or variable is referenced by some hidden way the call-graph
66       data structure must be updated accordingly by this function.
67       There should be little need to call this function and all the references
68       should be made explicit to cgraph code.  At present these functions are
69       used by C++ frontend to explicitly mark the keyed methods.
70
71     - analyze_expr callback
72
73       This function is responsible for lowering tree nodes not understood by
74       generic code into understandable ones or alternatively marking
75       callgraph and varpool nodes referenced by the as needed.
76
77       ??? On the tree-ssa genericizing should take place here and we will avoid
78       need for these hooks (replacing them by genericizing hook)
79
80     - expand_function callback
81
82       This function is used to expand function and pass it into RTL back-end.
83       Front-end should not make any assumptions about when this function can be
84       called.  In particular cgraph_assemble_pending_functions,
85       varpool_assemble_pending_variables, cgraph_finalize_function,
86       varpool_finalize_function, cgraph_optimize can cause arbitrarily
87       previously finalized functions to be expanded.
88
89     We implement two compilation modes.
90
91       - unit-at-a-time:  In this mode analyzing of all functions is deferred
92         to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
93
94         In cgraph_finalize_compilation_unit the reachable functions are
95         analyzed.  During analysis the call-graph edges from reachable
96         functions are constructed and their destinations are marked as
97         reachable.  References to functions and variables are discovered too
98         and variables found to be needed output to the assembly file.  Via
99         mark_referenced call in assemble_variable functions referenced by
100         static variables are noticed too.
101
102         The intra-procedural information is produced and its existence
103         indicated by global_info_ready.  Once this flag is set it is impossible
104         to change function from !reachable to reachable and thus
105         assemble_variable no longer call mark_referenced.
106
107         Finally the call-graph is topologically sorted and all reachable functions
108         that has not been completely inlined or are not external are output.
109
110         ??? It is possible that reference to function or variable is optimized
111         out.  We can not deal with this nicely because topological order is not
112         suitable for it.  For tree-ssa we may consider another pass doing
113         optimization and re-discovering reachable functions.
114
115         ??? Reorganize code so variables are output very last and only if they
116         really has been referenced by produced code, so we catch more cases
117         where reference has been optimized out.
118
119       - non-unit-at-a-time
120
121         All functions are variables are output as early as possible to conserve
122         memory consumption.  This may or may not result in less memory used but
123         it is still needed for some legacy code that rely on particular ordering
124         of things output from the compiler.
125
126         Varpool data structures are not used and variables are output directly.
127
128         Functions are output early using call of
129         cgraph_assemble_pending_function from cgraph_finalize_function.  The
130         decision on whether function is needed is made more conservative so
131         uninlininable static functions are needed too.  During the call-graph
132         construction the edge destinations are not marked as reachable and it
133         is completely relied upn assemble_variable to mark them.  */
134
135
136 #include "config.h"
137 #include "system.h"
138 #include "coretypes.h"
139 #include "tm.h"
140 #include "tree.h"
141 #include "rtl.h"
142 #include "tree-flow.h"
143 #include "tree-inline.h"
144 #include "langhooks.h"
145 #include "pointer-set.h"
146 #include "toplev.h"
147 #include "flags.h"
148 #include "ggc.h"
149 #include "debug.h"
150 #include "target.h"
151 #include "cgraph.h"
152 #include "diagnostic.h"
153 #include "timevar.h"
154 #include "params.h"
155 #include "fibheap.h"
156 #include "c-common.h"
157 #include "intl.h"
158 #include "function.h"
159 #include "ipa-prop.h"
160 #include "tree-gimple.h"
161 #include "tree-pass.h"
162 #include "output.h"
163
164 static void cgraph_expand_all_functions (void);
165 static void cgraph_mark_functions_to_output (void);
166 static void cgraph_expand_function (struct cgraph_node *);
167 static tree record_reference (tree *, int *, void *);
168 static void cgraph_output_pending_asms (void);
169 static void cgraph_increase_alignment (void);
170
171 /* Records tree nodes seen in record_reference.  Simply using
172    walk_tree_without_duplicates doesn't guarantee each node is visited
173    once because it gets a new htab upon each recursive call from
174    record_reference itself.  */
175 static struct pointer_set_t *visited_nodes;
176
177 static FILE *cgraph_dump_file;
178
179 /* Determine if function DECL is needed.  That is, visible to something
180    either outside this translation unit, something magic in the system
181    configury, or (if not doing unit-at-a-time) to something we havn't
182    seen yet.  */
183
184 static bool
185 decide_is_function_needed (struct cgraph_node *node, tree decl)
186 {
187   tree origin;
188   if (MAIN_NAME_P (DECL_NAME (decl))
189       && TREE_PUBLIC (decl))
190     {
191       node->local.externally_visible = true;
192       return true;
193     }
194
195   /* If the user told us it is used, then it must be so.  */
196   if (node->local.externally_visible)
197     return true;
198
199   if (!flag_unit_at_a_time && lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
200     return true;
201
202   /* ??? If the assembler name is set by hand, it is possible to assemble
203      the name later after finalizing the function and the fact is noticed
204      in assemble_name then.  This is arguably a bug.  */
205   if (DECL_ASSEMBLER_NAME_SET_P (decl)
206       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
207     return true;
208
209   /* If we decided it was needed before, but at the time we didn't have
210      the body of the function available, then it's still needed.  We have
211      to go back and re-check its dependencies now.  */
212   if (node->needed)
213     return true;
214
215   /* Externally visible functions must be output.  The exception is
216      COMDAT functions that must be output only when they are needed.
217
218      When not optimizing, also output the static functions. (see
219      PR24561), but don't do so for always_inline functions, functions
220      declared inline and nested functions.  These was optimized out
221      in the original implementation and it is unclear whether we want
222      to change the behavior here.  */
223   if (((TREE_PUBLIC (decl)
224         || (!optimize && !node->local.disregard_inline_limits
225             && !DECL_DECLARED_INLINE_P (decl)
226             && !node->origin))
227       && !flag_whole_program)
228       && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
229     return true;
230
231   /* Constructors and destructors are reachable from the runtime by
232      some mechanism.  */
233   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
234     return true;
235
236   if (flag_unit_at_a_time)
237     return false;
238
239   /* If not doing unit at a time, then we'll only defer this function
240      if its marked for inlining.  Otherwise we want to emit it now.  */
241
242   /* "extern inline" functions are never output locally.  */
243   if (DECL_EXTERNAL (decl))
244     return false;
245   /* Nested functions of extern inline function shall not be emit unless
246      we inlined the origin.  */
247   for (origin = decl_function_context (decl); origin;
248        origin = decl_function_context (origin))
249     if (DECL_EXTERNAL (origin))
250       return false;
251   /* We want to emit COMDAT functions only when absolutely necessary.  */
252   if (DECL_COMDAT (decl))
253     return false;
254   if (!DECL_INLINE (decl)
255       || (!node->local.disregard_inline_limits
256           /* When declared inline, defer even the uninlinable functions.
257              This allows them to be eliminated when unused.  */
258           && !DECL_DECLARED_INLINE_P (decl)
259           && (!node->local.inlinable || !cgraph_default_inline_p (node, NULL))))
260     return true;
261
262   return false;
263 }
264
265 /* When not doing unit-at-a-time, output all functions enqueued.
266    Return true when such a functions were found.  */
267
268 static bool
269 cgraph_assemble_pending_functions (void)
270 {
271   bool output = false;
272
273   if (flag_unit_at_a_time)
274     return false;
275
276   cgraph_output_pending_asms ();
277
278   while (cgraph_nodes_queue)
279     {
280       struct cgraph_node *n = cgraph_nodes_queue;
281
282       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
283       n->next_needed = NULL;
284       if (!n->global.inlined_to
285           && !n->alias
286           && !DECL_EXTERNAL (n->decl))
287         {
288           cgraph_expand_function (n);
289           output = true;
290         }
291     }
292
293   /* Process CGRAPH_EXPAND_QUEUE, these are functions created during
294      the expansion process.  Note that this queue may grow as its
295      being processed, as the new functions may generate new ones.  */
296   while (cgraph_expand_queue)
297     {
298       struct cgraph_node *n = cgraph_expand_queue;
299       cgraph_expand_queue = cgraph_expand_queue->next_needed;
300       n->next_needed = NULL;
301       cgraph_finalize_function (n->decl, false);
302       output = true;
303     }
304
305   return output;
306 }
307
308
309 /* As an GCC extension we allow redefinition of the function.  The
310    semantics when both copies of bodies differ is not well defined.
311    We replace the old body with new body so in unit at a time mode
312    we always use new body, while in normal mode we may end up with
313    old body inlined into some functions and new body expanded and
314    inlined in others.
315
316    ??? It may make more sense to use one body for inlining and other
317    body for expanding the function but this is difficult to do.  */
318
319 static void
320 cgraph_reset_node (struct cgraph_node *node)
321 {
322   /* If node->output is set, then this is a unit-at-a-time compilation
323      and we have already begun whole-unit analysis.  This is *not*
324      testing for whether we've already emitted the function.  That
325      case can be sort-of legitimately seen with real function
326      redefinition errors.  I would argue that the front end should
327      never present us with such a case, but don't enforce that for now.  */
328   gcc_assert (!node->output);
329
330   /* Reset our data structures so we can analyze the function again.  */
331   memset (&node->local, 0, sizeof (node->local));
332   memset (&node->global, 0, sizeof (node->global));
333   memset (&node->rtl, 0, sizeof (node->rtl));
334   node->analyzed = false;
335   node->local.redefined_extern_inline = true;
336   node->local.finalized = false;
337
338   if (!flag_unit_at_a_time)
339     {
340       struct cgraph_node *n, *next;
341
342       for (n = cgraph_nodes; n; n = next)
343         {
344           next = n->next;
345           if (n->global.inlined_to == node)
346             cgraph_remove_node (n);
347         }
348     }
349
350   cgraph_node_remove_callees (node);
351
352   /* We may need to re-queue the node for assembling in case
353      we already proceeded it and ignored as not needed.  */
354   if (node->reachable && !flag_unit_at_a_time)
355     {
356       struct cgraph_node *n;
357
358       for (n = cgraph_nodes_queue; n; n = n->next_needed)
359         if (n == node)
360           break;
361       if (!n)
362         node->reachable = 0;
363     }
364 }
365
366 static void
367 cgraph_lower_function (struct cgraph_node *node)
368 {
369   if (node->lowered)
370     return;
371   tree_lowering_passes (node->decl);
372   node->lowered = true;
373 }
374
375 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
376    logic in effect.  If NESTED is true, then our caller cannot stand to have
377    the garbage collector run at the moment.  We would need to either create
378    a new GC context, or just not compile right now.  */
379
380 void
381 cgraph_finalize_function (tree decl, bool nested)
382 {
383   struct cgraph_node *node = cgraph_node (decl);
384
385   if (node->local.finalized)
386     cgraph_reset_node (node);
387
388   notice_global_symbol (decl);
389   node->decl = decl;
390   node->local.finalized = true;
391   node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
392   if (node->nested)
393     lower_nested_functions (decl);
394   gcc_assert (!node->nested);
395
396   /* If not unit at a time, then we need to create the call graph
397      now, so that called functions can be queued and emitted now.  */
398   if (!flag_unit_at_a_time)
399     {
400       cgraph_analyze_function (node);
401       cgraph_decide_inlining_incrementally (node, false);
402     }
403
404   if (decide_is_function_needed (node, decl))
405     cgraph_mark_needed_node (node);
406
407   /* Since we reclaim unreachable nodes at the end of every language
408      level unit, we need to be conservative about possible entry points
409      there.  */
410   if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
411     cgraph_mark_reachable_node (node);
412
413   /* If not unit at a time, go ahead and emit everything we've found
414      to be reachable at this time.  */
415   if (!nested)
416     {
417       if (!cgraph_assemble_pending_functions ())
418         ggc_collect ();
419     }
420
421   /* If we've not yet emitted decl, tell the debug info about it.  */
422   if (!TREE_ASM_WRITTEN (decl))
423     (*debug_hooks->deferred_inline_function) (decl);
424
425   /* Possibly warn about unused parameters.  */
426   if (warn_unused_parameter)
427     do_warn_unused_parameter (decl);
428 }
429
430 /* Walk tree and record all calls.  Called via walk_tree.  */
431 static tree
432 record_reference (tree *tp, int *walk_subtrees, void *data)
433 {
434   tree t = *tp;
435
436   switch (TREE_CODE (t))
437     {
438     case VAR_DECL:
439       /* ??? Really, we should mark this decl as *potentially* referenced
440          by this function and re-examine whether the decl is actually used
441          after rtl has been generated.  */
442       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
443         {
444           varpool_mark_needed_node (varpool_node (t));
445           if (lang_hooks.callgraph.analyze_expr)
446             return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees,
447                                                       data);
448         }
449       break;
450
451     case FDESC_EXPR:
452     case ADDR_EXPR:
453       if (flag_unit_at_a_time)
454         {
455           /* Record dereferences to the functions.  This makes the
456              functions reachable unconditionally.  */
457           tree decl = TREE_OPERAND (*tp, 0);
458           if (TREE_CODE (decl) == FUNCTION_DECL)
459             cgraph_mark_needed_node (cgraph_node (decl));
460         }
461       break;
462
463     default:
464       /* Save some cycles by not walking types and declaration as we
465          won't find anything useful there anyway.  */
466       if (IS_TYPE_OR_DECL_P (*tp))
467         {
468           *walk_subtrees = 0;
469           break;
470         }
471
472       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
473         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);
474       break;
475     }
476
477   return NULL;
478 }
479
480 /* Create cgraph edges for function calls inside BODY from NODE.  */
481
482 static void
483 cgraph_create_edges (struct cgraph_node *node, tree body)
484 {
485   basic_block bb;
486
487   struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
488   block_stmt_iterator bsi;
489   tree step;
490   visited_nodes = pointer_set_create ();
491
492   /* Reach the trees by walking over the CFG, and note the
493      enclosing basic-blocks in the call edges.  */
494   FOR_EACH_BB_FN (bb, this_cfun)
495     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
496       {
497         tree stmt = bsi_stmt (bsi);
498         tree call = get_call_expr_in (stmt);
499         tree decl;
500
501         if (call && (decl = get_callee_fndecl (call)))
502           {
503             cgraph_create_edge (node, cgraph_node (decl), stmt,
504                                 bb->count,
505                                 bb->loop_depth);
506             walk_tree (&TREE_OPERAND (call, 1),
507                        record_reference, node, visited_nodes);
508             if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
509               walk_tree (&GIMPLE_STMT_OPERAND (stmt, 0),
510                          record_reference, node, visited_nodes);
511           }
512         else
513           walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes);
514       }
515
516   /* Look for initializers of constant variables and private statics.  */
517   for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list;
518        step;
519        step = TREE_CHAIN (step))
520     {
521       tree decl = TREE_VALUE (step);
522       if (TREE_CODE (decl) == VAR_DECL
523           && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
524           && flag_unit_at_a_time)
525         varpool_finalize_decl (decl);
526       else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))
527         walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
528     }
529
530   pointer_set_destroy (visited_nodes);
531   visited_nodes = NULL;
532 }
533
534 void
535 record_references_in_initializer (tree decl)
536 {
537   visited_nodes = pointer_set_create ();
538   walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
539   pointer_set_destroy (visited_nodes);
540   visited_nodes = NULL;
541 }
542
543
544 /* Give initial reasons why inlining would fail.  Those gets
545    either NULLified or usually overwritten by more precise reason
546    later.  */
547 static void
548 initialize_inline_failed (struct cgraph_node *node)
549 {
550   struct cgraph_edge *e;
551
552   for (e = node->callers; e; e = e->next_caller)
553     {
554       gcc_assert (!e->callee->global.inlined_to);
555       gcc_assert (e->inline_failed);
556       if (node->local.redefined_extern_inline)
557         e->inline_failed = N_("redefined extern inline functions are not "
558                            "considered for inlining");
559       else if (!node->local.inlinable)
560         e->inline_failed = N_("function not inlinable");
561       else
562         e->inline_failed = N_("function not considered for inlining");
563     }
564 }
565
566 /* Rebuild call edges from current function after a passes not aware
567    of cgraph updating.  */
568 static unsigned int
569 rebuild_cgraph_edges (void)
570 {
571   basic_block bb;
572   struct cgraph_node *node = cgraph_node (current_function_decl);
573   block_stmt_iterator bsi;
574
575   cgraph_node_remove_callees (node);
576
577   node->count = ENTRY_BLOCK_PTR->count;
578
579   FOR_EACH_BB (bb)
580     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
581       {
582         tree stmt = bsi_stmt (bsi);
583         tree call = get_call_expr_in (stmt);
584         tree decl;
585
586         if (call && (decl = get_callee_fndecl (call)))
587           cgraph_create_edge (node, cgraph_node (decl), stmt,
588                               bb->count,
589                               bb->loop_depth);
590       }
591   initialize_inline_failed (node);
592   gcc_assert (!node->global.inlined_to);
593   return 0;
594 }
595
596 struct tree_opt_pass pass_rebuild_cgraph_edges =
597 {
598   NULL,                                 /* name */
599   NULL,                                 /* gate */
600   rebuild_cgraph_edges,                 /* execute */
601   NULL,                                 /* sub */
602   NULL,                                 /* next */
603   0,                                    /* static_pass_number */
604   0,                                    /* tv_id */
605   PROP_cfg,                             /* properties_required */
606   0,                                    /* properties_provided */
607   0,                                    /* properties_destroyed */
608   0,                                    /* todo_flags_start */
609   0,                                    /* todo_flags_finish */
610   0                                     /* letter */
611 };
612
613 /* Verify cgraph nodes of given cgraph node.  */
614 void
615 verify_cgraph_node (struct cgraph_node *node)
616 {
617   struct cgraph_edge *e;
618   struct cgraph_node *main_clone;
619   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
620   basic_block this_block;
621   block_stmt_iterator bsi;
622   bool error_found = false;
623
624   if (errorcount || sorrycount)
625     return;
626
627   timevar_push (TV_CGRAPH_VERIFY);
628   for (e = node->callees; e; e = e->next_callee)
629     if (e->aux)
630       {
631         error ("aux field set for edge %s->%s",
632                cgraph_node_name (e->caller), cgraph_node_name (e->callee));
633         error_found = true;
634       }
635   if (node->count < 0)
636     {
637       error ("Execution count is negative");
638       error_found = true;
639     }
640   for (e = node->callers; e; e = e->next_caller)
641     {
642       if (e->count < 0)
643         {
644           error ("caller edge count is negative");
645           error_found = true;
646         }
647       if (!e->inline_failed)
648         {
649           if (node->global.inlined_to
650               != (e->caller->global.inlined_to
651                   ? e->caller->global.inlined_to : e->caller))
652             {
653               error ("inlined_to pointer is wrong");
654               error_found = true;
655             }
656           if (node->callers->next_caller)
657             {
658               error ("multiple inline callers");
659               error_found = true;
660             }
661         }
662       else
663         if (node->global.inlined_to)
664           {
665             error ("inlined_to pointer set for noninline callers");
666             error_found = true;
667           }
668     }
669   if (!node->callers && node->global.inlined_to)
670     {
671       error ("inlined_to pointer is set but no predecessors found");
672       error_found = true;
673     }
674   if (node->global.inlined_to == node)
675     {
676       error ("inlined_to pointer refers to itself");
677       error_found = true;
678     }
679
680   for (main_clone = cgraph_node (node->decl); main_clone;
681        main_clone = main_clone->next_clone)
682     if (main_clone == node)
683       break;
684   if (!cgraph_node (node->decl))
685     {
686       error ("node not found in cgraph_hash");
687       error_found = true;
688     }
689
690   if (node->analyzed
691       && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
692       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
693     {
694       if (this_cfun->cfg)
695         {
696           /* The nodes we're interested in are never shared, so walk
697              the tree ignoring duplicates.  */
698           visited_nodes = pointer_set_create ();
699           /* Reach the trees by walking over the CFG, and note the
700              enclosing basic-blocks in the call edges.  */
701           FOR_EACH_BB_FN (this_block, this_cfun)
702             for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
703               {
704                 tree stmt = bsi_stmt (bsi);
705                 tree call = get_call_expr_in (stmt);
706                 tree decl;
707                 if (call && (decl = get_callee_fndecl (call)))
708                   {
709                     struct cgraph_edge *e = cgraph_edge (node, stmt);
710                     if (e)
711                       {
712                         if (e->aux)
713                           {
714                             error ("shared call_stmt:");
715                             debug_generic_stmt (stmt);
716                             error_found = true;
717                           }
718                         if (e->callee->decl != cgraph_node (decl)->decl
719                             && e->inline_failed)
720                           {
721                             error ("edge points to wrong declaration:");
722                             debug_tree (e->callee->decl);
723                             fprintf (stderr," Instead of:");
724                             debug_tree (decl);
725                           }
726                         e->aux = (void *)1;
727                       }
728                     else
729                       {
730                         error ("missing callgraph edge for call stmt:");
731                         debug_generic_stmt (stmt);
732                         error_found = true;
733                       }
734                   }
735               }
736           pointer_set_destroy (visited_nodes);
737           visited_nodes = NULL;
738         }
739       else
740         /* No CFG available?!  */
741         gcc_unreachable ();
742
743       for (e = node->callees; e; e = e->next_callee)
744         {
745           if (!e->aux)
746             {
747               error ("edge %s->%s has no corresponding call_stmt",
748                      cgraph_node_name (e->caller),
749                      cgraph_node_name (e->callee));
750               debug_generic_stmt (e->call_stmt);
751               error_found = true;
752             }
753           e->aux = 0;
754         }
755     }
756   if (error_found)
757     {
758       dump_cgraph_node (stderr, node);
759       internal_error ("verify_cgraph_node failed");
760     }
761   timevar_pop (TV_CGRAPH_VERIFY);
762 }
763
764 /* Verify whole cgraph structure.  */
765 void
766 verify_cgraph (void)
767 {
768   struct cgraph_node *node;
769
770   if (sorrycount || errorcount)
771     return;
772
773   for (node = cgraph_nodes; node; node = node->next)
774     verify_cgraph_node (node);
775 }
776
777 /* Output all asm statements we have stored up to be output.  */
778
779 static void
780 cgraph_output_pending_asms (void)
781 {
782   struct cgraph_asm_node *can;
783
784   if (errorcount || sorrycount)
785     return;
786
787   for (can = cgraph_asm_nodes; can; can = can->next)
788     assemble_asm (can->asm_str);
789   cgraph_asm_nodes = NULL;
790 }
791
792 /* Analyze the function scheduled to be output.  */
793 void
794 cgraph_analyze_function (struct cgraph_node *node)
795 {
796   tree decl = node->decl;
797
798   current_function_decl = decl;
799   push_cfun (DECL_STRUCT_FUNCTION (decl));
800   cgraph_lower_function (node);
801
802   /* First kill forward declaration so reverse inlining works properly.  */
803   cgraph_create_edges (node, decl);
804
805   node->local.estimated_self_stack_size = estimated_stack_frame_size ();
806   node->global.estimated_stack_size = node->local.estimated_self_stack_size;
807   node->global.stack_frame_offset = 0;
808   node->local.inlinable = tree_inlinable_function_p (decl);
809   if (!flag_unit_at_a_time)
810     node->local.self_insns = estimate_num_insns (decl);
811   if (node->local.inlinable)
812     node->local.disregard_inline_limits
813       = lang_hooks.tree_inlining.disregard_inline_limits (decl);
814   initialize_inline_failed (node);
815   if (flag_really_no_inline && !node->local.disregard_inline_limits)
816     node->local.inlinable = 0;
817   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
818   node->global.insns = node->local.self_insns;
819
820   node->analyzed = true;
821   pop_cfun ();
822   current_function_decl = NULL;
823 }
824
825 /* Look for externally_visible and used attributes and mark cgraph nodes
826    accordingly.
827
828    We cannot mark the nodes at the point the attributes are processed (in
829    handle_*_attribute) because the copy of the declarations available at that
830    point may not be canonical.  For example, in:
831
832     void f();
833     void f() __attribute__((used));
834
835    the declaration we see in handle_used_attribute will be the second
836    declaration -- but the front end will subsequently merge that declaration
837    with the original declaration and discard the second declaration.
838
839    Furthermore, we can't mark these nodes in cgraph_finalize_function because:
840
841     void f() {}
842     void f() __attribute__((externally_visible));
843
844    is valid.
845
846    So, we walk the nodes at the end of the translation unit, applying the
847    attributes at that point.  */
848
849 static void
850 process_function_and_variable_attributes (struct cgraph_node *first,
851                                           struct varpool_node *first_var)
852 {
853   struct cgraph_node *node;
854   struct varpool_node *vnode;
855
856   for (node = cgraph_nodes; node != first; node = node->next)
857     {
858       tree decl = node->decl;
859       if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
860         {
861           mark_decl_referenced (decl);
862           if (node->local.finalized)
863              cgraph_mark_needed_node (node);
864         }
865       if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
866         {
867           if (! TREE_PUBLIC (node->decl))
868             warning (OPT_Wattributes,
869                      "%J%<externally_visible%> attribute have effect only on public objects",
870                      node->decl);
871           else
872             {
873               if (node->local.finalized)
874                 cgraph_mark_needed_node (node);
875               node->local.externally_visible = true;
876             }
877         }
878     }
879   for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
880     {
881       tree decl = vnode->decl;
882       if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
883         {
884           mark_decl_referenced (decl);
885           if (vnode->finalized)
886             varpool_mark_needed_node (vnode);
887         }
888       if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
889         {
890           if (! TREE_PUBLIC (vnode->decl))
891             warning (OPT_Wattributes,
892                      "%J%<externally_visible%> attribute have effect only on public objects",
893                      vnode->decl);
894           else
895             {
896               if (vnode->finalized)
897                 varpool_mark_needed_node (vnode);
898               vnode->externally_visible = true;
899             }
900         }
901     }
902 }
903
904 /* Analyze the whole compilation unit once it is parsed completely.  */
905
906 void
907 cgraph_finalize_compilation_unit (void)
908 {
909   struct cgraph_node *node, *next;
910   /* Keep track of already processed nodes when called multiple times for
911      intermodule optimization.  */
912   static struct cgraph_node *first_analyzed;
913   struct cgraph_node *first_processed = first_analyzed;
914   static struct varpool_node *first_analyzed_var;
915
916   if (errorcount || sorrycount)
917     return;
918
919   finish_aliases_1 ();
920
921   if (!flag_unit_at_a_time)
922     {
923       cgraph_output_pending_asms ();
924       cgraph_assemble_pending_functions ();
925       varpool_output_debug_info ();
926       return;
927     }
928
929   if (!quiet_flag)
930     {
931       fprintf (stderr, "\nAnalyzing compilation unit\n");
932       fflush (stderr);
933     }
934
935   timevar_push (TV_CGRAPH);
936   process_function_and_variable_attributes (first_processed,
937                                             first_analyzed_var);
938   first_processed = cgraph_nodes;
939   first_analyzed_var = varpool_nodes;
940   varpool_analyze_pending_decls ();
941   if (cgraph_dump_file)
942     {
943       fprintf (cgraph_dump_file, "Initial entry points:");
944       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
945         if (node->needed && DECL_SAVED_TREE (node->decl))
946           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
947       fprintf (cgraph_dump_file, "\n");
948     }
949
950   /* Propagate reachability flag and lower representation of all reachable
951      functions.  In the future, lowering will introduce new functions and
952      new entry points on the way (by template instantiation and virtual
953      method table generation for instance).  */
954   while (cgraph_nodes_queue)
955     {
956       struct cgraph_edge *edge;
957       tree decl = cgraph_nodes_queue->decl;
958
959       node = cgraph_nodes_queue;
960       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
961       node->next_needed = NULL;
962
963       /* ??? It is possible to create extern inline function and later using
964          weak alias attribute to kill its body. See
965          gcc.c-torture/compile/20011119-1.c  */
966       if (!DECL_SAVED_TREE (decl))
967         {
968           cgraph_reset_node (node);
969           continue;
970         }
971
972       gcc_assert (!node->analyzed && node->reachable);
973       gcc_assert (DECL_SAVED_TREE (decl));
974
975       cgraph_analyze_function (node);
976
977       for (edge = node->callees; edge; edge = edge->next_callee)
978         if (!edge->callee->reachable)
979           cgraph_mark_reachable_node (edge->callee);
980
981       /* We finalize local static variables during constructing callgraph
982          edges.  Process their attributes too.  */
983       process_function_and_variable_attributes (first_processed,
984                                                 first_analyzed_var);
985       first_processed = cgraph_nodes;
986       first_analyzed_var = varpool_nodes;
987       varpool_analyze_pending_decls ();
988     }
989
990   /* Collect entry points to the unit.  */
991   if (cgraph_dump_file)
992     {
993       fprintf (cgraph_dump_file, "Unit entry points:");
994       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
995         if (node->needed && DECL_SAVED_TREE (node->decl))
996           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
997       fprintf (cgraph_dump_file, "\n\nInitial ");
998       dump_cgraph (cgraph_dump_file);
999     }
1000
1001   if (cgraph_dump_file)
1002     fprintf (cgraph_dump_file, "\nReclaiming functions:");
1003
1004   for (node = cgraph_nodes; node != first_analyzed; node = next)
1005     {
1006       tree decl = node->decl;
1007       next = node->next;
1008
1009       if (node->local.finalized && !DECL_SAVED_TREE (decl))
1010         cgraph_reset_node (node);
1011
1012       if (!node->reachable && DECL_SAVED_TREE (decl))
1013         {
1014           if (cgraph_dump_file)
1015             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1016           cgraph_remove_node (node);
1017           continue;
1018         }
1019       else
1020         node->next_needed = NULL;
1021       gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl));
1022       gcc_assert (node->analyzed == node->local.finalized);
1023     }
1024   if (cgraph_dump_file)
1025     {
1026       fprintf (cgraph_dump_file, "\n\nReclaimed ");
1027       dump_cgraph (cgraph_dump_file);
1028     }
1029   first_analyzed = cgraph_nodes;
1030   ggc_collect ();
1031   timevar_pop (TV_CGRAPH);
1032 }
1033 /* Figure out what functions we want to assemble.  */
1034
1035 static void
1036 cgraph_mark_functions_to_output (void)
1037 {
1038   struct cgraph_node *node;
1039
1040   for (node = cgraph_nodes; node; node = node->next)
1041     {
1042       tree decl = node->decl;
1043       struct cgraph_edge *e;
1044
1045       gcc_assert (!node->output);
1046
1047       for (e = node->callers; e; e = e->next_caller)
1048         if (e->inline_failed)
1049           break;
1050
1051       /* We need to output all local functions that are used and not
1052          always inlined, as well as those that are reachable from
1053          outside the current compilation unit.  */
1054       if (DECL_SAVED_TREE (decl)
1055           && !node->global.inlined_to
1056           && (node->needed
1057               || (e && node->reachable))
1058           && !TREE_ASM_WRITTEN (decl)
1059           && !DECL_EXTERNAL (decl))
1060         node->output = 1;
1061       else
1062         {
1063           /* We should've reclaimed all functions that are not needed.  */
1064 #ifdef ENABLE_CHECKING
1065           if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
1066               && !DECL_EXTERNAL (decl))
1067             {
1068               dump_cgraph_node (stderr, node);
1069               internal_error ("failed to reclaim unneeded function");
1070             }
1071 #endif
1072           gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
1073                       || DECL_EXTERNAL (decl));
1074
1075         }
1076
1077     }
1078 }
1079
1080 /* Expand function specified by NODE.  */
1081
1082 static void
1083 cgraph_expand_function (struct cgraph_node *node)
1084 {
1085   tree decl = node->decl;
1086
1087   /* We ought to not compile any inline clones.  */
1088   gcc_assert (!node->global.inlined_to);
1089
1090   if (flag_unit_at_a_time)
1091     announce_function (decl);
1092
1093   cgraph_lower_function (node);
1094
1095   /* Generate RTL for the body of DECL.  */
1096   lang_hooks.callgraph.expand_function (decl);
1097
1098   /* Make sure that BE didn't give up on compiling.  */
1099   /* ??? Can happen with nested function of extern inline.  */
1100   gcc_assert (TREE_ASM_WRITTEN (node->decl));
1101
1102   current_function_decl = NULL;
1103   if (!cgraph_preserve_function_body_p (node->decl))
1104     {
1105       DECL_SAVED_TREE (node->decl) = NULL;
1106       DECL_STRUCT_FUNCTION (node->decl) = NULL;
1107       DECL_INITIAL (node->decl) = error_mark_node;
1108       /* Eliminate all call edges.  This is important so the call_expr no longer
1109          points to the dead function body.  */
1110       cgraph_node_remove_callees (node);
1111     }
1112
1113   cgraph_function_flags_ready = true;
1114 }
1115
1116 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1117
1118 bool
1119 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
1120 {
1121   *reason = e->inline_failed;
1122   return !e->inline_failed;
1123 }
1124
1125
1126
1127 /* Expand all functions that must be output.
1128
1129    Attempt to topologically sort the nodes so function is output when
1130    all called functions are already assembled to allow data to be
1131    propagated across the callgraph.  Use a stack to get smaller distance
1132    between a function and its callees (later we may choose to use a more
1133    sophisticated algorithm for function reordering; we will likely want
1134    to use subsections to make the output functions appear in top-down
1135    order).  */
1136
1137 static void
1138 cgraph_expand_all_functions (void)
1139 {
1140   struct cgraph_node *node;
1141   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1142   int order_pos = 0, new_order_pos = 0;
1143   int i;
1144
1145   order_pos = cgraph_postorder (order);
1146   gcc_assert (order_pos == cgraph_n_nodes);
1147
1148   /* Garbage collector may remove inline clones we eliminate during
1149      optimization.  So we must be sure to not reference them.  */
1150   for (i = 0; i < order_pos; i++)
1151     if (order[i]->output)
1152       order[new_order_pos++] = order[i];
1153
1154   for (i = new_order_pos - 1; i >= 0; i--)
1155     {
1156       node = order[i];
1157       if (node->output)
1158         {
1159           gcc_assert (node->reachable);
1160           node->output = 0;
1161           cgraph_expand_function (node);
1162         }
1163     }
1164
1165   free (order);
1166
1167   /* Process CGRAPH_EXPAND_QUEUE, these are functions created during
1168      the expansion process.  Note that this queue may grow as its
1169      being processed, as the new functions may generate new ones.  */
1170   while (cgraph_expand_queue)
1171     {
1172       node = cgraph_expand_queue;
1173       cgraph_expand_queue = cgraph_expand_queue->next_needed;
1174       node->next_needed = NULL;
1175       node->output = 0;
1176       node->lowered = DECL_STRUCT_FUNCTION (node->decl)->cfg != NULL;
1177       cgraph_expand_function (node);
1178     }
1179 }
1180
1181 /* This is used to sort the node types by the cgraph order number.  */
1182
1183 struct cgraph_order_sort
1184 {
1185   enum { ORDER_UNDEFINED = 0, ORDER_FUNCTION, ORDER_VAR, ORDER_ASM } kind;
1186   union
1187   {
1188     struct cgraph_node *f;
1189     struct varpool_node *v;
1190     struct cgraph_asm_node *a;
1191   } u;
1192 };
1193
1194 /* Output all functions, variables, and asm statements in the order
1195    according to their order fields, which is the order in which they
1196    appeared in the file.  This implements -fno-toplevel-reorder.  In
1197    this mode we may output functions and variables which don't really
1198    need to be output.  */
1199
1200 static void
1201 cgraph_output_in_order (void)
1202 {
1203   int max;
1204   size_t size;
1205   struct cgraph_order_sort *nodes;
1206   int i;
1207   struct cgraph_node *pf;
1208   struct varpool_node *pv;
1209   struct cgraph_asm_node *pa;
1210
1211   max = cgraph_order;
1212   size = max * sizeof (struct cgraph_order_sort);
1213   nodes = (struct cgraph_order_sort *) alloca (size);
1214   memset (nodes, 0, size);
1215
1216   varpool_analyze_pending_decls ();
1217
1218   for (pf = cgraph_nodes; pf; pf = pf->next)
1219     {
1220       if (pf->output)
1221         {
1222           i = pf->order;
1223           gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1224           nodes[i].kind = ORDER_FUNCTION;
1225           nodes[i].u.f = pf;
1226         }
1227     }
1228
1229   for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1230     {
1231       i = pv->order;
1232       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1233       nodes[i].kind = ORDER_VAR;
1234       nodes[i].u.v = pv;
1235     }
1236
1237   for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1238     {
1239       i = pa->order;
1240       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1241       nodes[i].kind = ORDER_ASM;
1242       nodes[i].u.a = pa;
1243     }
1244
1245   for (i = 0; i < max; ++i)
1246     {
1247       switch (nodes[i].kind)
1248         {
1249         case ORDER_FUNCTION:
1250           nodes[i].u.f->output = 0;
1251           cgraph_expand_function (nodes[i].u.f);
1252           break;
1253
1254         case ORDER_VAR:
1255           varpool_assemble_decl (nodes[i].u.v);
1256           break;
1257
1258         case ORDER_ASM:
1259           assemble_asm (nodes[i].u.a->asm_str);
1260           break;
1261
1262         case ORDER_UNDEFINED:
1263           break;
1264
1265         default:
1266           gcc_unreachable ();
1267         }
1268     }
1269
1270   cgraph_asm_nodes = NULL;
1271 }
1272
1273 /* Mark visibility of all functions.
1274
1275    A local function is one whose calls can occur only in the current
1276    compilation unit and all its calls are explicit, so we can change
1277    its calling convention.  We simply mark all static functions whose
1278    address is not taken as local.
1279
1280    We also change the TREE_PUBLIC flag of all declarations that are public
1281    in language point of view but we want to overwrite this default
1282    via visibilities for the backend point of view.  */
1283
1284 static void
1285 cgraph_function_and_variable_visibility (void)
1286 {
1287   struct cgraph_node *node;
1288   struct varpool_node *vnode;
1289
1290   for (node = cgraph_nodes; node; node = node->next)
1291     {
1292       if (node->reachable
1293           && (DECL_COMDAT (node->decl)
1294               || (!flag_whole_program
1295                   && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
1296         node->local.externally_visible = true;
1297       if (!node->local.externally_visible && node->analyzed
1298           && !DECL_EXTERNAL (node->decl))
1299         {
1300           gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
1301           TREE_PUBLIC (node->decl) = 0;
1302         }
1303       node->local.local = (!node->needed
1304                            && node->analyzed
1305                            && !DECL_EXTERNAL (node->decl)
1306                            && !node->local.externally_visible);
1307     }
1308   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
1309     {
1310       if (vnode->needed
1311           && !flag_whole_program
1312           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
1313         vnode->externally_visible = 1;
1314       if (!vnode->externally_visible)
1315         {
1316           gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
1317           TREE_PUBLIC (vnode->decl) = 0;
1318         }
1319      gcc_assert (TREE_STATIC (vnode->decl));
1320     }
1321
1322   /* Because we have to be conservative on the boundaries of source
1323      level units, it is possible that we marked some functions in
1324      reachable just because they might be used later via external
1325      linkage, but after making them local they are really unreachable
1326      now.  */
1327   cgraph_remove_unreachable_nodes (true, cgraph_dump_file);
1328
1329   if (cgraph_dump_file)
1330     {
1331       fprintf (cgraph_dump_file, "\nMarking local functions:");
1332       for (node = cgraph_nodes; node; node = node->next)
1333         if (node->local.local)
1334           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1335       fprintf (cgraph_dump_file, "\n\n");
1336       fprintf (cgraph_dump_file, "\nMarking externally visible functions:");
1337       for (node = cgraph_nodes; node; node = node->next)
1338         if (node->local.externally_visible)
1339           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1340       fprintf (cgraph_dump_file, "\n\n");
1341     }
1342   cgraph_function_flags_ready = true;
1343 }
1344
1345 /* Return true when function body of DECL still needs to be kept around
1346    for later re-use.  */
1347 bool
1348 cgraph_preserve_function_body_p (tree decl)
1349 {
1350   struct cgraph_node *node;
1351   if (!cgraph_global_info_ready)
1352     return (flag_really_no_inline
1353             ? lang_hooks.tree_inlining.disregard_inline_limits (decl)
1354             : DECL_INLINE (decl));
1355   /* Look if there is any clone around.  */
1356   for (node = cgraph_node (decl); node; node = node->next_clone)
1357     if (node->global.inlined_to)
1358       return true;
1359   return false;
1360 }
1361
1362 static void
1363 ipa_passes (void)
1364 {
1365   cfun = NULL;
1366   current_function_decl = NULL;
1367   tree_register_cfg_hooks ();
1368   bitmap_obstack_initialize (NULL);
1369   execute_ipa_pass_list (all_ipa_passes);
1370   bitmap_obstack_release (NULL);
1371 }
1372
1373 /* Perform simple optimizations based on callgraph.  */
1374
1375 void
1376 cgraph_optimize (void)
1377 {
1378   if (errorcount || sorrycount)
1379     return;
1380
1381 #ifdef ENABLE_CHECKING
1382   verify_cgraph ();
1383 #endif
1384   if (!flag_unit_at_a_time)
1385     {
1386       cgraph_output_pending_asms ();
1387       varpool_assemble_pending_decls ();
1388       varpool_output_debug_info ();
1389       return;
1390     }
1391
1392   /* Frontend may output common variables after the unit has been finalized.
1393      It is safe to deal with them here as they are always zero initialized.  */
1394   varpool_analyze_pending_decls ();
1395
1396   timevar_push (TV_CGRAPHOPT);
1397   if (!quiet_flag)
1398     fprintf (stderr, "Performing interprocedural optimizations\n");
1399
1400   cgraph_function_and_variable_visibility ();
1401   if (cgraph_dump_file)
1402     {
1403       fprintf (cgraph_dump_file, "Marked ");
1404       dump_cgraph (cgraph_dump_file);
1405     }
1406     
1407   /* Don't run the IPA passes if there was any error or sorry messages.  */
1408   if (errorcount == 0 && sorrycount == 0)
1409     ipa_passes ();
1410
1411   /* This pass remove bodies of extern inline functions we never inlined.
1412      Do this later so other IPA passes see what is really going on.  */
1413   cgraph_remove_unreachable_nodes (false, dump_file);
1414   cgraph_increase_alignment ();
1415   cgraph_global_info_ready = true;
1416   if (cgraph_dump_file)
1417     {
1418       fprintf (cgraph_dump_file, "Optimized ");
1419       dump_cgraph (cgraph_dump_file);
1420       dump_varpool (cgraph_dump_file);
1421     }
1422   timevar_pop (TV_CGRAPHOPT);
1423
1424   /* Output everything.  */
1425   if (!quiet_flag)
1426     fprintf (stderr, "Assembling functions:\n");
1427 #ifdef ENABLE_CHECKING
1428   verify_cgraph ();
1429 #endif
1430
1431   cgraph_mark_functions_to_output ();
1432
1433   if (!flag_toplevel_reorder)
1434     cgraph_output_in_order ();
1435   else
1436     {
1437       cgraph_output_pending_asms ();
1438
1439       cgraph_expand_all_functions ();
1440       varpool_remove_unreferenced_decls ();
1441
1442       varpool_assemble_pending_decls ();
1443       varpool_output_debug_info ();
1444     }
1445
1446   if (cgraph_dump_file)
1447     {
1448       fprintf (cgraph_dump_file, "\nFinal ");
1449       dump_cgraph (cgraph_dump_file);
1450     }
1451 #ifdef ENABLE_CHECKING
1452   verify_cgraph ();
1453   /* Double check that all inline clones are gone and that all
1454      function bodies have been released from memory.  */
1455   if (flag_unit_at_a_time
1456       && !(sorrycount || errorcount))
1457     {
1458       struct cgraph_node *node;
1459       bool error_found = false;
1460
1461       for (node = cgraph_nodes; node; node = node->next)
1462         if (node->analyzed
1463             && (node->global.inlined_to
1464                 || DECL_SAVED_TREE (node->decl)))
1465           {
1466             error_found = true;
1467             dump_cgraph_node (stderr, node);
1468           }
1469       if (error_found)
1470         internal_error ("nodes with no released memory found");
1471     }
1472 #endif
1473 }
1474
1475 /* Increase alignment of global arrays to improve vectorization potential.
1476    TODO:
1477    - Consider also structs that have an array field.
1478    - Use ipa analysis to prune arrays that can't be vectorized?
1479      This should involve global alignment analysis and in the future also
1480      array padding.  */
1481
1482 static void
1483 cgraph_increase_alignment (void)
1484 {
1485   if (flag_section_anchors && flag_tree_vectorize)
1486     {
1487       struct varpool_node *vnode;
1488
1489       /* Increase the alignment of all global arrays for vectorization.  */
1490       for (vnode = varpool_nodes_queue;
1491            vnode;
1492            vnode = vnode->next_needed)
1493         {
1494           tree vectype, decl = vnode->decl;
1495           unsigned int alignment;
1496
1497           if (TREE_CODE (TREE_TYPE (decl)) != ARRAY_TYPE)
1498             continue;
1499           vectype = get_vectype_for_scalar_type (TREE_TYPE (TREE_TYPE (decl)));
1500           if (!vectype)
1501             continue;
1502           alignment = TYPE_ALIGN (vectype);
1503           if (DECL_ALIGN (decl) >= alignment)
1504             continue;
1505
1506           if (vect_can_force_dr_alignment_p (decl, alignment))
1507             { 
1508               DECL_ALIGN (decl) = TYPE_ALIGN (vectype);
1509               DECL_USER_ALIGN (decl) = 1;
1510               if (cgraph_dump_file)
1511                 { 
1512                   fprintf (cgraph_dump_file, "Increasing alignment of decl: ");
1513                   print_generic_expr (cgraph_dump_file, decl, TDF_SLIM);
1514                 }
1515             }
1516         }
1517     }
1518 }
1519
1520 /* Generate and emit a static constructor or destructor.  WHICH must be
1521    one of 'I' or 'D'.  BODY should be a STATEMENT_LIST containing
1522    GENERIC statements.  */
1523
1524 void
1525 cgraph_build_static_cdtor (char which, tree body, int priority)
1526 {
1527   static int counter = 0;
1528   char which_buf[16];
1529   tree decl, name, resdecl;
1530
1531   sprintf (which_buf, "%c_%d", which, counter++);
1532   name = get_file_function_name (which_buf);
1533
1534   decl = build_decl (FUNCTION_DECL, name,
1535                      build_function_type (void_type_node, void_list_node));
1536   current_function_decl = decl;
1537
1538   resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1539   DECL_ARTIFICIAL (resdecl) = 1;
1540   DECL_IGNORED_P (resdecl) = 1;
1541   DECL_RESULT (decl) = resdecl;
1542
1543   allocate_struct_function (decl);
1544
1545   TREE_STATIC (decl) = 1;
1546   TREE_USED (decl) = 1;
1547   DECL_ARTIFICIAL (decl) = 1;
1548   DECL_IGNORED_P (decl) = 1;
1549   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1550   DECL_SAVED_TREE (decl) = body;
1551   TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1552   DECL_UNINLINABLE (decl) = 1;
1553
1554   DECL_INITIAL (decl) = make_node (BLOCK);
1555   TREE_USED (DECL_INITIAL (decl)) = 1;
1556
1557   DECL_SOURCE_LOCATION (decl) = input_location;
1558   cfun->function_end_locus = input_location;
1559
1560   switch (which)
1561     {
1562     case 'I':
1563       DECL_STATIC_CONSTRUCTOR (decl) = 1;
1564       break;
1565     case 'D':
1566       DECL_STATIC_DESTRUCTOR (decl) = 1;
1567       break;
1568     default:
1569       gcc_unreachable ();
1570     }
1571
1572   gimplify_function_tree (decl);
1573
1574   /* ??? We will get called LATE in the compilation process.  */
1575   if (cgraph_global_info_ready)
1576     {
1577       tree_lowering_passes (decl);
1578       tree_rest_of_compilation (decl);
1579     }
1580   else
1581     cgraph_finalize_function (decl, 0);
1582
1583   if (targetm.have_ctors_dtors)
1584     {
1585       void (*fn) (rtx, int);
1586
1587       if (which == 'I')
1588         fn = targetm.asm_out.constructor;
1589       else
1590         fn = targetm.asm_out.destructor;
1591       fn (XEXP (DECL_RTL (decl), 0), priority);
1592     }
1593 }
1594
1595 void
1596 init_cgraph (void)
1597 {
1598   cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1599 }
1600
1601 /* The edges representing the callers of the NEW_VERSION node were
1602    fixed by cgraph_function_versioning (), now the call_expr in their
1603    respective tree code should be updated to call the NEW_VERSION.  */
1604
1605 static void
1606 update_call_expr (struct cgraph_node *new_version)
1607 {
1608   struct cgraph_edge *e;
1609
1610   gcc_assert (new_version);
1611   for (e = new_version->callers; e; e = e->next_caller)
1612     /* Update the call expr on the edges
1613        to call the new version.  */
1614     TREE_OPERAND (TREE_OPERAND (get_call_expr_in (e->call_stmt), 0), 0) = new_version->decl;
1615 }
1616
1617
1618 /* Create a new cgraph node which is the new version of
1619    OLD_VERSION node.  REDIRECT_CALLERS holds the callers
1620    edges which should be redirected to point to
1621    NEW_VERSION.  ALL the callees edges of OLD_VERSION
1622    are cloned to the new version node.  Return the new
1623    version node.  */
1624
1625 static struct cgraph_node *
1626 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1627                                  tree new_decl,
1628                                  VEC(cgraph_edge_p,heap) *redirect_callers)
1629  {
1630    struct cgraph_node *new_version;
1631    struct cgraph_edge *e, *new_e;
1632    struct cgraph_edge *next_callee;
1633    unsigned i;
1634
1635    gcc_assert (old_version);
1636
1637    new_version = cgraph_node (new_decl);
1638
1639    new_version->analyzed = true;
1640    new_version->local = old_version->local;
1641    new_version->global = old_version->global;
1642    new_version->rtl = new_version->rtl;
1643    new_version->reachable = true;
1644    new_version->count = old_version->count;
1645
1646    /* Clone the old node callees.  Recursive calls are
1647       also cloned.  */
1648    for (e = old_version->callees;e; e=e->next_callee)
1649      {
1650        new_e = cgraph_clone_edge (e, new_version, e->call_stmt, 0, e->loop_nest, true);
1651        new_e->count = e->count;
1652      }
1653    /* Fix recursive calls.
1654       If OLD_VERSION has a recursive call after the
1655       previous edge cloning, the new version will have an edge
1656       pointing to the old version, which is wrong;
1657       Redirect it to point to the new version. */
1658    for (e = new_version->callees ; e; e = next_callee)
1659      {
1660        next_callee = e->next_callee;
1661        if (e->callee == old_version)
1662          cgraph_redirect_edge_callee (e, new_version);
1663
1664        if (!next_callee)
1665          break;
1666      }
1667    for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
1668      {
1669        /* Redirect calls to the old version node to point to its new
1670           version.  */
1671        cgraph_redirect_edge_callee (e, new_version);
1672      }
1673
1674    return new_version;
1675  }
1676
1677  /* Perform function versioning.
1678     Function versioning includes copying of the tree and
1679     a callgraph update (creating a new cgraph node and updating
1680     its callees and callers).
1681
1682     REDIRECT_CALLERS varray includes the edges to be redirected
1683     to the new version.
1684
1685     TREE_MAP is a mapping of tree nodes we want to replace with
1686     new ones (according to results of prior analysis).
1687     OLD_VERSION_NODE is the node that is versioned.
1688     It returns the new version's cgraph node.  */
1689
1690 struct cgraph_node *
1691 cgraph_function_versioning (struct cgraph_node *old_version_node,
1692                             VEC(cgraph_edge_p,heap) *redirect_callers,
1693                             varray_type tree_map)
1694 {
1695   tree old_decl = old_version_node->decl;
1696   struct cgraph_node *new_version_node = NULL;
1697   tree new_decl;
1698
1699   if (!tree_versionable_function_p (old_decl))
1700     return NULL;
1701
1702   /* Make a new FUNCTION_DECL tree node for the
1703      new version. */
1704   new_decl = copy_node (old_decl);
1705
1706   /* Create the new version's call-graph node.
1707      and update the edges of the new node. */
1708   new_version_node =
1709     cgraph_copy_node_for_versioning (old_version_node, new_decl,
1710                                      redirect_callers);
1711
1712   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1713   tree_function_versioning (old_decl, new_decl, tree_map, false);
1714   /* Update the call_expr on the edges to call the new version node. */
1715   update_call_expr (new_version_node);
1716
1717   /* Update the new version's properties.
1718      Make The new version visible only within this translation unit.
1719      ??? We cannot use COMDAT linkage because there is no
1720      ABI support for this.  */
1721   DECL_EXTERNAL (new_version_node->decl) = 0;
1722   DECL_ONE_ONLY (new_version_node->decl) = 0;
1723   TREE_PUBLIC (new_version_node->decl) = 0;
1724   DECL_COMDAT (new_version_node->decl) = 0;
1725   new_version_node->local.externally_visible = 0;
1726   new_version_node->local.local = 1;
1727   new_version_node->lowered = true;
1728   return new_version_node;
1729 }
1730
1731 /* Produce separate function body for inline clones so the offline copy can be
1732    modified without affecting them.  */
1733 struct cgraph_node *
1734 save_inline_function_body (struct cgraph_node *node)
1735 {
1736   struct cgraph_node *first_clone;
1737
1738   gcc_assert (node == cgraph_node (node->decl));
1739
1740   cgraph_lower_function (node);
1741
1742   /* In non-unit-at-a-time we construct full fledged clone we never output to
1743      assembly file.  This clone is pointed out by inline_decl of original function
1744      and inlining infrastructure knows how to deal with this.  */
1745   if (!flag_unit_at_a_time)
1746     {
1747       struct cgraph_edge *e;
1748
1749       first_clone = cgraph_clone_node (node, node->count, 0, false);
1750       first_clone->needed = 0;
1751       first_clone->reachable = 1;
1752       /* Recursively clone all bodies.  */
1753       for (e = first_clone->callees; e; e = e->next_callee)
1754         if (!e->inline_failed)
1755           cgraph_clone_inlined_nodes (e, true, false);
1756     }
1757   else
1758     first_clone = node->next_clone;
1759
1760   first_clone->decl = copy_node (node->decl);
1761   node->next_clone = NULL;
1762   if (!flag_unit_at_a_time)
1763     node->inline_decl = first_clone->decl;
1764   first_clone->prev_clone = NULL;
1765   cgraph_insert_node_to_hashtable (first_clone);
1766   gcc_assert (first_clone == cgraph_node (first_clone->decl));
1767
1768   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1769   tree_function_versioning (node->decl, first_clone->decl, NULL, true);
1770
1771   DECL_EXTERNAL (first_clone->decl) = 0;
1772   DECL_ONE_ONLY (first_clone->decl) = 0;
1773   TREE_PUBLIC (first_clone->decl) = 0;
1774   DECL_COMDAT (first_clone->decl) = 0;
1775
1776   for (node = first_clone->next_clone; node; node = node->next_clone)
1777     node->decl = first_clone->decl;
1778 #ifdef ENABLE_CHECKING
1779   verify_cgraph_node (first_clone);
1780 #endif
1781   return first_clone;
1782 }