Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / ipa-utils.c
1 /* Utilities for ipa analysis.
2    Copyright (C) 2005-2015 Free Software Foundation, Inc.
3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "options.h"
33 #include "wide-int.h"
34 #include "inchash.h"
35 #include "tree.h"
36 #include "fold-const.h"
37 #include "predict.h"
38 #include "hard-reg-set.h"
39 #include "input.h"
40 #include "function.h"
41 #include "dominance.h"
42 #include "cfg.h"
43 #include "basic-block.h"
44 #include "tree-ssa-alias.h"
45 #include "internal-fn.h"
46 #include "gimple-expr.h"
47 #include "is-a.h"
48 #include "gimple.h"
49 #include "tree-inline.h"
50 #include "dumpfile.h"
51 #include "langhooks.h"
52 #include "splay-tree.h"
53 #include "hash-map.h"
54 #include "plugin-api.h"
55 #include "ipa-ref.h"
56 #include "cgraph.h"
57 #include "ipa-utils.h"
58 #include "bitmap.h"
59 #include "ipa-reference.h"
60 #include "flags.h"
61 #include "diagnostic.h"
62 #include "langhooks.h"
63 #include "lto-streamer.h"
64 #include "alloc-pool.h"
65 #include "symbol-summary.h"
66 #include "ipa-prop.h"
67 #include "ipa-inline.h"
68
69 /* Debugging function for postorder and inorder code. NOTE is a string
70    that is printed before the nodes are printed.  ORDER is an array of
71    cgraph_nodes that has COUNT useful nodes in it.  */
72
73 void
74 ipa_print_order (FILE* out,
75                  const char * note,
76                  struct cgraph_node** order,
77                  int count)
78 {
79   int i;
80   fprintf (out, "\n\n ordered call graph: %s\n", note);
81
82   for (i = count - 1; i >= 0; i--)
83     order[i]->dump (out);
84   fprintf (out, "\n");
85   fflush (out);
86 }
87
88
89 struct searchc_env {
90   struct cgraph_node **stack;
91   int stack_size;
92   struct cgraph_node **result;
93   int order_pos;
94   splay_tree nodes_marked_new;
95   bool reduce;
96   bool allow_overwritable;
97   int count;
98 };
99
100 /* This is an implementation of Tarjan's strongly connected region
101    finder as reprinted in Aho Hopcraft and Ullman's The Design and
102    Analysis of Computer Programs (1975) pages 192-193.  This version
103    has been customized for cgraph_nodes.  The env parameter is because
104    it is recursive and there are no nested functions here.  This
105    function should only be called from itself or
106    ipa_reduced_postorder.  ENV is a stack env and would be
107    unnecessary if C had nested functions.  V is the node to start
108    searching from.  */
109
110 static void
111 searchc (struct searchc_env* env, struct cgraph_node *v,
112          bool (*ignore_edge) (struct cgraph_edge *))
113 {
114   struct cgraph_edge *edge;
115   struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
116
117   /* mark node as old */
118   v_info->new_node = false;
119   splay_tree_remove (env->nodes_marked_new, v->uid);
120
121   v_info->dfn_number = env->count;
122   v_info->low_link = env->count;
123   env->count++;
124   env->stack[(env->stack_size)++] = v;
125   v_info->on_stack = true;
126
127   for (edge = v->callees; edge; edge = edge->next_callee)
128     {
129       struct ipa_dfs_info * w_info;
130       enum availability avail;
131       struct cgraph_node *w = edge->callee->ultimate_alias_target (&avail);
132
133       if (!w || (ignore_edge && ignore_edge (edge)))
134         continue;
135
136       if (w->aux
137           && (avail > AVAIL_INTERPOSABLE
138               || (env->allow_overwritable && avail == AVAIL_INTERPOSABLE)))
139         {
140           w_info = (struct ipa_dfs_info *) w->aux;
141           if (w_info->new_node)
142             {
143               searchc (env, w, ignore_edge);
144               v_info->low_link =
145                 (v_info->low_link < w_info->low_link) ?
146                 v_info->low_link : w_info->low_link;
147             }
148           else
149             if ((w_info->dfn_number < v_info->dfn_number)
150                 && (w_info->on_stack))
151               v_info->low_link =
152                 (w_info->dfn_number < v_info->low_link) ?
153                 w_info->dfn_number : v_info->low_link;
154         }
155     }
156
157
158   if (v_info->low_link == v_info->dfn_number)
159     {
160       struct cgraph_node *last = NULL;
161       struct cgraph_node *x;
162       struct ipa_dfs_info *x_info;
163       do {
164         x = env->stack[--(env->stack_size)];
165         x_info = (struct ipa_dfs_info *) x->aux;
166         x_info->on_stack = false;
167         x_info->scc_no = v_info->dfn_number;
168
169         if (env->reduce)
170           {
171             x_info->next_cycle = last;
172             last = x;
173           }
174         else
175           env->result[env->order_pos++] = x;
176       }
177       while (v != x);
178       if (env->reduce)
179         env->result[env->order_pos++] = v;
180     }
181 }
182
183 /* Topsort the call graph by caller relation.  Put the result in ORDER.
184
185    The REDUCE flag is true if you want the cycles reduced to single nodes.
186    You can use ipa_get_nodes_in_cycle to obtain a vector containing all real
187    call graph nodes in a reduced node.
188
189    Set ALLOW_OVERWRITABLE if nodes with such availability should be included.
190    IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
191    for the topological sort.   */
192
193 int
194 ipa_reduced_postorder (struct cgraph_node **order,
195                        bool reduce, bool allow_overwritable,
196                        bool (*ignore_edge) (struct cgraph_edge *))
197 {
198   struct cgraph_node *node;
199   struct searchc_env env;
200   splay_tree_node result;
201   env.stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
202   env.stack_size = 0;
203   env.result = order;
204   env.order_pos = 0;
205   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
206   env.count = 1;
207   env.reduce = reduce;
208   env.allow_overwritable = allow_overwritable;
209
210   FOR_EACH_DEFINED_FUNCTION (node)
211     {
212       enum availability avail = node->get_availability ();
213
214       if (avail > AVAIL_INTERPOSABLE
215           || (allow_overwritable
216               && (avail == AVAIL_INTERPOSABLE)))
217         {
218           /* Reuse the info if it is already there.  */
219           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
220           if (!info)
221             info = XCNEW (struct ipa_dfs_info);
222           info->new_node = true;
223           info->on_stack = false;
224           info->next_cycle = NULL;
225           node->aux = info;
226
227           splay_tree_insert (env.nodes_marked_new,
228                              (splay_tree_key)node->uid,
229                              (splay_tree_value)node);
230         }
231       else
232         node->aux = NULL;
233     }
234   result = splay_tree_min (env.nodes_marked_new);
235   while (result)
236     {
237       node = (struct cgraph_node *)result->value;
238       searchc (&env, node, ignore_edge);
239       result = splay_tree_min (env.nodes_marked_new);
240     }
241   splay_tree_delete (env.nodes_marked_new);
242   free (env.stack);
243
244   return env.order_pos;
245 }
246
247 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
248    graph nodes.  */
249
250 void
251 ipa_free_postorder_info (void)
252 {
253   struct cgraph_node *node;
254   FOR_EACH_DEFINED_FUNCTION (node)
255     {
256       /* Get rid of the aux information.  */
257       if (node->aux)
258         {
259           free (node->aux);
260           node->aux = NULL;
261         }
262     }
263 }
264
265 /* Get the set of nodes for the cycle in the reduced call graph starting
266    from NODE.  */
267
268 vec<cgraph_node *>
269 ipa_get_nodes_in_cycle (struct cgraph_node *node)
270 {
271   vec<cgraph_node *> v = vNULL;
272   struct ipa_dfs_info *node_dfs_info;
273   while (node)
274     {
275       v.safe_push (node);
276       node_dfs_info = (struct ipa_dfs_info *) node->aux;
277       node = node_dfs_info->next_cycle;
278     }
279   return v;
280 }
281
282 /* Return true iff the CS is an edge within a strongly connected component as
283    computed by ipa_reduced_postorder.  */
284
285 bool
286 ipa_edge_within_scc (struct cgraph_edge *cs)
287 {
288   struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux;
289   struct ipa_dfs_info *callee_dfs;
290   struct cgraph_node *callee = cs->callee->function_symbol ();
291
292   callee_dfs = (struct ipa_dfs_info *) callee->aux;
293   return (caller_dfs
294           && callee_dfs
295           && caller_dfs->scc_no == callee_dfs->scc_no);
296 }
297
298 struct postorder_stack
299 {
300   struct cgraph_node *node;
301   struct cgraph_edge *edge;
302   int ref;
303 };
304
305 /* Fill array order with all nodes with output flag set in the reverse
306    topological order.  Return the number of elements in the array.
307    FIXME: While walking, consider aliases, too.  */
308
309 int
310 ipa_reverse_postorder (struct cgraph_node **order)
311 {
312   struct cgraph_node *node, *node2;
313   int stack_size = 0;
314   int order_pos = 0;
315   struct cgraph_edge *edge;
316   int pass;
317   struct ipa_ref *ref = NULL;
318
319   struct postorder_stack *stack =
320     XCNEWVEC (struct postorder_stack, symtab->cgraph_count);
321
322   /* We have to deal with cycles nicely, so use a depth first traversal
323      output algorithm.  Ignore the fact that some functions won't need
324      to be output and put them into order as well, so we get dependencies
325      right through inline functions.  */
326   FOR_EACH_FUNCTION (node)
327     node->aux = NULL;
328   for (pass = 0; pass < 2; pass++)
329     FOR_EACH_FUNCTION (node)
330       if (!node->aux
331           && (pass
332               || (!node->address_taken
333                   && !node->global.inlined_to
334                   && !node->alias && !node->thunk.thunk_p
335                   && !node->only_called_directly_p ())))
336         {
337           stack_size = 0;
338           stack[stack_size].node = node;
339           stack[stack_size].edge = node->callers;
340           stack[stack_size].ref = 0;
341           node->aux = (void *)(size_t)1;
342           while (stack_size >= 0)
343             {
344               while (true)
345                 {
346                   node2 = NULL;
347                   while (stack[stack_size].edge && !node2)
348                     {
349                       edge = stack[stack_size].edge;
350                       node2 = edge->caller;
351                       stack[stack_size].edge = edge->next_caller;
352                       /* Break possible cycles involving always-inline
353                          functions by ignoring edges from always-inline
354                          functions to non-always-inline functions.  */
355                       if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
356                           && !DECL_DISREGARD_INLINE_LIMITS
357                             (edge->callee->function_symbol ()->decl))
358                         node2 = NULL;
359                     }
360                   for (; stack[stack_size].node->iterate_referring (
361                                                        stack[stack_size].ref,
362                                                        ref) && !node2;
363                        stack[stack_size].ref++)
364                     {
365                       if (ref->use == IPA_REF_ALIAS)
366                         node2 = dyn_cast <cgraph_node *> (ref->referring);
367                     }
368                   if (!node2)
369                     break;
370                   if (!node2->aux)
371                     {
372                       stack[++stack_size].node = node2;
373                       stack[stack_size].edge = node2->callers;
374                       stack[stack_size].ref = 0;
375                       node2->aux = (void *)(size_t)1;
376                     }
377                 }
378               order[order_pos++] = stack[stack_size--].node;
379             }
380         }
381   free (stack);
382   FOR_EACH_FUNCTION (node)
383     node->aux = NULL;
384   return order_pos;
385 }
386
387
388
389 /* Given a memory reference T, will return the variable at the bottom
390    of the access.  Unlike get_base_address, this will recurse through
391    INDIRECT_REFS.  */
392
393 tree
394 get_base_var (tree t)
395 {
396   while (!SSA_VAR_P (t)
397          && (!CONSTANT_CLASS_P (t))
398          && TREE_CODE (t) != LABEL_DECL
399          && TREE_CODE (t) != FUNCTION_DECL
400          && TREE_CODE (t) != CONST_DECL
401          && TREE_CODE (t) != CONSTRUCTOR)
402     {
403       t = TREE_OPERAND (t, 0);
404     }
405   return t;
406 }
407
408
409 /* SRC and DST are going to be merged.  Take SRC's profile and merge it into
410    DST so it is not going to be lost.  Possibly destroy SRC's body on the way
411    unless PRESERVE_BODY is set.  */
412
413 void
414 ipa_merge_profiles (struct cgraph_node *dst,
415                     struct cgraph_node *src,
416                     bool preserve_body)
417 {
418   tree oldsrcdecl = src->decl;
419   struct function *srccfun, *dstcfun;
420   bool match = true;
421
422   if (!src->definition
423       || !dst->definition)
424     return;
425   if (src->frequency < dst->frequency)
426     src->frequency = dst->frequency;
427
428   /* Time profiles are merged.  */
429   if (dst->tp_first_run > src->tp_first_run && src->tp_first_run)
430     dst->tp_first_run = src->tp_first_run;
431
432   if (src->profile_id && !dst->profile_id)
433     dst->profile_id = src->profile_id;
434
435   if (!dst->count)
436     return;
437   if (symtab->dump_file)
438     {
439       fprintf (symtab->dump_file, "Merging profiles of %s/%i to %s/%i\n",
440                xstrdup_for_dump (src->name ()), src->order,
441                xstrdup_for_dump (dst->name ()), dst->order);
442     }
443   dst->count += src->count;
444
445   /* This is ugly.  We need to get both function bodies into memory.
446      If declaration is merged, we need to duplicate it to be able
447      to load body that is being replaced.  This makes symbol table
448      temporarily inconsistent.  */
449   if (src->decl == dst->decl)
450     {
451       struct lto_in_decl_state temp;
452       struct lto_in_decl_state *state;
453
454       /* We are going to move the decl, we want to remove its file decl data.
455          and link these with the new decl. */
456       temp.fn_decl = src->decl;
457       lto_in_decl_state **slot
458         = src->lto_file_data->function_decl_states->find_slot (&temp,
459                                                                NO_INSERT);
460       state = *slot;
461       src->lto_file_data->function_decl_states->clear_slot (slot);
462       gcc_assert (state);
463
464       /* Duplicate the decl and be sure it does not link into body of DST.  */
465       src->decl = copy_node (src->decl);
466       DECL_STRUCT_FUNCTION (src->decl) = NULL;
467       DECL_ARGUMENTS (src->decl) = NULL;
468       DECL_INITIAL (src->decl) = NULL;
469       DECL_RESULT (src->decl) = NULL;
470
471       /* Associate the decl state with new declaration, so LTO streamer
472          can look it up.  */
473       state->fn_decl = src->decl;
474       slot
475         = src->lto_file_data->function_decl_states->find_slot (state, INSERT);
476       gcc_assert (!*slot);
477       *slot = state;
478     }
479   src->get_untransformed_body ();
480   dst->get_untransformed_body ();
481   srccfun = DECL_STRUCT_FUNCTION (src->decl);
482   dstcfun = DECL_STRUCT_FUNCTION (dst->decl);
483   if (n_basic_blocks_for_fn (srccfun)
484       != n_basic_blocks_for_fn (dstcfun))
485     {
486       if (symtab->dump_file)
487         fprintf (symtab->dump_file,
488                  "Giving up; number of basic block mismatch.\n");
489       match = false;
490     }
491   else if (last_basic_block_for_fn (srccfun)
492            != last_basic_block_for_fn (dstcfun))
493     {
494       if (symtab->dump_file)
495         fprintf (symtab->dump_file,
496                  "Giving up; last block mismatch.\n");
497       match = false;
498     }
499   else 
500     {
501       basic_block srcbb, dstbb;
502
503       FOR_ALL_BB_FN (srcbb, srccfun)
504         {
505           unsigned int i;
506
507           dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index);
508           if (dstbb == NULL)
509             {
510               if (symtab->dump_file)
511                 fprintf (symtab->dump_file,
512                          "No matching block for bb %i.\n",
513                          srcbb->index);
514               match = false;
515               break;
516             }
517           if (EDGE_COUNT (srcbb->succs) != EDGE_COUNT (dstbb->succs))
518             {
519               if (symtab->dump_file)
520                 fprintf (symtab->dump_file,
521                          "Edge count mistmatch for bb %i.\n",
522                          srcbb->index);
523               match = false;
524               break;
525             }
526           for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
527             {
528               edge srce = EDGE_SUCC (srcbb, i);
529               edge dste = EDGE_SUCC (dstbb, i);
530               if (srce->dest->index != dste->dest->index)
531                 {
532                   if (symtab->dump_file)
533                     fprintf (symtab->dump_file,
534                              "Succ edge mistmatch for bb %i.\n",
535                              srce->dest->index);
536                   match = false;
537                   break;
538                 }
539             }
540         }
541     }
542   if (match)
543     {
544       struct cgraph_edge *e, *e2;
545       basic_block srcbb, dstbb;
546
547       /* TODO: merge also statement histograms.  */
548       FOR_ALL_BB_FN (srcbb, srccfun)
549         {
550           unsigned int i;
551
552           dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index);
553           dstbb->count += srcbb->count;
554           for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
555             {
556               edge srce = EDGE_SUCC (srcbb, i);
557               edge dste = EDGE_SUCC (dstbb, i);
558               dste->count += srce->count;
559             }
560         }
561       push_cfun (dstcfun);
562       counts_to_freqs ();
563       compute_function_frequency ();
564       pop_cfun ();
565       for (e = dst->callees; e; e = e->next_callee)
566         {
567           if (e->speculative)
568             continue;
569           e->count = gimple_bb (e->call_stmt)->count;
570           e->frequency = compute_call_stmt_bb_frequency
571                              (dst->decl,
572                               gimple_bb (e->call_stmt));
573         }
574       for (e = dst->indirect_calls, e2 = src->indirect_calls; e;
575            e2 = (e2 ? e2->next_callee : NULL), e = e->next_callee)
576         {
577           gcov_type count = gimple_bb (e->call_stmt)->count;
578           int freq = compute_call_stmt_bb_frequency
579                         (dst->decl,
580                          gimple_bb (e->call_stmt));
581           /* When call is speculative, we need to re-distribute probabilities
582              the same way as they was.  This is not really correct because
583              in the other copy the speculation may differ; but probably it
584              is not really worth the effort.  */
585           if (e->speculative)
586             {
587               cgraph_edge *direct, *indirect;
588               cgraph_edge *direct2 = NULL, *indirect2 = NULL;
589               ipa_ref *ref;
590
591               e->speculative_call_info (direct, indirect, ref);
592               gcc_assert (e == indirect);
593               if (e2 && e2->speculative)
594                 e2->speculative_call_info (direct2, indirect2, ref);
595               if (indirect->count || direct->count)
596                 {
597                   /* We should mismatch earlier if there is no matching
598                      indirect edge.  */
599                   if (!e2)
600                     {
601                       if (dump_file)
602                         fprintf (dump_file,
603                                  "Mismatch in merging indirect edges\n");
604                     }
605                   else if (!e2->speculative)
606                     indirect->count += e2->count;
607                   else if (e2->speculative)
608                     {
609                       if (DECL_ASSEMBLER_NAME (direct2->callee->decl)
610                           != DECL_ASSEMBLER_NAME (direct->callee->decl))
611                         {
612                           if (direct2->count >= direct->count)
613                             {
614                               direct->redirect_callee (direct2->callee);
615                               indirect->count += indirect2->count
616                                                  + direct->count;
617                               direct->count = direct2->count;
618                             }
619                           else
620                             indirect->count += indirect2->count + direct2->count;
621                         }
622                       else
623                         {
624                            direct->count += direct2->count;
625                            indirect->count += indirect2->count;
626                         }
627                     }
628                   int  prob = RDIV (direct->count * REG_BR_PROB_BASE ,
629                                     direct->count + indirect->count);
630                   direct->frequency = RDIV (freq * prob, REG_BR_PROB_BASE);
631                   indirect->frequency = RDIV (freq * (REG_BR_PROB_BASE - prob),
632                                               REG_BR_PROB_BASE);
633                 }
634               else
635                 /* At the moment we should have only profile feedback based
636                    speculations when merging.  */
637                 gcc_unreachable ();
638             }
639           else if (e2 && e2->speculative)
640             {
641               cgraph_edge *direct, *indirect;
642               ipa_ref *ref;
643
644               e2->speculative_call_info (direct, indirect, ref);
645               e->count = count;
646               e->frequency = freq;
647               int prob = RDIV (direct->count * REG_BR_PROB_BASE, e->count);
648               e->make_speculative (direct->callee, direct->count,
649                                    RDIV (freq * prob, REG_BR_PROB_BASE));
650             }
651           else
652             {
653               e->count = count;
654               e->frequency = freq;
655             }
656         }
657       if (!preserve_body)
658         src->release_body ();
659       inline_update_overall_summary (dst);
660     }
661   /* TODO: if there is no match, we can scale up.  */
662   src->decl = oldsrcdecl;
663 }
664
665 /* Return true if call to DEST is known to be self-recusive call withing FUNC.   */
666
667 bool
668 recursive_call_p (tree func, tree dest)
669 {
670   struct cgraph_node *dest_node = cgraph_node::get_create (dest);
671   struct cgraph_node *cnode = cgraph_node::get_create (func);
672
673   return dest_node->semantically_equivalent_p (cnode);
674 }