]>
Commit | Line | Data |
---|---|---|
ea900239 | 1 | /* Utilities for ipa analysis. |
a945c346 | 2 | Copyright (C) 2005-2024 Free Software Foundation, Inc. |
ea900239 DB |
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
ea900239 DB |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
ea900239 DB |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
c7131fb2 AM |
24 | #include "backend.h" |
25 | #include "tree.h" | |
26 | #include "gimple.h" | |
957060b5 AM |
27 | #include "predict.h" |
28 | #include "alloc-pool.h" | |
29 | #include "cgraph.h" | |
30 | #include "lto-streamer.h" | |
7ee2468b | 31 | #include "dumpfile.h" |
ea264ca5 | 32 | #include "splay-tree.h" |
ea900239 | 33 | #include "ipa-utils.h" |
dd912cb8 | 34 | #include "symbol-summary.h" |
8bc5448f | 35 | #include "tree-vrp.h" |
c8742849 MJ |
36 | #include "sreal.h" |
37 | #include "ipa-cp.h" | |
c582198b | 38 | #include "ipa-prop.h" |
27d020cf | 39 | #include "ipa-fnsummary.h" |
b1f30bf4 JH |
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" | |
da3aca03 JH |
45 | #include "calls.h" |
46 | #include "cfgloop.h" | |
47 | #include "cfganal.h" | |
ea900239 DB |
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 | ||
b8698a0f | 53 | void |
af8bca3c MJ |
54 | ipa_print_order (FILE* out, |
55 | const char * note, | |
56 | struct cgraph_node** order, | |
57 | int count) | |
ea900239 DB |
58 | { |
59 | int i; | |
60 | fprintf (out, "\n\n ordered call graph: %s\n", note); | |
b8698a0f | 61 | |
ea900239 | 62 | for (i = count - 1; i >= 0; i--) |
d52f5295 | 63 | order[i]->dump (out); |
ea900239 | 64 | fprintf (out, "\n"); |
c3284718 | 65 | fflush (out); |
ea900239 DB |
66 | } |
67 | ||
d52f5295 | 68 | |
ea900239 DB |
69 | struct searchc_env { |
70 | struct cgraph_node **stack; | |
ea900239 | 71 | struct cgraph_node **result; |
34e82342 | 72 | int stack_size; |
ea900239 DB |
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 | |
af8bca3c | 85 | ipa_reduced_postorder. ENV is a stack env and would be |
ea900239 DB |
86 | unnecessary if C had nested functions. V is the node to start |
87 | searching from. */ | |
88 | ||
89 | static void | |
2505c5ed JH |
90 | searchc (struct searchc_env* env, struct cgraph_node *v, |
91 | bool (*ignore_edge) (struct cgraph_edge *)) | |
ea900239 DB |
92 | { |
93 | struct cgraph_edge *edge; | |
67348ccc | 94 | struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux; |
b8698a0f | 95 | |
ea900239 | 96 | /* mark node as old */ |
c5274326 | 97 | v_info->new_node = false; |
4325656f | 98 | splay_tree_remove (env->nodes_marked_new, v->get_uid ()); |
b8698a0f | 99 | |
ea900239 DB |
100 | v_info->dfn_number = env->count; |
101 | v_info->low_link = env->count; | |
102 | env->count++; | |
103 | env->stack[(env->stack_size)++] = v; | |
104 | v_info->on_stack = true; | |
b8698a0f | 105 | |
ea900239 DB |
106 | for (edge = v->callees; edge; edge = edge->next_callee) |
107 | { | |
108 | struct ipa_dfs_info * w_info; | |
fede8efa | 109 | enum availability avail; |
d52f5295 | 110 | struct cgraph_node *w = edge->callee->ultimate_alias_target (&avail); |
e2c9111c | 111 | |
fede8efa | 112 | if (!w || (ignore_edge && ignore_edge (edge))) |
2505c5ed JH |
113 | continue; |
114 | ||
67348ccc | 115 | if (w->aux |
97e59627 | 116 | && (avail >= AVAIL_INTERPOSABLE)) |
ea900239 | 117 | { |
67348ccc | 118 | w_info = (struct ipa_dfs_info *) w->aux; |
b8698a0f | 119 | if (w_info->new_node) |
ea900239 | 120 | { |
2505c5ed | 121 | searchc (env, w, ignore_edge); |
ea900239 DB |
122 | v_info->low_link = |
123 | (v_info->low_link < w_info->low_link) ? | |
124 | v_info->low_link : w_info->low_link; | |
b8698a0f L |
125 | } |
126 | else | |
127 | if ((w_info->dfn_number < v_info->dfn_number) | |
128 | && (w_info->on_stack)) | |
ea900239 DB |
129 | v_info->low_link = |
130 | (w_info->dfn_number < v_info->low_link) ? | |
131 | w_info->dfn_number : v_info->low_link; | |
132 | } | |
133 | } | |
134 | ||
135 | ||
b8698a0f | 136 | if (v_info->low_link == v_info->dfn_number) |
ea900239 DB |
137 | { |
138 | struct cgraph_node *last = NULL; | |
139 | struct cgraph_node *x; | |
140 | struct ipa_dfs_info *x_info; | |
141 | do { | |
142 | x = env->stack[--(env->stack_size)]; | |
67348ccc | 143 | x_info = (struct ipa_dfs_info *) x->aux; |
ea900239 | 144 | x_info->on_stack = false; |
11026b51 | 145 | x_info->scc_no = v_info->dfn_number; |
b8698a0f L |
146 | |
147 | if (env->reduce) | |
ea900239 DB |
148 | { |
149 | x_info->next_cycle = last; | |
150 | last = x; | |
b8698a0f L |
151 | } |
152 | else | |
ea900239 | 153 | env->result[env->order_pos++] = x; |
b8698a0f | 154 | } |
ea900239 | 155 | while (v != x); |
b8698a0f | 156 | if (env->reduce) |
ea900239 DB |
157 | env->result[env->order_pos++] = v; |
158 | } | |
159 | } | |
160 | ||
161 | /* Topsort the call graph by caller relation. Put the result in ORDER. | |
162 | ||
df92c640 SB |
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. | |
af8bca3c MJ |
168 | IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant |
169 | for the topological sort. */ | |
ea900239 DB |
170 | |
171 | int | |
af8bca3c | 172 | ipa_reduced_postorder (struct cgraph_node **order, |
45272fd2 | 173 | bool reduce, |
af8bca3c | 174 | bool (*ignore_edge) (struct cgraph_edge *)) |
ea900239 DB |
175 | { |
176 | struct cgraph_node *node; | |
177 | struct searchc_env env; | |
178 | splay_tree_node result; | |
3dafb85c | 179 | env.stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); |
ea900239 DB |
180 | env.stack_size = 0; |
181 | env.result = order; | |
182 | env.order_pos = 0; | |
183 | env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0); | |
184 | env.count = 1; | |
185 | env.reduce = reduce; | |
b8698a0f | 186 | |
65c70e6b | 187 | FOR_EACH_DEFINED_FUNCTION (node) |
e2c9111c | 188 | { |
d52f5295 | 189 | enum availability avail = node->get_availability (); |
e2c9111c | 190 | |
d52f5295 | 191 | if (avail > AVAIL_INTERPOSABLE |
45272fd2 | 192 | || avail == AVAIL_INTERPOSABLE) |
e2c9111c JH |
193 | { |
194 | /* Reuse the info if it is already there. */ | |
67348ccc | 195 | struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux; |
e2c9111c JH |
196 | if (!info) |
197 | info = XCNEW (struct ipa_dfs_info); | |
198 | info->new_node = true; | |
199 | info->on_stack = false; | |
200 | info->next_cycle = NULL; | |
67348ccc | 201 | node->aux = info; |
b8698a0f | 202 | |
e2c9111c | 203 | splay_tree_insert (env.nodes_marked_new, |
4325656f | 204 | (splay_tree_key)node->get_uid (), |
e2c9111c | 205 | (splay_tree_value)node); |
b8698a0f L |
206 | } |
207 | else | |
67348ccc | 208 | node->aux = NULL; |
e2c9111c | 209 | } |
ea900239 DB |
210 | result = splay_tree_min (env.nodes_marked_new); |
211 | while (result) | |
212 | { | |
213 | node = (struct cgraph_node *)result->value; | |
2505c5ed | 214 | searchc (&env, node, ignore_edge); |
ea900239 DB |
215 | result = splay_tree_min (env.nodes_marked_new); |
216 | } | |
217 | splay_tree_delete (env.nodes_marked_new); | |
218 | free (env.stack); | |
219 | ||
220 | return env.order_pos; | |
221 | } | |
222 | ||
af8bca3c MJ |
223 | /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call |
224 | graph nodes. */ | |
225 | ||
226 | void | |
227 | ipa_free_postorder_info (void) | |
228 | { | |
229 | struct cgraph_node *node; | |
65c70e6b | 230 | FOR_EACH_DEFINED_FUNCTION (node) |
af8bca3c MJ |
231 | { |
232 | /* Get rid of the aux information. */ | |
67348ccc | 233 | if (node->aux) |
af8bca3c | 234 | { |
67348ccc DM |
235 | free (node->aux); |
236 | node->aux = NULL; | |
af8bca3c MJ |
237 | } |
238 | } | |
239 | } | |
240 | ||
df92c640 SB |
241 | /* Get the set of nodes for the cycle in the reduced call graph starting |
242 | from NODE. */ | |
243 | ||
d52f5295 | 244 | vec<cgraph_node *> |
df92c640 SB |
245 | ipa_get_nodes_in_cycle (struct cgraph_node *node) |
246 | { | |
d52f5295 | 247 | vec<cgraph_node *> v = vNULL; |
df92c640 SB |
248 | struct ipa_dfs_info *node_dfs_info; |
249 | while (node) | |
250 | { | |
9771b263 | 251 | v.safe_push (node); |
67348ccc | 252 | node_dfs_info = (struct ipa_dfs_info *) node->aux; |
df92c640 SB |
253 | node = node_dfs_info->next_cycle; |
254 | } | |
255 | return v; | |
256 | } | |
257 | ||
4cb13597 MJ |
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 | ipa_edge_within_scc (struct cgraph_edge *cs) | |
263 | { | |
67348ccc | 264 | struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux; |
4cb13597 | 265 | struct ipa_dfs_info *callee_dfs; |
d52f5295 | 266 | struct cgraph_node *callee = cs->callee->function_symbol (); |
4cb13597 | 267 | |
67348ccc | 268 | callee_dfs = (struct ipa_dfs_info *) callee->aux; |
4cb13597 MJ |
269 | return (caller_dfs |
270 | && callee_dfs | |
271 | && caller_dfs->scc_no == callee_dfs->scc_no); | |
272 | } | |
273 | ||
8775a18b JH |
274 | struct postorder_stack |
275 | { | |
276 | struct cgraph_node *node; | |
277 | struct cgraph_edge *edge; | |
278 | int ref; | |
279 | }; | |
280 | ||
af8bca3c | 281 | /* Fill array order with all nodes with output flag set in the reverse |
39e2db00 JH |
282 | topological order. Return the number of elements in the array. |
283 | FIXME: While walking, consider aliases, too. */ | |
af8bca3c MJ |
284 | |
285 | int | |
286 | ipa_reverse_postorder (struct cgraph_node **order) | |
287 | { | |
288 | struct cgraph_node *node, *node2; | |
289 | int stack_size = 0; | |
290 | int order_pos = 0; | |
8775a18b | 291 | struct cgraph_edge *edge; |
af8bca3c | 292 | int pass; |
d122681a | 293 | struct ipa_ref *ref = NULL; |
af8bca3c | 294 | |
8775a18b | 295 | struct postorder_stack *stack = |
3dafb85c | 296 | XCNEWVEC (struct postorder_stack, symtab->cgraph_count); |
af8bca3c MJ |
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. */ | |
65c70e6b | 302 | FOR_EACH_FUNCTION (node) |
67348ccc | 303 | node->aux = NULL; |
af8bca3c | 304 | for (pass = 0; pass < 2; pass++) |
65c70e6b | 305 | FOR_EACH_FUNCTION (node) |
67348ccc | 306 | if (!node->aux |
af8bca3c | 307 | && (pass |
67348ccc | 308 | || (!node->address_taken |
a62bfab5 | 309 | && !node->inlined_to |
67f3791f | 310 | && !node->alias && !node->thunk |
d52f5295 | 311 | && !node->only_called_directly_p ()))) |
af8bca3c | 312 | { |
8775a18b JH |
313 | stack_size = 0; |
314 | stack[stack_size].node = node; | |
315 | stack[stack_size].edge = node->callers; | |
316 | stack[stack_size].ref = 0; | |
67348ccc | 317 | node->aux = (void *)(size_t)1; |
8775a18b | 318 | while (stack_size >= 0) |
af8bca3c | 319 | { |
8775a18b | 320 | while (true) |
af8bca3c | 321 | { |
8775a18b JH |
322 | node2 = NULL; |
323 | while (stack[stack_size].edge && !node2) | |
af8bca3c | 324 | { |
8775a18b | 325 | edge = stack[stack_size].edge; |
af8bca3c | 326 | node2 = edge->caller; |
8775a18b | 327 | stack[stack_size].edge = edge->next_caller; |
8775a18b | 328 | } |
d122681a | 329 | for (; stack[stack_size].node->iterate_referring ( |
8775a18b JH |
330 | stack[stack_size].ref, |
331 | ref) && !node2; | |
332 | stack[stack_size].ref++) | |
333 | { | |
334 | if (ref->use == IPA_REF_ALIAS) | |
d122681a | 335 | node2 = dyn_cast <cgraph_node *> (ref->referring); |
8775a18b JH |
336 | } |
337 | if (!node2) | |
338 | break; | |
67348ccc | 339 | if (!node2->aux) |
8775a18b JH |
340 | { |
341 | stack[++stack_size].node = node2; | |
342 | stack[stack_size].edge = node2->callers; | |
343 | stack[stack_size].ref = 0; | |
67348ccc | 344 | node2->aux = (void *)(size_t)1; |
af8bca3c MJ |
345 | } |
346 | } | |
8775a18b | 347 | order[order_pos++] = stack[stack_size--].node; |
af8bca3c MJ |
348 | } |
349 | } | |
350 | free (stack); | |
65c70e6b | 351 | FOR_EACH_FUNCTION (node) |
67348ccc | 352 | node->aux = NULL; |
af8bca3c MJ |
353 | return order_pos; |
354 | } | |
355 | ||
356 | ||
ea900239 DB |
357 | |
358 | /* Given a memory reference T, will return the variable at the bottom | |
073a8998 | 359 | of the access. Unlike get_base_address, this will recurse through |
ea900239 DB |
360 | INDIRECT_REFS. */ |
361 | ||
362 | tree | |
363 | get_base_var (tree t) | |
364 | { | |
b8698a0f | 365 | while (!SSA_VAR_P (t) |
ea900239 DB |
366 | && (!CONSTANT_CLASS_P (t)) |
367 | && TREE_CODE (t) != LABEL_DECL | |
368 | && TREE_CODE (t) != FUNCTION_DECL | |
3baf459d DN |
369 | && TREE_CODE (t) != CONST_DECL |
370 | && TREE_CODE (t) != CONSTRUCTOR) | |
ea900239 DB |
371 | { |
372 | t = TREE_OPERAND (t, 0); | |
373 | } | |
374 | return t; | |
b8698a0f | 375 | } |
ea900239 | 376 | |
8ae4d429 JH |
377 | /* Scale function of calls in NODE by ratio ORIG_COUNT/NODE->count. */ |
378 | ||
379 | void | |
380 | scale_ipa_profile_for_fn (struct cgraph_node *node, profile_count orig_count) | |
381 | { | |
382 | profile_count to = node->count; | |
383 | profile_count::adjust_for_ipa_scaling (&to, &orig_count); | |
384 | struct cgraph_edge *e; | |
385 | ||
386 | for (e = node->callees; e; e = e->next_callee) | |
387 | e->count = e->count.apply_scale (to, orig_count); | |
388 | for (e = node->indirect_calls; e; e = e->next_callee) | |
389 | e->count = e->count.apply_scale (to, orig_count); | |
390 | } | |
1cb1a99f | 391 | |
4843f032 | 392 | /* SRC and DST are going to be merged. Take SRC's profile and merge it into |
b730d1c9 JH |
393 | DST so it is not going to be lost. Possibly destroy SRC's body on the way |
394 | unless PRESERVE_BODY is set. */ | |
4843f032 JH |
395 | |
396 | void | |
397 | ipa_merge_profiles (struct cgraph_node *dst, | |
b730d1c9 JH |
398 | struct cgraph_node *src, |
399 | bool preserve_body) | |
4843f032 | 400 | { |
67348ccc | 401 | tree oldsrcdecl = src->decl; |
4843f032 JH |
402 | struct function *srccfun, *dstcfun; |
403 | bool match = true; | |
eb081fd0 | 404 | bool copy_counts = false; |
4843f032 | 405 | |
67348ccc DM |
406 | if (!src->definition |
407 | || !dst->definition) | |
4843f032 | 408 | return; |
959b8c82 | 409 | |
4843f032 JH |
410 | if (src->frequency < dst->frequency) |
411 | src->frequency = dst->frequency; | |
9cec31f4 ML |
412 | |
413 | /* Time profiles are merged. */ | |
414 | if (dst->tp_first_run > src->tp_first_run && src->tp_first_run) | |
415 | dst->tp_first_run = src->tp_first_run; | |
416 | ||
fd29c024 ML |
417 | if (src->profile_id && !dst->profile_id) |
418 | dst->profile_id = src->profile_id; | |
cb90235d | 419 | |
6263c29d JH |
420 | /* Merging zero profile to dst is no-op. */ |
421 | if (src->count.ipa () == profile_count::zero ()) | |
422 | return; | |
423 | ||
3995f3a2 JH |
424 | /* FIXME when we merge in unknown profile, we ought to set counts as |
425 | unsafe. */ | |
1bad9c18 JH |
426 | if (!src->count.initialized_p () |
427 | || !(src->count.ipa () == src->count)) | |
4843f032 | 428 | return; |
959b8c82 JH |
429 | profile_count orig_count = dst->count; |
430 | ||
eb081fd0 JH |
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 | if ((dst->count.ipa ().nonzero_p () | |
436 | || src->count.ipa ().nonzero_p ()) | |
437 | && dst->count.ipa ().initialized_p () | |
438 | && src->count.ipa ().initialized_p ()) | |
439 | dst->count = dst->count.ipa () + src->count.ipa (); | |
440 | else if (dst->count.ipa ().initialized_p ()) | |
441 | ; | |
442 | else if (src->count.ipa ().initialized_p ()) | |
443 | { | |
444 | copy_counts = true; | |
445 | dst->count = src->count.ipa (); | |
446 | } | |
447 | ||
448 | /* If no updating needed return early. */ | |
449 | if (dst->count == orig_count) | |
450 | return; | |
4843f032 | 451 | |
e44deb43 JH |
452 | if (symtab->dump_file) |
453 | { | |
454 | fprintf (symtab->dump_file, "Merging profiles of %s count:", | |
455 | src->dump_name ()); | |
456 | src->count.dump (symtab->dump_file); | |
457 | fprintf (symtab->dump_file, " to %s count:", | |
458 | dst->dump_name ()); | |
459 | orig_count.dump (symtab->dump_file); | |
460 | fprintf (symtab->dump_file, " resulting count:"); | |
461 | dst->count.dump (symtab->dump_file); | |
462 | fprintf (symtab->dump_file, "\n"); | |
463 | } | |
464 | ||
8ae4d429 | 465 | /* First handle functions with no gimple body. */ |
67f3791f JH |
466 | if (dst->thunk || dst->alias |
467 | || src->thunk || src->alias) | |
8ae4d429 JH |
468 | { |
469 | scale_ipa_profile_for_fn (dst, orig_count); | |
470 | return; | |
471 | } | |
472 | ||
4843f032 JH |
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. */ | |
67348ccc | 477 | if (src->decl == dst->decl) |
4843f032 | 478 | { |
4843f032 JH |
479 | struct lto_in_decl_state temp; |
480 | 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. */ | |
67348ccc | 484 | temp.fn_decl = src->decl; |
907dadbd TS |
485 | lto_in_decl_state **slot |
486 | = src->lto_file_data->function_decl_states->find_slot (&temp, | |
487 | NO_INSERT); | |
488 | state = *slot; | |
489 | src->lto_file_data->function_decl_states->clear_slot (slot); | |
4843f032 JH |
490 | gcc_assert (state); |
491 | ||
492 | /* Duplicate the decl and be sure it does not link into body of DST. */ | |
67348ccc DM |
493 | src->decl = copy_node (src->decl); |
494 | DECL_STRUCT_FUNCTION (src->decl) = NULL; | |
495 | DECL_ARGUMENTS (src->decl) = NULL; | |
496 | DECL_INITIAL (src->decl) = NULL; | |
497 | DECL_RESULT (src->decl) = NULL; | |
4843f032 JH |
498 | |
499 | /* Associate the decl state with new declaration, so LTO streamer | |
500 | can look it up. */ | |
67348ccc | 501 | state->fn_decl = src->decl; |
907dadbd TS |
502 | slot |
503 | = src->lto_file_data->function_decl_states->find_slot (state, INSERT); | |
4843f032 JH |
504 | gcc_assert (!*slot); |
505 | *slot = state; | |
506 | } | |
e3bde69a JH |
507 | src->get_untransformed_body (); |
508 | dst->get_untransformed_body (); | |
67348ccc DM |
509 | srccfun = DECL_STRUCT_FUNCTION (src->decl); |
510 | dstcfun = DECL_STRUCT_FUNCTION (dst->decl); | |
0cae8d31 DM |
511 | if (n_basic_blocks_for_fn (srccfun) |
512 | != n_basic_blocks_for_fn (dstcfun)) | |
4843f032 | 513 | { |
3dafb85c ML |
514 | if (symtab->dump_file) |
515 | fprintf (symtab->dump_file, | |
4843f032 JH |
516 | "Giving up; number of basic block mismatch.\n"); |
517 | match = false; | |
518 | } | |
3986e690 DM |
519 | else if (last_basic_block_for_fn (srccfun) |
520 | != last_basic_block_for_fn (dstcfun)) | |
4843f032 | 521 | { |
3dafb85c ML |
522 | if (symtab->dump_file) |
523 | fprintf (symtab->dump_file, | |
4843f032 JH |
524 | "Giving up; last block mismatch.\n"); |
525 | match = false; | |
526 | } | |
527 | else | |
528 | { | |
529 | basic_block srcbb, dstbb; | |
e44deb43 | 530 | struct cgraph_edge *e, *e2; |
4843f032 | 531 | |
e44deb43 JH |
532 | for (e = dst->callees, e2 = src->callees; e && e2 && match; |
533 | e2 = e2->next_callee, e = e->next_callee) | |
4843f032 | 534 | { |
e44deb43 JH |
535 | if (gimple_bb (e->call_stmt)->index |
536 | != gimple_bb (e2->call_stmt)->index) | |
4843f032 | 537 | { |
3dafb85c ML |
538 | if (symtab->dump_file) |
539 | fprintf (symtab->dump_file, | |
e44deb43 | 540 | "Giving up; call stmt mismatch.\n"); |
4843f032 | 541 | match = false; |
4843f032 | 542 | } |
e44deb43 JH |
543 | } |
544 | if (e || e2) | |
545 | { | |
546 | if (symtab->dump_file) | |
547 | fprintf (symtab->dump_file, | |
548 | "Giving up; number of calls differs.\n"); | |
549 | match = false; | |
550 | } | |
551 | for (e = dst->indirect_calls, e2 = src->indirect_calls; e && e2 && match; | |
552 | e2 = e2->next_callee, e = e->next_callee) | |
553 | { | |
554 | if (gimple_bb (e->call_stmt)->index | |
555 | != gimple_bb (e2->call_stmt)->index) | |
4843f032 | 556 | { |
3dafb85c ML |
557 | if (symtab->dump_file) |
558 | fprintf (symtab->dump_file, | |
e44deb43 | 559 | "Giving up; indirect call stmt mismatch.\n"); |
4843f032 | 560 | match = false; |
4843f032 JH |
561 | } |
562 | } | |
e44deb43 JH |
563 | if (e || e2) |
564 | { | |
565 | if (symtab->dump_file) | |
566 | fprintf (symtab->dump_file, | |
567 | "Giving up; number of indirect calls differs.\n"); | |
568 | match=false; | |
569 | } | |
570 | ||
571 | if (match) | |
572 | FOR_ALL_BB_FN (srcbb, srccfun) | |
573 | { | |
574 | unsigned int i; | |
575 | ||
576 | dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index); | |
577 | if (dstbb == NULL) | |
578 | { | |
579 | if (symtab->dump_file) | |
580 | fprintf (symtab->dump_file, | |
581 | "No matching block for bb %i.\n", | |
582 | srcbb->index); | |
583 | match = false; | |
584 | break; | |
585 | } | |
586 | if (EDGE_COUNT (srcbb->succs) != EDGE_COUNT (dstbb->succs)) | |
587 | { | |
588 | if (symtab->dump_file) | |
589 | fprintf (symtab->dump_file, | |
590 | "Edge count mismatch for bb %i.\n", | |
591 | srcbb->index); | |
592 | match = false; | |
593 | break; | |
594 | } | |
595 | for (i = 0; i < EDGE_COUNT (srcbb->succs); i++) | |
596 | { | |
597 | edge srce = EDGE_SUCC (srcbb, i); | |
598 | edge dste = EDGE_SUCC (dstbb, i); | |
599 | if (srce->dest->index != dste->dest->index) | |
600 | { | |
601 | if (symtab->dump_file) | |
602 | fprintf (symtab->dump_file, | |
603 | "Succ edge mismatch for bb %i.\n", | |
604 | srce->dest->index); | |
605 | match = false; | |
606 | break; | |
607 | } | |
608 | } | |
609 | } | |
4843f032 JH |
610 | } |
611 | if (match) | |
612 | { | |
befb1f36 | 613 | struct cgraph_edge *e, *e2; |
4843f032 JH |
614 | basic_block srcbb, dstbb; |
615 | ||
eb081fd0 JH |
616 | /* Function and global profile may be out of sync. First scale it same |
617 | way as fixup_cfg would. */ | |
618 | profile_count srcnum = src->count; | |
619 | profile_count srcden = ENTRY_BLOCK_PTR_FOR_FN (srccfun)->count; | |
620 | bool srcscale = srcnum.initialized_p () && !(srcnum == srcden); | |
621 | profile_count dstnum = orig_count; | |
622 | profile_count dstden = ENTRY_BLOCK_PTR_FOR_FN (dstcfun)->count; | |
623 | bool dstscale = !copy_counts | |
624 | && dstnum.initialized_p () && !(dstnum == dstden); | |
625 | ||
4843f032 JH |
626 | /* TODO: merge also statement histograms. */ |
627 | FOR_ALL_BB_FN (srcbb, srccfun) | |
628 | { | |
629 | unsigned int i; | |
630 | ||
bbd79259 | 631 | dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index); |
e7a74006 | 632 | |
eb081fd0 JH |
633 | profile_count srccount = srcbb->count; |
634 | if (srcscale) | |
635 | srccount = srccount.apply_scale (srcnum, srcden); | |
636 | if (dstscale) | |
637 | dstbb->count = dstbb->count.apply_scale (dstnum, dstden); | |
638 | ||
639 | if (copy_counts) | |
4843f032 | 640 | { |
eb081fd0 | 641 | dstbb->count = srccount; |
ef30ab83 JH |
642 | for (i = 0; i < EDGE_COUNT (srcbb->succs); i++) |
643 | { | |
644 | edge srce = EDGE_SUCC (srcbb, i); | |
645 | edge dste = EDGE_SUCC (dstbb, i); | |
646 | if (srce->probability.initialized_p ()) | |
647 | dste->probability = srce->probability; | |
648 | } | |
649 | } | |
eb081fd0 | 650 | else |
ef30ab83 JH |
651 | { |
652 | for (i = 0; i < EDGE_COUNT (srcbb->succs); i++) | |
653 | { | |
654 | edge srce = EDGE_SUCC (srcbb, i); | |
655 | edge dste = EDGE_SUCC (dstbb, i); | |
043a6fcb ST |
656 | profile_count sum = |
657 | dstbb->count.ipa () + srccount.ipa (); | |
658 | if (sum.nonzero_p ()) | |
659 | dste->probability = | |
660 | dste->probability * dstbb->count.ipa ().probability_in | |
661 | (sum) | |
662 | + srce->probability * srcbb->count.ipa ().probability_in | |
663 | (sum); | |
ef30ab83 | 664 | } |
eb081fd0 | 665 | dstbb->count = dstbb->count.ipa () + srccount.ipa (); |
4843f032 JH |
666 | } |
667 | } | |
668 | push_cfun (dstcfun); | |
fc06ae0d | 669 | update_max_bb_count (); |
4843f032 JH |
670 | compute_function_frequency (); |
671 | pop_cfun (); | |
672 | for (e = dst->callees; e; e = e->next_callee) | |
673 | { | |
befb1f36 JH |
674 | if (e->speculative) |
675 | continue; | |
1bad9c18 | 676 | e->count = gimple_bb (e->call_stmt)->count; |
4843f032 | 677 | } |
befb1f36 JH |
678 | for (e = dst->indirect_calls, e2 = src->indirect_calls; e; |
679 | e2 = (e2 ? e2->next_callee : NULL), e = e->next_callee) | |
4843f032 | 680 | { |
845bb366 | 681 | if (!e->speculative && !e2->speculative) |
e44deb43 | 682 | { |
845bb366 JH |
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 | e->count = gimple_bb (e->call_stmt)->count; | |
687 | continue; | |
e44deb43 | 688 | } |
845bb366 JH |
689 | |
690 | /* When copying just remove all speuclations on dst and then copy | |
691 | one from src. */ | |
692 | if (copy_counts) | |
e44deb43 | 693 | { |
845bb366 JH |
694 | while (e->speculative) |
695 | cgraph_edge::resolve_speculation (e, NULL); | |
696 | e->count = gimple_bb (e->call_stmt)->count; | |
697 | if (e2->speculative) | |
e44deb43 | 698 | { |
845bb366 JH |
699 | for (cgraph_edge *e3 = e2->first_speculative_call_target (); |
700 | e3; | |
701 | e3 = e3->next_speculative_call_target ()) | |
f1ba88b1 | 702 | { |
845bb366 JH |
703 | cgraph_edge *ns; |
704 | ns = e->make_speculative | |
705 | (dyn_cast <cgraph_node *> | |
706 | (e3->speculative_call_target_ref ()->referred), | |
707 | e3->count, e3->speculative_id); | |
708 | /* Target may differ from ref (for example it may be | |
709 | redirected to local alias. */ | |
710 | ns->redirect_callee (e3->callee); | |
f1ba88b1 | 711 | } |
e44deb43 | 712 | } |
845bb366 | 713 | continue; |
e44deb43 JH |
714 | } |
715 | ||
845bb366 JH |
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 | int max_spec = 0; | |
720 | for (cgraph_edge *e3 = e->first_speculative_call_target (); | |
721 | e3; | |
722 | e3 = e3->next_speculative_call_target ()) | |
723 | if (e3->speculative_id > max_spec) | |
724 | max_spec = e3->speculative_id; | |
725 | for (cgraph_edge *e3 = e2->first_speculative_call_target (); | |
726 | e3; | |
727 | e3 = e3->next_speculative_call_target ()) | |
befb1f36 | 728 | { |
845bb366 JH |
729 | cgraph_edge *te |
730 | = e->speculative_call_for_target | |
731 | (dyn_cast <cgraph_node *> | |
732 | (e3->speculative_call_target_ref ()->referred)); | |
733 | if (te) | |
734 | te->count = te->count + e3->count; | |
735 | else | |
befb1f36 | 736 | { |
845bb366 JH |
737 | e->count = e->count + e3->count; |
738 | cgraph_edge *ns; | |
739 | ns = e->make_speculative | |
740 | (dyn_cast <cgraph_node *> | |
741 | (e3->speculative_call_target_ref () | |
742 | ->referred), | |
743 | e3->count, | |
744 | e3->speculative_id + max_spec + 1); | |
745 | /* Target may differ from ref (for example it may be | |
746 | redirected to local alias. */ | |
747 | ns->redirect_callee (e3->callee); | |
befb1f36 | 748 | } |
befb1f36 | 749 | } |
4843f032 | 750 | } |
b730d1c9 JH |
751 | if (!preserve_body) |
752 | src->release_body (); | |
61e8dc4b | 753 | /* Update summary. */ |
959b8c82 JH |
754 | 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 | |
8ae4d429 | 759 | scale_ipa_profile_for_fn (dst, orig_count); |
67348ccc | 760 | src->decl = oldsrcdecl; |
4843f032 JH |
761 | } |
762 | ||
845bb366 JH |
763 | /* Return true if call to DEST is known to be self-recusive |
764 | call withing FUNC. */ | |
fc11f321 JH |
765 | |
766 | bool | |
767 | recursive_call_p (tree func, tree dest) | |
768 | { | |
d52f5295 ML |
769 | struct cgraph_node *dest_node = cgraph_node::get_create (dest); |
770 | struct cgraph_node *cnode = cgraph_node::get_create (func); | |
acbbac04 JH |
771 | ipa_ref *alias; |
772 | enum availability avail; | |
773 | ||
774 | gcc_assert (!cnode->alias); | |
775 | if (cnode != dest_node->ultimate_alias_target (&avail)) | |
776 | return false; | |
777 | if (avail >= AVAIL_AVAILABLE) | |
778 | return true; | |
779 | 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 | FOR_EACH_ALIAS (cnode, alias) | |
784 | if (!dest_node->semantically_equivalent_p (alias->referring)) | |
785 | return false; | |
786 | return true; | |
fc11f321 | 787 | } |
b1f30bf4 JH |
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 | stmt_may_terminate_function_p (function *fun, gimple *stmt, bool assume_return_or_eh) | |
795 | { | |
796 | if (stmt_can_throw_external (fun, stmt)) | |
797 | return true; | |
da3aca03 JH |
798 | if (assume_return_or_eh) |
799 | return false; | |
b1f30bf4 JH |
800 | gasm *astmt = dyn_cast <gasm *> (stmt); |
801 | if (astmt && gimple_asm_volatile_p (astmt)) | |
802 | return true; | |
b1f30bf4 JH |
803 | if (gimple_could_trap_p (stmt)) |
804 | return true; | |
805 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
806 | { | |
807 | int flags = gimple_call_flags (call); | |
808 | if (flags & (ECF_PURE | ECF_CONST) && ! (flags & ECF_LOOPING_CONST_OR_PURE)) | |
809 | return false; | |
810 | modref_summary *s = get_modref_function_summary (call, NULL); | |
811 | 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 | find_always_executed_bbs (function *fun, bool assume_return_or_eh) | |
830 | { | |
831 | auto_vec<basic_block, 20> stack; | |
832 | auto_vec<basic_block, 20> terminating_bbs; | |
833 | hash_set<basic_block> visited; | |
da3aca03 | 834 | hash_set<basic_block> terminating_bbs_set; |
b1f30bf4 JH |
835 | edge e; |
836 | edge_iterator ei; | |
da3aca03 JH |
837 | int flags = flags_from_decl_or_type (fun->decl); |
838 | /* PUre and const functions always return. */ | |
839 | assume_return_or_eh |= (flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE); | |
840 | if (!assume_return_or_eh) | |
841 | mark_dfs_back_edges (fun); | |
b1f30bf4 JH |
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 | stack.safe_push (ENTRY_BLOCK_PTR_FOR_FN (fun)); | |
847 | while (!stack.is_empty ()) | |
848 | { | |
849 | basic_block bb = stack.pop (); | |
850 | bool found = false, found_exit = false; | |
da3aca03 JH |
851 | if (bb->index == EXIT_BLOCK) |
852 | continue; | |
b1f30bf4 JH |
853 | FOR_EACH_EDGE (e, ei, bb->succs) |
854 | { | |
855 | if (e->dest == EXIT_BLOCK_PTR_FOR_FN (fun)) | |
856 | { | |
857 | found_exit = true; | |
858 | break; | |
859 | } | |
860 | /* Watch for infinite loops. */ | |
da3aca03 JH |
861 | if (!found |
862 | && !assume_return_or_eh && (e->flags & EDGE_DFS_BACK)) | |
863 | { | |
864 | if (!dom_info_available_p (CDI_DOMINATORS)) | |
865 | 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 | if (e->dest->loop_father->header != e->dest | |
874 | || !dominated_by_p (CDI_DOMINATORS, bb, e->dest)) | |
875 | found = true; | |
876 | else if (!finite_loop_p (e->dest->loop_father)) | |
877 | found = true; | |
878 | } | |
b1f30bf4 | 879 | } |
da3aca03 JH |
880 | if (!assume_return_or_eh |
881 | && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP))) | |
882 | found = true; | |
b1f30bf4 JH |
883 | for (gimple_stmt_iterator si = gsi_start_nondebug_after_labels_bb (bb); |
884 | !gsi_end_p (si) && !found; gsi_next_nondebug (&si)) | |
885 | if (stmt_may_terminate_function_p (fun, gsi_stmt (si), assume_return_or_eh)) | |
886 | { | |
887 | found = true; | |
888 | break; | |
889 | } | |
890 | if (found) | |
891 | { | |
892 | visited.add (EXIT_BLOCK_PTR_FOR_FN (fun)); | |
893 | if (!found_exit) | |
da3aca03 JH |
894 | { |
895 | terminating_bbs.safe_push (bb); | |
896 | terminating_bbs_set.add (bb); | |
897 | } | |
b1f30bf4 JH |
898 | } |
899 | else | |
900 | FOR_EACH_EDGE (e, ei, bb->succs) | |
901 | if (!visited.add (e->dest)) | |
902 | 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 | bitmap ret = BITMAP_ALLOC (NULL); | |
910 | /* A degenerated case when there is no path to exit. */ | |
da3aca03 | 911 | if (!visited.contains (EXIT_BLOCK_PTR_FOR_FN (fun))) |
b1f30bf4 JH |
912 | { |
913 | bitmap_set_bit (ret, | |
914 | single_succ_edge | |
915 | (ENTRY_BLOCK_PTR_FOR_FN (fun))->dest->index); | |
916 | return ret; | |
917 | } | |
918 | ||
919 | struct astate | |
920 | { | |
921 | unsigned int dfs_preorder; | |
922 | unsigned int dfs_postorder; | |
923 | ||
924 | unsigned int low, high; | |
925 | }; | |
926 | ||
927 | struct worklist | |
928 | { | |
929 | basic_block bb; | |
930 | astate *cstate; | |
931 | }; | |
932 | ||
933 | struct obstack state_obstack; | |
934 | gcc_obstack_init (&state_obstack); | |
935 | hash_map<basic_block, astate *> state; | |
936 | auto_vec<worklist, 32> worklist_vec; | |
937 | 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 | worklist we = {EXIT_BLOCK_PTR_FOR_FN (fun), NULL}; | |
952 | worklist_vec.safe_push (we); | |
953 | while (!worklist_vec.is_empty ()) | |
954 | { | |
955 | worklist &w = worklist_vec.last (); | |
956 | basic_block bb = w.bb; | |
957 | astate *cstate = w.cstate; | |
958 | ||
959 | if (!cstate) | |
960 | { | |
961 | astate **slot = &state.get_or_insert (bb); | |
962 | ||
963 | cstate = *slot; | |
964 | /* Already processed by DFS? */ | |
965 | if (cstate) | |
966 | { | |
967 | worklist_vec.pop (); | |
968 | continue; | |
969 | } | |
970 | /* DFS is visiting BB for first time. */ | |
971 | *slot = cstate = XOBNEW (&state_obstack, struct astate); | |
da3aca03 | 972 | cstate->low = cstate->high = cstate->dfs_preorder = next_dfs_num++; |
b1f30bf4 JH |
973 | w.cstate = cstate; |
974 | /* Exit block is special; process all fake edges we identified. */ | |
975 | if (bb == EXIT_BLOCK_PTR_FOR_FN (fun)) | |
976 | for (basic_block bb2 : terminating_bbs) | |
977 | { | |
978 | worklist we = {bb2, NULL}; | |
979 | worklist_vec.safe_push (we); | |
980 | } | |
981 | FOR_EACH_EDGE (e, ei, bb->preds) | |
982 | if (visited.contains (e->src)) | |
983 | { | |
984 | worklist we = {e->src, NULL}; | |
985 | worklist_vec.safe_push (we); | |
986 | } | |
987 | /* Keep BB on worklist so we process it last time. */ | |
988 | continue; | |
989 | } | |
990 | /* We are finished with processing reachable BBs, see if we have articulation. */ | |
991 | worklist_vec.pop (); | |
992 | cstate->high = cstate->dfs_postorder = next_dfs_num++; | |
993 | stack.safe_push (bb); | |
994 | } | |
995 | /* This is the final postorder walk. Determine low and high values and mark | |
996 | always executed blocks. */ | |
997 | for (basic_block bb : stack) | |
998 | { | |
999 | astate *cstate = *state.get (bb); | |
1000 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1001 | { | |
1002 | 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 | if (!cstate2) | |
1006 | { | |
1007 | if (e->src != ENTRY_BLOCK_PTR_FOR_FN (fun)) | |
da3aca03 | 1008 | cstate->low = 0; |
b1f30bf4 JH |
1009 | continue; |
1010 | } | |
1011 | cstate->low = MIN (cstate->low, (*cstate2)->low); | |
1012 | cstate->high = MAX (cstate->high, (*cstate2)->high); | |
1013 | } | |
da3aca03 JH |
1014 | if (dump_file && (dump_flags & TDF_DETAILS) && bb != EXIT_BLOCK_PTR_FOR_FN (fun)) |
1015 | fprintf (dump_file, "BB %i %s preorder %i posorder %i low %i high %i\n", | |
1016 | bb->index, terminating_bbs_set.contains (bb) ? "(terminating)": "", | |
1017 | cstate->dfs_preorder, cstate->dfs_postorder, cstate->low, cstate->high); | |
b1f30bf4 JH |
1018 | if (cstate->low == cstate->dfs_preorder && cstate->high == cstate->dfs_postorder |
1019 | && bb != EXIT_BLOCK_PTR_FOR_FN (fun)) | |
1020 | bitmap_set_bit (ret, bb->index); | |
da3aca03 JH |
1021 | if (terminating_bbs_set.contains (bb)) |
1022 | cstate->low = 0; | |
1023 | else | |
1024 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1025 | { | |
1026 | astate **cstate2 = state.get (e->dest); | |
1027 | if (!cstate2) | |
1028 | continue; | |
1029 | cstate->low = MIN (cstate->low, (*cstate2)->low); | |
1030 | cstate->high = MAX (cstate->high, (*cstate2)->high); | |
1031 | } | |
1032 | } | |
b1f30bf4 | 1033 | obstack_free (&state_obstack, NULL); |
da3aca03 JH |
1034 | if (dump_file) |
1035 | { | |
1036 | fprintf (dump_file, "Always executed bbbs %s: ", | |
1037 | assume_return_or_eh ? "(assuming return or EH)": ""); | |
1038 | bitmap_print (dump_file, ret, "", "\n"); | |
1039 | } | |
b1f30bf4 JH |
1040 | |
1041 | return ret; | |
1042 | } |