1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2019 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"
35 /* Disable warnings about missing quoting in GCC diagnostics. */
37 # pragma GCC diagnostic push
38 # pragma GCC diagnostic ignored "-Wformat-diag"
41 /* A pointer to one of the hooks containers. */
42 static struct cfg_hooks
*cfg_hooks
;
44 /* Initialization of functions specific to the rtl IR. */
46 rtl_register_cfg_hooks (void)
48 cfg_hooks
= &rtl_cfg_hooks
;
51 /* Initialization of functions specific to the rtl IR. */
53 cfg_layout_rtl_register_cfg_hooks (void)
55 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
58 /* Initialization of functions specific to the tree IR. */
61 gimple_register_cfg_hooks (void)
63 cfg_hooks
= &gimple_cfg_hooks
;
73 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
75 *cfg_hooks
= new_cfg_hooks
;
78 /* Returns current ir type. */
81 current_ir_type (void)
83 if (cfg_hooks
== &gimple_cfg_hooks
)
85 else if (cfg_hooks
== &rtl_cfg_hooks
)
87 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
88 return IR_RTL_CFGLAYOUT
;
93 /* Verify the CFG consistency.
95 Currently it does following: checks edge and basic block list correctness
96 and calls into IL dependent checking then. */
99 verify_flow_info (void)
101 size_t *edge_checksum
;
103 basic_block bb
, last_bb_seen
;
104 basic_block
*last_visited
;
106 timevar_push (TV_CFG_VERIFY
);
107 last_visited
= XCNEWVEC (basic_block
, last_basic_block_for_fn (cfun
));
108 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
110 /* Check bb chain & numbers. */
111 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
112 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
114 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
115 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, bb
->index
))
117 error ("bb %d on wrong place", bb
->index
);
121 if (bb
->prev_bb
!= last_bb_seen
)
123 error ("prev_bb of %d should be %d, not %d",
124 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
131 /* Now check the basic blocks (boundaries etc.) */
132 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
138 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
140 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
144 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
146 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
150 if (!bb
->count
.verify ())
152 error ("verify_flow_info: Wrong count of block %i", bb
->index
);
155 /* FIXME: Graphite and SLJL and target code still tends to produce
156 edges with no probablity. */
157 if (profile_status_for_fn (cfun
) >= PROFILE_GUESSED
158 && !bb
->count
.initialized_p () && !flag_graphite
&& 0)
160 error ("verify_flow_info: Missing count of block %i", bb
->index
);
164 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
166 if (last_visited
[e
->dest
->index
] == bb
)
168 error ("verify_flow_info: Duplicate edge %i->%i",
169 e
->src
->index
, e
->dest
->index
);
172 /* FIXME: Graphite and SLJL and target code still tends to produce
173 edges with no probablity. */
174 if (profile_status_for_fn (cfun
) >= PROFILE_GUESSED
175 && !e
->probability
.initialized_p () && !flag_graphite
&& 0)
177 error ("Uninitialized probability of edge %i->%i", e
->src
->index
,
181 if (!e
->probability
.verify ())
183 error ("verify_flow_info: Wrong probability of edge %i->%i",
184 e
->src
->index
, e
->dest
->index
);
188 last_visited
[e
->dest
->index
] = bb
;
190 if (e
->flags
& EDGE_FALLTHRU
)
195 error ("verify_flow_info: Basic block %d succ edge is corrupted",
197 fprintf (stderr
, "Predecessor: ");
198 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
199 fprintf (stderr
, "\nSuccessor: ");
200 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
201 fprintf (stderr
, "\n");
205 edge_checksum
[e
->dest
->index
] += (size_t) e
;
209 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
213 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
217 error ("basic block %d pred edge is corrupted", bb
->index
);
218 fputs ("Predecessor: ", stderr
);
219 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
220 fputs ("\nSuccessor: ", stderr
);
221 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
222 fputc ('\n', stderr
);
226 if (ei
.index
!= e
->dest_idx
)
228 error ("basic block %d pred edge is corrupted", bb
->index
);
229 error ("its dest_idx should be %d, not %d",
230 ei
.index
, e
->dest_idx
);
231 fputs ("Predecessor: ", stderr
);
232 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
233 fputs ("\nSuccessor: ", stderr
);
234 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
235 fputc ('\n', stderr
);
239 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
243 /* Complete edge checksumming for ENTRY and EXIT. */
248 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
249 edge_checksum
[e
->dest
->index
] += (size_t) e
;
251 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
252 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
255 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
256 if (edge_checksum
[bb
->index
])
258 error ("basic block %i edge lists are corrupted", bb
->index
);
262 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
266 free (edge_checksum
);
268 if (cfg_hooks
->verify_flow_info
)
269 err
|= cfg_hooks
->verify_flow_info ();
271 internal_error ("verify_flow_info failed");
272 timevar_pop (TV_CFG_VERIFY
);
275 /* Print out one basic block BB to file OUTF. INDENT is printed at the
276 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
278 This function takes care of the purely graph related information.
279 The cfg hook for the active representation should dump
280 representation-specific information. */
283 dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
285 if (flags
& TDF_BLOCKS
)
286 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
287 if (cfg_hooks
->dump_bb
)
288 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
289 if (flags
& TDF_BLOCKS
)
290 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
295 debug (basic_block_def
&ref
)
297 dump_bb (stderr
, &ref
, 0, TDF_NONE
);
301 debug (basic_block_def
*ptr
)
306 fprintf (stderr
, "<nil>\n");
310 debug_slim (basic_block ptr
)
312 fprintf (stderr
, "<basic_block %p (%d)>", (void *) ptr
, ptr
->index
);
315 DEFINE_DEBUG_VEC (basic_block_def
*)
316 DEFINE_DEBUG_HASH_SET (basic_block_def
*)
318 /* Dumps basic block BB to pretty-printer PP, for use as a label of
319 a DOT graph record-node. The implementation of this hook is
320 expected to write the label to the stream that is attached to PP.
321 Field separators between instructions are pipe characters printed
322 verbatim. Instructions should be written with some characters
323 escaped, using pp_write_text_as_dot_label_to_stream(). */
326 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
328 if (!cfg_hooks
->dump_bb_for_graph
)
329 internal_error ("%s does not support dump_bb_for_graph",
331 /* TODO: Add pretty printer for counter. */
332 if (bb
->count
.initialized_p ())
333 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
.to_gcov_type ());
334 pp_write_text_to_stream (pp
);
335 if (!(dump_flags
& TDF_SLIM
))
336 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
339 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
341 dump_flow_info (FILE *file
, dump_flags_t flags
)
345 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
346 n_edges_for_fn (cfun
));
347 FOR_ALL_BB_FN (bb
, cfun
)
348 dump_bb (file
, bb
, 0, flags
);
353 /* Like above, but dump to stderr. To be called from debuggers. */
354 void debug_flow_info (void);
356 debug_flow_info (void)
358 dump_flow_info (stderr
, TDF_DETAILS
);
361 /* Redirect edge E to the given basic block DEST and update underlying program
362 representation. Returns edge representing redirected branch (that may not
363 be equivalent to E in the case of duplicate edges being removed) or NULL
364 if edge is not easily redirectable for whatever reason. */
367 redirect_edge_and_branch (edge e
, basic_block dest
)
371 if (!cfg_hooks
->redirect_edge_and_branch
)
372 internal_error ("%s does not support redirect_edge_and_branch",
375 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
377 /* If RET != E, then either the redirection failed, or the edge E
378 was removed since RET already lead to the same destination. */
379 if (current_loops
!= NULL
&& ret
== e
)
380 rescan_loop_exit (e
, false, false);
385 /* Returns true if it is possible to remove the edge E by redirecting it
386 to the destination of the other edge going from its source. */
389 can_remove_branch_p (const_edge e
)
391 if (!cfg_hooks
->can_remove_branch_p
)
392 internal_error ("%s does not support can_remove_branch_p",
395 if (EDGE_COUNT (e
->src
->succs
) != 2)
398 return cfg_hooks
->can_remove_branch_p (e
);
401 /* Removes E, by redirecting it to the destination of the other edge going
402 from its source. Can_remove_branch_p must be true for E, hence this
403 operation cannot fail. */
406 remove_branch (edge e
)
409 basic_block src
= e
->src
;
412 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
414 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
415 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
417 e
= redirect_edge_and_branch (e
, other
->dest
);
418 gcc_assert (e
!= NULL
);
420 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
424 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
429 if (current_loops
!= NULL
)
431 rescan_loop_exit (e
, false, true);
433 /* Removal of an edge inside an irreducible region or which leads
434 to an irreducible region can turn the region into a natural loop.
435 In that case, ask for the loop structure fixups.
437 FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
438 set, so always ask for fixups when removing an edge in that case. */
439 if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
440 || (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
441 || (e
->dest
->flags
& BB_IRREDUCIBLE_LOOP
))
442 loops_state_set (LOOPS_NEED_FIXUP
);
445 /* This is probably not needed, but it doesn't hurt. */
446 /* FIXME: This should be called via a remove_edge hook. */
447 if (current_ir_type () == IR_GIMPLE
)
448 redirect_edge_var_map_clear (e
);
453 /* Like redirect_edge_succ but avoid possible duplicate edge. */
456 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
460 s
= find_edge (e
->src
, new_succ
);
463 s
->flags
|= e
->flags
;
464 s
->probability
+= e
->probability
;
465 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
466 redirect_edge_var_map_dup (s
, e
);
471 redirect_edge_succ (e
, new_succ
);
476 /* Redirect the edge E to basic block DEST even if it requires creating
477 of a new basic block; then it returns the newly created basic block.
478 Aborts when redirection is impossible. */
481 redirect_edge_and_branch_force (edge e
, basic_block dest
)
483 basic_block ret
, src
= e
->src
;
485 if (!cfg_hooks
->redirect_edge_and_branch_force
)
486 internal_error ("%s does not support redirect_edge_and_branch_force",
489 if (current_loops
!= NULL
)
490 rescan_loop_exit (e
, false, true);
492 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
494 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
495 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
497 if (current_loops
!= NULL
)
502 = find_common_loop (single_pred (ret
)->loop_father
,
503 single_succ (ret
)->loop_father
);
504 add_bb_to_loop (ret
, loop
);
506 else if (find_edge (src
, dest
) == e
)
507 rescan_loop_exit (e
, true, false);
513 /* Splits basic block BB after the specified instruction I (but at least after
514 the labels). If I is NULL, splits just after labels. The newly created edge
515 is returned. The new basic block is created just after the old one. */
518 split_block_1 (basic_block bb
, void *i
)
523 if (!cfg_hooks
->split_block
)
524 internal_error ("%s does not support split_block", cfg_hooks
->name
);
526 new_bb
= cfg_hooks
->split_block (bb
, i
);
530 new_bb
->count
= bb
->count
;
531 new_bb
->discriminator
= bb
->discriminator
;
533 if (dom_info_available_p (CDI_DOMINATORS
))
535 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
536 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
539 if (current_loops
!= NULL
)
543 add_bb_to_loop (new_bb
, bb
->loop_father
);
544 /* Identify all loops bb may have been the latch of and adjust them. */
545 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
546 if (e
->dest
->loop_father
->latch
== bb
)
547 e
->dest
->loop_father
->latch
= new_bb
;
550 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
552 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
554 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
555 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
562 split_block (basic_block bb
, gimple
*i
)
564 return split_block_1 (bb
, i
);
568 split_block (basic_block bb
, rtx i
)
570 return split_block_1 (bb
, i
);
573 /* Splits block BB just after labels. The newly created edge is returned. */
576 split_block_after_labels (basic_block bb
)
578 return split_block_1 (bb
, NULL
);
581 /* Moves block BB immediately after block AFTER. Returns false if the
582 movement was impossible. */
585 move_block_after (basic_block bb
, basic_block after
)
589 if (!cfg_hooks
->move_block_after
)
590 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
592 ret
= cfg_hooks
->move_block_after (bb
, after
);
597 /* Deletes the basic block BB. */
600 delete_basic_block (basic_block bb
)
602 if (!cfg_hooks
->delete_basic_block
)
603 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
605 cfg_hooks
->delete_basic_block (bb
);
607 if (current_loops
!= NULL
)
609 struct loop
*loop
= bb
->loop_father
;
611 /* If we remove the header or the latch of a loop, mark the loop for
613 if (loop
->latch
== bb
614 || loop
->header
== bb
)
615 mark_loop_for_removal (loop
);
617 remove_bb_from_loops (bb
);
620 /* Remove the edges into and out of this block. Note that there may
621 indeed be edges in, if we are removing an unreachable loop. */
622 while (EDGE_COUNT (bb
->preds
) != 0)
623 remove_edge (EDGE_PRED (bb
, 0));
624 while (EDGE_COUNT (bb
->succs
) != 0)
625 remove_edge (EDGE_SUCC (bb
, 0));
627 if (dom_info_available_p (CDI_DOMINATORS
))
628 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
629 if (dom_info_available_p (CDI_POST_DOMINATORS
))
630 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
632 /* Remove the basic block from the array. */
636 /* Splits edge E and returns the newly created basic block. */
642 profile_count count
= e
->count ();
644 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
646 basic_block src
= e
->src
, dest
= e
->dest
;
648 if (!cfg_hooks
->split_edge
)
649 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
651 if (current_loops
!= NULL
)
652 rescan_loop_exit (e
, false, true);
654 ret
= cfg_hooks
->split_edge (e
);
656 single_succ_edge (ret
)->probability
= profile_probability::always ();
660 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
661 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
662 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
665 if (dom_info_available_p (CDI_DOMINATORS
))
666 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
668 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
670 /* There are two cases:
672 If the immediate dominator of e->dest is not e->src, it
675 If immediate dominator of e->dest is e->src, it may become
676 ret, provided that all other predecessors of e->dest are
677 dominated by e->dest. */
679 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
680 == single_pred (ret
))
683 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
685 if (f
== single_succ_edge (ret
))
688 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
694 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
698 if (current_loops
!= NULL
)
700 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
701 add_bb_to_loop (ret
, loop
);
703 /* If we split the latch edge of loop adjust the latch block. */
704 if (loop
->latch
== src
705 && loop
->header
== dest
)
712 /* Creates a new basic block just after the basic block AFTER.
713 HEAD and END are the first and the last statement belonging
714 to the block. If both are NULL, an empty block is created. */
717 create_basic_block_1 (void *head
, void *end
, basic_block after
)
721 if (!cfg_hooks
->create_basic_block
)
722 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
724 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
726 if (dom_info_available_p (CDI_DOMINATORS
))
727 add_to_dominance_info (CDI_DOMINATORS
, ret
);
728 if (dom_info_available_p (CDI_POST_DOMINATORS
))
729 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
735 create_basic_block (gimple_seq seq
, basic_block after
)
737 return create_basic_block_1 (seq
, NULL
, after
);
741 create_basic_block (rtx head
, rtx end
, basic_block after
)
743 return create_basic_block_1 (head
, end
, after
);
747 /* Creates an empty basic block just after basic block AFTER. */
750 create_empty_bb (basic_block after
)
752 return create_basic_block_1 (NULL
, NULL
, after
);
755 /* Checks whether we may merge blocks BB1 and BB2. */
758 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
762 if (!cfg_hooks
->can_merge_blocks_p
)
763 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
765 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
771 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
773 if (!cfg_hooks
->predict_edge
)
774 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
776 cfg_hooks
->predict_edge (e
, predictor
, probability
);
780 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
782 if (!cfg_hooks
->predict_edge
)
783 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
785 return cfg_hooks
->predicted_by_p (bb
, predictor
);
788 /* Merges basic block B into basic block A. */
791 merge_blocks (basic_block a
, basic_block b
)
796 if (!cfg_hooks
->merge_blocks
)
797 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
799 cfg_hooks
->merge_blocks (a
, b
);
801 if (current_loops
!= NULL
)
803 /* If the block we merge into is a loop header do nothing unless ... */
804 if (a
->loop_father
->header
== a
)
806 /* ... we merge two loop headers, in which case we kill
808 if (b
->loop_father
->header
== b
)
809 mark_loop_for_removal (b
->loop_father
);
811 /* If we merge a loop header into its predecessor, update the loop
813 else if (b
->loop_father
->header
== b
)
815 remove_bb_from_loops (a
);
816 add_bb_to_loop (a
, b
->loop_father
);
817 a
->loop_father
->header
= a
;
819 /* If we merge a loop latch into its predecessor, update the loop
821 if (b
->loop_father
->latch
822 && b
->loop_father
->latch
== b
)
823 b
->loop_father
->latch
= a
;
824 remove_bb_from_loops (b
);
827 /* Normally there should only be one successor of A and that is B, but
828 partway though the merge of blocks for conditional_execution we'll
829 be merging a TEST block with THEN and ELSE successors. Free the
830 whole lot of them and hope the caller knows what they're doing. */
832 while (EDGE_COUNT (a
->succs
) != 0)
833 remove_edge (EDGE_SUCC (a
, 0));
835 /* Adjust the edges out of B for the new owner. */
836 FOR_EACH_EDGE (e
, ei
, b
->succs
)
839 if (current_loops
!= NULL
)
841 /* If b was a latch, a now is. */
842 if (e
->dest
->loop_father
->latch
== b
)
843 e
->dest
->loop_father
->latch
= a
;
844 rescan_loop_exit (e
, true, false);
848 a
->flags
|= b
->flags
;
850 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
851 b
->preds
= b
->succs
= NULL
;
853 if (dom_info_available_p (CDI_DOMINATORS
))
854 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
856 if (dom_info_available_p (CDI_DOMINATORS
))
857 delete_from_dominance_info (CDI_DOMINATORS
, b
);
858 if (dom_info_available_p (CDI_POST_DOMINATORS
))
859 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
864 /* Split BB into entry part and the rest (the rest is the newly created block).
865 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
866 part. Returns the edge connecting the entry part to the rest. */
869 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
870 void (*new_bb_cbk
) (basic_block
))
874 basic_block dummy
, jump
;
875 struct loop
*loop
, *ploop
, *cloop
;
877 if (!cfg_hooks
->make_forwarder_block
)
878 internal_error ("%s does not support make_forwarder_block",
881 fallthru
= split_block_after_labels (bb
);
882 dummy
= fallthru
->src
;
883 dummy
->count
= profile_count::zero ();
886 /* Redirect back edges we want to keep. */
887 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
891 if (redirect_edge_p (e
))
893 dummy
->count
+= e
->count ();
899 jump
= redirect_edge_and_branch_force (e
, bb
);
902 /* If we redirected the loop latch edge, the JUMP block now acts like
903 the new latch of the loop. */
904 if (current_loops
!= NULL
905 && dummy
->loop_father
!= NULL
906 && dummy
->loop_father
->header
== dummy
907 && dummy
->loop_father
->latch
== e_src
)
908 dummy
->loop_father
->latch
= jump
;
910 if (new_bb_cbk
!= NULL
)
915 if (dom_info_available_p (CDI_DOMINATORS
))
917 vec
<basic_block
> doms_to_fix
;
918 doms_to_fix
.create (2);
919 doms_to_fix
.quick_push (dummy
);
920 doms_to_fix
.quick_push (bb
);
921 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
922 doms_to_fix
.release ();
925 if (current_loops
!= NULL
)
927 /* If we do not split a loop header, then both blocks belong to the
928 same loop. In case we split loop header and do not redirect the
929 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
930 BB becomes the new header. If latch is not recorded for the loop,
931 we leave this updating on the caller (this may only happen during
933 loop
= dummy
->loop_father
;
934 if (loop
->header
== dummy
935 && loop
->latch
!= NULL
936 && find_edge (loop
->latch
, dummy
) == NULL
)
938 remove_bb_from_loops (dummy
);
942 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
944 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
946 add_bb_to_loop (dummy
, cloop
);
949 /* In case we split loop latch, update it. */
950 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
951 if (ploop
->latch
== dummy
)
955 cfg_hooks
->make_forwarder_block (fallthru
);
960 /* Try to make the edge fallthru. */
963 tidy_fallthru_edge (edge e
)
965 if (cfg_hooks
->tidy_fallthru_edge
)
966 cfg_hooks
->tidy_fallthru_edge (e
);
969 /* Fix up edges that now fall through, or rather should now fall through
970 but previously required a jump around now deleted blocks. Simplify
971 the search by only examining blocks numerically adjacent, since this
972 is how they were created.
974 ??? This routine is currently RTL specific. */
977 tidy_fallthru_edges (void)
981 if (!cfg_hooks
->tidy_fallthru_edge
)
984 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
987 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
988 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
994 /* We care about simple conditional or unconditional jumps with
997 If we had a conditional branch to the next instruction when
998 CFG was built, then there will only be one out edge for the
999 block which ended with the conditional branch (since we do
1000 not create duplicate edges).
1002 Furthermore, the edge will be marked as a fallthru because we
1003 merge the flags for the duplicate edges. So we do not want to
1004 check that the edge is not a FALLTHRU edge. */
1006 if (single_succ_p (b
))
1008 s
= single_succ_edge (b
);
1009 if (! (s
->flags
& EDGE_COMPLEX
)
1011 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1012 tidy_fallthru_edge (s
);
1017 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1018 (and possibly create new basic block) to make edge non-fallthru.
1019 Return newly created BB or NULL if none. */
1022 force_nonfallthru (edge e
)
1024 basic_block ret
, src
= e
->src
;
1026 if (!cfg_hooks
->force_nonfallthru
)
1027 internal_error ("%s does not support force_nonfallthru",
1030 ret
= cfg_hooks
->force_nonfallthru (e
);
1033 if (dom_info_available_p (CDI_DOMINATORS
))
1034 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1036 if (current_loops
!= NULL
)
1038 basic_block pred
= single_pred (ret
);
1039 basic_block succ
= single_succ (ret
);
1041 = find_common_loop (pred
->loop_father
, succ
->loop_father
);
1042 rescan_loop_exit (e
, false, true);
1043 add_bb_to_loop (ret
, loop
);
1045 /* If we split the latch edge of loop adjust the latch block. */
1046 if (loop
->latch
== pred
1047 && loop
->header
== succ
)
1055 /* Returns true if we can duplicate basic block BB. */
1058 can_duplicate_block_p (const_basic_block bb
)
1060 if (!cfg_hooks
->can_duplicate_block_p
)
1061 internal_error ("%s does not support can_duplicate_block_p",
1064 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1067 return cfg_hooks
->can_duplicate_block_p (bb
);
1070 /* Duplicates basic block BB and redirects edge E to it. Returns the
1071 new basic block. The new basic block is placed after the basic block
1075 duplicate_block (basic_block bb
, edge e
, basic_block after
, copy_bb_data
*id
)
1079 profile_count new_count
= e
? e
->count (): profile_count::uninitialized ();
1082 if (!cfg_hooks
->duplicate_block
)
1083 internal_error ("%s does not support duplicate_block",
1086 if (bb
->count
< new_count
)
1087 new_count
= bb
->count
;
1089 gcc_checking_assert (can_duplicate_block_p (bb
));
1091 new_bb
= cfg_hooks
->duplicate_block (bb
, id
);
1093 move_block_after (new_bb
, after
);
1095 new_bb
->flags
= (bb
->flags
& ~BB_DUPLICATED
);
1096 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1098 /* Since we are creating edges from a new block to successors
1099 of another block (which therefore are known to be disjoint), there
1100 is no need to actually check for duplicated edges. */
1101 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1102 n
->probability
= s
->probability
;
1108 new_bb
->count
= new_count
;
1109 bb
->count
-= new_count
;
1111 redirect_edge_and_branch_force (e
, new_bb
);
1114 new_bb
->count
= bb
->count
;
1116 set_bb_original (new_bb
, bb
);
1117 set_bb_copy (bb
, new_bb
);
1119 /* Add the new block to the copy of the loop of BB, or directly to the loop
1120 of BB if the loop is not being copied. */
1121 if (current_loops
!= NULL
)
1123 struct loop
*cloop
= bb
->loop_father
;
1124 struct loop
*copy
= get_loop_copy (cloop
);
1125 /* If we copied the loop header block but not the loop
1126 we have created a loop with multiple entries. Ditch the loop,
1127 add the new block to the outer loop and arrange for a fixup. */
1129 && cloop
->header
== bb
)
1131 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1132 mark_loop_for_removal (cloop
);
1136 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1137 /* If we copied the loop latch block but not the loop, adjust
1140 && cloop
->latch
== bb
)
1142 cloop
->latch
= NULL
;
1143 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1151 /* Return 1 if BB ends with a call, possibly followed by some
1152 instructions that must stay with the call, 0 otherwise. */
1155 block_ends_with_call_p (basic_block bb
)
1157 if (!cfg_hooks
->block_ends_with_call_p
)
1158 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1160 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1163 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1166 block_ends_with_condjump_p (const_basic_block bb
)
1168 if (!cfg_hooks
->block_ends_with_condjump_p
)
1169 internal_error ("%s does not support block_ends_with_condjump_p",
1172 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1175 /* Add fake edges to the function exit for any non constant and non noreturn
1176 calls, volatile inline assembly in the bitmap of blocks specified by
1177 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1180 The goal is to expose cases in which entering a basic block does not imply
1181 that all subsequent instructions must be executed. */
1184 flow_call_edges_add (sbitmap blocks
)
1186 if (!cfg_hooks
->flow_call_edges_add
)
1187 internal_error ("%s does not support flow_call_edges_add",
1190 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1193 /* This function is called immediately after edge E is added to the
1194 edge vector E->dest->preds. */
1197 execute_on_growing_pred (edge e
)
1199 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1200 && cfg_hooks
->execute_on_growing_pred
)
1201 cfg_hooks
->execute_on_growing_pred (e
);
1204 /* This function is called immediately before edge E is removed from
1205 the edge vector E->dest->preds. */
1208 execute_on_shrinking_pred (edge e
)
1210 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1211 && cfg_hooks
->execute_on_shrinking_pred
)
1212 cfg_hooks
->execute_on_shrinking_pred (e
);
1215 /* This is used inside loop versioning when we want to insert
1216 stmts/insns on the edges, which have a different behavior
1217 in tree's and in RTL, so we made a CFG hook. */
1219 lv_flush_pending_stmts (edge e
)
1221 if (cfg_hooks
->flush_pending_stmts
)
1222 cfg_hooks
->flush_pending_stmts (e
);
1225 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1226 a new version of the loop basic-blocks, the parameters here are
1227 exactly the same as in duplicate_loop_to_header_edge or
1228 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1229 additional work to maintain ssa information that's why there is
1230 a need to call the tree_duplicate_loop_to_header_edge rather
1231 than duplicate_loop_to_header_edge when we are in tree mode. */
1233 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1235 sbitmap wont_exit
, edge orig
,
1236 vec
<edge
> *to_remove
,
1239 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1240 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1246 /* Conditional jumps are represented differently in trees and RTL,
1247 this hook takes a basic block that is known to have a cond jump
1248 at its end and extracts the taken and not taken edges out of it
1249 and store it in E1 and E2 respectively. */
1251 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1253 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1254 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1257 /* Responsible for updating the ssa info (PHI nodes) on the
1258 new condition basic block that guards the versioned loop. */
1260 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1261 basic_block new_block
, edge e
)
1263 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1264 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1267 /* Conditions in trees and RTL are different so we need
1268 a different handling when we add the condition to the
1271 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1272 basic_block new_block
, void *cond
)
1274 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1275 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1278 /* Checks whether all N blocks in BBS array can be copied. */
1280 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1286 for (i
= 0; i
< n
; i
++)
1287 bbs
[i
]->flags
|= BB_DUPLICATED
;
1289 for (i
= 0; i
< n
; i
++)
1291 /* In case we should redirect abnormal edge during duplication, fail. */
1293 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1294 if ((e
->flags
& EDGE_ABNORMAL
)
1295 && (e
->dest
->flags
& BB_DUPLICATED
))
1301 if (!can_duplicate_block_p (bbs
[i
]))
1309 for (i
= 0; i
< n
; i
++)
1310 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1315 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1316 are placed into array NEW_BBS in the same order. Edges from basic blocks
1317 in BBS are also duplicated and copies of those that lead into BBS are
1318 redirected to appropriate newly created block. The function assigns bbs
1319 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1320 loop, so this must be set up correctly in advance)
1322 If UPDATE_DOMINANCE is true then this function updates dominators locally
1323 (LOOPS structure that contains the information about dominators is passed
1324 to enable this), otherwise it does not update the dominator information
1325 and it assumed that the caller will do this, perhaps by destroying and
1326 recreating it instead of trying to do an incremental update like this
1327 function does when update_dominance is true.
1329 BASE is the superloop to that basic block belongs; if its header or latch
1330 is copied, we do not set the new blocks as header or latch.
1332 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1333 also in the same order.
1335 Newly created basic blocks are put after the basic block AFTER in the
1336 instruction stream, and the order of the blocks in BBS array is preserved. */
1339 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1340 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1341 struct loop
*base
, basic_block after
, bool update_dominance
)
1344 basic_block bb
, new_bb
, dom_bb
;
1348 /* Mark the blocks to be copied. This is used by edge creation hooks
1349 to decide whether to reallocate PHI nodes capacity to avoid reallocating
1350 PHIs in the set of source BBs. */
1351 for (i
= 0; i
< n
; i
++)
1352 bbs
[i
]->flags
|= BB_DUPLICATED
;
1354 /* Duplicate bbs, update dominators, assign bbs to loops. */
1355 for (i
= 0; i
< n
; i
++)
1359 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
, &id
);
1361 if (bb
->loop_father
)
1363 /* Possibly set loop header. */
1364 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1365 new_bb
->loop_father
->header
= new_bb
;
1367 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1368 new_bb
->loop_father
->latch
= new_bb
;
1372 /* Set dominators. */
1373 if (update_dominance
)
1375 for (i
= 0; i
< n
; i
++)
1378 new_bb
= new_bbs
[i
];
1380 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1381 if (dom_bb
->flags
& BB_DUPLICATED
)
1383 dom_bb
= get_bb_copy (dom_bb
);
1384 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1389 /* Redirect edges. */
1390 for (j
= 0; j
< num_edges
; j
++)
1391 new_edges
[j
] = NULL
;
1392 for (i
= 0; i
< n
; i
++)
1395 new_bb
= new_bbs
[i
];
1398 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1400 for (j
= 0; j
< num_edges
; j
++)
1401 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1404 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1406 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1410 /* Clear information about duplicates. */
1411 for (i
= 0; i
< n
; i
++)
1412 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1415 /* Return true if BB contains only labels or non-executable
1418 empty_block_p (basic_block bb
)
1420 gcc_assert (cfg_hooks
->empty_block_p
);
1421 return cfg_hooks
->empty_block_p (bb
);
1424 /* Split a basic block if it ends with a conditional branch and if
1425 the other part of the block is not empty. */
1427 split_block_before_cond_jump (basic_block bb
)
1429 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1430 return cfg_hooks
->split_block_before_cond_jump (bb
);
1433 /* Work-horse for passes.c:check_profile_consistency.
1434 Do book-keeping of the CFG for the profile consistency checker.
1435 Store the counting in RECORD. */
1438 profile_record_check_consistency (profile_record
*record
)
1444 FOR_ALL_BB_FN (bb
, cfun
)
1446 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1447 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1449 profile_probability sum
= profile_probability::never ();
1450 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1451 sum
+= e
->probability
;
1452 if (EDGE_COUNT (bb
->succs
)
1453 && sum
.differs_from_p (profile_probability::always ()))
1454 record
->num_mismatched_freq_out
++;
1455 profile_count lsum
= profile_count::zero ();
1456 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1457 lsum
+= e
->count ();
1458 if (EDGE_COUNT (bb
->succs
) && (lsum
.differs_from_p (bb
->count
)))
1459 record
->num_mismatched_count_out
++;
1461 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1462 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1464 profile_probability sum
= profile_probability::never ();
1465 profile_count lsum
= profile_count::zero ();
1466 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1468 sum
+= e
->probability
;
1469 lsum
+= e
->count ();
1471 if (EDGE_COUNT (bb
->preds
)
1472 && sum
.differs_from_p (profile_probability::always ()))
1473 record
->num_mismatched_freq_in
++;
1474 if (lsum
.differs_from_p (bb
->count
))
1475 record
->num_mismatched_count_in
++;
1477 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1478 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1480 gcc_assert (cfg_hooks
->account_profile_record
);
1481 cfg_hooks
->account_profile_record (bb
, record
);
1485 /* Work-horse for passes.c:acount_profile.
1486 Do book-keeping of the CFG for the profile accounting.
1487 Store the counting in RECORD. */
1490 profile_record_account_profile (profile_record
*record
)
1494 FOR_ALL_BB_FN (bb
, cfun
)
1496 gcc_assert (cfg_hooks
->account_profile_record
);
1497 cfg_hooks
->account_profile_record (bb
, record
);
1502 # pragma GCC diagnostic pop