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"
38 #include "hard-reg-set.h"
41 #include "dominance.h"
44 #include "basic-block.h"
47 #include "diagnostic-core.h"
49 #include "pretty-print.h"
51 /* A pointer to one of the hooks containers. */
52 static struct cfg_hooks
*cfg_hooks
;
54 /* Initialization of functions specific to the rtl IR. */
56 rtl_register_cfg_hooks (void)
58 cfg_hooks
= &rtl_cfg_hooks
;
61 /* Initialization of functions specific to the rtl IR. */
63 cfg_layout_rtl_register_cfg_hooks (void)
65 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
68 /* Initialization of functions specific to the tree IR. */
71 gimple_register_cfg_hooks (void)
73 cfg_hooks
= &gimple_cfg_hooks
;
83 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
85 *cfg_hooks
= new_cfg_hooks
;
88 /* Returns current ir type. */
91 current_ir_type (void)
93 if (cfg_hooks
== &gimple_cfg_hooks
)
95 else if (cfg_hooks
== &rtl_cfg_hooks
)
97 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
98 return IR_RTL_CFGLAYOUT
;
103 /* Verify the CFG consistency.
105 Currently it does following: checks edge and basic block list correctness
106 and calls into IL dependent checking then. */
109 verify_flow_info (void)
111 size_t *edge_checksum
;
113 basic_block bb
, last_bb_seen
;
114 basic_block
*last_visited
;
116 timevar_push (TV_CFG_VERIFY
);
117 last_visited
= XCNEWVEC (basic_block
, last_basic_block_for_fn (cfun
));
118 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
120 /* Check bb chain & numbers. */
121 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
122 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
124 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
125 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, bb
->index
))
127 error ("bb %d on wrong place", bb
->index
);
131 if (bb
->prev_bb
!= last_bb_seen
)
133 error ("prev_bb of %d should be %d, not %d",
134 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
141 /* Now check the basic blocks (boundaries etc.) */
142 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
148 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
150 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
154 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
156 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
162 error ("verify_flow_info: Wrong count of block %i %i",
163 bb
->index
, (int)bb
->count
);
166 if (bb
->frequency
< 0)
168 error ("verify_flow_info: Wrong frequency of block %i %i",
169 bb
->index
, bb
->frequency
);
172 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
174 if (last_visited
[e
->dest
->index
] == bb
)
176 error ("verify_flow_info: Duplicate edge %i->%i",
177 e
->src
->index
, e
->dest
->index
);
180 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
182 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
183 e
->src
->index
, e
->dest
->index
, e
->probability
);
188 error ("verify_flow_info: Wrong count of edge %i->%i %i",
189 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
193 last_visited
[e
->dest
->index
] = bb
;
195 if (e
->flags
& EDGE_FALLTHRU
)
200 error ("verify_flow_info: Basic block %d succ edge is corrupted",
202 fprintf (stderr
, "Predecessor: ");
203 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
204 fprintf (stderr
, "\nSuccessor: ");
205 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
206 fprintf (stderr
, "\n");
210 edge_checksum
[e
->dest
->index
] += (size_t) e
;
214 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
218 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
222 error ("basic block %d pred edge is corrupted", bb
->index
);
223 fputs ("Predecessor: ", stderr
);
224 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
225 fputs ("\nSuccessor: ", stderr
);
226 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
227 fputc ('\n', stderr
);
231 if (ei
.index
!= e
->dest_idx
)
233 error ("basic block %d pred edge is corrupted", bb
->index
);
234 error ("its dest_idx should be %d, not %d",
235 ei
.index
, e
->dest_idx
);
236 fputs ("Predecessor: ", stderr
);
237 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
238 fputs ("\nSuccessor: ", stderr
);
239 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
240 fputc ('\n', stderr
);
244 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
248 /* Complete edge checksumming for ENTRY and EXIT. */
253 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
254 edge_checksum
[e
->dest
->index
] += (size_t) e
;
256 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
257 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
260 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
261 if (edge_checksum
[bb
->index
])
263 error ("basic block %i edge lists are corrupted", bb
->index
);
267 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
271 free (edge_checksum
);
273 if (cfg_hooks
->verify_flow_info
)
274 err
|= cfg_hooks
->verify_flow_info ();
276 internal_error ("verify_flow_info failed");
277 timevar_pop (TV_CFG_VERIFY
);
280 /* Print out one basic block BB to file OUTF. INDENT is printed at the
281 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
283 This function takes care of the purely graph related information.
284 The cfg hook for the active representation should dump
285 representation-specific information. */
288 dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
290 if (flags
& TDF_BLOCKS
)
291 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
292 if (cfg_hooks
->dump_bb
)
293 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
294 if (flags
& TDF_BLOCKS
)
295 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
300 debug (basic_block_def
&ref
)
302 dump_bb (stderr
, &ref
, 0, 0);
306 debug (basic_block_def
*ptr
)
311 fprintf (stderr
, "<nil>\n");
315 /* Dumps basic block BB to pretty-printer PP, for use as a label of
316 a DOT graph record-node. The implementation of this hook is
317 expected to write the label to the stream that is attached to PP.
318 Field separators between instructions are pipe characters printed
319 verbatim. Instructions should be written with some characters
320 escaped, using pp_write_text_as_dot_label_to_stream(). */
323 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
325 if (!cfg_hooks
->dump_bb_for_graph
)
326 internal_error ("%s does not support dump_bb_for_graph",
329 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
);
330 pp_printf (pp
, " FREQ:%i |", bb
->frequency
);
331 pp_write_text_to_stream (pp
);
332 if (!(dump_flags
& TDF_SLIM
))
333 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
336 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
338 dump_flow_info (FILE *file
, int flags
)
342 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
343 n_edges_for_fn (cfun
));
344 FOR_ALL_BB_FN (bb
, cfun
)
345 dump_bb (file
, bb
, 0, flags
);
350 /* Like above, but dump to stderr. To be called from debuggers. */
351 void debug_flow_info (void);
353 debug_flow_info (void)
355 dump_flow_info (stderr
, TDF_DETAILS
);
358 /* Redirect edge E to the given basic block DEST and update underlying program
359 representation. Returns edge representing redirected branch (that may not
360 be equivalent to E in the case of duplicate edges being removed) or NULL
361 if edge is not easily redirectable for whatever reason. */
364 redirect_edge_and_branch (edge e
, basic_block dest
)
368 if (!cfg_hooks
->redirect_edge_and_branch
)
369 internal_error ("%s does not support redirect_edge_and_branch",
372 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
374 /* If RET != E, then either the redirection failed, or the edge E
375 was removed since RET already lead to the same destination. */
376 if (current_loops
!= NULL
&& ret
== e
)
377 rescan_loop_exit (e
, false, false);
382 /* Returns true if it is possible to remove the edge E by redirecting it
383 to the destination of the other edge going from its source. */
386 can_remove_branch_p (const_edge e
)
388 if (!cfg_hooks
->can_remove_branch_p
)
389 internal_error ("%s does not support can_remove_branch_p",
392 if (EDGE_COUNT (e
->src
->succs
) != 2)
395 return cfg_hooks
->can_remove_branch_p (e
);
398 /* Removes E, by redirecting it to the destination of the other edge going
399 from its source. Can_remove_branch_p must be true for E, hence this
400 operation cannot fail. */
403 remove_branch (edge e
)
406 basic_block src
= e
->src
;
409 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
411 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
412 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
414 e
= redirect_edge_and_branch (e
, other
->dest
);
415 gcc_assert (e
!= NULL
);
417 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
421 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
426 if (current_loops
!= NULL
)
427 rescan_loop_exit (e
, false, true);
429 /* This is probably not needed, but it doesn't hurt. */
430 /* FIXME: This should be called via a remove_edge hook. */
431 if (current_ir_type () == IR_GIMPLE
)
432 redirect_edge_var_map_clear (e
);
437 /* Like redirect_edge_succ but avoid possible duplicate edge. */
440 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
444 s
= find_edge (e
->src
, new_succ
);
447 s
->flags
|= e
->flags
;
448 s
->probability
+= e
->probability
;
449 if (s
->probability
> REG_BR_PROB_BASE
)
450 s
->probability
= REG_BR_PROB_BASE
;
451 s
->count
+= e
->count
;
452 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
453 redirect_edge_var_map_dup (s
, e
);
458 redirect_edge_succ (e
, new_succ
);
463 /* Redirect the edge E to basic block DEST even if it requires creating
464 of a new basic block; then it returns the newly created basic block.
465 Aborts when redirection is impossible. */
468 redirect_edge_and_branch_force (edge e
, basic_block dest
)
470 basic_block ret
, src
= e
->src
;
472 if (!cfg_hooks
->redirect_edge_and_branch_force
)
473 internal_error ("%s does not support redirect_edge_and_branch_force",
476 if (current_loops
!= NULL
)
477 rescan_loop_exit (e
, false, true);
479 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
481 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
482 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
484 if (current_loops
!= NULL
)
489 = find_common_loop (single_pred (ret
)->loop_father
,
490 single_succ (ret
)->loop_father
);
491 add_bb_to_loop (ret
, loop
);
493 else if (find_edge (src
, dest
) == e
)
494 rescan_loop_exit (e
, true, false);
500 /* Splits basic block BB after the specified instruction I (but at least after
501 the labels). If I is NULL, splits just after labels. The newly created edge
502 is returned. The new basic block is created just after the old one. */
505 split_block_1 (basic_block bb
, void *i
)
510 if (!cfg_hooks
->split_block
)
511 internal_error ("%s does not support split_block", cfg_hooks
->name
);
513 new_bb
= cfg_hooks
->split_block (bb
, i
);
517 new_bb
->count
= bb
->count
;
518 new_bb
->frequency
= bb
->frequency
;
519 new_bb
->discriminator
= bb
->discriminator
;
521 if (dom_info_available_p (CDI_DOMINATORS
))
523 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
524 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
527 if (current_loops
!= NULL
)
531 add_bb_to_loop (new_bb
, bb
->loop_father
);
532 /* Identify all loops bb may have been the latch of and adjust them. */
533 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
534 if (e
->dest
->loop_father
->latch
== bb
)
535 e
->dest
->loop_father
->latch
= new_bb
;
538 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
540 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
542 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
543 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
550 split_block (basic_block bb
, gimple i
)
552 return split_block_1 (bb
, i
);
556 split_block (basic_block bb
, rtx i
)
558 return split_block_1 (bb
, i
);
561 /* Splits block BB just after labels. The newly created edge is returned. */
564 split_block_after_labels (basic_block bb
)
566 return split_block_1 (bb
, NULL
);
569 /* Moves block BB immediately after block AFTER. Returns false if the
570 movement was impossible. */
573 move_block_after (basic_block bb
, basic_block after
)
577 if (!cfg_hooks
->move_block_after
)
578 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
580 ret
= cfg_hooks
->move_block_after (bb
, after
);
585 /* Deletes the basic block BB. */
588 delete_basic_block (basic_block bb
)
590 if (!cfg_hooks
->delete_basic_block
)
591 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
593 cfg_hooks
->delete_basic_block (bb
);
595 if (current_loops
!= NULL
)
597 struct loop
*loop
= bb
->loop_father
;
599 /* If we remove the header or the latch of a loop, mark the loop for
601 if (loop
->latch
== bb
602 || loop
->header
== bb
)
603 mark_loop_for_removal (loop
);
605 remove_bb_from_loops (bb
);
608 /* Remove the edges into and out of this block. Note that there may
609 indeed be edges in, if we are removing an unreachable loop. */
610 while (EDGE_COUNT (bb
->preds
) != 0)
611 remove_edge (EDGE_PRED (bb
, 0));
612 while (EDGE_COUNT (bb
->succs
) != 0)
613 remove_edge (EDGE_SUCC (bb
, 0));
615 if (dom_info_available_p (CDI_DOMINATORS
))
616 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
617 if (dom_info_available_p (CDI_POST_DOMINATORS
))
618 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
620 /* Remove the basic block from the array. */
624 /* Splits edge E and returns the newly created basic block. */
630 gcov_type count
= e
->count
;
631 int freq
= EDGE_FREQUENCY (e
);
633 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
635 basic_block src
= e
->src
, dest
= e
->dest
;
637 if (!cfg_hooks
->split_edge
)
638 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
640 if (current_loops
!= NULL
)
641 rescan_loop_exit (e
, false, true);
643 ret
= cfg_hooks
->split_edge (e
);
645 ret
->frequency
= freq
;
646 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
647 single_succ_edge (ret
)->count
= count
;
651 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
652 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
653 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
656 if (dom_info_available_p (CDI_DOMINATORS
))
657 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
659 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
661 /* There are two cases:
663 If the immediate dominator of e->dest is not e->src, it
666 If immediate dominator of e->dest is e->src, it may become
667 ret, provided that all other predecessors of e->dest are
668 dominated by e->dest. */
670 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
671 == single_pred (ret
))
674 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
676 if (f
== single_succ_edge (ret
))
679 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
685 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
689 if (current_loops
!= NULL
)
691 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
692 add_bb_to_loop (ret
, loop
);
694 /* If we split the latch edge of loop adjust the latch block. */
695 if (loop
->latch
== src
696 && loop
->header
== dest
)
703 /* Creates a new basic block just after the basic block AFTER.
704 HEAD and END are the first and the last statement belonging
705 to the block. If both are NULL, an empty block is created. */
708 create_basic_block_1 (void *head
, void *end
, basic_block after
)
712 if (!cfg_hooks
->create_basic_block
)
713 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
715 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
717 if (dom_info_available_p (CDI_DOMINATORS
))
718 add_to_dominance_info (CDI_DOMINATORS
, ret
);
719 if (dom_info_available_p (CDI_POST_DOMINATORS
))
720 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
726 create_basic_block (gimple_seq seq
, basic_block after
)
728 return create_basic_block_1 (seq
, NULL
, after
);
732 create_basic_block (rtx head
, rtx end
, basic_block after
)
734 return create_basic_block_1 (head
, end
, after
);
738 /* Creates an empty basic block just after basic block AFTER. */
741 create_empty_bb (basic_block after
)
743 return create_basic_block_1 (NULL
, NULL
, after
);
746 /* Checks whether we may merge blocks BB1 and BB2. */
749 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
753 if (!cfg_hooks
->can_merge_blocks_p
)
754 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
756 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
762 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
764 if (!cfg_hooks
->predict_edge
)
765 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
767 cfg_hooks
->predict_edge (e
, predictor
, probability
);
771 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
773 if (!cfg_hooks
->predict_edge
)
774 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
776 return cfg_hooks
->predicted_by_p (bb
, predictor
);
779 /* Merges basic block B into basic block A. */
782 merge_blocks (basic_block a
, basic_block b
)
787 if (!cfg_hooks
->merge_blocks
)
788 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
790 cfg_hooks
->merge_blocks (a
, b
);
792 if (current_loops
!= NULL
)
794 /* If the block we merge into is a loop header do nothing unless ... */
795 if (a
->loop_father
->header
== a
)
797 /* ... we merge two loop headers, in which case we kill
799 if (b
->loop_father
->header
== b
)
800 mark_loop_for_removal (b
->loop_father
);
802 /* If we merge a loop header into its predecessor, update the loop
804 else if (b
->loop_father
->header
== b
)
806 remove_bb_from_loops (a
);
807 add_bb_to_loop (a
, b
->loop_father
);
808 a
->loop_father
->header
= a
;
810 /* If we merge a loop latch into its predecessor, update the loop
812 if (b
->loop_father
->latch
813 && b
->loop_father
->latch
== b
)
814 b
->loop_father
->latch
= a
;
815 remove_bb_from_loops (b
);
818 /* Normally there should only be one successor of A and that is B, but
819 partway though the merge of blocks for conditional_execution we'll
820 be merging a TEST block with THEN and ELSE successors. Free the
821 whole lot of them and hope the caller knows what they're doing. */
823 while (EDGE_COUNT (a
->succs
) != 0)
824 remove_edge (EDGE_SUCC (a
, 0));
826 /* Adjust the edges out of B for the new owner. */
827 FOR_EACH_EDGE (e
, ei
, b
->succs
)
830 if (current_loops
!= NULL
)
832 /* If b was a latch, a now is. */
833 if (e
->dest
->loop_father
->latch
== b
)
834 e
->dest
->loop_father
->latch
= a
;
835 rescan_loop_exit (e
, true, false);
839 a
->flags
|= b
->flags
;
841 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
842 b
->preds
= b
->succs
= NULL
;
844 if (dom_info_available_p (CDI_DOMINATORS
))
845 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
847 if (dom_info_available_p (CDI_DOMINATORS
))
848 delete_from_dominance_info (CDI_DOMINATORS
, b
);
849 if (dom_info_available_p (CDI_POST_DOMINATORS
))
850 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
855 /* Split BB into entry part and the rest (the rest is the newly created block).
856 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
857 part. Returns the edge connecting the entry part to the rest. */
860 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
861 void (*new_bb_cbk
) (basic_block
))
865 basic_block dummy
, jump
;
866 struct loop
*loop
, *ploop
, *cloop
;
868 if (!cfg_hooks
->make_forwarder_block
)
869 internal_error ("%s does not support make_forwarder_block",
872 fallthru
= split_block_after_labels (bb
);
873 dummy
= fallthru
->src
;
875 dummy
->frequency
= 0;
879 /* Redirect back edges we want to keep. */
880 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
884 if (redirect_edge_p (e
))
886 dummy
->frequency
+= EDGE_FREQUENCY (e
);
887 if (dummy
->frequency
> BB_FREQ_MAX
)
888 dummy
->frequency
= BB_FREQ_MAX
;
890 dummy
->count
+= e
->count
;
891 fallthru
->count
+= e
->count
;
897 jump
= redirect_edge_and_branch_force (e
, bb
);
900 /* If we redirected the loop latch edge, the JUMP block now acts like
901 the new latch of the loop. */
902 if (current_loops
!= NULL
903 && dummy
->loop_father
!= NULL
904 && dummy
->loop_father
->header
== dummy
905 && dummy
->loop_father
->latch
== e_src
)
906 dummy
->loop_father
->latch
= jump
;
908 if (new_bb_cbk
!= NULL
)
913 if (dom_info_available_p (CDI_DOMINATORS
))
915 vec
<basic_block
> doms_to_fix
;
916 doms_to_fix
.create (2);
917 doms_to_fix
.quick_push (dummy
);
918 doms_to_fix
.quick_push (bb
);
919 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
920 doms_to_fix
.release ();
923 if (current_loops
!= NULL
)
925 /* If we do not split a loop header, then both blocks belong to the
926 same loop. In case we split loop header and do not redirect the
927 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
928 BB becomes the new header. If latch is not recorded for the loop,
929 we leave this updating on the caller (this may only happen during
931 loop
= dummy
->loop_father
;
932 if (loop
->header
== dummy
933 && loop
->latch
!= NULL
934 && find_edge (loop
->latch
, dummy
) == NULL
)
936 remove_bb_from_loops (dummy
);
940 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
942 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
944 add_bb_to_loop (dummy
, cloop
);
947 /* In case we split loop latch, update it. */
948 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
949 if (ploop
->latch
== dummy
)
953 cfg_hooks
->make_forwarder_block (fallthru
);
958 /* Try to make the edge fallthru. */
961 tidy_fallthru_edge (edge e
)
963 if (cfg_hooks
->tidy_fallthru_edge
)
964 cfg_hooks
->tidy_fallthru_edge (e
);
967 /* Fix up edges that now fall through, or rather should now fall through
968 but previously required a jump around now deleted blocks. Simplify
969 the search by only examining blocks numerically adjacent, since this
970 is how they were created.
972 ??? This routine is currently RTL specific. */
975 tidy_fallthru_edges (void)
979 if (!cfg_hooks
->tidy_fallthru_edge
)
982 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
985 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
986 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
992 /* We care about simple conditional or unconditional jumps with
995 If we had a conditional branch to the next instruction when
996 CFG was built, then there will only be one out edge for the
997 block which ended with the conditional branch (since we do
998 not create duplicate edges).
1000 Furthermore, the edge will be marked as a fallthru because we
1001 merge the flags for the duplicate edges. So we do not want to
1002 check that the edge is not a FALLTHRU edge. */
1004 if (single_succ_p (b
))
1006 s
= single_succ_edge (b
);
1007 if (! (s
->flags
& EDGE_COMPLEX
)
1009 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1010 tidy_fallthru_edge (s
);
1015 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1016 (and possibly create new basic block) to make edge non-fallthru.
1017 Return newly created BB or NULL if none. */
1020 force_nonfallthru (edge e
)
1022 basic_block ret
, src
= e
->src
;
1024 if (!cfg_hooks
->force_nonfallthru
)
1025 internal_error ("%s does not support force_nonfallthru",
1028 ret
= cfg_hooks
->force_nonfallthru (e
);
1031 if (dom_info_available_p (CDI_DOMINATORS
))
1032 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1034 if (current_loops
!= NULL
)
1037 = find_common_loop (single_pred (ret
)->loop_father
,
1038 single_succ (ret
)->loop_father
);
1039 rescan_loop_exit (e
, false, true);
1040 add_bb_to_loop (ret
, loop
);
1047 /* Returns true if we can duplicate basic block BB. */
1050 can_duplicate_block_p (const_basic_block bb
)
1052 if (!cfg_hooks
->can_duplicate_block_p
)
1053 internal_error ("%s does not support can_duplicate_block_p",
1056 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1059 return cfg_hooks
->can_duplicate_block_p (bb
);
1062 /* Duplicates basic block BB and redirects edge E to it. Returns the
1063 new basic block. The new basic block is placed after the basic block
1067 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1071 gcov_type new_count
= e
? e
->count
: 0;
1074 if (!cfg_hooks
->duplicate_block
)
1075 internal_error ("%s does not support duplicate_block",
1078 if (bb
->count
< new_count
)
1079 new_count
= bb
->count
;
1081 gcc_checking_assert (can_duplicate_block_p (bb
));
1083 new_bb
= cfg_hooks
->duplicate_block (bb
);
1085 move_block_after (new_bb
, after
);
1087 new_bb
->flags
= bb
->flags
;
1088 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1090 /* Since we are creating edges from a new block to successors
1091 of another block (which therefore are known to be disjoint), there
1092 is no need to actually check for duplicated edges. */
1093 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1094 n
->probability
= s
->probability
;
1097 /* Take care for overflows! */
1098 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1099 s
->count
-= n
->count
;
1102 n
->count
= s
->count
;
1108 new_bb
->count
= new_count
;
1109 bb
->count
-= new_count
;
1111 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1112 bb
->frequency
-= EDGE_FREQUENCY (e
);
1114 redirect_edge_and_branch_force (e
, new_bb
);
1118 if (bb
->frequency
< 0)
1123 new_bb
->count
= bb
->count
;
1124 new_bb
->frequency
= bb
->frequency
;
1127 set_bb_original (new_bb
, bb
);
1128 set_bb_copy (bb
, new_bb
);
1130 /* Add the new block to the copy of the loop of BB, or directly to the loop
1131 of BB if the loop is not being copied. */
1132 if (current_loops
!= NULL
)
1134 struct loop
*cloop
= bb
->loop_father
;
1135 struct loop
*copy
= get_loop_copy (cloop
);
1136 /* If we copied the loop header block but not the loop
1137 we have created a loop with multiple entries. Ditch the loop,
1138 add the new block to the outer loop and arrange for a fixup. */
1140 && cloop
->header
== bb
)
1142 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1143 mark_loop_for_removal (cloop
);
1147 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1148 /* If we copied the loop latch block but not the loop, adjust
1151 && cloop
->latch
== bb
)
1153 cloop
->latch
= NULL
;
1154 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1162 /* Return 1 if BB ends with a call, possibly followed by some
1163 instructions that must stay with the call, 0 otherwise. */
1166 block_ends_with_call_p (basic_block bb
)
1168 if (!cfg_hooks
->block_ends_with_call_p
)
1169 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1171 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1174 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1177 block_ends_with_condjump_p (const_basic_block bb
)
1179 if (!cfg_hooks
->block_ends_with_condjump_p
)
1180 internal_error ("%s does not support block_ends_with_condjump_p",
1183 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1186 /* Add fake edges to the function exit for any non constant and non noreturn
1187 calls, volatile inline assembly in the bitmap of blocks specified by
1188 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1191 The goal is to expose cases in which entering a basic block does not imply
1192 that all subsequent instructions must be executed. */
1195 flow_call_edges_add (sbitmap blocks
)
1197 if (!cfg_hooks
->flow_call_edges_add
)
1198 internal_error ("%s does not support flow_call_edges_add",
1201 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1204 /* This function is called immediately after edge E is added to the
1205 edge vector E->dest->preds. */
1208 execute_on_growing_pred (edge e
)
1210 if (cfg_hooks
->execute_on_growing_pred
)
1211 cfg_hooks
->execute_on_growing_pred (e
);
1214 /* This function is called immediately before edge E is removed from
1215 the edge vector E->dest->preds. */
1218 execute_on_shrinking_pred (edge e
)
1220 if (cfg_hooks
->execute_on_shrinking_pred
)
1221 cfg_hooks
->execute_on_shrinking_pred (e
);
1224 /* This is used inside loop versioning when we want to insert
1225 stmts/insns on the edges, which have a different behavior
1226 in tree's and in RTL, so we made a CFG hook. */
1228 lv_flush_pending_stmts (edge e
)
1230 if (cfg_hooks
->flush_pending_stmts
)
1231 cfg_hooks
->flush_pending_stmts (e
);
1234 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1235 a new version of the loop basic-blocks, the parameters here are
1236 exactly the same as in duplicate_loop_to_header_edge or
1237 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1238 additional work to maintain ssa information that's why there is
1239 a need to call the tree_duplicate_loop_to_header_edge rather
1240 than duplicate_loop_to_header_edge when we are in tree mode. */
1242 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1244 sbitmap wont_exit
, edge orig
,
1245 vec
<edge
> *to_remove
,
1248 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1249 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1255 /* Conditional jumps are represented differently in trees and RTL,
1256 this hook takes a basic block that is known to have a cond jump
1257 at its end and extracts the taken and not taken edges out of it
1258 and store it in E1 and E2 respectively. */
1260 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1262 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1263 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1266 /* Responsible for updating the ssa info (PHI nodes) on the
1267 new condition basic block that guards the versioned loop. */
1269 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1270 basic_block new_block
, edge e
)
1272 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1273 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1276 /* Conditions in trees and RTL are different so we need
1277 a different handling when we add the condition to the
1280 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1281 basic_block new_block
, void *cond
)
1283 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1284 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1287 /* Checks whether all N blocks in BBS array can be copied. */
1289 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1295 for (i
= 0; i
< n
; i
++)
1296 bbs
[i
]->flags
|= BB_DUPLICATED
;
1298 for (i
= 0; i
< n
; i
++)
1300 /* In case we should redirect abnormal edge during duplication, fail. */
1302 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1303 if ((e
->flags
& EDGE_ABNORMAL
)
1304 && (e
->dest
->flags
& BB_DUPLICATED
))
1310 if (!can_duplicate_block_p (bbs
[i
]))
1318 for (i
= 0; i
< n
; i
++)
1319 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1324 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1325 are placed into array NEW_BBS in the same order. Edges from basic blocks
1326 in BBS are also duplicated and copies of those that lead into BBS are
1327 redirected to appropriate newly created block. The function assigns bbs
1328 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1329 loop, so this must be set up correctly in advance)
1331 If UPDATE_DOMINANCE is true then this function updates dominators locally
1332 (LOOPS structure that contains the information about dominators is passed
1333 to enable this), otherwise it does not update the dominator information
1334 and it assumed that the caller will do this, perhaps by destroying and
1335 recreating it instead of trying to do an incremental update like this
1336 function does when update_dominance is true.
1338 BASE is the superloop to that basic block belongs; if its header or latch
1339 is copied, we do not set the new blocks as header or latch.
1341 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1342 also in the same order.
1344 Newly created basic blocks are put after the basic block AFTER in the
1345 instruction stream, and the order of the blocks in BBS array is preserved. */
1348 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1349 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1350 struct loop
*base
, basic_block after
, bool update_dominance
)
1353 basic_block bb
, new_bb
, dom_bb
;
1356 /* Duplicate bbs, update dominators, assign bbs to loops. */
1357 for (i
= 0; i
< n
; i
++)
1361 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1363 bb
->flags
|= BB_DUPLICATED
;
1364 if (bb
->loop_father
)
1366 /* Possibly set loop header. */
1367 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1368 new_bb
->loop_father
->header
= new_bb
;
1370 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1371 new_bb
->loop_father
->latch
= new_bb
;
1375 /* Set dominators. */
1376 if (update_dominance
)
1378 for (i
= 0; i
< n
; i
++)
1381 new_bb
= new_bbs
[i
];
1383 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1384 if (dom_bb
->flags
& BB_DUPLICATED
)
1386 dom_bb
= get_bb_copy (dom_bb
);
1387 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1392 /* Redirect edges. */
1393 for (j
= 0; j
< num_edges
; j
++)
1394 new_edges
[j
] = NULL
;
1395 for (i
= 0; i
< n
; i
++)
1398 new_bb
= new_bbs
[i
];
1401 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1403 for (j
= 0; j
< num_edges
; j
++)
1404 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1407 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1409 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1413 /* Clear information about duplicates. */
1414 for (i
= 0; i
< n
; i
++)
1415 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1418 /* Return true if BB contains only labels or non-executable
1421 empty_block_p (basic_block bb
)
1423 gcc_assert (cfg_hooks
->empty_block_p
);
1424 return cfg_hooks
->empty_block_p (bb
);
1427 /* Split a basic block if it ends with a conditional branch and if
1428 the other part of the block is not empty. */
1430 split_block_before_cond_jump (basic_block bb
)
1432 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1433 return cfg_hooks
->split_block_before_cond_jump (bb
);
1436 /* Work-horse for passes.c:check_profile_consistency.
1437 Do book-keeping of the CFG for the profile consistency checker.
1438 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1439 then do post-pass accounting. Store the counting in RECORD. */
1442 account_profile_record (struct profile_record
*record
, int after_pass
)
1450 FOR_ALL_BB_FN (bb
, cfun
)
1452 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1453 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1456 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1457 sum
+= e
->probability
;
1458 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1459 record
->num_mismatched_freq_out
[after_pass
]++;
1461 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1463 if (EDGE_COUNT (bb
->succs
)
1464 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1465 record
->num_mismatched_count_out
[after_pass
]++;
1467 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1468 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1471 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1472 sum
+= EDGE_FREQUENCY (e
);
1473 if (abs (sum
- bb
->frequency
) > 100
1474 || (MAX (sum
, bb
->frequency
) > 10
1475 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1476 record
->num_mismatched_freq_in
[after_pass
]++;
1478 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1480 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1481 record
->num_mismatched_count_in
[after_pass
]++;
1483 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1484 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1486 gcc_assert (cfg_hooks
->account_profile_record
);
1487 cfg_hooks
->account_profile_record (bb
, after_pass
, record
);