Line data Source code
1 : /* Hooks for cfg representation specific functions.
2 : Copyright (C) 2003-2026 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 : #define INCLUDE_VECTOR
22 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "rtl.h"
27 : #include "cfghooks.h"
28 : #include "timevar.h"
29 : #include "pretty-print.h"
30 : #include "diagnostic-core.h"
31 : #include "dumpfile.h"
32 : #include "cfganal.h"
33 : #include "tree.h"
34 : #include "tree-ssa.h"
35 : #include "tree-cfg.h"
36 : #include "cfgloop.h"
37 : #include "sreal.h"
38 : #include "profile.h"
39 : #include "diagnostics/sarif-sink.h"
40 : #include "custom-sarif-properties/cfg.h"
41 : #include "hierarchical_discriminator.h"
42 :
43 : /* Location used to allocate a copyid for a duplicated BB. */
44 :
45 : static location_t
46 3323256 : copyid_location_from_bb (basic_block bb)
47 : {
48 3323256 : if (!bb)
49 : return UNKNOWN_LOCATION;
50 :
51 3323256 : if (current_ir_type () == IR_GIMPLE)
52 : {
53 2839575 : gimple *last = last_nondebug_stmt (bb);
54 2839575 : return last ? gimple_location (last) : UNKNOWN_LOCATION;
55 : }
56 :
57 483681 : rtx_insn *insn;
58 686942 : FOR_BB_INSNS_REVERSE (bb, insn)
59 665013 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
60 461752 : return INSN_LOCATION (insn);
61 :
62 : return UNKNOWN_LOCATION;
63 : }
64 :
65 : /* Disable warnings about missing quoting in GCC diagnostics. */
66 : #if __GNUC__ >= 10
67 : # pragma GCC diagnostic push
68 : # pragma GCC diagnostic ignored "-Wformat-diag"
69 : #endif
70 :
71 : /* A pointer to one of the hooks containers. */
72 : static const struct cfg_hooks *cfg_hooks;
73 :
74 : /* Initialization of functions specific to the rtl IR. */
75 : void
76 4103234 : rtl_register_cfg_hooks (void)
77 : {
78 4103234 : cfg_hooks = &rtl_cfg_hooks;
79 4103234 : }
80 :
81 : /* Initialization of functions specific to the rtl IR. */
82 : void
83 2586428 : cfg_layout_rtl_register_cfg_hooks (void)
84 : {
85 2586428 : cfg_hooks = &cfg_layout_rtl_cfg_hooks;
86 2586428 : }
87 :
88 : /* Initialization of functions specific to the tree IR. */
89 :
90 : void
91 15381411 : gimple_register_cfg_hooks (void)
92 : {
93 15381411 : cfg_hooks = &gimple_cfg_hooks;
94 15381411 : }
95 :
96 : const struct cfg_hooks *
97 715 : get_cfg_hooks (void)
98 : {
99 715 : return cfg_hooks;
100 : }
101 :
102 : void
103 1430 : set_cfg_hooks (const struct cfg_hooks *new_cfg_hooks)
104 : {
105 1430 : cfg_hooks = new_cfg_hooks;
106 1430 : }
107 :
108 : /* Returns current ir type. */
109 :
110 : enum ir_type
111 334518515 : current_ir_type (void)
112 : {
113 334518515 : return cfg_hooks->ir;
114 : }
115 :
116 : static const char *
117 0 : current_ir_name (void)
118 : {
119 0 : enum ir_type ir = cfg_hooks->ir;
120 0 : switch (ir)
121 : {
122 : case IR_GIMPLE:
123 : return "gimple";
124 0 : case IR_RTL_CFGRTL:
125 0 : return "rtl";
126 0 : case IR_RTL_CFGLAYOUT:
127 0 : return "cfglayout mode";
128 0 : default:
129 0 : gcc_unreachable();
130 : }
131 : }
132 :
133 : /* Verify the CFG consistency.
134 :
135 : Currently it does following: checks edge and basic block list correctness
136 : and calls into IL dependent checking then. */
137 :
138 : DEBUG_FUNCTION void
139 339967587 : verify_flow_info (void)
140 : {
141 339967587 : size_t *edge_checksum;
142 339967587 : bool err = false;
143 339967587 : basic_block bb, last_bb_seen;
144 339967587 : basic_block *last_visited;
145 :
146 339967587 : timevar_push (TV_CFG_VERIFY);
147 339967587 : last_visited = XCNEWVEC (basic_block, last_basic_block_for_fn (cfun));
148 339967587 : edge_checksum = XCNEWVEC (size_t, last_basic_block_for_fn (cfun));
149 :
150 : /* Check bb chain & numbers. */
151 339967587 : last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
152 3843779780 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
153 : {
154 3503812193 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
155 3503812193 : && bb != BASIC_BLOCK_FOR_FN (cfun, bb->index))
156 : {
157 0 : error ("bb %d on wrong place", bb->index);
158 0 : err = true;
159 : }
160 :
161 3503812193 : if (bb->prev_bb != last_bb_seen)
162 : {
163 0 : error ("prev_bb of %d should be %d, not %d",
164 : bb->index, last_bb_seen->index, bb->prev_bb->index);
165 0 : err = true;
166 : }
167 :
168 3503812193 : last_bb_seen = bb;
169 : }
170 :
171 : /* Now check the basic blocks (boundaries etc.) */
172 3503812193 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
173 : {
174 3163844606 : int n_fallthru = 0;
175 3163844606 : edge e;
176 3163844606 : edge_iterator ei;
177 :
178 3163844606 : if (bb->loop_father != NULL && current_loops == NULL)
179 : {
180 0 : error ("verify_flow_info: Block %i has loop_father, but there are no loops",
181 : bb->index);
182 0 : err = true;
183 : }
184 3163844606 : if (bb->loop_father == NULL && current_loops != NULL)
185 : {
186 0 : error ("verify_flow_info: Block %i lacks loop_father", bb->index);
187 0 : err = true;
188 : }
189 :
190 3163844606 : if (!bb->count.verify ())
191 : {
192 0 : error ("verify_flow_info: Wrong count of block %i", bb->index);
193 0 : err = true;
194 : }
195 : /* FIXME: Graphite and SLJL and target code still tends to produce
196 : edges with no probability. */
197 3163844606 : if (profile_status_for_fn (cfun) >= PROFILE_GUESSED
198 : && !bb->count.initialized_p () && !flag_graphite && 0)
199 : {
200 : error ("verify_flow_info: Missing count of block %i", bb->index);
201 : err = true;
202 : }
203 :
204 3163844606 : if (bb->flags & ~cfun->cfg->bb_flags_allocated)
205 : {
206 0 : error ("verify_flow_info: unallocated flag set on BB %d", bb->index);
207 0 : err = true;
208 : }
209 :
210 7647388004 : FOR_EACH_EDGE (e, ei, bb->succs)
211 : {
212 4483543398 : if (last_visited [e->dest->index] == bb)
213 : {
214 0 : error ("verify_flow_info: Duplicate edge %i->%i",
215 0 : e->src->index, e->dest->index);
216 0 : err = true;
217 : }
218 : /* FIXME: Graphite and SLJL and target code still tends to produce
219 : edges with no probability. */
220 4483543398 : if (profile_status_for_fn (cfun) >= PROFILE_GUESSED
221 : && !e->probability.initialized_p () && !flag_graphite && 0)
222 : {
223 : error ("Uninitialized probability of edge %i->%i", e->src->index,
224 : e->dest->index);
225 : err = true;
226 : }
227 4483543398 : if (!e->probability.verify ())
228 : {
229 0 : error ("verify_flow_info: Wrong probability of edge %i->%i",
230 0 : e->src->index, e->dest->index);
231 0 : err = true;
232 : }
233 :
234 4483543398 : last_visited [e->dest->index] = bb;
235 :
236 4483543398 : if (e->flags & EDGE_FALLTHRU)
237 1713601053 : n_fallthru++;
238 :
239 4483543398 : if (e->src != bb)
240 : {
241 0 : error ("verify_flow_info: Basic block %d succ edge is corrupted",
242 : bb->index);
243 0 : fprintf (stderr, "Predecessor: ");
244 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
245 0 : fprintf (stderr, "\nSuccessor: ");
246 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
247 0 : fprintf (stderr, "\n");
248 0 : err = true;
249 : }
250 :
251 4483543398 : if (e->flags & ~cfun->cfg->edge_flags_allocated)
252 : {
253 0 : error ("verify_flow_info: unallocated edge flag set on %d -> %d",
254 0 : e->src->index, e->dest->index);
255 0 : err = true;
256 : }
257 :
258 4483543398 : edge_checksum[e->dest->index] += (size_t) e;
259 : }
260 3163844606 : if (n_fallthru > 1)
261 : {
262 0 : error ("wrong amount of branch edges after unconditional jump %i", bb->index);
263 0 : err = true;
264 : }
265 :
266 7644814300 : FOR_EACH_EDGE (e, ei, bb->preds)
267 : {
268 4480969694 : if (e->dest != bb)
269 : {
270 0 : error ("basic block %d pred edge is corrupted", bb->index);
271 0 : fputs ("Predecessor: ", stderr);
272 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
273 0 : fputs ("\nSuccessor: ", stderr);
274 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
275 0 : fputc ('\n', stderr);
276 0 : err = true;
277 : }
278 :
279 4480969694 : if (ei.index != e->dest_idx)
280 : {
281 0 : error ("basic block %d pred edge is corrupted", bb->index);
282 0 : error ("its dest_idx should be %d, not %d",
283 : ei.index, e->dest_idx);
284 0 : fputs ("Predecessor: ", stderr);
285 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
286 0 : fputs ("\nSuccessor: ", stderr);
287 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
288 0 : fputc ('\n', stderr);
289 0 : err = true;
290 : }
291 :
292 4480969694 : edge_checksum[e->dest->index] -= (size_t) e;
293 : }
294 : }
295 :
296 : /* Complete edge checksumming for ENTRY and EXIT. */
297 339967587 : {
298 339967587 : edge e;
299 339967587 : edge_iterator ei;
300 :
301 679935174 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
302 339967587 : edge_checksum[e->dest->index] += (size_t) e;
303 :
304 682508878 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
305 342541291 : edge_checksum[e->dest->index] -= (size_t) e;
306 : }
307 :
308 4183747367 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
309 3843779780 : if (edge_checksum[bb->index])
310 : {
311 0 : error ("basic block %i edge lists are corrupted", bb->index);
312 0 : err = true;
313 : }
314 :
315 : /* Clean up. */
316 339967587 : free (last_visited);
317 339967587 : free (edge_checksum);
318 :
319 339967587 : if (cfg_hooks->verify_flow_info)
320 339967587 : if (cfg_hooks->verify_flow_info ())
321 : err = true;
322 :
323 339967587 : if (err)
324 0 : internal_error ("verify_flow_info failed");
325 339967587 : timevar_pop (TV_CFG_VERIFY);
326 339967587 : }
327 :
328 : /* Print out one basic block BB to file OUTF. INDENT is printed at the
329 : start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
330 :
331 : This function takes care of the purely graph related information.
332 : The cfg hook for the active representation should dump
333 : representation-specific information. */
334 :
335 : void
336 312649 : dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
337 : {
338 312649 : if (flags & TDF_BLOCKS)
339 47979 : dump_bb_info (outf, bb, indent, flags, true, false);
340 312649 : if (cfg_hooks->dump_bb)
341 312649 : cfg_hooks->dump_bb (outf, bb, indent, flags);
342 312649 : if (flags & TDF_BLOCKS)
343 47979 : dump_bb_info (outf, bb, indent, flags, false, true);
344 312649 : fputc ('\n', outf);
345 312649 : }
346 :
347 : DEBUG_FUNCTION void
348 0 : debug (basic_block_def &ref)
349 : {
350 0 : dump_bb (stderr, &ref, 0, TDF_NONE);
351 0 : }
352 :
353 : DEBUG_FUNCTION void
354 0 : debug (basic_block_def *ptr)
355 : {
356 0 : if (ptr)
357 0 : debug (*ptr);
358 : else
359 0 : fprintf (stderr, "<nil>\n");
360 0 : }
361 :
362 : static void
363 0 : debug_slim (basic_block ptr)
364 : {
365 0 : fprintf (stderr, "<basic_block %p (%d)>", (void *) ptr, ptr->index);
366 0 : }
367 :
368 0 : DEFINE_DEBUG_VEC (basic_block_def *)
369 0 : DEFINE_DEBUG_HASH_SET (basic_block_def *)
370 :
371 : /* Dumps basic block BB to pretty-printer PP, for use as a label of
372 : a DOT graph record-node. The implementation of this hook is
373 : expected to write the label to the stream that is attached to PP.
374 : Field separators between instructions are pipe characters printed
375 : verbatim. Instructions should be written with some characters
376 : escaped, using pp_write_text_as_dot_label_to_stream(). */
377 :
378 : void
379 450 : dump_bb_for_graph (pretty_printer *pp, basic_block bb)
380 : {
381 450 : if (!cfg_hooks->dump_bb_for_graph)
382 0 : internal_error ("%s does not support dump_bb_for_graph",
383 : current_ir_name ());
384 : /* TODO: Add pretty printer for counter. */
385 450 : if (bb->count.initialized_p ())
386 351 : pp_printf (pp, "COUNT:" "%" PRId64, bb->count.to_gcov_type ());
387 450 : pp_write_text_to_stream (pp);
388 450 : if (!(dump_flags & TDF_SLIM))
389 450 : cfg_hooks->dump_bb_for_graph (pp, bb);
390 450 : }
391 :
392 : void
393 540 : dump_bb_as_sarif_properties (diagnostics::sarif_builder *builder,
394 : json::object &output_bag,
395 : basic_block bb)
396 : {
397 540 : if (!cfg_hooks->dump_bb_for_graph)
398 0 : internal_error ("%s does not support dump_bb_as_sarif_properties",
399 : current_ir_name ());
400 540 : namespace bb_property_names = custom_sarif_properties::cfg::basic_block;
401 540 : if (bb->index == ENTRY_BLOCK)
402 90 : output_bag.set_string (bb_property_names::kind, "entry");
403 450 : else if (bb->index == EXIT_BLOCK)
404 90 : output_bag.set_string (bb_property_names::kind, "exit");
405 360 : else if (BB_PARTITION (bb) == BB_HOT_PARTITION)
406 0 : output_bag.set_string (bb_property_names::kind, "hot");
407 360 : else if (BB_PARTITION (bb) == BB_COLD_PARTITION)
408 0 : output_bag.set_string (bb_property_names::kind, "cold");
409 540 : if (bb->count.initialized_p ())
410 : {
411 0 : pretty_printer pp;
412 0 : pp_printf (&pp, "%" PRId64, bb->count.to_gcov_type ());
413 0 : output_bag.set_string (bb_property_names::count,
414 : pp_formatted_text (&pp));
415 0 : }
416 540 : cfg_hooks->dump_bb_as_sarif_properties (builder, output_bag, bb);
417 540 : }
418 :
419 : /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
420 : void
421 291 : dump_flow_info (FILE *file, dump_flags_t flags)
422 : {
423 291 : basic_block bb;
424 :
425 291 : fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun),
426 291 : n_edges_for_fn (cfun));
427 2612 : FOR_ALL_BB_FN (bb, cfun)
428 2321 : dump_bb (file, bb, 0, flags);
429 :
430 291 : putc ('\n', file);
431 291 : }
432 :
433 : /* Like above, but dump to stderr. To be called from debuggers. */
434 : void debug_flow_info (void);
435 : DEBUG_FUNCTION void
436 0 : debug_flow_info (void)
437 : {
438 0 : dump_flow_info (stderr, TDF_DETAILS);
439 0 : }
440 :
441 : /* Redirect edge E to the given basic block DEST and update underlying program
442 : representation. Returns edge representing redirected branch (that may not
443 : be equivalent to E in the case of duplicate edges being removed) or NULL
444 : if edge is not easily redirectable for whatever reason. */
445 :
446 : edge
447 77134867 : redirect_edge_and_branch (edge e, basic_block dest)
448 : {
449 77134867 : edge ret;
450 :
451 77134867 : if (!cfg_hooks->redirect_edge_and_branch)
452 0 : internal_error ("%s does not support redirect_edge_and_branch",
453 : current_ir_name ());
454 :
455 77134867 : ret = cfg_hooks->redirect_edge_and_branch (e, dest);
456 :
457 : /* If RET != E, then either the redirection failed, or the edge E
458 : was removed since RET already lead to the same destination. */
459 77134867 : if (current_loops != NULL && ret == e)
460 64205419 : rescan_loop_exit (e, false, false);
461 :
462 77134867 : return ret;
463 : }
464 :
465 : /* Returns true if it is possible to remove the edge E by redirecting it
466 : to the destination of the other edge going from its source. */
467 :
468 : bool
469 458664 : can_remove_branch_p (const_edge e)
470 : {
471 458664 : if (!cfg_hooks->can_remove_branch_p)
472 0 : internal_error ("%s does not support can_remove_branch_p",
473 : current_ir_name ());
474 :
475 458664 : if (EDGE_COUNT (e->src->succs) != 2)
476 : return false;
477 :
478 458664 : return cfg_hooks->can_remove_branch_p (e);
479 : }
480 :
481 : /* Removes E, by redirecting it to the destination of the other edge going
482 : from its source. Can_remove_branch_p must be true for E, hence this
483 : operation cannot fail. */
484 :
485 : void
486 458723 : remove_branch (edge e)
487 : {
488 458723 : edge other;
489 458723 : basic_block src = e->src;
490 458723 : int irr;
491 :
492 458723 : gcc_assert (EDGE_COUNT (e->src->succs) == 2);
493 :
494 458723 : other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
495 458723 : irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
496 :
497 458723 : e = redirect_edge_and_branch (e, other->dest);
498 458723 : gcc_assert (e != NULL);
499 :
500 458723 : e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
501 458723 : e->flags |= irr;
502 458723 : }
503 :
504 : /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
505 :
506 : void
507 88164387 : remove_edge (edge e)
508 : {
509 88164387 : if (current_loops != NULL)
510 : {
511 78639995 : rescan_loop_exit (e, false, true);
512 :
513 : /* Removal of an edge inside an irreducible region or which leads
514 : to an irreducible region can turn the region into a natural loop.
515 : In that case, ask for the loop structure fixups.
516 :
517 : FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
518 : set, so always ask for fixups when removing an edge in that case. */
519 78639995 : if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
520 8288819 : || (e->flags & EDGE_IRREDUCIBLE_LOOP)
521 86925283 : || (e->dest->flags & BB_IRREDUCIBLE_LOOP))
522 70355531 : loops_state_set (LOOPS_NEED_FIXUP);
523 : }
524 :
525 : /* This is probably not needed, but it doesn't hurt. */
526 : /* FIXME: This should be called via a remove_edge hook. */
527 88164387 : if (current_ir_type () == IR_GIMPLE)
528 71592333 : redirect_edge_var_map_clear (e);
529 :
530 88164387 : remove_edge_raw (e);
531 88164387 : }
532 :
533 : /* Like redirect_edge_succ but avoid possible duplicate edge. */
534 :
535 : edge
536 82871138 : redirect_edge_succ_nodup (edge e, basic_block new_succ)
537 : {
538 82871138 : edge s;
539 :
540 82871138 : s = find_edge (e->src, new_succ);
541 82871138 : if (s && s != e)
542 : {
543 447184 : s->flags |= e->flags;
544 447184 : s->probability += e->probability;
545 : /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
546 447184 : redirect_edge_var_map_dup (s, e);
547 447184 : remove_edge (e);
548 447184 : e = s;
549 : }
550 : else
551 82423954 : redirect_edge_succ (e, new_succ);
552 :
553 82871138 : return e;
554 : }
555 :
556 : /* Redirect the edge E to basic block DEST even if it requires creating
557 : of a new basic block; then it returns the newly created basic block.
558 : Aborts when redirection is impossible. */
559 :
560 : basic_block
561 9511404 : redirect_edge_and_branch_force (edge e, basic_block dest)
562 : {
563 9511404 : basic_block ret, src = e->src;
564 :
565 9511404 : if (!cfg_hooks->redirect_edge_and_branch_force)
566 0 : internal_error ("%s does not support redirect_edge_and_branch_force",
567 : current_ir_name ());
568 :
569 9511404 : if (current_loops != NULL)
570 7783959 : rescan_loop_exit (e, false, true);
571 :
572 9511404 : ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
573 :
574 9511404 : if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
575 44107 : set_immediate_dominator (CDI_DOMINATORS, ret, src);
576 :
577 9511404 : if (current_loops != NULL)
578 : {
579 7783959 : if (ret != NULL)
580 : {
581 4 : class loop *loop
582 4 : = find_common_loop (single_pred (ret)->loop_father,
583 4 : single_succ (ret)->loop_father);
584 4 : add_bb_to_loop (ret, loop);
585 : }
586 7783955 : else if (find_edge (src, dest) == e)
587 7783953 : rescan_loop_exit (e, true, false);
588 : }
589 :
590 9511404 : return ret;
591 : }
592 :
593 : /* Splits basic block BB after the specified instruction I (but at least after
594 : the labels). If I is NULL, splits just after labels. The newly created edge
595 : is returned. The new basic block is created just after the old one. */
596 :
597 : static edge
598 9116794 : split_block_1 (basic_block bb, void *i)
599 : {
600 9116794 : basic_block new_bb;
601 9116794 : edge res;
602 :
603 9116794 : if (!cfg_hooks->split_block)
604 0 : internal_error ("%s does not support split_block", current_ir_name ());
605 :
606 9116794 : new_bb = cfg_hooks->split_block (bb, i);
607 9116794 : if (!new_bb)
608 : return NULL;
609 :
610 9116794 : new_bb->count = bb->count;
611 :
612 9116794 : if (dom_info_available_p (CDI_DOMINATORS))
613 : {
614 691563 : redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
615 691563 : set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
616 : }
617 :
618 9116794 : if (current_loops != NULL)
619 : {
620 8146165 : edge_iterator ei;
621 8146165 : edge e;
622 8146165 : add_bb_to_loop (new_bb, bb->loop_father);
623 : /* Identify all loops bb may have been the latch of and adjust them. */
624 20092891 : FOR_EACH_EDGE (e, ei, new_bb->succs)
625 11946726 : if (e->dest->loop_father->latch == bb)
626 130625 : e->dest->loop_father->latch = new_bb;
627 : }
628 :
629 9116794 : res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
630 :
631 9116794 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
632 : {
633 6981 : new_bb->flags |= BB_IRREDUCIBLE_LOOP;
634 6981 : res->flags |= EDGE_IRREDUCIBLE_LOOP;
635 : }
636 :
637 : return res;
638 : }
639 :
640 : edge
641 5952561 : split_block (basic_block bb, gimple *i)
642 : {
643 5952561 : return split_block_1 (bb, i);
644 : }
645 :
646 : edge
647 3042725 : split_block (basic_block bb, rtx i)
648 : {
649 3042725 : return split_block_1 (bb, i);
650 : }
651 :
652 : /* Splits block BB just after labels. The newly created edge is returned. */
653 :
654 : edge
655 121508 : split_block_after_labels (basic_block bb)
656 : {
657 121508 : return split_block_1 (bb, NULL);
658 : }
659 :
660 : /* Moves block BB immediately after block AFTER. Returns false if the
661 : movement was impossible. */
662 :
663 : bool
664 24977740 : move_block_after (basic_block bb, basic_block after)
665 : {
666 24977740 : bool ret;
667 :
668 24977740 : if (!cfg_hooks->move_block_after)
669 0 : internal_error ("%s does not support move_block_after",
670 : current_ir_name ());
671 :
672 24977740 : ret = cfg_hooks->move_block_after (bb, after);
673 :
674 24977740 : return ret;
675 : }
676 :
677 : /* Deletes the basic block BB. */
678 :
679 : void
680 44222610 : delete_basic_block (basic_block bb)
681 : {
682 44222610 : if (!cfg_hooks->delete_basic_block)
683 0 : internal_error ("%s does not support delete_basic_block",
684 : current_ir_name ());
685 :
686 44222610 : cfg_hooks->delete_basic_block (bb);
687 :
688 44222610 : if (current_loops != NULL)
689 : {
690 39019093 : class loop *loop = bb->loop_father;
691 :
692 : /* If we remove the header or the latch of a loop, mark the loop for
693 : removal. */
694 39019093 : if (loop->latch == bb
695 38813463 : || loop->header == bb)
696 249102 : mark_loop_for_removal (loop);
697 :
698 39019093 : remove_bb_from_loops (bb);
699 : }
700 :
701 : /* Remove the edges into and out of this block. Note that there may
702 : indeed be edges in, if we are removing an unreachable loop. */
703 89138824 : while (EDGE_COUNT (bb->preds) != 0)
704 689739 : remove_edge (EDGE_PRED (bb, 0));
705 51182646 : while (EDGE_COUNT (bb->succs) != 0)
706 6960036 : remove_edge (EDGE_SUCC (bb, 0));
707 :
708 44222610 : if (dom_info_available_p (CDI_DOMINATORS))
709 30868308 : delete_from_dominance_info (CDI_DOMINATORS, bb);
710 44222610 : if (dom_info_available_p (CDI_POST_DOMINATORS))
711 447951 : delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
712 :
713 : /* Remove the basic block from the array. */
714 44222610 : expunge_block (bb);
715 44222610 : }
716 :
717 : /* Splits edge E and returns the newly created basic block. */
718 :
719 : basic_block
720 30688449 : split_edge (edge e)
721 : {
722 30688449 : basic_block ret;
723 30688449 : profile_count count = e->count ();
724 30688449 : edge f;
725 30688449 : bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
726 30688449 : bool back = (e->flags & EDGE_DFS_BACK) != 0;
727 30688449 : class loop *loop;
728 30688449 : basic_block src = e->src, dest = e->dest;
729 :
730 30688449 : if (!cfg_hooks->split_edge)
731 0 : internal_error ("%s does not support split_edge", current_ir_name ());
732 :
733 30688449 : if (current_loops != NULL)
734 29190460 : rescan_loop_exit (e, false, true);
735 :
736 30688449 : ret = cfg_hooks->split_edge (e);
737 30688449 : ret->count = count;
738 30688449 : single_succ_edge (ret)->probability = profile_probability::always ();
739 :
740 30688449 : if (irr)
741 : {
742 79732 : ret->flags |= BB_IRREDUCIBLE_LOOP;
743 79732 : single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
744 79732 : single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
745 : }
746 30688449 : if (back)
747 : {
748 2094090 : single_pred_edge (ret)->flags &= ~EDGE_DFS_BACK;
749 2094090 : single_succ_edge (ret)->flags |= EDGE_DFS_BACK;
750 : }
751 :
752 30688449 : if (dom_info_available_p (CDI_DOMINATORS))
753 26409443 : set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
754 :
755 30688449 : if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
756 : {
757 : /* There are two cases:
758 :
759 : If the immediate dominator of e->dest is not e->src, it
760 : remains unchanged.
761 :
762 : If immediate dominator of e->dest is e->src, it may become
763 : ret, provided that all other predecessors of e->dest are
764 : dominated by e->dest. */
765 :
766 26409443 : if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
767 26409443 : == single_pred (ret))
768 : {
769 9149521 : edge_iterator ei;
770 20062864 : FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
771 : {
772 15800108 : if (f == single_succ_edge (ret))
773 6909325 : continue;
774 :
775 8890783 : if (!dominated_by_p (CDI_DOMINATORS, f->src,
776 8890783 : single_succ (ret)))
777 : break;
778 : }
779 :
780 9149521 : if (!f)
781 4262756 : set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
782 : }
783 : }
784 :
785 30688449 : if (current_loops != NULL)
786 : {
787 29190460 : loop = find_common_loop (src->loop_father, dest->loop_father);
788 29190460 : add_bb_to_loop (ret, loop);
789 :
790 : /* If we split the latch edge of loop adjust the latch block. */
791 29190460 : if (loop->latch == src
792 6460562 : && loop->header == dest)
793 6459855 : loop->latch = ret;
794 : }
795 :
796 30688449 : return ret;
797 : }
798 :
799 : /* Creates a new basic block just after the basic block AFTER.
800 : HEAD and END are the first and the last statement belonging
801 : to the block. If both are NULL, an empty block is created. */
802 :
803 : static basic_block
804 87534403 : create_basic_block_1 (void *head, void *end, basic_block after)
805 : {
806 87534403 : basic_block ret;
807 :
808 87534403 : if (!cfg_hooks->create_basic_block)
809 0 : internal_error ("%s does not support create_basic_block",
810 : current_ir_name ());
811 :
812 87534403 : ret = cfg_hooks->create_basic_block (head, end, after);
813 :
814 87534403 : if (dom_info_available_p (CDI_DOMINATORS))
815 32318758 : add_to_dominance_info (CDI_DOMINATORS, ret);
816 87534403 : if (dom_info_available_p (CDI_POST_DOMINATORS))
817 169194 : add_to_dominance_info (CDI_POST_DOMINATORS, ret);
818 :
819 87534403 : return ret;
820 : }
821 :
822 : basic_block
823 37887621 : create_basic_block (gimple_seq seq, basic_block after)
824 : {
825 37887621 : return create_basic_block_1 (seq, NULL, after);
826 : }
827 :
828 : basic_block
829 13466106 : create_basic_block (rtx head, rtx end, basic_block after)
830 : {
831 13466106 : return create_basic_block_1 (head, end, after);
832 : }
833 :
834 :
835 : /* Creates an empty basic block just after basic block AFTER. */
836 :
837 : basic_block
838 36180676 : create_empty_bb (basic_block after)
839 : {
840 36180676 : return create_basic_block_1 (NULL, NULL, after);
841 : }
842 :
843 : /* Checks whether we may merge blocks BB1 and BB2. */
844 :
845 : bool
846 440946238 : can_merge_blocks_p (basic_block bb1, basic_block bb2)
847 : {
848 440946238 : bool ret;
849 :
850 440946238 : if (!cfg_hooks->can_merge_blocks_p)
851 0 : internal_error ("%s does not support can_merge_blocks_p",
852 : current_ir_name ());
853 :
854 440946238 : ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
855 :
856 440946238 : return ret;
857 : }
858 :
859 : void
860 6468871 : predict_edge (edge e, enum br_predictor predictor, int probability)
861 : {
862 6468871 : if (!cfg_hooks->predict_edge)
863 0 : internal_error ("%s does not support predict_edge",
864 : current_ir_name ());
865 :
866 6468871 : cfg_hooks->predict_edge (e, predictor, probability);
867 6468871 : }
868 :
869 : bool
870 3230364 : predicted_by_p (const_basic_block bb, enum br_predictor predictor)
871 : {
872 3230364 : if (!cfg_hooks->predict_edge)
873 0 : internal_error ("%s does not support predicted_by_p",
874 : current_ir_name ());
875 :
876 3230364 : return cfg_hooks->predicted_by_p (bb, predictor);
877 : }
878 :
879 : /* Merges basic block B into basic block A. */
880 :
881 : void
882 22945090 : merge_blocks (basic_block a, basic_block b)
883 : {
884 22945090 : edge e;
885 22945090 : edge_iterator ei;
886 :
887 22945090 : if (!cfg_hooks->merge_blocks)
888 0 : internal_error ("%s does not support merge_blocks",
889 : current_ir_name ());
890 :
891 : /* Pick the more reliable count. If both qualities agrees, pick the larger
892 : one since turning mistakely hot code to cold is more harmful. */
893 22945090 : if (!a->count.initialized_p ())
894 12411695 : a->count = b->count;
895 10533395 : else if (a->count.quality () < b->count.quality ())
896 5945 : a->count = b->count;
897 10527450 : else if (a->count.quality () == b->count.quality ())
898 10521475 : a->count = profile_count::max_prefer_initialized (a->count, b->count);
899 :
900 22945090 : cfg_hooks->merge_blocks (a, b);
901 :
902 22945090 : if (current_loops != NULL)
903 : {
904 : /* If the block we merge into is a loop header do nothing unless ... */
905 19615220 : if (a->loop_father->header == a)
906 : {
907 : /* ... we merge two loop headers, in which case we kill
908 : the inner loop. */
909 651962 : if (b->loop_father->header == b)
910 428 : mark_loop_for_removal (b->loop_father);
911 : }
912 : /* If we merge a loop header into its predecessor, update the loop
913 : structure. */
914 18963258 : else if (b->loop_father->header == b)
915 : {
916 174 : remove_bb_from_loops (a);
917 174 : add_bb_to_loop (a, b->loop_father);
918 174 : a->loop_father->header = a;
919 : }
920 : /* If we merge a loop latch into its predecessor, update the loop
921 : structure. */
922 19615220 : if (b->loop_father->latch
923 19469501 : && b->loop_father->latch == b)
924 261046 : b->loop_father->latch = a;
925 19615220 : remove_bb_from_loops (b);
926 : }
927 :
928 : /* Normally there should only be one successor of A and that is B, but
929 : partway though the merge of blocks for conditional_execution we'll
930 : be merging a TEST block with THEN and ELSE successors. Free the
931 : whole lot of them and hope the caller knows what they're doing. */
932 :
933 45890180 : while (EDGE_COUNT (a->succs) != 0)
934 22945090 : remove_edge (EDGE_SUCC (a, 0));
935 :
936 : /* Adjust the edges out of B for the new owner. */
937 52115770 : FOR_EACH_EDGE (e, ei, b->succs)
938 : {
939 29170680 : e->src = a;
940 29170680 : if (current_loops != NULL)
941 : {
942 : /* If b was a latch, a now is. */
943 25427787 : if (e->dest->loop_father->latch == b)
944 846 : e->dest->loop_father->latch = a;
945 25427787 : rescan_loop_exit (e, true, false);
946 : }
947 : }
948 22945090 : a->succs = b->succs;
949 22945090 : a->flags |= b->flags;
950 :
951 : /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
952 22945090 : b->preds = b->succs = NULL;
953 :
954 22945090 : if (dom_info_available_p (CDI_DOMINATORS))
955 18220581 : redirect_immediate_dominators (CDI_DOMINATORS, b, a);
956 :
957 22945090 : if (dom_info_available_p (CDI_DOMINATORS))
958 18220581 : delete_from_dominance_info (CDI_DOMINATORS, b);
959 22945090 : if (dom_info_available_p (CDI_POST_DOMINATORS))
960 135045 : delete_from_dominance_info (CDI_POST_DOMINATORS, b);
961 :
962 22945090 : expunge_block (b);
963 22945090 : }
964 :
965 : /* Split BB into entry part and the rest (the rest is the newly created block).
966 : Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
967 : part. Returns the edge connecting the entry part to the rest.
968 : DATA gets passed on to REDIRECT_EDGE_P. */
969 :
970 : edge
971 95611 : make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge, void*), void *data)
972 : {
973 95611 : edge e, fallthru;
974 95611 : edge_iterator ei;
975 95611 : basic_block dummy, jump;
976 95611 : class loop *loop, *ploop, *cloop;
977 :
978 95611 : if (!cfg_hooks->make_forwarder_block)
979 0 : internal_error ("%s does not support make_forwarder_block",
980 : current_ir_name ());
981 :
982 95611 : fallthru = split_block_after_labels (bb);
983 95611 : dummy = fallthru->src;
984 95611 : dummy->count = profile_count::zero ();
985 95611 : bb = fallthru->dest;
986 :
987 : /* Redirect back edges we want to keep. */
988 413765 : for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
989 : {
990 318154 : basic_block e_src;
991 :
992 318154 : if (redirect_edge_p (e, data))
993 : {
994 219353 : dummy->count += e->count ();
995 219353 : ei_next (&ei);
996 219353 : continue;
997 : }
998 :
999 98801 : e_src = e->src;
1000 98801 : jump = redirect_edge_and_branch_force (e, bb);
1001 98801 : if (jump != NULL)
1002 : {
1003 : /* If we redirected the loop latch edge, the JUMP block now acts like
1004 : the new latch of the loop. */
1005 3 : if (current_loops != NULL
1006 3 : && dummy->loop_father != NULL
1007 3 : && dummy->loop_father->header == dummy
1008 3 : && dummy->loop_father->latch == e_src)
1009 0 : dummy->loop_father->latch = jump;
1010 : }
1011 : }
1012 :
1013 95611 : if (dom_info_available_p (CDI_DOMINATORS))
1014 : {
1015 53579 : vec<basic_block> doms_to_fix;
1016 53579 : doms_to_fix.create (2);
1017 53579 : doms_to_fix.quick_push (dummy);
1018 53579 : doms_to_fix.quick_push (bb);
1019 53579 : iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
1020 53579 : doms_to_fix.release ();
1021 : }
1022 :
1023 95611 : if (current_loops != NULL)
1024 : {
1025 : /* If we do not split a loop header, then both blocks belong to the
1026 : same loop. In case we split loop header and do not redirect the
1027 : latch edge to DUMMY, then DUMMY belongs to the outer loop, and
1028 : BB becomes the new header. If latch is not recorded for the loop,
1029 : we leave this updating on the caller (this may only happen during
1030 : loop analysis). */
1031 95611 : loop = dummy->loop_father;
1032 95611 : if (loop->header == dummy
1033 95405 : && loop->latch != NULL
1034 162984 : && find_edge (loop->latch, dummy) == NULL)
1035 : {
1036 67340 : remove_bb_from_loops (dummy);
1037 67340 : loop->header = bb;
1038 :
1039 67340 : cloop = loop;
1040 219142 : FOR_EACH_EDGE (e, ei, dummy->preds)
1041 : {
1042 151802 : cloop = find_common_loop (cloop, e->src->loop_father);
1043 : }
1044 67340 : add_bb_to_loop (dummy, cloop);
1045 : }
1046 :
1047 : /* In case we split loop latch, update it. */
1048 321230 : for (ploop = loop; ploop; ploop = loop_outer (ploop))
1049 225619 : if (ploop->latch == dummy)
1050 0 : ploop->latch = bb;
1051 : }
1052 :
1053 95611 : cfg_hooks->make_forwarder_block (fallthru);
1054 :
1055 95611 : return fallthru;
1056 : }
1057 :
1058 : /* Try to make the edge fallthru. */
1059 :
1060 : void
1061 885207 : tidy_fallthru_edge (edge e)
1062 : {
1063 885207 : if (cfg_hooks->tidy_fallthru_edge)
1064 885207 : cfg_hooks->tidy_fallthru_edge (e);
1065 885207 : }
1066 :
1067 : /* Fix up edges that now fall through, or rather should now fall through
1068 : but previously required a jump around now deleted blocks. Simplify
1069 : the search by only examining blocks numerically adjacent, since this
1070 : is how they were created.
1071 :
1072 : ??? This routine is currently RTL specific. */
1073 :
1074 : void
1075 484194 : tidy_fallthru_edges (void)
1076 : {
1077 484194 : basic_block b, c;
1078 :
1079 484194 : if (!cfg_hooks->tidy_fallthru_edge)
1080 : return;
1081 :
1082 133928 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1083 : return;
1084 :
1085 4613268 : FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
1086 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, next_bb)
1087 : {
1088 4479340 : edge s;
1089 :
1090 4479340 : c = b->next_bb;
1091 :
1092 : /* We care about simple conditional or unconditional jumps with
1093 : a single successor.
1094 :
1095 : If we had a conditional branch to the next instruction when
1096 : CFG was built, then there will only be one out edge for the
1097 : block which ended with the conditional branch (since we do
1098 : not create duplicate edges).
1099 :
1100 : Furthermore, the edge will be marked as a fallthru because we
1101 : merge the flags for the duplicate edges. So we do not want to
1102 : check that the edge is not a FALLTHRU edge. */
1103 :
1104 6600280 : if (single_succ_p (b))
1105 : {
1106 2120940 : s = single_succ_edge (b);
1107 2120940 : if (! (s->flags & EDGE_COMPLEX)
1108 2030256 : && s->dest == c
1109 3024643 : && !(JUMP_P (BB_END (b)) && CROSSING_JUMP_P (BB_END (b))))
1110 877678 : tidy_fallthru_edge (s);
1111 : }
1112 : }
1113 : }
1114 :
1115 : /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1116 : (and possibly create new basic block) to make edge non-fallthru.
1117 : Return newly created BB or NULL if none. */
1118 :
1119 : basic_block
1120 777704 : force_nonfallthru (edge e)
1121 : {
1122 777704 : basic_block ret, src = e->src;
1123 :
1124 777704 : if (!cfg_hooks->force_nonfallthru)
1125 0 : internal_error ("%s does not support force_nonfallthru",
1126 : current_ir_name ());
1127 :
1128 777704 : ret = cfg_hooks->force_nonfallthru (e);
1129 777704 : if (ret != NULL)
1130 : {
1131 183640 : if (dom_info_available_p (CDI_DOMINATORS))
1132 9912 : set_immediate_dominator (CDI_DOMINATORS, ret, src);
1133 :
1134 183640 : if (current_loops != NULL)
1135 : {
1136 67906 : basic_block pred = single_pred (ret);
1137 67906 : basic_block succ = single_succ (ret);
1138 67906 : class loop *loop
1139 67906 : = find_common_loop (pred->loop_father, succ->loop_father);
1140 67906 : rescan_loop_exit (e, false, true);
1141 67906 : add_bb_to_loop (ret, loop);
1142 :
1143 : /* If we split the latch edge of loop adjust the latch block. */
1144 67906 : if (loop->latch == pred
1145 5057 : && loop->header == succ)
1146 5057 : loop->latch = ret;
1147 : }
1148 : }
1149 :
1150 777704 : return ret;
1151 : }
1152 :
1153 : /* Returns true if we can duplicate basic block BB. */
1154 :
1155 : bool
1156 24836518 : can_duplicate_block_p (const_basic_block bb)
1157 : {
1158 24836518 : if (!cfg_hooks->can_duplicate_block_p)
1159 0 : internal_error ("%s does not support can_duplicate_block_p",
1160 : current_ir_name ());
1161 :
1162 24836518 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1163 : return false;
1164 :
1165 24836518 : return cfg_hooks->can_duplicate_block_p (bb);
1166 : }
1167 :
1168 : /* Returns true if we can duplicate E's destination with E redirected to the
1169 : copy. */
1170 :
1171 : bool
1172 6410600 : can_duplicate_block_on_edge_p (edge e)
1173 : {
1174 6410600 : basic_block bb = e->dest;
1175 :
1176 6410600 : if (!can_duplicate_block_p (bb))
1177 : return false;
1178 :
1179 6410600 : if (e->flags & EDGE_COMPLEX)
1180 : return false;
1181 :
1182 6410600 : edge s;
1183 6410600 : edge_iterator ei;
1184 19037284 : FOR_EACH_EDGE (s, ei, bb->succs)
1185 12627091 : if (s->flags & EDGE_COMPLEX)
1186 : return false;
1187 :
1188 : return true;
1189 : }
1190 :
1191 : /* Duplicate basic block BB, place it after AFTER (if non-null) and redirect
1192 : edge E to it (if non-null). Return the new basic block.
1193 :
1194 : If BB contains a returns_twice call, the caller is responsible for recreating
1195 : incoming abnormal edges corresponding to the "second return" for the copy.
1196 : gimple_can_duplicate_bb_p rejects such blocks, while RTL likes to live
1197 : dangerously.
1198 :
1199 : If BB has incoming abnormal edges for some other reason, their destinations
1200 : should be tied to label(s) of the original BB and not the copy. */
1201 :
1202 : basic_block
1203 4814902 : duplicate_block (basic_block bb, edge e, basic_block after, copy_bb_data *id)
1204 : {
1205 4814902 : edge s, n;
1206 4814902 : basic_block new_bb;
1207 5146077 : profile_count new_count = e ? e->count (): profile_count::uninitialized ();
1208 4814902 : edge_iterator ei;
1209 :
1210 4814902 : if (!cfg_hooks->duplicate_block)
1211 0 : internal_error ("%s does not support duplicate_block",
1212 : current_ir_name ());
1213 :
1214 4814902 : if (bb->count < new_count)
1215 1853 : new_count = bb->count;
1216 :
1217 4814902 : gcc_checking_assert (can_duplicate_block_p (bb));
1218 :
1219 4814902 : new_bb = cfg_hooks->duplicate_block (bb, id);
1220 4814902 : if (after)
1221 4489510 : move_block_after (new_bb, after);
1222 :
1223 4814902 : new_bb->flags = (bb->flags & ~BB_DUPLICATED);
1224 13286921 : FOR_EACH_EDGE (s, ei, bb->succs)
1225 : {
1226 : /* Since we are creating edges from a new block to successors
1227 : of another block (which therefore are known to be disjoint), there
1228 : is no need to actually check for duplicated edges. */
1229 8472019 : n = unchecked_make_edge (new_bb, s->dest, s->flags);
1230 8472019 : n->probability = s->probability;
1231 8472019 : n->aux = s->aux;
1232 : }
1233 :
1234 4814902 : if (e)
1235 : {
1236 331175 : new_bb->count = new_count;
1237 331175 : bb->count -= new_count;
1238 :
1239 331175 : redirect_edge_and_branch_force (e, new_bb);
1240 : }
1241 : else
1242 4483727 : new_bb->count = bb->count;
1243 :
1244 4814902 : set_bb_original (new_bb, bb);
1245 4814902 : set_bb_copy (bb, new_bb);
1246 :
1247 : /* Add the new block to the copy of the loop of BB, or directly to the loop
1248 : of BB if the loop is not being copied. */
1249 4814902 : if (current_loops != NULL)
1250 : {
1251 4508701 : class loop *cloop = bb->loop_father;
1252 4508701 : class loop *copy = get_loop_copy (cloop);
1253 : /* If we copied the loop header block but not the loop
1254 : we have created a loop with multiple entries. Ditch the loop,
1255 : add the new block to the outer loop and arrange for a fixup. */
1256 4508701 : if (!copy
1257 387341 : && cloop->header == bb)
1258 : {
1259 2748 : add_bb_to_loop (new_bb, loop_outer (cloop));
1260 2748 : mark_loop_for_removal (cloop);
1261 : }
1262 : else
1263 : {
1264 4505953 : add_bb_to_loop (new_bb, copy ? copy : cloop);
1265 : /* If we copied the loop latch block but not the loop, adjust
1266 : loop state. */
1267 4505953 : if (!copy
1268 384593 : && cloop->latch == bb)
1269 : {
1270 1654 : cloop->latch = NULL;
1271 1654 : loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1272 : }
1273 : }
1274 : }
1275 :
1276 : /* Skip if copy_bbs assigns one copyid for the whole region. */
1277 4814902 : if (!id || !id->skip_copyid)
1278 : {
1279 656367 : location_t loc = copyid_location_from_bb (bb);
1280 656367 : if (loc != UNKNOWN_LOCATION)
1281 628645 : assign_discriminators_to_bb (new_bb, 0,
1282 : allocate_copyid_base (loc, 1));
1283 : }
1284 :
1285 4814902 : return new_bb;
1286 : }
1287 :
1288 : /* Return 1 if BB ends with a call, possibly followed by some
1289 : instructions that must stay with the call, 0 otherwise. */
1290 :
1291 : bool
1292 10086154 : block_ends_with_call_p (basic_block bb)
1293 : {
1294 10086154 : if (!cfg_hooks->block_ends_with_call_p)
1295 0 : internal_error ("%s does not support block_ends_with_call_p",
1296 : current_ir_name ());
1297 :
1298 10086154 : return (cfg_hooks->block_ends_with_call_p) (bb);
1299 : }
1300 :
1301 : /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1302 :
1303 : bool
1304 1804 : block_ends_with_condjump_p (const_basic_block bb)
1305 : {
1306 1804 : if (!cfg_hooks->block_ends_with_condjump_p)
1307 0 : internal_error ("%s does not support block_ends_with_condjump_p",
1308 : current_ir_name ());
1309 :
1310 1804 : return (cfg_hooks->block_ends_with_condjump_p) (bb);
1311 : }
1312 :
1313 : /* Add fake edges to the function exit for any non constant and non noreturn
1314 : calls, volatile inline assembly in the bitmap of blocks specified by
1315 : BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1316 : that were split.
1317 :
1318 : The goal is to expose cases in which entering a basic block does not imply
1319 : that all subsequent instructions must be executed. */
1320 :
1321 : int
1322 3023 : flow_call_edges_add (sbitmap blocks)
1323 : {
1324 3023 : if (!cfg_hooks->flow_call_edges_add)
1325 0 : internal_error ("%s does not support flow_call_edges_add",
1326 : current_ir_name ());
1327 :
1328 3023 : return (cfg_hooks->flow_call_edges_add) (blocks);
1329 : }
1330 :
1331 : /* This function is called immediately after edge E is added to the
1332 : edge vector E->dest->preds. */
1333 :
1334 : void
1335 209780059 : execute_on_growing_pred (edge e)
1336 : {
1337 209780059 : if (! (e->dest->flags & BB_DUPLICATED)
1338 207418168 : && cfg_hooks->execute_on_growing_pred)
1339 165773965 : cfg_hooks->execute_on_growing_pred (e);
1340 209780059 : }
1341 :
1342 : /* This function is called immediately before edge E is removed from
1343 : the edge vector E->dest->preds. */
1344 :
1345 : void
1346 177141626 : execute_on_shrinking_pred (edge e)
1347 : {
1348 177141626 : if (! (e->dest->flags & BB_DUPLICATED)
1349 174779735 : && cfg_hooks->execute_on_shrinking_pred)
1350 135670565 : cfg_hooks->execute_on_shrinking_pred (e);
1351 177141626 : }
1352 :
1353 : /* This is used inside loop versioning when we want to insert
1354 : stmts/insns on the edges, which have a different behavior
1355 : in tree's and in RTL, so we made a CFG hook. */
1356 : void
1357 35766 : lv_flush_pending_stmts (edge e)
1358 : {
1359 35766 : if (cfg_hooks->flush_pending_stmts)
1360 35766 : cfg_hooks->flush_pending_stmts (e);
1361 35766 : }
1362 :
1363 : /* Loop versioning uses the duplicate_loop_body_to_header_edge to create
1364 : a new version of the loop basic-blocks, the parameters here are
1365 : exactly the same as in duplicate_loop_body_to_header_edge or
1366 : tree_duplicate_loop_body_to_header_edge; while in tree-ssa there is
1367 : additional work to maintain ssa information that's why there is
1368 : a need to call the tree_duplicate_loop_body_to_header_edge rather
1369 : than duplicate_loop_body_to_header_edge when we are in tree mode. */
1370 : bool
1371 35776 : cfg_hook_duplicate_loop_body_to_header_edge (class loop *loop, edge e,
1372 : unsigned int ndupl,
1373 : sbitmap wont_exit, edge orig,
1374 : vec<edge> *to_remove, int flags)
1375 : {
1376 35776 : gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_body_to_header_edge);
1377 35776 : return cfg_hooks->cfg_hook_duplicate_loop_body_to_header_edge (
1378 35776 : loop, e, ndupl, wont_exit, orig, to_remove, flags);
1379 : }
1380 :
1381 : /* Conditional jumps are represented differently in trees and RTL,
1382 : this hook takes a basic block that is known to have a cond jump
1383 : at its end and extracts the taken and not taken edges out of it
1384 : and store it in E1 and E2 respectively. */
1385 : void
1386 0 : extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1387 : {
1388 0 : gcc_assert (cfg_hooks->extract_cond_bb_edges);
1389 0 : cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1390 0 : }
1391 :
1392 : /* Responsible for updating the ssa info (PHI nodes) on the
1393 : new condition basic block that guards the versioned loop. */
1394 : void
1395 35766 : lv_adjust_loop_header_phi (basic_block first, basic_block second,
1396 : basic_block new_block, edge e)
1397 : {
1398 35766 : if (cfg_hooks->lv_adjust_loop_header_phi)
1399 35766 : cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1400 35766 : }
1401 :
1402 : /* Conditions in trees and RTL are different so we need
1403 : a different handling when we add the condition to the
1404 : versioning code. */
1405 : void
1406 35766 : lv_add_condition_to_bb (basic_block first, basic_block second,
1407 : basic_block new_block, void *cond)
1408 : {
1409 35766 : gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1410 35766 : cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1411 35766 : }
1412 :
1413 : /* Checks whether all N blocks in BBS array can be copied.
1414 :
1415 : PREVAILING_EXIT is as in copy_bbs. If non-NULL, the copy of its source
1416 : keeps only the prevailing edge, so the abnormal successor edges of that
1417 : block do not require redirection. */
1418 : bool
1419 3455427 : can_copy_bbs_p (basic_block *bbs, unsigned n, edge prevailing_exit)
1420 : {
1421 3455427 : unsigned i;
1422 3455427 : edge e;
1423 3455427 : int ret = true;
1424 :
1425 12345496 : for (i = 0; i < n; i++)
1426 8890069 : bbs[i]->flags |= BB_DUPLICATED;
1427 :
1428 : /* A prevailing edge jumping back into the region is not supported:
1429 : its copy would have to keep targeting the original block. */
1430 3455427 : if (prevailing_exit && (prevailing_exit->dest->flags & BB_DUPLICATED))
1431 : {
1432 1 : ret = false;
1433 1 : goto end;
1434 : }
1435 :
1436 12157300 : for (i = 0; i < n; i++)
1437 : {
1438 : /* In case we should redirect abnormal edge during duplication, fail.
1439 : However, the copy of PREVAILING_EXIT->src is exempt as its outgoing
1440 : edges are removed or left in place rather than redirected. */
1441 8714265 : edge_iterator ei;
1442 8714265 : if (!(prevailing_exit && bbs[i] == prevailing_exit->src))
1443 23214564 : FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1444 14509621 : if ((e->flags & EDGE_ABNORMAL)
1445 116834 : && (e->dest->flags & BB_DUPLICATED))
1446 : {
1447 9231 : ret = false;
1448 9231 : goto end;
1449 : }
1450 :
1451 8705034 : if (!can_duplicate_block_p (bbs[i]))
1452 : {
1453 3160 : ret = false;
1454 3160 : break;
1455 : }
1456 : }
1457 :
1458 3443035 : end:
1459 12345496 : for (i = 0; i < n; i++)
1460 8890069 : bbs[i]->flags &= ~BB_DUPLICATED;
1461 :
1462 3455427 : return ret;
1463 : }
1464 :
1465 : /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1466 : are placed into array NEW_BBS in the same order. Edges from basic blocks
1467 : in BBS are also duplicated and copies of those that lead into BBS are
1468 : redirected to appropriate newly created block. The function assigns bbs
1469 : into loops (copy of basic block bb is assigned to bb->loop_father->copy
1470 : loop, so this must be set up correctly in advance)
1471 :
1472 : If UPDATE_DOMINANCE is true then this function updates dominators locally
1473 : (LOOPS structure that contains the information about dominators is passed
1474 : to enable this), otherwise it does not update the dominator information
1475 : and it assumed that the caller will do this, perhaps by destroying and
1476 : recreating it instead of trying to do an incremental update like this
1477 : function does when update_dominance is true.
1478 :
1479 : BASE is the superloop to that basic block belongs; if its header or latch
1480 : is copied, we do not set the new blocks as header or latch.
1481 :
1482 : Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1483 : also in the same order.
1484 :
1485 : Newly created basic blocks are put after the basic block AFTER in the
1486 : instruction stream, and the order of the blocks in BBS array is preserved.
1487 :
1488 : If PREVAILING_EXIT is non-NULL, its source must be in BBS, and its
1489 : destination must not be: the copy of that block keeps only its edges to
1490 : PREVAILING_EXIT->dest, and the rest of its outgoing edges are removed. None
1491 : of its edges are redirected, which allows copying a region whose exit block
1492 : has abnormal successor edges into the region. It is the caller's
1493 : responsibility to remove or rewrite the copied block's control
1494 : statement. */
1495 :
1496 : void
1497 2528058 : copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1498 : edge *edges, unsigned num_edges, edge *new_edges,
1499 : class loop *base, basic_block after, bool update_dominance,
1500 : edge prevailing_exit)
1501 : {
1502 2528058 : unsigned i, j;
1503 2528058 : basic_block bb, new_bb, dom_bb;
1504 2528058 : edge e;
1505 2528058 : copy_bb_data id;
1506 :
1507 : /* One copyid for the region (not per BB). */
1508 2528058 : id.skip_copyid = true;
1509 :
1510 : /* Mark the blocks to be copied. This is used by edge creation hooks
1511 : to decide whether to reallocate PHI nodes capacity to avoid reallocating
1512 : PHIs in the set of source BBs. */
1513 6686593 : for (i = 0; i < n; i++)
1514 4158535 : bbs[i]->flags |= BB_DUPLICATED;
1515 :
1516 : /* A prevailing edge into the region would be redirected like any
1517 : other. We refuse this in can_copy_bbs_p. */
1518 2528058 : gcc_checking_assert (!prevailing_exit
1519 : || !(prevailing_exit->dest->flags & BB_DUPLICATED));
1520 :
1521 : /* Duplicate bbs, update dominators, assign bbs to loops. */
1522 6686593 : for (i = 0; i < n; i++)
1523 : {
1524 : /* Duplicate. */
1525 4158535 : bb = bbs[i];
1526 4158535 : new_bb = new_bbs[i] = duplicate_block (bb, NULL, after, &id);
1527 4158535 : after = new_bb;
1528 4158535 : if (bb->loop_father)
1529 : {
1530 : /* Possibly set loop header. */
1531 4158535 : if (bb->loop_father->header == bb && bb->loop_father != base)
1532 41497 : new_bb->loop_father->header = new_bb;
1533 : /* Or latch. */
1534 4158535 : if (bb->loop_father->latch == bb && bb->loop_father != base)
1535 41497 : new_bb->loop_father->latch = new_bb;
1536 : }
1537 : }
1538 :
1539 : /* Set dominators. */
1540 2528058 : if (update_dominance)
1541 : {
1542 3537375 : for (i = 0; i < n; i++)
1543 : {
1544 2343265 : bb = bbs[i];
1545 2343265 : new_bb = new_bbs[i];
1546 :
1547 2343265 : dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1548 2343265 : if (dom_bb->flags & BB_DUPLICATED)
1549 : {
1550 1149155 : dom_bb = get_bb_copy (dom_bb);
1551 1149155 : set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1552 : }
1553 : }
1554 : }
1555 :
1556 : /* Redirect edges. */
1557 6686593 : for (i = 0; i < n; i++)
1558 : {
1559 4158535 : edge_iterator ei;
1560 4158535 : new_bb = new_bbs[i];
1561 4158535 : bb = bbs[i];
1562 :
1563 11541959 : for (ei = ei_start (new_bb->succs); (e = ei_safe_edge (ei)); )
1564 : {
1565 : /* Remove the edges that do not prevail instead of
1566 : redirecting them. */
1567 7383424 : if (prevailing_exit && bb == prevailing_exit->src
1568 268 : && e->dest != prevailing_exit->dest)
1569 : {
1570 179 : remove_edge (e);
1571 179 : continue;
1572 : }
1573 7383245 : if (e->dest->flags & BB_DUPLICATED)
1574 2361887 : redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1575 7383245 : ei_next (&ei);
1576 : }
1577 : }
1578 4298705 : for (j = 0; j < num_edges; j++)
1579 : {
1580 1770647 : if (!edges[j])
1581 93702 : new_edges[j] = NULL;
1582 : else
1583 : {
1584 1676945 : basic_block src = edges[j]->src;
1585 1676945 : basic_block dest = edges[j]->dest;
1586 1676945 : if (src->flags & BB_DUPLICATED)
1587 1676945 : src = get_bb_copy (src);
1588 1676945 : if (dest->flags & BB_DUPLICATED)
1589 521781 : dest = get_bb_copy (dest);
1590 1676945 : new_edges[j] = find_edge (src, dest);
1591 : }
1592 : }
1593 :
1594 : /* Clear information about duplicates. */
1595 6686593 : for (i = 0; i < n; i++)
1596 4158535 : bbs[i]->flags &= ~BB_DUPLICATED;
1597 :
1598 : /* One copyid for the whole region, keyed off the first source block that
1599 : has a location. */
1600 : location_t loc = UNKNOWN_LOCATION;
1601 5194947 : for (i = 0; i < n && loc == UNKNOWN_LOCATION; i++)
1602 2666889 : loc = copyid_location_from_bb (bbs[i]);
1603 :
1604 2528058 : if (loc != UNKNOWN_LOCATION)
1605 : {
1606 2443519 : unsigned int copyid = allocate_copyid_base (loc, 1);
1607 8889379 : for (i = 0; i < n; i++)
1608 4002341 : assign_discriminators_to_bb (new_bbs[i], 0, copyid);
1609 : }
1610 2528058 : }
1611 :
1612 : /* Return true if BB contains only labels or non-executable
1613 : instructions */
1614 : bool
1615 15460461 : empty_block_p (basic_block bb)
1616 : {
1617 15460461 : gcc_assert (cfg_hooks->empty_block_p);
1618 15460461 : return cfg_hooks->empty_block_p (bb);
1619 : }
1620 :
1621 : /* Split a basic block if it ends with a conditional branch and if
1622 : the other part of the block is not empty. */
1623 : basic_block
1624 557 : split_block_before_cond_jump (basic_block bb)
1625 : {
1626 557 : gcc_assert (cfg_hooks->split_block_before_cond_jump);
1627 557 : return cfg_hooks->split_block_before_cond_jump (bb);
1628 : }
1629 :
1630 : /* Work-horse for passes.cc:check_profile_consistency.
1631 : Do book-keeping of the CFG for the profile consistency checker.
1632 : Store the counting in RECORD. */
1633 :
1634 : void
1635 0 : profile_record_check_consistency (profile_record *record)
1636 : {
1637 0 : basic_block bb;
1638 0 : edge_iterator ei;
1639 0 : edge e;
1640 :
1641 0 : FOR_ALL_BB_FN (bb, cfun)
1642 : {
1643 0 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
1644 0 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1645 0 : && EDGE_COUNT (bb->succs))
1646 : {
1647 0 : sreal sum = 0;
1648 0 : bool found = false;
1649 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1650 : {
1651 0 : if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
1652 0 : found = true;
1653 0 : if (e->probability.initialized_p ())
1654 0 : sum += e->probability.to_sreal ();
1655 : }
1656 0 : double dsum = sum.to_double ();
1657 0 : if (found && (dsum < 0.9 || dsum > 1.1)
1658 0 : && !(bb->count == profile_count::zero ()))
1659 : {
1660 0 : record->num_mismatched_prob_out++;
1661 0 : dsum = dsum > 1 ? dsum - 1 : 1 - dsum;
1662 0 : if (profile_info)
1663 : {
1664 0 : if (ENTRY_BLOCK_PTR_FOR_FN
1665 0 : (cfun)->count.ipa ().initialized_p ()
1666 0 : && ENTRY_BLOCK_PTR_FOR_FN
1667 0 : (cfun)->count.ipa ().nonzero_p ()
1668 0 : && bb->count.ipa ().initialized_p ())
1669 0 : record->dyn_mismatched_prob_out
1670 0 : += dsum * bb->count.ipa ().to_gcov_type ();
1671 : }
1672 0 : else if (bb->count.initialized_p ())
1673 0 : record->dyn_mismatched_prob_out
1674 0 : += dsum * bb->count.to_sreal_scale
1675 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
1676 : }
1677 : }
1678 0 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1679 0 : && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1680 : {
1681 0 : profile_count lsum = profile_count::zero ();
1682 0 : FOR_EACH_EDGE (e, ei, bb->preds)
1683 0 : lsum += e->count ();
1684 0 : if (lsum.differs_from_p (bb->count))
1685 : {
1686 0 : record->num_mismatched_count_in++;
1687 0 : profile_count max;
1688 0 : if (lsum < bb->count)
1689 0 : max = bb->count;
1690 : else
1691 0 : max = lsum;
1692 0 : if (profile_info)
1693 : {
1694 0 : if (ENTRY_BLOCK_PTR_FOR_FN
1695 0 : (cfun)->count.ipa ().initialized_p ()
1696 0 : && ENTRY_BLOCK_PTR_FOR_FN
1697 0 : (cfun)->count.ipa ().nonzero_p ()
1698 0 : && max.ipa ().initialized_p ())
1699 0 : record->dyn_mismatched_count_in
1700 0 : += max.ipa ().to_gcov_type ();
1701 : }
1702 0 : else if (bb->count.initialized_p ())
1703 0 : record->dyn_mismatched_prob_out
1704 0 : += max.to_sreal_scale
1705 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
1706 : }
1707 : }
1708 0 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1709 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1710 0 : continue;
1711 : }
1712 0 : }
1713 :
1714 : /* Work-horse for passes.cc:acount_profile.
1715 : Do book-keeping of the CFG for the profile accounting.
1716 : Store the counting in RECORD. */
1717 :
1718 : void
1719 0 : profile_record_account_profile (profile_record *record)
1720 : {
1721 0 : basic_block bb;
1722 :
1723 0 : FOR_ALL_BB_FN (bb, cfun)
1724 : {
1725 0 : gcc_assert (cfg_hooks->account_profile_record);
1726 0 : cfg_hooks->account_profile_record (bb, record);
1727 : }
1728 0 : }
1729 :
1730 : #if __GNUC__ >= 10
1731 : # pragma GCC diagnostic pop
1732 : #endif
|
