Branch data Line data Source code
1 : : /* Utilities for ipa analysis.
2 : : Copyright (C) 2005-2024 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 "backend.h"
25 : : #include "tree.h"
26 : : #include "gimple.h"
27 : : #include "predict.h"
28 : : #include "alloc-pool.h"
29 : : #include "cgraph.h"
30 : : #include "lto-streamer.h"
31 : : #include "dumpfile.h"
32 : : #include "splay-tree.h"
33 : : #include "ipa-utils.h"
34 : : #include "symbol-summary.h"
35 : : #include "tree-vrp.h"
36 : : #include "sreal.h"
37 : : #include "ipa-cp.h"
38 : : #include "ipa-prop.h"
39 : : #include "ipa-fnsummary.h"
40 : : #include "tree-eh.h"
41 : : #include "gimple-iterator.h"
42 : : #include "ipa-modref-tree.h"
43 : : #include "ipa-modref.h"
44 : : #include "tree-ssa-loop-niter.h"
45 : : #include "calls.h"
46 : : #include "cfgloop.h"
47 : : #include "cfganal.h"
48 : :
49 : : /* Debugging function for postorder and inorder code. NOTE is a string
50 : : that is printed before the nodes are printed. ORDER is an array of
51 : : cgraph_nodes that has COUNT useful nodes in it. */
52 : :
53 : : void
54 : 84 : ipa_print_order (FILE* out,
55 : : const char * note,
56 : : struct cgraph_node** order,
57 : : int count)
58 : : {
59 : 84 : int i;
60 : 84 : fprintf (out, "\n\n ordered call graph: %s\n", note);
61 : :
62 : 268 : for (i = count - 1; i >= 0; i--)
63 : 184 : order[i]->dump (out);
64 : 84 : fprintf (out, "\n");
65 : 84 : fflush (out);
66 : 84 : }
67 : :
68 : :
69 : : struct searchc_env {
70 : : struct cgraph_node **stack;
71 : : struct cgraph_node **result;
72 : : int stack_size;
73 : : int order_pos;
74 : : splay_tree nodes_marked_new;
75 : : bool reduce;
76 : : int count;
77 : : };
78 : :
79 : : /* This is an implementation of Tarjan's strongly connected region
80 : : finder as reprinted in Aho Hopcraft and Ullman's The Design and
81 : : Analysis of Computer Programs (1975) pages 192-193. This version
82 : : has been customized for cgraph_nodes. The env parameter is because
83 : : it is recursive and there are no nested functions here. This
84 : : function should only be called from itself or
85 : : ipa_reduced_postorder. ENV is a stack env and would be
86 : : unnecessary if C had nested functions. V is the node to start
87 : : searching from. */
88 : :
89 : : static void
90 : 12930168 : searchc (struct searchc_env* env, struct cgraph_node *v,
91 : : bool (*ignore_edge) (struct cgraph_edge *))
92 : : {
93 : 12930168 : struct cgraph_edge *edge;
94 : 12930168 : struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
95 : :
96 : : /* mark node as old */
97 : 12930168 : v_info->new_node = false;
98 : 12930168 : splay_tree_remove (env->nodes_marked_new, v->get_uid ());
99 : :
100 : 12930168 : v_info->dfn_number = env->count;
101 : 12930168 : v_info->low_link = env->count;
102 : 12930168 : env->count++;
103 : 12930168 : env->stack[(env->stack_size)++] = v;
104 : 12930168 : v_info->on_stack = true;
105 : :
106 : 54954655 : for (edge = v->callees; edge; edge = edge->next_callee)
107 : : {
108 : 42024487 : struct ipa_dfs_info * w_info;
109 : 42024487 : enum availability avail;
110 : 42024487 : struct cgraph_node *w = edge->callee->ultimate_alias_target (&avail);
111 : :
112 : 42024487 : if (!w || (ignore_edge && ignore_edge (edge)))
113 : 26228431 : continue;
114 : :
115 : 15796056 : if (w->aux
116 : 12719522 : && (avail >= AVAIL_INTERPOSABLE))
117 : : {
118 : 12719522 : w_info = (struct ipa_dfs_info *) w->aux;
119 : 12719522 : if (w_info->new_node)
120 : : {
121 : 5012169 : searchc (env, w, ignore_edge);
122 : 5012169 : v_info->low_link =
123 : 5012169 : (v_info->low_link < w_info->low_link) ?
124 : : v_info->low_link : w_info->low_link;
125 : : }
126 : : else
127 : 7707353 : if ((w_info->dfn_number < v_info->dfn_number)
128 : 6922956 : && (w_info->on_stack))
129 : 68359 : v_info->low_link =
130 : 68359 : (w_info->dfn_number < v_info->low_link) ?
131 : : w_info->dfn_number : v_info->low_link;
132 : : }
133 : : }
134 : :
135 : :
136 : 12930168 : if (v_info->low_link == v_info->dfn_number)
137 : : {
138 : : struct cgraph_node *last = NULL;
139 : 12930168 : struct cgraph_node *x;
140 : 12930168 : struct ipa_dfs_info *x_info;
141 : 12930168 : do {
142 : 12930168 : x = env->stack[--(env->stack_size)];
143 : 12930168 : x_info = (struct ipa_dfs_info *) x->aux;
144 : 12930168 : x_info->on_stack = false;
145 : 12930168 : x_info->scc_no = v_info->dfn_number;
146 : :
147 : 12930168 : if (env->reduce)
148 : : {
149 : 12930168 : x_info->next_cycle = last;
150 : 12930168 : last = x;
151 : : }
152 : : else
153 : 0 : env->result[env->order_pos++] = x;
154 : : }
155 : 12930168 : while (v != x);
156 : 12845335 : if (env->reduce)
157 : 12845335 : env->result[env->order_pos++] = v;
158 : : }
159 : 12930168 : }
160 : :
161 : : /* Topsort the call graph by caller relation. Put the result in ORDER.
162 : :
163 : : The REDUCE flag is true if you want the cycles reduced to single nodes.
164 : : You can use ipa_get_nodes_in_cycle to obtain a vector containing all real
165 : : call graph nodes in a reduced node.
166 : :
167 : : Set ALLOW_OVERWRITABLE if nodes with such availability should be included.
168 : : IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
169 : : for the topological sort. */
170 : :
171 : : int
172 : 1045450 : ipa_reduced_postorder (struct cgraph_node **order,
173 : : bool reduce,
174 : : bool (*ignore_edge) (struct cgraph_edge *))
175 : : {
176 : 1045450 : struct cgraph_node *node;
177 : 1045450 : struct searchc_env env;
178 : 1045450 : splay_tree_node result;
179 : 1045450 : env.stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
180 : 1045450 : env.stack_size = 0;
181 : 1045450 : env.result = order;
182 : 1045450 : env.order_pos = 0;
183 : 1045450 : env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
184 : 1045450 : env.count = 1;
185 : 1045450 : env.reduce = reduce;
186 : :
187 : 13975646 : FOR_EACH_DEFINED_FUNCTION (node)
188 : : {
189 : 12930196 : enum availability avail = node->get_availability ();
190 : :
191 : 12930196 : if (avail > AVAIL_INTERPOSABLE
192 : 12930196 : || avail == AVAIL_INTERPOSABLE)
193 : : {
194 : : /* Reuse the info if it is already there. */
195 : 12930168 : struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
196 : 12930168 : if (!info)
197 : 12930168 : info = XCNEW (struct ipa_dfs_info);
198 : 12930168 : info->new_node = true;
199 : 12930168 : info->on_stack = false;
200 : 12930168 : info->next_cycle = NULL;
201 : 12930168 : node->aux = info;
202 : :
203 : 12930168 : splay_tree_insert (env.nodes_marked_new,
204 : 12930168 : (splay_tree_key)node->get_uid (),
205 : : (splay_tree_value)node);
206 : : }
207 : : else
208 : 28 : node->aux = NULL;
209 : : }
210 : 1045450 : result = splay_tree_min (env.nodes_marked_new);
211 : 10008899 : while (result)
212 : : {
213 : 7917999 : node = (struct cgraph_node *)result->value;
214 : 7917999 : searchc (&env, node, ignore_edge);
215 : 7917999 : result = splay_tree_min (env.nodes_marked_new);
216 : : }
217 : 1045450 : splay_tree_delete (env.nodes_marked_new);
218 : 1045450 : free (env.stack);
219 : :
220 : 1045450 : return env.order_pos;
221 : : }
222 : :
223 : : /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
224 : : graph nodes. */
225 : :
226 : : void
227 : 1190870 : ipa_free_postorder_info (void)
228 : : {
229 : 1190870 : struct cgraph_node *node;
230 : 16293034 : FOR_EACH_DEFINED_FUNCTION (node)
231 : : {
232 : : /* Get rid of the aux information. */
233 : 15102164 : if (node->aux)
234 : : {
235 : 12930168 : free (node->aux);
236 : 12930168 : node->aux = NULL;
237 : : }
238 : : }
239 : 1190870 : }
240 : :
241 : : /* Get the set of nodes for the cycle in the reduced call graph starting
242 : : from NODE. */
243 : :
244 : : vec<cgraph_node *>
245 : 5840287 : ipa_get_nodes_in_cycle (struct cgraph_node *node)
246 : : {
247 : 5840287 : vec<cgraph_node *> v = vNULL;
248 : 5840287 : struct ipa_dfs_info *node_dfs_info;
249 : 11721290 : while (node)
250 : : {
251 : 5881003 : v.safe_push (node);
252 : 5881003 : node_dfs_info = (struct ipa_dfs_info *) node->aux;
253 : 5881003 : node = node_dfs_info->next_cycle;
254 : : }
255 : 5840287 : return v;
256 : : }
257 : :
258 : : /* Return true iff the CS is an edge within a strongly connected component as
259 : : computed by ipa_reduced_postorder. */
260 : :
261 : : bool
262 : 14973217 : ipa_edge_within_scc (struct cgraph_edge *cs)
263 : : {
264 : 14973217 : struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux;
265 : 14973217 : struct ipa_dfs_info *callee_dfs;
266 : 14973217 : struct cgraph_node *callee = cs->callee->function_symbol ();
267 : :
268 : 14973217 : callee_dfs = (struct ipa_dfs_info *) callee->aux;
269 : 14973217 : return (caller_dfs
270 : 14973217 : && callee_dfs
271 : 14973217 : && caller_dfs->scc_no == callee_dfs->scc_no);
272 : : }
273 : :
274 : : struct postorder_stack
275 : : {
276 : : struct cgraph_node *node;
277 : : struct cgraph_edge *edge;
278 : : int ref;
279 : : };
280 : :
281 : : /* Fill array order with all nodes with output flag set in the reverse
282 : : topological order. Return the number of elements in the array.
283 : : FIXME: While walking, consider aliases, too. */
284 : :
285 : : int
286 : 1231253 : ipa_reverse_postorder (struct cgraph_node **order)
287 : : {
288 : 1231253 : struct cgraph_node *node, *node2;
289 : 1231253 : int stack_size = 0;
290 : 1231253 : int order_pos = 0;
291 : 1231253 : struct cgraph_edge *edge;
292 : 1231253 : int pass;
293 : 1231253 : struct ipa_ref *ref = NULL;
294 : :
295 : 1231253 : struct postorder_stack *stack =
296 : 1231253 : XCNEWVEC (struct postorder_stack, symtab->cgraph_count);
297 : :
298 : : /* We have to deal with cycles nicely, so use a depth first traversal
299 : : output algorithm. Ignore the fact that some functions won't need
300 : : to be output and put them into order as well, so we get dependencies
301 : : right through inline functions. */
302 : 26425556 : FOR_EACH_FUNCTION (node)
303 : 23963050 : node->aux = NULL;
304 : 3693759 : for (pass = 0; pass < 2; pass++)
305 : 100777212 : FOR_EACH_FUNCTION (node)
306 : 47926100 : if (!node->aux
307 : 47926100 : && (pass
308 : 21598758 : || (!node->address_taken
309 : 14876925 : && !node->inlined_to
310 : 12705729 : && !node->alias && !node->thunk
311 : 12186119 : && !node->only_called_directly_p ())))
312 : : {
313 : 17686879 : stack_size = 0;
314 : 17686879 : stack[stack_size].node = node;
315 : 17686879 : stack[stack_size].edge = node->callers;
316 : 17686879 : stack[stack_size].ref = 0;
317 : 17686879 : node->aux = (void *)(size_t)1;
318 : 41649929 : while (stack_size >= 0)
319 : : {
320 : 67098893 : while (true)
321 : : {
322 : 67098893 : node2 = NULL;
323 : 109294853 : while (stack[stack_size].edge && !node2)
324 : : {
325 : 42195960 : edge = stack[stack_size].edge;
326 : 42195960 : node2 = edge->caller;
327 : 42195960 : stack[stack_size].edge = edge->next_caller;
328 : : }
329 : 162856864 : for (; stack[stack_size].node->iterate_referring (
330 : 76651919 : stack[stack_size].ref,
331 : 76651919 : ref) && !node2;
332 : : stack[stack_size].ref++)
333 : : {
334 : 9553026 : if (ref->use == IPA_REF_ALIAS)
335 : 10492909 : node2 = dyn_cast <cgraph_node *> (ref->referring);
336 : : }
337 : 67098893 : if (!node2)
338 : : break;
339 : 43135843 : if (!node2->aux)
340 : : {
341 : 6276171 : stack[++stack_size].node = node2;
342 : 6276171 : stack[stack_size].edge = node2->callers;
343 : 6276171 : stack[stack_size].ref = 0;
344 : 6276171 : node2->aux = (void *)(size_t)1;
345 : : }
346 : : }
347 : 23963050 : order[order_pos++] = stack[stack_size--].node;
348 : : }
349 : : }
350 : 1231253 : free (stack);
351 : 26425556 : FOR_EACH_FUNCTION (node)
352 : 23963050 : node->aux = NULL;
353 : 1231253 : return order_pos;
354 : : }
355 : :
356 : :
357 : :
358 : : /* Given a memory reference T, will return the variable at the bottom
359 : : of the access. Unlike get_base_address, this will recurse through
360 : : INDIRECT_REFS. */
361 : :
362 : : tree
363 : 4641699 : get_base_var (tree t)
364 : : {
365 : 4641699 : while (!SSA_VAR_P (t)
366 : 6892645 : && (!CONSTANT_CLASS_P (t))
367 : : && TREE_CODE (t) != LABEL_DECL
368 : : && TREE_CODE (t) != FUNCTION_DECL
369 : : && TREE_CODE (t) != CONST_DECL
370 : 9498027 : && TREE_CODE (t) != CONSTRUCTOR)
371 : : {
372 : 4856328 : t = TREE_OPERAND (t, 0);
373 : : }
374 : 4641699 : return t;
375 : : }
376 : :
377 : : /* Scale function of calls in NODE by ratio ORIG_COUNT/NODE->count. */
378 : :
379 : : void
380 : 0 : scale_ipa_profile_for_fn (struct cgraph_node *node, profile_count orig_count)
381 : : {
382 : 0 : profile_count to = node->count;
383 : 0 : profile_count::adjust_for_ipa_scaling (&to, &orig_count);
384 : 0 : struct cgraph_edge *e;
385 : :
386 : 0 : for (e = node->callees; e; e = e->next_callee)
387 : 0 : e->count = e->count.apply_scale (to, orig_count);
388 : 0 : for (e = node->indirect_calls; e; e = e->next_callee)
389 : 0 : e->count = e->count.apply_scale (to, orig_count);
390 : 0 : }
391 : :
392 : : /* SRC and DST are going to be merged. Take SRC's profile and merge it into
393 : : DST so it is not going to be lost. Possibly destroy SRC's body on the way
394 : : unless PRESERVE_BODY is set. */
395 : :
396 : : void
397 : 32270 : ipa_merge_profiles (struct cgraph_node *dst,
398 : : struct cgraph_node *src,
399 : : bool preserve_body)
400 : : {
401 : 32270 : tree oldsrcdecl = src->decl;
402 : 32270 : struct function *srccfun, *dstcfun;
403 : 32270 : bool match = true;
404 : 32270 : bool copy_counts = false;
405 : :
406 : 32270 : if (!src->definition
407 : 30452 : || !dst->definition)
408 : 32266 : return;
409 : :
410 : 30452 : if (src->frequency < dst->frequency)
411 : 70 : src->frequency = dst->frequency;
412 : :
413 : : /* Time profiles are merged. */
414 : 30452 : if (dst->tp_first_run > src->tp_first_run && src->tp_first_run)
415 : 1 : dst->tp_first_run = src->tp_first_run;
416 : :
417 : 30452 : if (src->profile_id && !dst->profile_id)
418 : 0 : dst->profile_id = src->profile_id;
419 : :
420 : : /* Merging zero profile to dst is no-op. */
421 : 30452 : if (src->count.ipa () == profile_count::zero ())
422 : 130 : return;
423 : :
424 : : /* FIXME when we merge in unknown profile, we ought to set counts as
425 : : unsafe. */
426 : 30322 : if (!src->count.initialized_p ()
427 : 30322 : || !(src->count.ipa () == src->count))
428 : 30318 : return;
429 : 4 : profile_count orig_count = dst->count;
430 : :
431 : : /* Either sum the profiles if both are IPA and not global0, or
432 : : pick more informative one (that is nonzero IPA if other is
433 : : uninitialized, guessed or global0). */
434 : :
435 : 4 : if ((dst->count.ipa ().nonzero_p ()
436 : 0 : || src->count.ipa ().nonzero_p ())
437 : 4 : && dst->count.ipa ().initialized_p ()
438 : 4 : && src->count.ipa ().initialized_p ())
439 : 4 : dst->count = dst->count.ipa () + src->count.ipa ();
440 : 0 : else if (dst->count.ipa ().initialized_p ())
441 : : ;
442 : 0 : else if (src->count.ipa ().initialized_p ())
443 : : {
444 : 0 : copy_counts = true;
445 : 0 : dst->count = src->count.ipa ();
446 : : }
447 : :
448 : : /* If no updating needed return early. */
449 : 32270 : if (dst->count == orig_count)
450 : : return;
451 : :
452 : 4 : if (symtab->dump_file)
453 : : {
454 : 0 : fprintf (symtab->dump_file, "Merging profiles of %s count:",
455 : : src->dump_name ());
456 : 0 : src->count.dump (symtab->dump_file);
457 : 0 : fprintf (symtab->dump_file, " to %s count:",
458 : : dst->dump_name ());
459 : 0 : orig_count.dump (symtab->dump_file);
460 : 0 : fprintf (symtab->dump_file, " resulting count:");
461 : 0 : dst->count.dump (symtab->dump_file);
462 : 0 : fprintf (symtab->dump_file, "\n");
463 : : }
464 : :
465 : : /* First handle functions with no gimple body. */
466 : 4 : if (dst->thunk || dst->alias
467 : 4 : || src->thunk || src->alias)
468 : : {
469 : 0 : scale_ipa_profile_for_fn (dst, orig_count);
470 : 0 : return;
471 : : }
472 : :
473 : : /* This is ugly. We need to get both function bodies into memory.
474 : : If declaration is merged, we need to duplicate it to be able
475 : : to load body that is being replaced. This makes symbol table
476 : : temporarily inconsistent. */
477 : 4 : if (src->decl == dst->decl)
478 : : {
479 : 0 : struct lto_in_decl_state temp;
480 : 0 : struct lto_in_decl_state *state;
481 : :
482 : : /* We are going to move the decl, we want to remove its file decl data.
483 : : and link these with the new decl. */
484 : 0 : temp.fn_decl = src->decl;
485 : 0 : lto_in_decl_state **slot
486 : 0 : = src->lto_file_data->function_decl_states->find_slot (&temp,
487 : : NO_INSERT);
488 : 0 : state = *slot;
489 : 0 : src->lto_file_data->function_decl_states->clear_slot (slot);
490 : 0 : gcc_assert (state);
491 : :
492 : : /* Duplicate the decl and be sure it does not link into body of DST. */
493 : 0 : src->decl = copy_node (src->decl);
494 : 0 : DECL_STRUCT_FUNCTION (src->decl) = NULL;
495 : 0 : DECL_ARGUMENTS (src->decl) = NULL;
496 : 0 : DECL_INITIAL (src->decl) = NULL;
497 : 0 : DECL_RESULT (src->decl) = NULL;
498 : :
499 : : /* Associate the decl state with new declaration, so LTO streamer
500 : : can look it up. */
501 : 0 : state->fn_decl = src->decl;
502 : 0 : slot
503 : 0 : = src->lto_file_data->function_decl_states->find_slot (state, INSERT);
504 : 0 : gcc_assert (!*slot);
505 : 0 : *slot = state;
506 : : }
507 : 4 : src->get_untransformed_body ();
508 : 4 : dst->get_untransformed_body ();
509 : 4 : srccfun = DECL_STRUCT_FUNCTION (src->decl);
510 : 4 : dstcfun = DECL_STRUCT_FUNCTION (dst->decl);
511 : 4 : if (n_basic_blocks_for_fn (srccfun)
512 : 4 : != n_basic_blocks_for_fn (dstcfun))
513 : : {
514 : 0 : if (symtab->dump_file)
515 : 0 : fprintf (symtab->dump_file,
516 : : "Giving up; number of basic block mismatch.\n");
517 : : match = false;
518 : : }
519 : 4 : else if (last_basic_block_for_fn (srccfun)
520 : 4 : != last_basic_block_for_fn (dstcfun))
521 : : {
522 : 0 : if (symtab->dump_file)
523 : 0 : fprintf (symtab->dump_file,
524 : : "Giving up; last block mismatch.\n");
525 : : match = false;
526 : : }
527 : : else
528 : : {
529 : 4 : basic_block srcbb, dstbb;
530 : 4 : struct cgraph_edge *e, *e2;
531 : :
532 : 5 : for (e = dst->callees, e2 = src->callees; e && e2 && match;
533 : 1 : e2 = e2->next_callee, e = e->next_callee)
534 : : {
535 : 1 : if (gimple_bb (e->call_stmt)->index
536 : 1 : != gimple_bb (e2->call_stmt)->index)
537 : : {
538 : 0 : if (symtab->dump_file)
539 : 0 : fprintf (symtab->dump_file,
540 : : "Giving up; call stmt mismatch.\n");
541 : : match = false;
542 : : }
543 : : }
544 : 4 : if (e || e2)
545 : : {
546 : 0 : if (symtab->dump_file)
547 : 0 : fprintf (symtab->dump_file,
548 : : "Giving up; number of calls differs.\n");
549 : : match = false;
550 : : }
551 : 4 : for (e = dst->indirect_calls, e2 = src->indirect_calls; e && e2 && match;
552 : 0 : e2 = e2->next_callee, e = e->next_callee)
553 : : {
554 : 0 : if (gimple_bb (e->call_stmt)->index
555 : 0 : != gimple_bb (e2->call_stmt)->index)
556 : : {
557 : 0 : if (symtab->dump_file)
558 : 0 : fprintf (symtab->dump_file,
559 : : "Giving up; indirect call stmt mismatch.\n");
560 : : match = false;
561 : : }
562 : : }
563 : 4 : if (e || e2)
564 : : {
565 : 0 : if (symtab->dump_file)
566 : 0 : fprintf (symtab->dump_file,
567 : : "Giving up; number of indirect calls differs.\n");
568 : : match=false;
569 : : }
570 : :
571 : 4 : if (match)
572 : 18 : FOR_ALL_BB_FN (srcbb, srccfun)
573 : : {
574 : 14 : unsigned int i;
575 : :
576 : 14 : dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index);
577 : 14 : if (dstbb == NULL)
578 : : {
579 : 0 : if (symtab->dump_file)
580 : 0 : fprintf (symtab->dump_file,
581 : : "No matching block for bb %i.\n",
582 : : srcbb->index);
583 : : match = false;
584 : : break;
585 : : }
586 : 34 : if (EDGE_COUNT (srcbb->succs) != EDGE_COUNT (dstbb->succs))
587 : : {
588 : 0 : if (symtab->dump_file)
589 : 0 : fprintf (symtab->dump_file,
590 : : "Edge count mismatch for bb %i.\n",
591 : : srcbb->index);
592 : : match = false;
593 : : break;
594 : : }
595 : 25 : for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
596 : : {
597 : 11 : edge srce = EDGE_SUCC (srcbb, i);
598 : 11 : edge dste = EDGE_SUCC (dstbb, i);
599 : 11 : if (srce->dest->index != dste->dest->index)
600 : : {
601 : 0 : if (symtab->dump_file)
602 : 0 : fprintf (symtab->dump_file,
603 : : "Succ edge mismatch for bb %i.\n",
604 : : srce->dest->index);
605 : : match = false;
606 : : break;
607 : : }
608 : : }
609 : : }
610 : : }
611 : 4 : if (match)
612 : : {
613 : 4 : struct cgraph_edge *e, *e2;
614 : 4 : basic_block srcbb, dstbb;
615 : :
616 : : /* Function and global profile may be out of sync. First scale it same
617 : : way as fixup_cfg would. */
618 : 4 : profile_count srcnum = src->count;
619 : 4 : profile_count srcden = ENTRY_BLOCK_PTR_FOR_FN (srccfun)->count;
620 : 4 : bool srcscale = srcnum.initialized_p () && !(srcnum == srcden);
621 : 4 : profile_count dstnum = orig_count;
622 : 4 : profile_count dstden = ENTRY_BLOCK_PTR_FOR_FN (dstcfun)->count;
623 : 4 : bool dstscale = !copy_counts
624 : 4 : && dstnum.initialized_p () && !(dstnum == dstden);
625 : :
626 : : /* TODO: merge also statement histograms. */
627 : 18 : FOR_ALL_BB_FN (srcbb, srccfun)
628 : : {
629 : 14 : unsigned int i;
630 : :
631 : 14 : dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index);
632 : :
633 : 14 : profile_count srccount = srcbb->count;
634 : 14 : if (srcscale)
635 : 0 : srccount = srccount.apply_scale (srcnum, srcden);
636 : 14 : if (dstscale)
637 : 0 : dstbb->count = dstbb->count.apply_scale (dstnum, dstden);
638 : :
639 : 14 : if (copy_counts)
640 : : {
641 : 0 : dstbb->count = srccount;
642 : 0 : for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
643 : : {
644 : 0 : edge srce = EDGE_SUCC (srcbb, i);
645 : 0 : edge dste = EDGE_SUCC (dstbb, i);
646 : 0 : if (srce->probability.initialized_p ())
647 : 0 : dste->probability = srce->probability;
648 : : }
649 : : }
650 : : else
651 : : {
652 : 46 : for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
653 : : {
654 : 11 : edge srce = EDGE_SUCC (srcbb, i);
655 : 11 : edge dste = EDGE_SUCC (dstbb, i);
656 : 11 : profile_count sum =
657 : 11 : dstbb->count.ipa () + srccount.ipa ();
658 : 22 : if (sum.nonzero_p ())
659 : 10 : dste->probability =
660 : 20 : dste->probability * dstbb->count.ipa ().probability_in
661 : 10 : (sum)
662 : 10 : + srce->probability * srcbb->count.ipa ().probability_in
663 : 20 : (sum);
664 : : }
665 : 14 : dstbb->count = dstbb->count.ipa () + srccount.ipa ();
666 : : }
667 : : }
668 : 4 : push_cfun (dstcfun);
669 : 4 : update_max_bb_count ();
670 : 4 : compute_function_frequency ();
671 : 4 : pop_cfun ();
672 : 5 : for (e = dst->callees; e; e = e->next_callee)
673 : : {
674 : 1 : if (e->speculative)
675 : 0 : continue;
676 : 1 : e->count = gimple_bb (e->call_stmt)->count;
677 : : }
678 : 4 : for (e = dst->indirect_calls, e2 = src->indirect_calls; e;
679 : 0 : e2 = (e2 ? e2->next_callee : NULL), e = e->next_callee)
680 : : {
681 : 0 : if (!e->speculative && !e2->speculative)
682 : : {
683 : : /* FIXME: we need to also merge ipa-profile histograms
684 : : because with LTO merging happens from lto-symtab before
685 : : these are converted to indirect edges. */
686 : 0 : e->count = gimple_bb (e->call_stmt)->count;
687 : 0 : continue;
688 : : }
689 : :
690 : : /* When copying just remove all speuclations on dst and then copy
691 : : one from src. */
692 : 0 : if (copy_counts)
693 : : {
694 : 0 : while (e->speculative)
695 : 0 : cgraph_edge::resolve_speculation (e, NULL);
696 : 0 : e->count = gimple_bb (e->call_stmt)->count;
697 : 0 : if (e2->speculative)
698 : : {
699 : 0 : for (cgraph_edge *e3 = e2->first_speculative_call_target ();
700 : 0 : e3;
701 : 0 : e3 = e3->next_speculative_call_target ())
702 : : {
703 : 0 : cgraph_edge *ns;
704 : 0 : ns = e->make_speculative
705 : 0 : (dyn_cast <cgraph_node *>
706 : 0 : (e3->speculative_call_target_ref ()->referred),
707 : 0 : e3->count, e3->speculative_id);
708 : : /* Target may differ from ref (for example it may be
709 : : redirected to local alias. */
710 : 0 : ns->redirect_callee (e3->callee);
711 : : }
712 : : }
713 : 0 : continue;
714 : 0 : }
715 : :
716 : : /* Iterate all speculations in SRC, see if corresponding ones exist
717 : : int DST and if so, sum the counts. Otherwise create new
718 : : speculation. */
719 : 0 : int max_spec = 0;
720 : 0 : for (cgraph_edge *e3 = e->first_speculative_call_target ();
721 : 0 : e3;
722 : 0 : e3 = e3->next_speculative_call_target ())
723 : 0 : if (e3->speculative_id > max_spec)
724 : : max_spec = e3->speculative_id;
725 : 0 : for (cgraph_edge *e3 = e2->first_speculative_call_target ();
726 : 0 : e3;
727 : 0 : e3 = e3->next_speculative_call_target ())
728 : : {
729 : 0 : cgraph_edge *te
730 : : = e->speculative_call_for_target
731 : 0 : (dyn_cast <cgraph_node *>
732 : 0 : (e3->speculative_call_target_ref ()->referred));
733 : 0 : if (te)
734 : 0 : te->count = te->count + e3->count;
735 : : else
736 : : {
737 : 0 : e->count = e->count + e3->count;
738 : 0 : cgraph_edge *ns;
739 : 0 : ns = e->make_speculative
740 : 0 : (dyn_cast <cgraph_node *>
741 : 0 : (e3->speculative_call_target_ref ()
742 : : ->referred),
743 : : e3->count,
744 : 0 : e3->speculative_id + max_spec + 1);
745 : : /* Target may differ from ref (for example it may be
746 : : redirected to local alias. */
747 : 0 : ns->redirect_callee (e3->callee);
748 : : }
749 : : }
750 : : }
751 : 4 : if (!preserve_body)
752 : 1 : src->release_body ();
753 : : /* Update summary. */
754 : 4 : compute_fn_summary (dst, 0);
755 : : }
756 : : /* We can't update CFG profile, but we can scale IPA profile. CFG
757 : : will be scaled according to dst->count after IPA passes. */
758 : : else
759 : 0 : scale_ipa_profile_for_fn (dst, orig_count);
760 : 4 : src->decl = oldsrcdecl;
761 : : }
762 : :
763 : : /* Return true if call to DEST is known to be self-recusive
764 : : call withing FUNC. */
765 : :
766 : : bool
767 : 27854391 : recursive_call_p (tree func, tree dest)
768 : : {
769 : 27854391 : struct cgraph_node *dest_node = cgraph_node::get_create (dest);
770 : 27854391 : struct cgraph_node *cnode = cgraph_node::get_create (func);
771 : 27854391 : ipa_ref *alias;
772 : 27854391 : enum availability avail;
773 : :
774 : 27854391 : gcc_assert (!cnode->alias);
775 : 27854391 : if (cnode != dest_node->ultimate_alias_target (&avail))
776 : : return false;
777 : 67149 : if (avail >= AVAIL_AVAILABLE)
778 : : return true;
779 : 2377 : if (!dest_node->semantically_equivalent_p (cnode))
780 : : return false;
781 : : /* If there is only one way to call the fuction or we know all of them
782 : : are semantically equivalent, we still can consider call recursive. */
783 : 2432 : FOR_EACH_ALIAS (cnode, alias)
784 : 64 : if (!dest_node->semantically_equivalent_p (alias->referring))
785 : : return false;
786 : : return true;
787 : : }
788 : :
789 : : /* Return true if stmt may terminate execution of function.
790 : : If assume_return_or_eh we can further assume that the function ends
791 : : either by retrn statement or EH (no trapping or infinite loops). */
792 : :
793 : : bool
794 : 64972035 : stmt_may_terminate_function_p (function *fun, gimple *stmt, bool assume_return_or_eh)
795 : : {
796 : 64972035 : if (stmt_can_throw_external (fun, stmt))
797 : : return true;
798 : 63079882 : if (assume_return_or_eh)
799 : : return false;
800 : 773238 : gasm *astmt = dyn_cast <gasm *> (stmt);
801 : 20 : if (astmt && gimple_asm_volatile_p (astmt))
802 : : return true;
803 : 773218 : if (gimple_could_trap_p (stmt))
804 : : return true;
805 : 706069 : if (gcall *call = dyn_cast <gcall *> (stmt))
806 : : {
807 : 206436 : int flags = gimple_call_flags (call);
808 : 206436 : if (flags & (ECF_PURE | ECF_CONST) && ! (flags & ECF_LOOPING_CONST_OR_PURE))
809 : : return false;
810 : 70276 : modref_summary *s = get_modref_function_summary (call, NULL);
811 : 70276 : if (s && !s->side_effects)
812 : : return false;
813 : : return true;
814 : : }
815 : : return false;
816 : : }
817 : :
818 : : /* Return bitmap of all basic blocks whose first statements are known to
819 : : execute on every invocation of the function.
820 : :
821 : : If assume_return_or_eh we can further assume that the function ends
822 : : either by retrn statement or EH (no trapping or infinite loops).
823 : : This is useful when sumarizing function in passes like ipa-modref.
824 : :
825 : : Seeing assume_return_or_eh to false is used to prove that given
826 : : statmeent will be executed even if the function gets into infinite
827 : : loop or trap. */
828 : : bitmap
829 : 4483565 : find_always_executed_bbs (function *fun, bool assume_return_or_eh)
830 : : {
831 : 4483565 : auto_vec<basic_block, 20> stack;
832 : 4483565 : auto_vec<basic_block, 20> terminating_bbs;
833 : 4483565 : hash_set<basic_block> visited;
834 : 4483565 : hash_set<basic_block> terminating_bbs_set;
835 : 4483565 : edge e;
836 : 4483565 : edge_iterator ei;
837 : 4483565 : int flags = flags_from_decl_or_type (fun->decl);
838 : : /* PUre and const functions always return. */
839 : 4483565 : assume_return_or_eh |= (flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE);
840 : 4483565 : if (!assume_return_or_eh)
841 : 52376 : mark_dfs_back_edges (fun);
842 : :
843 : : /* First walk all BBs reachable from entry stopping on statements that may
844 : : terminate execution. Everything past this statement is not going to be executed
845 : : each invocation. */
846 : 4483565 : stack.safe_push (ENTRY_BLOCK_PTR_FOR_FN (fun));
847 : 40745087 : while (!stack.is_empty ())
848 : : {
849 : 31777957 : basic_block bb = stack.pop ();
850 : 31777957 : bool found = false, found_exit = false;
851 : 31777957 : if (bb->index == EXIT_BLOCK)
852 : 3168482 : continue;
853 : 61316460 : FOR_EACH_EDGE (e, ei, bb->succs)
854 : : {
855 : 36656591 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (fun))
856 : : {
857 : : found_exit = true;
858 : : break;
859 : : }
860 : : /* Watch for infinite loops. */
861 : 32706985 : if (!found
862 : 673137 : && !assume_return_or_eh && (e->flags & EDGE_DFS_BACK))
863 : : {
864 : 43824 : if (!dom_info_available_p (CDI_DOMINATORS))
865 : 919 : calculate_dominance_info (CDI_DOMINATORS);
866 : : /* If this is not a loop latch edge it is an irreducible region.
867 : : Assume that it is infinite.
868 : : TODO: with C++ forced progression we can still walk the
869 : : irreducible region and see if it contains any side effects.
870 : : Similarly for loops. -ffinite-loops does not really imply
871 : : this since we allow inlining across -ffinite-loops bondary
872 : : and thus it can be used only as a loop flag. */
873 : 43824 : if (e->dest->loop_father->header != e->dest
874 : 43824 : || !dominated_by_p (CDI_DOMINATORS, bb, e->dest))
875 : : found = true;
876 : 43824 : else if (!finite_loop_p (e->dest->loop_father))
877 : 8 : found = true;
878 : : }
879 : : }
880 : 28609475 : if (!assume_return_or_eh
881 : 28609475 : && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP)))
882 : : found = true;
883 : 28609475 : for (gimple_stmt_iterator si = gsi_start_nondebug_after_labels_bb (bb);
884 : 91453295 : !gsi_end_p (si) && !found; gsi_next_nondebug (&si))
885 : 64867054 : if (stmt_may_terminate_function_p (fun, gsi_stmt (si), assume_return_or_eh))
886 : : {
887 : : found = true;
888 : : break;
889 : : }
890 : 28609475 : if (found)
891 : : {
892 : 2026161 : visited.add (EXIT_BLOCK_PTR_FOR_FN (fun));
893 : 2026161 : if (!found_exit)
894 : : {
895 : 1337238 : terminating_bbs.safe_push (bb);
896 : 1337238 : terminating_bbs_set.add (bb);
897 : : }
898 : : }
899 : : else
900 : 61128267 : FOR_EACH_EDGE (e, ei, bb->succs)
901 : 34544953 : if (!visited.add (e->dest))
902 : 27294392 : stack.safe_push (e->dest);
903 : : }
904 : :
905 : : /* Next walk from exit block and find all articulations in the CFG.
906 : : Add all terminating basic blocks as "fake" predecessors of the
907 : : exit block. */
908 : :
909 : 4483565 : bitmap ret = BITMAP_ALLOC (NULL);
910 : : /* A degenerated case when there is no path to exit. */
911 : 4483565 : if (!visited.contains (EXIT_BLOCK_PTR_FOR_FN (fun)))
912 : : {
913 : 108678 : bitmap_set_bit (ret,
914 : : single_succ_edge
915 : 54339 : (ENTRY_BLOCK_PTR_FOR_FN (fun))->dest->index);
916 : 54339 : return ret;
917 : : }
918 : :
919 : 4429226 : struct astate
920 : : {
921 : : unsigned int dfs_preorder;
922 : : unsigned int dfs_postorder;
923 : :
924 : : unsigned int low, high;
925 : : };
926 : :
927 : 4429226 : struct worklist
928 : : {
929 : : basic_block bb;
930 : : astate *cstate;
931 : : };
932 : :
933 : 4429226 : struct obstack state_obstack;
934 : 4429226 : gcc_obstack_init (&state_obstack);
935 : 4429226 : hash_map<basic_block, astate *> state;
936 : 4429226 : auto_vec<worklist, 32> worklist_vec;
937 : 4429226 : unsigned int next_dfs_num = 1;
938 : :
939 : : /* Always executed blocks are blocks that are on every path from entry to exit.
940 : : We proceed in two steps. First we do backward DFS walk (so we know that entry
941 : : is always reached) and record preorder and postorder visiting times.
942 : :
943 : : In second step we proceed in postorder and for every block A we compute
944 : : minimal preorder (A.low) and maximal postorder (A.high) of block reachable
945 : : from the BBs in DFS subtree of A. If A is always executed there are no
946 : : edges out of this subtree. This can be tested by checking that A.low == A.preorder
947 : : and B.high == A.postorder.
948 : :
949 : : This is first step. Do backward DFS walk and record preorder, postorder
950 : : and predecessor info. Initialize stack in postorder. */
951 : 4429226 : worklist we = {EXIT_BLOCK_PTR_FOR_FN (fun), NULL};
952 : 4429226 : worklist_vec.safe_push (we);
953 : 69556573 : while (!worklist_vec.is_empty ())
954 : : {
955 : 60698121 : worklist &w = worklist_vec.last ();
956 : 60698121 : basic_block bb = w.bb;
957 : 60698121 : astate *cstate = w.cstate;
958 : :
959 : 60698121 : if (!cstate)
960 : : {
961 : 34177406 : astate **slot = &state.get_or_insert (bb);
962 : :
963 : 34177406 : cstate = *slot;
964 : : /* Already processed by DFS? */
965 : 34177406 : if (cstate)
966 : : {
967 : 7656691 : worklist_vec.pop ();
968 : 34177406 : continue;
969 : : }
970 : : /* DFS is visiting BB for first time. */
971 : 26520715 : *slot = cstate = XOBNEW (&state_obstack, struct astate);
972 : 26520715 : cstate->low = cstate->high = cstate->dfs_preorder = next_dfs_num++;
973 : 26520715 : w.cstate = cstate;
974 : : /* Exit block is special; process all fake edges we identified. */
975 : 26520715 : if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
976 : 14624916 : for (basic_block bb2 : terminating_bbs)
977 : : {
978 : 1337238 : worklist we = {bb2, NULL};
979 : 1337238 : worklist_vec.safe_push (we);
980 : : }
981 : 60063582 : FOR_EACH_EDGE (e, ei, bb->preds)
982 : 33542867 : if (visited.contains (e->src))
983 : : {
984 : 28410942 : worklist we = {e->src, NULL};
985 : 28410942 : worklist_vec.safe_push (we);
986 : : }
987 : : /* Keep BB on worklist so we process it last time. */
988 : 26520715 : continue;
989 : 26520715 : }
990 : : /* We are finished with processing reachable BBs, see if we have articulation. */
991 : 26520715 : worklist_vec.pop ();
992 : 26520715 : cstate->high = cstate->dfs_postorder = next_dfs_num++;
993 : 26520715 : stack.safe_push (bb);
994 : : }
995 : : /* This is the final postorder walk. Determine low and high values and mark
996 : : always executed blocks. */
997 : 39808393 : for (basic_block bb : stack)
998 : : {
999 : 26520715 : astate *cstate = *state.get (bb);
1000 : 60063582 : FOR_EACH_EDGE (e, ei, bb->preds)
1001 : : {
1002 : 33542867 : astate **cstate2 = state.get (e->src);
1003 : : /* We skip walking part of CFG reached only after first edge to exit.
1004 : : No BB reachable from the skipped part is always executed */
1005 : 33542867 : if (!cstate2)
1006 : : {
1007 : 5131925 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (fun))
1008 : 702699 : cstate->low = 0;
1009 : 5131925 : continue;
1010 : : }
1011 : 28410942 : cstate->low = MIN (cstate->low, (*cstate2)->low);
1012 : 28410942 : cstate->high = MAX (cstate->high, (*cstate2)->high);
1013 : : }
1014 : 26520715 : if (dump_file && (dump_flags & TDF_DETAILS) && bb != EXIT_BLOCK_PTR_FOR_FN (fun))
1015 : 16 : fprintf (dump_file, "BB %i %s preorder %i posorder %i low %i high %i\n",
1016 : 8 : bb->index, terminating_bbs_set.contains (bb) ? "(terminating)": "",
1017 : : cstate->dfs_preorder, cstate->dfs_postorder, cstate->low, cstate->high);
1018 : 26520715 : if (cstate->low == cstate->dfs_preorder && cstate->high == cstate->dfs_postorder
1019 : 11337019 : && bb != EXIT_BLOCK_PTR_FOR_FN (fun))
1020 : 7549693 : bitmap_set_bit (ret, bb->index);
1021 : 26520715 : if (terminating_bbs_set.contains (bb))
1022 : 1337238 : cstate->low = 0;
1023 : : else
1024 : 54697690 : FOR_EACH_EDGE (e, ei, bb->succs)
1025 : : {
1026 : 29514213 : astate **cstate2 = state.get (e->dest);
1027 : 29514213 : if (!cstate2)
1028 : 1430024 : continue;
1029 : 28084189 : cstate->low = MIN (cstate->low, (*cstate2)->low);
1030 : 28084189 : cstate->high = MAX (cstate->high, (*cstate2)->high);
1031 : : }
1032 : : }
1033 : 4429226 : obstack_free (&state_obstack, NULL);
1034 : 4429226 : if (dump_file)
1035 : : {
1036 : 187 : fprintf (dump_file, "Always executed bbbs %s: ",
1037 : : assume_return_or_eh ? "(assuming return or EH)": "");
1038 : 176 : bitmap_print (dump_file, ret, "", "\n");
1039 : : }
1040 : :
1041 : 4429226 : return ret;
1042 : 8912791 : }
|
