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