Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / cgraphclones.c
1 /* Callgraph clones
2    Copyright (C) 2003-2015 Free Software Foundation, Inc.
3    Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This module provide facilities for clonning functions. I.e. creating
22    new functions based on existing functions with simple modifications,
23    such as replacement of parameters.
24
25    To allow whole program optimization without actual presence of function
26    bodies, an additional infrastructure is provided for so-called virtual
27    clones
28
29    A virtual clone in the callgraph is a function that has no
30    associated body, just a description of how to create its body based
31    on a different function (which itself may be a virtual clone).
32
33    The description of function modifications includes adjustments to
34    the function's signature (which allows, for example, removing or
35    adding function arguments), substitutions to perform on the
36    function body, and, for inlined functions, a pointer to the
37    function that it will be inlined into.
38
39    It is also possible to redirect any edge of the callgraph from a
40    function to its virtual clone.  This implies updating of the call
41    site to adjust for the new function signature.
42
43    Most of the transformations performed by inter-procedural
44    optimizations can be represented via virtual clones.  For
45    instance, a constant propagation pass can produce a virtual clone
46    of the function which replaces one of its arguments by a
47    constant.  The inliner can represent its decisions by producing a
48    clone of a function whose body will be later integrated into
49    a given function.
50
51    Using virtual clones, the program can be easily updated
52    during the Execute stage, solving most of pass interactions
53    problems that would otherwise occur during Transform.
54
55    Virtual clones are later materialized in the LTRANS stage and
56    turned into real functions.  Passes executed after the virtual
57    clone were introduced also perform their Transform stage
58    on new functions, so for a pass there is no significant
59    difference between operating on a real function or a virtual
60    clone introduced before its Execute stage.
61
62    Optimization passes then work on virtual clones introduced before
63    their Execute stage as if they were real functions.  The
64    only difference is that clones are not visible during the
65    Generate Summary stage.  */
66
67 #include "config.h"
68 #include "system.h"
69 #include "coretypes.h"
70 #include "tm.h"
71 #include "rtl.h"
72 #include "hash-set.h"
73 #include "machmode.h"
74 #include "vec.h"
75 #include "double-int.h"
76 #include "input.h"
77 #include "alias.h"
78 #include "symtab.h"
79 #include "wide-int.h"
80 #include "inchash.h"
81 #include "tree.h"
82 #include "fold-const.h"
83 #include "stringpool.h"
84 #include "hard-reg-set.h"
85 #include "input.h"
86 #include "function.h"
87 #include "emit-rtl.h"
88 #include "predict.h"
89 #include "basic-block.h"
90 #include "tree-ssa-alias.h"
91 #include "internal-fn.h"
92 #include "tree-eh.h"
93 #include "gimple-expr.h"
94 #include "is-a.h"
95 #include "gimple.h"
96 #include "bitmap.h"
97 #include "tree-cfg.h"
98 #include "tree-inline.h"
99 #include "langhooks.h"
100 #include "toplev.h"
101 #include "flags.h"
102 #include "debug.h"
103 #include "target.h"
104 #include "diagnostic.h"
105 #include "params.h"
106 #include "intl.h"
107 #include "hash-map.h"
108 #include "plugin-api.h"
109 #include "ipa-ref.h"
110 #include "cgraph.h"
111 #include "alloc-pool.h"
112 #include "symbol-summary.h"
113 #include "ipa-prop.h"
114 #include "tree-iterator.h"
115 #include "tree-dump.h"
116 #include "gimple-pretty-print.h"
117 #include "coverage.h"
118 #include "ipa-inline.h"
119 #include "ipa-utils.h"
120 #include "lto-streamer.h"
121 #include "except.h"
122
123 /* Create clone of edge in the node N represented by CALL_EXPR
124    the callgraph.  */
125
126 cgraph_edge *
127 cgraph_edge::clone (cgraph_node *n, gcall *call_stmt, unsigned stmt_uid,
128                     gcov_type count_scale, int freq_scale, bool update_original)
129 {
130   cgraph_edge *new_edge;
131   gcov_type gcov_count = apply_probability (count, count_scale);
132   gcov_type freq;
133
134   /* We do not want to ignore loop nest after frequency drops to 0.  */
135   if (!freq_scale)
136     freq_scale = 1;
137   freq = frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
138   if (freq > CGRAPH_FREQ_MAX)
139     freq = CGRAPH_FREQ_MAX;
140
141   if (indirect_unknown_callee)
142     {
143       tree decl;
144
145       if (call_stmt && (decl = gimple_call_fndecl (call_stmt))
146           /* When the call is speculative, we need to resolve it 
147              via cgraph_resolve_speculation and not here.  */
148           && !speculative)
149         {
150           cgraph_node *callee = cgraph_node::get (decl);
151           gcc_checking_assert (callee);
152           new_edge = n->create_edge (callee, call_stmt, gcov_count, freq);
153         }
154       else
155         {
156           new_edge = n->create_indirect_edge (call_stmt,
157                                               indirect_info->ecf_flags,
158                                               count, freq, false);
159           *new_edge->indirect_info = *indirect_info;
160         }
161     }
162   else
163     {
164       new_edge = n->create_edge (callee, call_stmt, gcov_count, freq);
165       if (indirect_info)
166         {
167           new_edge->indirect_info
168             = ggc_cleared_alloc<cgraph_indirect_call_info> ();
169           *new_edge->indirect_info = *indirect_info;
170         }
171     }
172
173   new_edge->inline_failed = inline_failed;
174   new_edge->indirect_inlining_edge = indirect_inlining_edge;
175   new_edge->lto_stmt_uid = stmt_uid;
176   /* Clone flags that depend on call_stmt availability manually.  */
177   new_edge->can_throw_external = can_throw_external;
178   new_edge->call_stmt_cannot_inline_p = call_stmt_cannot_inline_p;
179   new_edge->speculative = speculative;
180   new_edge->in_polymorphic_cdtor = in_polymorphic_cdtor;
181   if (update_original)
182     {
183       count -= new_edge->count;
184       if (count < 0)
185         count = 0;
186     }
187   symtab->call_edge_duplication_hooks (this, new_edge);
188   return new_edge;
189 }
190
191 /* Build variant of function type ORIG_TYPE skipping ARGS_TO_SKIP and the
192    return value if SKIP_RETURN is true.  */
193
194 static tree
195 build_function_type_skip_args (tree orig_type, bitmap args_to_skip,
196                                bool skip_return)
197 {
198   tree new_type = NULL;
199   tree args, new_args = NULL;
200   tree new_reversed;
201   int i = 0;
202
203   for (args = TYPE_ARG_TYPES (orig_type); args && args != void_list_node;
204        args = TREE_CHAIN (args), i++)
205     if (!args_to_skip || !bitmap_bit_p (args_to_skip, i))
206       new_args = tree_cons (NULL_TREE, TREE_VALUE (args), new_args);
207
208   new_reversed = nreverse (new_args);
209   if (args)
210     {
211       if (new_reversed)
212         TREE_CHAIN (new_args) = void_list_node;
213       else
214         new_reversed = void_list_node;
215     }
216
217   /* Use copy_node to preserve as much as possible from original type
218      (debug info, attribute lists etc.)
219      Exception is METHOD_TYPEs must have THIS argument.
220      When we are asked to remove it, we need to build new FUNCTION_TYPE
221      instead.  */
222   if (TREE_CODE (orig_type) != METHOD_TYPE
223       || !args_to_skip
224       || !bitmap_bit_p (args_to_skip, 0))
225     {
226       new_type = build_distinct_type_copy (orig_type);
227       TYPE_ARG_TYPES (new_type) = new_reversed;
228     }
229   else
230     {
231       new_type
232         = build_distinct_type_copy (build_function_type (TREE_TYPE (orig_type),
233                                                          new_reversed));
234       TYPE_CONTEXT (new_type) = TYPE_CONTEXT (orig_type);
235     }
236
237   if (skip_return)
238     TREE_TYPE (new_type) = void_type_node;
239
240   return new_type;
241 }
242
243 /* Build variant of function decl ORIG_DECL skipping ARGS_TO_SKIP and the
244    return value if SKIP_RETURN is true.
245
246    Arguments from DECL_ARGUMENTS list can't be removed now, since they are
247    linked by TREE_CHAIN directly.  The caller is responsible for eliminating
248    them when they are being duplicated (i.e. copy_arguments_for_versioning).  */
249
250 static tree
251 build_function_decl_skip_args (tree orig_decl, bitmap args_to_skip,
252                                bool skip_return)
253 {
254   tree new_decl = copy_node (orig_decl);
255   tree new_type;
256
257   new_type = TREE_TYPE (orig_decl);
258   if (prototype_p (new_type)
259       || (skip_return && !VOID_TYPE_P (TREE_TYPE (new_type))))
260     new_type
261       = build_function_type_skip_args (new_type, args_to_skip, skip_return);
262   TREE_TYPE (new_decl) = new_type;
263
264   /* For declarations setting DECL_VINDEX (i.e. methods)
265      we expect first argument to be THIS pointer.   */
266   if (args_to_skip && bitmap_bit_p (args_to_skip, 0))
267     DECL_VINDEX (new_decl) = NULL_TREE;
268
269   /* When signature changes, we need to clear builtin info.  */
270   if (DECL_BUILT_IN (new_decl)
271       && args_to_skip
272       && !bitmap_empty_p (args_to_skip))
273     {
274       DECL_BUILT_IN_CLASS (new_decl) = NOT_BUILT_IN;
275       DECL_FUNCTION_CODE (new_decl) = (enum built_in_function) 0;
276     }
277   /* The FE might have information and assumptions about the other
278      arguments.  */
279   DECL_LANG_SPECIFIC (new_decl) = NULL;
280   return new_decl;
281 }
282
283 /* Set flags of NEW_NODE and its decl.  NEW_NODE is a newly created private
284    clone or its thunk.  */
285
286 static void
287 set_new_clone_decl_and_node_flags (cgraph_node *new_node)
288 {
289   DECL_EXTERNAL (new_node->decl) = 0;
290   TREE_PUBLIC (new_node->decl) = 0;
291   DECL_COMDAT (new_node->decl) = 0;
292   DECL_WEAK (new_node->decl) = 0;
293   DECL_VIRTUAL_P (new_node->decl) = 0;
294   DECL_STATIC_CONSTRUCTOR (new_node->decl) = 0;
295   DECL_STATIC_DESTRUCTOR (new_node->decl) = 0;
296
297   new_node->externally_visible = 0;
298   new_node->local.local = 1;
299   new_node->lowered = true;
300 }
301
302 /* Duplicate thunk THUNK if necessary but make it to refer to NODE.
303    ARGS_TO_SKIP, if non-NULL, determines which parameters should be omitted.
304    Function can return NODE if no thunk is necessary, which can happen when
305    thunk is this_adjusting but we are removing this parameter.  */
306
307 static cgraph_node *
308 duplicate_thunk_for_node (cgraph_node *thunk, cgraph_node *node)
309 {
310   cgraph_node *new_thunk, *thunk_of;
311   thunk_of = thunk->callees->callee->ultimate_alias_target ();
312
313   if (thunk_of->thunk.thunk_p)
314     node = duplicate_thunk_for_node (thunk_of, node);
315
316   if (!DECL_ARGUMENTS (thunk->decl))
317     thunk->get_untransformed_body ();
318
319   cgraph_edge *cs;
320   for (cs = node->callers; cs; cs = cs->next_caller)
321     if (cs->caller->thunk.thunk_p
322         && cs->caller->thunk.this_adjusting == thunk->thunk.this_adjusting
323         && cs->caller->thunk.fixed_offset == thunk->thunk.fixed_offset
324         && cs->caller->thunk.virtual_offset_p == thunk->thunk.virtual_offset_p
325         && cs->caller->thunk.virtual_value == thunk->thunk.virtual_value)
326       return cs->caller;
327
328   tree new_decl;
329   if (!node->clone.args_to_skip)
330     new_decl = copy_node (thunk->decl);
331   else
332     {
333       /* We do not need to duplicate this_adjusting thunks if we have removed
334          this.  */
335       if (thunk->thunk.this_adjusting
336           && bitmap_bit_p (node->clone.args_to_skip, 0))
337         return node;
338
339       new_decl = build_function_decl_skip_args (thunk->decl,
340                                                 node->clone.args_to_skip,
341                                                 false);
342     }
343
344   tree *link = &DECL_ARGUMENTS (new_decl);
345   int i = 0;
346   for (tree pd = DECL_ARGUMENTS (thunk->decl); pd; pd = DECL_CHAIN (pd), i++)
347     {
348       if (!node->clone.args_to_skip
349           || !bitmap_bit_p (node->clone.args_to_skip, i))
350         {
351           tree nd = copy_node (pd);
352           DECL_CONTEXT (nd) = new_decl;
353           *link = nd;
354           link = &DECL_CHAIN (nd);
355         }
356     }
357   *link = NULL_TREE;
358
359   gcc_checking_assert (!DECL_STRUCT_FUNCTION (new_decl));
360   gcc_checking_assert (!DECL_INITIAL (new_decl));
361   gcc_checking_assert (!DECL_RESULT (new_decl));
362   gcc_checking_assert (!DECL_RTL_SET_P (new_decl));
363
364   DECL_NAME (new_decl) = clone_function_name (thunk->decl, "artificial_thunk");
365   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
366
367   new_thunk = cgraph_node::create (new_decl);
368   set_new_clone_decl_and_node_flags (new_thunk);
369   new_thunk->definition = true;
370   new_thunk->thunk = thunk->thunk;
371   new_thunk->unique_name = in_lto_p;
372   new_thunk->former_clone_of = thunk->decl;
373   new_thunk->clone.args_to_skip = node->clone.args_to_skip;
374   new_thunk->clone.combined_args_to_skip = node->clone.combined_args_to_skip;
375
376   cgraph_edge *e = new_thunk->create_edge (node, NULL, 0,
377                                                   CGRAPH_FREQ_BASE);
378   e->call_stmt_cannot_inline_p = true;
379   symtab->call_edge_duplication_hooks (thunk->callees, e);
380   symtab->call_cgraph_duplication_hooks (thunk, new_thunk);
381   return new_thunk;
382 }
383
384 /* If E does not lead to a thunk, simply redirect it to N.  Otherwise create
385    one or more equivalent thunks for N and redirect E to the first in the
386    chain.  Note that it is then necessary to call
387    n->expand_all_artificial_thunks once all callers are redirected.  */
388
389 void
390 cgraph_edge::redirect_callee_duplicating_thunks (cgraph_node *n)
391 {
392   cgraph_node *orig_to = callee->ultimate_alias_target ();
393   if (orig_to->thunk.thunk_p)
394     n = duplicate_thunk_for_node (orig_to, n);
395
396   redirect_callee (n);
397 }
398
399 /* Call expand_thunk on all callers that are thunks and if analyze those nodes
400    that were expanded.  */
401
402 void
403 cgraph_node::expand_all_artificial_thunks ()
404 {
405   cgraph_edge *e;
406   for (e = callers; e;)
407     if (e->caller->thunk.thunk_p)
408       {
409         cgraph_node *thunk = e->caller;
410
411         e = e->next_caller;
412         if (thunk->expand_thunk (false, false))
413           {
414             thunk->thunk.thunk_p = false;
415             thunk->analyze ();
416           }
417         thunk->expand_all_artificial_thunks ();
418       }
419     else
420       e = e->next_caller;
421 }
422
423 /* Create node representing clone of N executed COUNT times.  Decrease
424    the execution counts from original node too.
425    The new clone will have decl set to DECL that may or may not be the same
426    as decl of N.
427
428    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
429    function's profile to reflect the fact that part of execution is handled
430    by node.  
431    When CALL_DUPLICATOIN_HOOK is true, the ipa passes are acknowledged about
432    the new clone. Otherwise the caller is responsible for doing so later.
433
434    If the new node is being inlined into another one, NEW_INLINED_TO should be
435    the outline function the new one is (even indirectly) inlined to.  All hooks
436    will see this in node's global.inlined_to, when invoked.  Can be NULL if the
437    node is not inlined.  */
438
439 cgraph_node *
440 cgraph_node::create_clone (tree decl, gcov_type gcov_count, int freq,
441                            bool update_original,
442                            vec<cgraph_edge *> redirect_callers,
443                            bool call_duplication_hook,
444                            cgraph_node *new_inlined_to,
445                            bitmap args_to_skip)
446 {
447   cgraph_node *new_node = symtab->create_empty ();
448   cgraph_edge *e;
449   gcov_type count_scale;
450   unsigned i;
451
452   new_node->decl = decl;
453   new_node->register_symbol ();
454   new_node->origin = origin;
455   new_node->lto_file_data = lto_file_data;
456   if (new_node->origin)
457     {
458       new_node->next_nested = new_node->origin->nested;
459       new_node->origin->nested = new_node;
460     }
461   new_node->analyzed = analyzed;
462   new_node->definition = definition;
463   new_node->local = local;
464   new_node->externally_visible = false;
465   new_node->no_reorder = no_reorder;
466   new_node->local.local = true;
467   new_node->global = global;
468   new_node->global.inlined_to = new_inlined_to;
469   new_node->rtl = rtl;
470   new_node->count = count;
471   new_node->frequency = frequency;
472   new_node->tp_first_run = tp_first_run;
473   new_node->tm_clone = tm_clone;
474
475   new_node->clone.tree_map = NULL;
476   new_node->clone.args_to_skip = args_to_skip;
477   if (!args_to_skip)
478     new_node->clone.combined_args_to_skip = clone.combined_args_to_skip;
479   else if (clone.combined_args_to_skip)
480     {
481       new_node->clone.combined_args_to_skip = BITMAP_GGC_ALLOC ();
482       bitmap_ior (new_node->clone.combined_args_to_skip,
483                   clone.combined_args_to_skip, args_to_skip);
484     }
485   else
486     new_node->clone.combined_args_to_skip = args_to_skip;
487
488   if (count)
489     {
490       if (new_node->count > count)
491         count_scale = REG_BR_PROB_BASE;
492       else
493         count_scale = GCOV_COMPUTE_SCALE (new_node->count, count);
494     }
495   else
496     count_scale = 0;
497   if (update_original)
498     {
499       count -= gcov_count;
500       if (count < 0)
501         count = 0;
502     }
503
504   FOR_EACH_VEC_ELT (redirect_callers, i, e)
505     {
506       /* Redirect calls to the old version node to point to its new
507          version.  The only exception is when the edge was proved to
508          be unreachable during the clonning procedure.  */
509       if (!e->callee
510           || DECL_BUILT_IN_CLASS (e->callee->decl) != BUILT_IN_NORMAL
511           || DECL_FUNCTION_CODE (e->callee->decl) != BUILT_IN_UNREACHABLE)
512         e->redirect_callee_duplicating_thunks (new_node);
513     }
514   new_node->expand_all_artificial_thunks ();
515
516   for (e = callees;e; e=e->next_callee)
517     e->clone (new_node, e->call_stmt, e->lto_stmt_uid, count_scale,
518               freq, update_original);
519
520   for (e = indirect_calls; e; e = e->next_callee)
521     e->clone (new_node, e->call_stmt, e->lto_stmt_uid,
522               count_scale, freq, update_original);
523   new_node->clone_references (this);
524
525   new_node->next_sibling_clone = clones;
526   if (clones)
527     clones->prev_sibling_clone = new_node;
528   clones = new_node;
529   new_node->clone_of = this;
530
531   if (call_duplication_hook)
532     symtab->call_cgraph_duplication_hooks (this, new_node);
533   return new_node;
534 }
535
536 /* Return a new assembler name for a clone of DECL with SUFFIX.  */
537
538 static GTY(()) unsigned int clone_fn_id_num;
539
540 tree
541 clone_function_name (tree decl, const char *suffix)
542 {
543   tree name = DECL_ASSEMBLER_NAME (decl);
544   size_t len = IDENTIFIER_LENGTH (name);
545   char *tmp_name, *prefix;
546
547   prefix = XALLOCAVEC (char, len + strlen (suffix) + 2);
548   memcpy (prefix, IDENTIFIER_POINTER (name), len);
549   strcpy (prefix + len + 1, suffix);
550 #ifndef NO_DOT_IN_LABEL
551   prefix[len] = '.';
552 #elif !defined NO_DOLLAR_IN_LABEL
553   prefix[len] = '$';
554 #else
555   prefix[len] = '_';
556 #endif
557   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
558   return get_identifier (tmp_name);
559 }
560
561 /* Create callgraph node clone with new declaration.  The actual body will
562    be copied later at compilation stage.
563
564    TODO: after merging in ipa-sra use function call notes instead of args_to_skip
565    bitmap interface.
566    */
567 cgraph_node *
568 cgraph_node::create_virtual_clone (vec<cgraph_edge *> redirect_callers,
569                                    vec<ipa_replace_map *, va_gc> *tree_map,
570                                    bitmap args_to_skip, const char * suffix)
571 {
572   tree old_decl = decl;
573   cgraph_node *new_node = NULL;
574   tree new_decl;
575   size_t len, i;
576   ipa_replace_map *map;
577   char *name;
578
579   if (!in_lto_p)
580     gcc_checking_assert  (tree_versionable_function_p (old_decl));
581
582   gcc_assert (local.can_change_signature || !args_to_skip);
583
584   /* Make a new FUNCTION_DECL tree node */
585   if (!args_to_skip)
586     new_decl = copy_node (old_decl);
587   else
588     new_decl = build_function_decl_skip_args (old_decl, args_to_skip, false);
589
590   /* These pointers represent function body and will be populated only when clone
591      is materialized.  */
592   gcc_assert (new_decl != old_decl);
593   DECL_STRUCT_FUNCTION (new_decl) = NULL;
594   DECL_ARGUMENTS (new_decl) = NULL;
595   DECL_INITIAL (new_decl) = NULL;
596   DECL_RESULT (new_decl) = NULL; 
597   /* We can not do DECL_RESULT (new_decl) = NULL; here because of LTO partitioning
598      sometimes storing only clone decl instead of original.  */
599
600   /* Generate a new name for the new version. */
601   len = IDENTIFIER_LENGTH (DECL_NAME (old_decl));
602   name = XALLOCAVEC (char, len + strlen (suffix) + 2);
603   memcpy (name, IDENTIFIER_POINTER (DECL_NAME (old_decl)), len);
604   strcpy (name + len + 1, suffix);
605   name[len] = '.';
606   DECL_NAME (new_decl) = get_identifier (name);
607   SET_DECL_ASSEMBLER_NAME (new_decl, clone_function_name (old_decl, suffix));
608   SET_DECL_RTL (new_decl, NULL);
609
610   new_node = create_clone (new_decl, count, CGRAPH_FREQ_BASE, false,
611                            redirect_callers, false, NULL, args_to_skip);
612
613   /* Update the properties.
614      Make clone visible only within this translation unit.  Make sure
615      that is not weak also.
616      ??? We cannot use COMDAT linkage because there is no
617      ABI support for this.  */
618   set_new_clone_decl_and_node_flags (new_node);
619   new_node->clone.tree_map = tree_map;
620
621   /* Clones of global symbols or symbols with unique names are unique.  */
622   if ((TREE_PUBLIC (old_decl)
623        && !DECL_EXTERNAL (old_decl)
624        && !DECL_WEAK (old_decl)
625        && !DECL_COMDAT (old_decl))
626       || in_lto_p)
627     new_node->unique_name = true;
628   FOR_EACH_VEC_SAFE_ELT (tree_map, i, map)
629     new_node->maybe_create_reference (map->new_tree, IPA_REF_ADDR, NULL);
630
631   if (ipa_transforms_to_apply.exists ())
632     new_node->ipa_transforms_to_apply
633       = ipa_transforms_to_apply.copy ();
634
635   symtab->call_cgraph_duplication_hooks (this, new_node);
636
637   return new_node;
638 }
639
640 /* callgraph node being removed from symbol table; see if its entry can be
641    replaced by other inline clone.  */
642 cgraph_node *
643 cgraph_node::find_replacement (void)
644 {
645   cgraph_node *next_inline_clone, *replacement;
646
647   for (next_inline_clone = clones;
648        next_inline_clone
649        && next_inline_clone->decl != decl;
650        next_inline_clone = next_inline_clone->next_sibling_clone)
651     ;
652
653   /* If there is inline clone of the node being removed, we need
654      to put it into the position of removed node and reorganize all
655      other clones to be based on it.  */
656   if (next_inline_clone)
657     {
658       cgraph_node *n;
659       cgraph_node *new_clones;
660
661       replacement = next_inline_clone;
662
663       /* Unlink inline clone from the list of clones of removed node.  */
664       if (next_inline_clone->next_sibling_clone)
665         next_inline_clone->next_sibling_clone->prev_sibling_clone
666           = next_inline_clone->prev_sibling_clone;
667       if (next_inline_clone->prev_sibling_clone)
668         {
669           gcc_assert (clones != next_inline_clone);
670           next_inline_clone->prev_sibling_clone->next_sibling_clone
671             = next_inline_clone->next_sibling_clone;
672         }
673       else
674         {
675           gcc_assert (clones == next_inline_clone);
676           clones = next_inline_clone->next_sibling_clone;
677         }
678
679       new_clones = clones;
680       clones = NULL;
681
682       /* Copy clone info.  */
683       next_inline_clone->clone = clone;
684
685       /* Now place it into clone tree at same level at NODE.  */
686       next_inline_clone->clone_of = clone_of;
687       next_inline_clone->prev_sibling_clone = NULL;
688       next_inline_clone->next_sibling_clone = NULL;
689       if (clone_of)
690         {
691           if (clone_of->clones)
692             clone_of->clones->prev_sibling_clone = next_inline_clone;
693           next_inline_clone->next_sibling_clone = clone_of->clones;
694           clone_of->clones = next_inline_clone;
695         }
696
697       /* Merge the clone list.  */
698       if (new_clones)
699         {
700           if (!next_inline_clone->clones)
701             next_inline_clone->clones = new_clones;
702           else
703             {
704               n = next_inline_clone->clones;
705               while (n->next_sibling_clone)
706                 n = n->next_sibling_clone;
707               n->next_sibling_clone = new_clones;
708               new_clones->prev_sibling_clone = n;
709             }
710         }
711
712       /* Update clone_of pointers.  */
713       n = new_clones;
714       while (n)
715         {
716           n->clone_of = next_inline_clone;
717           n = n->next_sibling_clone;
718         }
719       return replacement;
720     }
721   else
722     return NULL;
723 }
724
725 /* Like cgraph_set_call_stmt but walk the clone tree and update all
726    clones sharing the same function body.  
727    When WHOLE_SPECULATIVE_EDGES is true, all three components of
728    speculative edge gets updated.  Otherwise we update only direct
729    call.  */
730
731 void
732 cgraph_node::set_call_stmt_including_clones (gimple old_stmt,
733                                              gcall *new_stmt,
734                                              bool update_speculative)
735 {
736   cgraph_node *node;
737   cgraph_edge *edge = get_edge (old_stmt);
738
739   if (edge)
740     edge->set_call_stmt (new_stmt, update_speculative);
741
742   node = clones;
743   if (node)
744     while (node != this)
745       {
746         cgraph_edge *edge = node->get_edge (old_stmt);
747         if (edge)
748           {
749             edge->set_call_stmt (new_stmt, update_speculative);
750             /* If UPDATE_SPECULATIVE is false, it means that we are turning
751                speculative call into a real code sequence.  Update the
752                callgraph edges.  */
753             if (edge->speculative && !update_speculative)
754               {
755                 cgraph_edge *direct, *indirect;
756                 ipa_ref *ref;
757
758                 gcc_assert (!edge->indirect_unknown_callee);
759                 edge->speculative_call_info (direct, indirect, ref);
760                 direct->speculative = false;
761                 indirect->speculative = false;
762                 ref->speculative = false;
763               }
764           }
765         if (node->clones)
766           node = node->clones;
767         else if (node->next_sibling_clone)
768           node = node->next_sibling_clone;
769         else
770           {
771             while (node != this && !node->next_sibling_clone)
772               node = node->clone_of;
773             if (node != this)
774               node = node->next_sibling_clone;
775           }
776       }
777 }
778
779 /* Like cgraph_create_edge walk the clone tree and update all clones sharing
780    same function body.  If clones already have edge for OLD_STMT; only
781    update the edge same way as cgraph_set_call_stmt_including_clones does.
782
783    TODO: COUNT and LOOP_DEPTH should be properly distributed based on relative
784    frequencies of the clones.  */
785
786 void
787 cgraph_node::create_edge_including_clones (cgraph_node *callee,
788                                            gimple old_stmt, gcall *stmt,
789                                            gcov_type count,
790                                            int freq,
791                                            cgraph_inline_failed_t reason)
792 {
793   cgraph_node *node;
794   cgraph_edge *edge;
795
796   if (!get_edge (stmt))
797     {
798       edge = create_edge (callee, stmt, count, freq);
799       edge->inline_failed = reason;
800     }
801
802   node = clones;
803   if (node)
804     while (node != this)
805       {
806         cgraph_edge *edge = node->get_edge (old_stmt);
807
808         /* It is possible that clones already contain the edge while
809            master didn't.  Either we promoted indirect call into direct
810            call in the clone or we are processing clones of unreachable
811            master where edges has been removed.  */
812         if (edge)
813           edge->set_call_stmt (stmt);
814         else if (! node->get_edge (stmt))
815           {
816             edge = node->create_edge (callee, stmt, count, freq);
817             edge->inline_failed = reason;
818           }
819
820         if (node->clones)
821           node = node->clones;
822         else if (node->next_sibling_clone)
823           node = node->next_sibling_clone;
824         else
825           {
826             while (node != this && !node->next_sibling_clone)
827               node = node->clone_of;
828             if (node != this)
829               node = node->next_sibling_clone;
830           }
831       }
832 }
833
834 /* Remove the node from cgraph and all inline clones inlined into it.
835    Skip however removal of FORBIDDEN_NODE and return true if it needs to be
836    removed.  This allows to call the function from outer loop walking clone
837    tree.  */
838
839 bool
840 cgraph_node::remove_symbol_and_inline_clones (cgraph_node *forbidden_node)
841 {
842   cgraph_edge *e, *next;
843   bool found = false;
844
845   if (this == forbidden_node)
846     {
847       callers->remove ();
848       return true;
849     }
850   for (e = callees; e; e = next)
851     {
852       next = e->next_callee;
853       if (!e->inline_failed)
854         found |= e->callee->remove_symbol_and_inline_clones (forbidden_node);
855     }
856   remove ();
857   return found;
858 }
859
860 /* The edges representing the callers of the NEW_VERSION node were
861    fixed by cgraph_function_versioning (), now the call_expr in their
862    respective tree code should be updated to call the NEW_VERSION.  */
863
864 static void
865 update_call_expr (cgraph_node *new_version)
866 {
867   cgraph_edge *e;
868
869   gcc_assert (new_version);
870
871   /* Update the call expr on the edges to call the new version.  */
872   for (e = new_version->callers; e; e = e->next_caller)
873     {
874       function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
875       gimple_call_set_fndecl (e->call_stmt, new_version->decl);
876       maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
877     }
878 }
879
880
881 /* Create a new cgraph node which is the new version of
882    callgraph node.  REDIRECT_CALLERS holds the callers
883    edges which should be redirected to point to
884    NEW_VERSION.  ALL the callees edges of the node
885    are cloned to the new version node.  Return the new
886    version node. 
887
888    If non-NULL BLOCK_TO_COPY determine what basic blocks 
889    was copied to prevent duplications of calls that are dead
890    in the clone.  */
891
892 cgraph_node *
893 cgraph_node::create_version_clone (tree new_decl,
894                                   vec<cgraph_edge *> redirect_callers,
895                                   bitmap bbs_to_copy)
896  {
897    cgraph_node *new_version;
898    cgraph_edge *e;
899    unsigned i;
900
901    new_version = cgraph_node::create (new_decl);
902
903    new_version->analyzed = analyzed;
904    new_version->definition = definition;
905    new_version->local = local;
906    new_version->externally_visible = false;
907    new_version->no_reorder = no_reorder;
908    new_version->local.local = new_version->definition;
909    new_version->global = global;
910    new_version->rtl = rtl;
911    new_version->count = count;
912
913    for (e = callees; e; e=e->next_callee)
914      if (!bbs_to_copy
915          || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
916        e->clone (new_version, e->call_stmt,
917                  e->lto_stmt_uid, REG_BR_PROB_BASE,
918                  CGRAPH_FREQ_BASE,
919                  true);
920    for (e = indirect_calls; e; e=e->next_callee)
921      if (!bbs_to_copy
922          || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
923        e->clone (new_version, e->call_stmt,
924                  e->lto_stmt_uid, REG_BR_PROB_BASE,
925                  CGRAPH_FREQ_BASE,
926                  true);
927    FOR_EACH_VEC_ELT (redirect_callers, i, e)
928      {
929        /* Redirect calls to the old version node to point to its new
930           version.  */
931        e->redirect_callee (new_version);
932      }
933
934    symtab->call_cgraph_duplication_hooks (this, new_version);
935
936    return new_version;
937  }
938
939 /* Perform function versioning.
940    Function versioning includes copying of the tree and
941    a callgraph update (creating a new cgraph node and updating
942    its callees and callers).
943
944    REDIRECT_CALLERS varray includes the edges to be redirected
945    to the new version.
946
947    TREE_MAP is a mapping of tree nodes we want to replace with
948    new ones (according to results of prior analysis).
949
950    If non-NULL ARGS_TO_SKIP determine function parameters to remove
951    from new version.
952    If SKIP_RETURN is true, the new version will return void.
953    If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
954    If non_NULL NEW_ENTRY determine new entry BB of the clone.
955
956    Return the new version's cgraph node.  */
957
958 cgraph_node *
959 cgraph_node::create_version_clone_with_body
960   (vec<cgraph_edge *> redirect_callers,
961    vec<ipa_replace_map *, va_gc> *tree_map, bitmap args_to_skip,
962    bool skip_return, bitmap bbs_to_copy, basic_block new_entry_block,
963    const char *clone_name)
964 {
965   tree old_decl = decl;
966   cgraph_node *new_version_node = NULL;
967   tree new_decl;
968
969   if (!tree_versionable_function_p (old_decl))
970     return NULL;
971
972   gcc_assert (local.can_change_signature || !args_to_skip);
973
974   /* Make a new FUNCTION_DECL tree node for the new version. */
975   if (!args_to_skip && !skip_return)
976     new_decl = copy_node (old_decl);
977   else
978     new_decl
979       = build_function_decl_skip_args (old_decl, args_to_skip, skip_return);
980
981   /* Generate a new name for the new version. */
982   DECL_NAME (new_decl) = clone_function_name (old_decl, clone_name);
983   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
984   SET_DECL_RTL (new_decl, NULL);
985
986   /* When the old decl was a con-/destructor make sure the clone isn't.  */
987   DECL_STATIC_CONSTRUCTOR (new_decl) = 0;
988   DECL_STATIC_DESTRUCTOR (new_decl) = 0;
989
990   /* Create the new version's call-graph node.
991      and update the edges of the new node. */
992   new_version_node = create_version_clone (new_decl, redirect_callers,
993                                           bbs_to_copy);
994
995   if (ipa_transforms_to_apply.exists ())
996     new_version_node->ipa_transforms_to_apply
997       = ipa_transforms_to_apply.copy ();
998   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
999   tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip,
1000                             skip_return, bbs_to_copy, new_entry_block);
1001
1002   /* Update the new version's properties.
1003      Make The new version visible only within this translation unit.  Make sure
1004      that is not weak also.
1005      ??? We cannot use COMDAT linkage because there is no
1006      ABI support for this.  */
1007   new_version_node->make_decl_local ();
1008   DECL_VIRTUAL_P (new_version_node->decl) = 0;
1009   new_version_node->externally_visible = 0;
1010   new_version_node->local.local = 1;
1011   new_version_node->lowered = true;
1012   /* Clones of global symbols or symbols with unique names are unique.  */
1013   if ((TREE_PUBLIC (old_decl)
1014        && !DECL_EXTERNAL (old_decl)
1015        && !DECL_WEAK (old_decl)
1016        && !DECL_COMDAT (old_decl))
1017       || in_lto_p)
1018     new_version_node->unique_name = true;
1019
1020   /* Update the call_expr on the edges to call the new version node. */
1021   update_call_expr (new_version_node);
1022
1023   symtab->call_cgraph_insertion_hooks (this);
1024   return new_version_node;
1025 }
1026
1027 /* Given virtual clone, turn it into actual clone.  */
1028
1029 static void
1030 cgraph_materialize_clone (cgraph_node *node)
1031 {
1032   bitmap_obstack_initialize (NULL);
1033   node->former_clone_of = node->clone_of->decl;
1034   if (node->clone_of->former_clone_of)
1035     node->former_clone_of = node->clone_of->former_clone_of;
1036   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1037   tree_function_versioning (node->clone_of->decl, node->decl,
1038                             node->clone.tree_map, true,
1039                             node->clone.args_to_skip, false,
1040                             NULL, NULL);
1041   if (symtab->dump_file)
1042     {
1043       dump_function_to_file (node->clone_of->decl, symtab->dump_file,
1044                              dump_flags);
1045       dump_function_to_file (node->decl, symtab->dump_file, dump_flags);
1046     }
1047
1048   /* Function is no longer clone.  */
1049   if (node->next_sibling_clone)
1050     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1051   if (node->prev_sibling_clone)
1052     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1053   else
1054     node->clone_of->clones = node->next_sibling_clone;
1055   node->next_sibling_clone = NULL;
1056   node->prev_sibling_clone = NULL;
1057   if (!node->clone_of->analyzed && !node->clone_of->clones)
1058     {
1059       node->clone_of->release_body ();
1060       node->clone_of->remove_callees ();
1061       node->clone_of->remove_all_references ();
1062     }
1063   node->clone_of = NULL;
1064   bitmap_obstack_release (NULL);
1065 }
1066
1067 /* Once all functions from compilation unit are in memory, produce all clones
1068    and update all calls.  We might also do this on demand if we don't want to
1069    bring all functions to memory prior compilation, but current WHOPR
1070    implementation does that and it is is bit easier to keep everything right in
1071    this order.  */
1072
1073 void
1074 symbol_table::materialize_all_clones (void)
1075 {
1076   cgraph_node *node;
1077   bool stabilized = false;
1078   
1079
1080   if (symtab->dump_file)
1081     fprintf (symtab->dump_file, "Materializing clones\n");
1082 #ifdef ENABLE_CHECKING
1083   cgraph_node::verify_cgraph_nodes ();
1084 #endif
1085
1086   /* We can also do topological order, but number of iterations should be
1087      bounded by number of IPA passes since single IPA pass is probably not
1088      going to create clones of clones it created itself.  */
1089   while (!stabilized)
1090     {
1091       stabilized = true;
1092       FOR_EACH_FUNCTION (node)
1093         {
1094           if (node->clone_of && node->decl != node->clone_of->decl
1095               && !gimple_has_body_p (node->decl))
1096             {
1097               if (!node->clone_of->clone_of)
1098                 node->clone_of->get_untransformed_body ();
1099               if (gimple_has_body_p (node->clone_of->decl))
1100                 {
1101                   if (symtab->dump_file)
1102                     {
1103                       fprintf (symtab->dump_file, "cloning %s to %s\n",
1104                                xstrdup_for_dump (node->clone_of->name ()),
1105                                xstrdup_for_dump (node->name ()));
1106                       if (node->clone.tree_map)
1107                         {
1108                           unsigned int i;
1109                           fprintf (symtab->dump_file, "   replace map: ");
1110                           for (i = 0;
1111                                i < vec_safe_length (node->clone.tree_map);
1112                                i++)
1113                             {
1114                               ipa_replace_map *replace_info;
1115                               replace_info = (*node->clone.tree_map)[i];
1116                               print_generic_expr (symtab->dump_file, replace_info->old_tree, 0);
1117                               fprintf (symtab->dump_file, " -> ");
1118                               print_generic_expr (symtab->dump_file, replace_info->new_tree, 0);
1119                               fprintf (symtab->dump_file, "%s%s;",
1120                                        replace_info->replace_p ? "(replace)":"",
1121                                        replace_info->ref_p ? "(ref)":"");
1122                             }
1123                           fprintf (symtab->dump_file, "\n");
1124                         }
1125                       if (node->clone.args_to_skip)
1126                         {
1127                           fprintf (symtab->dump_file, "   args_to_skip: ");
1128                           dump_bitmap (symtab->dump_file,
1129                                        node->clone.args_to_skip);
1130                         }
1131                       if (node->clone.args_to_skip)
1132                         {
1133                           fprintf (symtab->dump_file, "   combined_args_to_skip:");
1134                           dump_bitmap (symtab->dump_file, node->clone.combined_args_to_skip);
1135                         }
1136                     }
1137                   cgraph_materialize_clone (node);
1138                   stabilized = false;
1139                 }
1140             }
1141         }
1142     }
1143   FOR_EACH_FUNCTION (node)
1144     if (!node->analyzed && node->callees)
1145       {
1146         node->remove_callees ();
1147         node->remove_all_references ();
1148       }
1149     else
1150       node->clear_stmts_in_references ();
1151   if (symtab->dump_file)
1152     fprintf (symtab->dump_file, "Materialization Call site updates done.\n");
1153 #ifdef ENABLE_CHECKING
1154   cgraph_node::verify_cgraph_nodes ();
1155 #endif
1156   symtab->remove_unreachable_nodes (symtab->dump_file);
1157 }
1158
1159 #include "gt-cgraphclones.h"