1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2022 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
28 #include "pretty-print.h"
29 #include "diagnostic-core.h"
37 /* Disable warnings about missing quoting in GCC diagnostics. */
39 # pragma GCC diagnostic push
40 # pragma GCC diagnostic ignored "-Wformat-diag"
43 /* A pointer to one of the hooks containers. */
44 static struct cfg_hooks
*cfg_hooks
;
46 /* Initialization of functions specific to the rtl IR. */
48 rtl_register_cfg_hooks (void)
50 cfg_hooks
= &rtl_cfg_hooks
;
53 /* Initialization of functions specific to the rtl IR. */
55 cfg_layout_rtl_register_cfg_hooks (void)
57 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
60 /* Initialization of functions specific to the tree IR. */
63 gimple_register_cfg_hooks (void)
65 cfg_hooks
= &gimple_cfg_hooks
;
75 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
77 *cfg_hooks
= new_cfg_hooks
;
80 /* Returns current ir type. */
83 current_ir_type (void)
85 if (cfg_hooks
== &gimple_cfg_hooks
)
87 else if (cfg_hooks
== &rtl_cfg_hooks
)
89 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
90 return IR_RTL_CFGLAYOUT
;
95 /* Verify the CFG consistency.
97 Currently it does following: checks edge and basic block list correctness
98 and calls into IL dependent checking then. */
101 verify_flow_info (void)
103 size_t *edge_checksum
;
105 basic_block bb
, last_bb_seen
;
106 basic_block
*last_visited
;
108 timevar_push (TV_CFG_VERIFY
);
109 last_visited
= XCNEWVEC (basic_block
, last_basic_block_for_fn (cfun
));
110 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
112 /* Check bb chain & numbers. */
113 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
114 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
116 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
117 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, bb
->index
))
119 error ("bb %d on wrong place", bb
->index
);
123 if (bb
->prev_bb
!= last_bb_seen
)
125 error ("prev_bb of %d should be %d, not %d",
126 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
133 /* Now check the basic blocks (boundaries etc.) */
134 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
140 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
142 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
146 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
148 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
152 if (!bb
->count
.verify ())
154 error ("verify_flow_info: Wrong count of block %i", bb
->index
);
157 /* FIXME: Graphite and SLJL and target code still tends to produce
158 edges with no probability. */
159 if (profile_status_for_fn (cfun
) >= PROFILE_GUESSED
160 && !bb
->count
.initialized_p () && !flag_graphite
&& 0)
162 error ("verify_flow_info: Missing count of block %i", bb
->index
);
166 if (bb
->flags
& ~cfun
->cfg
->bb_flags_allocated
)
168 error ("verify_flow_info: unallocated flag set on BB %d", bb
->index
);
172 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
174 if (last_visited
[e
->dest
->index
] == bb
)
176 error ("verify_flow_info: Duplicate edge %i->%i",
177 e
->src
->index
, e
->dest
->index
);
180 /* FIXME: Graphite and SLJL and target code still tends to produce
181 edges with no probability. */
182 if (profile_status_for_fn (cfun
) >= PROFILE_GUESSED
183 && !e
->probability
.initialized_p () && !flag_graphite
&& 0)
185 error ("Uninitialized probability of edge %i->%i", e
->src
->index
,
189 if (!e
->probability
.verify ())
191 error ("verify_flow_info: Wrong probability of edge %i->%i",
192 e
->src
->index
, e
->dest
->index
);
196 last_visited
[e
->dest
->index
] = bb
;
198 if (e
->flags
& EDGE_FALLTHRU
)
203 error ("verify_flow_info: Basic block %d succ edge is corrupted",
205 fprintf (stderr
, "Predecessor: ");
206 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
207 fprintf (stderr
, "\nSuccessor: ");
208 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
209 fprintf (stderr
, "\n");
213 if (e
->flags
& ~cfun
->cfg
->edge_flags_allocated
)
215 error ("verify_flow_info: unallocated edge flag set on %d -> %d",
216 e
->src
->index
, e
->dest
->index
);
220 edge_checksum
[e
->dest
->index
] += (size_t) e
;
224 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
228 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
232 error ("basic block %d pred edge is corrupted", bb
->index
);
233 fputs ("Predecessor: ", stderr
);
234 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
235 fputs ("\nSuccessor: ", stderr
);
236 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
237 fputc ('\n', stderr
);
241 if (ei
.index
!= e
->dest_idx
)
243 error ("basic block %d pred edge is corrupted", bb
->index
);
244 error ("its dest_idx should be %d, not %d",
245 ei
.index
, e
->dest_idx
);
246 fputs ("Predecessor: ", stderr
);
247 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
248 fputs ("\nSuccessor: ", stderr
);
249 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
250 fputc ('\n', stderr
);
254 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
258 /* Complete edge checksumming for ENTRY and EXIT. */
263 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
264 edge_checksum
[e
->dest
->index
] += (size_t) e
;
266 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
267 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
270 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
271 if (edge_checksum
[bb
->index
])
273 error ("basic block %i edge lists are corrupted", bb
->index
);
279 free (edge_checksum
);
281 if (cfg_hooks
->verify_flow_info
)
282 err
|= cfg_hooks
->verify_flow_info ();
284 internal_error ("verify_flow_info failed");
285 timevar_pop (TV_CFG_VERIFY
);
288 /* Print out one basic block BB to file OUTF. INDENT is printed at the
289 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
291 This function takes care of the purely graph related information.
292 The cfg hook for the active representation should dump
293 representation-specific information. */
296 dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
298 if (flags
& TDF_BLOCKS
)
299 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
300 if (cfg_hooks
->dump_bb
)
301 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
302 if (flags
& TDF_BLOCKS
)
303 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
308 debug (basic_block_def
&ref
)
310 dump_bb (stderr
, &ref
, 0, TDF_NONE
);
314 debug (basic_block_def
*ptr
)
319 fprintf (stderr
, "<nil>\n");
323 debug_slim (basic_block ptr
)
325 fprintf (stderr
, "<basic_block %p (%d)>", (void *) ptr
, ptr
->index
);
328 DEFINE_DEBUG_VEC (basic_block_def
*)
329 DEFINE_DEBUG_HASH_SET (basic_block_def
*)
331 /* Dumps basic block BB to pretty-printer PP, for use as a label of
332 a DOT graph record-node. The implementation of this hook is
333 expected to write the label to the stream that is attached to PP.
334 Field separators between instructions are pipe characters printed
335 verbatim. Instructions should be written with some characters
336 escaped, using pp_write_text_as_dot_label_to_stream(). */
339 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
341 if (!cfg_hooks
->dump_bb_for_graph
)
342 internal_error ("%s does not support dump_bb_for_graph",
344 /* TODO: Add pretty printer for counter. */
345 if (bb
->count
.initialized_p ())
346 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
.to_gcov_type ());
347 pp_write_text_to_stream (pp
);
348 if (!(dump_flags
& TDF_SLIM
))
349 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
352 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
354 dump_flow_info (FILE *file
, dump_flags_t flags
)
358 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
359 n_edges_for_fn (cfun
));
360 FOR_ALL_BB_FN (bb
, cfun
)
361 dump_bb (file
, bb
, 0, flags
);
366 /* Like above, but dump to stderr. To be called from debuggers. */
367 void debug_flow_info (void);
369 debug_flow_info (void)
371 dump_flow_info (stderr
, TDF_DETAILS
);
374 /* Redirect edge E to the given basic block DEST and update underlying program
375 representation. Returns edge representing redirected branch (that may not
376 be equivalent to E in the case of duplicate edges being removed) or NULL
377 if edge is not easily redirectable for whatever reason. */
380 redirect_edge_and_branch (edge e
, basic_block dest
)
384 if (!cfg_hooks
->redirect_edge_and_branch
)
385 internal_error ("%s does not support redirect_edge_and_branch",
388 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
390 /* If RET != E, then either the redirection failed, or the edge E
391 was removed since RET already lead to the same destination. */
392 if (current_loops
!= NULL
&& ret
== e
)
393 rescan_loop_exit (e
, false, false);
398 /* Returns true if it is possible to remove the edge E by redirecting it
399 to the destination of the other edge going from its source. */
402 can_remove_branch_p (const_edge e
)
404 if (!cfg_hooks
->can_remove_branch_p
)
405 internal_error ("%s does not support can_remove_branch_p",
408 if (EDGE_COUNT (e
->src
->succs
) != 2)
411 return cfg_hooks
->can_remove_branch_p (e
);
414 /* Removes E, by redirecting it to the destination of the other edge going
415 from its source. Can_remove_branch_p must be true for E, hence this
416 operation cannot fail. */
419 remove_branch (edge e
)
422 basic_block src
= e
->src
;
425 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
427 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
428 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
430 e
= redirect_edge_and_branch (e
, other
->dest
);
431 gcc_assert (e
!= NULL
);
433 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
437 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
442 if (current_loops
!= NULL
)
444 rescan_loop_exit (e
, false, true);
446 /* Removal of an edge inside an irreducible region or which leads
447 to an irreducible region can turn the region into a natural loop.
448 In that case, ask for the loop structure fixups.
450 FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
451 set, so always ask for fixups when removing an edge in that case. */
452 if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
453 || (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
454 || (e
->dest
->flags
& BB_IRREDUCIBLE_LOOP
))
455 loops_state_set (LOOPS_NEED_FIXUP
);
458 /* This is probably not needed, but it doesn't hurt. */
459 /* FIXME: This should be called via a remove_edge hook. */
460 if (current_ir_type () == IR_GIMPLE
)
461 redirect_edge_var_map_clear (e
);
466 /* Like redirect_edge_succ but avoid possible duplicate edge. */
469 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
473 s
= find_edge (e
->src
, new_succ
);
476 s
->flags
|= e
->flags
;
477 s
->probability
+= e
->probability
;
478 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
479 redirect_edge_var_map_dup (s
, e
);
484 redirect_edge_succ (e
, new_succ
);
489 /* Redirect the edge E to basic block DEST even if it requires creating
490 of a new basic block; then it returns the newly created basic block.
491 Aborts when redirection is impossible. */
494 redirect_edge_and_branch_force (edge e
, basic_block dest
)
496 basic_block ret
, src
= e
->src
;
498 if (!cfg_hooks
->redirect_edge_and_branch_force
)
499 internal_error ("%s does not support redirect_edge_and_branch_force",
502 if (current_loops
!= NULL
)
503 rescan_loop_exit (e
, false, true);
505 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
507 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
508 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
510 if (current_loops
!= NULL
)
515 = find_common_loop (single_pred (ret
)->loop_father
,
516 single_succ (ret
)->loop_father
);
517 add_bb_to_loop (ret
, loop
);
519 else if (find_edge (src
, dest
) == e
)
520 rescan_loop_exit (e
, true, false);
526 /* Splits basic block BB after the specified instruction I (but at least after
527 the labels). If I is NULL, splits just after labels. The newly created edge
528 is returned. The new basic block is created just after the old one. */
531 split_block_1 (basic_block bb
, void *i
)
536 if (!cfg_hooks
->split_block
)
537 internal_error ("%s does not support split_block", cfg_hooks
->name
);
539 new_bb
= cfg_hooks
->split_block (bb
, i
);
543 new_bb
->count
= bb
->count
;
544 new_bb
->discriminator
= bb
->discriminator
;
546 if (dom_info_available_p (CDI_DOMINATORS
))
548 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
549 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
552 if (current_loops
!= NULL
)
556 add_bb_to_loop (new_bb
, bb
->loop_father
);
557 /* Identify all loops bb may have been the latch of and adjust them. */
558 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
559 if (e
->dest
->loop_father
->latch
== bb
)
560 e
->dest
->loop_father
->latch
= new_bb
;
563 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
565 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
567 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
568 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
575 split_block (basic_block bb
, gimple
*i
)
577 return split_block_1 (bb
, i
);
581 split_block (basic_block bb
, rtx i
)
583 return split_block_1 (bb
, i
);
586 /* Splits block BB just after labels. The newly created edge is returned. */
589 split_block_after_labels (basic_block bb
)
591 return split_block_1 (bb
, NULL
);
594 /* Moves block BB immediately after block AFTER. Returns false if the
595 movement was impossible. */
598 move_block_after (basic_block bb
, basic_block after
)
602 if (!cfg_hooks
->move_block_after
)
603 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
605 ret
= cfg_hooks
->move_block_after (bb
, after
);
610 /* Deletes the basic block BB. */
613 delete_basic_block (basic_block bb
)
615 if (!cfg_hooks
->delete_basic_block
)
616 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
618 cfg_hooks
->delete_basic_block (bb
);
620 if (current_loops
!= NULL
)
622 class loop
*loop
= bb
->loop_father
;
624 /* If we remove the header or the latch of a loop, mark the loop for
626 if (loop
->latch
== bb
627 || loop
->header
== bb
)
628 mark_loop_for_removal (loop
);
630 remove_bb_from_loops (bb
);
633 /* Remove the edges into and out of this block. Note that there may
634 indeed be edges in, if we are removing an unreachable loop. */
635 while (EDGE_COUNT (bb
->preds
) != 0)
636 remove_edge (EDGE_PRED (bb
, 0));
637 while (EDGE_COUNT (bb
->succs
) != 0)
638 remove_edge (EDGE_SUCC (bb
, 0));
640 if (dom_info_available_p (CDI_DOMINATORS
))
641 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
642 if (dom_info_available_p (CDI_POST_DOMINATORS
))
643 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
645 /* Remove the basic block from the array. */
649 /* Splits edge E and returns the newly created basic block. */
655 profile_count count
= e
->count ();
657 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
658 bool back
= (e
->flags
& EDGE_DFS_BACK
) != 0;
660 basic_block src
= e
->src
, dest
= e
->dest
;
662 if (!cfg_hooks
->split_edge
)
663 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
665 if (current_loops
!= NULL
)
666 rescan_loop_exit (e
, false, true);
668 ret
= cfg_hooks
->split_edge (e
);
670 single_succ_edge (ret
)->probability
= profile_probability::always ();
674 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
675 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
676 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
680 single_pred_edge (ret
)->flags
&= ~EDGE_DFS_BACK
;
681 single_succ_edge (ret
)->flags
|= EDGE_DFS_BACK
;
684 if (dom_info_available_p (CDI_DOMINATORS
))
685 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
687 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
689 /* There are two cases:
691 If the immediate dominator of e->dest is not e->src, it
694 If immediate dominator of e->dest is e->src, it may become
695 ret, provided that all other predecessors of e->dest are
696 dominated by e->dest. */
698 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
699 == single_pred (ret
))
702 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
704 if (f
== single_succ_edge (ret
))
707 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
713 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
717 if (current_loops
!= NULL
)
719 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
720 add_bb_to_loop (ret
, loop
);
722 /* If we split the latch edge of loop adjust the latch block. */
723 if (loop
->latch
== src
724 && loop
->header
== dest
)
731 /* Creates a new basic block just after the basic block AFTER.
732 HEAD and END are the first and the last statement belonging
733 to the block. If both are NULL, an empty block is created. */
736 create_basic_block_1 (void *head
, void *end
, basic_block after
)
740 if (!cfg_hooks
->create_basic_block
)
741 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
743 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
745 if (dom_info_available_p (CDI_DOMINATORS
))
746 add_to_dominance_info (CDI_DOMINATORS
, ret
);
747 if (dom_info_available_p (CDI_POST_DOMINATORS
))
748 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
754 create_basic_block (gimple_seq seq
, basic_block after
)
756 return create_basic_block_1 (seq
, NULL
, after
);
760 create_basic_block (rtx head
, rtx end
, basic_block after
)
762 return create_basic_block_1 (head
, end
, after
);
766 /* Creates an empty basic block just after basic block AFTER. */
769 create_empty_bb (basic_block after
)
771 return create_basic_block_1 (NULL
, NULL
, after
);
774 /* Checks whether we may merge blocks BB1 and BB2. */
777 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
781 if (!cfg_hooks
->can_merge_blocks_p
)
782 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
784 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
790 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
792 if (!cfg_hooks
->predict_edge
)
793 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
795 cfg_hooks
->predict_edge (e
, predictor
, probability
);
799 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
801 if (!cfg_hooks
->predict_edge
)
802 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
804 return cfg_hooks
->predicted_by_p (bb
, predictor
);
807 /* Merges basic block B into basic block A. */
810 merge_blocks (basic_block a
, basic_block b
)
815 if (!cfg_hooks
->merge_blocks
)
816 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
818 cfg_hooks
->merge_blocks (a
, b
);
820 if (current_loops
!= NULL
)
822 /* If the block we merge into is a loop header do nothing unless ... */
823 if (a
->loop_father
->header
== a
)
825 /* ... we merge two loop headers, in which case we kill
827 if (b
->loop_father
->header
== b
)
828 mark_loop_for_removal (b
->loop_father
);
830 /* If we merge a loop header into its predecessor, update the loop
832 else if (b
->loop_father
->header
== b
)
834 remove_bb_from_loops (a
);
835 add_bb_to_loop (a
, b
->loop_father
);
836 a
->loop_father
->header
= a
;
838 /* If we merge a loop latch into its predecessor, update the loop
840 if (b
->loop_father
->latch
841 && b
->loop_father
->latch
== b
)
842 b
->loop_father
->latch
= a
;
843 remove_bb_from_loops (b
);
846 /* Normally there should only be one successor of A and that is B, but
847 partway though the merge of blocks for conditional_execution we'll
848 be merging a TEST block with THEN and ELSE successors. Free the
849 whole lot of them and hope the caller knows what they're doing. */
851 while (EDGE_COUNT (a
->succs
) != 0)
852 remove_edge (EDGE_SUCC (a
, 0));
854 /* Adjust the edges out of B for the new owner. */
855 FOR_EACH_EDGE (e
, ei
, b
->succs
)
858 if (current_loops
!= NULL
)
860 /* If b was a latch, a now is. */
861 if (e
->dest
->loop_father
->latch
== b
)
862 e
->dest
->loop_father
->latch
= a
;
863 rescan_loop_exit (e
, true, false);
867 a
->flags
|= b
->flags
;
869 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
870 b
->preds
= b
->succs
= NULL
;
872 if (dom_info_available_p (CDI_DOMINATORS
))
873 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
875 if (dom_info_available_p (CDI_DOMINATORS
))
876 delete_from_dominance_info (CDI_DOMINATORS
, b
);
877 if (dom_info_available_p (CDI_POST_DOMINATORS
))
878 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
883 /* Split BB into entry part and the rest (the rest is the newly created block).
884 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
885 part. Returns the edge connecting the entry part to the rest. */
888 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
889 void (*new_bb_cbk
) (basic_block
))
893 basic_block dummy
, jump
;
894 class loop
*loop
, *ploop
, *cloop
;
896 if (!cfg_hooks
->make_forwarder_block
)
897 internal_error ("%s does not support make_forwarder_block",
900 fallthru
= split_block_after_labels (bb
);
901 dummy
= fallthru
->src
;
902 dummy
->count
= profile_count::zero ();
905 /* Redirect back edges we want to keep. */
906 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
910 if (redirect_edge_p (e
))
912 dummy
->count
+= e
->count ();
918 jump
= redirect_edge_and_branch_force (e
, bb
);
921 /* If we redirected the loop latch edge, the JUMP block now acts like
922 the new latch of the loop. */
923 if (current_loops
!= NULL
924 && dummy
->loop_father
!= NULL
925 && dummy
->loop_father
->header
== dummy
926 && dummy
->loop_father
->latch
== e_src
)
927 dummy
->loop_father
->latch
= jump
;
929 if (new_bb_cbk
!= NULL
)
934 if (dom_info_available_p (CDI_DOMINATORS
))
936 vec
<basic_block
> doms_to_fix
;
937 doms_to_fix
.create (2);
938 doms_to_fix
.quick_push (dummy
);
939 doms_to_fix
.quick_push (bb
);
940 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
941 doms_to_fix
.release ();
944 if (current_loops
!= NULL
)
946 /* If we do not split a loop header, then both blocks belong to the
947 same loop. In case we split loop header and do not redirect the
948 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
949 BB becomes the new header. If latch is not recorded for the loop,
950 we leave this updating on the caller (this may only happen during
952 loop
= dummy
->loop_father
;
953 if (loop
->header
== dummy
954 && loop
->latch
!= NULL
955 && find_edge (loop
->latch
, dummy
) == NULL
)
957 remove_bb_from_loops (dummy
);
961 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
963 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
965 add_bb_to_loop (dummy
, cloop
);
968 /* In case we split loop latch, update it. */
969 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
970 if (ploop
->latch
== dummy
)
974 cfg_hooks
->make_forwarder_block (fallthru
);
979 /* Try to make the edge fallthru. */
982 tidy_fallthru_edge (edge e
)
984 if (cfg_hooks
->tidy_fallthru_edge
)
985 cfg_hooks
->tidy_fallthru_edge (e
);
988 /* Fix up edges that now fall through, or rather should now fall through
989 but previously required a jump around now deleted blocks. Simplify
990 the search by only examining blocks numerically adjacent, since this
991 is how they were created.
993 ??? This routine is currently RTL specific. */
996 tidy_fallthru_edges (void)
1000 if (!cfg_hooks
->tidy_fallthru_edge
)
1003 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1006 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
1007 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
1013 /* We care about simple conditional or unconditional jumps with
1016 If we had a conditional branch to the next instruction when
1017 CFG was built, then there will only be one out edge for the
1018 block which ended with the conditional branch (since we do
1019 not create duplicate edges).
1021 Furthermore, the edge will be marked as a fallthru because we
1022 merge the flags for the duplicate edges. So we do not want to
1023 check that the edge is not a FALLTHRU edge. */
1025 if (single_succ_p (b
))
1027 s
= single_succ_edge (b
);
1028 if (! (s
->flags
& EDGE_COMPLEX
)
1030 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1031 tidy_fallthru_edge (s
);
1036 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1037 (and possibly create new basic block) to make edge non-fallthru.
1038 Return newly created BB or NULL if none. */
1041 force_nonfallthru (edge e
)
1043 basic_block ret
, src
= e
->src
;
1045 if (!cfg_hooks
->force_nonfallthru
)
1046 internal_error ("%s does not support force_nonfallthru",
1049 ret
= cfg_hooks
->force_nonfallthru (e
);
1052 if (dom_info_available_p (CDI_DOMINATORS
))
1053 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1055 if (current_loops
!= NULL
)
1057 basic_block pred
= single_pred (ret
);
1058 basic_block succ
= single_succ (ret
);
1060 = find_common_loop (pred
->loop_father
, succ
->loop_father
);
1061 rescan_loop_exit (e
, false, true);
1062 add_bb_to_loop (ret
, loop
);
1064 /* If we split the latch edge of loop adjust the latch block. */
1065 if (loop
->latch
== pred
1066 && loop
->header
== succ
)
1074 /* Returns true if we can duplicate basic block BB. */
1077 can_duplicate_block_p (const_basic_block bb
)
1079 if (!cfg_hooks
->can_duplicate_block_p
)
1080 internal_error ("%s does not support can_duplicate_block_p",
1083 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1086 return cfg_hooks
->can_duplicate_block_p (bb
);
1089 /* Duplicate basic block BB, place it after AFTER (if non-null) and redirect
1090 edge E to it (if non-null). Return the new basic block.
1092 If BB contains a returns_twice call, the caller is responsible for recreating
1093 incoming abnormal edges corresponding to the "second return" for the copy.
1094 gimple_can_duplicate_bb_p rejects such blocks, while RTL likes to live
1097 If BB has incoming abnormal edges for some other reason, their destinations
1098 should be tied to label(s) of the original BB and not the copy. */
1101 duplicate_block (basic_block bb
, edge e
, basic_block after
, copy_bb_data
*id
)
1105 profile_count new_count
= e
? e
->count (): profile_count::uninitialized ();
1108 if (!cfg_hooks
->duplicate_block
)
1109 internal_error ("%s does not support duplicate_block",
1112 if (bb
->count
< new_count
)
1113 new_count
= bb
->count
;
1115 gcc_checking_assert (can_duplicate_block_p (bb
));
1117 new_bb
= cfg_hooks
->duplicate_block (bb
, id
);
1119 move_block_after (new_bb
, after
);
1121 new_bb
->flags
= (bb
->flags
& ~BB_DUPLICATED
);
1122 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1124 /* Since we are creating edges from a new block to successors
1125 of another block (which therefore are known to be disjoint), there
1126 is no need to actually check for duplicated edges. */
1127 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1128 n
->probability
= s
->probability
;
1134 new_bb
->count
= new_count
;
1135 bb
->count
-= new_count
;
1137 redirect_edge_and_branch_force (e
, new_bb
);
1140 new_bb
->count
= bb
->count
;
1142 set_bb_original (new_bb
, bb
);
1143 set_bb_copy (bb
, new_bb
);
1145 /* Add the new block to the copy of the loop of BB, or directly to the loop
1146 of BB if the loop is not being copied. */
1147 if (current_loops
!= NULL
)
1149 class loop
*cloop
= bb
->loop_father
;
1150 class loop
*copy
= get_loop_copy (cloop
);
1151 /* If we copied the loop header block but not the loop
1152 we have created a loop with multiple entries. Ditch the loop,
1153 add the new block to the outer loop and arrange for a fixup. */
1155 && cloop
->header
== bb
)
1157 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1158 mark_loop_for_removal (cloop
);
1162 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1163 /* If we copied the loop latch block but not the loop, adjust
1166 && cloop
->latch
== bb
)
1168 cloop
->latch
= NULL
;
1169 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1177 /* Return 1 if BB ends with a call, possibly followed by some
1178 instructions that must stay with the call, 0 otherwise. */
1181 block_ends_with_call_p (basic_block bb
)
1183 if (!cfg_hooks
->block_ends_with_call_p
)
1184 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1186 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1189 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1192 block_ends_with_condjump_p (const_basic_block bb
)
1194 if (!cfg_hooks
->block_ends_with_condjump_p
)
1195 internal_error ("%s does not support block_ends_with_condjump_p",
1198 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1201 /* Add fake edges to the function exit for any non constant and non noreturn
1202 calls, volatile inline assembly in the bitmap of blocks specified by
1203 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1206 The goal is to expose cases in which entering a basic block does not imply
1207 that all subsequent instructions must be executed. */
1210 flow_call_edges_add (sbitmap blocks
)
1212 if (!cfg_hooks
->flow_call_edges_add
)
1213 internal_error ("%s does not support flow_call_edges_add",
1216 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1219 /* This function is called immediately after edge E is added to the
1220 edge vector E->dest->preds. */
1223 execute_on_growing_pred (edge e
)
1225 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1226 && cfg_hooks
->execute_on_growing_pred
)
1227 cfg_hooks
->execute_on_growing_pred (e
);
1230 /* This function is called immediately before edge E is removed from
1231 the edge vector E->dest->preds. */
1234 execute_on_shrinking_pred (edge e
)
1236 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1237 && cfg_hooks
->execute_on_shrinking_pred
)
1238 cfg_hooks
->execute_on_shrinking_pred (e
);
1241 /* This is used inside loop versioning when we want to insert
1242 stmts/insns on the edges, which have a different behavior
1243 in tree's and in RTL, so we made a CFG hook. */
1245 lv_flush_pending_stmts (edge e
)
1247 if (cfg_hooks
->flush_pending_stmts
)
1248 cfg_hooks
->flush_pending_stmts (e
);
1251 /* Loop versioning uses the duplicate_loop_body_to_header_edge to create
1252 a new version of the loop basic-blocks, the parameters here are
1253 exactly the same as in duplicate_loop_body_to_header_edge or
1254 tree_duplicate_loop_body_to_header_edge; while in tree-ssa there is
1255 additional work to maintain ssa information that's why there is
1256 a need to call the tree_duplicate_loop_body_to_header_edge rather
1257 than duplicate_loop_body_to_header_edge when we are in tree mode. */
1259 cfg_hook_duplicate_loop_body_to_header_edge (class loop
*loop
, edge e
,
1261 sbitmap wont_exit
, edge orig
,
1262 vec
<edge
> *to_remove
, int flags
)
1264 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_body_to_header_edge
);
1265 return cfg_hooks
->cfg_hook_duplicate_loop_body_to_header_edge (
1266 loop
, e
, ndupl
, wont_exit
, orig
, to_remove
, flags
);
1269 /* Conditional jumps are represented differently in trees and RTL,
1270 this hook takes a basic block that is known to have a cond jump
1271 at its end and extracts the taken and not taken edges out of it
1272 and store it in E1 and E2 respectively. */
1274 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1276 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1277 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1280 /* Responsible for updating the ssa info (PHI nodes) on the
1281 new condition basic block that guards the versioned loop. */
1283 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1284 basic_block new_block
, edge e
)
1286 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1287 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1290 /* Conditions in trees and RTL are different so we need
1291 a different handling when we add the condition to the
1294 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1295 basic_block new_block
, void *cond
)
1297 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1298 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1301 /* Checks whether all N blocks in BBS array can be copied. */
1303 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1309 for (i
= 0; i
< n
; i
++)
1310 bbs
[i
]->flags
|= BB_DUPLICATED
;
1312 for (i
= 0; i
< n
; i
++)
1314 /* In case we should redirect abnormal edge during duplication, fail. */
1316 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1317 if ((e
->flags
& EDGE_ABNORMAL
)
1318 && (e
->dest
->flags
& BB_DUPLICATED
))
1324 if (!can_duplicate_block_p (bbs
[i
]))
1332 for (i
= 0; i
< n
; i
++)
1333 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1338 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1339 are placed into array NEW_BBS in the same order. Edges from basic blocks
1340 in BBS are also duplicated and copies of those that lead into BBS are
1341 redirected to appropriate newly created block. The function assigns bbs
1342 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1343 loop, so this must be set up correctly in advance)
1345 If UPDATE_DOMINANCE is true then this function updates dominators locally
1346 (LOOPS structure that contains the information about dominators is passed
1347 to enable this), otherwise it does not update the dominator information
1348 and it assumed that the caller will do this, perhaps by destroying and
1349 recreating it instead of trying to do an incremental update like this
1350 function does when update_dominance is true.
1352 BASE is the superloop to that basic block belongs; if its header or latch
1353 is copied, we do not set the new blocks as header or latch.
1355 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1356 also in the same order.
1358 Newly created basic blocks are put after the basic block AFTER in the
1359 instruction stream, and the order of the blocks in BBS array is preserved. */
1362 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1363 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1364 class loop
*base
, basic_block after
, bool update_dominance
)
1367 basic_block bb
, new_bb
, dom_bb
;
1371 /* Mark the blocks to be copied. This is used by edge creation hooks
1372 to decide whether to reallocate PHI nodes capacity to avoid reallocating
1373 PHIs in the set of source BBs. */
1374 for (i
= 0; i
< n
; i
++)
1375 bbs
[i
]->flags
|= BB_DUPLICATED
;
1377 /* Duplicate bbs, update dominators, assign bbs to loops. */
1378 for (i
= 0; i
< n
; i
++)
1382 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
, &id
);
1384 if (bb
->loop_father
)
1386 /* Possibly set loop header. */
1387 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1388 new_bb
->loop_father
->header
= new_bb
;
1390 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1391 new_bb
->loop_father
->latch
= new_bb
;
1395 /* Set dominators. */
1396 if (update_dominance
)
1398 for (i
= 0; i
< n
; i
++)
1401 new_bb
= new_bbs
[i
];
1403 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1404 if (dom_bb
->flags
& BB_DUPLICATED
)
1406 dom_bb
= get_bb_copy (dom_bb
);
1407 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1412 /* Redirect edges. */
1413 for (i
= 0; i
< n
; i
++)
1416 new_bb
= new_bbs
[i
];
1419 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1421 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1423 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1426 for (j
= 0; j
< num_edges
; j
++)
1429 new_edges
[j
] = NULL
;
1432 basic_block src
= edges
[j
]->src
;
1433 basic_block dest
= edges
[j
]->dest
;
1434 if (src
->flags
& BB_DUPLICATED
)
1435 src
= get_bb_copy (src
);
1436 if (dest
->flags
& BB_DUPLICATED
)
1437 dest
= get_bb_copy (dest
);
1438 new_edges
[j
] = find_edge (src
, dest
);
1442 /* Clear information about duplicates. */
1443 for (i
= 0; i
< n
; i
++)
1444 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1447 /* Return true if BB contains only labels or non-executable
1450 empty_block_p (basic_block bb
)
1452 gcc_assert (cfg_hooks
->empty_block_p
);
1453 return cfg_hooks
->empty_block_p (bb
);
1456 /* Split a basic block if it ends with a conditional branch and if
1457 the other part of the block is not empty. */
1459 split_block_before_cond_jump (basic_block bb
)
1461 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1462 return cfg_hooks
->split_block_before_cond_jump (bb
);
1465 /* Work-horse for passes.cc:check_profile_consistency.
1466 Do book-keeping of the CFG for the profile consistency checker.
1467 Store the counting in RECORD. */
1470 profile_record_check_consistency (profile_record
*record
)
1476 FOR_ALL_BB_FN (bb
, cfun
)
1478 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1479 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
1480 && EDGE_COUNT (bb
->succs
))
1484 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1486 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
1488 if (e
->probability
.initialized_p ())
1489 sum
+= e
->probability
.to_sreal ();
1491 double dsum
= sum
.to_double ();
1492 if (found
&& (dsum
< 0.9 || dsum
> 1.1)
1493 && !(bb
->count
== profile_count::zero ()))
1495 record
->num_mismatched_prob_out
++;
1496 dsum
= dsum
> 1 ? dsum
- 1 : 1 - dsum
;
1499 if (ENTRY_BLOCK_PTR_FOR_FN
1500 (cfun
)->count
.ipa ().initialized_p ()
1501 && ENTRY_BLOCK_PTR_FOR_FN
1502 (cfun
)->count
.ipa ().nonzero_p ()
1503 && bb
->count
.ipa ().initialized_p ())
1504 record
->dyn_mismatched_prob_out
1505 += dsum
* bb
->count
.ipa ().to_gcov_type ();
1507 else if (bb
->count
.initialized_p ())
1508 record
->dyn_mismatched_prob_out
1509 += dsum
* bb
->count
.to_sreal_scale
1510 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).to_double ();
1513 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1514 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1516 profile_count lsum
= profile_count::zero ();
1517 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1518 lsum
+= e
->count ();
1519 if (lsum
.differs_from_p (bb
->count
))
1521 record
->num_mismatched_count_in
++;
1523 if (lsum
< bb
->count
)
1529 if (ENTRY_BLOCK_PTR_FOR_FN
1530 (cfun
)->count
.ipa ().initialized_p ()
1531 && ENTRY_BLOCK_PTR_FOR_FN
1532 (cfun
)->count
.ipa ().nonzero_p ()
1533 && max
.ipa ().initialized_p ())
1534 record
->dyn_mismatched_count_in
1535 += max
.ipa ().to_gcov_type ();
1537 else if (bb
->count
.initialized_p ())
1538 record
->dyn_mismatched_prob_out
1539 += max
.to_sreal_scale
1540 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).to_double ();
1543 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1544 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1549 /* Work-horse for passes.cc:acount_profile.
1550 Do book-keeping of the CFG for the profile accounting.
1551 Store the counting in RECORD. */
1554 profile_record_account_profile (profile_record
*record
)
1558 FOR_ALL_BB_FN (bb
, cfun
)
1560 gcc_assert (cfg_hooks
->account_profile_record
);
1561 cfg_hooks
->account_profile_record (bb
, record
);
1566 # pragma GCC diagnostic pop