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
);
264 free (edge_checksum
);
266 if (cfg_hooks
->verify_flow_info
)
267 err
|= cfg_hooks
->verify_flow_info ();
269 internal_error ("verify_flow_info failed");
270 timevar_pop (TV_CFG_VERIFY
);
273 /* Print out one basic block BB to file OUTF. INDENT is printed at the
274 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
276 This function takes care of the purely graph related information.
277 The cfg hook for the active representation should dump
278 representation-specific information. */
281 dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
283 if (flags
& TDF_BLOCKS
)
284 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
285 if (cfg_hooks
->dump_bb
)
286 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
287 if (flags
& TDF_BLOCKS
)
288 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
293 debug (basic_block_def
&ref
)
295 dump_bb (stderr
, &ref
, 0, TDF_NONE
);
299 debug (basic_block_def
*ptr
)
304 fprintf (stderr
, "<nil>\n");
308 debug_slim (basic_block ptr
)
310 fprintf (stderr
, "<basic_block %p (%d)>", (void *) ptr
, ptr
->index
);
313 DEFINE_DEBUG_VEC (basic_block_def
*)
314 DEFINE_DEBUG_HASH_SET (basic_block_def
*)
316 /* Dumps basic block BB to pretty-printer PP, for use as a label of
317 a DOT graph record-node. The implementation of this hook is
318 expected to write the label to the stream that is attached to PP.
319 Field separators between instructions are pipe characters printed
320 verbatim. Instructions should be written with some characters
321 escaped, using pp_write_text_as_dot_label_to_stream(). */
324 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
326 if (!cfg_hooks
->dump_bb_for_graph
)
327 internal_error ("%s does not support dump_bb_for_graph",
329 /* TODO: Add pretty printer for counter. */
330 if (bb
->count
.initialized_p ())
331 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
.to_gcov_type ());
332 pp_write_text_to_stream (pp
);
333 if (!(dump_flags
& TDF_SLIM
))
334 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
337 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
339 dump_flow_info (FILE *file
, dump_flags_t flags
)
343 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
344 n_edges_for_fn (cfun
));
345 FOR_ALL_BB_FN (bb
, cfun
)
346 dump_bb (file
, bb
, 0, flags
);
351 /* Like above, but dump to stderr. To be called from debuggers. */
352 void debug_flow_info (void);
354 debug_flow_info (void)
356 dump_flow_info (stderr
, TDF_DETAILS
);
359 /* Redirect edge E to the given basic block DEST and update underlying program
360 representation. Returns edge representing redirected branch (that may not
361 be equivalent to E in the case of duplicate edges being removed) or NULL
362 if edge is not easily redirectable for whatever reason. */
365 redirect_edge_and_branch (edge e
, basic_block dest
)
369 if (!cfg_hooks
->redirect_edge_and_branch
)
370 internal_error ("%s does not support redirect_edge_and_branch",
373 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
375 /* If RET != E, then either the redirection failed, or the edge E
376 was removed since RET already lead to the same destination. */
377 if (current_loops
!= NULL
&& ret
== e
)
378 rescan_loop_exit (e
, false, false);
383 /* Returns true if it is possible to remove the edge E by redirecting it
384 to the destination of the other edge going from its source. */
387 can_remove_branch_p (const_edge e
)
389 if (!cfg_hooks
->can_remove_branch_p
)
390 internal_error ("%s does not support can_remove_branch_p",
393 if (EDGE_COUNT (e
->src
->succs
) != 2)
396 return cfg_hooks
->can_remove_branch_p (e
);
399 /* Removes E, by redirecting it to the destination of the other edge going
400 from its source. Can_remove_branch_p must be true for E, hence this
401 operation cannot fail. */
404 remove_branch (edge e
)
407 basic_block src
= e
->src
;
410 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
412 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
413 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
415 e
= redirect_edge_and_branch (e
, other
->dest
);
416 gcc_assert (e
!= NULL
);
418 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
422 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
427 if (current_loops
!= NULL
)
429 rescan_loop_exit (e
, false, true);
431 /* Removal of an edge inside an irreducible region or which leads
432 to an irreducible region can turn the region into a natural loop.
433 In that case, ask for the loop structure fixups.
435 FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
436 set, so always ask for fixups when removing an edge in that case. */
437 if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
438 || (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
439 || (e
->dest
->flags
& BB_IRREDUCIBLE_LOOP
))
440 loops_state_set (LOOPS_NEED_FIXUP
);
443 /* This is probably not needed, but it doesn't hurt. */
444 /* FIXME: This should be called via a remove_edge hook. */
445 if (current_ir_type () == IR_GIMPLE
)
446 redirect_edge_var_map_clear (e
);
451 /* Like redirect_edge_succ but avoid possible duplicate edge. */
454 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
458 s
= find_edge (e
->src
, new_succ
);
461 s
->flags
|= e
->flags
;
462 s
->probability
+= e
->probability
;
463 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
464 redirect_edge_var_map_dup (s
, e
);
469 redirect_edge_succ (e
, new_succ
);
474 /* Redirect the edge E to basic block DEST even if it requires creating
475 of a new basic block; then it returns the newly created basic block.
476 Aborts when redirection is impossible. */
479 redirect_edge_and_branch_force (edge e
, basic_block dest
)
481 basic_block ret
, src
= e
->src
;
483 if (!cfg_hooks
->redirect_edge_and_branch_force
)
484 internal_error ("%s does not support redirect_edge_and_branch_force",
487 if (current_loops
!= NULL
)
488 rescan_loop_exit (e
, false, true);
490 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
492 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
493 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
495 if (current_loops
!= NULL
)
500 = find_common_loop (single_pred (ret
)->loop_father
,
501 single_succ (ret
)->loop_father
);
502 add_bb_to_loop (ret
, loop
);
504 else if (find_edge (src
, dest
) == e
)
505 rescan_loop_exit (e
, true, false);
511 /* Splits basic block BB after the specified instruction I (but at least after
512 the labels). If I is NULL, splits just after labels. The newly created edge
513 is returned. The new basic block is created just after the old one. */
516 split_block_1 (basic_block bb
, void *i
)
521 if (!cfg_hooks
->split_block
)
522 internal_error ("%s does not support split_block", cfg_hooks
->name
);
524 new_bb
= cfg_hooks
->split_block (bb
, i
);
528 new_bb
->count
= bb
->count
;
529 new_bb
->discriminator
= bb
->discriminator
;
531 if (dom_info_available_p (CDI_DOMINATORS
))
533 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
534 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
537 if (current_loops
!= NULL
)
541 add_bb_to_loop (new_bb
, bb
->loop_father
);
542 /* Identify all loops bb may have been the latch of and adjust them. */
543 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
544 if (e
->dest
->loop_father
->latch
== bb
)
545 e
->dest
->loop_father
->latch
= new_bb
;
548 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
550 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
552 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
553 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
560 split_block (basic_block bb
, gimple
*i
)
562 return split_block_1 (bb
, i
);
566 split_block (basic_block bb
, rtx i
)
568 return split_block_1 (bb
, i
);
571 /* Splits block BB just after labels. The newly created edge is returned. */
574 split_block_after_labels (basic_block bb
)
576 return split_block_1 (bb
, NULL
);
579 /* Moves block BB immediately after block AFTER. Returns false if the
580 movement was impossible. */
583 move_block_after (basic_block bb
, basic_block after
)
587 if (!cfg_hooks
->move_block_after
)
588 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
590 ret
= cfg_hooks
->move_block_after (bb
, after
);
595 /* Deletes the basic block BB. */
598 delete_basic_block (basic_block bb
)
600 if (!cfg_hooks
->delete_basic_block
)
601 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
603 cfg_hooks
->delete_basic_block (bb
);
605 if (current_loops
!= NULL
)
607 class loop
*loop
= bb
->loop_father
;
609 /* If we remove the header or the latch of a loop, mark the loop for
611 if (loop
->latch
== bb
612 || loop
->header
== bb
)
613 mark_loop_for_removal (loop
);
615 remove_bb_from_loops (bb
);
618 /* Remove the edges into and out of this block. Note that there may
619 indeed be edges in, if we are removing an unreachable loop. */
620 while (EDGE_COUNT (bb
->preds
) != 0)
621 remove_edge (EDGE_PRED (bb
, 0));
622 while (EDGE_COUNT (bb
->succs
) != 0)
623 remove_edge (EDGE_SUCC (bb
, 0));
625 if (dom_info_available_p (CDI_DOMINATORS
))
626 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
627 if (dom_info_available_p (CDI_POST_DOMINATORS
))
628 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
630 /* Remove the basic block from the array. */
634 /* Splits edge E and returns the newly created basic block. */
640 profile_count count
= e
->count ();
642 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
644 basic_block src
= e
->src
, dest
= e
->dest
;
646 if (!cfg_hooks
->split_edge
)
647 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
649 if (current_loops
!= NULL
)
650 rescan_loop_exit (e
, false, true);
652 ret
= cfg_hooks
->split_edge (e
);
654 single_succ_edge (ret
)->probability
= profile_probability::always ();
658 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
659 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
660 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
663 if (dom_info_available_p (CDI_DOMINATORS
))
664 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
666 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
668 /* There are two cases:
670 If the immediate dominator of e->dest is not e->src, it
673 If immediate dominator of e->dest is e->src, it may become
674 ret, provided that all other predecessors of e->dest are
675 dominated by e->dest. */
677 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
678 == single_pred (ret
))
681 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
683 if (f
== single_succ_edge (ret
))
686 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
692 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
696 if (current_loops
!= NULL
)
698 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
699 add_bb_to_loop (ret
, loop
);
701 /* If we split the latch edge of loop adjust the latch block. */
702 if (loop
->latch
== src
703 && loop
->header
== dest
)
710 /* Creates a new basic block just after the basic block AFTER.
711 HEAD and END are the first and the last statement belonging
712 to the block. If both are NULL, an empty block is created. */
715 create_basic_block_1 (void *head
, void *end
, basic_block after
)
719 if (!cfg_hooks
->create_basic_block
)
720 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
722 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
724 if (dom_info_available_p (CDI_DOMINATORS
))
725 add_to_dominance_info (CDI_DOMINATORS
, ret
);
726 if (dom_info_available_p (CDI_POST_DOMINATORS
))
727 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
733 create_basic_block (gimple_seq seq
, basic_block after
)
735 return create_basic_block_1 (seq
, NULL
, after
);
739 create_basic_block (rtx head
, rtx end
, basic_block after
)
741 return create_basic_block_1 (head
, end
, after
);
745 /* Creates an empty basic block just after basic block AFTER. */
748 create_empty_bb (basic_block after
)
750 return create_basic_block_1 (NULL
, NULL
, after
);
753 /* Checks whether we may merge blocks BB1 and BB2. */
756 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
760 if (!cfg_hooks
->can_merge_blocks_p
)
761 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
763 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
769 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
771 if (!cfg_hooks
->predict_edge
)
772 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
774 cfg_hooks
->predict_edge (e
, predictor
, probability
);
778 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
780 if (!cfg_hooks
->predict_edge
)
781 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
783 return cfg_hooks
->predicted_by_p (bb
, predictor
);
786 /* Merges basic block B into basic block A. */
789 merge_blocks (basic_block a
, basic_block b
)
794 if (!cfg_hooks
->merge_blocks
)
795 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
797 cfg_hooks
->merge_blocks (a
, b
);
799 if (current_loops
!= NULL
)
801 /* If the block we merge into is a loop header do nothing unless ... */
802 if (a
->loop_father
->header
== a
)
804 /* ... we merge two loop headers, in which case we kill
806 if (b
->loop_father
->header
== b
)
807 mark_loop_for_removal (b
->loop_father
);
809 /* If we merge a loop header into its predecessor, update the loop
811 else if (b
->loop_father
->header
== b
)
813 remove_bb_from_loops (a
);
814 add_bb_to_loop (a
, b
->loop_father
);
815 a
->loop_father
->header
= a
;
817 /* If we merge a loop latch into its predecessor, update the loop
819 if (b
->loop_father
->latch
820 && b
->loop_father
->latch
== b
)
821 b
->loop_father
->latch
= a
;
822 remove_bb_from_loops (b
);
825 /* Normally there should only be one successor of A and that is B, but
826 partway though the merge of blocks for conditional_execution we'll
827 be merging a TEST block with THEN and ELSE successors. Free the
828 whole lot of them and hope the caller knows what they're doing. */
830 while (EDGE_COUNT (a
->succs
) != 0)
831 remove_edge (EDGE_SUCC (a
, 0));
833 /* Adjust the edges out of B for the new owner. */
834 FOR_EACH_EDGE (e
, ei
, b
->succs
)
837 if (current_loops
!= NULL
)
839 /* If b was a latch, a now is. */
840 if (e
->dest
->loop_father
->latch
== b
)
841 e
->dest
->loop_father
->latch
= a
;
842 rescan_loop_exit (e
, true, false);
846 a
->flags
|= b
->flags
;
848 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
849 b
->preds
= b
->succs
= NULL
;
851 if (dom_info_available_p (CDI_DOMINATORS
))
852 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
854 if (dom_info_available_p (CDI_DOMINATORS
))
855 delete_from_dominance_info (CDI_DOMINATORS
, b
);
856 if (dom_info_available_p (CDI_POST_DOMINATORS
))
857 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
862 /* Split BB into entry part and the rest (the rest is the newly created block).
863 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
864 part. Returns the edge connecting the entry part to the rest. */
867 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
868 void (*new_bb_cbk
) (basic_block
))
872 basic_block dummy
, jump
;
873 class loop
*loop
, *ploop
, *cloop
;
875 if (!cfg_hooks
->make_forwarder_block
)
876 internal_error ("%s does not support make_forwarder_block",
879 fallthru
= split_block_after_labels (bb
);
880 dummy
= fallthru
->src
;
881 dummy
->count
= profile_count::zero ();
884 /* Redirect back edges we want to keep. */
885 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
889 if (redirect_edge_p (e
))
891 dummy
->count
+= e
->count ();
897 jump
= redirect_edge_and_branch_force (e
, bb
);
900 /* If we redirected the loop latch edge, the JUMP block now acts like
901 the new latch of the loop. */
902 if (current_loops
!= NULL
903 && dummy
->loop_father
!= NULL
904 && dummy
->loop_father
->header
== dummy
905 && dummy
->loop_father
->latch
== e_src
)
906 dummy
->loop_father
->latch
= jump
;
908 if (new_bb_cbk
!= NULL
)
913 if (dom_info_available_p (CDI_DOMINATORS
))
915 vec
<basic_block
> doms_to_fix
;
916 doms_to_fix
.create (2);
917 doms_to_fix
.quick_push (dummy
);
918 doms_to_fix
.quick_push (bb
);
919 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
920 doms_to_fix
.release ();
923 if (current_loops
!= NULL
)
925 /* If we do not split a loop header, then both blocks belong to the
926 same loop. In case we split loop header and do not redirect the
927 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
928 BB becomes the new header. If latch is not recorded for the loop,
929 we leave this updating on the caller (this may only happen during
931 loop
= dummy
->loop_father
;
932 if (loop
->header
== dummy
933 && loop
->latch
!= NULL
934 && find_edge (loop
->latch
, dummy
) == NULL
)
936 remove_bb_from_loops (dummy
);
940 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
942 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
944 add_bb_to_loop (dummy
, cloop
);
947 /* In case we split loop latch, update it. */
948 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
949 if (ploop
->latch
== dummy
)
953 cfg_hooks
->make_forwarder_block (fallthru
);
958 /* Try to make the edge fallthru. */
961 tidy_fallthru_edge (edge e
)
963 if (cfg_hooks
->tidy_fallthru_edge
)
964 cfg_hooks
->tidy_fallthru_edge (e
);
967 /* Fix up edges that now fall through, or rather should now fall through
968 but previously required a jump around now deleted blocks. Simplify
969 the search by only examining blocks numerically adjacent, since this
970 is how they were created.
972 ??? This routine is currently RTL specific. */
975 tidy_fallthru_edges (void)
979 if (!cfg_hooks
->tidy_fallthru_edge
)
982 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
985 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
986 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
992 /* We care about simple conditional or unconditional jumps with
995 If we had a conditional branch to the next instruction when
996 CFG was built, then there will only be one out edge for the
997 block which ended with the conditional branch (since we do
998 not create duplicate edges).
1000 Furthermore, the edge will be marked as a fallthru because we
1001 merge the flags for the duplicate edges. So we do not want to
1002 check that the edge is not a FALLTHRU edge. */
1004 if (single_succ_p (b
))
1006 s
= single_succ_edge (b
);
1007 if (! (s
->flags
& EDGE_COMPLEX
)
1009 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1010 tidy_fallthru_edge (s
);
1015 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1016 (and possibly create new basic block) to make edge non-fallthru.
1017 Return newly created BB or NULL if none. */
1020 force_nonfallthru (edge e
)
1022 basic_block ret
, src
= e
->src
;
1024 if (!cfg_hooks
->force_nonfallthru
)
1025 internal_error ("%s does not support force_nonfallthru",
1028 ret
= cfg_hooks
->force_nonfallthru (e
);
1031 if (dom_info_available_p (CDI_DOMINATORS
))
1032 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1034 if (current_loops
!= NULL
)
1036 basic_block pred
= single_pred (ret
);
1037 basic_block succ
= single_succ (ret
);
1039 = find_common_loop (pred
->loop_father
, succ
->loop_father
);
1040 rescan_loop_exit (e
, false, true);
1041 add_bb_to_loop (ret
, loop
);
1043 /* If we split the latch edge of loop adjust the latch block. */
1044 if (loop
->latch
== pred
1045 && loop
->header
== succ
)
1053 /* Returns true if we can duplicate basic block BB. */
1056 can_duplicate_block_p (const_basic_block bb
)
1058 if (!cfg_hooks
->can_duplicate_block_p
)
1059 internal_error ("%s does not support can_duplicate_block_p",
1062 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1065 return cfg_hooks
->can_duplicate_block_p (bb
);
1068 /* Duplicates basic block BB and redirects edge E to it. Returns the
1069 new basic block. The new basic block is placed after the basic block
1073 duplicate_block (basic_block bb
, edge e
, basic_block after
, copy_bb_data
*id
)
1077 profile_count new_count
= e
? e
->count (): profile_count::uninitialized ();
1080 if (!cfg_hooks
->duplicate_block
)
1081 internal_error ("%s does not support duplicate_block",
1084 if (bb
->count
< new_count
)
1085 new_count
= bb
->count
;
1087 gcc_checking_assert (can_duplicate_block_p (bb
));
1089 new_bb
= cfg_hooks
->duplicate_block (bb
, id
);
1091 move_block_after (new_bb
, after
);
1093 new_bb
->flags
= (bb
->flags
& ~BB_DUPLICATED
);
1094 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1096 /* Since we are creating edges from a new block to successors
1097 of another block (which therefore are known to be disjoint), there
1098 is no need to actually check for duplicated edges. */
1099 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1100 n
->probability
= s
->probability
;
1106 new_bb
->count
= new_count
;
1107 bb
->count
-= new_count
;
1109 redirect_edge_and_branch_force (e
, new_bb
);
1112 new_bb
->count
= bb
->count
;
1114 set_bb_original (new_bb
, bb
);
1115 set_bb_copy (bb
, new_bb
);
1117 /* Add the new block to the copy of the loop of BB, or directly to the loop
1118 of BB if the loop is not being copied. */
1119 if (current_loops
!= NULL
)
1121 class loop
*cloop
= bb
->loop_father
;
1122 class loop
*copy
= get_loop_copy (cloop
);
1123 /* If we copied the loop header block but not the loop
1124 we have created a loop with multiple entries. Ditch the loop,
1125 add the new block to the outer loop and arrange for a fixup. */
1127 && cloop
->header
== bb
)
1129 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1130 mark_loop_for_removal (cloop
);
1134 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1135 /* If we copied the loop latch block but not the loop, adjust
1138 && cloop
->latch
== bb
)
1140 cloop
->latch
= NULL
;
1141 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1149 /* Return 1 if BB ends with a call, possibly followed by some
1150 instructions that must stay with the call, 0 otherwise. */
1153 block_ends_with_call_p (basic_block bb
)
1155 if (!cfg_hooks
->block_ends_with_call_p
)
1156 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1158 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1161 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1164 block_ends_with_condjump_p (const_basic_block bb
)
1166 if (!cfg_hooks
->block_ends_with_condjump_p
)
1167 internal_error ("%s does not support block_ends_with_condjump_p",
1170 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1173 /* Add fake edges to the function exit for any non constant and non noreturn
1174 calls, volatile inline assembly in the bitmap of blocks specified by
1175 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1178 The goal is to expose cases in which entering a basic block does not imply
1179 that all subsequent instructions must be executed. */
1182 flow_call_edges_add (sbitmap blocks
)
1184 if (!cfg_hooks
->flow_call_edges_add
)
1185 internal_error ("%s does not support flow_call_edges_add",
1188 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1191 /* This function is called immediately after edge E is added to the
1192 edge vector E->dest->preds. */
1195 execute_on_growing_pred (edge e
)
1197 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1198 && cfg_hooks
->execute_on_growing_pred
)
1199 cfg_hooks
->execute_on_growing_pred (e
);
1202 /* This function is called immediately before edge E is removed from
1203 the edge vector E->dest->preds. */
1206 execute_on_shrinking_pred (edge e
)
1208 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1209 && cfg_hooks
->execute_on_shrinking_pred
)
1210 cfg_hooks
->execute_on_shrinking_pred (e
);
1213 /* This is used inside loop versioning when we want to insert
1214 stmts/insns on the edges, which have a different behavior
1215 in tree's and in RTL, so we made a CFG hook. */
1217 lv_flush_pending_stmts (edge e
)
1219 if (cfg_hooks
->flush_pending_stmts
)
1220 cfg_hooks
->flush_pending_stmts (e
);
1223 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1224 a new version of the loop basic-blocks, the parameters here are
1225 exactly the same as in duplicate_loop_to_header_edge or
1226 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1227 additional work to maintain ssa information that's why there is
1228 a need to call the tree_duplicate_loop_to_header_edge rather
1229 than duplicate_loop_to_header_edge when we are in tree mode. */
1231 cfg_hook_duplicate_loop_to_header_edge (class loop
*loop
, edge e
,
1233 sbitmap wont_exit
, edge orig
,
1234 vec
<edge
> *to_remove
,
1237 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1238 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1244 /* Conditional jumps are represented differently in trees and RTL,
1245 this hook takes a basic block that is known to have a cond jump
1246 at its end and extracts the taken and not taken edges out of it
1247 and store it in E1 and E2 respectively. */
1249 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1251 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1252 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1255 /* Responsible for updating the ssa info (PHI nodes) on the
1256 new condition basic block that guards the versioned loop. */
1258 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1259 basic_block new_block
, edge e
)
1261 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1262 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1265 /* Conditions in trees and RTL are different so we need
1266 a different handling when we add the condition to the
1269 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1270 basic_block new_block
, void *cond
)
1272 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1273 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1276 /* Checks whether all N blocks in BBS array can be copied. */
1278 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1284 for (i
= 0; i
< n
; i
++)
1285 bbs
[i
]->flags
|= BB_DUPLICATED
;
1287 for (i
= 0; i
< n
; i
++)
1289 /* In case we should redirect abnormal edge during duplication, fail. */
1291 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1292 if ((e
->flags
& EDGE_ABNORMAL
)
1293 && (e
->dest
->flags
& BB_DUPLICATED
))
1299 if (!can_duplicate_block_p (bbs
[i
]))
1307 for (i
= 0; i
< n
; i
++)
1308 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1313 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1314 are placed into array NEW_BBS in the same order. Edges from basic blocks
1315 in BBS are also duplicated and copies of those that lead into BBS are
1316 redirected to appropriate newly created block. The function assigns bbs
1317 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1318 loop, so this must be set up correctly in advance)
1320 If UPDATE_DOMINANCE is true then this function updates dominators locally
1321 (LOOPS structure that contains the information about dominators is passed
1322 to enable this), otherwise it does not update the dominator information
1323 and it assumed that the caller will do this, perhaps by destroying and
1324 recreating it instead of trying to do an incremental update like this
1325 function does when update_dominance is true.
1327 BASE is the superloop to that basic block belongs; if its header or latch
1328 is copied, we do not set the new blocks as header or latch.
1330 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1331 also in the same order.
1333 Newly created basic blocks are put after the basic block AFTER in the
1334 instruction stream, and the order of the blocks in BBS array is preserved. */
1337 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1338 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1339 class loop
*base
, basic_block after
, bool update_dominance
)
1342 basic_block bb
, new_bb
, dom_bb
;
1346 /* Mark the blocks to be copied. This is used by edge creation hooks
1347 to decide whether to reallocate PHI nodes capacity to avoid reallocating
1348 PHIs in the set of source BBs. */
1349 for (i
= 0; i
< n
; i
++)
1350 bbs
[i
]->flags
|= BB_DUPLICATED
;
1352 /* Duplicate bbs, update dominators, assign bbs to loops. */
1353 for (i
= 0; i
< n
; i
++)
1357 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
, &id
);
1359 if (bb
->loop_father
)
1361 /* Possibly set loop header. */
1362 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1363 new_bb
->loop_father
->header
= new_bb
;
1365 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1366 new_bb
->loop_father
->latch
= new_bb
;
1370 /* Set dominators. */
1371 if (update_dominance
)
1373 for (i
= 0; i
< n
; i
++)
1376 new_bb
= new_bbs
[i
];
1378 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1379 if (dom_bb
->flags
& BB_DUPLICATED
)
1381 dom_bb
= get_bb_copy (dom_bb
);
1382 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1387 /* Redirect edges. */
1388 for (j
= 0; j
< num_edges
; j
++)
1389 new_edges
[j
] = NULL
;
1390 for (i
= 0; i
< n
; i
++)
1393 new_bb
= new_bbs
[i
];
1396 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1398 for (j
= 0; j
< num_edges
; j
++)
1399 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1402 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1404 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1408 /* Clear information about duplicates. */
1409 for (i
= 0; i
< n
; i
++)
1410 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1413 /* Return true if BB contains only labels or non-executable
1416 empty_block_p (basic_block bb
)
1418 gcc_assert (cfg_hooks
->empty_block_p
);
1419 return cfg_hooks
->empty_block_p (bb
);
1422 /* Split a basic block if it ends with a conditional branch and if
1423 the other part of the block is not empty. */
1425 split_block_before_cond_jump (basic_block bb
)
1427 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1428 return cfg_hooks
->split_block_before_cond_jump (bb
);
1431 /* Work-horse for passes.c:check_profile_consistency.
1432 Do book-keeping of the CFG for the profile consistency checker.
1433 Store the counting in RECORD. */
1436 profile_record_check_consistency (profile_record
*record
)
1442 FOR_ALL_BB_FN (bb
, cfun
)
1444 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1445 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1447 profile_probability sum
= profile_probability::never ();
1448 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1449 sum
+= e
->probability
;
1450 if (EDGE_COUNT (bb
->succs
)
1451 && sum
.differs_from_p (profile_probability::always ()))
1452 record
->num_mismatched_freq_out
++;
1453 profile_count lsum
= profile_count::zero ();
1454 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1455 lsum
+= e
->count ();
1456 if (EDGE_COUNT (bb
->succs
) && (lsum
.differs_from_p (bb
->count
)))
1457 record
->num_mismatched_count_out
++;
1459 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1460 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1462 profile_probability sum
= profile_probability::never ();
1463 profile_count lsum
= profile_count::zero ();
1464 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1466 sum
+= e
->probability
;
1467 lsum
+= e
->count ();
1469 if (EDGE_COUNT (bb
->preds
)
1470 && sum
.differs_from_p (profile_probability::always ()))
1471 record
->num_mismatched_freq_in
++;
1472 if (lsum
.differs_from_p (bb
->count
))
1473 record
->num_mismatched_count_in
++;
1475 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1476 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1478 gcc_assert (cfg_hooks
->account_profile_record
);
1479 cfg_hooks
->account_profile_record (bb
, record
);
1483 /* Work-horse for passes.c:acount_profile.
1484 Do book-keeping of the CFG for the profile accounting.
1485 Store the counting in RECORD. */
1488 profile_record_account_profile (profile_record
*record
)
1492 FOR_ALL_BB_FN (bb
, cfun
)
1494 gcc_assert (cfg_hooks
->account_profile_record
);
1495 cfg_hooks
->account_profile_record (bb
, record
);
1500 # pragma GCC diagnostic pop