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"
33 #include "diagnostic-core.h"
35 #include "pretty-print.h"
37 /* A pointer to one of the hooks containers. */
38 static struct cfg_hooks
*cfg_hooks
;
40 /* Initialization of functions specific to the rtl IR. */
42 rtl_register_cfg_hooks (void)
44 cfg_hooks
= &rtl_cfg_hooks
;
47 /* Initialization of functions specific to the rtl IR. */
49 cfg_layout_rtl_register_cfg_hooks (void)
51 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
54 /* Initialization of functions specific to the tree IR. */
57 gimple_register_cfg_hooks (void)
59 cfg_hooks
= &gimple_cfg_hooks
;
69 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
71 *cfg_hooks
= new_cfg_hooks
;
74 /* Returns current ir type. */
77 current_ir_type (void)
79 if (cfg_hooks
== &gimple_cfg_hooks
)
81 else if (cfg_hooks
== &rtl_cfg_hooks
)
83 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
84 return IR_RTL_CFGLAYOUT
;
89 /* Verify the CFG consistency.
91 Currently it does following: checks edge and basic block list correctness
92 and calls into IL dependent checking then. */
95 verify_flow_info (void)
97 size_t *edge_checksum
;
99 basic_block bb
, last_bb_seen
;
100 basic_block
*last_visited
;
102 timevar_push (TV_CFG_VERIFY
);
103 last_visited
= XCNEWVEC (basic_block
, last_basic_block_for_fn (cfun
));
104 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
106 /* Check bb chain & numbers. */
107 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
108 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
110 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
111 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, bb
->index
))
113 error ("bb %d on wrong place", bb
->index
);
117 if (bb
->prev_bb
!= last_bb_seen
)
119 error ("prev_bb of %d should be %d, not %d",
120 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
127 /* Now check the basic blocks (boundaries etc.) */
128 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
134 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
136 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
140 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
142 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
148 error ("verify_flow_info: Wrong count of block %i %i",
149 bb
->index
, (int)bb
->count
);
152 if (bb
->frequency
< 0)
154 error ("verify_flow_info: Wrong frequency of block %i %i",
155 bb
->index
, bb
->frequency
);
158 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
160 if (last_visited
[e
->dest
->index
] == bb
)
162 error ("verify_flow_info: Duplicate edge %i->%i",
163 e
->src
->index
, e
->dest
->index
);
166 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
168 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
169 e
->src
->index
, e
->dest
->index
, e
->probability
);
174 error ("verify_flow_info: Wrong count of edge %i->%i %i",
175 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
179 last_visited
[e
->dest
->index
] = bb
;
181 if (e
->flags
& EDGE_FALLTHRU
)
186 error ("verify_flow_info: Basic block %d succ edge is corrupted",
188 fprintf (stderr
, "Predecessor: ");
189 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
190 fprintf (stderr
, "\nSuccessor: ");
191 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
192 fprintf (stderr
, "\n");
196 edge_checksum
[e
->dest
->index
] += (size_t) e
;
200 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
204 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
208 error ("basic block %d pred edge is corrupted", bb
->index
);
209 fputs ("Predecessor: ", stderr
);
210 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
211 fputs ("\nSuccessor: ", stderr
);
212 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
213 fputc ('\n', stderr
);
217 if (ei
.index
!= e
->dest_idx
)
219 error ("basic block %d pred edge is corrupted", bb
->index
);
220 error ("its dest_idx should be %d, not %d",
221 ei
.index
, e
->dest_idx
);
222 fputs ("Predecessor: ", stderr
);
223 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
224 fputs ("\nSuccessor: ", stderr
);
225 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
226 fputc ('\n', stderr
);
230 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
234 /* Complete edge checksumming for ENTRY and EXIT. */
239 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
240 edge_checksum
[e
->dest
->index
] += (size_t) e
;
242 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
243 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
246 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
247 if (edge_checksum
[bb
->index
])
249 error ("basic block %i edge lists are corrupted", bb
->index
);
253 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
257 free (edge_checksum
);
259 if (cfg_hooks
->verify_flow_info
)
260 err
|= cfg_hooks
->verify_flow_info ();
262 internal_error ("verify_flow_info failed");
263 timevar_pop (TV_CFG_VERIFY
);
266 /* Print out one basic block BB to file OUTF. INDENT is printed at the
267 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
269 This function takes care of the purely graph related information.
270 The cfg hook for the active representation should dump
271 representation-specific information. */
274 dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
276 if (flags
& TDF_BLOCKS
)
277 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
278 if (cfg_hooks
->dump_bb
)
279 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
280 if (flags
& TDF_BLOCKS
)
281 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
286 debug (basic_block_def
&ref
)
288 dump_bb (stderr
, &ref
, 0, 0);
292 debug (basic_block_def
*ptr
)
297 fprintf (stderr
, "<nil>\n");
301 /* Dumps basic block BB to pretty-printer PP, for use as a label of
302 a DOT graph record-node. The implementation of this hook is
303 expected to write the label to the stream that is attached to PP.
304 Field separators between instructions are pipe characters printed
305 verbatim. Instructions should be written with some characters
306 escaped, using pp_write_text_as_dot_label_to_stream(). */
309 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
311 if (!cfg_hooks
->dump_bb_for_graph
)
312 internal_error ("%s does not support dump_bb_for_graph",
315 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
);
316 pp_printf (pp
, " FREQ:%i |", bb
->frequency
);
317 pp_write_text_to_stream (pp
);
318 if (!(dump_flags
& TDF_SLIM
))
319 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
322 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
324 dump_flow_info (FILE *file
, int flags
)
328 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
329 n_edges_for_fn (cfun
));
330 FOR_ALL_BB_FN (bb
, cfun
)
331 dump_bb (file
, bb
, 0, flags
);
336 /* Like above, but dump to stderr. To be called from debuggers. */
337 void debug_flow_info (void);
339 debug_flow_info (void)
341 dump_flow_info (stderr
, TDF_DETAILS
);
344 /* Redirect edge E to the given basic block DEST and update underlying program
345 representation. Returns edge representing redirected branch (that may not
346 be equivalent to E in the case of duplicate edges being removed) or NULL
347 if edge is not easily redirectable for whatever reason. */
350 redirect_edge_and_branch (edge e
, basic_block dest
)
354 if (!cfg_hooks
->redirect_edge_and_branch
)
355 internal_error ("%s does not support redirect_edge_and_branch",
358 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
360 /* If RET != E, then either the redirection failed, or the edge E
361 was removed since RET already lead to the same destination. */
362 if (current_loops
!= NULL
&& ret
== e
)
363 rescan_loop_exit (e
, false, false);
368 /* Returns true if it is possible to remove the edge E by redirecting it
369 to the destination of the other edge going from its source. */
372 can_remove_branch_p (const_edge e
)
374 if (!cfg_hooks
->can_remove_branch_p
)
375 internal_error ("%s does not support can_remove_branch_p",
378 if (EDGE_COUNT (e
->src
->succs
) != 2)
381 return cfg_hooks
->can_remove_branch_p (e
);
384 /* Removes E, by redirecting it to the destination of the other edge going
385 from its source. Can_remove_branch_p must be true for E, hence this
386 operation cannot fail. */
389 remove_branch (edge e
)
392 basic_block src
= e
->src
;
395 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
397 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
398 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
400 e
= redirect_edge_and_branch (e
, other
->dest
);
401 gcc_assert (e
!= NULL
);
403 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
407 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
412 if (current_loops
!= NULL
)
413 rescan_loop_exit (e
, false, true);
415 /* This is probably not needed, but it doesn't hurt. */
416 /* FIXME: This should be called via a remove_edge hook. */
417 if (current_ir_type () == IR_GIMPLE
)
418 redirect_edge_var_map_clear (e
);
423 /* Like redirect_edge_succ but avoid possible duplicate edge. */
426 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
430 s
= find_edge (e
->src
, new_succ
);
433 s
->flags
|= e
->flags
;
434 s
->probability
+= e
->probability
;
435 if (s
->probability
> REG_BR_PROB_BASE
)
436 s
->probability
= REG_BR_PROB_BASE
;
437 s
->count
+= e
->count
;
438 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
439 redirect_edge_var_map_dup (s
, e
);
444 redirect_edge_succ (e
, new_succ
);
449 /* Redirect the edge E to basic block DEST even if it requires creating
450 of a new basic block; then it returns the newly created basic block.
451 Aborts when redirection is impossible. */
454 redirect_edge_and_branch_force (edge e
, basic_block dest
)
456 basic_block ret
, src
= e
->src
;
458 if (!cfg_hooks
->redirect_edge_and_branch_force
)
459 internal_error ("%s does not support redirect_edge_and_branch_force",
462 if (current_loops
!= NULL
)
463 rescan_loop_exit (e
, false, true);
465 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
467 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
468 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
470 if (current_loops
!= NULL
)
475 = find_common_loop (single_pred (ret
)->loop_father
,
476 single_succ (ret
)->loop_father
);
477 add_bb_to_loop (ret
, loop
);
479 else if (find_edge (src
, dest
) == e
)
480 rescan_loop_exit (e
, true, false);
486 /* Splits basic block BB after the specified instruction I (but at least after
487 the labels). If I is NULL, splits just after labels. The newly created edge
488 is returned. The new basic block is created just after the old one. */
491 split_block_1 (basic_block bb
, void *i
)
496 if (!cfg_hooks
->split_block
)
497 internal_error ("%s does not support split_block", cfg_hooks
->name
);
499 new_bb
= cfg_hooks
->split_block (bb
, i
);
503 new_bb
->count
= bb
->count
;
504 new_bb
->frequency
= bb
->frequency
;
505 new_bb
->discriminator
= bb
->discriminator
;
507 if (dom_info_available_p (CDI_DOMINATORS
))
509 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
510 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
513 if (current_loops
!= NULL
)
517 add_bb_to_loop (new_bb
, bb
->loop_father
);
518 /* Identify all loops bb may have been the latch of and adjust them. */
519 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
520 if (e
->dest
->loop_father
->latch
== bb
)
521 e
->dest
->loop_father
->latch
= new_bb
;
524 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
526 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
528 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
529 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
536 split_block (basic_block bb
, gimple
*i
)
538 return split_block_1 (bb
, i
);
542 split_block (basic_block bb
, rtx i
)
544 return split_block_1 (bb
, i
);
547 /* Splits block BB just after labels. The newly created edge is returned. */
550 split_block_after_labels (basic_block bb
)
552 return split_block_1 (bb
, NULL
);
555 /* Moves block BB immediately after block AFTER. Returns false if the
556 movement was impossible. */
559 move_block_after (basic_block bb
, basic_block after
)
563 if (!cfg_hooks
->move_block_after
)
564 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
566 ret
= cfg_hooks
->move_block_after (bb
, after
);
571 /* Deletes the basic block BB. */
574 delete_basic_block (basic_block bb
)
576 if (!cfg_hooks
->delete_basic_block
)
577 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
579 cfg_hooks
->delete_basic_block (bb
);
581 if (current_loops
!= NULL
)
583 struct loop
*loop
= bb
->loop_father
;
585 /* If we remove the header or the latch of a loop, mark the loop for
587 if (loop
->latch
== bb
588 || loop
->header
== bb
)
589 mark_loop_for_removal (loop
);
591 remove_bb_from_loops (bb
);
594 /* Remove the edges into and out of this block. Note that there may
595 indeed be edges in, if we are removing an unreachable loop. */
596 while (EDGE_COUNT (bb
->preds
) != 0)
597 remove_edge (EDGE_PRED (bb
, 0));
598 while (EDGE_COUNT (bb
->succs
) != 0)
599 remove_edge (EDGE_SUCC (bb
, 0));
601 if (dom_info_available_p (CDI_DOMINATORS
))
602 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
603 if (dom_info_available_p (CDI_POST_DOMINATORS
))
604 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
606 /* Remove the basic block from the array. */
610 /* Splits edge E and returns the newly created basic block. */
616 gcov_type count
= e
->count
;
617 int freq
= EDGE_FREQUENCY (e
);
619 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
621 basic_block src
= e
->src
, dest
= e
->dest
;
623 if (!cfg_hooks
->split_edge
)
624 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
626 if (current_loops
!= NULL
)
627 rescan_loop_exit (e
, false, true);
629 ret
= cfg_hooks
->split_edge (e
);
631 ret
->frequency
= freq
;
632 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
633 single_succ_edge (ret
)->count
= count
;
637 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
638 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
639 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
642 if (dom_info_available_p (CDI_DOMINATORS
))
643 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
645 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
647 /* There are two cases:
649 If the immediate dominator of e->dest is not e->src, it
652 If immediate dominator of e->dest is e->src, it may become
653 ret, provided that all other predecessors of e->dest are
654 dominated by e->dest. */
656 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
657 == single_pred (ret
))
660 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
662 if (f
== single_succ_edge (ret
))
665 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
671 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
675 if (current_loops
!= NULL
)
677 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
678 add_bb_to_loop (ret
, loop
);
680 /* If we split the latch edge of loop adjust the latch block. */
681 if (loop
->latch
== src
682 && loop
->header
== dest
)
689 /* Creates a new basic block just after the basic block AFTER.
690 HEAD and END are the first and the last statement belonging
691 to the block. If both are NULL, an empty block is created. */
694 create_basic_block_1 (void *head
, void *end
, basic_block after
)
698 if (!cfg_hooks
->create_basic_block
)
699 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
701 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
703 if (dom_info_available_p (CDI_DOMINATORS
))
704 add_to_dominance_info (CDI_DOMINATORS
, ret
);
705 if (dom_info_available_p (CDI_POST_DOMINATORS
))
706 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
712 create_basic_block (gimple_seq seq
, basic_block after
)
714 return create_basic_block_1 (seq
, NULL
, after
);
718 create_basic_block (rtx head
, rtx end
, basic_block after
)
720 return create_basic_block_1 (head
, end
, after
);
724 /* Creates an empty basic block just after basic block AFTER. */
727 create_empty_bb (basic_block after
)
729 return create_basic_block_1 (NULL
, NULL
, after
);
732 /* Checks whether we may merge blocks BB1 and BB2. */
735 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
739 if (!cfg_hooks
->can_merge_blocks_p
)
740 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
742 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
748 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
750 if (!cfg_hooks
->predict_edge
)
751 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
753 cfg_hooks
->predict_edge (e
, predictor
, probability
);
757 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
759 if (!cfg_hooks
->predict_edge
)
760 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
762 return cfg_hooks
->predicted_by_p (bb
, predictor
);
765 /* Merges basic block B into basic block A. */
768 merge_blocks (basic_block a
, basic_block b
)
773 if (!cfg_hooks
->merge_blocks
)
774 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
776 cfg_hooks
->merge_blocks (a
, b
);
778 if (current_loops
!= NULL
)
780 /* If the block we merge into is a loop header do nothing unless ... */
781 if (a
->loop_father
->header
== a
)
783 /* ... we merge two loop headers, in which case we kill
785 if (b
->loop_father
->header
== b
)
786 mark_loop_for_removal (b
->loop_father
);
788 /* If we merge a loop header into its predecessor, update the loop
790 else if (b
->loop_father
->header
== b
)
792 remove_bb_from_loops (a
);
793 add_bb_to_loop (a
, b
->loop_father
);
794 a
->loop_father
->header
= a
;
796 /* If we merge a loop latch into its predecessor, update the loop
798 if (b
->loop_father
->latch
799 && b
->loop_father
->latch
== b
)
800 b
->loop_father
->latch
= a
;
801 remove_bb_from_loops (b
);
804 /* Normally there should only be one successor of A and that is B, but
805 partway though the merge of blocks for conditional_execution we'll
806 be merging a TEST block with THEN and ELSE successors. Free the
807 whole lot of them and hope the caller knows what they're doing. */
809 while (EDGE_COUNT (a
->succs
) != 0)
810 remove_edge (EDGE_SUCC (a
, 0));
812 /* Adjust the edges out of B for the new owner. */
813 FOR_EACH_EDGE (e
, ei
, b
->succs
)
816 if (current_loops
!= NULL
)
818 /* If b was a latch, a now is. */
819 if (e
->dest
->loop_father
->latch
== b
)
820 e
->dest
->loop_father
->latch
= a
;
821 rescan_loop_exit (e
, true, false);
825 a
->flags
|= b
->flags
;
827 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
828 b
->preds
= b
->succs
= NULL
;
830 if (dom_info_available_p (CDI_DOMINATORS
))
831 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
833 if (dom_info_available_p (CDI_DOMINATORS
))
834 delete_from_dominance_info (CDI_DOMINATORS
, b
);
835 if (dom_info_available_p (CDI_POST_DOMINATORS
))
836 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
841 /* Split BB into entry part and the rest (the rest is the newly created block).
842 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
843 part. Returns the edge connecting the entry part to the rest. */
846 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
847 void (*new_bb_cbk
) (basic_block
))
851 basic_block dummy
, jump
;
852 struct loop
*loop
, *ploop
, *cloop
;
854 if (!cfg_hooks
->make_forwarder_block
)
855 internal_error ("%s does not support make_forwarder_block",
858 fallthru
= split_block_after_labels (bb
);
859 dummy
= fallthru
->src
;
861 dummy
->frequency
= 0;
865 /* Redirect back edges we want to keep. */
866 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
870 if (redirect_edge_p (e
))
872 dummy
->frequency
+= EDGE_FREQUENCY (e
);
873 if (dummy
->frequency
> BB_FREQ_MAX
)
874 dummy
->frequency
= BB_FREQ_MAX
;
876 dummy
->count
+= e
->count
;
877 fallthru
->count
+= e
->count
;
883 jump
= redirect_edge_and_branch_force (e
, bb
);
886 /* If we redirected the loop latch edge, the JUMP block now acts like
887 the new latch of the loop. */
888 if (current_loops
!= NULL
889 && dummy
->loop_father
!= NULL
890 && dummy
->loop_father
->header
== dummy
891 && dummy
->loop_father
->latch
== e_src
)
892 dummy
->loop_father
->latch
= jump
;
894 if (new_bb_cbk
!= NULL
)
899 if (dom_info_available_p (CDI_DOMINATORS
))
901 vec
<basic_block
> doms_to_fix
;
902 doms_to_fix
.create (2);
903 doms_to_fix
.quick_push (dummy
);
904 doms_to_fix
.quick_push (bb
);
905 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
906 doms_to_fix
.release ();
909 if (current_loops
!= NULL
)
911 /* If we do not split a loop header, then both blocks belong to the
912 same loop. In case we split loop header and do not redirect the
913 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
914 BB becomes the new header. If latch is not recorded for the loop,
915 we leave this updating on the caller (this may only happen during
917 loop
= dummy
->loop_father
;
918 if (loop
->header
== dummy
919 && loop
->latch
!= NULL
920 && find_edge (loop
->latch
, dummy
) == NULL
)
922 remove_bb_from_loops (dummy
);
926 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
928 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
930 add_bb_to_loop (dummy
, cloop
);
933 /* In case we split loop latch, update it. */
934 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
935 if (ploop
->latch
== dummy
)
939 cfg_hooks
->make_forwarder_block (fallthru
);
944 /* Try to make the edge fallthru. */
947 tidy_fallthru_edge (edge e
)
949 if (cfg_hooks
->tidy_fallthru_edge
)
950 cfg_hooks
->tidy_fallthru_edge (e
);
953 /* Fix up edges that now fall through, or rather should now fall through
954 but previously required a jump around now deleted blocks. Simplify
955 the search by only examining blocks numerically adjacent, since this
956 is how they were created.
958 ??? This routine is currently RTL specific. */
961 tidy_fallthru_edges (void)
965 if (!cfg_hooks
->tidy_fallthru_edge
)
968 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
971 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
972 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
978 /* We care about simple conditional or unconditional jumps with
981 If we had a conditional branch to the next instruction when
982 CFG was built, then there will only be one out edge for the
983 block which ended with the conditional branch (since we do
984 not create duplicate edges).
986 Furthermore, the edge will be marked as a fallthru because we
987 merge the flags for the duplicate edges. So we do not want to
988 check that the edge is not a FALLTHRU edge. */
990 if (single_succ_p (b
))
992 s
= single_succ_edge (b
);
993 if (! (s
->flags
& EDGE_COMPLEX
)
995 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
996 tidy_fallthru_edge (s
);
1001 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1002 (and possibly create new basic block) to make edge non-fallthru.
1003 Return newly created BB or NULL if none. */
1006 force_nonfallthru (edge e
)
1008 basic_block ret
, src
= e
->src
;
1010 if (!cfg_hooks
->force_nonfallthru
)
1011 internal_error ("%s does not support force_nonfallthru",
1014 ret
= cfg_hooks
->force_nonfallthru (e
);
1017 if (dom_info_available_p (CDI_DOMINATORS
))
1018 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1020 if (current_loops
!= NULL
)
1023 = find_common_loop (single_pred (ret
)->loop_father
,
1024 single_succ (ret
)->loop_father
);
1025 rescan_loop_exit (e
, false, true);
1026 add_bb_to_loop (ret
, loop
);
1033 /* Returns true if we can duplicate basic block BB. */
1036 can_duplicate_block_p (const_basic_block bb
)
1038 if (!cfg_hooks
->can_duplicate_block_p
)
1039 internal_error ("%s does not support can_duplicate_block_p",
1042 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1045 return cfg_hooks
->can_duplicate_block_p (bb
);
1048 /* Duplicates basic block BB and redirects edge E to it. Returns the
1049 new basic block. The new basic block is placed after the basic block
1053 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1057 gcov_type new_count
= e
? e
->count
: 0;
1060 if (!cfg_hooks
->duplicate_block
)
1061 internal_error ("%s does not support duplicate_block",
1064 if (bb
->count
< new_count
)
1065 new_count
= bb
->count
;
1067 gcc_checking_assert (can_duplicate_block_p (bb
));
1069 new_bb
= cfg_hooks
->duplicate_block (bb
);
1071 move_block_after (new_bb
, after
);
1073 new_bb
->flags
= bb
->flags
;
1074 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1076 /* Since we are creating edges from a new block to successors
1077 of another block (which therefore are known to be disjoint), there
1078 is no need to actually check for duplicated edges. */
1079 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1080 n
->probability
= s
->probability
;
1083 /* Take care for overflows! */
1084 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1085 s
->count
-= n
->count
;
1088 n
->count
= s
->count
;
1094 new_bb
->count
= new_count
;
1095 bb
->count
-= new_count
;
1097 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1098 bb
->frequency
-= EDGE_FREQUENCY (e
);
1100 redirect_edge_and_branch_force (e
, new_bb
);
1104 if (bb
->frequency
< 0)
1109 new_bb
->count
= bb
->count
;
1110 new_bb
->frequency
= bb
->frequency
;
1113 set_bb_original (new_bb
, bb
);
1114 set_bb_copy (bb
, new_bb
);
1116 /* Add the new block to the copy of the loop of BB, or directly to the loop
1117 of BB if the loop is not being copied. */
1118 if (current_loops
!= NULL
)
1120 struct loop
*cloop
= bb
->loop_father
;
1121 struct loop
*copy
= get_loop_copy (cloop
);
1122 /* If we copied the loop header block but not the loop
1123 we have created a loop with multiple entries. Ditch the loop,
1124 add the new block to the outer loop and arrange for a fixup. */
1126 && cloop
->header
== bb
)
1128 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1129 mark_loop_for_removal (cloop
);
1133 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1134 /* If we copied the loop latch block but not the loop, adjust
1137 && cloop
->latch
== bb
)
1139 cloop
->latch
= NULL
;
1140 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1148 /* Return 1 if BB ends with a call, possibly followed by some
1149 instructions that must stay with the call, 0 otherwise. */
1152 block_ends_with_call_p (basic_block bb
)
1154 if (!cfg_hooks
->block_ends_with_call_p
)
1155 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1157 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1160 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1163 block_ends_with_condjump_p (const_basic_block bb
)
1165 if (!cfg_hooks
->block_ends_with_condjump_p
)
1166 internal_error ("%s does not support block_ends_with_condjump_p",
1169 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1172 /* Add fake edges to the function exit for any non constant and non noreturn
1173 calls, volatile inline assembly in the bitmap of blocks specified by
1174 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1177 The goal is to expose cases in which entering a basic block does not imply
1178 that all subsequent instructions must be executed. */
1181 flow_call_edges_add (sbitmap blocks
)
1183 if (!cfg_hooks
->flow_call_edges_add
)
1184 internal_error ("%s does not support flow_call_edges_add",
1187 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1190 /* This function is called immediately after edge E is added to the
1191 edge vector E->dest->preds. */
1194 execute_on_growing_pred (edge e
)
1196 if (cfg_hooks
->execute_on_growing_pred
)
1197 cfg_hooks
->execute_on_growing_pred (e
);
1200 /* This function is called immediately before edge E is removed from
1201 the edge vector E->dest->preds. */
1204 execute_on_shrinking_pred (edge e
)
1206 if (cfg_hooks
->execute_on_shrinking_pred
)
1207 cfg_hooks
->execute_on_shrinking_pred (e
);
1210 /* This is used inside loop versioning when we want to insert
1211 stmts/insns on the edges, which have a different behavior
1212 in tree's and in RTL, so we made a CFG hook. */
1214 lv_flush_pending_stmts (edge e
)
1216 if (cfg_hooks
->flush_pending_stmts
)
1217 cfg_hooks
->flush_pending_stmts (e
);
1220 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1221 a new version of the loop basic-blocks, the parameters here are
1222 exactly the same as in duplicate_loop_to_header_edge or
1223 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1224 additional work to maintain ssa information that's why there is
1225 a need to call the tree_duplicate_loop_to_header_edge rather
1226 than duplicate_loop_to_header_edge when we are in tree mode. */
1228 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1230 sbitmap wont_exit
, edge orig
,
1231 vec
<edge
> *to_remove
,
1234 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1235 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1241 /* Conditional jumps are represented differently in trees and RTL,
1242 this hook takes a basic block that is known to have a cond jump
1243 at its end and extracts the taken and not taken edges out of it
1244 and store it in E1 and E2 respectively. */
1246 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1248 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1249 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1252 /* Responsible for updating the ssa info (PHI nodes) on the
1253 new condition basic block that guards the versioned loop. */
1255 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1256 basic_block new_block
, edge e
)
1258 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1259 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1262 /* Conditions in trees and RTL are different so we need
1263 a different handling when we add the condition to the
1266 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1267 basic_block new_block
, void *cond
)
1269 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1270 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1273 /* Checks whether all N blocks in BBS array can be copied. */
1275 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1281 for (i
= 0; i
< n
; i
++)
1282 bbs
[i
]->flags
|= BB_DUPLICATED
;
1284 for (i
= 0; i
< n
; i
++)
1286 /* In case we should redirect abnormal edge during duplication, fail. */
1288 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1289 if ((e
->flags
& EDGE_ABNORMAL
)
1290 && (e
->dest
->flags
& BB_DUPLICATED
))
1296 if (!can_duplicate_block_p (bbs
[i
]))
1304 for (i
= 0; i
< n
; i
++)
1305 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1310 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1311 are placed into array NEW_BBS in the same order. Edges from basic blocks
1312 in BBS are also duplicated and copies of those that lead into BBS are
1313 redirected to appropriate newly created block. The function assigns bbs
1314 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1315 loop, so this must be set up correctly in advance)
1317 If UPDATE_DOMINANCE is true then this function updates dominators locally
1318 (LOOPS structure that contains the information about dominators is passed
1319 to enable this), otherwise it does not update the dominator information
1320 and it assumed that the caller will do this, perhaps by destroying and
1321 recreating it instead of trying to do an incremental update like this
1322 function does when update_dominance is true.
1324 BASE is the superloop to that basic block belongs; if its header or latch
1325 is copied, we do not set the new blocks as header or latch.
1327 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1328 also in the same order.
1330 Newly created basic blocks are put after the basic block AFTER in the
1331 instruction stream, and the order of the blocks in BBS array is preserved. */
1334 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1335 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1336 struct loop
*base
, basic_block after
, bool update_dominance
)
1339 basic_block bb
, new_bb
, dom_bb
;
1342 /* Duplicate bbs, update dominators, assign bbs to loops. */
1343 for (i
= 0; i
< n
; i
++)
1347 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1349 bb
->flags
|= BB_DUPLICATED
;
1350 if (bb
->loop_father
)
1352 /* Possibly set loop header. */
1353 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1354 new_bb
->loop_father
->header
= new_bb
;
1356 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1357 new_bb
->loop_father
->latch
= new_bb
;
1361 /* Set dominators. */
1362 if (update_dominance
)
1364 for (i
= 0; i
< n
; i
++)
1367 new_bb
= new_bbs
[i
];
1369 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1370 if (dom_bb
->flags
& BB_DUPLICATED
)
1372 dom_bb
= get_bb_copy (dom_bb
);
1373 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1378 /* Redirect edges. */
1379 for (j
= 0; j
< num_edges
; j
++)
1380 new_edges
[j
] = NULL
;
1381 for (i
= 0; i
< n
; i
++)
1384 new_bb
= new_bbs
[i
];
1387 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1389 for (j
= 0; j
< num_edges
; j
++)
1390 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1393 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1395 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1399 /* Clear information about duplicates. */
1400 for (i
= 0; i
< n
; i
++)
1401 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1404 /* Return true if BB contains only labels or non-executable
1407 empty_block_p (basic_block bb
)
1409 gcc_assert (cfg_hooks
->empty_block_p
);
1410 return cfg_hooks
->empty_block_p (bb
);
1413 /* Split a basic block if it ends with a conditional branch and if
1414 the other part of the block is not empty. */
1416 split_block_before_cond_jump (basic_block bb
)
1418 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1419 return cfg_hooks
->split_block_before_cond_jump (bb
);
1422 /* Work-horse for passes.c:check_profile_consistency.
1423 Do book-keeping of the CFG for the profile consistency checker.
1424 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1425 then do post-pass accounting. Store the counting in RECORD. */
1428 account_profile_record (struct profile_record
*record
, int after_pass
)
1436 FOR_ALL_BB_FN (bb
, cfun
)
1438 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1439 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1442 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1443 sum
+= e
->probability
;
1444 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1445 record
->num_mismatched_freq_out
[after_pass
]++;
1447 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1449 if (EDGE_COUNT (bb
->succs
)
1450 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1451 record
->num_mismatched_count_out
[after_pass
]++;
1453 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1454 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1457 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1458 sum
+= EDGE_FREQUENCY (e
);
1459 if (abs (sum
- bb
->frequency
) > 100
1460 || (MAX (sum
, bb
->frequency
) > 10
1461 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1462 record
->num_mismatched_freq_in
[after_pass
]++;
1464 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1466 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1467 record
->num_mismatched_count_in
[after_pass
]++;
1469 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1470 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1472 gcc_assert (cfg_hooks
->account_profile_record
);
1473 cfg_hooks
->account_profile_record (bb
, after_pass
, record
);