1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2017 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 /* A pointer to one of the hooks containers. */
36 static struct cfg_hooks
*cfg_hooks
;
38 /* Initialization of functions specific to the rtl IR. */
40 rtl_register_cfg_hooks (void)
42 cfg_hooks
= &rtl_cfg_hooks
;
45 /* Initialization of functions specific to the rtl IR. */
47 cfg_layout_rtl_register_cfg_hooks (void)
49 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
52 /* Initialization of functions specific to the tree IR. */
55 gimple_register_cfg_hooks (void)
57 cfg_hooks
= &gimple_cfg_hooks
;
67 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
69 *cfg_hooks
= new_cfg_hooks
;
72 /* Returns current ir type. */
75 current_ir_type (void)
77 if (cfg_hooks
== &gimple_cfg_hooks
)
79 else if (cfg_hooks
== &rtl_cfg_hooks
)
81 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
82 return IR_RTL_CFGLAYOUT
;
87 /* Verify the CFG consistency.
89 Currently it does following: checks edge and basic block list correctness
90 and calls into IL dependent checking then. */
93 verify_flow_info (void)
95 size_t *edge_checksum
;
97 basic_block bb
, last_bb_seen
;
98 basic_block
*last_visited
;
100 timevar_push (TV_CFG_VERIFY
);
101 last_visited
= XCNEWVEC (basic_block
, last_basic_block_for_fn (cfun
));
102 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
104 /* Check bb chain & numbers. */
105 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
106 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
108 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
109 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, bb
->index
))
111 error ("bb %d on wrong place", bb
->index
);
115 if (bb
->prev_bb
!= last_bb_seen
)
117 error ("prev_bb of %d should be %d, not %d",
118 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
125 /* Now check the basic blocks (boundaries etc.) */
126 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
132 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
134 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
138 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
140 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
146 error ("verify_flow_info: Wrong count of block %i %i",
147 bb
->index
, (int)bb
->count
);
150 if (bb
->frequency
< 0)
152 error ("verify_flow_info: Wrong frequency of block %i %i",
153 bb
->index
, bb
->frequency
);
156 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
158 if (last_visited
[e
->dest
->index
] == bb
)
160 error ("verify_flow_info: Duplicate edge %i->%i",
161 e
->src
->index
, e
->dest
->index
);
164 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
166 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
167 e
->src
->index
, e
->dest
->index
, e
->probability
);
172 error ("verify_flow_info: Wrong count of edge %i->%i %i",
173 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
177 last_visited
[e
->dest
->index
] = bb
;
179 if (e
->flags
& EDGE_FALLTHRU
)
184 error ("verify_flow_info: Basic block %d succ edge is corrupted",
186 fprintf (stderr
, "Predecessor: ");
187 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
188 fprintf (stderr
, "\nSuccessor: ");
189 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
190 fprintf (stderr
, "\n");
194 edge_checksum
[e
->dest
->index
] += (size_t) e
;
198 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
202 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
206 error ("basic block %d pred edge is corrupted", bb
->index
);
207 fputs ("Predecessor: ", stderr
);
208 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
209 fputs ("\nSuccessor: ", stderr
);
210 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
211 fputc ('\n', stderr
);
215 if (ei
.index
!= e
->dest_idx
)
217 error ("basic block %d pred edge is corrupted", bb
->index
);
218 error ("its dest_idx should be %d, not %d",
219 ei
.index
, e
->dest_idx
);
220 fputs ("Predecessor: ", stderr
);
221 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
222 fputs ("\nSuccessor: ", stderr
);
223 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
224 fputc ('\n', stderr
);
228 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
232 /* Complete edge checksumming for ENTRY and EXIT. */
237 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
238 edge_checksum
[e
->dest
->index
] += (size_t) e
;
240 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
241 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
244 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
245 if (edge_checksum
[bb
->index
])
247 error ("basic block %i edge lists are corrupted", bb
->index
);
251 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
255 free (edge_checksum
);
257 if (cfg_hooks
->verify_flow_info
)
258 err
|= cfg_hooks
->verify_flow_info ();
260 internal_error ("verify_flow_info failed");
261 timevar_pop (TV_CFG_VERIFY
);
264 /* Print out one basic block BB to file OUTF. INDENT is printed at the
265 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
267 This function takes care of the purely graph related information.
268 The cfg hook for the active representation should dump
269 representation-specific information. */
272 dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
274 if (flags
& TDF_BLOCKS
)
275 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
276 if (cfg_hooks
->dump_bb
)
277 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
278 if (flags
& TDF_BLOCKS
)
279 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
284 debug (basic_block_def
&ref
)
286 dump_bb (stderr
, &ref
, 0, 0);
290 debug (basic_block_def
*ptr
)
295 fprintf (stderr
, "<nil>\n");
299 /* Dumps basic block BB to pretty-printer PP, for use as a label of
300 a DOT graph record-node. The implementation of this hook is
301 expected to write the label to the stream that is attached to PP.
302 Field separators between instructions are pipe characters printed
303 verbatim. Instructions should be written with some characters
304 escaped, using pp_write_text_as_dot_label_to_stream(). */
307 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
309 if (!cfg_hooks
->dump_bb_for_graph
)
310 internal_error ("%s does not support dump_bb_for_graph",
313 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
);
314 pp_printf (pp
, " FREQ:%i |", bb
->frequency
);
315 pp_write_text_to_stream (pp
);
316 if (!(dump_flags
& TDF_SLIM
))
317 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
320 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
322 dump_flow_info (FILE *file
, dump_flags_t flags
)
326 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
327 n_edges_for_fn (cfun
));
328 FOR_ALL_BB_FN (bb
, cfun
)
329 dump_bb (file
, bb
, 0, flags
);
334 /* Like above, but dump to stderr. To be called from debuggers. */
335 void debug_flow_info (void);
337 debug_flow_info (void)
339 dump_flow_info (stderr
, TDF_DETAILS
);
342 /* Redirect edge E to the given basic block DEST and update underlying program
343 representation. Returns edge representing redirected branch (that may not
344 be equivalent to E in the case of duplicate edges being removed) or NULL
345 if edge is not easily redirectable for whatever reason. */
348 redirect_edge_and_branch (edge e
, basic_block dest
)
352 if (!cfg_hooks
->redirect_edge_and_branch
)
353 internal_error ("%s does not support redirect_edge_and_branch",
356 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
358 /* If RET != E, then either the redirection failed, or the edge E
359 was removed since RET already lead to the same destination. */
360 if (current_loops
!= NULL
&& ret
== e
)
361 rescan_loop_exit (e
, false, false);
366 /* Returns true if it is possible to remove the edge E by redirecting it
367 to the destination of the other edge going from its source. */
370 can_remove_branch_p (const_edge e
)
372 if (!cfg_hooks
->can_remove_branch_p
)
373 internal_error ("%s does not support can_remove_branch_p",
376 if (EDGE_COUNT (e
->src
->succs
) != 2)
379 return cfg_hooks
->can_remove_branch_p (e
);
382 /* Removes E, by redirecting it to the destination of the other edge going
383 from its source. Can_remove_branch_p must be true for E, hence this
384 operation cannot fail. */
387 remove_branch (edge e
)
390 basic_block src
= e
->src
;
393 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
395 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
396 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
398 e
= redirect_edge_and_branch (e
, other
->dest
);
399 gcc_assert (e
!= NULL
);
401 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
405 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
410 if (current_loops
!= NULL
)
412 rescan_loop_exit (e
, false, true);
414 /* Removal of an edge inside an irreducible region or which leads
415 to an irreducible region can turn the region into a natural loop.
416 In that case, ask for the loop structure fixups.
418 FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
419 set, so always ask for fixups when removing an edge in that case. */
420 if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
421 || (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
422 || (e
->dest
->flags
& BB_IRREDUCIBLE_LOOP
))
423 loops_state_set (LOOPS_NEED_FIXUP
);
426 /* This is probably not needed, but it doesn't hurt. */
427 /* FIXME: This should be called via a remove_edge hook. */
428 if (current_ir_type () == IR_GIMPLE
)
429 redirect_edge_var_map_clear (e
);
434 /* Like redirect_edge_succ but avoid possible duplicate edge. */
437 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
441 s
= find_edge (e
->src
, new_succ
);
444 s
->flags
|= e
->flags
;
445 s
->probability
+= e
->probability
;
446 if (s
->probability
> REG_BR_PROB_BASE
)
447 s
->probability
= REG_BR_PROB_BASE
;
448 s
->count
+= e
->count
;
449 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
450 redirect_edge_var_map_dup (s
, e
);
455 redirect_edge_succ (e
, new_succ
);
460 /* Redirect the edge E to basic block DEST even if it requires creating
461 of a new basic block; then it returns the newly created basic block.
462 Aborts when redirection is impossible. */
465 redirect_edge_and_branch_force (edge e
, basic_block dest
)
467 basic_block ret
, src
= e
->src
;
469 if (!cfg_hooks
->redirect_edge_and_branch_force
)
470 internal_error ("%s does not support redirect_edge_and_branch_force",
473 if (current_loops
!= NULL
)
474 rescan_loop_exit (e
, false, true);
476 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
478 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
479 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
481 if (current_loops
!= NULL
)
486 = find_common_loop (single_pred (ret
)->loop_father
,
487 single_succ (ret
)->loop_father
);
488 add_bb_to_loop (ret
, loop
);
490 else if (find_edge (src
, dest
) == e
)
491 rescan_loop_exit (e
, true, false);
497 /* Splits basic block BB after the specified instruction I (but at least after
498 the labels). If I is NULL, splits just after labels. The newly created edge
499 is returned. The new basic block is created just after the old one. */
502 split_block_1 (basic_block bb
, void *i
)
507 if (!cfg_hooks
->split_block
)
508 internal_error ("%s does not support split_block", cfg_hooks
->name
);
510 new_bb
= cfg_hooks
->split_block (bb
, i
);
514 new_bb
->count
= bb
->count
;
515 new_bb
->frequency
= bb
->frequency
;
516 new_bb
->discriminator
= bb
->discriminator
;
518 if (dom_info_available_p (CDI_DOMINATORS
))
520 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
521 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
524 if (current_loops
!= NULL
)
528 add_bb_to_loop (new_bb
, bb
->loop_father
);
529 /* Identify all loops bb may have been the latch of and adjust them. */
530 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
531 if (e
->dest
->loop_father
->latch
== bb
)
532 e
->dest
->loop_father
->latch
= new_bb
;
535 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
537 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
539 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
540 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
547 split_block (basic_block bb
, gimple
*i
)
549 return split_block_1 (bb
, i
);
553 split_block (basic_block bb
, rtx i
)
555 return split_block_1 (bb
, i
);
558 /* Splits block BB just after labels. The newly created edge is returned. */
561 split_block_after_labels (basic_block bb
)
563 return split_block_1 (bb
, NULL
);
566 /* Moves block BB immediately after block AFTER. Returns false if the
567 movement was impossible. */
570 move_block_after (basic_block bb
, basic_block after
)
574 if (!cfg_hooks
->move_block_after
)
575 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
577 ret
= cfg_hooks
->move_block_after (bb
, after
);
582 /* Deletes the basic block BB. */
585 delete_basic_block (basic_block bb
)
587 if (!cfg_hooks
->delete_basic_block
)
588 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
590 cfg_hooks
->delete_basic_block (bb
);
592 if (current_loops
!= NULL
)
594 struct loop
*loop
= bb
->loop_father
;
596 /* If we remove the header or the latch of a loop, mark the loop for
598 if (loop
->latch
== bb
599 || loop
->header
== bb
)
600 mark_loop_for_removal (loop
);
602 remove_bb_from_loops (bb
);
605 /* Remove the edges into and out of this block. Note that there may
606 indeed be edges in, if we are removing an unreachable loop. */
607 while (EDGE_COUNT (bb
->preds
) != 0)
608 remove_edge (EDGE_PRED (bb
, 0));
609 while (EDGE_COUNT (bb
->succs
) != 0)
610 remove_edge (EDGE_SUCC (bb
, 0));
612 if (dom_info_available_p (CDI_DOMINATORS
))
613 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
614 if (dom_info_available_p (CDI_POST_DOMINATORS
))
615 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
617 /* Remove the basic block from the array. */
621 /* Splits edge E and returns the newly created basic block. */
627 gcov_type count
= e
->count
;
628 int freq
= EDGE_FREQUENCY (e
);
630 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
632 basic_block src
= e
->src
, dest
= e
->dest
;
634 if (!cfg_hooks
->split_edge
)
635 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
637 if (current_loops
!= NULL
)
638 rescan_loop_exit (e
, false, true);
640 ret
= cfg_hooks
->split_edge (e
);
642 ret
->frequency
= freq
;
643 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
644 single_succ_edge (ret
)->count
= count
;
648 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
649 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
650 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
653 if (dom_info_available_p (CDI_DOMINATORS
))
654 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
656 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
658 /* There are two cases:
660 If the immediate dominator of e->dest is not e->src, it
663 If immediate dominator of e->dest is e->src, it may become
664 ret, provided that all other predecessors of e->dest are
665 dominated by e->dest. */
667 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
668 == single_pred (ret
))
671 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
673 if (f
== single_succ_edge (ret
))
676 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
682 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
686 if (current_loops
!= NULL
)
688 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
689 add_bb_to_loop (ret
, loop
);
691 /* If we split the latch edge of loop adjust the latch block. */
692 if (loop
->latch
== src
693 && loop
->header
== dest
)
700 /* Creates a new basic block just after the basic block AFTER.
701 HEAD and END are the first and the last statement belonging
702 to the block. If both are NULL, an empty block is created. */
705 create_basic_block_1 (void *head
, void *end
, basic_block after
)
709 if (!cfg_hooks
->create_basic_block
)
710 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
712 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
714 if (dom_info_available_p (CDI_DOMINATORS
))
715 add_to_dominance_info (CDI_DOMINATORS
, ret
);
716 if (dom_info_available_p (CDI_POST_DOMINATORS
))
717 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
723 create_basic_block (gimple_seq seq
, basic_block after
)
725 return create_basic_block_1 (seq
, NULL
, after
);
729 create_basic_block (rtx head
, rtx end
, basic_block after
)
731 return create_basic_block_1 (head
, end
, after
);
735 /* Creates an empty basic block just after basic block AFTER. */
738 create_empty_bb (basic_block after
)
740 return create_basic_block_1 (NULL
, NULL
, after
);
743 /* Checks whether we may merge blocks BB1 and BB2. */
746 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
750 if (!cfg_hooks
->can_merge_blocks_p
)
751 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
753 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
759 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
761 if (!cfg_hooks
->predict_edge
)
762 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
764 cfg_hooks
->predict_edge (e
, predictor
, probability
);
768 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
770 if (!cfg_hooks
->predict_edge
)
771 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
773 return cfg_hooks
->predicted_by_p (bb
, predictor
);
776 /* Merges basic block B into basic block A. */
779 merge_blocks (basic_block a
, basic_block b
)
784 if (!cfg_hooks
->merge_blocks
)
785 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
787 cfg_hooks
->merge_blocks (a
, b
);
789 if (current_loops
!= NULL
)
791 /* If the block we merge into is a loop header do nothing unless ... */
792 if (a
->loop_father
->header
== a
)
794 /* ... we merge two loop headers, in which case we kill
796 if (b
->loop_father
->header
== b
)
797 mark_loop_for_removal (b
->loop_father
);
799 /* If we merge a loop header into its predecessor, update the loop
801 else if (b
->loop_father
->header
== b
)
803 remove_bb_from_loops (a
);
804 add_bb_to_loop (a
, b
->loop_father
);
805 a
->loop_father
->header
= a
;
807 /* If we merge a loop latch into its predecessor, update the loop
809 if (b
->loop_father
->latch
810 && b
->loop_father
->latch
== b
)
811 b
->loop_father
->latch
= a
;
812 remove_bb_from_loops (b
);
815 /* Normally there should only be one successor of A and that is B, but
816 partway though the merge of blocks for conditional_execution we'll
817 be merging a TEST block with THEN and ELSE successors. Free the
818 whole lot of them and hope the caller knows what they're doing. */
820 while (EDGE_COUNT (a
->succs
) != 0)
821 remove_edge (EDGE_SUCC (a
, 0));
823 /* Adjust the edges out of B for the new owner. */
824 FOR_EACH_EDGE (e
, ei
, b
->succs
)
827 if (current_loops
!= NULL
)
829 /* If b was a latch, a now is. */
830 if (e
->dest
->loop_father
->latch
== b
)
831 e
->dest
->loop_father
->latch
= a
;
832 rescan_loop_exit (e
, true, false);
836 a
->flags
|= b
->flags
;
838 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
839 b
->preds
= b
->succs
= NULL
;
841 if (dom_info_available_p (CDI_DOMINATORS
))
842 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
844 if (dom_info_available_p (CDI_DOMINATORS
))
845 delete_from_dominance_info (CDI_DOMINATORS
, b
);
846 if (dom_info_available_p (CDI_POST_DOMINATORS
))
847 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
852 /* Split BB into entry part and the rest (the rest is the newly created block).
853 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
854 part. Returns the edge connecting the entry part to the rest. */
857 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
858 void (*new_bb_cbk
) (basic_block
))
862 basic_block dummy
, jump
;
863 struct loop
*loop
, *ploop
, *cloop
;
865 if (!cfg_hooks
->make_forwarder_block
)
866 internal_error ("%s does not support make_forwarder_block",
869 fallthru
= split_block_after_labels (bb
);
870 dummy
= fallthru
->src
;
872 dummy
->frequency
= 0;
876 /* Redirect back edges we want to keep. */
877 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
881 if (redirect_edge_p (e
))
883 dummy
->frequency
+= EDGE_FREQUENCY (e
);
884 if (dummy
->frequency
> BB_FREQ_MAX
)
885 dummy
->frequency
= BB_FREQ_MAX
;
887 dummy
->count
+= e
->count
;
888 fallthru
->count
+= e
->count
;
894 jump
= redirect_edge_and_branch_force (e
, bb
);
897 /* If we redirected the loop latch edge, the JUMP block now acts like
898 the new latch of the loop. */
899 if (current_loops
!= NULL
900 && dummy
->loop_father
!= NULL
901 && dummy
->loop_father
->header
== dummy
902 && dummy
->loop_father
->latch
== e_src
)
903 dummy
->loop_father
->latch
= jump
;
905 if (new_bb_cbk
!= NULL
)
910 if (dom_info_available_p (CDI_DOMINATORS
))
912 vec
<basic_block
> doms_to_fix
;
913 doms_to_fix
.create (2);
914 doms_to_fix
.quick_push (dummy
);
915 doms_to_fix
.quick_push (bb
);
916 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
917 doms_to_fix
.release ();
920 if (current_loops
!= NULL
)
922 /* If we do not split a loop header, then both blocks belong to the
923 same loop. In case we split loop header and do not redirect the
924 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
925 BB becomes the new header. If latch is not recorded for the loop,
926 we leave this updating on the caller (this may only happen during
928 loop
= dummy
->loop_father
;
929 if (loop
->header
== dummy
930 && loop
->latch
!= NULL
931 && find_edge (loop
->latch
, dummy
) == NULL
)
933 remove_bb_from_loops (dummy
);
937 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
939 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
941 add_bb_to_loop (dummy
, cloop
);
944 /* In case we split loop latch, update it. */
945 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
946 if (ploop
->latch
== dummy
)
950 cfg_hooks
->make_forwarder_block (fallthru
);
955 /* Try to make the edge fallthru. */
958 tidy_fallthru_edge (edge e
)
960 if (cfg_hooks
->tidy_fallthru_edge
)
961 cfg_hooks
->tidy_fallthru_edge (e
);
964 /* Fix up edges that now fall through, or rather should now fall through
965 but previously required a jump around now deleted blocks. Simplify
966 the search by only examining blocks numerically adjacent, since this
967 is how they were created.
969 ??? This routine is currently RTL specific. */
972 tidy_fallthru_edges (void)
976 if (!cfg_hooks
->tidy_fallthru_edge
)
979 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
982 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
983 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
989 /* We care about simple conditional or unconditional jumps with
992 If we had a conditional branch to the next instruction when
993 CFG was built, then there will only be one out edge for the
994 block which ended with the conditional branch (since we do
995 not create duplicate edges).
997 Furthermore, the edge will be marked as a fallthru because we
998 merge the flags for the duplicate edges. So we do not want to
999 check that the edge is not a FALLTHRU edge. */
1001 if (single_succ_p (b
))
1003 s
= single_succ_edge (b
);
1004 if (! (s
->flags
& EDGE_COMPLEX
)
1006 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1007 tidy_fallthru_edge (s
);
1012 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1013 (and possibly create new basic block) to make edge non-fallthru.
1014 Return newly created BB or NULL if none. */
1017 force_nonfallthru (edge e
)
1019 basic_block ret
, src
= e
->src
;
1021 if (!cfg_hooks
->force_nonfallthru
)
1022 internal_error ("%s does not support force_nonfallthru",
1025 ret
= cfg_hooks
->force_nonfallthru (e
);
1028 if (dom_info_available_p (CDI_DOMINATORS
))
1029 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1031 if (current_loops
!= NULL
)
1033 basic_block pred
= single_pred (ret
);
1034 basic_block succ
= single_succ (ret
);
1036 = find_common_loop (pred
->loop_father
, succ
->loop_father
);
1037 rescan_loop_exit (e
, false, true);
1038 add_bb_to_loop (ret
, loop
);
1040 /* If we split the latch edge of loop adjust the latch block. */
1041 if (loop
->latch
== pred
1042 && loop
->header
== succ
)
1050 /* Returns true if we can duplicate basic block BB. */
1053 can_duplicate_block_p (const_basic_block bb
)
1055 if (!cfg_hooks
->can_duplicate_block_p
)
1056 internal_error ("%s does not support can_duplicate_block_p",
1059 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1062 return cfg_hooks
->can_duplicate_block_p (bb
);
1065 /* Duplicates basic block BB and redirects edge E to it. Returns the
1066 new basic block. The new basic block is placed after the basic block
1070 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1074 gcov_type new_count
= e
? e
->count
: 0;
1077 if (!cfg_hooks
->duplicate_block
)
1078 internal_error ("%s does not support duplicate_block",
1081 if (bb
->count
< new_count
)
1082 new_count
= bb
->count
;
1084 gcc_checking_assert (can_duplicate_block_p (bb
));
1086 new_bb
= cfg_hooks
->duplicate_block (bb
);
1088 move_block_after (new_bb
, after
);
1090 new_bb
->flags
= bb
->flags
;
1091 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1093 /* Since we are creating edges from a new block to successors
1094 of another block (which therefore are known to be disjoint), there
1095 is no need to actually check for duplicated edges. */
1096 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1097 n
->probability
= s
->probability
;
1100 /* Take care for overflows! */
1101 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1102 s
->count
-= n
->count
;
1105 n
->count
= s
->count
;
1111 new_bb
->count
= new_count
;
1112 bb
->count
-= new_count
;
1114 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1115 bb
->frequency
-= EDGE_FREQUENCY (e
);
1117 redirect_edge_and_branch_force (e
, new_bb
);
1121 if (bb
->frequency
< 0)
1126 new_bb
->count
= bb
->count
;
1127 new_bb
->frequency
= bb
->frequency
;
1130 set_bb_original (new_bb
, bb
);
1131 set_bb_copy (bb
, new_bb
);
1133 /* Add the new block to the copy of the loop of BB, or directly to the loop
1134 of BB if the loop is not being copied. */
1135 if (current_loops
!= NULL
)
1137 struct loop
*cloop
= bb
->loop_father
;
1138 struct loop
*copy
= get_loop_copy (cloop
);
1139 /* If we copied the loop header block but not the loop
1140 we have created a loop with multiple entries. Ditch the loop,
1141 add the new block to the outer loop and arrange for a fixup. */
1143 && cloop
->header
== bb
)
1145 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1146 mark_loop_for_removal (cloop
);
1150 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1151 /* If we copied the loop latch block but not the loop, adjust
1154 && cloop
->latch
== bb
)
1156 cloop
->latch
= NULL
;
1157 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1165 /* Return 1 if BB ends with a call, possibly followed by some
1166 instructions that must stay with the call, 0 otherwise. */
1169 block_ends_with_call_p (basic_block bb
)
1171 if (!cfg_hooks
->block_ends_with_call_p
)
1172 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1174 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1177 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1180 block_ends_with_condjump_p (const_basic_block bb
)
1182 if (!cfg_hooks
->block_ends_with_condjump_p
)
1183 internal_error ("%s does not support block_ends_with_condjump_p",
1186 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1189 /* Add fake edges to the function exit for any non constant and non noreturn
1190 calls, volatile inline assembly in the bitmap of blocks specified by
1191 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1194 The goal is to expose cases in which entering a basic block does not imply
1195 that all subsequent instructions must be executed. */
1198 flow_call_edges_add (sbitmap blocks
)
1200 if (!cfg_hooks
->flow_call_edges_add
)
1201 internal_error ("%s does not support flow_call_edges_add",
1204 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1207 /* This function is called immediately after edge E is added to the
1208 edge vector E->dest->preds. */
1211 execute_on_growing_pred (edge e
)
1213 if (cfg_hooks
->execute_on_growing_pred
)
1214 cfg_hooks
->execute_on_growing_pred (e
);
1217 /* This function is called immediately before edge E is removed from
1218 the edge vector E->dest->preds. */
1221 execute_on_shrinking_pred (edge e
)
1223 if (cfg_hooks
->execute_on_shrinking_pred
)
1224 cfg_hooks
->execute_on_shrinking_pred (e
);
1227 /* This is used inside loop versioning when we want to insert
1228 stmts/insns on the edges, which have a different behavior
1229 in tree's and in RTL, so we made a CFG hook. */
1231 lv_flush_pending_stmts (edge e
)
1233 if (cfg_hooks
->flush_pending_stmts
)
1234 cfg_hooks
->flush_pending_stmts (e
);
1237 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1238 a new version of the loop basic-blocks, the parameters here are
1239 exactly the same as in duplicate_loop_to_header_edge or
1240 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1241 additional work to maintain ssa information that's why there is
1242 a need to call the tree_duplicate_loop_to_header_edge rather
1243 than duplicate_loop_to_header_edge when we are in tree mode. */
1245 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1247 sbitmap wont_exit
, edge orig
,
1248 vec
<edge
> *to_remove
,
1251 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1252 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1258 /* Conditional jumps are represented differently in trees and RTL,
1259 this hook takes a basic block that is known to have a cond jump
1260 at its end and extracts the taken and not taken edges out of it
1261 and store it in E1 and E2 respectively. */
1263 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1265 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1266 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1269 /* Responsible for updating the ssa info (PHI nodes) on the
1270 new condition basic block that guards the versioned loop. */
1272 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1273 basic_block new_block
, edge e
)
1275 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1276 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1279 /* Conditions in trees and RTL are different so we need
1280 a different handling when we add the condition to the
1283 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1284 basic_block new_block
, void *cond
)
1286 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1287 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1290 /* Checks whether all N blocks in BBS array can be copied. */
1292 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1298 for (i
= 0; i
< n
; i
++)
1299 bbs
[i
]->flags
|= BB_DUPLICATED
;
1301 for (i
= 0; i
< n
; i
++)
1303 /* In case we should redirect abnormal edge during duplication, fail. */
1305 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1306 if ((e
->flags
& EDGE_ABNORMAL
)
1307 && (e
->dest
->flags
& BB_DUPLICATED
))
1313 if (!can_duplicate_block_p (bbs
[i
]))
1321 for (i
= 0; i
< n
; i
++)
1322 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1327 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1328 are placed into array NEW_BBS in the same order. Edges from basic blocks
1329 in BBS are also duplicated and copies of those that lead into BBS are
1330 redirected to appropriate newly created block. The function assigns bbs
1331 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1332 loop, so this must be set up correctly in advance)
1334 If UPDATE_DOMINANCE is true then this function updates dominators locally
1335 (LOOPS structure that contains the information about dominators is passed
1336 to enable this), otherwise it does not update the dominator information
1337 and it assumed that the caller will do this, perhaps by destroying and
1338 recreating it instead of trying to do an incremental update like this
1339 function does when update_dominance is true.
1341 BASE is the superloop to that basic block belongs; if its header or latch
1342 is copied, we do not set the new blocks as header or latch.
1344 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1345 also in the same order.
1347 Newly created basic blocks are put after the basic block AFTER in the
1348 instruction stream, and the order of the blocks in BBS array is preserved. */
1351 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1352 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1353 struct loop
*base
, basic_block after
, bool update_dominance
)
1356 basic_block bb
, new_bb
, dom_bb
;
1359 /* Duplicate bbs, update dominators, assign bbs to loops. */
1360 for (i
= 0; i
< n
; i
++)
1364 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1366 bb
->flags
|= BB_DUPLICATED
;
1367 if (bb
->loop_father
)
1369 /* Possibly set loop header. */
1370 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1371 new_bb
->loop_father
->header
= new_bb
;
1373 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1374 new_bb
->loop_father
->latch
= new_bb
;
1378 /* Set dominators. */
1379 if (update_dominance
)
1381 for (i
= 0; i
< n
; i
++)
1384 new_bb
= new_bbs
[i
];
1386 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1387 if (dom_bb
->flags
& BB_DUPLICATED
)
1389 dom_bb
= get_bb_copy (dom_bb
);
1390 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1395 /* Redirect edges. */
1396 for (j
= 0; j
< num_edges
; j
++)
1397 new_edges
[j
] = NULL
;
1398 for (i
= 0; i
< n
; i
++)
1401 new_bb
= new_bbs
[i
];
1404 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1406 for (j
= 0; j
< num_edges
; j
++)
1407 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1410 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1412 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1416 /* Clear information about duplicates. */
1417 for (i
= 0; i
< n
; i
++)
1418 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1421 /* Return true if BB contains only labels or non-executable
1424 empty_block_p (basic_block bb
)
1426 gcc_assert (cfg_hooks
->empty_block_p
);
1427 return cfg_hooks
->empty_block_p (bb
);
1430 /* Split a basic block if it ends with a conditional branch and if
1431 the other part of the block is not empty. */
1433 split_block_before_cond_jump (basic_block bb
)
1435 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1436 return cfg_hooks
->split_block_before_cond_jump (bb
);
1439 /* Work-horse for passes.c:check_profile_consistency.
1440 Do book-keeping of the CFG for the profile consistency checker.
1441 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1442 then do post-pass accounting. Store the counting in RECORD. */
1445 account_profile_record (struct profile_record
*record
, int after_pass
)
1453 FOR_ALL_BB_FN (bb
, cfun
)
1455 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1456 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1459 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1460 sum
+= e
->probability
;
1461 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1462 record
->num_mismatched_freq_out
[after_pass
]++;
1464 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1466 if (EDGE_COUNT (bb
->succs
)
1467 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1468 record
->num_mismatched_count_out
[after_pass
]++;
1470 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1471 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1474 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1475 sum
+= EDGE_FREQUENCY (e
);
1476 if (abs (sum
- bb
->frequency
) > 100
1477 || (MAX (sum
, bb
->frequency
) > 10
1478 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1479 record
->num_mismatched_freq_in
[after_pass
]++;
1481 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1483 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1484 record
->num_mismatched_count_in
[after_pass
]++;
1486 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1487 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1489 gcc_assert (cfg_hooks
->account_profile_record
);
1490 cfg_hooks
->account_profile_record (bb
, after_pass
, record
);