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 /* Duplicates basic block BB and redirects edge E to it. Returns the
1090 new basic block. The new basic block is placed after the basic block
1094 duplicate_block (basic_block bb
, edge e
, basic_block after
, copy_bb_data
*id
)
1098 profile_count new_count
= e
? e
->count (): profile_count::uninitialized ();
1101 if (!cfg_hooks
->duplicate_block
)
1102 internal_error ("%s does not support duplicate_block",
1105 if (bb
->count
< new_count
)
1106 new_count
= bb
->count
;
1108 gcc_checking_assert (can_duplicate_block_p (bb
));
1110 new_bb
= cfg_hooks
->duplicate_block (bb
, id
);
1112 move_block_after (new_bb
, after
);
1114 new_bb
->flags
= (bb
->flags
& ~BB_DUPLICATED
);
1115 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1117 /* Since we are creating edges from a new block to successors
1118 of another block (which therefore are known to be disjoint), there
1119 is no need to actually check for duplicated edges. */
1120 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1121 n
->probability
= s
->probability
;
1127 new_bb
->count
= new_count
;
1128 bb
->count
-= new_count
;
1130 redirect_edge_and_branch_force (e
, new_bb
);
1133 new_bb
->count
= bb
->count
;
1135 set_bb_original (new_bb
, bb
);
1136 set_bb_copy (bb
, new_bb
);
1138 /* Add the new block to the copy of the loop of BB, or directly to the loop
1139 of BB if the loop is not being copied. */
1140 if (current_loops
!= NULL
)
1142 class loop
*cloop
= bb
->loop_father
;
1143 class loop
*copy
= get_loop_copy (cloop
);
1144 /* If we copied the loop header block but not the loop
1145 we have created a loop with multiple entries. Ditch the loop,
1146 add the new block to the outer loop and arrange for a fixup. */
1148 && cloop
->header
== bb
)
1150 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1151 mark_loop_for_removal (cloop
);
1155 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1156 /* If we copied the loop latch block but not the loop, adjust
1159 && cloop
->latch
== bb
)
1161 cloop
->latch
= NULL
;
1162 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1170 /* Return 1 if BB ends with a call, possibly followed by some
1171 instructions that must stay with the call, 0 otherwise. */
1174 block_ends_with_call_p (basic_block bb
)
1176 if (!cfg_hooks
->block_ends_with_call_p
)
1177 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1179 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1182 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1185 block_ends_with_condjump_p (const_basic_block bb
)
1187 if (!cfg_hooks
->block_ends_with_condjump_p
)
1188 internal_error ("%s does not support block_ends_with_condjump_p",
1191 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1194 /* Add fake edges to the function exit for any non constant and non noreturn
1195 calls, volatile inline assembly in the bitmap of blocks specified by
1196 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1199 The goal is to expose cases in which entering a basic block does not imply
1200 that all subsequent instructions must be executed. */
1203 flow_call_edges_add (sbitmap blocks
)
1205 if (!cfg_hooks
->flow_call_edges_add
)
1206 internal_error ("%s does not support flow_call_edges_add",
1209 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1212 /* This function is called immediately after edge E is added to the
1213 edge vector E->dest->preds. */
1216 execute_on_growing_pred (edge e
)
1218 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1219 && cfg_hooks
->execute_on_growing_pred
)
1220 cfg_hooks
->execute_on_growing_pred (e
);
1223 /* This function is called immediately before edge E is removed from
1224 the edge vector E->dest->preds. */
1227 execute_on_shrinking_pred (edge e
)
1229 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1230 && cfg_hooks
->execute_on_shrinking_pred
)
1231 cfg_hooks
->execute_on_shrinking_pred (e
);
1234 /* This is used inside loop versioning when we want to insert
1235 stmts/insns on the edges, which have a different behavior
1236 in tree's and in RTL, so we made a CFG hook. */
1238 lv_flush_pending_stmts (edge e
)
1240 if (cfg_hooks
->flush_pending_stmts
)
1241 cfg_hooks
->flush_pending_stmts (e
);
1244 /* Loop versioning uses the duplicate_loop_body_to_header_edge to create
1245 a new version of the loop basic-blocks, the parameters here are
1246 exactly the same as in duplicate_loop_body_to_header_edge or
1247 tree_duplicate_loop_body_to_header_edge; while in tree-ssa there is
1248 additional work to maintain ssa information that's why there is
1249 a need to call the tree_duplicate_loop_body_to_header_edge rather
1250 than duplicate_loop_body_to_header_edge when we are in tree mode. */
1252 cfg_hook_duplicate_loop_body_to_header_edge (class loop
*loop
, edge e
,
1254 sbitmap wont_exit
, edge orig
,
1255 vec
<edge
> *to_remove
, int flags
)
1257 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_body_to_header_edge
);
1258 return cfg_hooks
->cfg_hook_duplicate_loop_body_to_header_edge (
1259 loop
, e
, ndupl
, wont_exit
, orig
, to_remove
, flags
);
1262 /* Conditional jumps are represented differently in trees and RTL,
1263 this hook takes a basic block that is known to have a cond jump
1264 at its end and extracts the taken and not taken edges out of it
1265 and store it in E1 and E2 respectively. */
1267 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1269 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1270 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1273 /* Responsible for updating the ssa info (PHI nodes) on the
1274 new condition basic block that guards the versioned loop. */
1276 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1277 basic_block new_block
, edge e
)
1279 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1280 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1283 /* Conditions in trees and RTL are different so we need
1284 a different handling when we add the condition to the
1287 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1288 basic_block new_block
, void *cond
)
1290 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1291 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1294 /* Checks whether all N blocks in BBS array can be copied. */
1296 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1302 for (i
= 0; i
< n
; i
++)
1303 bbs
[i
]->flags
|= BB_DUPLICATED
;
1305 for (i
= 0; i
< n
; i
++)
1307 /* In case we should redirect abnormal edge during duplication, fail. */
1309 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1310 if ((e
->flags
& EDGE_ABNORMAL
)
1311 && (e
->dest
->flags
& BB_DUPLICATED
))
1317 if (!can_duplicate_block_p (bbs
[i
]))
1325 for (i
= 0; i
< n
; i
++)
1326 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1331 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1332 are placed into array NEW_BBS in the same order. Edges from basic blocks
1333 in BBS are also duplicated and copies of those that lead into BBS are
1334 redirected to appropriate newly created block. The function assigns bbs
1335 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1336 loop, so this must be set up correctly in advance)
1338 If UPDATE_DOMINANCE is true then this function updates dominators locally
1339 (LOOPS structure that contains the information about dominators is passed
1340 to enable this), otherwise it does not update the dominator information
1341 and it assumed that the caller will do this, perhaps by destroying and
1342 recreating it instead of trying to do an incremental update like this
1343 function does when update_dominance is true.
1345 BASE is the superloop to that basic block belongs; if its header or latch
1346 is copied, we do not set the new blocks as header or latch.
1348 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1349 also in the same order.
1351 Newly created basic blocks are put after the basic block AFTER in the
1352 instruction stream, and the order of the blocks in BBS array is preserved. */
1355 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1356 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1357 class loop
*base
, basic_block after
, bool update_dominance
)
1360 basic_block bb
, new_bb
, dom_bb
;
1364 /* Mark the blocks to be copied. This is used by edge creation hooks
1365 to decide whether to reallocate PHI nodes capacity to avoid reallocating
1366 PHIs in the set of source BBs. */
1367 for (i
= 0; i
< n
; i
++)
1368 bbs
[i
]->flags
|= BB_DUPLICATED
;
1370 /* Duplicate bbs, update dominators, assign bbs to loops. */
1371 for (i
= 0; i
< n
; i
++)
1375 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
, &id
);
1377 if (bb
->loop_father
)
1379 /* Possibly set loop header. */
1380 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1381 new_bb
->loop_father
->header
= new_bb
;
1383 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1384 new_bb
->loop_father
->latch
= new_bb
;
1388 /* Set dominators. */
1389 if (update_dominance
)
1391 for (i
= 0; i
< n
; i
++)
1394 new_bb
= new_bbs
[i
];
1396 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1397 if (dom_bb
->flags
& BB_DUPLICATED
)
1399 dom_bb
= get_bb_copy (dom_bb
);
1400 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1405 /* Redirect edges. */
1406 for (i
= 0; i
< n
; i
++)
1409 new_bb
= new_bbs
[i
];
1412 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1414 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1416 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1419 for (j
= 0; j
< num_edges
; j
++)
1422 new_edges
[j
] = NULL
;
1425 basic_block src
= edges
[j
]->src
;
1426 basic_block dest
= edges
[j
]->dest
;
1427 if (src
->flags
& BB_DUPLICATED
)
1428 src
= get_bb_copy (src
);
1429 if (dest
->flags
& BB_DUPLICATED
)
1430 dest
= get_bb_copy (dest
);
1431 new_edges
[j
] = find_edge (src
, dest
);
1435 /* Clear information about duplicates. */
1436 for (i
= 0; i
< n
; i
++)
1437 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1440 /* Return true if BB contains only labels or non-executable
1443 empty_block_p (basic_block bb
)
1445 gcc_assert (cfg_hooks
->empty_block_p
);
1446 return cfg_hooks
->empty_block_p (bb
);
1449 /* Split a basic block if it ends with a conditional branch and if
1450 the other part of the block is not empty. */
1452 split_block_before_cond_jump (basic_block bb
)
1454 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1455 return cfg_hooks
->split_block_before_cond_jump (bb
);
1458 /* Work-horse for passes.c:check_profile_consistency.
1459 Do book-keeping of the CFG for the profile consistency checker.
1460 Store the counting in RECORD. */
1463 profile_record_check_consistency (profile_record
*record
)
1469 FOR_ALL_BB_FN (bb
, cfun
)
1471 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1472 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
1473 && EDGE_COUNT (bb
->succs
))
1477 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1479 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
1481 if (e
->probability
.initialized_p ())
1482 sum
+= e
->probability
.to_sreal ();
1484 double dsum
= sum
.to_double ();
1485 if (found
&& (dsum
< 0.9 || dsum
> 1.1)
1486 && !(bb
->count
== profile_count::zero ()))
1488 record
->num_mismatched_prob_out
++;
1489 dsum
= dsum
> 1 ? dsum
- 1 : 1 - dsum
;
1492 if (ENTRY_BLOCK_PTR_FOR_FN
1493 (cfun
)->count
.ipa ().initialized_p ()
1494 && ENTRY_BLOCK_PTR_FOR_FN
1495 (cfun
)->count
.ipa ().nonzero_p ()
1496 && bb
->count
.ipa ().initialized_p ())
1497 record
->dyn_mismatched_prob_out
1498 += dsum
* bb
->count
.ipa ().to_gcov_type ();
1500 else if (bb
->count
.initialized_p ())
1501 record
->dyn_mismatched_prob_out
1502 += dsum
* bb
->count
.to_sreal_scale
1503 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).to_double ();
1506 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1507 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1509 profile_count lsum
= profile_count::zero ();
1510 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1511 lsum
+= e
->count ();
1512 if (lsum
.differs_from_p (bb
->count
))
1514 record
->num_mismatched_count_in
++;
1516 if (lsum
< bb
->count
)
1522 if (ENTRY_BLOCK_PTR_FOR_FN
1523 (cfun
)->count
.ipa ().initialized_p ()
1524 && ENTRY_BLOCK_PTR_FOR_FN
1525 (cfun
)->count
.ipa ().nonzero_p ()
1526 && max
.ipa ().initialized_p ())
1527 record
->dyn_mismatched_count_in
1528 += max
.ipa ().to_gcov_type ();
1530 else if (bb
->count
.initialized_p ())
1531 record
->dyn_mismatched_prob_out
1532 += max
.to_sreal_scale
1533 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).to_double ();
1536 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1537 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1542 /* Work-horse for passes.c:acount_profile.
1543 Do book-keeping of the CFG for the profile accounting.
1544 Store the counting in RECORD. */
1547 profile_record_account_profile (profile_record
*record
)
1551 FOR_ALL_BB_FN (bb
, cfun
)
1553 gcc_assert (cfg_hooks
->account_profile_record
);
1554 cfg_hooks
->account_profile_record (bb
, record
);
1559 # pragma GCC diagnostic pop