OSDN Git Service

* cgraphunit.c (verify_cgraph_node): Do checking that DECL match
[pf3gnuchains/gcc-fork.git] / gcc / cgraphunit.c
1 /* Callgraph based interprocedural optimizations.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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 "tree-pretty-print.h"
127 #include "gimple-pretty-print.h"
128 #include "timevar.h"
129 #include "params.h"
130 #include "fibheap.h"
131 #include "intl.h"
132 #include "function.h"
133 #include "ipa-prop.h"
134 #include "gimple.h"
135 #include "tree-iterator.h"
136 #include "tree-pass.h"
137 #include "tree-dump.h"
138 #include "output.h"
139 #include "coverage.h"
140 #include "plugin.h"
141
142 static void cgraph_expand_all_functions (void);
143 static void cgraph_mark_functions_to_output (void);
144 static void cgraph_expand_function (struct cgraph_node *);
145 static void cgraph_output_pending_asms (void);
146 static void cgraph_analyze_function (struct cgraph_node *);
147
148 static FILE *cgraph_dump_file;
149
150 /* A vector of FUNCTION_DECLs declared as static constructors.  */
151 static GTY (()) VEC(tree, gc) *static_ctors;
152 /* A vector of FUNCTION_DECLs declared as static destructors.  */
153 static GTY (()) VEC(tree, gc) *static_dtors;
154
155 /* Used for vtable lookup in thunk adjusting.  */
156 static GTY (()) tree vtable_entry_type;
157
158 /* When target does not have ctors and dtors, we call all constructor
159    and destructor by special initialization/destruction function
160    recognized by collect2.
161
162    When we are going to build this function, collect all constructors and
163    destructors and turn them into normal functions.  */
164
165 static void
166 record_cdtor_fn (tree fndecl)
167 {
168   struct cgraph_node *node;
169   if (targetm.have_ctors_dtors
170       || (!DECL_STATIC_CONSTRUCTOR (fndecl)
171           && !DECL_STATIC_DESTRUCTOR (fndecl)))
172     return;
173
174   if (DECL_STATIC_CONSTRUCTOR (fndecl))
175     {
176       VEC_safe_push (tree, gc, static_ctors, fndecl);
177       DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
178     }
179   if (DECL_STATIC_DESTRUCTOR (fndecl))
180     {
181       VEC_safe_push (tree, gc, static_dtors, fndecl);
182       DECL_STATIC_DESTRUCTOR (fndecl) = 0;
183     }
184   node = cgraph_node (fndecl);
185   node->local.disregard_inline_limits = 1;
186   cgraph_mark_reachable_node (node);
187 }
188
189 /* Define global constructors/destructor functions for the CDTORS, of
190    which they are LEN.  The CDTORS are sorted by initialization
191    priority.  If CTOR_P is true, these are constructors; otherwise,
192    they are destructors.  */
193
194 static void
195 build_cdtor (bool ctor_p, tree *cdtors, size_t len)
196 {
197   size_t i;
198
199   i = 0;
200   while (i < len)
201     {
202       tree body;
203       tree fn;
204       priority_type priority;
205
206       priority = 0;
207       body = NULL_TREE;
208       /* Find the next batch of constructors/destructors with the same
209          initialization priority.  */
210       do
211         {
212           priority_type p;
213           fn = cdtors[i];
214           p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
215           if (!body)
216             priority = p;
217           else if (p != priority)
218             break;
219           append_to_statement_list (build_function_call_expr (UNKNOWN_LOCATION,
220                                                               fn, 0),
221                                     &body);
222           ++i;
223         }
224       while (i < len);
225       gcc_assert (body != NULL_TREE);
226       /* Generate a function to call all the function of like
227          priority.  */
228       cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
229     }
230 }
231
232 /* Comparison function for qsort.  P1 and P2 are actually of type
233    "tree *" and point to static constructors.  DECL_INIT_PRIORITY is
234    used to determine the sort order.  */
235
236 static int
237 compare_ctor (const void *p1, const void *p2)
238 {
239   tree f1;
240   tree f2;
241   int priority1;
242   int priority2;
243
244   f1 = *(const tree *)p1;
245   f2 = *(const tree *)p2;
246   priority1 = DECL_INIT_PRIORITY (f1);
247   priority2 = DECL_INIT_PRIORITY (f2);
248
249   if (priority1 < priority2)
250     return -1;
251   else if (priority1 > priority2)
252     return 1;
253   else
254     /* Ensure a stable sort.  */
255     return (const tree *)p1 - (const tree *)p2;
256 }
257
258 /* Comparison function for qsort.  P1 and P2 are actually of type
259    "tree *" and point to static destructors.  DECL_FINI_PRIORITY is
260    used to determine the sort order.  */
261
262 static int
263 compare_dtor (const void *p1, const void *p2)
264 {
265   tree f1;
266   tree f2;
267   int priority1;
268   int priority2;
269
270   f1 = *(const tree *)p1;
271   f2 = *(const tree *)p2;
272   priority1 = DECL_FINI_PRIORITY (f1);
273   priority2 = DECL_FINI_PRIORITY (f2);
274
275   if (priority1 < priority2)
276     return -1;
277   else if (priority1 > priority2)
278     return 1;
279   else
280     /* Ensure a stable sort.  */
281     return (const tree *)p1 - (const tree *)p2;
282 }
283
284 /* Generate functions to call static constructors and destructors
285    for targets that do not support .ctors/.dtors sections.  These
286    functions have magic names which are detected by collect2.  */
287
288 static void
289 cgraph_build_cdtor_fns (void)
290 {
291   if (!VEC_empty (tree, static_ctors))
292     {
293       gcc_assert (!targetm.have_ctors_dtors);
294       qsort (VEC_address (tree, static_ctors),
295              VEC_length (tree, static_ctors),
296              sizeof (tree),
297              compare_ctor);
298       build_cdtor (/*ctor_p=*/true,
299                    VEC_address (tree, static_ctors),
300                    VEC_length (tree, static_ctors));
301       VEC_truncate (tree, static_ctors, 0);
302     }
303
304   if (!VEC_empty (tree, static_dtors))
305     {
306       gcc_assert (!targetm.have_ctors_dtors);
307       qsort (VEC_address (tree, static_dtors),
308              VEC_length (tree, static_dtors),
309              sizeof (tree),
310              compare_dtor);
311       build_cdtor (/*ctor_p=*/false,
312                    VEC_address (tree, static_dtors),
313                    VEC_length (tree, static_dtors));
314       VEC_truncate (tree, static_dtors, 0);
315     }
316 }
317
318 /* Determine if function DECL is needed.  That is, visible to something
319    either outside this translation unit, something magic in the system
320    configury.  */
321
322 bool
323 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
324 {
325   /* If the user told us it is used, then it must be so.  */
326   if (node->local.externally_visible)
327     return true;
328
329   /* ??? If the assembler name is set by hand, it is possible to assemble
330      the name later after finalizing the function and the fact is noticed
331      in assemble_name then.  This is arguably a bug.  */
332   if (DECL_ASSEMBLER_NAME_SET_P (decl)
333       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
334     return true;
335
336   /* With -fkeep-inline-functions we are keeping all inline functions except
337      for extern inline ones.  */
338   if (flag_keep_inline_functions
339       && DECL_DECLARED_INLINE_P (decl)
340       && !DECL_EXTERNAL (decl)
341       && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
342      return true;
343
344   /* If we decided it was needed before, but at the time we didn't have
345      the body of the function available, then it's still needed.  We have
346      to go back and re-check its dependencies now.  */
347   if (node->needed)
348     return true;
349
350   /* Externally visible functions must be output.  The exception is
351      COMDAT functions that must be output only when they are needed.
352
353      When not optimizing, also output the static functions. (see
354      PR24561), but don't do so for always_inline functions, functions
355      declared inline and nested functions.  These was optimized out
356      in the original implementation and it is unclear whether we want
357      to change the behavior here.  */
358   if (((TREE_PUBLIC (decl)
359         || (!optimize && !node->local.disregard_inline_limits
360             && !DECL_DECLARED_INLINE_P (decl)
361             && !node->origin))
362        && !flag_whole_program
363        && !flag_lto
364        && !flag_whopr)
365       && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
366     return true;
367
368   /* Constructors and destructors are reachable from the runtime by
369      some mechanism.  */
370   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
371     return true;
372
373   return false;
374 }
375
376 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
377    functions into callgraph in a way so they look like ordinary reachable
378    functions inserted into callgraph already at construction time.  */
379
380 bool
381 cgraph_process_new_functions (void)
382 {
383   bool output = false;
384   tree fndecl;
385   struct cgraph_node *node;
386
387   varpool_analyze_pending_decls ();
388   /*  Note that this queue may grow as its being processed, as the new
389       functions may generate new ones.  */
390   while (cgraph_new_nodes)
391     {
392       node = cgraph_new_nodes;
393       fndecl = node->decl;
394       cgraph_new_nodes = cgraph_new_nodes->next_needed;
395       switch (cgraph_state)
396         {
397         case CGRAPH_STATE_CONSTRUCTION:
398           /* At construction time we just need to finalize function and move
399              it into reachable functions list.  */
400
401           node->next_needed = NULL;
402           cgraph_finalize_function (fndecl, false);
403           cgraph_mark_reachable_node (node);
404           output = true;
405           break;
406
407         case CGRAPH_STATE_IPA:
408         case CGRAPH_STATE_IPA_SSA:
409           /* When IPA optimization already started, do all essential
410              transformations that has been already performed on the whole
411              cgraph but not on this function.  */
412
413           gimple_register_cfg_hooks ();
414           if (!node->analyzed)
415             cgraph_analyze_function (node);
416           push_cfun (DECL_STRUCT_FUNCTION (fndecl));
417           current_function_decl = fndecl;
418           compute_inline_parameters (node);
419           if ((cgraph_state == CGRAPH_STATE_IPA_SSA
420               && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
421               /* When not optimizing, be sure we run early local passes anyway
422                  to expand OMP.  */
423               || !optimize)
424             execute_pass_list (pass_early_local_passes.pass.sub);
425           free_dominance_info (CDI_POST_DOMINATORS);
426           free_dominance_info (CDI_DOMINATORS);
427           pop_cfun ();
428           current_function_decl = NULL;
429           break;
430
431         case CGRAPH_STATE_EXPANSION:
432           /* Functions created during expansion shall be compiled
433              directly.  */
434           node->process = 0;
435           cgraph_expand_function (node);
436           break;
437
438         default:
439           gcc_unreachable ();
440           break;
441         }
442       cgraph_call_function_insertion_hooks (node);
443       varpool_analyze_pending_decls ();
444     }
445   return output;
446 }
447
448 /* As an GCC extension we allow redefinition of the function.  The
449    semantics when both copies of bodies differ is not well defined.
450    We replace the old body with new body so in unit at a time mode
451    we always use new body, while in normal mode we may end up with
452    old body inlined into some functions and new body expanded and
453    inlined in others.
454
455    ??? It may make more sense to use one body for inlining and other
456    body for expanding the function but this is difficult to do.  */
457
458 static void
459 cgraph_reset_node (struct cgraph_node *node)
460 {
461   /* If node->process is set, then we have already begun whole-unit analysis.
462      This is *not* testing for whether we've already emitted the function.
463      That case can be sort-of legitimately seen with real function redefinition
464      errors.  I would argue that the front end should never present us with
465      such a case, but don't enforce that for now.  */
466   gcc_assert (!node->process);
467
468   /* Reset our data structures so we can analyze the function again.  */
469   memset (&node->local, 0, sizeof (node->local));
470   memset (&node->global, 0, sizeof (node->global));
471   memset (&node->rtl, 0, sizeof (node->rtl));
472   node->analyzed = false;
473   node->local.redefined_extern_inline = true;
474   node->local.finalized = false;
475
476   cgraph_node_remove_callees (node);
477
478   /* We may need to re-queue the node for assembling in case
479      we already proceeded it and ignored as not needed or got
480      a re-declaration in IMA mode.  */
481   if (node->reachable)
482     {
483       struct cgraph_node *n;
484
485       for (n = cgraph_nodes_queue; n; n = n->next_needed)
486         if (n == node)
487           break;
488       if (!n)
489         node->reachable = 0;
490     }
491 }
492
493 static void
494 cgraph_lower_function (struct cgraph_node *node)
495 {
496   if (node->lowered)
497     return;
498
499   if (node->nested)
500     lower_nested_functions (node->decl);
501   gcc_assert (!node->nested);
502
503   tree_lowering_passes (node->decl);
504   node->lowered = true;
505 }
506
507 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
508    logic in effect.  If NESTED is true, then our caller cannot stand to have
509    the garbage collector run at the moment.  We would need to either create
510    a new GC context, or just not compile right now.  */
511
512 void
513 cgraph_finalize_function (tree decl, bool nested)
514 {
515   struct cgraph_node *node = cgraph_node (decl);
516
517   if (node->local.finalized)
518     cgraph_reset_node (node);
519
520   node->pid = cgraph_max_pid ++;
521   notice_global_symbol (decl);
522   node->local.finalized = true;
523   node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
524   node->finalized_by_frontend = true;
525   record_cdtor_fn (node->decl);
526
527   if (cgraph_decide_is_function_needed (node, decl))
528     cgraph_mark_needed_node (node);
529
530   /* Since we reclaim unreachable nodes at the end of every language
531      level unit, we need to be conservative about possible entry points
532      there.  */
533   if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
534     cgraph_mark_reachable_node (node);
535
536   /* If we've not yet emitted decl, tell the debug info about it.  */
537   if (!TREE_ASM_WRITTEN (decl))
538     (*debug_hooks->deferred_inline_function) (decl);
539
540   /* Possibly warn about unused parameters.  */
541   if (warn_unused_parameter)
542     do_warn_unused_parameter (decl);
543
544   if (!nested)
545     ggc_collect ();
546 }
547
548 /* C99 extern inline keywords allow changing of declaration after function
549    has been finalized.  We need to re-decide if we want to mark the function as
550    needed then.   */
551
552 void
553 cgraph_mark_if_needed (tree decl)
554 {
555   struct cgraph_node *node = cgraph_node (decl);
556   if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
557     cgraph_mark_needed_node (node);
558 }
559
560 /* Return TRUE if NODE2 is equivalent to NODE or its clone.  */
561 static bool
562 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
563 {
564   while (node != node2 && node2)
565     node2 = node2->clone_of;
566   return node2 != NULL;
567 }
568
569 /* Verify cgraph nodes of given cgraph node.  */
570 void
571 verify_cgraph_node (struct cgraph_node *node)
572 {
573   struct cgraph_edge *e;
574   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
575   struct function *saved_cfun = cfun;
576   basic_block this_block;
577   gimple_stmt_iterator gsi;
578   bool error_found = false;
579
580   if (errorcount || sorrycount)
581     return;
582
583   timevar_push (TV_CGRAPH_VERIFY);
584   /* debug_generic_stmt needs correct cfun */
585   set_cfun (this_cfun);
586   for (e = node->callees; e; e = e->next_callee)
587     if (e->aux)
588       {
589         error ("aux field set for edge %s->%s",
590                identifier_to_locale (cgraph_node_name (e->caller)),
591                identifier_to_locale (cgraph_node_name (e->callee)));
592         error_found = true;
593       }
594   if (node->count < 0)
595     {
596       error ("Execution count is negative");
597       error_found = true;
598     }
599   if (node->global.inlined_to && node->local.externally_visible)
600     {
601       error ("Externally visible inline clone");
602       error_found = true;
603     }
604   if (node->global.inlined_to && node->address_taken)
605     {
606       error ("Inline clone with address taken");
607       error_found = true;
608     }
609   if (node->global.inlined_to && node->needed)
610     {
611       error ("Inline clone is needed");
612       error_found = true;
613     }
614   for (e = node->indirect_calls; e; e = e->next_callee)
615     {
616       if (e->aux)
617         {
618           error ("aux field set for indirect edge from %s",
619                  identifier_to_locale (cgraph_node_name (e->caller)));
620           error_found = true;
621         }
622       if (!e->indirect_unknown_callee
623           || !e->indirect_info)
624         {
625           error ("An indirect edge from %s is not marked as indirect or has "
626                  "associated indirect_info, the corresponding statement is: ",
627                  identifier_to_locale (cgraph_node_name (e->caller)));
628           debug_gimple_stmt (e->call_stmt);
629           error_found = true;
630         }
631     }
632   for (e = node->callers; e; e = e->next_caller)
633     {
634       if (e->count < 0)
635         {
636           error ("caller edge count is negative");
637           error_found = true;
638         }
639       if (e->frequency < 0)
640         {
641           error ("caller edge frequency is negative");
642           error_found = true;
643         }
644       if (e->frequency > CGRAPH_FREQ_MAX)
645         {
646           error ("caller edge frequency is too large");
647           error_found = true;
648         }
649       if (gimple_has_body_p (e->caller->decl)
650           && !e->caller->global.inlined_to
651           && (e->frequency
652               != compute_call_stmt_bb_frequency (e->caller->decl,
653                                                  gimple_bb (e->call_stmt))))
654         {
655           error ("caller edge frequency %i does not match BB freqency %i",
656                  e->frequency,
657                  compute_call_stmt_bb_frequency (e->caller->decl,
658                                                  gimple_bb (e->call_stmt)));
659           error_found = true;
660         }
661       if (!e->inline_failed)
662         {
663           if (node->global.inlined_to
664               != (e->caller->global.inlined_to
665                   ? e->caller->global.inlined_to : e->caller))
666             {
667               error ("inlined_to pointer is wrong");
668               error_found = true;
669             }
670           if (node->callers->next_caller)
671             {
672               error ("multiple inline callers");
673               error_found = true;
674             }
675         }
676       else
677         if (node->global.inlined_to)
678           {
679             error ("inlined_to pointer set for noninline callers");
680             error_found = true;
681           }
682     }
683   if (!node->callers && node->global.inlined_to)
684     {
685       error ("inlined_to pointer is set but no predecessors found");
686       error_found = true;
687     }
688   if (node->global.inlined_to == node)
689     {
690       error ("inlined_to pointer refers to itself");
691       error_found = true;
692     }
693
694   if (!cgraph_node (node->decl))
695     {
696       error ("node not found in cgraph_hash");
697       error_found = true;
698     }
699
700   if (node->clone_of)
701     {
702       struct cgraph_node *n;
703       for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
704         if (n == node)
705           break;
706       if (!n)
707         {
708           error ("node has wrong clone_of");
709           error_found = true;
710         }
711     }
712   if (node->clones)
713     {
714       struct cgraph_node *n;
715       for (n = node->clones; n; n = n->next_sibling_clone)
716         if (n->clone_of != node)
717           break;
718       if (n)
719         {
720           error ("node has wrong clone list");
721           error_found = true;
722         }
723     }
724   if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
725     {
726        error ("node is in clone list but it is not clone");
727        error_found = true;
728     }
729   if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
730     {
731       error ("node has wrong prev_clone pointer");
732       error_found = true;
733     }
734   if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
735     {
736       error ("double linked list of clones corrupted");
737       error_found = true;
738     }
739   if (node->same_comdat_group)
740     {
741       struct cgraph_node *n = node->same_comdat_group;
742
743       if (!DECL_ONE_ONLY (node->decl))
744         {
745           error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
746           error_found = true;
747         }
748       if (n == node)
749         {
750           error ("node is alone in a comdat group");
751           error_found = true;
752         }
753       do
754         {
755           if (!n->same_comdat_group)
756             {
757               error ("same_comdat_group is not a circular list");
758               error_found = true;
759               break;
760             }
761           n = n->same_comdat_group;
762         }
763       while (n != node);
764     }
765
766   if (node->analyzed && gimple_has_body_p (node->decl)
767       && !TREE_ASM_WRITTEN (node->decl)
768       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
769       && !flag_wpa)
770     {
771       if (this_cfun->cfg)
772         {
773           /* The nodes we're interested in are never shared, so walk
774              the tree ignoring duplicates.  */
775           struct pointer_set_t *visited_nodes = pointer_set_create ();
776           /* Reach the trees by walking over the CFG, and note the
777              enclosing basic-blocks in the call edges.  */
778           FOR_EACH_BB_FN (this_block, this_cfun)
779             for (gsi = gsi_start_bb (this_block);
780                  !gsi_end_p (gsi);
781                  gsi_next (&gsi))
782               {
783                 gimple stmt = gsi_stmt (gsi);
784                 if (is_gimple_call (stmt))
785                   {
786                     struct cgraph_edge *e = cgraph_edge (node, stmt);
787                     tree decl = gimple_call_fndecl (stmt);
788                     if (e)
789                       {
790                         if (e->aux)
791                           {
792                             error ("shared call_stmt:");
793                             debug_gimple_stmt (stmt);
794                             error_found = true;
795                           }
796                         if (!e->indirect_unknown_callee)
797                           {
798                             if (e->callee->same_body_alias)
799                               {
800                                 error ("edge points to same body alias:");
801                                 debug_tree (e->callee->decl);
802                                 error_found = true;
803                               }
804 #ifdef ENABLE_CHECKING
805                             else if (!e->callee->global.inlined_to
806                                      && decl
807                                      && cgraph_get_node (decl)
808                                      && (e->callee->former_clone_of
809                                          != cgraph_get_node (decl)->decl)
810                                      && !clone_of_p (cgraph_node (decl),
811                                                      e->callee))
812                               {
813                                 error ("edge points to wrong declaration:");
814                                 debug_tree (e->callee->decl);
815                                 fprintf (stderr," Instead of:");
816                                 debug_tree (decl);
817                                 error_found = true;
818                               }
819 #endif
820                           }
821                         else if (decl)
822                           {
823                             error ("an indirect edge with unknown callee "
824                                    "corresponding to a call_stmt with "
825                                    "a known declaration:");
826                             error_found = true;
827                             debug_gimple_stmt (e->call_stmt);
828                           }
829                         e->aux = (void *)1;
830                       }
831                     else if (decl)
832                       {
833                         error ("missing callgraph edge for call stmt:");
834                         debug_gimple_stmt (stmt);
835                         error_found = true;
836                       }
837                   }
838               }
839           pointer_set_destroy (visited_nodes);
840         }
841       else
842         /* No CFG available?!  */
843         gcc_unreachable ();
844
845       for (e = node->callees; e; e = e->next_callee)
846         {
847           if (!e->aux)
848             {
849               error ("edge %s->%s has no corresponding call_stmt",
850                      identifier_to_locale (cgraph_node_name (e->caller)),
851                      identifier_to_locale (cgraph_node_name (e->callee)));
852               debug_gimple_stmt (e->call_stmt);
853               error_found = true;
854             }
855           e->aux = 0;
856         }
857       for (e = node->indirect_calls; e; e = e->next_callee)
858         {
859           if (!e->aux)
860             {
861               error ("an indirect edge from %s has no corresponding call_stmt",
862                      identifier_to_locale (cgraph_node_name (e->caller)));
863               debug_gimple_stmt (e->call_stmt);
864               error_found = true;
865             }
866           e->aux = 0;
867         }
868     }
869   if (error_found)
870     {
871       dump_cgraph_node (stderr, node);
872       internal_error ("verify_cgraph_node failed");
873     }
874   set_cfun (saved_cfun);
875   timevar_pop (TV_CGRAPH_VERIFY);
876 }
877
878 /* Verify whole cgraph structure.  */
879 void
880 verify_cgraph (void)
881 {
882   struct cgraph_node *node;
883
884   if (sorrycount || errorcount)
885     return;
886
887   for (node = cgraph_nodes; node; node = node->next)
888     verify_cgraph_node (node);
889 }
890
891 /* Output all asm statements we have stored up to be output.  */
892
893 static void
894 cgraph_output_pending_asms (void)
895 {
896   struct cgraph_asm_node *can;
897
898   if (errorcount || sorrycount)
899     return;
900
901   for (can = cgraph_asm_nodes; can; can = can->next)
902     assemble_asm (can->asm_str);
903   cgraph_asm_nodes = NULL;
904 }
905
906 /* Analyze the function scheduled to be output.  */
907 static void
908 cgraph_analyze_function (struct cgraph_node *node)
909 {
910   tree save = current_function_decl;
911   tree decl = node->decl;
912
913   current_function_decl = decl;
914   push_cfun (DECL_STRUCT_FUNCTION (decl));
915
916   assign_assembler_name_if_neeeded (node->decl);
917
918   /* Make sure to gimplify bodies only once.  During analyzing a
919      function we lower it, which will require gimplified nested
920      functions, so we can end up here with an already gimplified
921      body.  */
922   if (!gimple_body (decl))
923     gimplify_function_tree (decl);
924   dump_function (TDI_generic, decl);
925
926   cgraph_lower_function (node);
927   node->analyzed = true;
928
929   pop_cfun ();
930   current_function_decl = save;
931 }
932
933 /* Look for externally_visible and used attributes and mark cgraph nodes
934    accordingly.
935
936    We cannot mark the nodes at the point the attributes are processed (in
937    handle_*_attribute) because the copy of the declarations available at that
938    point may not be canonical.  For example, in:
939
940     void f();
941     void f() __attribute__((used));
942
943    the declaration we see in handle_used_attribute will be the second
944    declaration -- but the front end will subsequently merge that declaration
945    with the original declaration and discard the second declaration.
946
947    Furthermore, we can't mark these nodes in cgraph_finalize_function because:
948
949     void f() {}
950     void f() __attribute__((externally_visible));
951
952    is valid.
953
954    So, we walk the nodes at the end of the translation unit, applying the
955    attributes at that point.  */
956
957 static void
958 process_function_and_variable_attributes (struct cgraph_node *first,
959                                           struct varpool_node *first_var)
960 {
961   struct cgraph_node *node;
962   struct varpool_node *vnode;
963
964   for (node = cgraph_nodes; node != first; node = node->next)
965     {
966       tree decl = node->decl;
967       if (DECL_PRESERVE_P (decl))
968         cgraph_mark_needed_node (node);
969       if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
970         {
971           if (! TREE_PUBLIC (node->decl))
972             warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
973                         "%<externally_visible%>"
974                         " attribute have effect only on public objects");
975           else if (node->local.finalized)
976              cgraph_mark_needed_node (node);
977         }
978     }
979   for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
980     {
981       tree decl = vnode->decl;
982       if (DECL_PRESERVE_P (decl))
983         {
984           vnode->force_output = true;
985           if (vnode->finalized)
986             varpool_mark_needed_node (vnode);
987         }
988       if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
989         {
990           if (! TREE_PUBLIC (vnode->decl))
991             warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
992                         "%<externally_visible%>"
993                         " attribute have effect only on public objects");
994           else if (vnode->finalized)
995             varpool_mark_needed_node (vnode);
996         }
997     }
998 }
999
1000 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
1001    each reachable functions) and build cgraph.
1002    The function can be called multiple times after inserting new nodes
1003    into beginning of queue.  Just the new part of queue is re-scanned then.  */
1004
1005 static void
1006 cgraph_analyze_functions (void)
1007 {
1008   /* Keep track of already processed nodes when called multiple times for
1009      intermodule optimization.  */
1010   static struct cgraph_node *first_analyzed;
1011   struct cgraph_node *first_processed = first_analyzed;
1012   static struct varpool_node *first_analyzed_var;
1013   struct cgraph_node *node, *next;
1014
1015   process_function_and_variable_attributes (first_processed,
1016                                             first_analyzed_var);
1017   first_processed = cgraph_nodes;
1018   first_analyzed_var = varpool_nodes;
1019   varpool_analyze_pending_decls ();
1020   if (cgraph_dump_file)
1021     {
1022       fprintf (cgraph_dump_file, "Initial entry points:");
1023       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1024         if (node->needed)
1025           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1026       fprintf (cgraph_dump_file, "\n");
1027     }
1028   cgraph_process_new_functions ();
1029
1030   /* Propagate reachability flag and lower representation of all reachable
1031      functions.  In the future, lowering will introduce new functions and
1032      new entry points on the way (by template instantiation and virtual
1033      method table generation for instance).  */
1034   while (cgraph_nodes_queue)
1035     {
1036       struct cgraph_edge *edge;
1037       tree decl = cgraph_nodes_queue->decl;
1038
1039       node = cgraph_nodes_queue;
1040       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
1041       node->next_needed = NULL;
1042
1043       /* ??? It is possible to create extern inline function and later using
1044          weak alias attribute to kill its body. See
1045          gcc.c-torture/compile/20011119-1.c  */
1046       if (!DECL_STRUCT_FUNCTION (decl))
1047         {
1048           cgraph_reset_node (node);
1049           continue;
1050         }
1051
1052       if (!node->analyzed)
1053         cgraph_analyze_function (node);
1054
1055       for (edge = node->callees; edge; edge = edge->next_callee)
1056         if (!edge->callee->reachable)
1057           cgraph_mark_reachable_node (edge->callee);
1058
1059       if (node->same_comdat_group)
1060         {
1061           for (next = node->same_comdat_group;
1062                next != node;
1063                next = next->same_comdat_group)
1064             cgraph_mark_reachable_node (next);
1065         }
1066
1067       /* If decl is a clone of an abstract function, mark that abstract
1068          function so that we don't release its body. The DECL_INITIAL() of that
1069          abstract function declaration will be later needed to output debug info.  */
1070       if (DECL_ABSTRACT_ORIGIN (decl))
1071         {
1072           struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
1073           origin_node->abstract_and_needed = true;
1074         }
1075
1076       /* We finalize local static variables during constructing callgraph
1077          edges.  Process their attributes too.  */
1078       process_function_and_variable_attributes (first_processed,
1079                                                 first_analyzed_var);
1080       first_processed = cgraph_nodes;
1081       first_analyzed_var = varpool_nodes;
1082       varpool_analyze_pending_decls ();
1083       cgraph_process_new_functions ();
1084     }
1085
1086   /* Collect entry points to the unit.  */
1087   if (cgraph_dump_file)
1088     {
1089       fprintf (cgraph_dump_file, "Unit entry points:");
1090       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1091         if (node->needed)
1092           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1093       fprintf (cgraph_dump_file, "\n\nInitial ");
1094       dump_cgraph (cgraph_dump_file);
1095     }
1096
1097   if (cgraph_dump_file)
1098     fprintf (cgraph_dump_file, "\nReclaiming functions:");
1099
1100   for (node = cgraph_nodes; node != first_analyzed; node = next)
1101     {
1102       tree decl = node->decl;
1103       next = node->next;
1104
1105       if (node->local.finalized && !gimple_has_body_p (decl))
1106         cgraph_reset_node (node);
1107
1108       if (!node->reachable && gimple_has_body_p (decl))
1109         {
1110           if (cgraph_dump_file)
1111             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1112           cgraph_remove_node (node);
1113           continue;
1114         }
1115       else
1116         node->next_needed = NULL;
1117       gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1118       gcc_assert (node->analyzed == node->local.finalized);
1119     }
1120   if (cgraph_dump_file)
1121     {
1122       fprintf (cgraph_dump_file, "\n\nReclaimed ");
1123       dump_cgraph (cgraph_dump_file);
1124     }
1125   first_analyzed = cgraph_nodes;
1126   ggc_collect ();
1127 }
1128
1129
1130 /* Analyze the whole compilation unit once it is parsed completely.  */
1131
1132 void
1133 cgraph_finalize_compilation_unit (void)
1134 {
1135   timevar_push (TV_CGRAPH);
1136
1137   /* Do not skip analyzing the functions if there were errors, we
1138      miss diagnostics for following functions otherwise.  */
1139
1140   /* Emit size functions we didn't inline.  */
1141   finalize_size_functions ();
1142
1143   /* Call functions declared with the "constructor" or "destructor"
1144      attribute.  */
1145   cgraph_build_cdtor_fns ();
1146
1147   /* Mark alias targets necessary and emit diagnostics.  */
1148   finish_aliases_1 ();
1149
1150   if (!quiet_flag)
1151     {
1152       fprintf (stderr, "\nAnalyzing compilation unit\n");
1153       fflush (stderr);
1154     }
1155
1156   /* Gimplify and lower all functions, compute reachability and
1157      remove unreachable nodes.  */
1158   cgraph_analyze_functions ();
1159
1160   /* Mark alias targets necessary and emit diagnostics.  */
1161   finish_aliases_1 ();
1162
1163   /* Gimplify and lower thunks.  */
1164   cgraph_analyze_functions ();
1165
1166   /* Finally drive the pass manager.  */
1167   cgraph_optimize ();
1168
1169   timevar_pop (TV_CGRAPH);
1170 }
1171
1172
1173 /* Figure out what functions we want to assemble.  */
1174
1175 static void
1176 cgraph_mark_functions_to_output (void)
1177 {
1178   struct cgraph_node *node;
1179 #ifdef ENABLE_CHECKING
1180   bool check_same_comdat_groups = false;
1181
1182   for (node = cgraph_nodes; node; node = node->next)
1183     gcc_assert (!node->process);
1184 #endif
1185
1186   for (node = cgraph_nodes; node; node = node->next)
1187     {
1188       tree decl = node->decl;
1189       struct cgraph_edge *e;
1190
1191       gcc_assert (!node->process || node->same_comdat_group);
1192       if (node->process)
1193         continue;
1194
1195       for (e = node->callers; e; e = e->next_caller)
1196         if (e->inline_failed)
1197           break;
1198
1199       /* We need to output all local functions that are used and not
1200          always inlined, as well as those that are reachable from
1201          outside the current compilation unit.  */
1202       if (node->analyzed
1203           && !node->global.inlined_to
1204           && (node->needed || node->reachable_from_other_partition
1205               || node->address_taken
1206               || (e && node->reachable))
1207           && !TREE_ASM_WRITTEN (decl)
1208           && !DECL_EXTERNAL (decl))
1209         {
1210           node->process = 1;
1211           if (node->same_comdat_group)
1212             {
1213               struct cgraph_node *next;
1214               for (next = node->same_comdat_group;
1215                    next != node;
1216                    next = next->same_comdat_group)
1217                 next->process = 1;
1218             }
1219         }
1220       else if (node->same_comdat_group)
1221         {
1222 #ifdef ENABLE_CHECKING
1223           check_same_comdat_groups = true;
1224 #endif
1225         }
1226       else
1227         {
1228           /* We should've reclaimed all functions that are not needed.  */
1229 #ifdef ENABLE_CHECKING
1230           if (!node->global.inlined_to
1231               && gimple_has_body_p (decl)
1232               /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1233                  are inside partition, we can end up not removing the body since we no longer
1234                  have analyzed node pointing to it.  */
1235               && !node->in_other_partition
1236               && !DECL_EXTERNAL (decl))
1237             {
1238               dump_cgraph_node (stderr, node);
1239               internal_error ("failed to reclaim unneeded function");
1240             }
1241 #endif
1242           gcc_assert (node->global.inlined_to
1243                       || !gimple_has_body_p (decl)
1244                       || node->in_other_partition
1245                       || DECL_EXTERNAL (decl));
1246
1247         }
1248
1249     }
1250 #ifdef ENABLE_CHECKING
1251   if (check_same_comdat_groups)
1252     for (node = cgraph_nodes; node; node = node->next)
1253       if (node->same_comdat_group && !node->process)
1254         {
1255           tree decl = node->decl;
1256           if (!node->global.inlined_to
1257               && gimple_has_body_p (decl)
1258               /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1259                  are inside partition, we can end up not removing the body since we no longer
1260                  have analyzed node pointing to it.  */
1261               && !node->in_other_partition
1262               && !DECL_EXTERNAL (decl))
1263             {
1264               dump_cgraph_node (stderr, node);
1265               internal_error ("failed to reclaim unneeded function");
1266             }
1267         }
1268 #endif
1269 }
1270
1271 /* DECL is FUNCTION_DECL.  Initialize datastructures so DECL is a function
1272    in lowered gimple form.
1273    
1274    Set current_function_decl and cfun to newly constructed empty function body.
1275    return basic block in the function body.  */
1276
1277 static basic_block
1278 init_lowered_empty_function (tree decl)
1279 {
1280   basic_block bb;
1281
1282   current_function_decl = decl;
1283   allocate_struct_function (decl, false);
1284   gimple_register_cfg_hooks ();
1285   init_empty_tree_cfg ();
1286   init_tree_ssa (cfun);
1287   init_ssa_operands ();
1288   cfun->gimple_df->in_ssa_p = true;
1289   DECL_INITIAL (decl) = make_node (BLOCK);
1290
1291   DECL_SAVED_TREE (decl) = error_mark_node;
1292   cfun->curr_properties |=
1293     (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1294      PROP_ssa);
1295
1296   /* Create BB for body of the function and connect it properly.  */
1297   bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1298   make_edge (ENTRY_BLOCK_PTR, bb, 0);
1299   make_edge (bb, EXIT_BLOCK_PTR, 0);
1300
1301   return bb;
1302 }
1303
1304 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1305    offset indicated by VIRTUAL_OFFSET, if that is
1306    non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1307    zero for a result adjusting thunk.  */
1308
1309 static tree
1310 thunk_adjust (gimple_stmt_iterator * bsi,
1311               tree ptr, bool this_adjusting,
1312               HOST_WIDE_INT fixed_offset, tree virtual_offset)
1313 {
1314   gimple stmt;
1315   tree ret;
1316
1317   if (this_adjusting
1318       && fixed_offset != 0)
1319     {
1320       stmt = gimple_build_assign (ptr,
1321                                   fold_build2_loc (input_location,
1322                                                    POINTER_PLUS_EXPR,
1323                                                    TREE_TYPE (ptr), ptr,
1324                                                    size_int (fixed_offset)));
1325       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1326     }
1327
1328   /* If there's a virtual offset, look up that value in the vtable and
1329      adjust the pointer again.  */
1330   if (virtual_offset)
1331     {
1332       tree vtabletmp;
1333       tree vtabletmp2;
1334       tree vtabletmp3;
1335       tree offsettmp;
1336
1337       if (!vtable_entry_type)
1338         {
1339           tree vfunc_type = make_node (FUNCTION_TYPE);
1340           TREE_TYPE (vfunc_type) = integer_type_node;
1341           TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1342           layout_type (vfunc_type);
1343
1344           vtable_entry_type = build_pointer_type (vfunc_type);
1345         }
1346
1347       vtabletmp =
1348         create_tmp_var (build_pointer_type
1349                         (build_pointer_type (vtable_entry_type)), "vptr");
1350
1351       /* The vptr is always at offset zero in the object.  */
1352       stmt = gimple_build_assign (vtabletmp,
1353                                   build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1354                                           ptr));
1355       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1356       mark_symbols_for_renaming (stmt);
1357       find_referenced_vars_in (stmt);
1358
1359       /* Form the vtable address.  */
1360       vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1361                                    "vtableaddr");
1362       stmt = gimple_build_assign (vtabletmp2,
1363                                   build1 (INDIRECT_REF,
1364                                           TREE_TYPE (vtabletmp2), vtabletmp));
1365       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1366       mark_symbols_for_renaming (stmt);
1367       find_referenced_vars_in (stmt);
1368
1369       /* Find the entry with the vcall offset.  */
1370       stmt = gimple_build_assign (vtabletmp2,
1371                                   fold_build2_loc (input_location,
1372                                                    POINTER_PLUS_EXPR,
1373                                                    TREE_TYPE (vtabletmp2),
1374                                                    vtabletmp2,
1375                                                    fold_convert (sizetype,
1376                                                                  virtual_offset)));
1377       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1378
1379       /* Get the offset itself.  */
1380       vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1381                                    "vcalloffset");
1382       stmt = gimple_build_assign (vtabletmp3,
1383                                   build1 (INDIRECT_REF,
1384                                           TREE_TYPE (vtabletmp3),
1385                                           vtabletmp2));
1386       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1387       mark_symbols_for_renaming (stmt);
1388       find_referenced_vars_in (stmt);
1389
1390       /* Cast to sizetype.  */
1391       offsettmp = create_tmp_var (sizetype, "offset");
1392       stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1393       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1394       mark_symbols_for_renaming (stmt);
1395       find_referenced_vars_in (stmt);
1396
1397       /* Adjust the `this' pointer.  */
1398       ptr = fold_build2_loc (input_location,
1399                              POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1400                              offsettmp);
1401     }
1402
1403   if (!this_adjusting
1404       && fixed_offset != 0)
1405     /* Adjust the pointer by the constant.  */
1406     {
1407       tree ptrtmp;
1408
1409       if (TREE_CODE (ptr) == VAR_DECL)
1410         ptrtmp = ptr;
1411       else
1412         {
1413           ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1414           stmt = gimple_build_assign (ptrtmp, ptr);
1415           gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1416           mark_symbols_for_renaming (stmt);
1417           find_referenced_vars_in (stmt);
1418         }
1419       ptr = fold_build2_loc (input_location,
1420                              POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1421                              size_int (fixed_offset));
1422     }
1423
1424   /* Emit the statement and gimplify the adjustment expression.  */
1425   ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1426   stmt = gimple_build_assign (ret, ptr);
1427   mark_symbols_for_renaming (stmt);
1428   find_referenced_vars_in (stmt);
1429   gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1430
1431   return ret;
1432 }
1433
1434 /* Produce assembler for thunk NODE.  */
1435
1436 static void
1437 assemble_thunk (struct cgraph_node *node)
1438 {
1439   bool this_adjusting = node->thunk.this_adjusting;
1440   HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1441   HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1442   tree virtual_offset = NULL;
1443   tree alias = node->thunk.alias;
1444   tree thunk_fndecl = node->decl;
1445   tree a = DECL_ARGUMENTS (thunk_fndecl);
1446
1447   current_function_decl = thunk_fndecl;
1448
1449   if (this_adjusting
1450       && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1451                                               virtual_value, alias))
1452     {
1453       const char *fnname;
1454       tree fn_block;
1455       
1456       DECL_RESULT (thunk_fndecl)
1457         = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1458                       RESULT_DECL, 0, integer_type_node);
1459       fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1460
1461       /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1462          create one.  */
1463       fn_block = make_node (BLOCK);
1464       BLOCK_VARS (fn_block) = a;
1465       DECL_INITIAL (thunk_fndecl) = fn_block;
1466       init_function_start (thunk_fndecl);
1467       cfun->is_thunk = 1;
1468       assemble_start_function (thunk_fndecl, fnname);
1469
1470       targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1471                                        fixed_offset, virtual_value, alias);
1472
1473       assemble_end_function (thunk_fndecl, fnname);
1474       init_insn_lengths ();
1475       free_after_compilation (cfun);
1476       set_cfun (NULL);
1477       TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1478     }
1479   else
1480     {
1481       tree restype;
1482       basic_block bb, then_bb, else_bb, return_bb;
1483       gimple_stmt_iterator bsi;
1484       int nargs = 0;
1485       tree arg;
1486       int i;
1487       tree resdecl;
1488       tree restmp = NULL;
1489       VEC(tree, heap) *vargs;
1490
1491       gimple call;
1492       gimple ret;
1493
1494       DECL_IGNORED_P (thunk_fndecl) = 1;
1495       bitmap_obstack_initialize (NULL);
1496
1497       if (node->thunk.virtual_offset_p)
1498         virtual_offset = size_int (virtual_value);
1499
1500       /* Build the return declaration for the function.  */
1501       restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1502       if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1503         {
1504           resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1505           DECL_ARTIFICIAL (resdecl) = 1;
1506           DECL_IGNORED_P (resdecl) = 1;
1507           DECL_RESULT (thunk_fndecl) = resdecl;
1508         }
1509       else
1510         resdecl = DECL_RESULT (thunk_fndecl);
1511
1512       bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1513
1514       bsi = gsi_start_bb (bb);
1515
1516       /* Build call to the function being thunked.  */
1517       if (!VOID_TYPE_P (restype))
1518         {
1519           if (!is_gimple_reg_type (restype))
1520             {
1521               restmp = resdecl;
1522               cfun->local_decls = tree_cons (NULL_TREE, restmp, cfun->local_decls);
1523               BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1524             }
1525           else
1526             restmp = create_tmp_var_raw (restype, "retval");
1527         }
1528
1529       for (arg = a; arg; arg = TREE_CHAIN (arg))
1530         nargs++;
1531       vargs = VEC_alloc (tree, heap, nargs);
1532       if (this_adjusting)
1533         VEC_quick_push (tree, vargs,
1534                         thunk_adjust (&bsi,
1535                                       a, 1, fixed_offset,
1536                                       virtual_offset));
1537       else
1538         VEC_quick_push (tree, vargs, a);
1539       for (i = 1, arg = TREE_CHAIN (a); i < nargs; i++, arg = TREE_CHAIN (arg))
1540         VEC_quick_push (tree, vargs, arg);
1541       call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1542       VEC_free (tree, heap, vargs);
1543       gimple_call_set_cannot_inline (call, true);
1544       gimple_call_set_from_thunk (call, true);
1545       if (restmp)
1546         gimple_call_set_lhs (call, restmp);
1547       gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1548       mark_symbols_for_renaming (call);
1549       find_referenced_vars_in (call);
1550       update_stmt (call);
1551
1552       if (restmp && !this_adjusting)
1553         {
1554           tree true_label = NULL_TREE;
1555
1556           if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1557             {
1558               gimple stmt;
1559               /* If the return type is a pointer, we need to
1560                  protect against NULL.  We know there will be an
1561                  adjustment, because that's why we're emitting a
1562                  thunk.  */
1563               then_bb = create_basic_block (NULL, (void *) 0, bb);
1564               return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1565               else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1566               remove_edge (single_succ_edge (bb));
1567               true_label = gimple_block_label (then_bb);
1568               stmt = gimple_build_cond (NE_EXPR, restmp,
1569                                         fold_convert (TREE_TYPE (restmp),
1570                                                       integer_zero_node),
1571                                         NULL_TREE, NULL_TREE);
1572               gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1573               make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1574               make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1575               make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1576               make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1577               make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1578               bsi = gsi_last_bb (then_bb);
1579             }
1580
1581           restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1582                                  fixed_offset, virtual_offset);
1583           if (true_label)
1584             {
1585               gimple stmt;
1586               bsi = gsi_last_bb (else_bb);
1587               stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1588                                                                 integer_zero_node));
1589               gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1590               bsi = gsi_last_bb (return_bb);
1591             }
1592         }
1593       else
1594         gimple_call_set_tail (call, true);
1595
1596       /* Build return value.  */
1597       ret = gimple_build_return (restmp);
1598       gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1599
1600       delete_unreachable_blocks ();
1601       update_ssa (TODO_update_ssa);
1602
1603       cgraph_remove_same_body_alias (node);
1604       /* Since we want to emit the thunk, we explicitly mark its name as
1605          referenced.  */
1606       cgraph_add_new_function (thunk_fndecl, true);
1607       bitmap_obstack_release (NULL);
1608     }
1609   current_function_decl = NULL;
1610 }
1611
1612 /* Expand function specified by NODE.  */
1613
1614 static void
1615 cgraph_expand_function (struct cgraph_node *node)
1616 {
1617   tree decl = node->decl;
1618
1619   /* We ought to not compile any inline clones.  */
1620   gcc_assert (!node->global.inlined_to);
1621
1622   announce_function (decl);
1623   node->process = 0;
1624
1625   gcc_assert (node->lowered);
1626
1627   /* Generate RTL for the body of DECL.  */
1628   tree_rest_of_compilation (decl);
1629
1630   /* Make sure that BE didn't give up on compiling.  */
1631   gcc_assert (TREE_ASM_WRITTEN (decl));
1632   current_function_decl = NULL;
1633   if (node->same_body)
1634     {
1635       struct cgraph_node *alias, *next;
1636       bool saved_alias = node->alias;
1637       for (alias = node->same_body;
1638            alias && alias->next; alias = alias->next)
1639         ;
1640       /* Walk aliases in the order they were created; it is possible that
1641          thunks reffers to the aliases made earlier.  */
1642       for (; alias; alias = next)
1643         {
1644           next = alias->previous;
1645           if (!alias->thunk.thunk_p)
1646             assemble_alias (alias->decl,
1647                             DECL_ASSEMBLER_NAME (alias->thunk.alias));
1648           else
1649             assemble_thunk (alias);
1650         }
1651       node->alias = saved_alias;
1652     }
1653   gcc_assert (!cgraph_preserve_function_body_p (decl));
1654   cgraph_release_function_body (node);
1655   /* Eliminate all call edges.  This is important so the GIMPLE_CALL no longer
1656      points to the dead function body.  */
1657   cgraph_node_remove_callees (node);
1658
1659   cgraph_function_flags_ready = true;
1660 }
1661
1662 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1663
1664 bool
1665 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1666 {
1667   *reason = e->inline_failed;
1668   return !e->inline_failed;
1669 }
1670
1671
1672
1673 /* Expand all functions that must be output.
1674
1675    Attempt to topologically sort the nodes so function is output when
1676    all called functions are already assembled to allow data to be
1677    propagated across the callgraph.  Use a stack to get smaller distance
1678    between a function and its callees (later we may choose to use a more
1679    sophisticated algorithm for function reordering; we will likely want
1680    to use subsections to make the output functions appear in top-down
1681    order).  */
1682
1683 static void
1684 cgraph_expand_all_functions (void)
1685 {
1686   struct cgraph_node *node;
1687   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1688   int order_pos, new_order_pos = 0;
1689   int i;
1690
1691   order_pos = cgraph_postorder (order);
1692   gcc_assert (order_pos == cgraph_n_nodes);
1693
1694   /* Garbage collector may remove inline clones we eliminate during
1695      optimization.  So we must be sure to not reference them.  */
1696   for (i = 0; i < order_pos; i++)
1697     if (order[i]->process)
1698       order[new_order_pos++] = order[i];
1699
1700   for (i = new_order_pos - 1; i >= 0; i--)
1701     {
1702       node = order[i];
1703       if (node->process)
1704         {
1705           gcc_assert (node->reachable);
1706           node->process = 0;
1707           cgraph_expand_function (node);
1708         }
1709     }
1710   cgraph_process_new_functions ();
1711
1712   free (order);
1713
1714 }
1715
1716 /* This is used to sort the node types by the cgraph order number.  */
1717
1718 enum cgraph_order_sort_kind
1719 {
1720   ORDER_UNDEFINED = 0,
1721   ORDER_FUNCTION,
1722   ORDER_VAR,
1723   ORDER_ASM
1724 };
1725
1726 struct cgraph_order_sort
1727 {
1728   enum cgraph_order_sort_kind kind;
1729   union
1730   {
1731     struct cgraph_node *f;
1732     struct varpool_node *v;
1733     struct cgraph_asm_node *a;
1734   } u;
1735 };
1736
1737 /* Output all functions, variables, and asm statements in the order
1738    according to their order fields, which is the order in which they
1739    appeared in the file.  This implements -fno-toplevel-reorder.  In
1740    this mode we may output functions and variables which don't really
1741    need to be output.  */
1742
1743 static void
1744 cgraph_output_in_order (void)
1745 {
1746   int max;
1747   struct cgraph_order_sort *nodes;
1748   int i;
1749   struct cgraph_node *pf;
1750   struct varpool_node *pv;
1751   struct cgraph_asm_node *pa;
1752
1753   max = cgraph_order;
1754   nodes = XCNEWVEC (struct cgraph_order_sort, max);
1755
1756   varpool_analyze_pending_decls ();
1757
1758   for (pf = cgraph_nodes; pf; pf = pf->next)
1759     {
1760       if (pf->process)
1761         {
1762           i = pf->order;
1763           gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1764           nodes[i].kind = ORDER_FUNCTION;
1765           nodes[i].u.f = pf;
1766         }
1767     }
1768
1769   for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1770     {
1771       i = pv->order;
1772       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1773       nodes[i].kind = ORDER_VAR;
1774       nodes[i].u.v = pv;
1775     }
1776
1777   for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1778     {
1779       i = pa->order;
1780       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1781       nodes[i].kind = ORDER_ASM;
1782       nodes[i].u.a = pa;
1783     }
1784
1785   /* In toplevel reorder mode we output all statics; mark them as needed.  */
1786   for (i = 0; i < max; ++i)
1787     {
1788       if (nodes[i].kind == ORDER_VAR)
1789         {
1790           varpool_mark_needed_node (nodes[i].u.v);
1791         }
1792     }
1793   varpool_empty_needed_queue ();
1794
1795   for (i = 0; i < max; ++i)
1796     {
1797       switch (nodes[i].kind)
1798         {
1799         case ORDER_FUNCTION:
1800           nodes[i].u.f->process = 0;
1801           cgraph_expand_function (nodes[i].u.f);
1802           break;
1803
1804         case ORDER_VAR:
1805           varpool_assemble_decl (nodes[i].u.v);
1806           break;
1807
1808         case ORDER_ASM:
1809           assemble_asm (nodes[i].u.a->asm_str);
1810           break;
1811
1812         case ORDER_UNDEFINED:
1813           break;
1814
1815         default:
1816           gcc_unreachable ();
1817         }
1818     }
1819
1820   cgraph_asm_nodes = NULL;
1821   free (nodes);
1822 }
1823
1824 /* Return true when function body of DECL still needs to be kept around
1825    for later re-use.  */
1826 bool
1827 cgraph_preserve_function_body_p (tree decl)
1828 {
1829   struct cgraph_node *node;
1830
1831   gcc_assert (cgraph_global_info_ready);
1832   /* Look if there is any clone around.  */
1833   node = cgraph_node (decl);
1834   if (node->clones)
1835     return true;
1836   return false;
1837 }
1838
1839 static void
1840 ipa_passes (void)
1841 {
1842   set_cfun (NULL);
1843   current_function_decl = NULL;
1844   gimple_register_cfg_hooks ();
1845   bitmap_obstack_initialize (NULL);
1846
1847   invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1848
1849   if (!in_lto_p)
1850     execute_ipa_pass_list (all_small_ipa_passes);
1851
1852   /* If pass_all_early_optimizations was not scheduled, the state of
1853      the cgraph will not be properly updated.  Update it now.  */
1854   if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1855     cgraph_state = CGRAPH_STATE_IPA_SSA;
1856
1857   if (!in_lto_p)
1858     {
1859       /* Generate coverage variables and constructors.  */
1860       coverage_finish ();
1861
1862       /* Process new functions added.  */
1863       set_cfun (NULL);
1864       current_function_decl = NULL;
1865       cgraph_process_new_functions ();
1866
1867       execute_ipa_summary_passes
1868         ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1869     }
1870
1871   /* Some targets need to handle LTO assembler output specially.  */
1872   if (flag_generate_lto)
1873     targetm.asm_out.lto_start ();
1874
1875   execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1876
1877   if (!in_lto_p)
1878     ipa_write_summaries ();
1879
1880   if (flag_generate_lto)
1881     targetm.asm_out.lto_end ();
1882
1883   if (!flag_ltrans)
1884     execute_ipa_pass_list (all_regular_ipa_passes);
1885   invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1886
1887   bitmap_obstack_release (NULL);
1888 }
1889
1890
1891 /* Perform simple optimizations based on callgraph.  */
1892
1893 void
1894 cgraph_optimize (void)
1895 {
1896   if (errorcount || sorrycount)
1897     return;
1898
1899 #ifdef ENABLE_CHECKING
1900   verify_cgraph ();
1901 #endif
1902
1903   /* Frontend may output common variables after the unit has been finalized.
1904      It is safe to deal with them here as they are always zero initialized.  */
1905   varpool_analyze_pending_decls ();
1906
1907   timevar_push (TV_CGRAPHOPT);
1908   if (pre_ipa_mem_report)
1909     {
1910       fprintf (stderr, "Memory consumption before IPA\n");
1911       dump_memory_report (false);
1912     }
1913   if (!quiet_flag)
1914     fprintf (stderr, "Performing interprocedural optimizations\n");
1915   cgraph_state = CGRAPH_STATE_IPA;
1916
1917   /* Don't run the IPA passes if there was any error or sorry messages.  */
1918   if (errorcount == 0 && sorrycount == 0)
1919     ipa_passes ();
1920
1921   /* Do nothing else if any IPA pass found errors.  */
1922   if (errorcount || sorrycount)
1923     {
1924       timevar_pop (TV_CGRAPHOPT);
1925       return;
1926     }
1927
1928   /* This pass remove bodies of extern inline functions we never inlined.
1929      Do this later so other IPA passes see what is really going on.  */
1930   cgraph_remove_unreachable_nodes (false, dump_file);
1931   cgraph_global_info_ready = true;
1932   if (cgraph_dump_file)
1933     {
1934       fprintf (cgraph_dump_file, "Optimized ");
1935       dump_cgraph (cgraph_dump_file);
1936       dump_varpool (cgraph_dump_file);
1937     }
1938   if (post_ipa_mem_report)
1939     {
1940       fprintf (stderr, "Memory consumption after IPA\n");
1941       dump_memory_report (false);
1942     }
1943   timevar_pop (TV_CGRAPHOPT);
1944
1945   /* Output everything.  */
1946   (*debug_hooks->assembly_start) ();
1947   if (!quiet_flag)
1948     fprintf (stderr, "Assembling functions:\n");
1949 #ifdef ENABLE_CHECKING
1950   verify_cgraph ();
1951 #endif
1952
1953   cgraph_materialize_all_clones ();
1954   cgraph_mark_functions_to_output ();
1955
1956   cgraph_state = CGRAPH_STATE_EXPANSION;
1957   if (!flag_toplevel_reorder)
1958     cgraph_output_in_order ();
1959   else
1960     {
1961       cgraph_output_pending_asms ();
1962
1963       cgraph_expand_all_functions ();
1964       varpool_remove_unreferenced_decls ();
1965
1966       varpool_assemble_pending_decls ();
1967     }
1968   cgraph_process_new_functions ();
1969   cgraph_state = CGRAPH_STATE_FINISHED;
1970
1971   if (cgraph_dump_file)
1972     {
1973       fprintf (cgraph_dump_file, "\nFinal ");
1974       dump_cgraph (cgraph_dump_file);
1975     }
1976 #ifdef ENABLE_CHECKING
1977   verify_cgraph ();
1978   /* Double check that all inline clones are gone and that all
1979      function bodies have been released from memory.  */
1980   if (!(sorrycount || errorcount))
1981     {
1982       struct cgraph_node *node;
1983       bool error_found = false;
1984
1985       for (node = cgraph_nodes; node; node = node->next)
1986         if (node->analyzed
1987             && (node->global.inlined_to
1988                 || gimple_has_body_p (node->decl)))
1989           {
1990             error_found = true;
1991             dump_cgraph_node (stderr, node);
1992           }
1993       if (error_found)
1994         internal_error ("nodes with unreleased memory found");
1995     }
1996 #endif
1997 }
1998
1999
2000 /* Generate and emit a static constructor or destructor.  WHICH must
2001    be one of 'I' (for a constructor) or 'D' (for a destructor).  BODY
2002    is a STATEMENT_LIST containing GENERIC statements.  PRIORITY is the
2003    initialization priority for this constructor or destructor.  */
2004
2005 void
2006 cgraph_build_static_cdtor (char which, tree body, int priority)
2007 {
2008   static int counter = 0;
2009   char which_buf[16];
2010   tree decl, name, resdecl;
2011
2012   /* The priority is encoded in the constructor or destructor name.
2013      collect2 will sort the names and arrange that they are called at
2014      program startup.  */
2015   sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
2016   name = get_file_function_name (which_buf);
2017
2018   decl = build_decl (input_location, FUNCTION_DECL, name,
2019                      build_function_type (void_type_node, void_list_node));
2020   current_function_decl = decl;
2021
2022   resdecl = build_decl (input_location,
2023                         RESULT_DECL, NULL_TREE, void_type_node);
2024   DECL_ARTIFICIAL (resdecl) = 1;
2025   DECL_RESULT (decl) = resdecl;
2026   DECL_CONTEXT (resdecl) = decl;
2027
2028   allocate_struct_function (decl, false);
2029
2030   TREE_STATIC (decl) = 1;
2031   TREE_USED (decl) = 1;
2032   DECL_ARTIFICIAL (decl) = 1;
2033   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
2034   DECL_SAVED_TREE (decl) = body;
2035   if (!targetm.have_ctors_dtors)
2036     {
2037       TREE_PUBLIC (decl) = 1;
2038       DECL_PRESERVE_P (decl) = 1;
2039     }
2040   DECL_UNINLINABLE (decl) = 1;
2041
2042   DECL_INITIAL (decl) = make_node (BLOCK);
2043   TREE_USED (DECL_INITIAL (decl)) = 1;
2044
2045   DECL_SOURCE_LOCATION (decl) = input_location;
2046   cfun->function_end_locus = input_location;
2047
2048   switch (which)
2049     {
2050     case 'I':
2051       DECL_STATIC_CONSTRUCTOR (decl) = 1;
2052       decl_init_priority_insert (decl, priority);
2053       break;
2054     case 'D':
2055       DECL_STATIC_DESTRUCTOR (decl) = 1;
2056       decl_fini_priority_insert (decl, priority);
2057       break;
2058     default:
2059       gcc_unreachable ();
2060     }
2061
2062   gimplify_function_tree (decl);
2063
2064   cgraph_add_new_function (decl, false);
2065   cgraph_mark_needed_node (cgraph_node (decl));
2066   set_cfun (NULL);
2067 }
2068
2069 void
2070 init_cgraph (void)
2071 {
2072   cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
2073 }
2074
2075 /* The edges representing the callers of the NEW_VERSION node were
2076    fixed by cgraph_function_versioning (), now the call_expr in their
2077    respective tree code should be updated to call the NEW_VERSION.  */
2078
2079 static void
2080 update_call_expr (struct cgraph_node *new_version)
2081 {
2082   struct cgraph_edge *e;
2083
2084   gcc_assert (new_version);
2085
2086   /* Update the call expr on the edges to call the new version.  */
2087   for (e = new_version->callers; e; e = e->next_caller)
2088     {
2089       struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
2090       gimple_call_set_fndecl (e->call_stmt, new_version->decl);
2091       maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
2092     }
2093 }
2094
2095
2096 /* Create a new cgraph node which is the new version of
2097    OLD_VERSION node.  REDIRECT_CALLERS holds the callers
2098    edges which should be redirected to point to
2099    NEW_VERSION.  ALL the callees edges of OLD_VERSION
2100    are cloned to the new version node.  Return the new
2101    version node.  */
2102
2103 static struct cgraph_node *
2104 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
2105                                  tree new_decl,
2106                                  VEC(cgraph_edge_p,heap) *redirect_callers)
2107  {
2108    struct cgraph_node *new_version;
2109    struct cgraph_edge *e;
2110    struct cgraph_edge *next_callee;
2111    unsigned i;
2112
2113    gcc_assert (old_version);
2114
2115    new_version = cgraph_node (new_decl);
2116
2117    new_version->analyzed = true;
2118    new_version->local = old_version->local;
2119    new_version->global = old_version->global;
2120    new_version->rtl = new_version->rtl;
2121    new_version->reachable = true;
2122    new_version->count = old_version->count;
2123
2124    /* Clone the old node callees.  Recursive calls are
2125       also cloned.  */
2126    for (e = old_version->callees;e; e=e->next_callee)
2127      {
2128        cgraph_clone_edge (e, new_version, e->call_stmt,
2129                           e->lto_stmt_uid, REG_BR_PROB_BASE,
2130                           CGRAPH_FREQ_BASE,
2131                           e->loop_nest, true);
2132      }
2133    /* Fix recursive calls.
2134       If OLD_VERSION has a recursive call after the
2135       previous edge cloning, the new version will have an edge
2136       pointing to the old version, which is wrong;
2137       Redirect it to point to the new version. */
2138    for (e = new_version->callees ; e; e = next_callee)
2139      {
2140        next_callee = e->next_callee;
2141        if (e->callee == old_version)
2142          cgraph_redirect_edge_callee (e, new_version);
2143
2144        if (!next_callee)
2145          break;
2146      }
2147    for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2148      {
2149        /* Redirect calls to the old version node to point to its new
2150           version.  */
2151        cgraph_redirect_edge_callee (e, new_version);
2152      }
2153
2154    return new_version;
2155  }
2156
2157  /* Perform function versioning.
2158     Function versioning includes copying of the tree and
2159     a callgraph update (creating a new cgraph node and updating
2160     its callees and callers).
2161
2162     REDIRECT_CALLERS varray includes the edges to be redirected
2163     to the new version.
2164
2165     TREE_MAP is a mapping of tree nodes we want to replace with
2166     new ones (according to results of prior analysis).
2167     OLD_VERSION_NODE is the node that is versioned.
2168     It returns the new version's cgraph node.
2169     ARGS_TO_SKIP lists arguments to be omitted from functions
2170     */
2171
2172 struct cgraph_node *
2173 cgraph_function_versioning (struct cgraph_node *old_version_node,
2174                             VEC(cgraph_edge_p,heap) *redirect_callers,
2175                             VEC (ipa_replace_map_p,gc)* tree_map,
2176                             bitmap args_to_skip)
2177 {
2178   tree old_decl = old_version_node->decl;
2179   struct cgraph_node *new_version_node = NULL;
2180   tree new_decl;
2181
2182   if (!tree_versionable_function_p (old_decl))
2183     return NULL;
2184
2185   /* Make a new FUNCTION_DECL tree node for the
2186      new version. */
2187   if (!args_to_skip)
2188     new_decl = copy_node (old_decl);
2189   else
2190     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2191
2192   /* Create the new version's call-graph node.
2193      and update the edges of the new node. */
2194   new_version_node =
2195     cgraph_copy_node_for_versioning (old_version_node, new_decl,
2196                                      redirect_callers);
2197
2198   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
2199   tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip);
2200
2201   /* Update the new version's properties.
2202      Make The new version visible only within this translation unit.  Make sure
2203      that is not weak also.
2204      ??? We cannot use COMDAT linkage because there is no
2205      ABI support for this.  */
2206   cgraph_make_decl_local (new_version_node->decl);
2207   DECL_VIRTUAL_P (new_version_node->decl) = 0;
2208   new_version_node->local.externally_visible = 0;
2209   new_version_node->local.local = 1;
2210   new_version_node->lowered = true;
2211
2212   /* Update the call_expr on the edges to call the new version node. */
2213   update_call_expr (new_version_node);
2214
2215   cgraph_call_function_insertion_hooks (new_version_node);
2216   return new_version_node;
2217 }
2218
2219 /* Produce separate function body for inline clones so the offline copy can be
2220    modified without affecting them.  */
2221 struct cgraph_node *
2222 save_inline_function_body (struct cgraph_node *node)
2223 {
2224   struct cgraph_node *first_clone, *n;
2225
2226   gcc_assert (node == cgraph_node (node->decl));
2227
2228   cgraph_lower_function (node);
2229
2230   first_clone = node->clones;
2231
2232   first_clone->decl = copy_node (node->decl);
2233   cgraph_insert_node_to_hashtable (first_clone);
2234   gcc_assert (first_clone == cgraph_node (first_clone->decl));
2235   if (first_clone->next_sibling_clone)
2236     {
2237       for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2238         n->clone_of = first_clone;
2239       n->clone_of = first_clone;
2240       n->next_sibling_clone = first_clone->clones;
2241       if (first_clone->clones)
2242         first_clone->clones->prev_sibling_clone = n;
2243       first_clone->clones = first_clone->next_sibling_clone;
2244       first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2245       first_clone->next_sibling_clone = NULL;
2246       gcc_assert (!first_clone->prev_sibling_clone);
2247     }
2248   first_clone->clone_of = NULL;
2249   node->clones = NULL;
2250
2251   if (first_clone->clones)
2252     for (n = first_clone->clones; n != first_clone;)
2253       {
2254         gcc_assert (n->decl == node->decl);
2255         n->decl = first_clone->decl;
2256         if (n->clones)
2257           n = n->clones;
2258         else if (n->next_sibling_clone)
2259           n = n->next_sibling_clone;
2260         else
2261           {
2262             while (n != first_clone && !n->next_sibling_clone)
2263               n = n->clone_of;
2264             if (n != first_clone)
2265               n = n->next_sibling_clone;
2266           }
2267       }
2268
2269   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
2270   tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL);
2271
2272   DECL_EXTERNAL (first_clone->decl) = 0;
2273   DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2274   TREE_PUBLIC (first_clone->decl) = 0;
2275   DECL_COMDAT (first_clone->decl) = 0;
2276   VEC_free (ipa_opt_pass, heap,
2277             first_clone->ipa_transforms_to_apply);
2278   first_clone->ipa_transforms_to_apply = NULL;
2279
2280 #ifdef ENABLE_CHECKING
2281   verify_cgraph_node (first_clone);
2282 #endif
2283   return first_clone;
2284 }
2285
2286 /* Given virtual clone, turn it into actual clone.  */
2287 static void
2288 cgraph_materialize_clone (struct cgraph_node *node)
2289 {
2290   bitmap_obstack_initialize (NULL);
2291 #ifdef ENABLE_CHECKING
2292   node->former_clone_of = node->clone_of->decl;
2293   if (node->clone_of->former_clone_of)
2294     node->former_clone_of = node->clone_of->former_clone_of;
2295 #endif
2296   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
2297   tree_function_versioning (node->clone_of->decl, node->decl,
2298                             node->clone.tree_map, true,
2299                             node->clone.args_to_skip);
2300   if (cgraph_dump_file)
2301     {
2302       dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2303       dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2304     }
2305
2306   /* Function is no longer clone.  */
2307   if (node->next_sibling_clone)
2308     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2309   if (node->prev_sibling_clone)
2310     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2311   else
2312     node->clone_of->clones = node->next_sibling_clone;
2313   node->next_sibling_clone = NULL;
2314   node->prev_sibling_clone = NULL;
2315   if (!node->clone_of->analyzed && !node->clone_of->clones)
2316     cgraph_remove_node (node->clone_of);
2317   node->clone_of = NULL;
2318   bitmap_obstack_release (NULL);
2319 }
2320
2321 /* If necessary, change the function declaration in the call statement
2322    associated with E so that it corresponds to the edge callee.  */
2323
2324 gimple
2325 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2326 {
2327   tree decl = gimple_call_fndecl (e->call_stmt);
2328   gimple new_stmt;
2329   gimple_stmt_iterator gsi;
2330
2331   if (!decl || decl == e->callee->decl
2332       /* Don't update call from same body alias to the real function.  */
2333       || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
2334     return e->call_stmt;
2335
2336   gcc_assert (!cgraph_node (decl)->clone.combined_args_to_skip);
2337
2338   if (cgraph_dump_file)
2339     {
2340       fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2341                cgraph_node_name (e->caller), e->caller->uid,
2342                cgraph_node_name (e->callee), e->callee->uid);
2343       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2344       if (e->callee->clone.combined_args_to_skip)
2345         {
2346           fprintf (cgraph_dump_file, " combined args to skip: ");
2347           dump_bitmap (cgraph_dump_file, e->callee->clone.combined_args_to_skip);
2348         }
2349     }
2350
2351   if (e->callee->clone.combined_args_to_skip)
2352     new_stmt = gimple_call_copy_skip_args (e->call_stmt,
2353                                        e->callee->clone.combined_args_to_skip);
2354   else
2355     new_stmt = e->call_stmt;
2356   if (gimple_vdef (new_stmt)
2357       && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2358     SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2359   gimple_call_set_fndecl (new_stmt, e->callee->decl);
2360
2361   gsi = gsi_for_stmt (e->call_stmt);
2362   gsi_replace (&gsi, new_stmt, true);
2363   update_stmt (new_stmt);
2364
2365   /* Update EH information too, just in case.  */
2366   maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
2367
2368   cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2369
2370   if (cgraph_dump_file)
2371     {
2372       fprintf (cgraph_dump_file, "  updated to:");
2373       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2374     }
2375   return new_stmt;
2376 }
2377
2378 /* Once all functions from compilation unit are in memory, produce all clones
2379    and update all calls.  We might also do this on demand if we don't want to
2380    bring all functions to memory prior compilation, but current WHOPR
2381    implementation does that and it is is bit easier to keep everything right in
2382    this order.  */
2383 void
2384 cgraph_materialize_all_clones (void)
2385 {
2386   struct cgraph_node *node;
2387   bool stabilized = false;
2388
2389   if (cgraph_dump_file)
2390     fprintf (cgraph_dump_file, "Materializing clones\n");
2391 #ifdef ENABLE_CHECKING
2392   verify_cgraph ();
2393 #endif
2394
2395   /* We can also do topological order, but number of iterations should be
2396      bounded by number of IPA passes since single IPA pass is probably not
2397      going to create clones of clones it created itself.  */
2398   while (!stabilized)
2399     {
2400       stabilized = true;
2401       for (node = cgraph_nodes; node; node = node->next)
2402         {
2403           if (node->clone_of && node->decl != node->clone_of->decl
2404               && !gimple_has_body_p (node->decl))
2405             {
2406               if (gimple_has_body_p (node->clone_of->decl))
2407                 {
2408                   if (cgraph_dump_file)
2409                     {
2410                       fprintf (cgraph_dump_file, "clonning %s to %s\n",
2411                                cgraph_node_name (node->clone_of),
2412                                cgraph_node_name (node));
2413                       if (node->clone.tree_map)
2414                         {
2415                           unsigned int i;
2416                           fprintf (cgraph_dump_file, "   replace map: ");
2417                           for (i = 0; i < VEC_length (ipa_replace_map_p,
2418                                                       node->clone.tree_map);
2419                                                       i++)
2420                             {
2421                               struct ipa_replace_map *replace_info;
2422                               replace_info = VEC_index (ipa_replace_map_p,
2423                                                         node->clone.tree_map,
2424                                                         i);
2425                               print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2426                               fprintf (cgraph_dump_file, " -> ");
2427                               print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2428                               fprintf (cgraph_dump_file, "%s%s;",
2429                                        replace_info->replace_p ? "(replace)":"",
2430                                        replace_info->ref_p ? "(ref)":"");
2431                             }
2432                           fprintf (cgraph_dump_file, "\n");
2433                         }
2434                       if (node->clone.args_to_skip)
2435                         {
2436                           fprintf (cgraph_dump_file, "   args_to_skip: ");
2437                           dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2438                         }
2439                       if (node->clone.args_to_skip)
2440                         {
2441                           fprintf (cgraph_dump_file, "   combined_args_to_skip:");
2442                           dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2443                         }
2444                     }
2445                   cgraph_materialize_clone (node);
2446                   stabilized = false;
2447                 }
2448             }
2449         }
2450     }
2451   for (node = cgraph_nodes; node; node = node->next)
2452     if (!node->analyzed && node->callees)
2453       cgraph_node_remove_callees (node);
2454   if (cgraph_dump_file)
2455     fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2456 #ifdef ENABLE_CHECKING
2457   verify_cgraph ();
2458 #endif
2459   cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2460 }
2461
2462 #include "gt-cgraphunit.h"