Branch data Line data Source code
1 : : /* Hooks for cfg representation specific functions.
2 : : Copyright (C) 2003-2025 Free Software Foundation, Inc.
3 : : Contributed by Sebastian Pop <s.pop@laposte.net>
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License 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 "rtl.h"
26 : : #include "cfghooks.h"
27 : : #include "timevar.h"
28 : : #include "pretty-print.h"
29 : : #include "diagnostic-core.h"
30 : : #include "dumpfile.h"
31 : : #include "cfganal.h"
32 : : #include "tree.h"
33 : : #include "tree-ssa.h"
34 : : #include "cfgloop.h"
35 : : #include "sreal.h"
36 : : #include "profile.h"
37 : :
38 : : /* Disable warnings about missing quoting in GCC diagnostics. */
39 : : #if __GNUC__ >= 10
40 : : # pragma GCC diagnostic push
41 : : # pragma GCC diagnostic ignored "-Wformat-diag"
42 : : #endif
43 : :
44 : : /* A pointer to one of the hooks containers. */
45 : : static struct cfg_hooks *cfg_hooks;
46 : :
47 : : /* Initialization of functions specific to the rtl IR. */
48 : : void
49 : 3975894 : rtl_register_cfg_hooks (void)
50 : : {
51 : 3975894 : cfg_hooks = &rtl_cfg_hooks;
52 : 3975894 : }
53 : :
54 : : /* Initialization of functions specific to the rtl IR. */
55 : : void
56 : 2506626 : cfg_layout_rtl_register_cfg_hooks (void)
57 : : {
58 : 2506626 : cfg_hooks = &cfg_layout_rtl_cfg_hooks;
59 : 2506626 : }
60 : :
61 : : /* Initialization of functions specific to the tree IR. */
62 : :
63 : : void
64 : 14611265 : gimple_register_cfg_hooks (void)
65 : : {
66 : 14611265 : cfg_hooks = &gimple_cfg_hooks;
67 : 14611265 : }
68 : :
69 : : struct cfg_hooks
70 : 814 : get_cfg_hooks (void)
71 : : {
72 : 814 : return *cfg_hooks;
73 : : }
74 : :
75 : : void
76 : 1628 : set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
77 : : {
78 : 1628 : *cfg_hooks = new_cfg_hooks;
79 : 1628 : }
80 : :
81 : : /* Returns current ir type. */
82 : :
83 : : enum ir_type
84 : 271715297 : current_ir_type (void)
85 : : {
86 : 271715297 : if (cfg_hooks == &gimple_cfg_hooks)
87 : : return IR_GIMPLE;
88 : 118588608 : else if (cfg_hooks == &rtl_cfg_hooks)
89 : : return IR_RTL_CFGRTL;
90 : 40311426 : else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
91 : : return IR_RTL_CFGLAYOUT;
92 : : else
93 : 0 : gcc_unreachable ();
94 : : }
95 : :
96 : : /* Verify the CFG consistency.
97 : :
98 : : Currently it does following: checks edge and basic block list correctness
99 : : and calls into IL dependent checking then. */
100 : :
101 : : DEBUG_FUNCTION void
102 : 328731521 : verify_flow_info (void)
103 : : {
104 : 328731521 : size_t *edge_checksum;
105 : 328731521 : bool err = false;
106 : 328731521 : basic_block bb, last_bb_seen;
107 : 328731521 : basic_block *last_visited;
108 : :
109 : 328731521 : timevar_push (TV_CFG_VERIFY);
110 : 328731521 : last_visited = XCNEWVEC (basic_block, last_basic_block_for_fn (cfun));
111 : 328731521 : edge_checksum = XCNEWVEC (size_t, last_basic_block_for_fn (cfun));
112 : :
113 : : /* Check bb chain & numbers. */
114 : 328731521 : last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
115 : 3748587707 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
116 : : {
117 : 3419856186 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
118 : 3419856186 : && bb != BASIC_BLOCK_FOR_FN (cfun, bb->index))
119 : : {
120 : 0 : error ("bb %d on wrong place", bb->index);
121 : 0 : err = true;
122 : : }
123 : :
124 : 3419856186 : if (bb->prev_bb != last_bb_seen)
125 : : {
126 : 0 : error ("prev_bb of %d should be %d, not %d",
127 : : bb->index, last_bb_seen->index, bb->prev_bb->index);
128 : 0 : err = true;
129 : : }
130 : :
131 : 3419856186 : last_bb_seen = bb;
132 : : }
133 : :
134 : : /* Now check the basic blocks (boundaries etc.) */
135 : 3419856186 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
136 : : {
137 : 3091124665 : int n_fallthru = 0;
138 : 3091124665 : edge e;
139 : 3091124665 : edge_iterator ei;
140 : :
141 : 3091124665 : if (bb->loop_father != NULL && current_loops == NULL)
142 : : {
143 : 0 : error ("verify_flow_info: Block %i has loop_father, but there are no loops",
144 : : bb->index);
145 : 0 : err = true;
146 : : }
147 : 3091124665 : if (bb->loop_father == NULL && current_loops != NULL)
148 : : {
149 : 0 : error ("verify_flow_info: Block %i lacks loop_father", bb->index);
150 : 0 : err = true;
151 : : }
152 : :
153 : 3091124665 : if (!bb->count.verify ())
154 : : {
155 : 0 : error ("verify_flow_info: Wrong count of block %i", bb->index);
156 : 0 : err = true;
157 : : }
158 : : /* FIXME: Graphite and SLJL and target code still tends to produce
159 : : edges with no probability. */
160 : 3091124665 : if (profile_status_for_fn (cfun) >= PROFILE_GUESSED
161 : : && !bb->count.initialized_p () && !flag_graphite && 0)
162 : : {
163 : : error ("verify_flow_info: Missing count of block %i", bb->index);
164 : : err = true;
165 : : }
166 : :
167 : 3091124665 : if (bb->flags & ~cfun->cfg->bb_flags_allocated)
168 : : {
169 : 0 : error ("verify_flow_info: unallocated flag set on BB %d", bb->index);
170 : 0 : err = true;
171 : : }
172 : :
173 : 7471701655 : FOR_EACH_EDGE (e, ei, bb->succs)
174 : : {
175 : 4380576990 : if (last_visited [e->dest->index] == bb)
176 : : {
177 : 0 : error ("verify_flow_info: Duplicate edge %i->%i",
178 : 0 : e->src->index, e->dest->index);
179 : 0 : err = true;
180 : : }
181 : : /* FIXME: Graphite and SLJL and target code still tends to produce
182 : : edges with no probability. */
183 : 4380576990 : if (profile_status_for_fn (cfun) >= PROFILE_GUESSED
184 : : && !e->probability.initialized_p () && !flag_graphite && 0)
185 : : {
186 : : error ("Uninitialized probability of edge %i->%i", e->src->index,
187 : : e->dest->index);
188 : : err = true;
189 : : }
190 : 4380576990 : if (!e->probability.verify ())
191 : : {
192 : 0 : error ("verify_flow_info: Wrong probability of edge %i->%i",
193 : 0 : e->src->index, e->dest->index);
194 : 0 : err = true;
195 : : }
196 : :
197 : 4380576990 : last_visited [e->dest->index] = bb;
198 : :
199 : 4380576990 : if (e->flags & EDGE_FALLTHRU)
200 : 1693587614 : n_fallthru++;
201 : :
202 : 4380576990 : if (e->src != bb)
203 : : {
204 : 0 : error ("verify_flow_info: Basic block %d succ edge is corrupted",
205 : : bb->index);
206 : 0 : fprintf (stderr, "Predecessor: ");
207 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
208 : 0 : fprintf (stderr, "\nSuccessor: ");
209 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
210 : 0 : fprintf (stderr, "\n");
211 : 0 : err = true;
212 : : }
213 : :
214 : 4380576990 : if (e->flags & ~cfun->cfg->edge_flags_allocated)
215 : : {
216 : 0 : error ("verify_flow_info: unallocated edge flag set on %d -> %d",
217 : 0 : e->src->index, e->dest->index);
218 : 0 : err = true;
219 : : }
220 : :
221 : 4380576990 : edge_checksum[e->dest->index] += (size_t) e;
222 : : }
223 : 3091124665 : if (n_fallthru > 1)
224 : : {
225 : 0 : error ("wrong amount of branch edges after unconditional jump %i", bb->index);
226 : 0 : err = true;
227 : : }
228 : :
229 : 7468933354 : FOR_EACH_EDGE (e, ei, bb->preds)
230 : : {
231 : 4377808689 : if (e->dest != bb)
232 : : {
233 : 0 : error ("basic block %d pred edge is corrupted", bb->index);
234 : 0 : fputs ("Predecessor: ", stderr);
235 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
236 : 0 : fputs ("\nSuccessor: ", stderr);
237 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
238 : 0 : fputc ('\n', stderr);
239 : 0 : err = true;
240 : : }
241 : :
242 : 4377808689 : if (ei.index != e->dest_idx)
243 : : {
244 : 0 : error ("basic block %d pred edge is corrupted", bb->index);
245 : 0 : error ("its dest_idx should be %d, not %d",
246 : : ei.index, e->dest_idx);
247 : 0 : fputs ("Predecessor: ", stderr);
248 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
249 : 0 : fputs ("\nSuccessor: ", stderr);
250 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
251 : 0 : fputc ('\n', stderr);
252 : 0 : err = true;
253 : : }
254 : :
255 : 4377808689 : edge_checksum[e->dest->index] -= (size_t) e;
256 : : }
257 : : }
258 : :
259 : : /* Complete edge checksumming for ENTRY and EXIT. */
260 : 328731521 : {
261 : 328731521 : edge e;
262 : 328731521 : edge_iterator ei;
263 : :
264 : 657463042 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
265 : 328731521 : edge_checksum[e->dest->index] += (size_t) e;
266 : :
267 : 660231343 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
268 : 331499822 : edge_checksum[e->dest->index] -= (size_t) e;
269 : : }
270 : :
271 : 4077319228 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
272 : 3748587707 : if (edge_checksum[bb->index])
273 : : {
274 : 0 : error ("basic block %i edge lists are corrupted", bb->index);
275 : 0 : err = true;
276 : : }
277 : :
278 : : /* Clean up. */
279 : 328731521 : free (last_visited);
280 : 328731521 : free (edge_checksum);
281 : :
282 : 328731521 : if (cfg_hooks->verify_flow_info)
283 : 328731521 : if (cfg_hooks->verify_flow_info ())
284 : : err = true;
285 : :
286 : 328731521 : if (err)
287 : 0 : internal_error ("verify_flow_info failed");
288 : 328731521 : timevar_pop (TV_CFG_VERIFY);
289 : 328731521 : }
290 : :
291 : : /* Print out one basic block BB to file OUTF. INDENT is printed at the
292 : : start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
293 : :
294 : : This function takes care of the purely graph related information.
295 : : The cfg hook for the active representation should dump
296 : : representation-specific information. */
297 : :
298 : : void
299 : 289899 : dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
300 : : {
301 : 289899 : if (flags & TDF_BLOCKS)
302 : 41990 : dump_bb_info (outf, bb, indent, flags, true, false);
303 : 289899 : if (cfg_hooks->dump_bb)
304 : 289899 : cfg_hooks->dump_bb (outf, bb, indent, flags);
305 : 289899 : if (flags & TDF_BLOCKS)
306 : 41990 : dump_bb_info (outf, bb, indent, flags, false, true);
307 : 289899 : fputc ('\n', outf);
308 : 289899 : }
309 : :
310 : : DEBUG_FUNCTION void
311 : 0 : debug (basic_block_def &ref)
312 : : {
313 : 0 : dump_bb (stderr, &ref, 0, TDF_NONE);
314 : 0 : }
315 : :
316 : : DEBUG_FUNCTION void
317 : 0 : debug (basic_block_def *ptr)
318 : : {
319 : 0 : if (ptr)
320 : 0 : debug (*ptr);
321 : : else
322 : 0 : fprintf (stderr, "<nil>\n");
323 : 0 : }
324 : :
325 : : static void
326 : 0 : debug_slim (basic_block ptr)
327 : : {
328 : 0 : fprintf (stderr, "<basic_block %p (%d)>", (void *) ptr, ptr->index);
329 : 0 : }
330 : :
331 : 0 : DEFINE_DEBUG_VEC (basic_block_def *)
332 : 0 : DEFINE_DEBUG_HASH_SET (basic_block_def *)
333 : :
334 : : /* Dumps basic block BB to pretty-printer PP, for use as a label of
335 : : a DOT graph record-node. The implementation of this hook is
336 : : expected to write the label to the stream that is attached to PP.
337 : : Field separators between instructions are pipe characters printed
338 : : verbatim. Instructions should be written with some characters
339 : : escaped, using pp_write_text_as_dot_label_to_stream(). */
340 : :
341 : : void
342 : 451 : dump_bb_for_graph (pretty_printer *pp, basic_block bb)
343 : : {
344 : 451 : if (!cfg_hooks->dump_bb_for_graph)
345 : 0 : internal_error ("%s does not support dump_bb_for_graph",
346 : : cfg_hooks->name);
347 : : /* TODO: Add pretty printer for counter. */
348 : 451 : if (bb->count.initialized_p ())
349 : 352 : pp_printf (pp, "COUNT:" "%" PRId64, bb->count.to_gcov_type ());
350 : 451 : pp_write_text_to_stream (pp);
351 : 451 : if (!(dump_flags & TDF_SLIM))
352 : 451 : cfg_hooks->dump_bb_for_graph (pp, bb);
353 : 451 : }
354 : :
355 : : /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
356 : : void
357 : 288 : dump_flow_info (FILE *file, dump_flags_t flags)
358 : : {
359 : 288 : basic_block bb;
360 : :
361 : 288 : fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun),
362 : 288 : n_edges_for_fn (cfun));
363 : 2631 : FOR_ALL_BB_FN (bb, cfun)
364 : 2343 : dump_bb (file, bb, 0, flags);
365 : :
366 : 288 : putc ('\n', file);
367 : 288 : }
368 : :
369 : : /* Like above, but dump to stderr. To be called from debuggers. */
370 : : void debug_flow_info (void);
371 : : DEBUG_FUNCTION void
372 : 0 : debug_flow_info (void)
373 : : {
374 : 0 : dump_flow_info (stderr, TDF_DETAILS);
375 : 0 : }
376 : :
377 : : /* Redirect edge E to the given basic block DEST and update underlying program
378 : : representation. Returns edge representing redirected branch (that may not
379 : : be equivalent to E in the case of duplicate edges being removed) or NULL
380 : : if edge is not easily redirectable for whatever reason. */
381 : :
382 : : edge
383 : 76717800 : redirect_edge_and_branch (edge e, basic_block dest)
384 : : {
385 : 76717800 : edge ret;
386 : :
387 : 76717800 : if (!cfg_hooks->redirect_edge_and_branch)
388 : 0 : internal_error ("%s does not support redirect_edge_and_branch",
389 : : cfg_hooks->name);
390 : :
391 : 76717800 : ret = cfg_hooks->redirect_edge_and_branch (e, dest);
392 : :
393 : : /* If RET != E, then either the redirection failed, or the edge E
394 : : was removed since RET already lead to the same destination. */
395 : 76717800 : if (current_loops != NULL && ret == e)
396 : 63093049 : rescan_loop_exit (e, false, false);
397 : :
398 : 76717800 : return ret;
399 : : }
400 : :
401 : : /* Returns true if it is possible to remove the edge E by redirecting it
402 : : to the destination of the other edge going from its source. */
403 : :
404 : : bool
405 : 426983 : can_remove_branch_p (const_edge e)
406 : : {
407 : 426983 : if (!cfg_hooks->can_remove_branch_p)
408 : 0 : internal_error ("%s does not support can_remove_branch_p",
409 : : cfg_hooks->name);
410 : :
411 : 426983 : if (EDGE_COUNT (e->src->succs) != 2)
412 : : return false;
413 : :
414 : 426983 : return cfg_hooks->can_remove_branch_p (e);
415 : : }
416 : :
417 : : /* Removes E, by redirecting it to the destination of the other edge going
418 : : from its source. Can_remove_branch_p must be true for E, hence this
419 : : operation cannot fail. */
420 : :
421 : : void
422 : 427043 : remove_branch (edge e)
423 : : {
424 : 427043 : edge other;
425 : 427043 : basic_block src = e->src;
426 : 427043 : int irr;
427 : :
428 : 427043 : gcc_assert (EDGE_COUNT (e->src->succs) == 2);
429 : :
430 : 427043 : other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
431 : 427043 : irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
432 : :
433 : 427043 : e = redirect_edge_and_branch (e, other->dest);
434 : 427043 : gcc_assert (e != NULL);
435 : :
436 : 427043 : e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
437 : 427043 : e->flags |= irr;
438 : 427043 : }
439 : :
440 : : /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
441 : :
442 : : void
443 : 84036559 : remove_edge (edge e)
444 : : {
445 : 84036559 : if (current_loops != NULL)
446 : : {
447 : 74806291 : rescan_loop_exit (e, false, true);
448 : :
449 : : /* Removal of an edge inside an irreducible region or which leads
450 : : to an irreducible region can turn the region into a natural loop.
451 : : In that case, ask for the loop structure fixups.
452 : :
453 : : FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
454 : : set, so always ask for fixups when removing an edge in that case. */
455 : 74806291 : if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
456 : 7448767 : || (e->flags & EDGE_IRREDUCIBLE_LOOP)
457 : 82251228 : || (e->dest->flags & BB_IRREDUCIBLE_LOOP))
458 : 67361887 : loops_state_set (LOOPS_NEED_FIXUP);
459 : : }
460 : :
461 : : /* This is probably not needed, but it doesn't hurt. */
462 : : /* FIXME: This should be called via a remove_edge hook. */
463 : 84036559 : if (current_ir_type () == IR_GIMPLE)
464 : 67742278 : redirect_edge_var_map_clear (e);
465 : :
466 : 84036559 : remove_edge_raw (e);
467 : 84036559 : }
468 : :
469 : : /* Like redirect_edge_succ but avoid possible duplicate edge. */
470 : :
471 : : edge
472 : 81029754 : redirect_edge_succ_nodup (edge e, basic_block new_succ)
473 : : {
474 : 81029754 : edge s;
475 : :
476 : 81029754 : s = find_edge (e->src, new_succ);
477 : 81029754 : if (s && s != e)
478 : : {
479 : 410409 : s->flags |= e->flags;
480 : 410409 : s->probability += e->probability;
481 : : /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
482 : 410409 : redirect_edge_var_map_dup (s, e);
483 : 410409 : remove_edge (e);
484 : 410409 : e = s;
485 : : }
486 : : else
487 : 80619345 : redirect_edge_succ (e, new_succ);
488 : :
489 : 81029754 : return e;
490 : : }
491 : :
492 : : /* Redirect the edge E to basic block DEST even if it requires creating
493 : : of a new basic block; then it returns the newly created basic block.
494 : : Aborts when redirection is impossible. */
495 : :
496 : : basic_block
497 : 8763989 : redirect_edge_and_branch_force (edge e, basic_block dest)
498 : : {
499 : 8763989 : basic_block ret, src = e->src;
500 : :
501 : 8763989 : if (!cfg_hooks->redirect_edge_and_branch_force)
502 : 0 : internal_error ("%s does not support redirect_edge_and_branch_force",
503 : : cfg_hooks->name);
504 : :
505 : 8763989 : if (current_loops != NULL)
506 : 7064733 : rescan_loop_exit (e, false, true);
507 : :
508 : 8763989 : ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
509 : :
510 : 8763989 : if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
511 : 43837 : set_immediate_dominator (CDI_DOMINATORS, ret, src);
512 : :
513 : 8763989 : if (current_loops != NULL)
514 : : {
515 : 7064733 : if (ret != NULL)
516 : : {
517 : 4 : class loop *loop
518 : 4 : = find_common_loop (single_pred (ret)->loop_father,
519 : 4 : single_succ (ret)->loop_father);
520 : 4 : add_bb_to_loop (ret, loop);
521 : : }
522 : 7064729 : else if (find_edge (src, dest) == e)
523 : 7064722 : rescan_loop_exit (e, true, false);
524 : : }
525 : :
526 : 8763989 : return ret;
527 : : }
528 : :
529 : : /* Splits basic block BB after the specified instruction I (but at least after
530 : : the labels). If I is NULL, splits just after labels. The newly created edge
531 : : is returned. The new basic block is created just after the old one. */
532 : :
533 : : static edge
534 : 8744624 : split_block_1 (basic_block bb, void *i)
535 : : {
536 : 8744624 : basic_block new_bb;
537 : 8744624 : edge res;
538 : :
539 : 8744624 : if (!cfg_hooks->split_block)
540 : 0 : internal_error ("%s does not support split_block", cfg_hooks->name);
541 : :
542 : 8744624 : new_bb = cfg_hooks->split_block (bb, i);
543 : 8744624 : if (!new_bb)
544 : : return NULL;
545 : :
546 : 8744624 : new_bb->count = bb->count;
547 : :
548 : 8744624 : if (dom_info_available_p (CDI_DOMINATORS))
549 : : {
550 : 811705 : redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
551 : 811705 : set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
552 : : }
553 : :
554 : 8744624 : if (current_loops != NULL)
555 : : {
556 : 7769037 : edge_iterator ei;
557 : 7769037 : edge e;
558 : 7769037 : add_bb_to_loop (new_bb, bb->loop_father);
559 : : /* Identify all loops bb may have been the latch of and adjust them. */
560 : 19272367 : FOR_EACH_EDGE (e, ei, new_bb->succs)
561 : 11503330 : if (e->dest->loop_father->latch == bb)
562 : 124866 : e->dest->loop_father->latch = new_bb;
563 : : }
564 : :
565 : 8744624 : res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
566 : :
567 : 8744624 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
568 : : {
569 : 5397 : new_bb->flags |= BB_IRREDUCIBLE_LOOP;
570 : 5397 : res->flags |= EDGE_IRREDUCIBLE_LOOP;
571 : : }
572 : :
573 : : return res;
574 : : }
575 : :
576 : : edge
577 : 5526692 : split_block (basic_block bb, gimple *i)
578 : : {
579 : 5526692 : return split_block_1 (bb, i);
580 : : }
581 : :
582 : : edge
583 : 2961857 : split_block (basic_block bb, rtx i)
584 : : {
585 : 2961857 : return split_block_1 (bb, i);
586 : : }
587 : :
588 : : /* Splits block BB just after labels. The newly created edge is returned. */
589 : :
590 : : edge
591 : 256075 : split_block_after_labels (basic_block bb)
592 : : {
593 : 256075 : return split_block_1 (bb, NULL);
594 : : }
595 : :
596 : : /* Moves block BB immediately after block AFTER. Returns false if the
597 : : movement was impossible. */
598 : :
599 : : bool
600 : 22182051 : move_block_after (basic_block bb, basic_block after)
601 : : {
602 : 22182051 : bool ret;
603 : :
604 : 22182051 : if (!cfg_hooks->move_block_after)
605 : 0 : internal_error ("%s does not support move_block_after", cfg_hooks->name);
606 : :
607 : 22182051 : ret = cfg_hooks->move_block_after (bb, after);
608 : :
609 : 22182051 : return ret;
610 : : }
611 : :
612 : : /* Deletes the basic block BB. */
613 : :
614 : : void
615 : 44061548 : delete_basic_block (basic_block bb)
616 : : {
617 : 44061548 : if (!cfg_hooks->delete_basic_block)
618 : 0 : internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
619 : :
620 : 44061548 : cfg_hooks->delete_basic_block (bb);
621 : :
622 : 44061548 : if (current_loops != NULL)
623 : : {
624 : 38853212 : class loop *loop = bb->loop_father;
625 : :
626 : : /* If we remove the header or the latch of a loop, mark the loop for
627 : : removal. */
628 : 38853212 : if (loop->latch == bb
629 : 38634073 : || loop->header == bb)
630 : 265169 : mark_loop_for_removal (loop);
631 : :
632 : 38853212 : remove_bb_from_loops (bb);
633 : : }
634 : :
635 : : /* Remove the edges into and out of this block. Note that there may
636 : : indeed be edges in, if we are removing an unreachable loop. */
637 : 88871634 : while (EDGE_COUNT (bb->preds) != 0)
638 : 711847 : remove_edge (EDGE_PRED (bb, 0));
639 : 51011472 : while (EDGE_COUNT (bb->succs) != 0)
640 : 6949924 : remove_edge (EDGE_SUCC (bb, 0));
641 : :
642 : 44061548 : if (dom_info_available_p (CDI_DOMINATORS))
643 : 31011318 : delete_from_dominance_info (CDI_DOMINATORS, bb);
644 : 44061548 : if (dom_info_available_p (CDI_POST_DOMINATORS))
645 : 499253 : delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
646 : :
647 : : /* Remove the basic block from the array. */
648 : 44061548 : expunge_block (bb);
649 : 44061548 : }
650 : :
651 : : /* Splits edge E and returns the newly created basic block. */
652 : :
653 : : basic_block
654 : 30062270 : split_edge (edge e)
655 : : {
656 : 30062270 : basic_block ret;
657 : 30062270 : profile_count count = e->count ();
658 : 30062270 : edge f;
659 : 30062270 : bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
660 : 30062270 : bool back = (e->flags & EDGE_DFS_BACK) != 0;
661 : 30062270 : class loop *loop;
662 : 30062270 : basic_block src = e->src, dest = e->dest;
663 : :
664 : 30062270 : if (!cfg_hooks->split_edge)
665 : 0 : internal_error ("%s does not support split_edge", cfg_hooks->name);
666 : :
667 : 30062270 : if (current_loops != NULL)
668 : 28618340 : rescan_loop_exit (e, false, true);
669 : :
670 : 30062270 : ret = cfg_hooks->split_edge (e);
671 : 30062270 : ret->count = count;
672 : 30062270 : single_succ_edge (ret)->probability = profile_probability::always ();
673 : :
674 : 30062270 : if (irr)
675 : : {
676 : 76420 : ret->flags |= BB_IRREDUCIBLE_LOOP;
677 : 76420 : single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
678 : 76420 : single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
679 : : }
680 : 30062270 : if (back)
681 : : {
682 : 2058670 : single_pred_edge (ret)->flags &= ~EDGE_DFS_BACK;
683 : 2058670 : single_succ_edge (ret)->flags |= EDGE_DFS_BACK;
684 : : }
685 : :
686 : 30062270 : if (dom_info_available_p (CDI_DOMINATORS))
687 : 25986479 : set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
688 : :
689 : 30062270 : if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
690 : : {
691 : : /* There are two cases:
692 : :
693 : : If the immediate dominator of e->dest is not e->src, it
694 : : remains unchanged.
695 : :
696 : : If immediate dominator of e->dest is e->src, it may become
697 : : ret, provided that all other predecessors of e->dest are
698 : : dominated by e->dest. */
699 : :
700 : 25986479 : if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
701 : 25986479 : == single_pred (ret))
702 : : {
703 : 9087768 : edge_iterator ei;
704 : 20087229 : FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
705 : : {
706 : 15941388 : if (f == single_succ_edge (ret))
707 : 7116661 : continue;
708 : :
709 : 8824727 : if (!dominated_by_p (CDI_DOMINATORS, f->src,
710 : 8824727 : single_succ (ret)))
711 : : break;
712 : : }
713 : :
714 : 9087768 : if (!f)
715 : 4145841 : set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
716 : : }
717 : : }
718 : :
719 : 30062270 : if (current_loops != NULL)
720 : : {
721 : 28618340 : loop = find_common_loop (src->loop_father, dest->loop_father);
722 : 28618340 : add_bb_to_loop (ret, loop);
723 : :
724 : : /* If we split the latch edge of loop adjust the latch block. */
725 : 28618340 : if (loop->latch == src
726 : 6159141 : && loop->header == dest)
727 : 6159086 : loop->latch = ret;
728 : : }
729 : :
730 : 30062270 : return ret;
731 : : }
732 : :
733 : : /* Creates a new basic block just after the basic block AFTER.
734 : : HEAD and END are the first and the last statement belonging
735 : : to the block. If both are NULL, an empty block is created. */
736 : :
737 : : static basic_block
738 : 83917939 : create_basic_block_1 (void *head, void *end, basic_block after)
739 : : {
740 : 83917939 : basic_block ret;
741 : :
742 : 83917939 : if (!cfg_hooks->create_basic_block)
743 : 0 : internal_error ("%s does not support create_basic_block", cfg_hooks->name);
744 : :
745 : 83917939 : ret = cfg_hooks->create_basic_block (head, end, after);
746 : :
747 : 83917939 : if (dom_info_available_p (CDI_DOMINATORS))
748 : 31547794 : add_to_dominance_info (CDI_DOMINATORS, ret);
749 : 83917939 : if (dom_info_available_p (CDI_POST_DOMINATORS))
750 : 189885 : add_to_dominance_info (CDI_POST_DOMINATORS, ret);
751 : :
752 : 83917939 : return ret;
753 : : }
754 : :
755 : : basic_block
756 : 35528582 : create_basic_block (gimple_seq seq, basic_block after)
757 : : {
758 : 35528582 : return create_basic_block_1 (seq, NULL, after);
759 : : }
760 : :
761 : : basic_block
762 : 13355839 : create_basic_block (rtx head, rtx end, basic_block after)
763 : : {
764 : 13355839 : return create_basic_block_1 (head, end, after);
765 : : }
766 : :
767 : :
768 : : /* Creates an empty basic block just after basic block AFTER. */
769 : :
770 : : basic_block
771 : 35033518 : create_empty_bb (basic_block after)
772 : : {
773 : 35033518 : return create_basic_block_1 (NULL, NULL, after);
774 : : }
775 : :
776 : : /* Checks whether we may merge blocks BB1 and BB2. */
777 : :
778 : : bool
779 : 420973129 : can_merge_blocks_p (basic_block bb1, basic_block bb2)
780 : : {
781 : 420973129 : bool ret;
782 : :
783 : 420973129 : if (!cfg_hooks->can_merge_blocks_p)
784 : 0 : internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
785 : :
786 : 420973129 : ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
787 : :
788 : 420973129 : return ret;
789 : : }
790 : :
791 : : void
792 : 6533419 : predict_edge (edge e, enum br_predictor predictor, int probability)
793 : : {
794 : 6533419 : if (!cfg_hooks->predict_edge)
795 : 0 : internal_error ("%s does not support predict_edge", cfg_hooks->name);
796 : :
797 : 6533419 : cfg_hooks->predict_edge (e, predictor, probability);
798 : 6533419 : }
799 : :
800 : : bool
801 : 3239429 : predicted_by_p (const_basic_block bb, enum br_predictor predictor)
802 : : {
803 : 3239429 : if (!cfg_hooks->predict_edge)
804 : 0 : internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
805 : :
806 : 3239429 : return cfg_hooks->predicted_by_p (bb, predictor);
807 : : }
808 : :
809 : : /* Merges basic block B into basic block A. */
810 : :
811 : : void
812 : 20395150 : merge_blocks (basic_block a, basic_block b)
813 : : {
814 : 20395150 : edge e;
815 : 20395150 : edge_iterator ei;
816 : :
817 : 20395150 : if (!cfg_hooks->merge_blocks)
818 : 0 : internal_error ("%s does not support merge_blocks", cfg_hooks->name);
819 : :
820 : : /* Pick the more reliable count. If both qualities agrees, pick the larger
821 : : one since turning mistakely hot code to cold is more harmful. */
822 : 20395150 : if (!a->count.initialized_p ())
823 : 11208955 : a->count = b->count;
824 : 9186195 : else if (a->count.quality () < b->count.quality ())
825 : 6489 : a->count = b->count;
826 : 9179706 : else if (a->count.quality () == b->count.quality ())
827 : 9174296 : a->count = profile_count::max_prefer_initialized (a->count, b->count);
828 : :
829 : 20395150 : cfg_hooks->merge_blocks (a, b);
830 : :
831 : 20395150 : if (current_loops != NULL)
832 : : {
833 : : /* If the block we merge into is a loop header do nothing unless ... */
834 : 17300365 : if (a->loop_father->header == a)
835 : : {
836 : : /* ... we merge two loop headers, in which case we kill
837 : : the inner loop. */
838 : 619342 : if (b->loop_father->header == b)
839 : 436 : mark_loop_for_removal (b->loop_father);
840 : : }
841 : : /* If we merge a loop header into its predecessor, update the loop
842 : : structure. */
843 : 16681023 : else if (b->loop_father->header == b)
844 : : {
845 : 169 : remove_bb_from_loops (a);
846 : 169 : add_bb_to_loop (a, b->loop_father);
847 : 169 : a->loop_father->header = a;
848 : : }
849 : : /* If we merge a loop latch into its predecessor, update the loop
850 : : structure. */
851 : 17300365 : if (b->loop_father->latch
852 : 17159689 : && b->loop_father->latch == b)
853 : 238585 : b->loop_father->latch = a;
854 : 17300365 : remove_bb_from_loops (b);
855 : : }
856 : :
857 : : /* Normally there should only be one successor of A and that is B, but
858 : : partway though the merge of blocks for conditional_execution we'll
859 : : be merging a TEST block with THEN and ELSE successors. Free the
860 : : whole lot of them and hope the caller knows what they're doing. */
861 : :
862 : 40790300 : while (EDGE_COUNT (a->succs) != 0)
863 : 20395150 : remove_edge (EDGE_SUCC (a, 0));
864 : :
865 : : /* Adjust the edges out of B for the new owner. */
866 : 46749177 : FOR_EACH_EDGE (e, ei, b->succs)
867 : : {
868 : 26354027 : e->src = a;
869 : 26354027 : if (current_loops != NULL)
870 : : {
871 : : /* If b was a latch, a now is. */
872 : 22879421 : if (e->dest->loop_father->latch == b)
873 : 1007 : e->dest->loop_father->latch = a;
874 : 22879421 : rescan_loop_exit (e, true, false);
875 : : }
876 : : }
877 : 20395150 : a->succs = b->succs;
878 : 20395150 : a->flags |= b->flags;
879 : :
880 : : /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
881 : 20395150 : b->preds = b->succs = NULL;
882 : :
883 : 20395150 : if (dom_info_available_p (CDI_DOMINATORS))
884 : 15729192 : redirect_immediate_dominators (CDI_DOMINATORS, b, a);
885 : :
886 : 20395150 : if (dom_info_available_p (CDI_DOMINATORS))
887 : 15729192 : delete_from_dominance_info (CDI_DOMINATORS, b);
888 : 20395150 : if (dom_info_available_p (CDI_POST_DOMINATORS))
889 : 121189 : delete_from_dominance_info (CDI_POST_DOMINATORS, b);
890 : :
891 : 20395150 : expunge_block (b);
892 : 20395150 : }
893 : :
894 : : /* Split BB into entry part and the rest (the rest is the newly created block).
895 : : Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
896 : : part. Returns the edge connecting the entry part to the rest. */
897 : :
898 : : edge
899 : 231607 : make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
900 : : void (*new_bb_cbk) (basic_block))
901 : : {
902 : 231607 : edge e, fallthru;
903 : 231607 : edge_iterator ei;
904 : 231607 : basic_block dummy, jump;
905 : 231607 : class loop *loop, *ploop, *cloop;
906 : :
907 : 231607 : if (!cfg_hooks->make_forwarder_block)
908 : 0 : internal_error ("%s does not support make_forwarder_block",
909 : : cfg_hooks->name);
910 : :
911 : 231607 : fallthru = split_block_after_labels (bb);
912 : 231607 : dummy = fallthru->src;
913 : 231607 : dummy->count = profile_count::zero ();
914 : 231607 : bb = fallthru->dest;
915 : :
916 : : /* Redirect back edges we want to keep. */
917 : 1037234 : for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
918 : : {
919 : 805627 : basic_block e_src;
920 : :
921 : 805627 : if (redirect_edge_p (e))
922 : : {
923 : 564129 : dummy->count += e->count ();
924 : 564129 : ei_next (&ei);
925 : 564129 : continue;
926 : : }
927 : :
928 : 241498 : e_src = e->src;
929 : 241498 : jump = redirect_edge_and_branch_force (e, bb);
930 : 241498 : if (jump != NULL)
931 : : {
932 : : /* If we redirected the loop latch edge, the JUMP block now acts like
933 : : the new latch of the loop. */
934 : 3 : if (current_loops != NULL
935 : 3 : && dummy->loop_father != NULL
936 : 3 : && dummy->loop_father->header == dummy
937 : 3 : && dummy->loop_father->latch == e_src)
938 : 0 : dummy->loop_father->latch = jump;
939 : :
940 : 3 : if (new_bb_cbk != NULL)
941 : 0 : new_bb_cbk (jump);
942 : : }
943 : : }
944 : :
945 : 231607 : if (dom_info_available_p (CDI_DOMINATORS))
946 : : {
947 : 188116 : vec<basic_block> doms_to_fix;
948 : 188116 : doms_to_fix.create (2);
949 : 188116 : doms_to_fix.quick_push (dummy);
950 : 188116 : doms_to_fix.quick_push (bb);
951 : 188116 : iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
952 : 188116 : doms_to_fix.release ();
953 : : }
954 : :
955 : 231607 : if (current_loops != NULL)
956 : : {
957 : : /* If we do not split a loop header, then both blocks belong to the
958 : : same loop. In case we split loop header and do not redirect the
959 : : latch edge to DUMMY, then DUMMY belongs to the outer loop, and
960 : : BB becomes the new header. If latch is not recorded for the loop,
961 : : we leave this updating on the caller (this may only happen during
962 : : loop analysis). */
963 : 231607 : loop = dummy->loop_father;
964 : 231607 : if (loop->header == dummy
965 : 231422 : && loop->latch != NULL
966 : 363679 : && find_edge (loop->latch, dummy) == NULL)
967 : : {
968 : 132034 : remove_bb_from_loops (dummy);
969 : 132034 : loop->header = bb;
970 : :
971 : 132034 : cloop = loop;
972 : 446087 : FOR_EACH_EDGE (e, ei, dummy->preds)
973 : : {
974 : 314053 : cloop = find_common_loop (cloop, e->src->loop_father);
975 : : }
976 : 132034 : add_bb_to_loop (dummy, cloop);
977 : : }
978 : :
979 : : /* In case we split loop latch, update it. */
980 : 757913 : for (ploop = loop; ploop; ploop = loop_outer (ploop))
981 : 526306 : if (ploop->latch == dummy)
982 : 0 : ploop->latch = bb;
983 : : }
984 : :
985 : 231607 : cfg_hooks->make_forwarder_block (fallthru);
986 : :
987 : 231607 : return fallthru;
988 : : }
989 : :
990 : : /* Try to make the edge fallthru. */
991 : :
992 : : void
993 : 800719 : tidy_fallthru_edge (edge e)
994 : : {
995 : 800719 : if (cfg_hooks->tidy_fallthru_edge)
996 : 800719 : cfg_hooks->tidy_fallthru_edge (e);
997 : 800719 : }
998 : :
999 : : /* Fix up edges that now fall through, or rather should now fall through
1000 : : but previously required a jump around now deleted blocks. Simplify
1001 : : the search by only examining blocks numerically adjacent, since this
1002 : : is how they were created.
1003 : :
1004 : : ??? This routine is currently RTL specific. */
1005 : :
1006 : : void
1007 : 464090 : tidy_fallthru_edges (void)
1008 : : {
1009 : 464090 : basic_block b, c;
1010 : :
1011 : 464090 : if (!cfg_hooks->tidy_fallthru_edge)
1012 : : return;
1013 : :
1014 : 126741 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1015 : : return;
1016 : :
1017 : 4316605 : FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
1018 : : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, next_bb)
1019 : : {
1020 : 4189864 : edge s;
1021 : :
1022 : 4189864 : c = b->next_bb;
1023 : :
1024 : : /* We care about simple conditional or unconditional jumps with
1025 : : a single successor.
1026 : :
1027 : : If we had a conditional branch to the next instruction when
1028 : : CFG was built, then there will only be one out edge for the
1029 : : block which ended with the conditional branch (since we do
1030 : : not create duplicate edges).
1031 : :
1032 : : Furthermore, the edge will be marked as a fallthru because we
1033 : : merge the flags for the duplicate edges. So we do not want to
1034 : : check that the edge is not a FALLTHRU edge. */
1035 : :
1036 : 6201830 : if (single_succ_p (b))
1037 : : {
1038 : 2011966 : s = single_succ_edge (b);
1039 : 2011966 : if (! (s->flags & EDGE_COMPLEX)
1040 : 1949549 : && s->dest == c
1041 : 2855861 : && !(JUMP_P (BB_END (b)) && CROSSING_JUMP_P (BB_END (b))))
1042 : 792904 : tidy_fallthru_edge (s);
1043 : : }
1044 : : }
1045 : : }
1046 : :
1047 : : /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1048 : : (and possibly create new basic block) to make edge non-fallthru.
1049 : : Return newly created BB or NULL if none. */
1050 : :
1051 : : basic_block
1052 : 889796 : force_nonfallthru (edge e)
1053 : : {
1054 : 889796 : basic_block ret, src = e->src;
1055 : :
1056 : 889796 : if (!cfg_hooks->force_nonfallthru)
1057 : 0 : internal_error ("%s does not support force_nonfallthru",
1058 : : cfg_hooks->name);
1059 : :
1060 : 889796 : ret = cfg_hooks->force_nonfallthru (e);
1061 : 889796 : if (ret != NULL)
1062 : : {
1063 : 186933 : if (dom_info_available_p (CDI_DOMINATORS))
1064 : 10340 : set_immediate_dominator (CDI_DOMINATORS, ret, src);
1065 : :
1066 : 186933 : if (current_loops != NULL)
1067 : : {
1068 : 79015 : basic_block pred = single_pred (ret);
1069 : 79015 : basic_block succ = single_succ (ret);
1070 : 79015 : class loop *loop
1071 : 79015 : = find_common_loop (pred->loop_father, succ->loop_father);
1072 : 79015 : rescan_loop_exit (e, false, true);
1073 : 79015 : add_bb_to_loop (ret, loop);
1074 : :
1075 : : /* If we split the latch edge of loop adjust the latch block. */
1076 : 79015 : if (loop->latch == pred
1077 : 3432 : && loop->header == succ)
1078 : 3432 : loop->latch = ret;
1079 : : }
1080 : : }
1081 : :
1082 : 889796 : return ret;
1083 : : }
1084 : :
1085 : : /* Returns true if we can duplicate basic block BB. */
1086 : :
1087 : : bool
1088 : 17787618 : can_duplicate_block_p (const_basic_block bb)
1089 : : {
1090 : 17787618 : if (!cfg_hooks->can_duplicate_block_p)
1091 : 0 : internal_error ("%s does not support can_duplicate_block_p",
1092 : : cfg_hooks->name);
1093 : :
1094 : 17787618 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1095 : : return false;
1096 : :
1097 : 17787618 : return cfg_hooks->can_duplicate_block_p (bb);
1098 : : }
1099 : :
1100 : : /* Duplicate basic block BB, place it after AFTER (if non-null) and redirect
1101 : : edge E to it (if non-null). Return the new basic block.
1102 : :
1103 : : If BB contains a returns_twice call, the caller is responsible for recreating
1104 : : incoming abnormal edges corresponding to the "second return" for the copy.
1105 : : gimple_can_duplicate_bb_p rejects such blocks, while RTL likes to live
1106 : : dangerously.
1107 : :
1108 : : If BB has incoming abnormal edges for some other reason, their destinations
1109 : : should be tied to label(s) of the original BB and not the copy. */
1110 : :
1111 : : basic_block
1112 : 4528615 : duplicate_block (basic_block bb, edge e, basic_block after, copy_bb_data *id)
1113 : : {
1114 : 4528615 : edge s, n;
1115 : 4528615 : basic_block new_bb;
1116 : 4814916 : profile_count new_count = e ? e->count (): profile_count::uninitialized ();
1117 : 4528615 : edge_iterator ei;
1118 : :
1119 : 4528615 : if (!cfg_hooks->duplicate_block)
1120 : 0 : internal_error ("%s does not support duplicate_block",
1121 : : cfg_hooks->name);
1122 : :
1123 : 4528615 : if (bb->count < new_count)
1124 : 1288 : new_count = bb->count;
1125 : :
1126 : 4528615 : gcc_checking_assert (can_duplicate_block_p (bb));
1127 : :
1128 : 4528615 : new_bb = cfg_hooks->duplicate_block (bb, id);
1129 : 4528615 : if (after)
1130 : 4151104 : move_block_after (new_bb, after);
1131 : :
1132 : 4528615 : new_bb->flags = (bb->flags & ~BB_DUPLICATED);
1133 : 12446212 : FOR_EACH_EDGE (s, ei, bb->succs)
1134 : : {
1135 : : /* Since we are creating edges from a new block to successors
1136 : : of another block (which therefore are known to be disjoint), there
1137 : : is no need to actually check for duplicated edges. */
1138 : 7917597 : n = unchecked_make_edge (new_bb, s->dest, s->flags);
1139 : 7917597 : n->probability = s->probability;
1140 : 7917597 : n->aux = s->aux;
1141 : : }
1142 : :
1143 : 4528615 : if (e)
1144 : : {
1145 : 286301 : new_bb->count = new_count;
1146 : 286301 : bb->count -= new_count;
1147 : :
1148 : 286301 : redirect_edge_and_branch_force (e, new_bb);
1149 : : }
1150 : : else
1151 : 4242314 : new_bb->count = bb->count;
1152 : :
1153 : 4528615 : set_bb_original (new_bb, bb);
1154 : 4528615 : set_bb_copy (bb, new_bb);
1155 : :
1156 : : /* Add the new block to the copy of the loop of BB, or directly to the loop
1157 : : of BB if the loop is not being copied. */
1158 : 4528615 : if (current_loops != NULL)
1159 : : {
1160 : 4217902 : class loop *cloop = bb->loop_father;
1161 : 4217902 : class loop *copy = get_loop_copy (cloop);
1162 : : /* If we copied the loop header block but not the loop
1163 : : we have created a loop with multiple entries. Ditch the loop,
1164 : : add the new block to the outer loop and arrange for a fixup. */
1165 : 4217902 : if (!copy
1166 : 383437 : && cloop->header == bb)
1167 : : {
1168 : 432 : add_bb_to_loop (new_bb, loop_outer (cloop));
1169 : 432 : mark_loop_for_removal (cloop);
1170 : : }
1171 : : else
1172 : : {
1173 : 4217470 : add_bb_to_loop (new_bb, copy ? copy : cloop);
1174 : : /* If we copied the loop latch block but not the loop, adjust
1175 : : loop state. */
1176 : 4217470 : if (!copy
1177 : 383005 : && cloop->latch == bb)
1178 : : {
1179 : 569 : cloop->latch = NULL;
1180 : 569 : loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1181 : : }
1182 : : }
1183 : : }
1184 : :
1185 : 4528615 : return new_bb;
1186 : : }
1187 : :
1188 : : /* Return 1 if BB ends with a call, possibly followed by some
1189 : : instructions that must stay with the call, 0 otherwise. */
1190 : :
1191 : : bool
1192 : 9827125 : block_ends_with_call_p (basic_block bb)
1193 : : {
1194 : 9827125 : if (!cfg_hooks->block_ends_with_call_p)
1195 : 0 : internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1196 : :
1197 : 9827125 : return (cfg_hooks->block_ends_with_call_p) (bb);
1198 : : }
1199 : :
1200 : : /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1201 : :
1202 : : bool
1203 : 1741 : block_ends_with_condjump_p (const_basic_block bb)
1204 : : {
1205 : 1741 : if (!cfg_hooks->block_ends_with_condjump_p)
1206 : 0 : internal_error ("%s does not support block_ends_with_condjump_p",
1207 : : cfg_hooks->name);
1208 : :
1209 : 1741 : return (cfg_hooks->block_ends_with_condjump_p) (bb);
1210 : : }
1211 : :
1212 : : /* Add fake edges to the function exit for any non constant and non noreturn
1213 : : calls, volatile inline assembly in the bitmap of blocks specified by
1214 : : BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1215 : : that were split.
1216 : :
1217 : : The goal is to expose cases in which entering a basic block does not imply
1218 : : that all subsequent instructions must be executed. */
1219 : :
1220 : : int
1221 : 2543 : flow_call_edges_add (sbitmap blocks)
1222 : : {
1223 : 2543 : if (!cfg_hooks->flow_call_edges_add)
1224 : 0 : internal_error ("%s does not support flow_call_edges_add",
1225 : : cfg_hooks->name);
1226 : :
1227 : 2543 : return (cfg_hooks->flow_call_edges_add) (blocks);
1228 : : }
1229 : :
1230 : : /* This function is called immediately after edge E is added to the
1231 : : edge vector E->dest->preds. */
1232 : :
1233 : : void
1234 : 202451534 : execute_on_growing_pred (edge e)
1235 : : {
1236 : 202451534 : if (! (e->dest->flags & BB_DUPLICATED)
1237 : 200224578 : && cfg_hooks->execute_on_growing_pred)
1238 : 158678957 : cfg_hooks->execute_on_growing_pred (e);
1239 : 202451534 : }
1240 : :
1241 : : /* This function is called immediately before edge E is removed from
1242 : : the edge vector E->dest->preds. */
1243 : :
1244 : : void
1245 : 171197772 : execute_on_shrinking_pred (edge e)
1246 : : {
1247 : 171197772 : if (! (e->dest->flags & BB_DUPLICATED)
1248 : 168970816 : && cfg_hooks->execute_on_shrinking_pred)
1249 : 129918625 : cfg_hooks->execute_on_shrinking_pred (e);
1250 : 171197772 : }
1251 : :
1252 : : /* This is used inside loop versioning when we want to insert
1253 : : stmts/insns on the edges, which have a different behavior
1254 : : in tree's and in RTL, so we made a CFG hook. */
1255 : : void
1256 : 35574 : lv_flush_pending_stmts (edge e)
1257 : : {
1258 : 35574 : if (cfg_hooks->flush_pending_stmts)
1259 : 35574 : cfg_hooks->flush_pending_stmts (e);
1260 : 35574 : }
1261 : :
1262 : : /* Loop versioning uses the duplicate_loop_body_to_header_edge to create
1263 : : a new version of the loop basic-blocks, the parameters here are
1264 : : exactly the same as in duplicate_loop_body_to_header_edge or
1265 : : tree_duplicate_loop_body_to_header_edge; while in tree-ssa there is
1266 : : additional work to maintain ssa information that's why there is
1267 : : a need to call the tree_duplicate_loop_body_to_header_edge rather
1268 : : than duplicate_loop_body_to_header_edge when we are in tree mode. */
1269 : : bool
1270 : 35584 : cfg_hook_duplicate_loop_body_to_header_edge (class loop *loop, edge e,
1271 : : unsigned int ndupl,
1272 : : sbitmap wont_exit, edge orig,
1273 : : vec<edge> *to_remove, int flags)
1274 : : {
1275 : 35584 : gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_body_to_header_edge);
1276 : 35584 : return cfg_hooks->cfg_hook_duplicate_loop_body_to_header_edge (
1277 : 35584 : loop, e, ndupl, wont_exit, orig, to_remove, flags);
1278 : : }
1279 : :
1280 : : /* Conditional jumps are represented differently in trees and RTL,
1281 : : this hook takes a basic block that is known to have a cond jump
1282 : : at its end and extracts the taken and not taken edges out of it
1283 : : and store it in E1 and E2 respectively. */
1284 : : void
1285 : 0 : extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1286 : : {
1287 : 0 : gcc_assert (cfg_hooks->extract_cond_bb_edges);
1288 : 0 : cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1289 : 0 : }
1290 : :
1291 : : /* Responsible for updating the ssa info (PHI nodes) on the
1292 : : new condition basic block that guards the versioned loop. */
1293 : : void
1294 : 35574 : lv_adjust_loop_header_phi (basic_block first, basic_block second,
1295 : : basic_block new_block, edge e)
1296 : : {
1297 : 35574 : if (cfg_hooks->lv_adjust_loop_header_phi)
1298 : 35574 : cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1299 : 35574 : }
1300 : :
1301 : : /* Conditions in trees and RTL are different so we need
1302 : : a different handling when we add the condition to the
1303 : : versioning code. */
1304 : : void
1305 : 35574 : lv_add_condition_to_bb (basic_block first, basic_block second,
1306 : : basic_block new_block, void *cond)
1307 : : {
1308 : 35574 : gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1309 : 35574 : cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1310 : 35574 : }
1311 : :
1312 : : /* Checks whether all N blocks in BBS array can be copied. */
1313 : : bool
1314 : 3101574 : can_copy_bbs_p (basic_block *bbs, unsigned n)
1315 : : {
1316 : 3101574 : unsigned i;
1317 : 3101574 : edge e;
1318 : 3101574 : int ret = true;
1319 : :
1320 : 11270000 : for (i = 0; i < n; i++)
1321 : 8168426 : bbs[i]->flags |= BB_DUPLICATED;
1322 : :
1323 : 11123307 : for (i = 0; i < n; i++)
1324 : : {
1325 : : /* In case we should redirect abnormal edge during duplication, fail. */
1326 : 8032743 : edge_iterator ei;
1327 : 21345394 : FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1328 : 13321821 : if ((e->flags & EDGE_ABNORMAL)
1329 : 119824 : && (e->dest->flags & BB_DUPLICATED))
1330 : : {
1331 : 9170 : ret = false;
1332 : 9170 : goto end;
1333 : : }
1334 : :
1335 : 8023573 : if (!can_duplicate_block_p (bbs[i]))
1336 : : {
1337 : 1840 : ret = false;
1338 : 1840 : break;
1339 : : }
1340 : : }
1341 : :
1342 : 3090564 : end:
1343 : 11270000 : for (i = 0; i < n; i++)
1344 : 8168426 : bbs[i]->flags &= ~BB_DUPLICATED;
1345 : :
1346 : 3101574 : return ret;
1347 : : }
1348 : :
1349 : : /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1350 : : are placed into array NEW_BBS in the same order. Edges from basic blocks
1351 : : in BBS are also duplicated and copies of those that lead into BBS are
1352 : : redirected to appropriate newly created block. The function assigns bbs
1353 : : into loops (copy of basic block bb is assigned to bb->loop_father->copy
1354 : : loop, so this must be set up correctly in advance)
1355 : :
1356 : : If UPDATE_DOMINANCE is true then this function updates dominators locally
1357 : : (LOOPS structure that contains the information about dominators is passed
1358 : : to enable this), otherwise it does not update the dominator information
1359 : : and it assumed that the caller will do this, perhaps by destroying and
1360 : : recreating it instead of trying to do an incremental update like this
1361 : : function does when update_dominance is true.
1362 : :
1363 : : BASE is the superloop to that basic block belongs; if its header or latch
1364 : : is copied, we do not set the new blocks as header or latch.
1365 : :
1366 : : Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1367 : : also in the same order.
1368 : :
1369 : : Newly created basic blocks are put after the basic block AFTER in the
1370 : : instruction stream, and the order of the blocks in BBS array is preserved. */
1371 : :
1372 : : void
1373 : 2305258 : copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1374 : : edge *edges, unsigned num_edges, edge *new_edges,
1375 : : class loop *base, basic_block after, bool update_dominance)
1376 : : {
1377 : 2305258 : unsigned i, j;
1378 : 2305258 : basic_block bb, new_bb, dom_bb;
1379 : 2305258 : edge e;
1380 : 2305258 : copy_bb_data id;
1381 : :
1382 : : /* Mark the blocks to be copied. This is used by edge creation hooks
1383 : : to decide whether to reallocate PHI nodes capacity to avoid reallocating
1384 : : PHIs in the set of source BBs. */
1385 : 6170231 : for (i = 0; i < n; i++)
1386 : 3864973 : bbs[i]->flags |= BB_DUPLICATED;
1387 : :
1388 : : /* Duplicate bbs, update dominators, assign bbs to loops. */
1389 : 6170231 : for (i = 0; i < n; i++)
1390 : : {
1391 : : /* Duplicate. */
1392 : 3864973 : bb = bbs[i];
1393 : 3864973 : new_bb = new_bbs[i] = duplicate_block (bb, NULL, after, &id);
1394 : 3864973 : after = new_bb;
1395 : 3864973 : if (bb->loop_father)
1396 : : {
1397 : : /* Possibly set loop header. */
1398 : 3864973 : if (bb->loop_father->header == bb && bb->loop_father != base)
1399 : 39941 : new_bb->loop_father->header = new_bb;
1400 : : /* Or latch. */
1401 : 3864973 : if (bb->loop_father->latch == bb && bb->loop_father != base)
1402 : 39941 : new_bb->loop_father->latch = new_bb;
1403 : : }
1404 : : }
1405 : :
1406 : : /* Set dominators. */
1407 : 2305258 : if (update_dominance)
1408 : : {
1409 : 3272736 : for (i = 0; i < n; i++)
1410 : : {
1411 : 2156325 : bb = bbs[i];
1412 : 2156325 : new_bb = new_bbs[i];
1413 : :
1414 : 2156325 : dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1415 : 2156325 : if (dom_bb->flags & BB_DUPLICATED)
1416 : : {
1417 : 1039914 : dom_bb = get_bb_copy (dom_bb);
1418 : 1039914 : set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1419 : : }
1420 : : }
1421 : : }
1422 : :
1423 : : /* Redirect edges. */
1424 : 6170231 : for (i = 0; i < n; i++)
1425 : : {
1426 : 3864973 : edge_iterator ei;
1427 : 3864973 : new_bb = new_bbs[i];
1428 : 3864973 : bb = bbs[i];
1429 : :
1430 : 10680144 : FOR_EACH_EDGE (e, ei, new_bb->succs)
1431 : : {
1432 : 6815171 : if (!(e->dest->flags & BB_DUPLICATED))
1433 : 4588215 : continue;
1434 : 2226956 : redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1435 : : }
1436 : : }
1437 : 5134395 : for (j = 0; j < num_edges; j++)
1438 : : {
1439 : 2829137 : if (!edges[j])
1440 : 74824 : new_edges[j] = NULL;
1441 : : else
1442 : : {
1443 : 2754313 : basic_block src = edges[j]->src;
1444 : 2754313 : basic_block dest = edges[j]->dest;
1445 : 2754313 : if (src->flags & BB_DUPLICATED)
1446 : 2754313 : src = get_bb_copy (src);
1447 : 2754313 : if (dest->flags & BB_DUPLICATED)
1448 : 486083 : dest = get_bb_copy (dest);
1449 : 2754313 : new_edges[j] = find_edge (src, dest);
1450 : : }
1451 : : }
1452 : :
1453 : : /* Clear information about duplicates. */
1454 : 6170231 : for (i = 0; i < n; i++)
1455 : 3864973 : bbs[i]->flags &= ~BB_DUPLICATED;
1456 : 2305258 : }
1457 : :
1458 : : /* Return true if BB contains only labels or non-executable
1459 : : instructions */
1460 : : bool
1461 : 13782975 : empty_block_p (basic_block bb)
1462 : : {
1463 : 13782975 : gcc_assert (cfg_hooks->empty_block_p);
1464 : 13782975 : return cfg_hooks->empty_block_p (bb);
1465 : : }
1466 : :
1467 : : /* Split a basic block if it ends with a conditional branch and if
1468 : : the other part of the block is not empty. */
1469 : : basic_block
1470 : 558 : split_block_before_cond_jump (basic_block bb)
1471 : : {
1472 : 558 : gcc_assert (cfg_hooks->split_block_before_cond_jump);
1473 : 558 : return cfg_hooks->split_block_before_cond_jump (bb);
1474 : : }
1475 : :
1476 : : /* Work-horse for passes.cc:check_profile_consistency.
1477 : : Do book-keeping of the CFG for the profile consistency checker.
1478 : : Store the counting in RECORD. */
1479 : :
1480 : : void
1481 : 0 : profile_record_check_consistency (profile_record *record)
1482 : : {
1483 : 0 : basic_block bb;
1484 : 0 : edge_iterator ei;
1485 : 0 : edge e;
1486 : :
1487 : 0 : FOR_ALL_BB_FN (bb, cfun)
1488 : : {
1489 : 0 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
1490 : 0 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1491 : 0 : && EDGE_COUNT (bb->succs))
1492 : : {
1493 : 0 : sreal sum = 0;
1494 : 0 : bool found = false;
1495 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1496 : : {
1497 : 0 : if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
1498 : 0 : found = true;
1499 : 0 : if (e->probability.initialized_p ())
1500 : 0 : sum += e->probability.to_sreal ();
1501 : : }
1502 : 0 : double dsum = sum.to_double ();
1503 : 0 : if (found && (dsum < 0.9 || dsum > 1.1)
1504 : 0 : && !(bb->count == profile_count::zero ()))
1505 : : {
1506 : 0 : record->num_mismatched_prob_out++;
1507 : 0 : dsum = dsum > 1 ? dsum - 1 : 1 - dsum;
1508 : 0 : if (profile_info)
1509 : : {
1510 : 0 : if (ENTRY_BLOCK_PTR_FOR_FN
1511 : 0 : (cfun)->count.ipa ().initialized_p ()
1512 : 0 : && ENTRY_BLOCK_PTR_FOR_FN
1513 : 0 : (cfun)->count.ipa ().nonzero_p ()
1514 : 0 : && bb->count.ipa ().initialized_p ())
1515 : 0 : record->dyn_mismatched_prob_out
1516 : 0 : += dsum * bb->count.ipa ().to_gcov_type ();
1517 : : }
1518 : 0 : else if (bb->count.initialized_p ())
1519 : 0 : record->dyn_mismatched_prob_out
1520 : 0 : += dsum * bb->count.to_sreal_scale
1521 : 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
1522 : : }
1523 : : }
1524 : 0 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1525 : 0 : && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1526 : : {
1527 : 0 : profile_count lsum = profile_count::zero ();
1528 : 0 : FOR_EACH_EDGE (e, ei, bb->preds)
1529 : 0 : lsum += e->count ();
1530 : 0 : if (lsum.differs_from_p (bb->count))
1531 : : {
1532 : 0 : record->num_mismatched_count_in++;
1533 : 0 : profile_count max;
1534 : 0 : if (lsum < bb->count)
1535 : 0 : max = bb->count;
1536 : : else
1537 : 0 : max = lsum;
1538 : 0 : if (profile_info)
1539 : : {
1540 : 0 : if (ENTRY_BLOCK_PTR_FOR_FN
1541 : 0 : (cfun)->count.ipa ().initialized_p ()
1542 : 0 : && ENTRY_BLOCK_PTR_FOR_FN
1543 : 0 : (cfun)->count.ipa ().nonzero_p ()
1544 : 0 : && max.ipa ().initialized_p ())
1545 : 0 : record->dyn_mismatched_count_in
1546 : 0 : += max.ipa ().to_gcov_type ();
1547 : : }
1548 : 0 : else if (bb->count.initialized_p ())
1549 : 0 : record->dyn_mismatched_prob_out
1550 : 0 : += max.to_sreal_scale
1551 : 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
1552 : : }
1553 : : }
1554 : 0 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1555 : : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1556 : 0 : continue;
1557 : : }
1558 : 0 : }
1559 : :
1560 : : /* Work-horse for passes.cc:acount_profile.
1561 : : Do book-keeping of the CFG for the profile accounting.
1562 : : Store the counting in RECORD. */
1563 : :
1564 : : void
1565 : 0 : profile_record_account_profile (profile_record *record)
1566 : : {
1567 : 0 : basic_block bb;
1568 : :
1569 : 0 : FOR_ALL_BB_FN (bb, cfun)
1570 : : {
1571 : 0 : gcc_assert (cfg_hooks->account_profile_record);
1572 : 0 : cfg_hooks->account_profile_record (bb, record);
1573 : : }
1574 : 0 : }
1575 : :
1576 : : #if __GNUC__ >= 10
1577 : : # pragma GCC diagnostic pop
1578 : : #endif
|
