xref: /dflybsd-src/contrib/gcc-8.0/gcc/ipa-utils.c (revision 95059079af47f9a66a175f374f2da1a5020e3255)
138fd1498Szrj /* Utilities for ipa analysis.
238fd1498Szrj    Copyright (C) 2005-2018 Free Software Foundation, Inc.
338fd1498Szrj    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
438fd1498Szrj 
538fd1498Szrj This file is part of GCC.
638fd1498Szrj 
738fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
838fd1498Szrj the terms of the GNU General Public License as published by the Free
938fd1498Szrj Software Foundation; either version 3, or (at your option) any later
1038fd1498Szrj version.
1138fd1498Szrj 
1238fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1338fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
1438fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
1538fd1498Szrj for more details.
1638fd1498Szrj 
1738fd1498Szrj You should have received a copy of the GNU General Public License
1838fd1498Szrj along with GCC; see the file COPYING3.  If not see
1938fd1498Szrj <http://www.gnu.org/licenses/>.  */
2038fd1498Szrj 
2138fd1498Szrj #include "config.h"
2238fd1498Szrj #include "system.h"
2338fd1498Szrj #include "coretypes.h"
2438fd1498Szrj #include "backend.h"
2538fd1498Szrj #include "tree.h"
2638fd1498Szrj #include "gimple.h"
2738fd1498Szrj #include "predict.h"
2838fd1498Szrj #include "alloc-pool.h"
2938fd1498Szrj #include "cgraph.h"
3038fd1498Szrj #include "lto-streamer.h"
3138fd1498Szrj #include "dumpfile.h"
3238fd1498Szrj #include "splay-tree.h"
3338fd1498Szrj #include "ipa-utils.h"
3438fd1498Szrj #include "symbol-summary.h"
3538fd1498Szrj #include "tree-vrp.h"
3638fd1498Szrj #include "ipa-prop.h"
3738fd1498Szrj #include "ipa-fnsummary.h"
3838fd1498Szrj 
3938fd1498Szrj /* Debugging function for postorder and inorder code. NOTE is a string
4038fd1498Szrj    that is printed before the nodes are printed.  ORDER is an array of
4138fd1498Szrj    cgraph_nodes that has COUNT useful nodes in it.  */
4238fd1498Szrj 
4338fd1498Szrj void
ipa_print_order(FILE * out,const char * note,struct cgraph_node ** order,int count)4438fd1498Szrj ipa_print_order (FILE* out,
4538fd1498Szrj 		 const char * note,
4638fd1498Szrj 		 struct cgraph_node** order,
4738fd1498Szrj 		 int count)
4838fd1498Szrj {
4938fd1498Szrj   int i;
5038fd1498Szrj   fprintf (out, "\n\n ordered call graph: %s\n", note);
5138fd1498Szrj 
5238fd1498Szrj   for (i = count - 1; i >= 0; i--)
5338fd1498Szrj     order[i]->dump (out);
5438fd1498Szrj   fprintf (out, "\n");
5538fd1498Szrj   fflush (out);
5638fd1498Szrj }
5738fd1498Szrj 
5838fd1498Szrj 
5938fd1498Szrj struct searchc_env {
6038fd1498Szrj   struct cgraph_node **stack;
6138fd1498Szrj   struct cgraph_node **result;
6238fd1498Szrj   int stack_size;
6338fd1498Szrj   int order_pos;
6438fd1498Szrj   splay_tree nodes_marked_new;
6538fd1498Szrj   bool reduce;
6638fd1498Szrj   int count;
6738fd1498Szrj };
6838fd1498Szrj 
6938fd1498Szrj /* This is an implementation of Tarjan's strongly connected region
7038fd1498Szrj    finder as reprinted in Aho Hopcraft and Ullman's The Design and
7138fd1498Szrj    Analysis of Computer Programs (1975) pages 192-193.  This version
7238fd1498Szrj    has been customized for cgraph_nodes.  The env parameter is because
7338fd1498Szrj    it is recursive and there are no nested functions here.  This
7438fd1498Szrj    function should only be called from itself or
7538fd1498Szrj    ipa_reduced_postorder.  ENV is a stack env and would be
7638fd1498Szrj    unnecessary if C had nested functions.  V is the node to start
7738fd1498Szrj    searching from.  */
7838fd1498Szrj 
7938fd1498Szrj static void
searchc(struct searchc_env * env,struct cgraph_node * v,bool (* ignore_edge)(struct cgraph_edge *))8038fd1498Szrj searchc (struct searchc_env* env, struct cgraph_node *v,
8138fd1498Szrj 	 bool (*ignore_edge) (struct cgraph_edge *))
8238fd1498Szrj {
8338fd1498Szrj   struct cgraph_edge *edge;
8438fd1498Szrj   struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
8538fd1498Szrj 
8638fd1498Szrj   /* mark node as old */
8738fd1498Szrj   v_info->new_node = false;
8838fd1498Szrj   splay_tree_remove (env->nodes_marked_new, v->uid);
8938fd1498Szrj 
9038fd1498Szrj   v_info->dfn_number = env->count;
9138fd1498Szrj   v_info->low_link = env->count;
9238fd1498Szrj   env->count++;
9338fd1498Szrj   env->stack[(env->stack_size)++] = v;
9438fd1498Szrj   v_info->on_stack = true;
9538fd1498Szrj 
9638fd1498Szrj   for (edge = v->callees; edge; edge = edge->next_callee)
9738fd1498Szrj     {
9838fd1498Szrj       struct ipa_dfs_info * w_info;
9938fd1498Szrj       enum availability avail;
10038fd1498Szrj       struct cgraph_node *w = edge->callee->ultimate_alias_target (&avail);
10138fd1498Szrj 
10238fd1498Szrj       if (!w || (ignore_edge && ignore_edge (edge)))
10338fd1498Szrj         continue;
10438fd1498Szrj 
10538fd1498Szrj       if (w->aux
10638fd1498Szrj 	  && (avail > AVAIL_INTERPOSABLE
107*58e805e6Szrj 	      || avail == AVAIL_INTERPOSABLE))
10838fd1498Szrj 	{
10938fd1498Szrj 	  w_info = (struct ipa_dfs_info *) w->aux;
11038fd1498Szrj 	  if (w_info->new_node)
11138fd1498Szrj 	    {
11238fd1498Szrj 	      searchc (env, w, ignore_edge);
11338fd1498Szrj 	      v_info->low_link =
11438fd1498Szrj 		(v_info->low_link < w_info->low_link) ?
11538fd1498Szrj 		v_info->low_link : w_info->low_link;
11638fd1498Szrj 	    }
11738fd1498Szrj 	  else
11838fd1498Szrj 	    if ((w_info->dfn_number < v_info->dfn_number)
11938fd1498Szrj 		&& (w_info->on_stack))
12038fd1498Szrj 	      v_info->low_link =
12138fd1498Szrj 		(w_info->dfn_number < v_info->low_link) ?
12238fd1498Szrj 		w_info->dfn_number : v_info->low_link;
12338fd1498Szrj 	}
12438fd1498Szrj     }
12538fd1498Szrj 
12638fd1498Szrj 
12738fd1498Szrj   if (v_info->low_link == v_info->dfn_number)
12838fd1498Szrj     {
12938fd1498Szrj       struct cgraph_node *last = NULL;
13038fd1498Szrj       struct cgraph_node *x;
13138fd1498Szrj       struct ipa_dfs_info *x_info;
13238fd1498Szrj       do {
13338fd1498Szrj 	x = env->stack[--(env->stack_size)];
13438fd1498Szrj 	x_info = (struct ipa_dfs_info *) x->aux;
13538fd1498Szrj 	x_info->on_stack = false;
13638fd1498Szrj 	x_info->scc_no = v_info->dfn_number;
13738fd1498Szrj 
13838fd1498Szrj 	if (env->reduce)
13938fd1498Szrj 	  {
14038fd1498Szrj 	    x_info->next_cycle = last;
14138fd1498Szrj 	    last = x;
14238fd1498Szrj 	  }
14338fd1498Szrj 	else
14438fd1498Szrj 	  env->result[env->order_pos++] = x;
14538fd1498Szrj       }
14638fd1498Szrj       while (v != x);
14738fd1498Szrj       if (env->reduce)
14838fd1498Szrj 	env->result[env->order_pos++] = v;
14938fd1498Szrj     }
15038fd1498Szrj }
15138fd1498Szrj 
15238fd1498Szrj /* Topsort the call graph by caller relation.  Put the result in ORDER.
15338fd1498Szrj 
15438fd1498Szrj    The REDUCE flag is true if you want the cycles reduced to single nodes.
15538fd1498Szrj    You can use ipa_get_nodes_in_cycle to obtain a vector containing all real
15638fd1498Szrj    call graph nodes in a reduced node.
15738fd1498Szrj 
15838fd1498Szrj    Set ALLOW_OVERWRITABLE if nodes with such availability should be included.
15938fd1498Szrj    IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
16038fd1498Szrj    for the topological sort.   */
16138fd1498Szrj 
16238fd1498Szrj int
ipa_reduced_postorder(struct cgraph_node ** order,bool reduce,bool (* ignore_edge)(struct cgraph_edge *))16338fd1498Szrj ipa_reduced_postorder (struct cgraph_node **order,
164*58e805e6Szrj 		       bool reduce,
16538fd1498Szrj 		       bool (*ignore_edge) (struct cgraph_edge *))
16638fd1498Szrj {
16738fd1498Szrj   struct cgraph_node *node;
16838fd1498Szrj   struct searchc_env env;
16938fd1498Szrj   splay_tree_node result;
17038fd1498Szrj   env.stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
17138fd1498Szrj   env.stack_size = 0;
17238fd1498Szrj   env.result = order;
17338fd1498Szrj   env.order_pos = 0;
17438fd1498Szrj   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
17538fd1498Szrj   env.count = 1;
17638fd1498Szrj   env.reduce = reduce;
17738fd1498Szrj 
17838fd1498Szrj   FOR_EACH_DEFINED_FUNCTION (node)
17938fd1498Szrj     {
18038fd1498Szrj       enum availability avail = node->get_availability ();
18138fd1498Szrj 
18238fd1498Szrj       if (avail > AVAIL_INTERPOSABLE
183*58e805e6Szrj 	  || avail == AVAIL_INTERPOSABLE)
18438fd1498Szrj 	{
18538fd1498Szrj 	  /* Reuse the info if it is already there.  */
18638fd1498Szrj 	  struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
18738fd1498Szrj 	  if (!info)
18838fd1498Szrj 	    info = XCNEW (struct ipa_dfs_info);
18938fd1498Szrj 	  info->new_node = true;
19038fd1498Szrj 	  info->on_stack = false;
19138fd1498Szrj 	  info->next_cycle = NULL;
19238fd1498Szrj 	  node->aux = info;
19338fd1498Szrj 
19438fd1498Szrj 	  splay_tree_insert (env.nodes_marked_new,
19538fd1498Szrj 			     (splay_tree_key)node->uid,
19638fd1498Szrj 			     (splay_tree_value)node);
19738fd1498Szrj 	}
19838fd1498Szrj       else
19938fd1498Szrj 	node->aux = NULL;
20038fd1498Szrj     }
20138fd1498Szrj   result = splay_tree_min (env.nodes_marked_new);
20238fd1498Szrj   while (result)
20338fd1498Szrj     {
20438fd1498Szrj       node = (struct cgraph_node *)result->value;
20538fd1498Szrj       searchc (&env, node, ignore_edge);
20638fd1498Szrj       result = splay_tree_min (env.nodes_marked_new);
20738fd1498Szrj     }
20838fd1498Szrj   splay_tree_delete (env.nodes_marked_new);
20938fd1498Szrj   free (env.stack);
21038fd1498Szrj 
21138fd1498Szrj   return env.order_pos;
21238fd1498Szrj }
21338fd1498Szrj 
21438fd1498Szrj /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
21538fd1498Szrj    graph nodes.  */
21638fd1498Szrj 
21738fd1498Szrj void
ipa_free_postorder_info(void)21838fd1498Szrj ipa_free_postorder_info (void)
21938fd1498Szrj {
22038fd1498Szrj   struct cgraph_node *node;
22138fd1498Szrj   FOR_EACH_DEFINED_FUNCTION (node)
22238fd1498Szrj     {
22338fd1498Szrj       /* Get rid of the aux information.  */
22438fd1498Szrj       if (node->aux)
22538fd1498Szrj 	{
22638fd1498Szrj 	  free (node->aux);
22738fd1498Szrj 	  node->aux = NULL;
22838fd1498Szrj 	}
22938fd1498Szrj     }
23038fd1498Szrj }
23138fd1498Szrj 
23238fd1498Szrj /* Get the set of nodes for the cycle in the reduced call graph starting
23338fd1498Szrj    from NODE.  */
23438fd1498Szrj 
23538fd1498Szrj vec<cgraph_node *>
ipa_get_nodes_in_cycle(struct cgraph_node * node)23638fd1498Szrj ipa_get_nodes_in_cycle (struct cgraph_node *node)
23738fd1498Szrj {
23838fd1498Szrj   vec<cgraph_node *> v = vNULL;
23938fd1498Szrj   struct ipa_dfs_info *node_dfs_info;
24038fd1498Szrj   while (node)
24138fd1498Szrj     {
24238fd1498Szrj       v.safe_push (node);
24338fd1498Szrj       node_dfs_info = (struct ipa_dfs_info *) node->aux;
24438fd1498Szrj       node = node_dfs_info->next_cycle;
24538fd1498Szrj     }
24638fd1498Szrj   return v;
24738fd1498Szrj }
24838fd1498Szrj 
24938fd1498Szrj /* Return true iff the CS is an edge within a strongly connected component as
25038fd1498Szrj    computed by ipa_reduced_postorder.  */
25138fd1498Szrj 
25238fd1498Szrj bool
ipa_edge_within_scc(struct cgraph_edge * cs)25338fd1498Szrj ipa_edge_within_scc (struct cgraph_edge *cs)
25438fd1498Szrj {
25538fd1498Szrj   struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux;
25638fd1498Szrj   struct ipa_dfs_info *callee_dfs;
25738fd1498Szrj   struct cgraph_node *callee = cs->callee->function_symbol ();
25838fd1498Szrj 
25938fd1498Szrj   callee_dfs = (struct ipa_dfs_info *) callee->aux;
26038fd1498Szrj   return (caller_dfs
26138fd1498Szrj 	  && callee_dfs
26238fd1498Szrj 	  && caller_dfs->scc_no == callee_dfs->scc_no);
26338fd1498Szrj }
26438fd1498Szrj 
26538fd1498Szrj struct postorder_stack
26638fd1498Szrj {
26738fd1498Szrj   struct cgraph_node *node;
26838fd1498Szrj   struct cgraph_edge *edge;
26938fd1498Szrj   int ref;
27038fd1498Szrj };
27138fd1498Szrj 
27238fd1498Szrj /* Fill array order with all nodes with output flag set in the reverse
27338fd1498Szrj    topological order.  Return the number of elements in the array.
27438fd1498Szrj    FIXME: While walking, consider aliases, too.  */
27538fd1498Szrj 
27638fd1498Szrj int
ipa_reverse_postorder(struct cgraph_node ** order)27738fd1498Szrj ipa_reverse_postorder (struct cgraph_node **order)
27838fd1498Szrj {
27938fd1498Szrj   struct cgraph_node *node, *node2;
28038fd1498Szrj   int stack_size = 0;
28138fd1498Szrj   int order_pos = 0;
28238fd1498Szrj   struct cgraph_edge *edge;
28338fd1498Szrj   int pass;
28438fd1498Szrj   struct ipa_ref *ref = NULL;
28538fd1498Szrj 
28638fd1498Szrj   struct postorder_stack *stack =
28738fd1498Szrj     XCNEWVEC (struct postorder_stack, symtab->cgraph_count);
28838fd1498Szrj 
28938fd1498Szrj   /* We have to deal with cycles nicely, so use a depth first traversal
29038fd1498Szrj      output algorithm.  Ignore the fact that some functions won't need
29138fd1498Szrj      to be output and put them into order as well, so we get dependencies
29238fd1498Szrj      right through inline functions.  */
29338fd1498Szrj   FOR_EACH_FUNCTION (node)
29438fd1498Szrj     node->aux = NULL;
29538fd1498Szrj   for (pass = 0; pass < 2; pass++)
29638fd1498Szrj     FOR_EACH_FUNCTION (node)
29738fd1498Szrj       if (!node->aux
29838fd1498Szrj 	  && (pass
29938fd1498Szrj 	      || (!node->address_taken
30038fd1498Szrj 		  && !node->global.inlined_to
30138fd1498Szrj 		  && !node->alias && !node->thunk.thunk_p
30238fd1498Szrj 		  && !node->only_called_directly_p ())))
30338fd1498Szrj 	{
30438fd1498Szrj 	  stack_size = 0;
30538fd1498Szrj           stack[stack_size].node = node;
30638fd1498Szrj 	  stack[stack_size].edge = node->callers;
30738fd1498Szrj 	  stack[stack_size].ref = 0;
30838fd1498Szrj 	  node->aux = (void *)(size_t)1;
30938fd1498Szrj 	  while (stack_size >= 0)
31038fd1498Szrj 	    {
31138fd1498Szrj 	      while (true)
31238fd1498Szrj 		{
31338fd1498Szrj 		  node2 = NULL;
31438fd1498Szrj 		  while (stack[stack_size].edge && !node2)
31538fd1498Szrj 		    {
31638fd1498Szrj 		      edge = stack[stack_size].edge;
31738fd1498Szrj 		      node2 = edge->caller;
31838fd1498Szrj 		      stack[stack_size].edge = edge->next_caller;
31938fd1498Szrj 		      /* Break possible cycles involving always-inline
32038fd1498Szrj 			 functions by ignoring edges from always-inline
32138fd1498Szrj 			 functions to non-always-inline functions.  */
32238fd1498Szrj 		      if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
32338fd1498Szrj 			  && !DECL_DISREGARD_INLINE_LIMITS
32438fd1498Szrj 			    (edge->callee->function_symbol ()->decl))
32538fd1498Szrj 			node2 = NULL;
32638fd1498Szrj 		    }
32738fd1498Szrj 		  for (; stack[stack_size].node->iterate_referring (
32838fd1498Szrj 						       stack[stack_size].ref,
32938fd1498Szrj 						       ref) && !node2;
33038fd1498Szrj 		       stack[stack_size].ref++)
33138fd1498Szrj 		    {
33238fd1498Szrj 		      if (ref->use == IPA_REF_ALIAS)
33338fd1498Szrj 			node2 = dyn_cast <cgraph_node *> (ref->referring);
33438fd1498Szrj 		    }
33538fd1498Szrj 		  if (!node2)
33638fd1498Szrj 		    break;
33738fd1498Szrj 		  if (!node2->aux)
33838fd1498Szrj 		    {
33938fd1498Szrj 		      stack[++stack_size].node = node2;
34038fd1498Szrj 		      stack[stack_size].edge = node2->callers;
34138fd1498Szrj 		      stack[stack_size].ref = 0;
34238fd1498Szrj 		      node2->aux = (void *)(size_t)1;
34338fd1498Szrj 		    }
34438fd1498Szrj 		}
34538fd1498Szrj 	      order[order_pos++] = stack[stack_size--].node;
34638fd1498Szrj 	    }
34738fd1498Szrj 	}
34838fd1498Szrj   free (stack);
34938fd1498Szrj   FOR_EACH_FUNCTION (node)
35038fd1498Szrj     node->aux = NULL;
35138fd1498Szrj   return order_pos;
35238fd1498Szrj }
35338fd1498Szrj 
35438fd1498Szrj 
35538fd1498Szrj 
35638fd1498Szrj /* Given a memory reference T, will return the variable at the bottom
35738fd1498Szrj    of the access.  Unlike get_base_address, this will recurse through
35838fd1498Szrj    INDIRECT_REFS.  */
35938fd1498Szrj 
36038fd1498Szrj tree
get_base_var(tree t)36138fd1498Szrj get_base_var (tree t)
36238fd1498Szrj {
36338fd1498Szrj   while (!SSA_VAR_P (t)
36438fd1498Szrj 	 && (!CONSTANT_CLASS_P (t))
36538fd1498Szrj 	 && TREE_CODE (t) != LABEL_DECL
36638fd1498Szrj 	 && TREE_CODE (t) != FUNCTION_DECL
36738fd1498Szrj 	 && TREE_CODE (t) != CONST_DECL
36838fd1498Szrj 	 && TREE_CODE (t) != CONSTRUCTOR)
36938fd1498Szrj     {
37038fd1498Szrj       t = TREE_OPERAND (t, 0);
37138fd1498Szrj     }
37238fd1498Szrj   return t;
37338fd1498Szrj }
37438fd1498Szrj 
375*58e805e6Szrj /* Scale function of calls in NODE by ratio ORIG_COUNT/NODE->count.  */
376*58e805e6Szrj 
377*58e805e6Szrj void
scale_ipa_profile_for_fn(struct cgraph_node * node,profile_count orig_count)378*58e805e6Szrj scale_ipa_profile_for_fn (struct cgraph_node *node, profile_count orig_count)
379*58e805e6Szrj {
380*58e805e6Szrj   profile_count to = node->count;
381*58e805e6Szrj   profile_count::adjust_for_ipa_scaling (&to, &orig_count);
382*58e805e6Szrj   struct cgraph_edge *e;
383*58e805e6Szrj 
384*58e805e6Szrj   for (e = node->callees; e; e = e->next_callee)
385*58e805e6Szrj     e->count = e->count.apply_scale (to, orig_count);
386*58e805e6Szrj   for (e = node->indirect_calls; e; e = e->next_callee)
387*58e805e6Szrj     e->count = e->count.apply_scale (to, orig_count);
388*58e805e6Szrj }
38938fd1498Szrj 
39038fd1498Szrj /* SRC and DST are going to be merged.  Take SRC's profile and merge it into
39138fd1498Szrj    DST so it is not going to be lost.  Possibly destroy SRC's body on the way
39238fd1498Szrj    unless PRESERVE_BODY is set.  */
39338fd1498Szrj 
39438fd1498Szrj void
ipa_merge_profiles(struct cgraph_node * dst,struct cgraph_node * src,bool preserve_body)39538fd1498Szrj ipa_merge_profiles (struct cgraph_node *dst,
39638fd1498Szrj 		    struct cgraph_node *src,
39738fd1498Szrj 		    bool preserve_body)
39838fd1498Szrj {
39938fd1498Szrj   tree oldsrcdecl = src->decl;
40038fd1498Szrj   struct function *srccfun, *dstcfun;
40138fd1498Szrj   bool match = true;
40238fd1498Szrj 
40338fd1498Szrj   if (!src->definition
40438fd1498Szrj       || !dst->definition)
40538fd1498Szrj     return;
406*58e805e6Szrj 
40738fd1498Szrj   if (src->frequency < dst->frequency)
40838fd1498Szrj     src->frequency = dst->frequency;
40938fd1498Szrj 
41038fd1498Szrj   /* Time profiles are merged.  */
41138fd1498Szrj   if (dst->tp_first_run > src->tp_first_run && src->tp_first_run)
41238fd1498Szrj     dst->tp_first_run = src->tp_first_run;
41338fd1498Szrj 
41438fd1498Szrj   if (src->profile_id && !dst->profile_id)
41538fd1498Szrj     dst->profile_id = src->profile_id;
41638fd1498Szrj 
417*58e805e6Szrj   /* Merging zero profile to dst is no-op.  */
418*58e805e6Szrj   if (src->count.ipa () == profile_count::zero ())
419*58e805e6Szrj     return;
420*58e805e6Szrj 
42138fd1498Szrj   /* FIXME when we merge in unknown profile, we ought to set counts as
42238fd1498Szrj      unsafe.  */
42338fd1498Szrj   if (!src->count.initialized_p ()
42438fd1498Szrj       || !(src->count.ipa () == src->count))
42538fd1498Szrj     return;
42638fd1498Szrj   if (symtab->dump_file)
42738fd1498Szrj     {
42838fd1498Szrj       fprintf (symtab->dump_file, "Merging profiles of %s to %s\n",
42938fd1498Szrj 	       src->dump_name (), dst->dump_name ());
43038fd1498Szrj     }
431*58e805e6Szrj   profile_count orig_count = dst->count;
432*58e805e6Szrj 
43338fd1498Szrj   if (dst->count.initialized_p () && dst->count.ipa () == dst->count)
43438fd1498Szrj     dst->count += src->count.ipa ();
43538fd1498Szrj   else
43638fd1498Szrj     dst->count = src->count.ipa ();
43738fd1498Szrj 
438*58e805e6Szrj   /* First handle functions with no gimple body.  */
439*58e805e6Szrj   if (dst->thunk.thunk_p || dst->alias
440*58e805e6Szrj       || src->thunk.thunk_p || src->alias)
441*58e805e6Szrj     {
442*58e805e6Szrj       scale_ipa_profile_for_fn (dst, orig_count);
443*58e805e6Szrj       return;
444*58e805e6Szrj     }
445*58e805e6Szrj 
44638fd1498Szrj   /* This is ugly.  We need to get both function bodies into memory.
44738fd1498Szrj      If declaration is merged, we need to duplicate it to be able
44838fd1498Szrj      to load body that is being replaced.  This makes symbol table
44938fd1498Szrj      temporarily inconsistent.  */
45038fd1498Szrj   if (src->decl == dst->decl)
45138fd1498Szrj     {
45238fd1498Szrj       struct lto_in_decl_state temp;
45338fd1498Szrj       struct lto_in_decl_state *state;
45438fd1498Szrj 
45538fd1498Szrj       /* We are going to move the decl, we want to remove its file decl data.
45638fd1498Szrj 	 and link these with the new decl. */
45738fd1498Szrj       temp.fn_decl = src->decl;
45838fd1498Szrj       lto_in_decl_state **slot
45938fd1498Szrj 	= src->lto_file_data->function_decl_states->find_slot (&temp,
46038fd1498Szrj 							       NO_INSERT);
46138fd1498Szrj       state = *slot;
46238fd1498Szrj       src->lto_file_data->function_decl_states->clear_slot (slot);
46338fd1498Szrj       gcc_assert (state);
46438fd1498Szrj 
46538fd1498Szrj       /* Duplicate the decl and be sure it does not link into body of DST.  */
46638fd1498Szrj       src->decl = copy_node (src->decl);
46738fd1498Szrj       DECL_STRUCT_FUNCTION (src->decl) = NULL;
46838fd1498Szrj       DECL_ARGUMENTS (src->decl) = NULL;
46938fd1498Szrj       DECL_INITIAL (src->decl) = NULL;
47038fd1498Szrj       DECL_RESULT (src->decl) = NULL;
47138fd1498Szrj 
47238fd1498Szrj       /* Associate the decl state with new declaration, so LTO streamer
47338fd1498Szrj  	 can look it up.  */
47438fd1498Szrj       state->fn_decl = src->decl;
47538fd1498Szrj       slot
47638fd1498Szrj 	= src->lto_file_data->function_decl_states->find_slot (state, INSERT);
47738fd1498Szrj       gcc_assert (!*slot);
47838fd1498Szrj       *slot = state;
47938fd1498Szrj     }
48038fd1498Szrj   src->get_untransformed_body ();
48138fd1498Szrj   dst->get_untransformed_body ();
48238fd1498Szrj   srccfun = DECL_STRUCT_FUNCTION (src->decl);
48338fd1498Szrj   dstcfun = DECL_STRUCT_FUNCTION (dst->decl);
48438fd1498Szrj   if (n_basic_blocks_for_fn (srccfun)
48538fd1498Szrj       != n_basic_blocks_for_fn (dstcfun))
48638fd1498Szrj     {
48738fd1498Szrj       if (symtab->dump_file)
48838fd1498Szrj 	fprintf (symtab->dump_file,
48938fd1498Szrj 		 "Giving up; number of basic block mismatch.\n");
49038fd1498Szrj       match = false;
49138fd1498Szrj     }
49238fd1498Szrj   else if (last_basic_block_for_fn (srccfun)
49338fd1498Szrj 	   != last_basic_block_for_fn (dstcfun))
49438fd1498Szrj     {
49538fd1498Szrj       if (symtab->dump_file)
49638fd1498Szrj 	fprintf (symtab->dump_file,
49738fd1498Szrj 		 "Giving up; last block mismatch.\n");
49838fd1498Szrj       match = false;
49938fd1498Szrj     }
50038fd1498Szrj   else
50138fd1498Szrj     {
50238fd1498Szrj       basic_block srcbb, dstbb;
50338fd1498Szrj 
50438fd1498Szrj       FOR_ALL_BB_FN (srcbb, srccfun)
50538fd1498Szrj 	{
50638fd1498Szrj 	  unsigned int i;
50738fd1498Szrj 
50838fd1498Szrj 	  dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index);
50938fd1498Szrj 	  if (dstbb == NULL)
51038fd1498Szrj 	    {
51138fd1498Szrj 	      if (symtab->dump_file)
51238fd1498Szrj 		fprintf (symtab->dump_file,
51338fd1498Szrj 			 "No matching block for bb %i.\n",
51438fd1498Szrj 			 srcbb->index);
51538fd1498Szrj 	      match = false;
51638fd1498Szrj 	      break;
51738fd1498Szrj 	    }
51838fd1498Szrj 	  if (EDGE_COUNT (srcbb->succs) != EDGE_COUNT (dstbb->succs))
51938fd1498Szrj 	    {
52038fd1498Szrj 	      if (symtab->dump_file)
52138fd1498Szrj 		fprintf (symtab->dump_file,
52238fd1498Szrj 			 "Edge count mistmatch for bb %i.\n",
52338fd1498Szrj 			 srcbb->index);
52438fd1498Szrj 	      match = false;
52538fd1498Szrj 	      break;
52638fd1498Szrj 	    }
52738fd1498Szrj 	  for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
52838fd1498Szrj 	    {
52938fd1498Szrj 	      edge srce = EDGE_SUCC (srcbb, i);
53038fd1498Szrj 	      edge dste = EDGE_SUCC (dstbb, i);
53138fd1498Szrj 	      if (srce->dest->index != dste->dest->index)
53238fd1498Szrj 		{
53338fd1498Szrj 		  if (symtab->dump_file)
53438fd1498Szrj 		    fprintf (symtab->dump_file,
53538fd1498Szrj 			     "Succ edge mistmatch for bb %i.\n",
53638fd1498Szrj 			     srce->dest->index);
53738fd1498Szrj 		  match = false;
53838fd1498Szrj 		  break;
53938fd1498Szrj 		}
54038fd1498Szrj 	    }
54138fd1498Szrj 	}
54238fd1498Szrj     }
54338fd1498Szrj   if (match)
54438fd1498Szrj     {
54538fd1498Szrj       struct cgraph_edge *e, *e2;
54638fd1498Szrj       basic_block srcbb, dstbb;
54738fd1498Szrj 
54838fd1498Szrj       /* TODO: merge also statement histograms.  */
54938fd1498Szrj       FOR_ALL_BB_FN (srcbb, srccfun)
55038fd1498Szrj 	{
55138fd1498Szrj 	  unsigned int i;
55238fd1498Szrj 
55338fd1498Szrj 	  dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index);
55438fd1498Szrj 
55538fd1498Szrj 	  /* Either sum the profiles if both are IPA and not global0, or
55638fd1498Szrj 	     pick more informative one (that is nonzero IPA if other is
55738fd1498Szrj 	     uninitialized, guessed or global0).   */
55838fd1498Szrj 	  if (!dstbb->count.ipa ().initialized_p ()
55938fd1498Szrj 	      || (dstbb->count.ipa () == profile_count::zero ()
56038fd1498Szrj 		  && (srcbb->count.ipa ().initialized_p ()
56138fd1498Szrj 		      && !(srcbb->count.ipa () == profile_count::zero ()))))
56238fd1498Szrj 	    {
56338fd1498Szrj 	      dstbb->count = srcbb->count;
56438fd1498Szrj 	      for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
56538fd1498Szrj 		{
56638fd1498Szrj 		  edge srce = EDGE_SUCC (srcbb, i);
56738fd1498Szrj 		  edge dste = EDGE_SUCC (dstbb, i);
56838fd1498Szrj 		  if (srce->probability.initialized_p ())
56938fd1498Szrj 		    dste->probability = srce->probability;
57038fd1498Szrj 		}
57138fd1498Szrj 	    }
57238fd1498Szrj 	  else if (srcbb->count.ipa ().initialized_p ()
57338fd1498Szrj 		   && !(srcbb->count.ipa () == profile_count::zero ()))
57438fd1498Szrj 	    {
57538fd1498Szrj 	      for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
57638fd1498Szrj 		{
57738fd1498Szrj 		  edge srce = EDGE_SUCC (srcbb, i);
57838fd1498Szrj 		  edge dste = EDGE_SUCC (dstbb, i);
57938fd1498Szrj 		  dste->probability =
58038fd1498Szrj 		    dste->probability * dstbb->count.probability_in (dstbb->count + srcbb->count)
58138fd1498Szrj 		    + srce->probability * srcbb->count.probability_in (dstbb->count + srcbb->count);
58238fd1498Szrj 		}
58338fd1498Szrj 	      dstbb->count += srcbb->count;
58438fd1498Szrj 	    }
58538fd1498Szrj 	}
58638fd1498Szrj       push_cfun (dstcfun);
58738fd1498Szrj       update_max_bb_count ();
58838fd1498Szrj       compute_function_frequency ();
58938fd1498Szrj       pop_cfun ();
59038fd1498Szrj       for (e = dst->callees; e; e = e->next_callee)
59138fd1498Szrj 	{
59238fd1498Szrj 	  if (e->speculative)
59338fd1498Szrj 	    continue;
59438fd1498Szrj 	  e->count = gimple_bb (e->call_stmt)->count;
59538fd1498Szrj 	}
59638fd1498Szrj       for (e = dst->indirect_calls, e2 = src->indirect_calls; e;
59738fd1498Szrj 	   e2 = (e2 ? e2->next_callee : NULL), e = e->next_callee)
59838fd1498Szrj 	{
59938fd1498Szrj 	  profile_count count = gimple_bb (e->call_stmt)->count;
60038fd1498Szrj 	  /* When call is speculative, we need to re-distribute probabilities
60138fd1498Szrj 	     the same way as they was.  This is not really correct because
60238fd1498Szrj 	     in the other copy the speculation may differ; but probably it
60338fd1498Szrj 	     is not really worth the effort.  */
60438fd1498Szrj 	  if (e->speculative)
60538fd1498Szrj 	    {
60638fd1498Szrj 	      cgraph_edge *direct, *indirect;
60738fd1498Szrj 	      cgraph_edge *direct2 = NULL, *indirect2 = NULL;
60838fd1498Szrj 	      ipa_ref *ref;
60938fd1498Szrj 
61038fd1498Szrj 	      e->speculative_call_info (direct, indirect, ref);
61138fd1498Szrj 	      gcc_assert (e == indirect);
61238fd1498Szrj 	      if (e2 && e2->speculative)
61338fd1498Szrj 	        e2->speculative_call_info (direct2, indirect2, ref);
61438fd1498Szrj 	      if (indirect->count > profile_count::zero ()
61538fd1498Szrj 		  || direct->count > profile_count::zero ())
61638fd1498Szrj 		{
61738fd1498Szrj 		  /* We should mismatch earlier if there is no matching
61838fd1498Szrj 		     indirect edge.  */
61938fd1498Szrj 		  if (!e2)
62038fd1498Szrj 		    {
62138fd1498Szrj 		      if (dump_file)
62238fd1498Szrj 		        fprintf (dump_file,
62338fd1498Szrj 				 "Mismatch in merging indirect edges\n");
62438fd1498Szrj 		    }
62538fd1498Szrj 		  else if (!e2->speculative)
62638fd1498Szrj 		    indirect->count += e2->count;
62738fd1498Szrj 		  else if (e2->speculative)
62838fd1498Szrj 		    {
62938fd1498Szrj 		      if (DECL_ASSEMBLER_NAME (direct2->callee->decl)
63038fd1498Szrj 			  != DECL_ASSEMBLER_NAME (direct->callee->decl))
63138fd1498Szrj 			{
63238fd1498Szrj 			  if (direct2->count >= direct->count)
63338fd1498Szrj 			    {
63438fd1498Szrj 			      direct->redirect_callee (direct2->callee);
63538fd1498Szrj 			      indirect->count += indirect2->count
63638fd1498Szrj 						 + direct->count;
63738fd1498Szrj 			      direct->count = direct2->count;
63838fd1498Szrj 			    }
63938fd1498Szrj 			  else
64038fd1498Szrj 			    indirect->count += indirect2->count + direct2->count;
64138fd1498Szrj 			}
64238fd1498Szrj 		      else
64338fd1498Szrj 			{
64438fd1498Szrj 			   direct->count += direct2->count;
64538fd1498Szrj 			   indirect->count += indirect2->count;
64638fd1498Szrj 			}
64738fd1498Szrj 		    }
64838fd1498Szrj 		}
64938fd1498Szrj 	      else
65038fd1498Szrj 		/* At the moment we should have only profile feedback based
65138fd1498Szrj 		   speculations when merging.  */
65238fd1498Szrj 		gcc_unreachable ();
65338fd1498Szrj 	    }
65438fd1498Szrj 	  else if (e2 && e2->speculative)
65538fd1498Szrj 	    {
65638fd1498Szrj 	      cgraph_edge *direct, *indirect;
65738fd1498Szrj 	      ipa_ref *ref;
65838fd1498Szrj 
65938fd1498Szrj 	      e2->speculative_call_info (direct, indirect, ref);
66038fd1498Szrj 	      e->count = count;
66138fd1498Szrj 	      e->make_speculative (direct->callee, direct->count);
66238fd1498Szrj 	    }
66338fd1498Szrj 	  else
66438fd1498Szrj 	    e->count = count;
66538fd1498Szrj 	}
66638fd1498Szrj       if (!preserve_body)
66738fd1498Szrj         src->release_body ();
66838fd1498Szrj       ipa_update_overall_fn_summary (dst);
66938fd1498Szrj     }
670*58e805e6Szrj   /* We can't update CFG profile, but we can scale IPA profile. CFG
671*58e805e6Szrj      will be scaled according to dst->count after IPA passes.  */
672*58e805e6Szrj   else
673*58e805e6Szrj     scale_ipa_profile_for_fn (dst, orig_count);
67438fd1498Szrj   src->decl = oldsrcdecl;
67538fd1498Szrj }
67638fd1498Szrj 
67738fd1498Szrj /* Return true if call to DEST is known to be self-recusive call withing FUNC.   */
67838fd1498Szrj 
67938fd1498Szrj bool
recursive_call_p(tree func,tree dest)68038fd1498Szrj recursive_call_p (tree func, tree dest)
68138fd1498Szrj {
68238fd1498Szrj   struct cgraph_node *dest_node = cgraph_node::get_create (dest);
68338fd1498Szrj   struct cgraph_node *cnode = cgraph_node::get_create (func);
68438fd1498Szrj   ipa_ref *alias;
68538fd1498Szrj   enum availability avail;
68638fd1498Szrj 
68738fd1498Szrj   gcc_assert (!cnode->alias);
68838fd1498Szrj   if (cnode != dest_node->ultimate_alias_target (&avail))
68938fd1498Szrj     return false;
69038fd1498Szrj   if (avail >= AVAIL_AVAILABLE)
69138fd1498Szrj     return true;
69238fd1498Szrj   if (!dest_node->semantically_equivalent_p (cnode))
69338fd1498Szrj     return false;
69438fd1498Szrj   /* If there is only one way to call the fuction or we know all of them
69538fd1498Szrj      are semantically equivalent, we still can consider call recursive.  */
69638fd1498Szrj   FOR_EACH_ALIAS (cnode, alias)
69738fd1498Szrj     if (!dest_node->semantically_equivalent_p (alias->referring))
69838fd1498Szrj       return false;
69938fd1498Szrj   return true;
70038fd1498Szrj }
701