1/* Utilities for ipa analysis.
2   Copyright (C) 2005-2015 Free Software Foundation, Inc.
3   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
73void
74ipa_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
89struct 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
110static void
111searchc (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
193int
194ipa_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
250void
251ipa_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
268vec<cgraph_node *>
269ipa_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
285bool
286ipa_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
298struct 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
309int
310ipa_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
393tree
394get_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
413void
414ipa_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
667bool
668recursive_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}
675