1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2015 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"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
38 #include "basic-block.h"
41 #include "diagnostic-core.h"
43 #include "pretty-print.h"
45 /* A pointer to one of the hooks containers. */
46 static struct cfg_hooks
*cfg_hooks
;
48 /* Initialization of functions specific to the rtl IR. */
50 rtl_register_cfg_hooks (void)
52 cfg_hooks
= &rtl_cfg_hooks
;
55 /* Initialization of functions specific to the rtl IR. */
57 cfg_layout_rtl_register_cfg_hooks (void)
59 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
62 /* Initialization of functions specific to the tree IR. */
65 gimple_register_cfg_hooks (void)
67 cfg_hooks
= &gimple_cfg_hooks
;
77 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
79 *cfg_hooks
= new_cfg_hooks
;
82 /* Returns current ir type. */
85 current_ir_type (void)
87 if (cfg_hooks
== &gimple_cfg_hooks
)
89 else if (cfg_hooks
== &rtl_cfg_hooks
)
91 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
92 return IR_RTL_CFGLAYOUT
;
97 /* Verify the CFG consistency.
99 Currently it does following: checks edge and basic block list correctness
100 and calls into IL dependent checking then. */
103 verify_flow_info (void)
105 size_t *edge_checksum
;
107 basic_block bb
, last_bb_seen
;
108 basic_block
*last_visited
;
110 timevar_push (TV_CFG_VERIFY
);
111 last_visited
= XCNEWVEC (basic_block
, last_basic_block_for_fn (cfun
));
112 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
114 /* Check bb chain & numbers. */
115 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
116 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
118 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
119 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, bb
->index
))
121 error ("bb %d on wrong place", bb
->index
);
125 if (bb
->prev_bb
!= last_bb_seen
)
127 error ("prev_bb of %d should be %d, not %d",
128 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
135 /* Now check the basic blocks (boundaries etc.) */
136 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
142 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
144 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
148 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
150 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
156 error ("verify_flow_info: Wrong count of block %i %i",
157 bb
->index
, (int)bb
->count
);
160 if (bb
->frequency
< 0)
162 error ("verify_flow_info: Wrong frequency of block %i %i",
163 bb
->index
, bb
->frequency
);
166 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
168 if (last_visited
[e
->dest
->index
] == bb
)
170 error ("verify_flow_info: Duplicate edge %i->%i",
171 e
->src
->index
, e
->dest
->index
);
174 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
176 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
177 e
->src
->index
, e
->dest
->index
, e
->probability
);
182 error ("verify_flow_info: Wrong count of edge %i->%i %i",
183 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
187 last_visited
[e
->dest
->index
] = bb
;
189 if (e
->flags
& EDGE_FALLTHRU
)
194 error ("verify_flow_info: Basic block %d succ edge is corrupted",
196 fprintf (stderr
, "Predecessor: ");
197 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
198 fprintf (stderr
, "\nSuccessor: ");
199 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
200 fprintf (stderr
, "\n");
204 edge_checksum
[e
->dest
->index
] += (size_t) e
;
208 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
212 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
216 error ("basic block %d pred edge is corrupted", bb
->index
);
217 fputs ("Predecessor: ", stderr
);
218 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
219 fputs ("\nSuccessor: ", stderr
);
220 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
221 fputc ('\n', stderr
);
225 if (ei
.index
!= e
->dest_idx
)
227 error ("basic block %d pred edge is corrupted", bb
->index
);
228 error ("its dest_idx should be %d, not %d",
229 ei
.index
, e
->dest_idx
);
230 fputs ("Predecessor: ", stderr
);
231 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
232 fputs ("\nSuccessor: ", stderr
);
233 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
234 fputc ('\n', stderr
);
238 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
242 /* Complete edge checksumming for ENTRY and EXIT. */
247 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
248 edge_checksum
[e
->dest
->index
] += (size_t) e
;
250 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
251 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
254 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
255 if (edge_checksum
[bb
->index
])
257 error ("basic block %i edge lists are corrupted", bb
->index
);
261 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
265 free (edge_checksum
);
267 if (cfg_hooks
->verify_flow_info
)
268 err
|= cfg_hooks
->verify_flow_info ();
270 internal_error ("verify_flow_info failed");
271 timevar_pop (TV_CFG_VERIFY
);
274 /* Print out one basic block BB to file OUTF. INDENT is printed at the
275 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
277 This function takes care of the purely graph related information.
278 The cfg hook for the active representation should dump
279 representation-specific information. */
282 dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
284 if (flags
& TDF_BLOCKS
)
285 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
286 if (cfg_hooks
->dump_bb
)
287 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
288 if (flags
& TDF_BLOCKS
)
289 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
294 debug (basic_block_def
&ref
)
296 dump_bb (stderr
, &ref
, 0, 0);
300 debug (basic_block_def
*ptr
)
305 fprintf (stderr
, "<nil>\n");
309 /* Dumps basic block BB to pretty-printer PP, for use as a label of
310 a DOT graph record-node. The implementation of this hook is
311 expected to write the label to the stream that is attached to PP.
312 Field separators between instructions are pipe characters printed
313 verbatim. Instructions should be written with some characters
314 escaped, using pp_write_text_as_dot_label_to_stream(). */
317 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
319 if (!cfg_hooks
->dump_bb_for_graph
)
320 internal_error ("%s does not support dump_bb_for_graph",
323 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
);
324 pp_printf (pp
, " FREQ:%i |", bb
->frequency
);
325 pp_write_text_to_stream (pp
);
326 if (!(dump_flags
& TDF_SLIM
))
327 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
330 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
332 dump_flow_info (FILE *file
, int flags
)
336 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
337 n_edges_for_fn (cfun
));
338 FOR_ALL_BB_FN (bb
, cfun
)
339 dump_bb (file
, bb
, 0, flags
);
344 /* Like above, but dump to stderr. To be called from debuggers. */
345 void debug_flow_info (void);
347 debug_flow_info (void)
349 dump_flow_info (stderr
, TDF_DETAILS
);
352 /* Redirect edge E to the given basic block DEST and update underlying program
353 representation. Returns edge representing redirected branch (that may not
354 be equivalent to E in the case of duplicate edges being removed) or NULL
355 if edge is not easily redirectable for whatever reason. */
358 redirect_edge_and_branch (edge e
, basic_block dest
)
362 if (!cfg_hooks
->redirect_edge_and_branch
)
363 internal_error ("%s does not support redirect_edge_and_branch",
366 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
368 /* If RET != E, then either the redirection failed, or the edge E
369 was removed since RET already lead to the same destination. */
370 if (current_loops
!= NULL
&& ret
== e
)
371 rescan_loop_exit (e
, false, false);
376 /* Returns true if it is possible to remove the edge E by redirecting it
377 to the destination of the other edge going from its source. */
380 can_remove_branch_p (const_edge e
)
382 if (!cfg_hooks
->can_remove_branch_p
)
383 internal_error ("%s does not support can_remove_branch_p",
386 if (EDGE_COUNT (e
->src
->succs
) != 2)
389 return cfg_hooks
->can_remove_branch_p (e
);
392 /* Removes E, by redirecting it to the destination of the other edge going
393 from its source. Can_remove_branch_p must be true for E, hence this
394 operation cannot fail. */
397 remove_branch (edge e
)
400 basic_block src
= e
->src
;
403 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
405 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
406 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
408 e
= redirect_edge_and_branch (e
, other
->dest
);
409 gcc_assert (e
!= NULL
);
411 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
415 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
420 if (current_loops
!= NULL
)
421 rescan_loop_exit (e
, false, true);
423 /* This is probably not needed, but it doesn't hurt. */
424 /* FIXME: This should be called via a remove_edge hook. */
425 if (current_ir_type () == IR_GIMPLE
)
426 redirect_edge_var_map_clear (e
);
431 /* Like redirect_edge_succ but avoid possible duplicate edge. */
434 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
438 s
= find_edge (e
->src
, new_succ
);
441 s
->flags
|= e
->flags
;
442 s
->probability
+= e
->probability
;
443 if (s
->probability
> REG_BR_PROB_BASE
)
444 s
->probability
= REG_BR_PROB_BASE
;
445 s
->count
+= e
->count
;
446 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
447 redirect_edge_var_map_dup (s
, e
);
452 redirect_edge_succ (e
, new_succ
);
457 /* Redirect the edge E to basic block DEST even if it requires creating
458 of a new basic block; then it returns the newly created basic block.
459 Aborts when redirection is impossible. */
462 redirect_edge_and_branch_force (edge e
, basic_block dest
)
464 basic_block ret
, src
= e
->src
;
466 if (!cfg_hooks
->redirect_edge_and_branch_force
)
467 internal_error ("%s does not support redirect_edge_and_branch_force",
470 if (current_loops
!= NULL
)
471 rescan_loop_exit (e
, false, true);
473 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
475 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
476 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
478 if (current_loops
!= NULL
)
483 = find_common_loop (single_pred (ret
)->loop_father
,
484 single_succ (ret
)->loop_father
);
485 add_bb_to_loop (ret
, loop
);
487 else if (find_edge (src
, dest
) == e
)
488 rescan_loop_exit (e
, true, false);
494 /* Splits basic block BB after the specified instruction I (but at least after
495 the labels). If I is NULL, splits just after labels. The newly created edge
496 is returned. The new basic block is created just after the old one. */
499 split_block_1 (basic_block bb
, void *i
)
504 if (!cfg_hooks
->split_block
)
505 internal_error ("%s does not support split_block", cfg_hooks
->name
);
507 new_bb
= cfg_hooks
->split_block (bb
, i
);
511 new_bb
->count
= bb
->count
;
512 new_bb
->frequency
= bb
->frequency
;
513 new_bb
->discriminator
= bb
->discriminator
;
515 if (dom_info_available_p (CDI_DOMINATORS
))
517 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
518 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
521 if (current_loops
!= NULL
)
525 add_bb_to_loop (new_bb
, bb
->loop_father
);
526 /* Identify all loops bb may have been the latch of and adjust them. */
527 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
528 if (e
->dest
->loop_father
->latch
== bb
)
529 e
->dest
->loop_father
->latch
= new_bb
;
532 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
534 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
536 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
537 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
544 split_block (basic_block bb
, gimple i
)
546 return split_block_1 (bb
, i
);
550 split_block (basic_block bb
, rtx i
)
552 return split_block_1 (bb
, i
);
555 /* Splits block BB just after labels. The newly created edge is returned. */
558 split_block_after_labels (basic_block bb
)
560 return split_block_1 (bb
, NULL
);
563 /* Moves block BB immediately after block AFTER. Returns false if the
564 movement was impossible. */
567 move_block_after (basic_block bb
, basic_block after
)
571 if (!cfg_hooks
->move_block_after
)
572 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
574 ret
= cfg_hooks
->move_block_after (bb
, after
);
579 /* Deletes the basic block BB. */
582 delete_basic_block (basic_block bb
)
584 if (!cfg_hooks
->delete_basic_block
)
585 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
587 cfg_hooks
->delete_basic_block (bb
);
589 if (current_loops
!= NULL
)
591 struct loop
*loop
= bb
->loop_father
;
593 /* If we remove the header or the latch of a loop, mark the loop for
595 if (loop
->latch
== bb
596 || loop
->header
== bb
)
597 mark_loop_for_removal (loop
);
599 remove_bb_from_loops (bb
);
602 /* Remove the edges into and out of this block. Note that there may
603 indeed be edges in, if we are removing an unreachable loop. */
604 while (EDGE_COUNT (bb
->preds
) != 0)
605 remove_edge (EDGE_PRED (bb
, 0));
606 while (EDGE_COUNT (bb
->succs
) != 0)
607 remove_edge (EDGE_SUCC (bb
, 0));
609 if (dom_info_available_p (CDI_DOMINATORS
))
610 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
611 if (dom_info_available_p (CDI_POST_DOMINATORS
))
612 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
614 /* Remove the basic block from the array. */
618 /* Splits edge E and returns the newly created basic block. */
624 gcov_type count
= e
->count
;
625 int freq
= EDGE_FREQUENCY (e
);
627 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
629 basic_block src
= e
->src
, dest
= e
->dest
;
631 if (!cfg_hooks
->split_edge
)
632 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
634 if (current_loops
!= NULL
)
635 rescan_loop_exit (e
, false, true);
637 ret
= cfg_hooks
->split_edge (e
);
639 ret
->frequency
= freq
;
640 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
641 single_succ_edge (ret
)->count
= count
;
645 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
646 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
647 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
650 if (dom_info_available_p (CDI_DOMINATORS
))
651 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
653 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
655 /* There are two cases:
657 If the immediate dominator of e->dest is not e->src, it
660 If immediate dominator of e->dest is e->src, it may become
661 ret, provided that all other predecessors of e->dest are
662 dominated by e->dest. */
664 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
665 == single_pred (ret
))
668 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
670 if (f
== single_succ_edge (ret
))
673 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
679 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
683 if (current_loops
!= NULL
)
685 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
686 add_bb_to_loop (ret
, loop
);
688 /* If we split the latch edge of loop adjust the latch block. */
689 if (loop
->latch
== src
690 && loop
->header
== dest
)
697 /* Creates a new basic block just after the basic block AFTER.
698 HEAD and END are the first and the last statement belonging
699 to the block. If both are NULL, an empty block is created. */
702 create_basic_block_1 (void *head
, void *end
, basic_block after
)
706 if (!cfg_hooks
->create_basic_block
)
707 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
709 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
711 if (dom_info_available_p (CDI_DOMINATORS
))
712 add_to_dominance_info (CDI_DOMINATORS
, ret
);
713 if (dom_info_available_p (CDI_POST_DOMINATORS
))
714 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
720 create_basic_block (gimple_seq seq
, basic_block after
)
722 return create_basic_block_1 (seq
, NULL
, after
);
726 create_basic_block (rtx head
, rtx end
, basic_block after
)
728 return create_basic_block_1 (head
, end
, after
);
732 /* Creates an empty basic block just after basic block AFTER. */
735 create_empty_bb (basic_block after
)
737 return create_basic_block_1 (NULL
, NULL
, after
);
740 /* Checks whether we may merge blocks BB1 and BB2. */
743 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
747 if (!cfg_hooks
->can_merge_blocks_p
)
748 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
750 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
756 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
758 if (!cfg_hooks
->predict_edge
)
759 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
761 cfg_hooks
->predict_edge (e
, predictor
, probability
);
765 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
767 if (!cfg_hooks
->predict_edge
)
768 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
770 return cfg_hooks
->predicted_by_p (bb
, predictor
);
773 /* Merges basic block B into basic block A. */
776 merge_blocks (basic_block a
, basic_block b
)
781 if (!cfg_hooks
->merge_blocks
)
782 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
784 cfg_hooks
->merge_blocks (a
, b
);
786 if (current_loops
!= NULL
)
788 /* If the block we merge into is a loop header do nothing unless ... */
789 if (a
->loop_father
->header
== a
)
791 /* ... we merge two loop headers, in which case we kill
793 if (b
->loop_father
->header
== b
)
794 mark_loop_for_removal (b
->loop_father
);
796 /* If we merge a loop header into its predecessor, update the loop
798 else if (b
->loop_father
->header
== b
)
800 remove_bb_from_loops (a
);
801 add_bb_to_loop (a
, b
->loop_father
);
802 a
->loop_father
->header
= a
;
804 /* If we merge a loop latch into its predecessor, update the loop
806 if (b
->loop_father
->latch
807 && b
->loop_father
->latch
== b
)
808 b
->loop_father
->latch
= a
;
809 remove_bb_from_loops (b
);
812 /* Normally there should only be one successor of A and that is B, but
813 partway though the merge of blocks for conditional_execution we'll
814 be merging a TEST block with THEN and ELSE successors. Free the
815 whole lot of them and hope the caller knows what they're doing. */
817 while (EDGE_COUNT (a
->succs
) != 0)
818 remove_edge (EDGE_SUCC (a
, 0));
820 /* Adjust the edges out of B for the new owner. */
821 FOR_EACH_EDGE (e
, ei
, b
->succs
)
824 if (current_loops
!= NULL
)
826 /* If b was a latch, a now is. */
827 if (e
->dest
->loop_father
->latch
== b
)
828 e
->dest
->loop_father
->latch
= a
;
829 rescan_loop_exit (e
, true, false);
833 a
->flags
|= b
->flags
;
835 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
836 b
->preds
= b
->succs
= NULL
;
838 if (dom_info_available_p (CDI_DOMINATORS
))
839 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
841 if (dom_info_available_p (CDI_DOMINATORS
))
842 delete_from_dominance_info (CDI_DOMINATORS
, b
);
843 if (dom_info_available_p (CDI_POST_DOMINATORS
))
844 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
849 /* Split BB into entry part and the rest (the rest is the newly created block).
850 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
851 part. Returns the edge connecting the entry part to the rest. */
854 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
855 void (*new_bb_cbk
) (basic_block
))
859 basic_block dummy
, jump
;
860 struct loop
*loop
, *ploop
, *cloop
;
862 if (!cfg_hooks
->make_forwarder_block
)
863 internal_error ("%s does not support make_forwarder_block",
866 fallthru
= split_block_after_labels (bb
);
867 dummy
= fallthru
->src
;
869 dummy
->frequency
= 0;
873 /* Redirect back edges we want to keep. */
874 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
878 if (redirect_edge_p (e
))
880 dummy
->frequency
+= EDGE_FREQUENCY (e
);
881 if (dummy
->frequency
> BB_FREQ_MAX
)
882 dummy
->frequency
= BB_FREQ_MAX
;
884 dummy
->count
+= e
->count
;
885 fallthru
->count
+= e
->count
;
891 jump
= redirect_edge_and_branch_force (e
, bb
);
894 /* If we redirected the loop latch edge, the JUMP block now acts like
895 the new latch of the loop. */
896 if (current_loops
!= NULL
897 && dummy
->loop_father
!= NULL
898 && dummy
->loop_father
->header
== dummy
899 && dummy
->loop_father
->latch
== e_src
)
900 dummy
->loop_father
->latch
= jump
;
902 if (new_bb_cbk
!= NULL
)
907 if (dom_info_available_p (CDI_DOMINATORS
))
909 vec
<basic_block
> doms_to_fix
;
910 doms_to_fix
.create (2);
911 doms_to_fix
.quick_push (dummy
);
912 doms_to_fix
.quick_push (bb
);
913 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
914 doms_to_fix
.release ();
917 if (current_loops
!= NULL
)
919 /* If we do not split a loop header, then both blocks belong to the
920 same loop. In case we split loop header and do not redirect the
921 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
922 BB becomes the new header. If latch is not recorded for the loop,
923 we leave this updating on the caller (this may only happen during
925 loop
= dummy
->loop_father
;
926 if (loop
->header
== dummy
927 && loop
->latch
!= NULL
928 && find_edge (loop
->latch
, dummy
) == NULL
)
930 remove_bb_from_loops (dummy
);
934 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
936 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
938 add_bb_to_loop (dummy
, cloop
);
941 /* In case we split loop latch, update it. */
942 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
943 if (ploop
->latch
== dummy
)
947 cfg_hooks
->make_forwarder_block (fallthru
);
952 /* Try to make the edge fallthru. */
955 tidy_fallthru_edge (edge e
)
957 if (cfg_hooks
->tidy_fallthru_edge
)
958 cfg_hooks
->tidy_fallthru_edge (e
);
961 /* Fix up edges that now fall through, or rather should now fall through
962 but previously required a jump around now deleted blocks. Simplify
963 the search by only examining blocks numerically adjacent, since this
964 is how they were created.
966 ??? This routine is currently RTL specific. */
969 tidy_fallthru_edges (void)
973 if (!cfg_hooks
->tidy_fallthru_edge
)
976 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
979 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
980 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
986 /* We care about simple conditional or unconditional jumps with
989 If we had a conditional branch to the next instruction when
990 CFG was built, then there will only be one out edge for the
991 block which ended with the conditional branch (since we do
992 not create duplicate edges).
994 Furthermore, the edge will be marked as a fallthru because we
995 merge the flags for the duplicate edges. So we do not want to
996 check that the edge is not a FALLTHRU edge. */
998 if (single_succ_p (b
))
1000 s
= single_succ_edge (b
);
1001 if (! (s
->flags
& EDGE_COMPLEX
)
1003 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1004 tidy_fallthru_edge (s
);
1009 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1010 (and possibly create new basic block) to make edge non-fallthru.
1011 Return newly created BB or NULL if none. */
1014 force_nonfallthru (edge e
)
1016 basic_block ret
, src
= e
->src
;
1018 if (!cfg_hooks
->force_nonfallthru
)
1019 internal_error ("%s does not support force_nonfallthru",
1022 ret
= cfg_hooks
->force_nonfallthru (e
);
1025 if (dom_info_available_p (CDI_DOMINATORS
))
1026 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1028 if (current_loops
!= NULL
)
1031 = find_common_loop (single_pred (ret
)->loop_father
,
1032 single_succ (ret
)->loop_father
);
1033 rescan_loop_exit (e
, false, true);
1034 add_bb_to_loop (ret
, loop
);
1041 /* Returns true if we can duplicate basic block BB. */
1044 can_duplicate_block_p (const_basic_block bb
)
1046 if (!cfg_hooks
->can_duplicate_block_p
)
1047 internal_error ("%s does not support can_duplicate_block_p",
1050 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1053 return cfg_hooks
->can_duplicate_block_p (bb
);
1056 /* Duplicates basic block BB and redirects edge E to it. Returns the
1057 new basic block. The new basic block is placed after the basic block
1061 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1065 gcov_type new_count
= e
? e
->count
: 0;
1068 if (!cfg_hooks
->duplicate_block
)
1069 internal_error ("%s does not support duplicate_block",
1072 if (bb
->count
< new_count
)
1073 new_count
= bb
->count
;
1075 gcc_checking_assert (can_duplicate_block_p (bb
));
1077 new_bb
= cfg_hooks
->duplicate_block (bb
);
1079 move_block_after (new_bb
, after
);
1081 new_bb
->flags
= bb
->flags
;
1082 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1084 /* Since we are creating edges from a new block to successors
1085 of another block (which therefore are known to be disjoint), there
1086 is no need to actually check for duplicated edges. */
1087 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1088 n
->probability
= s
->probability
;
1091 /* Take care for overflows! */
1092 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1093 s
->count
-= n
->count
;
1096 n
->count
= s
->count
;
1102 new_bb
->count
= new_count
;
1103 bb
->count
-= new_count
;
1105 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1106 bb
->frequency
-= EDGE_FREQUENCY (e
);
1108 redirect_edge_and_branch_force (e
, new_bb
);
1112 if (bb
->frequency
< 0)
1117 new_bb
->count
= bb
->count
;
1118 new_bb
->frequency
= bb
->frequency
;
1121 set_bb_original (new_bb
, bb
);
1122 set_bb_copy (bb
, new_bb
);
1124 /* Add the new block to the copy of the loop of BB, or directly to the loop
1125 of BB if the loop is not being copied. */
1126 if (current_loops
!= NULL
)
1128 struct loop
*cloop
= bb
->loop_father
;
1129 struct loop
*copy
= get_loop_copy (cloop
);
1130 /* If we copied the loop header block but not the loop
1131 we have created a loop with multiple entries. Ditch the loop,
1132 add the new block to the outer loop and arrange for a fixup. */
1134 && cloop
->header
== bb
)
1136 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1137 mark_loop_for_removal (cloop
);
1141 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1142 /* If we copied the loop latch block but not the loop, adjust
1145 && cloop
->latch
== bb
)
1147 cloop
->latch
= NULL
;
1148 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1156 /* Return 1 if BB ends with a call, possibly followed by some
1157 instructions that must stay with the call, 0 otherwise. */
1160 block_ends_with_call_p (basic_block bb
)
1162 if (!cfg_hooks
->block_ends_with_call_p
)
1163 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1165 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1168 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1171 block_ends_with_condjump_p (const_basic_block bb
)
1173 if (!cfg_hooks
->block_ends_with_condjump_p
)
1174 internal_error ("%s does not support block_ends_with_condjump_p",
1177 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1180 /* Add fake edges to the function exit for any non constant and non noreturn
1181 calls, volatile inline assembly in the bitmap of blocks specified by
1182 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1185 The goal is to expose cases in which entering a basic block does not imply
1186 that all subsequent instructions must be executed. */
1189 flow_call_edges_add (sbitmap blocks
)
1191 if (!cfg_hooks
->flow_call_edges_add
)
1192 internal_error ("%s does not support flow_call_edges_add",
1195 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1198 /* This function is called immediately after edge E is added to the
1199 edge vector E->dest->preds. */
1202 execute_on_growing_pred (edge e
)
1204 if (cfg_hooks
->execute_on_growing_pred
)
1205 cfg_hooks
->execute_on_growing_pred (e
);
1208 /* This function is called immediately before edge E is removed from
1209 the edge vector E->dest->preds. */
1212 execute_on_shrinking_pred (edge e
)
1214 if (cfg_hooks
->execute_on_shrinking_pred
)
1215 cfg_hooks
->execute_on_shrinking_pred (e
);
1218 /* This is used inside loop versioning when we want to insert
1219 stmts/insns on the edges, which have a different behavior
1220 in tree's and in RTL, so we made a CFG hook. */
1222 lv_flush_pending_stmts (edge e
)
1224 if (cfg_hooks
->flush_pending_stmts
)
1225 cfg_hooks
->flush_pending_stmts (e
);
1228 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1229 a new version of the loop basic-blocks, the parameters here are
1230 exactly the same as in duplicate_loop_to_header_edge or
1231 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1232 additional work to maintain ssa information that's why there is
1233 a need to call the tree_duplicate_loop_to_header_edge rather
1234 than duplicate_loop_to_header_edge when we are in tree mode. */
1236 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1238 sbitmap wont_exit
, edge orig
,
1239 vec
<edge
> *to_remove
,
1242 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1243 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1249 /* Conditional jumps are represented differently in trees and RTL,
1250 this hook takes a basic block that is known to have a cond jump
1251 at its end and extracts the taken and not taken edges out of it
1252 and store it in E1 and E2 respectively. */
1254 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1256 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1257 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1260 /* Responsible for updating the ssa info (PHI nodes) on the
1261 new condition basic block that guards the versioned loop. */
1263 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1264 basic_block new_block
, edge e
)
1266 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1267 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1270 /* Conditions in trees and RTL are different so we need
1271 a different handling when we add the condition to the
1274 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1275 basic_block new_block
, void *cond
)
1277 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1278 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1281 /* Checks whether all N blocks in BBS array can be copied. */
1283 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1289 for (i
= 0; i
< n
; i
++)
1290 bbs
[i
]->flags
|= BB_DUPLICATED
;
1292 for (i
= 0; i
< n
; i
++)
1294 /* In case we should redirect abnormal edge during duplication, fail. */
1296 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1297 if ((e
->flags
& EDGE_ABNORMAL
)
1298 && (e
->dest
->flags
& BB_DUPLICATED
))
1304 if (!can_duplicate_block_p (bbs
[i
]))
1312 for (i
= 0; i
< n
; i
++)
1313 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1318 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1319 are placed into array NEW_BBS in the same order. Edges from basic blocks
1320 in BBS are also duplicated and copies of those that lead into BBS are
1321 redirected to appropriate newly created block. The function assigns bbs
1322 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1323 loop, so this must be set up correctly in advance)
1325 If UPDATE_DOMINANCE is true then this function updates dominators locally
1326 (LOOPS structure that contains the information about dominators is passed
1327 to enable this), otherwise it does not update the dominator information
1328 and it assumed that the caller will do this, perhaps by destroying and
1329 recreating it instead of trying to do an incremental update like this
1330 function does when update_dominance is true.
1332 BASE is the superloop to that basic block belongs; if its header or latch
1333 is copied, we do not set the new blocks as header or latch.
1335 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1336 also in the same order.
1338 Newly created basic blocks are put after the basic block AFTER in the
1339 instruction stream, and the order of the blocks in BBS array is preserved. */
1342 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1343 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1344 struct loop
*base
, basic_block after
, bool update_dominance
)
1347 basic_block bb
, new_bb
, dom_bb
;
1350 /* Duplicate bbs, update dominators, assign bbs to loops. */
1351 for (i
= 0; i
< n
; i
++)
1355 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1357 bb
->flags
|= BB_DUPLICATED
;
1358 if (bb
->loop_father
)
1360 /* Possibly set loop header. */
1361 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1362 new_bb
->loop_father
->header
= new_bb
;
1364 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1365 new_bb
->loop_father
->latch
= new_bb
;
1369 /* Set dominators. */
1370 if (update_dominance
)
1372 for (i
= 0; i
< n
; i
++)
1375 new_bb
= new_bbs
[i
];
1377 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1378 if (dom_bb
->flags
& BB_DUPLICATED
)
1380 dom_bb
= get_bb_copy (dom_bb
);
1381 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1386 /* Redirect edges. */
1387 for (j
= 0; j
< num_edges
; j
++)
1388 new_edges
[j
] = NULL
;
1389 for (i
= 0; i
< n
; i
++)
1392 new_bb
= new_bbs
[i
];
1395 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1397 for (j
= 0; j
< num_edges
; j
++)
1398 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1401 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1403 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1407 /* Clear information about duplicates. */
1408 for (i
= 0; i
< n
; i
++)
1409 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1412 /* Return true if BB contains only labels or non-executable
1415 empty_block_p (basic_block bb
)
1417 gcc_assert (cfg_hooks
->empty_block_p
);
1418 return cfg_hooks
->empty_block_p (bb
);
1421 /* Split a basic block if it ends with a conditional branch and if
1422 the other part of the block is not empty. */
1424 split_block_before_cond_jump (basic_block bb
)
1426 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1427 return cfg_hooks
->split_block_before_cond_jump (bb
);
1430 /* Work-horse for passes.c:check_profile_consistency.
1431 Do book-keeping of the CFG for the profile consistency checker.
1432 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1433 then do post-pass accounting. Store the counting in RECORD. */
1436 account_profile_record (struct profile_record
*record
, int after_pass
)
1444 FOR_ALL_BB_FN (bb
, cfun
)
1446 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1447 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1450 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1451 sum
+= e
->probability
;
1452 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1453 record
->num_mismatched_freq_out
[after_pass
]++;
1455 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1457 if (EDGE_COUNT (bb
->succs
)
1458 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1459 record
->num_mismatched_count_out
[after_pass
]++;
1461 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1462 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1465 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1466 sum
+= EDGE_FREQUENCY (e
);
1467 if (abs (sum
- bb
->frequency
) > 100
1468 || (MAX (sum
, bb
->frequency
) > 10
1469 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1470 record
->num_mismatched_freq_in
[after_pass
]++;
1472 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1474 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1475 record
->num_mismatched_count_in
[after_pass
]++;
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
, after_pass
, record
);