OSDN Git Service

* cgraph.c (cgraph_release_function_body): Update use of
[pf3gnuchains/gcc-fork.git] / gcc / cgraphunit.c
1 /* Callgraph based interprocedural optimizations.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3    Free Software Foundation, Inc.
4    Contributed by Jan Hubicka
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
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 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         Analyzing of all functions is deferred
81         to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
82
83         In cgraph_finalize_compilation_unit the reachable functions are
84         analyzed.  During analysis the call-graph edges from reachable
85         functions are constructed and their destinations are marked as
86         reachable.  References to functions and variables are discovered too
87         and variables found to be needed output to the assembly file.  Via
88         mark_referenced call in assemble_variable functions referenced by
89         static variables are noticed too.
90
91         The intra-procedural information is produced and its existence
92         indicated by global_info_ready.  Once this flag is set it is impossible
93         to change function from !reachable to reachable and thus
94         assemble_variable no longer call mark_referenced.
95
96         Finally the call-graph is topologically sorted and all reachable functions
97         that has not been completely inlined or are not external are output.
98
99         ??? It is possible that reference to function or variable is optimized
100         out.  We can not deal with this nicely because topological order is not
101         suitable for it.  For tree-ssa we may consider another pass doing
102         optimization and re-discovering reachable functions.
103
104         ??? Reorganize code so variables are output very last and only if they
105         really has been referenced by produced code, so we catch more cases
106         where reference has been optimized out.  */
107
108
109 #include "config.h"
110 #include "system.h"
111 #include "coretypes.h"
112 #include "tm.h"
113 #include "tree.h"
114 #include "rtl.h"
115 #include "tree-flow.h"
116 #include "tree-inline.h"
117 #include "langhooks.h"
118 #include "pointer-set.h"
119 #include "toplev.h"
120 #include "flags.h"
121 #include "ggc.h"
122 #include "debug.h"
123 #include "target.h"
124 #include "cgraph.h"
125 #include "diagnostic.h"
126 #include "timevar.h"
127 #include "params.h"
128 #include "fibheap.h"
129 #include "intl.h"
130 #include "function.h"
131 #include "ipa-prop.h"
132 #include "gimple.h"
133 #include "tree-iterator.h"
134 #include "tree-pass.h"
135 #include "tree-dump.h"
136 #include "output.h"
137 #include "coverage.h"
138
139 static void cgraph_expand_all_functions (void);
140 static void cgraph_mark_functions_to_output (void);
141 static void cgraph_expand_function (struct cgraph_node *);
142 static void cgraph_output_pending_asms (void);
143 static void cgraph_analyze_function (struct cgraph_node *);
144
145 static FILE *cgraph_dump_file;
146
147 /* A vector of FUNCTION_DECLs declared as static constructors.  */
148 static GTY (()) VEC(tree, gc) *static_ctors;
149 /* A vector of FUNCTION_DECLs declared as static destructors.  */
150 static GTY (()) VEC(tree, gc) *static_dtors;
151
152 /* When target does not have ctors and dtors, we call all constructor
153    and destructor by special initialization/destruction function
154    recognized by collect2.  
155    
156    When we are going to build this function, collect all constructors and
157    destructors and turn them into normal functions.  */
158
159 static void
160 record_cdtor_fn (tree fndecl)
161 {
162   struct cgraph_node *node;
163   if (targetm.have_ctors_dtors
164       || (!DECL_STATIC_CONSTRUCTOR (fndecl)
165           && !DECL_STATIC_DESTRUCTOR (fndecl)))
166     return;
167
168   if (DECL_STATIC_CONSTRUCTOR (fndecl))
169     {
170       VEC_safe_push (tree, gc, static_ctors, fndecl);
171       DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
172     }
173   if (DECL_STATIC_DESTRUCTOR (fndecl))
174     {
175       VEC_safe_push (tree, gc, static_dtors, fndecl);
176       DECL_STATIC_DESTRUCTOR (fndecl) = 0;
177     }
178   node = cgraph_node (fndecl);
179   node->local.disregard_inline_limits = 1;
180   cgraph_mark_reachable_node (node);
181 }
182
183 /* Define global constructors/destructor functions for the CDTORS, of
184    which they are LEN.  The CDTORS are sorted by initialization
185    priority.  If CTOR_P is true, these are constructors; otherwise,
186    they are destructors.  */
187
188 static void
189 build_cdtor (bool ctor_p, tree *cdtors, size_t len)
190 {
191   size_t i;
192
193   i = 0;
194   while (i < len)
195     {
196       tree body;
197       tree fn;
198       priority_type priority;
199
200       priority = 0;
201       body = NULL_TREE;
202       /* Find the next batch of constructors/destructors with the same
203          initialization priority.  */
204       do
205         {
206           priority_type p;
207           fn = cdtors[i];
208           p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
209           if (!body)
210             priority = p;
211           else if (p != priority)
212             break;
213           append_to_statement_list (build_function_call_expr (UNKNOWN_LOCATION,
214                                                               fn, 0),
215                                     &body);
216           ++i;
217         }
218       while (i < len);
219       gcc_assert (body != NULL_TREE);
220       /* Generate a function to call all the function of like
221          priority.  */
222       cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
223     }
224 }
225
226 /* Comparison function for qsort.  P1 and P2 are actually of type
227    "tree *" and point to static constructors.  DECL_INIT_PRIORITY is
228    used to determine the sort order.  */
229
230 static int
231 compare_ctor (const void *p1, const void *p2)
232 {
233   tree f1;
234   tree f2;
235   int priority1;
236   int priority2;
237
238   f1 = *(const tree *)p1;
239   f2 = *(const tree *)p2;
240   priority1 = DECL_INIT_PRIORITY (f1);
241   priority2 = DECL_INIT_PRIORITY (f2);
242   
243   if (priority1 < priority2)
244     return -1;
245   else if (priority1 > priority2)
246     return 1;
247   else
248     /* Ensure a stable sort.  */
249     return (const tree *)p1 - (const tree *)p2;
250 }
251
252 /* Comparison function for qsort.  P1 and P2 are actually of type
253    "tree *" and point to static destructors.  DECL_FINI_PRIORITY is
254    used to determine the sort order.  */
255
256 static int
257 compare_dtor (const void *p1, const void *p2)
258 {
259   tree f1;
260   tree f2;
261   int priority1;
262   int priority2;
263
264   f1 = *(const tree *)p1;
265   f2 = *(const tree *)p2;
266   priority1 = DECL_FINI_PRIORITY (f1);
267   priority2 = DECL_FINI_PRIORITY (f2);
268   
269   if (priority1 < priority2)
270     return -1;
271   else if (priority1 > priority2)
272     return 1;
273   else
274     /* Ensure a stable sort.  */
275     return (const tree *)p1 - (const tree *)p2;
276 }
277
278 /* Generate functions to call static constructors and destructors
279    for targets that do not support .ctors/.dtors sections.  These
280    functions have magic names which are detected by collect2.  */
281
282 static void
283 cgraph_build_cdtor_fns (void)
284 {
285   if (!VEC_empty (tree, static_ctors))
286     {
287       gcc_assert (!targetm.have_ctors_dtors);
288       qsort (VEC_address (tree, static_ctors),
289              VEC_length (tree, static_ctors), 
290              sizeof (tree),
291              compare_ctor);
292       build_cdtor (/*ctor_p=*/true,
293                    VEC_address (tree, static_ctors),
294                    VEC_length (tree, static_ctors)); 
295       VEC_truncate (tree, static_ctors, 0);
296     }
297
298   if (!VEC_empty (tree, static_dtors))
299     {
300       gcc_assert (!targetm.have_ctors_dtors);
301       qsort (VEC_address (tree, static_dtors),
302              VEC_length (tree, static_dtors), 
303              sizeof (tree),
304              compare_dtor);
305       build_cdtor (/*ctor_p=*/false,
306                    VEC_address (tree, static_dtors),
307                    VEC_length (tree, static_dtors)); 
308       VEC_truncate (tree, static_dtors, 0);
309     }
310 }
311
312 /* Determine if function DECL is needed.  That is, visible to something
313    either outside this translation unit, something magic in the system
314    configury.  */
315
316 bool
317 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
318 {
319   /* If the user told us it is used, then it must be so.  */
320   if (node->local.externally_visible)
321     return true;
322
323   /* ??? If the assembler name is set by hand, it is possible to assemble
324      the name later after finalizing the function and the fact is noticed
325      in assemble_name then.  This is arguably a bug.  */
326   if (DECL_ASSEMBLER_NAME_SET_P (decl)
327       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
328     return true;
329
330   /* With -fkeep-inline-functions we are keeping all inline functions except
331      for extern inline ones.  */
332   if (flag_keep_inline_functions
333       && DECL_DECLARED_INLINE_P (decl)
334       && !DECL_EXTERNAL (decl)
335       && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
336      return true;
337
338   /* If we decided it was needed before, but at the time we didn't have
339      the body of the function available, then it's still needed.  We have
340      to go back and re-check its dependencies now.  */
341   if (node->needed)
342     return true;
343
344   /* Externally visible functions must be output.  The exception is
345      COMDAT functions that must be output only when they are needed.
346
347      When not optimizing, also output the static functions. (see
348      PR24561), but don't do so for always_inline functions, functions
349      declared inline and nested functions.  These was optimized out
350      in the original implementation and it is unclear whether we want
351      to change the behavior here.  */
352   if (((TREE_PUBLIC (decl)
353         || (!optimize && !node->local.disregard_inline_limits
354             && !DECL_DECLARED_INLINE_P (decl)
355             && !node->origin))
356        && !flag_whole_program
357        && !flag_lto
358        && !flag_whopr)
359       && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
360     return true;
361
362   /* Constructors and destructors are reachable from the runtime by
363      some mechanism.  */
364   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
365     return true;
366
367   return false;
368 }
369
370 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
371    functions into callgraph in a way so they look like ordinary reachable
372    functions inserted into callgraph already at construction time.  */
373
374 bool
375 cgraph_process_new_functions (void)
376 {
377   bool output = false;
378   tree fndecl;
379   struct cgraph_node *node;
380
381   /*  Note that this queue may grow as its being processed, as the new
382       functions may generate new ones.  */
383   while (cgraph_new_nodes)
384     {
385       node = cgraph_new_nodes;
386       fndecl = node->decl;
387       cgraph_new_nodes = cgraph_new_nodes->next_needed;
388       switch (cgraph_state)
389         {
390         case CGRAPH_STATE_CONSTRUCTION:
391           /* At construction time we just need to finalize function and move
392              it into reachable functions list.  */
393
394           node->next_needed = NULL;
395           cgraph_finalize_function (fndecl, false);
396           cgraph_mark_reachable_node (node);
397           output = true;
398           break;
399
400         case CGRAPH_STATE_IPA:
401         case CGRAPH_STATE_IPA_SSA:
402           /* When IPA optimization already started, do all essential
403              transformations that has been already performed on the whole
404              cgraph but not on this function.  */
405
406           gimple_register_cfg_hooks ();
407           if (!node->analyzed)
408             cgraph_analyze_function (node);
409           push_cfun (DECL_STRUCT_FUNCTION (fndecl));
410           current_function_decl = fndecl;
411           compute_inline_parameters (node);
412           if ((cgraph_state == CGRAPH_STATE_IPA_SSA
413               && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
414               /* When not optimizing, be sure we run early local passes anyway
415                  to expand OMP.  */
416               || !optimize)
417             execute_pass_list (pass_early_local_passes.pass.sub);
418           free_dominance_info (CDI_POST_DOMINATORS);
419           free_dominance_info (CDI_DOMINATORS);
420           pop_cfun ();
421           current_function_decl = NULL;
422           break;
423
424         case CGRAPH_STATE_EXPANSION:
425           /* Functions created during expansion shall be compiled
426              directly.  */
427           node->process = 0;
428           cgraph_expand_function (node);
429           break;
430
431         default:
432           gcc_unreachable ();
433           break;
434         }
435       cgraph_call_function_insertion_hooks (node);
436     }
437   return output;
438 }
439
440 /* As an GCC extension we allow redefinition of the function.  The
441    semantics when both copies of bodies differ is not well defined.
442    We replace the old body with new body so in unit at a time mode
443    we always use new body, while in normal mode we may end up with
444    old body inlined into some functions and new body expanded and
445    inlined in others.
446
447    ??? It may make more sense to use one body for inlining and other
448    body for expanding the function but this is difficult to do.  */
449
450 static void
451 cgraph_reset_node (struct cgraph_node *node)
452 {
453   /* If node->process is set, then we have already begun whole-unit analysis.
454      This is *not* testing for whether we've already emitted the function.
455      That case can be sort-of legitimately seen with real function redefinition
456      errors.  I would argue that the front end should never present us with
457      such a case, but don't enforce that for now.  */
458   gcc_assert (!node->process);
459
460   /* Reset our data structures so we can analyze the function again.  */
461   memset (&node->local, 0, sizeof (node->local));
462   memset (&node->global, 0, sizeof (node->global));
463   memset (&node->rtl, 0, sizeof (node->rtl));
464   node->analyzed = false;
465   node->local.redefined_extern_inline = true;
466   node->local.finalized = false;
467
468   cgraph_node_remove_callees (node);
469
470   /* We may need to re-queue the node for assembling in case
471      we already proceeded it and ignored as not needed or got
472      a re-declaration in IMA mode.  */
473   if (node->reachable)
474     {
475       struct cgraph_node *n;
476
477       for (n = cgraph_nodes_queue; n; n = n->next_needed)
478         if (n == node)
479           break;
480       if (!n)
481         node->reachable = 0;
482     }
483 }
484
485 static void
486 cgraph_lower_function (struct cgraph_node *node)
487 {
488   if (node->lowered)
489     return;
490
491   if (node->nested)
492     lower_nested_functions (node->decl);
493   gcc_assert (!node->nested);
494
495   tree_lowering_passes (node->decl);
496   node->lowered = true;
497 }
498
499 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
500    logic in effect.  If NESTED is true, then our caller cannot stand to have
501    the garbage collector run at the moment.  We would need to either create
502    a new GC context, or just not compile right now.  */
503
504 void
505 cgraph_finalize_function (tree decl, bool nested)
506 {
507   struct cgraph_node *node = cgraph_node (decl);
508
509   if (node->local.finalized)
510     cgraph_reset_node (node);
511
512   node->pid = cgraph_max_pid ++;
513   notice_global_symbol (decl);
514   node->local.finalized = true;
515   node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
516   node->finalized_by_frontend = true;
517   record_cdtor_fn (node->decl);
518
519   if (cgraph_decide_is_function_needed (node, decl))
520     cgraph_mark_needed_node (node);
521
522   /* Since we reclaim unreachable nodes at the end of every language
523      level unit, we need to be conservative about possible entry points
524      there.  */
525   if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
526     cgraph_mark_reachable_node (node);
527
528   /* If we've not yet emitted decl, tell the debug info about it.  */
529   if (!TREE_ASM_WRITTEN (decl))
530     (*debug_hooks->deferred_inline_function) (decl);
531
532   /* Possibly warn about unused parameters.  */
533   if (warn_unused_parameter)
534     do_warn_unused_parameter (decl);
535
536   if (!nested)
537     ggc_collect ();
538 }
539
540 /* C99 extern inline keywords allow changing of declaration after function
541    has been finalized.  We need to re-decide if we want to mark the function as
542    needed then.   */
543
544 void
545 cgraph_mark_if_needed (tree decl)
546 {
547   struct cgraph_node *node = cgraph_node (decl);
548   if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
549     cgraph_mark_needed_node (node);
550 }
551
552 /* Return TRUE if NODE2 is equivalent to NODE or its clone.  */
553 static bool
554 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
555 {
556   while (node != node2 && node2)
557     node2 = node2->clone_of;
558   return node2 != NULL;
559 }
560
561 /* Verify cgraph nodes of given cgraph node.  */
562 void
563 verify_cgraph_node (struct cgraph_node *node)
564 {
565   struct cgraph_edge *e;
566   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
567   struct function *saved_cfun = cfun;
568   basic_block this_block;
569   gimple_stmt_iterator gsi;
570   bool error_found = false;
571
572   if (errorcount || sorrycount)
573     return;
574
575   timevar_push (TV_CGRAPH_VERIFY);
576   /* debug_generic_stmt needs correct cfun */
577   set_cfun (this_cfun);
578   for (e = node->callees; e; e = e->next_callee)
579     if (e->aux)
580       {
581         error ("aux field set for edge %s->%s",
582                identifier_to_locale (cgraph_node_name (e->caller)),
583                identifier_to_locale (cgraph_node_name (e->callee)));
584         error_found = true;
585       }
586   if (node->count < 0)
587     {
588       error ("Execution count is negative");
589       error_found = true;
590     }
591   if (node->global.inlined_to && node->local.externally_visible)
592     {
593       error ("Externally visible inline clone");
594       error_found = true;
595     }
596   if (node->global.inlined_to && node->address_taken)
597     {
598       error ("Inline clone with address taken");
599       error_found = true;
600     }
601   if (node->global.inlined_to && node->needed)
602     {
603       error ("Inline clone is needed");
604       error_found = true;
605     }
606   for (e = node->callers; e; e = e->next_caller)
607     {
608       if (e->count < 0)
609         {
610           error ("caller edge count is negative");
611           error_found = true;
612         }
613       if (e->frequency < 0)
614         {
615           error ("caller edge frequency is negative");
616           error_found = true;
617         }
618       if (e->frequency > CGRAPH_FREQ_MAX)
619         {
620           error ("caller edge frequency is too large");
621           error_found = true;
622         }
623       if (!e->inline_failed)
624         {
625           if (node->global.inlined_to
626               != (e->caller->global.inlined_to
627                   ? e->caller->global.inlined_to : e->caller))
628             {
629               error ("inlined_to pointer is wrong");
630               error_found = true;
631             }
632           if (node->callers->next_caller)
633             {
634               error ("multiple inline callers");
635               error_found = true;
636             }
637         }
638       else
639         if (node->global.inlined_to)
640           {
641             error ("inlined_to pointer set for noninline callers");
642             error_found = true;
643           }
644     }
645   if (!node->callers && node->global.inlined_to)
646     {
647       error ("inlined_to pointer is set but no predecessors found");
648       error_found = true;
649     }
650   if (node->global.inlined_to == node)
651     {
652       error ("inlined_to pointer refers to itself");
653       error_found = true;
654     }
655
656   if (!cgraph_node (node->decl))
657     {
658       error ("node not found in cgraph_hash");
659       error_found = true;
660     }
661
662   if (node->clone_of)
663     {
664       struct cgraph_node *n;
665       for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
666         if (n == node)
667           break;
668       if (!n)
669         {
670           error ("node has wrong clone_of");
671           error_found = true;
672         }
673     }
674   if (node->clones)
675     {
676       struct cgraph_node *n;
677       for (n = node->clones; n; n = n->next_sibling_clone)
678         if (n->clone_of != node)
679           break;
680       if (n)
681         {
682           error ("node has wrong clone list");
683           error_found = true;
684         }
685     }
686   if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
687     {
688        error ("node is in clone list but it is not clone");
689        error_found = true;
690     }
691   if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
692     {
693       error ("node has wrong prev_clone pointer");
694       error_found = true;
695     }
696   if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
697     {
698       error ("double linked list of clones corrupted");
699       error_found = true;
700     }
701
702   if (node->analyzed && gimple_has_body_p (node->decl)
703       && !TREE_ASM_WRITTEN (node->decl)
704       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
705       && !flag_wpa)
706     {
707       if (this_cfun->cfg)
708         {
709           /* The nodes we're interested in are never shared, so walk
710              the tree ignoring duplicates.  */
711           struct pointer_set_t *visited_nodes = pointer_set_create ();
712           /* Reach the trees by walking over the CFG, and note the
713              enclosing basic-blocks in the call edges.  */
714           FOR_EACH_BB_FN (this_block, this_cfun)
715             for (gsi = gsi_start_bb (this_block);
716                  !gsi_end_p (gsi);
717                  gsi_next (&gsi))
718               {
719                 gimple stmt = gsi_stmt (gsi);
720                 tree decl;
721                 if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
722                   {
723                     struct cgraph_edge *e = cgraph_edge (node, stmt);
724                     if (e)
725                       {
726                         if (e->aux)
727                           {
728                             error ("shared call_stmt:");
729                             debug_gimple_stmt (stmt);
730                             error_found = true;
731                           }
732                         if (!clone_of_p (cgraph_node (decl), e->callee)
733                             && !e->callee->global.inlined_to)
734                           {
735                             error ("edge points to wrong declaration:");
736                             debug_tree (e->callee->decl);
737                             fprintf (stderr," Instead of:");
738                             debug_tree (decl);
739                           }
740                         e->aux = (void *)1;
741                       }
742                     else
743                       {
744                         error ("missing callgraph edge for call stmt:");
745                         debug_gimple_stmt (stmt);
746                         error_found = true;
747                       }
748                   }
749               }
750           pointer_set_destroy (visited_nodes);
751         }
752       else
753         /* No CFG available?!  */
754         gcc_unreachable ();
755
756       for (e = node->callees; e; e = e->next_callee)
757         {
758           if (!e->aux && !e->indirect_call)
759             {
760               error ("edge %s->%s has no corresponding call_stmt",
761                      identifier_to_locale (cgraph_node_name (e->caller)),
762                      identifier_to_locale (cgraph_node_name (e->callee)));
763               debug_gimple_stmt (e->call_stmt);
764               error_found = true;
765             }
766           e->aux = 0;
767         }
768     }
769   if (error_found)
770     {
771       dump_cgraph_node (stderr, node);
772       internal_error ("verify_cgraph_node failed");
773     }
774   set_cfun (saved_cfun);
775   timevar_pop (TV_CGRAPH_VERIFY);
776 }
777
778 /* Verify whole cgraph structure.  */
779 void
780 verify_cgraph (void)
781 {
782   struct cgraph_node *node;
783
784   if (sorrycount || errorcount)
785     return;
786
787   for (node = cgraph_nodes; node; node = node->next)
788     verify_cgraph_node (node);
789 }
790
791 /* Output all asm statements we have stored up to be output.  */
792
793 static void
794 cgraph_output_pending_asms (void)
795 {
796   struct cgraph_asm_node *can;
797
798   if (errorcount || sorrycount)
799     return;
800
801   for (can = cgraph_asm_nodes; can; can = can->next)
802     assemble_asm (can->asm_str);
803   cgraph_asm_nodes = NULL;
804 }
805
806 /* Analyze the function scheduled to be output.  */
807 static void
808 cgraph_analyze_function (struct cgraph_node *node)
809 {
810   tree save = current_function_decl;
811   tree decl = node->decl;
812
813   current_function_decl = decl;
814   push_cfun (DECL_STRUCT_FUNCTION (decl));
815
816   /* Make sure to gimplify bodies only once.  During analyzing a
817      function we lower it, which will require gimplified nested
818      functions, so we can end up here with an already gimplified
819      body.  */
820   if (!gimple_body (decl))
821     gimplify_function_tree (decl);
822   dump_function (TDI_generic, decl);
823
824   cgraph_lower_function (node);
825   node->analyzed = true;
826
827   pop_cfun ();
828   current_function_decl = save;
829 }
830
831 /* Look for externally_visible and used attributes and mark cgraph nodes
832    accordingly.
833
834    We cannot mark the nodes at the point the attributes are processed (in
835    handle_*_attribute) because the copy of the declarations available at that
836    point may not be canonical.  For example, in:
837
838     void f();
839     void f() __attribute__((used));
840
841    the declaration we see in handle_used_attribute will be the second
842    declaration -- but the front end will subsequently merge that declaration
843    with the original declaration and discard the second declaration.
844
845    Furthermore, we can't mark these nodes in cgraph_finalize_function because:
846
847     void f() {}
848     void f() __attribute__((externally_visible));
849
850    is valid.
851
852    So, we walk the nodes at the end of the translation unit, applying the
853    attributes at that point.  */
854
855 static void
856 process_function_and_variable_attributes (struct cgraph_node *first,
857                                           struct varpool_node *first_var)
858 {
859   struct cgraph_node *node;
860   struct varpool_node *vnode;
861
862   for (node = cgraph_nodes; node != first; node = node->next)
863     {
864       tree decl = node->decl;
865       if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
866         {
867           mark_decl_referenced (decl);
868           if (node->local.finalized)
869              cgraph_mark_needed_node (node);
870         }
871       if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
872         {
873           if (! TREE_PUBLIC (node->decl))
874             warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
875                         "%<externally_visible%>"
876                         " attribute have effect only on public objects");
877           else if (node->local.finalized)
878              cgraph_mark_needed_node (node);
879         }
880     }
881   for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
882     {
883       tree decl = vnode->decl;
884       if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
885         {
886           mark_decl_referenced (decl);
887           vnode->force_output = true;
888           if (vnode->finalized)
889             varpool_mark_needed_node (vnode);
890         }
891       if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
892         {
893           if (! TREE_PUBLIC (vnode->decl))
894             warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
895                         "%<externally_visible%>"
896                         " attribute have effect only on public objects");
897           else if (vnode->finalized)
898             varpool_mark_needed_node (vnode);
899         }
900     }
901 }
902
903 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
904    each reachable functions) and build cgraph.
905    The function can be called multiple times after inserting new nodes
906    into beginning of queue.  Just the new part of queue is re-scanned then.  */
907
908 static void
909 cgraph_analyze_functions (void)
910 {
911   /* Keep track of already processed nodes when called multiple times for
912      intermodule optimization.  */
913   static struct cgraph_node *first_analyzed;
914   struct cgraph_node *first_processed = first_analyzed;
915   static struct varpool_node *first_analyzed_var;
916   struct cgraph_node *node, *next;
917
918   process_function_and_variable_attributes (first_processed,
919                                             first_analyzed_var);
920   first_processed = cgraph_nodes;
921   first_analyzed_var = varpool_nodes;
922   varpool_analyze_pending_decls ();
923   if (cgraph_dump_file)
924     {
925       fprintf (cgraph_dump_file, "Initial entry points:");
926       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
927         if (node->needed)
928           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
929       fprintf (cgraph_dump_file, "\n");
930     }
931   cgraph_process_new_functions ();
932
933   /* Propagate reachability flag and lower representation of all reachable
934      functions.  In the future, lowering will introduce new functions and
935      new entry points on the way (by template instantiation and virtual
936      method table generation for instance).  */
937   while (cgraph_nodes_queue)
938     {
939       struct cgraph_edge *edge;
940       tree decl = cgraph_nodes_queue->decl;
941
942       node = cgraph_nodes_queue;
943       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
944       node->next_needed = NULL;
945
946       /* ??? It is possible to create extern inline function and later using
947          weak alias attribute to kill its body. See
948          gcc.c-torture/compile/20011119-1.c  */
949       if (!DECL_STRUCT_FUNCTION (decl))
950         {
951           cgraph_reset_node (node);
952           continue;
953         }
954
955       if (!node->analyzed)
956         cgraph_analyze_function (node);
957
958       for (edge = node->callees; edge; edge = edge->next_callee)
959         if (!edge->callee->reachable)
960           cgraph_mark_reachable_node (edge->callee);
961
962       /* If decl is a clone of an abstract function, mark that abstract
963          function so that we don't release its body. The DECL_INITIAL() of that
964          abstract function declaration will be later needed to output debug info.  */
965       if (DECL_ABSTRACT_ORIGIN (decl))
966         {
967           struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
968           origin_node->abstract_and_needed = true;
969         }
970
971       /* We finalize local static variables during constructing callgraph
972          edges.  Process their attributes too.  */
973       process_function_and_variable_attributes (first_processed,
974                                                 first_analyzed_var);
975       first_processed = cgraph_nodes;
976       first_analyzed_var = varpool_nodes;
977       varpool_analyze_pending_decls ();
978       cgraph_process_new_functions ();
979     }
980
981   /* Collect entry points to the unit.  */
982   if (cgraph_dump_file)
983     {
984       fprintf (cgraph_dump_file, "Unit entry points:");
985       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
986         if (node->needed)
987           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
988       fprintf (cgraph_dump_file, "\n\nInitial ");
989       dump_cgraph (cgraph_dump_file);
990     }
991
992   if (cgraph_dump_file)
993     fprintf (cgraph_dump_file, "\nReclaiming functions:");
994
995   for (node = cgraph_nodes; node != first_analyzed; node = next)
996     {
997       tree decl = node->decl;
998       next = node->next;
999
1000       if (node->local.finalized && !gimple_has_body_p (decl))
1001         cgraph_reset_node (node);
1002
1003       if (!node->reachable && gimple_has_body_p (decl))
1004         {
1005           if (cgraph_dump_file)
1006             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1007           cgraph_remove_node (node);
1008           continue;
1009         }
1010       else
1011         node->next_needed = NULL;
1012       gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1013       gcc_assert (node->analyzed == node->local.finalized);
1014     }
1015   if (cgraph_dump_file)
1016     {
1017       fprintf (cgraph_dump_file, "\n\nReclaimed ");
1018       dump_cgraph (cgraph_dump_file);
1019     }
1020   first_analyzed = cgraph_nodes;
1021   ggc_collect ();
1022 }
1023
1024
1025 /* Emit thunks for every node in the cgraph.
1026    FIXME: We really ought to emit thunks only for functions that are needed.  */
1027
1028 static void
1029 cgraph_emit_thunks (void)
1030 {
1031   struct cgraph_node *n;
1032
1033   for (n = cgraph_nodes; n; n = n->next)
1034     {
1035       /* Only emit thunks on functions defined in this TU.
1036          Note that this may emit more thunks than strictly necessary.
1037          During optimization some nodes may disappear.  It would be
1038          nice to only emit thunks only for the functions that will be
1039          emitted, but we cannot know that until the inliner and other
1040          IPA passes have run (see the sequencing of the call to
1041          cgraph_mark_functions_to_output in cgraph_optimize).  */
1042       if (n->reachable
1043           && !DECL_EXTERNAL (n->decl))
1044         lang_hooks.callgraph.emit_associated_thunks (n->decl);
1045     }
1046 }
1047
1048
1049 /* Analyze the whole compilation unit once it is parsed completely.  */
1050
1051 void
1052 cgraph_finalize_compilation_unit (void)
1053 {
1054   timevar_push (TV_CGRAPH);
1055
1056   /* Do not skip analyzing the functions if there were errors, we
1057      miss diagnostics for following functions otherwise.  */
1058
1059   /* Emit size functions we didn't inline.  */
1060   finalize_size_functions ();
1061
1062   /* Call functions declared with the "constructor" or "destructor"
1063      attribute.  */
1064   cgraph_build_cdtor_fns ();
1065
1066   /* Mark alias targets necessary and emit diagnostics.  */
1067   finish_aliases_1 ();
1068
1069   if (!quiet_flag)
1070     {
1071       fprintf (stderr, "\nAnalyzing compilation unit\n");
1072       fflush (stderr);
1073     }
1074
1075   /* Gimplify and lower all functions, compute reachability and
1076      remove unreachable nodes.  */
1077   cgraph_analyze_functions ();
1078
1079   /* Emit thunks for reachable nodes, if needed.  */
1080   if (lang_hooks.callgraph.emit_associated_thunks)
1081     cgraph_emit_thunks ();
1082
1083   /* Mark alias targets necessary and emit diagnostics.  */
1084   finish_aliases_1 ();
1085
1086   /* Gimplify and lower thunks.  */
1087   cgraph_analyze_functions ();
1088
1089   /* Finally drive the pass manager.  */
1090   cgraph_optimize ();
1091
1092   timevar_pop (TV_CGRAPH);
1093 }
1094
1095
1096 /* Figure out what functions we want to assemble.  */
1097
1098 static void
1099 cgraph_mark_functions_to_output (void)
1100 {
1101   struct cgraph_node *node;
1102
1103   for (node = cgraph_nodes; node; node = node->next)
1104     {
1105       tree decl = node->decl;
1106       struct cgraph_edge *e;
1107
1108       gcc_assert (!node->process);
1109
1110       for (e = node->callers; e; e = e->next_caller)
1111         if (e->inline_failed)
1112           break;
1113
1114       /* We need to output all local functions that are used and not
1115          always inlined, as well as those that are reachable from
1116          outside the current compilation unit.  */
1117       if (node->analyzed
1118           && !node->global.inlined_to
1119           && (node->needed
1120               || (e && node->reachable))
1121           && !TREE_ASM_WRITTEN (decl)
1122           && !DECL_EXTERNAL (decl))
1123         node->process = 1;
1124       else
1125         {
1126           /* We should've reclaimed all functions that are not needed.  */
1127 #ifdef ENABLE_CHECKING
1128           if (!node->global.inlined_to
1129               && gimple_has_body_p (decl)
1130               && !DECL_EXTERNAL (decl))
1131             {
1132               dump_cgraph_node (stderr, node);
1133               internal_error ("failed to reclaim unneeded function");
1134             }
1135 #endif
1136           gcc_assert (node->global.inlined_to
1137                       || !gimple_has_body_p (decl)
1138                       || DECL_EXTERNAL (decl));
1139
1140         }
1141
1142     }
1143 }
1144
1145 /* Expand function specified by NODE.  */
1146
1147 static void
1148 cgraph_expand_function (struct cgraph_node *node)
1149 {
1150   tree decl = node->decl;
1151
1152   /* We ought to not compile any inline clones.  */
1153   gcc_assert (!node->global.inlined_to);
1154
1155   announce_function (decl);
1156   node->process = 0;
1157
1158   gcc_assert (node->lowered);
1159
1160   /* Generate RTL for the body of DECL.  */
1161   tree_rest_of_compilation (decl);
1162
1163   /* Make sure that BE didn't give up on compiling.  */
1164   gcc_assert (TREE_ASM_WRITTEN (decl));
1165   current_function_decl = NULL;
1166   gcc_assert (!cgraph_preserve_function_body_p (decl));
1167   cgraph_release_function_body (node);
1168   /* Eliminate all call edges.  This is important so the GIMPLE_CALL no longer
1169      points to the dead function body.  */
1170   cgraph_node_remove_callees (node);
1171
1172   cgraph_function_flags_ready = true;
1173 }
1174
1175 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1176
1177 bool
1178 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1179 {
1180   *reason = e->inline_failed;
1181   return !e->inline_failed;
1182 }
1183
1184
1185
1186 /* Expand all functions that must be output.
1187
1188    Attempt to topologically sort the nodes so function is output when
1189    all called functions are already assembled to allow data to be
1190    propagated across the callgraph.  Use a stack to get smaller distance
1191    between a function and its callees (later we may choose to use a more
1192    sophisticated algorithm for function reordering; we will likely want
1193    to use subsections to make the output functions appear in top-down
1194    order).  */
1195
1196 static void
1197 cgraph_expand_all_functions (void)
1198 {
1199   struct cgraph_node *node;
1200   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1201   int order_pos, new_order_pos = 0;
1202   int i;
1203
1204   order_pos = cgraph_postorder (order);
1205   gcc_assert (order_pos == cgraph_n_nodes);
1206
1207   /* Garbage collector may remove inline clones we eliminate during
1208      optimization.  So we must be sure to not reference them.  */
1209   for (i = 0; i < order_pos; i++)
1210     if (order[i]->process)
1211       order[new_order_pos++] = order[i];
1212
1213   for (i = new_order_pos - 1; i >= 0; i--)
1214     {
1215       node = order[i];
1216       if (node->process)
1217         {
1218           gcc_assert (node->reachable);
1219           node->process = 0;
1220           cgraph_expand_function (node);
1221         }
1222     }
1223   cgraph_process_new_functions ();
1224
1225   free (order);
1226
1227 }
1228
1229 /* This is used to sort the node types by the cgraph order number.  */
1230
1231 enum cgraph_order_sort_kind
1232 {
1233   ORDER_UNDEFINED = 0,
1234   ORDER_FUNCTION,
1235   ORDER_VAR,
1236   ORDER_ASM
1237 };
1238
1239 struct cgraph_order_sort
1240 {
1241   enum cgraph_order_sort_kind kind;
1242   union
1243   {
1244     struct cgraph_node *f;
1245     struct varpool_node *v;
1246     struct cgraph_asm_node *a;
1247   } u;
1248 };
1249
1250 /* Output all functions, variables, and asm statements in the order
1251    according to their order fields, which is the order in which they
1252    appeared in the file.  This implements -fno-toplevel-reorder.  In
1253    this mode we may output functions and variables which don't really
1254    need to be output.  */
1255
1256 static void
1257 cgraph_output_in_order (void)
1258 {
1259   int max;
1260   size_t size;
1261   struct cgraph_order_sort *nodes;
1262   int i;
1263   struct cgraph_node *pf;
1264   struct varpool_node *pv;
1265   struct cgraph_asm_node *pa;
1266
1267   max = cgraph_order;
1268   size = max * sizeof (struct cgraph_order_sort);
1269   nodes = (struct cgraph_order_sort *) alloca (size);
1270   memset (nodes, 0, size);
1271
1272   varpool_analyze_pending_decls ();
1273
1274   for (pf = cgraph_nodes; pf; pf = pf->next)
1275     {
1276       if (pf->process)
1277         {
1278           i = pf->order;
1279           gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1280           nodes[i].kind = ORDER_FUNCTION;
1281           nodes[i].u.f = pf;
1282         }
1283     }
1284
1285   for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1286     {
1287       i = pv->order;
1288       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1289       nodes[i].kind = ORDER_VAR;
1290       nodes[i].u.v = pv;
1291     }
1292
1293   for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1294     {
1295       i = pa->order;
1296       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1297       nodes[i].kind = ORDER_ASM;
1298       nodes[i].u.a = pa;
1299     }
1300
1301   /* In toplevel reorder mode we output all statics; mark them as needed.  */
1302   for (i = 0; i < max; ++i)
1303     {
1304       if (nodes[i].kind == ORDER_VAR)
1305         {
1306           varpool_mark_needed_node (nodes[i].u.v);
1307         }
1308     }
1309   varpool_empty_needed_queue ();
1310
1311   for (i = 0; i < max; ++i)
1312     {
1313       switch (nodes[i].kind)
1314         {
1315         case ORDER_FUNCTION:
1316           nodes[i].u.f->process = 0;
1317           cgraph_expand_function (nodes[i].u.f);
1318           break;
1319
1320         case ORDER_VAR:
1321           varpool_assemble_decl (nodes[i].u.v);
1322           break;
1323
1324         case ORDER_ASM:
1325           assemble_asm (nodes[i].u.a->asm_str);
1326           break;
1327
1328         case ORDER_UNDEFINED:
1329           break;
1330
1331         default:
1332           gcc_unreachable ();
1333         }
1334     }
1335
1336   cgraph_asm_nodes = NULL;
1337 }
1338
1339 /* Return true when function body of DECL still needs to be kept around
1340    for later re-use.  */
1341 bool
1342 cgraph_preserve_function_body_p (tree decl)
1343 {
1344   struct cgraph_node *node;
1345
1346   gcc_assert (cgraph_global_info_ready);
1347   /* Look if there is any clone around.  */
1348   node = cgraph_node (decl);
1349   if (node->clones)
1350     return true;
1351   return false;
1352 }
1353
1354 static void
1355 ipa_passes (void)
1356 {
1357   set_cfun (NULL);
1358   current_function_decl = NULL;
1359   gimple_register_cfg_hooks ();
1360   bitmap_obstack_initialize (NULL);
1361
1362   if (!in_lto_p)
1363     execute_ipa_pass_list (all_small_ipa_passes);
1364
1365   /* If pass_all_early_optimizations was not scheduled, the state of
1366      the cgraph will not be properly updated.  Update it now.  */
1367   if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1368     cgraph_state = CGRAPH_STATE_IPA_SSA;
1369
1370   if (!in_lto_p)
1371     {
1372       /* Generate coverage variables and constructors.  */
1373       coverage_finish ();
1374
1375       /* Process new functions added.  */
1376       set_cfun (NULL);
1377       current_function_decl = NULL;
1378       cgraph_process_new_functions ();
1379
1380       execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1381     }
1382   execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1383
1384   if (!in_lto_p)
1385     ipa_write_summaries ();
1386
1387   if (!flag_ltrans)
1388     execute_ipa_pass_list (all_regular_ipa_passes);
1389
1390   bitmap_obstack_release (NULL);
1391 }
1392
1393
1394 /* Perform simple optimizations based on callgraph.  */
1395
1396 void
1397 cgraph_optimize (void)
1398 {
1399   if (errorcount || sorrycount)
1400     return;
1401
1402 #ifdef ENABLE_CHECKING
1403   verify_cgraph ();
1404 #endif
1405
1406   /* Frontend may output common variables after the unit has been finalized.
1407      It is safe to deal with them here as they are always zero initialized.  */
1408   varpool_analyze_pending_decls ();
1409
1410   timevar_push (TV_CGRAPHOPT);
1411   if (pre_ipa_mem_report)
1412     {
1413       fprintf (stderr, "Memory consumption before IPA\n");
1414       dump_memory_report (false);
1415     }
1416   if (!quiet_flag)
1417     fprintf (stderr, "Performing interprocedural optimizations\n");
1418   cgraph_state = CGRAPH_STATE_IPA;
1419
1420   /* Don't run the IPA passes if there was any error or sorry messages.  */
1421   if (errorcount == 0 && sorrycount == 0)
1422     ipa_passes ();
1423
1424   /* Do nothing else if any IPA pass found errors.  */
1425   if (errorcount || sorrycount)
1426     {
1427       timevar_pop (TV_CGRAPHOPT);
1428       return;
1429     }
1430
1431   /* This pass remove bodies of extern inline functions we never inlined.
1432      Do this later so other IPA passes see what is really going on.  */
1433   cgraph_remove_unreachable_nodes (false, dump_file);
1434   cgraph_global_info_ready = true;
1435   if (cgraph_dump_file)
1436     {
1437       fprintf (cgraph_dump_file, "Optimized ");
1438       dump_cgraph (cgraph_dump_file);
1439       dump_varpool (cgraph_dump_file);
1440     }
1441   if (post_ipa_mem_report)
1442     {
1443       fprintf (stderr, "Memory consumption after IPA\n");
1444       dump_memory_report (false);
1445     }
1446   timevar_pop (TV_CGRAPHOPT);
1447
1448   /* Output everything.  */
1449   (*debug_hooks->assembly_start) ();
1450   if (!quiet_flag)
1451     fprintf (stderr, "Assembling functions:\n");
1452 #ifdef ENABLE_CHECKING
1453   verify_cgraph ();
1454 #endif
1455
1456   cgraph_materialize_all_clones ();
1457   cgraph_mark_functions_to_output ();
1458
1459   cgraph_state = CGRAPH_STATE_EXPANSION;
1460   if (!flag_toplevel_reorder)
1461     cgraph_output_in_order ();
1462   else
1463     {
1464       cgraph_output_pending_asms ();
1465
1466       cgraph_expand_all_functions ();
1467       varpool_remove_unreferenced_decls ();
1468
1469       varpool_assemble_pending_decls ();
1470     }
1471   cgraph_process_new_functions ();
1472   cgraph_state = CGRAPH_STATE_FINISHED;
1473
1474   if (cgraph_dump_file)
1475     {
1476       fprintf (cgraph_dump_file, "\nFinal ");
1477       dump_cgraph (cgraph_dump_file);
1478     }
1479 #ifdef ENABLE_CHECKING
1480   verify_cgraph ();
1481   /* Double check that all inline clones are gone and that all
1482      function bodies have been released from memory.  */
1483   if (!(sorrycount || errorcount))
1484     {
1485       struct cgraph_node *node;
1486       bool error_found = false;
1487
1488       for (node = cgraph_nodes; node; node = node->next)
1489         if (node->analyzed
1490             && (node->global.inlined_to
1491                 || gimple_has_body_p (node->decl)))
1492           {
1493             error_found = true;
1494             dump_cgraph_node (stderr, node);
1495           }
1496       if (error_found)
1497         internal_error ("nodes with unreleased memory found");
1498     }
1499 #endif
1500 }
1501
1502
1503 /* Generate and emit a static constructor or destructor.  WHICH must
1504    be one of 'I' (for a constructor) or 'D' (for a destructor).  BODY
1505    is a STATEMENT_LIST containing GENERIC statements.  PRIORITY is the
1506    initialization priority for this constructor or destructor.  */
1507
1508 void
1509 cgraph_build_static_cdtor (char which, tree body, int priority)
1510 {
1511   static int counter = 0;
1512   char which_buf[16];
1513   tree decl, name, resdecl;
1514
1515   /* The priority is encoded in the constructor or destructor name.
1516      collect2 will sort the names and arrange that they are called at
1517      program startup.  */
1518   sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
1519   name = get_file_function_name (which_buf);
1520
1521   decl = build_decl (input_location, FUNCTION_DECL, name,
1522                      build_function_type (void_type_node, void_list_node));
1523   current_function_decl = decl;
1524
1525   resdecl = build_decl (input_location,
1526                         RESULT_DECL, NULL_TREE, void_type_node);
1527   DECL_ARTIFICIAL (resdecl) = 1;
1528   DECL_RESULT (decl) = resdecl;
1529   DECL_CONTEXT (resdecl) = decl;
1530
1531   allocate_struct_function (decl, false);
1532
1533   TREE_STATIC (decl) = 1;
1534   TREE_USED (decl) = 1;
1535   DECL_ARTIFICIAL (decl) = 1;
1536   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1537   DECL_SAVED_TREE (decl) = body;
1538   TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1539   DECL_UNINLINABLE (decl) = 1;
1540
1541   DECL_INITIAL (decl) = make_node (BLOCK);
1542   TREE_USED (DECL_INITIAL (decl)) = 1;
1543
1544   DECL_SOURCE_LOCATION (decl) = input_location;
1545   cfun->function_end_locus = input_location;
1546
1547   switch (which)
1548     {
1549     case 'I':
1550       DECL_STATIC_CONSTRUCTOR (decl) = 1;
1551       decl_init_priority_insert (decl, priority);
1552       break;
1553     case 'D':
1554       DECL_STATIC_DESTRUCTOR (decl) = 1;
1555       decl_fini_priority_insert (decl, priority);
1556       break;
1557     default:
1558       gcc_unreachable ();
1559     }
1560
1561   gimplify_function_tree (decl);
1562
1563   cgraph_add_new_function (decl, false);
1564   cgraph_mark_needed_node (cgraph_node (decl));
1565   set_cfun (NULL);
1566 }
1567
1568 void
1569 init_cgraph (void)
1570 {
1571   cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1572 }
1573
1574 /* The edges representing the callers of the NEW_VERSION node were
1575    fixed by cgraph_function_versioning (), now the call_expr in their
1576    respective tree code should be updated to call the NEW_VERSION.  */
1577
1578 static void
1579 update_call_expr (struct cgraph_node *new_version)
1580 {
1581   struct cgraph_edge *e;
1582
1583   gcc_assert (new_version);
1584
1585   /* Update the call expr on the edges to call the new version.  */
1586   for (e = new_version->callers; e; e = e->next_caller)
1587     {
1588       struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
1589       gimple_call_set_fndecl (e->call_stmt, new_version->decl);
1590       maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
1591     }
1592 }
1593
1594
1595 /* Create a new cgraph node which is the new version of
1596    OLD_VERSION node.  REDIRECT_CALLERS holds the callers
1597    edges which should be redirected to point to
1598    NEW_VERSION.  ALL the callees edges of OLD_VERSION
1599    are cloned to the new version node.  Return the new
1600    version node.  */
1601
1602 static struct cgraph_node *
1603 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1604                                  tree new_decl,
1605                                  VEC(cgraph_edge_p,heap) *redirect_callers)
1606  {
1607    struct cgraph_node *new_version;
1608    struct cgraph_edge *e, *new_e;
1609    struct cgraph_edge *next_callee;
1610    unsigned i;
1611
1612    gcc_assert (old_version);
1613
1614    new_version = cgraph_node (new_decl);
1615
1616    new_version->analyzed = true;
1617    new_version->local = old_version->local;
1618    new_version->global = old_version->global;
1619    new_version->rtl = new_version->rtl;
1620    new_version->reachable = true;
1621    new_version->count = old_version->count;
1622
1623    /* Clone the old node callees.  Recursive calls are
1624       also cloned.  */
1625    for (e = old_version->callees;e; e=e->next_callee)
1626      {
1627        new_e = cgraph_clone_edge (e, new_version, e->call_stmt,
1628                                   e->lto_stmt_uid, 0, e->frequency,
1629                                   e->loop_nest, true);
1630        new_e->count = e->count;
1631      }
1632    /* Fix recursive calls.
1633       If OLD_VERSION has a recursive call after the
1634       previous edge cloning, the new version will have an edge
1635       pointing to the old version, which is wrong;
1636       Redirect it to point to the new version. */
1637    for (e = new_version->callees ; e; e = next_callee)
1638      {
1639        next_callee = e->next_callee;
1640        if (e->callee == old_version)
1641          cgraph_redirect_edge_callee (e, new_version);
1642
1643        if (!next_callee)
1644          break;
1645      }
1646    for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
1647      {
1648        /* Redirect calls to the old version node to point to its new
1649           version.  */
1650        cgraph_redirect_edge_callee (e, new_version);
1651      }
1652
1653    return new_version;
1654  }
1655
1656  /* Perform function versioning.
1657     Function versioning includes copying of the tree and
1658     a callgraph update (creating a new cgraph node and updating
1659     its callees and callers).
1660
1661     REDIRECT_CALLERS varray includes the edges to be redirected
1662     to the new version.
1663
1664     TREE_MAP is a mapping of tree nodes we want to replace with
1665     new ones (according to results of prior analysis).
1666     OLD_VERSION_NODE is the node that is versioned.
1667     It returns the new version's cgraph node. 
1668     ARGS_TO_SKIP lists arguments to be omitted from functions
1669     */
1670
1671 struct cgraph_node *
1672 cgraph_function_versioning (struct cgraph_node *old_version_node,
1673                             VEC(cgraph_edge_p,heap) *redirect_callers,
1674                             VEC (ipa_replace_map_p,gc)* tree_map,
1675                             bitmap args_to_skip)
1676 {
1677   tree old_decl = old_version_node->decl;
1678   struct cgraph_node *new_version_node = NULL;
1679   tree new_decl;
1680
1681   if (!tree_versionable_function_p (old_decl))
1682     return NULL;
1683
1684   /* Make a new FUNCTION_DECL tree node for the
1685      new version. */
1686   if (!args_to_skip)
1687     new_decl = copy_node (old_decl);
1688   else
1689     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
1690
1691   /* Create the new version's call-graph node.
1692      and update the edges of the new node. */
1693   new_version_node =
1694     cgraph_copy_node_for_versioning (old_version_node, new_decl,
1695                                      redirect_callers);
1696
1697   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1698   tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip);
1699
1700   /* Update the new version's properties.
1701      Make The new version visible only within this translation unit.  Make sure
1702      that is not weak also.
1703      ??? We cannot use COMDAT linkage because there is no
1704      ABI support for this.  */
1705   DECL_EXTERNAL (new_version_node->decl) = 0;
1706   DECL_COMDAT_GROUP (new_version_node->decl) = NULL_TREE;
1707   TREE_PUBLIC (new_version_node->decl) = 0;
1708   DECL_COMDAT (new_version_node->decl) = 0;
1709   DECL_WEAK (new_version_node->decl) = 0;
1710   DECL_VIRTUAL_P (new_version_node->decl) = 0;
1711   new_version_node->local.externally_visible = 0;
1712   new_version_node->local.local = 1;
1713   new_version_node->lowered = true;
1714
1715   /* Update the call_expr on the edges to call the new version node. */
1716   update_call_expr (new_version_node);
1717   
1718   cgraph_call_function_insertion_hooks (new_version_node);
1719   return new_version_node;
1720 }
1721
1722 /* Produce separate function body for inline clones so the offline copy can be
1723    modified without affecting them.  */
1724 struct cgraph_node *
1725 save_inline_function_body (struct cgraph_node *node)
1726 {
1727   struct cgraph_node *first_clone, *n;
1728
1729   gcc_assert (node == cgraph_node (node->decl));
1730
1731   cgraph_lower_function (node);
1732
1733   first_clone = node->clones;
1734
1735   first_clone->decl = copy_node (node->decl);
1736   cgraph_insert_node_to_hashtable (first_clone);
1737   gcc_assert (first_clone == cgraph_node (first_clone->decl));
1738   if (first_clone->next_sibling_clone)
1739     {
1740       for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
1741         n->clone_of = first_clone;
1742       n->clone_of = first_clone;
1743       n->next_sibling_clone = first_clone->clones;
1744       if (first_clone->clones)
1745         first_clone->clones->prev_sibling_clone = n;
1746       first_clone->clones = first_clone->next_sibling_clone;
1747       first_clone->next_sibling_clone->prev_sibling_clone = NULL;
1748       first_clone->next_sibling_clone = NULL;
1749       gcc_assert (!first_clone->prev_sibling_clone);
1750     }
1751   first_clone->clone_of = NULL;
1752   node->clones = NULL;
1753
1754   if (first_clone->clones)
1755     for (n = first_clone->clones; n != first_clone;)
1756       {
1757         gcc_assert (n->decl == node->decl);
1758         n->decl = first_clone->decl;
1759         if (n->clones)
1760           n = n->clones;
1761         else if (n->next_sibling_clone)
1762           n = n->next_sibling_clone;
1763         else
1764           {
1765             while (n != first_clone && !n->next_sibling_clone)
1766               n = n->clone_of;
1767             if (n != first_clone)
1768               n = n->next_sibling_clone;
1769           }
1770       }
1771
1772   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1773   tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL);
1774
1775   DECL_EXTERNAL (first_clone->decl) = 0;
1776   DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
1777   TREE_PUBLIC (first_clone->decl) = 0;
1778   DECL_COMDAT (first_clone->decl) = 0;
1779   VEC_free (ipa_opt_pass, heap,
1780             first_clone->ipa_transforms_to_apply);
1781   first_clone->ipa_transforms_to_apply = NULL;
1782
1783 #ifdef ENABLE_CHECKING
1784   verify_cgraph_node (first_clone);
1785 #endif
1786   return first_clone;
1787 }
1788
1789 /* Given virtual clone, turn it into actual clone.  */
1790 static void
1791 cgraph_materialize_clone (struct cgraph_node *node)
1792 {
1793   bitmap_obstack_initialize (NULL);
1794   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1795   tree_function_versioning (node->clone_of->decl, node->decl,
1796                             node->clone.tree_map, true,
1797                             node->clone.args_to_skip);
1798   if (cgraph_dump_file)
1799     {
1800       dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
1801       dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
1802     }
1803
1804   /* Function is no longer clone.  */
1805   if (node->next_sibling_clone)
1806     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1807   if (node->prev_sibling_clone)
1808     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1809   else
1810     node->clone_of->clones = node->next_sibling_clone;
1811   node->next_sibling_clone = NULL;
1812   node->prev_sibling_clone = NULL;
1813   if (!node->clone_of->analyzed && !node->clone_of->clones)
1814     cgraph_remove_node (node->clone_of);
1815   node->clone_of = NULL;
1816   bitmap_obstack_release (NULL);
1817 }
1818
1819 /* Once all functions from compilation unit are in memory, produce all clones
1820    and update all calls.
1821    We might also do this on demand if we don't want to bring all functions to
1822    memory prior compilation, but current WHOPR implementation does that and it is
1823    is bit easier to keep everything right in this order.  */
1824 void
1825 cgraph_materialize_all_clones (void)
1826 {
1827   struct cgraph_node *node;
1828   bool stabilized = false;
1829
1830   if (cgraph_dump_file)
1831     fprintf (cgraph_dump_file, "Materializing clones\n");
1832 #ifdef ENABLE_CHECKING
1833   verify_cgraph ();
1834 #endif
1835
1836   /* We can also do topological order, but number of iterations should be
1837      bounded by number of IPA passes since single IPA pass is probably not
1838      going to create clones of clones it created itself.  */
1839   while (!stabilized)
1840     {
1841       stabilized = true;
1842       for (node = cgraph_nodes; node; node = node->next)
1843         {
1844           if (node->clone_of && node->decl != node->clone_of->decl
1845               && !gimple_has_body_p (node->decl))
1846             {
1847               if (gimple_has_body_p (node->clone_of->decl))
1848                 {
1849                   if (cgraph_dump_file)
1850                     {
1851                       fprintf (cgraph_dump_file, "clonning %s to %s\n",
1852                                cgraph_node_name (node->clone_of),
1853                                cgraph_node_name (node));
1854                       if (node->clone.tree_map)
1855                         {
1856                           unsigned int i;
1857                           fprintf (cgraph_dump_file, "   replace map: ");
1858                           for (i = 0; i < VEC_length (ipa_replace_map_p,
1859                                                       node->clone.tree_map);
1860                                                       i++)
1861                             {
1862                               struct ipa_replace_map *replace_info;
1863                               replace_info = VEC_index (ipa_replace_map_p,
1864                                                         node->clone.tree_map,
1865                                                         i);
1866                               print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
1867                               fprintf (cgraph_dump_file, " -> ");
1868                               print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
1869                               fprintf (cgraph_dump_file, "%s%s;",
1870                                        replace_info->replace_p ? "(replace)":"",
1871                                        replace_info->ref_p ? "(ref)":"");
1872                             }
1873                           fprintf (cgraph_dump_file, "\n");
1874                         }
1875                       if (node->clone.args_to_skip)
1876                         {
1877                           fprintf (cgraph_dump_file, "   args_to_skip: ");
1878                           dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
1879                         }
1880                       if (node->clone.args_to_skip)
1881                         {
1882                           fprintf (cgraph_dump_file, "   combined_args_to_skip:");
1883                           dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
1884                         }
1885                     }
1886                   cgraph_materialize_clone (node);
1887                 }
1888               else
1889                 stabilized = false;
1890             }
1891         }
1892     }
1893   if (cgraph_dump_file)
1894     fprintf (cgraph_dump_file, "Updating call sites\n");
1895   for (node = cgraph_nodes; node; node = node->next)
1896     if (node->analyzed && gimple_has_body_p (node->decl)
1897         && (!node->clone_of || node->clone_of->decl != node->decl))
1898       {
1899         struct cgraph_edge *e;
1900
1901         current_function_decl = node->decl;
1902         push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1903         for (e = node->callees; e; e = e->next_callee)
1904           {
1905             tree decl = gimple_call_fndecl (e->call_stmt);
1906             /* When function gets inlined, indirect inlining might've invented
1907                new edge for orginally indirect stmt.  Since we are not
1908                preserving clones in the original form, we must not update here
1909                since other inline clones don't need to contain call to the same
1910                call.  Inliner will do the substitution for us later.  */
1911             if (decl && decl != e->callee->decl)
1912               {
1913                 gimple new_stmt;
1914                 gimple_stmt_iterator gsi;
1915                 
1916                 if (cgraph_dump_file)
1917                   {
1918                     fprintf (cgraph_dump_file, "updating call of %s in %s:",
1919                              cgraph_node_name (node),
1920                              cgraph_node_name (e->callee));
1921                     print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
1922                   }
1923
1924                 if (e->callee->clone.combined_args_to_skip)
1925                   new_stmt = gimple_call_copy_skip_args (e->call_stmt,
1926                                                          e->callee->clone.combined_args_to_skip);
1927                 else
1928                   new_stmt = e->call_stmt;
1929                 if (gimple_vdef (new_stmt)
1930                     && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
1931                   SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
1932                 gimple_call_set_fndecl (new_stmt, e->callee->decl);
1933
1934                 gsi = gsi_for_stmt (e->call_stmt);
1935                 gsi_replace (&gsi, new_stmt, true);
1936
1937                 /* Update EH information too, just in case.  */
1938                 maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
1939
1940                 cgraph_set_call_stmt_including_clones (node, e->call_stmt, new_stmt);
1941
1942                 if (cgraph_dump_file)
1943                   {
1944                     fprintf (cgraph_dump_file, "  updated to:");
1945                     print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
1946                   }
1947               }
1948           }
1949         pop_cfun ();
1950         current_function_decl = NULL;
1951 #ifdef ENABLE_CHECKING
1952         verify_cgraph_node (node);
1953 #endif
1954       }
1955 #ifdef ENABLE_CHECKING
1956   verify_cgraph ();
1957 #endif
1958   cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
1959 }
1960
1961 #include "gt-cgraphunit.h"