1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
31 #include "diagnostic-core.h"
33 #include "pretty-print.h"
35 /* A pointer to one of the hooks containers. */
36 static struct cfg_hooks
*cfg_hooks
;
38 /* Initialization of functions specific to the rtl IR. */
40 rtl_register_cfg_hooks (void)
42 cfg_hooks
= &rtl_cfg_hooks
;
45 /* Initialization of functions specific to the rtl IR. */
47 cfg_layout_rtl_register_cfg_hooks (void)
49 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
52 /* Initialization of functions specific to the tree IR. */
55 gimple_register_cfg_hooks (void)
57 cfg_hooks
= &gimple_cfg_hooks
;
67 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
69 *cfg_hooks
= new_cfg_hooks
;
72 /* Returns current ir type. */
75 current_ir_type (void)
77 if (cfg_hooks
== &gimple_cfg_hooks
)
79 else if (cfg_hooks
== &rtl_cfg_hooks
)
81 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
82 return IR_RTL_CFGLAYOUT
;
87 /* Verify the CFG consistency.
89 Currently it does following: checks edge and basic block list correctness
90 and calls into IL dependent checking then. */
93 verify_flow_info (void)
95 size_t *edge_checksum
;
97 basic_block bb
, last_bb_seen
;
98 basic_block
*last_visited
;
100 timevar_push (TV_CFG_VERIFY
);
101 last_visited
= XCNEWVEC (basic_block
, last_basic_block
);
102 edge_checksum
= XCNEWVEC (size_t, last_basic_block
);
104 /* Check bb chain & numbers. */
105 last_bb_seen
= ENTRY_BLOCK_PTR
;
106 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
108 if (bb
!= EXIT_BLOCK_PTR
109 && bb
!= BASIC_BLOCK (bb
->index
))
111 error ("bb %d on wrong place", bb
->index
);
115 if (bb
->prev_bb
!= last_bb_seen
)
117 error ("prev_bb of %d should be %d, not %d",
118 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
125 /* Now check the basic blocks (boundaries etc.) */
126 FOR_EACH_BB_REVERSE (bb
)
132 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
134 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
138 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
140 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
146 error ("verify_flow_info: Wrong count of block %i %i",
147 bb
->index
, (int)bb
->count
);
150 if (bb
->frequency
< 0)
152 error ("verify_flow_info: Wrong frequency of block %i %i",
153 bb
->index
, bb
->frequency
);
156 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
158 if (last_visited
[e
->dest
->index
] == bb
)
160 error ("verify_flow_info: Duplicate edge %i->%i",
161 e
->src
->index
, e
->dest
->index
);
164 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
166 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
167 e
->src
->index
, e
->dest
->index
, e
->probability
);
172 error ("verify_flow_info: Wrong count of edge %i->%i %i",
173 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
177 last_visited
[e
->dest
->index
] = bb
;
179 if (e
->flags
& EDGE_FALLTHRU
)
184 error ("verify_flow_info: Basic block %d succ edge is corrupted",
186 fprintf (stderr
, "Predecessor: ");
187 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
188 fprintf (stderr
, "\nSuccessor: ");
189 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
190 fprintf (stderr
, "\n");
194 edge_checksum
[e
->dest
->index
] += (size_t) e
;
198 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
202 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
206 error ("basic block %d pred edge is corrupted", bb
->index
);
207 fputs ("Predecessor: ", stderr
);
208 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
209 fputs ("\nSuccessor: ", stderr
);
210 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
211 fputc ('\n', stderr
);
215 if (ei
.index
!= e
->dest_idx
)
217 error ("basic block %d pred edge is corrupted", bb
->index
);
218 error ("its dest_idx should be %d, not %d",
219 ei
.index
, e
->dest_idx
);
220 fputs ("Predecessor: ", stderr
);
221 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
222 fputs ("\nSuccessor: ", stderr
);
223 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
224 fputc ('\n', stderr
);
228 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
232 /* Complete edge checksumming for ENTRY and EXIT. */
237 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
238 edge_checksum
[e
->dest
->index
] += (size_t) e
;
240 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
241 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
244 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
245 if (edge_checksum
[bb
->index
])
247 error ("basic block %i edge lists are corrupted", bb
->index
);
251 last_bb_seen
= ENTRY_BLOCK_PTR
;
255 free (edge_checksum
);
257 if (cfg_hooks
->verify_flow_info
)
258 err
|= cfg_hooks
->verify_flow_info ();
260 internal_error ("verify_flow_info failed");
261 timevar_pop (TV_CFG_VERIFY
);
264 /* Print out one basic block BB to file OUTF. INDENT is printed at the
265 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
267 This function takes care of the purely graph related information.
268 The cfg hook for the active representation should dump
269 representation-specific information. */
272 dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
274 if (flags
& TDF_BLOCKS
)
275 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
276 if (cfg_hooks
->dump_bb
)
277 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
278 if (flags
& TDF_BLOCKS
)
279 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
284 debug (basic_block_def
&ref
)
286 dump_bb (stderr
, &ref
, 0, 0);
290 debug (basic_block_def
*ptr
)
295 fprintf (stderr
, "<nil>\n");
299 /* Dumps basic block BB to pretty-printer PP, for use as a label of
300 a DOT graph record-node. The implementation of this hook is
301 expected to write the label to the stream that is attached to PP.
302 Field separators between instructions are pipe characters printed
303 verbatim. Instructions should be written with some characters
304 escaped, using pp_write_text_as_dot_label_to_stream(). */
307 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
309 if (!cfg_hooks
->dump_bb_for_graph
)
310 internal_error ("%s does not support dump_bb_for_graph",
313 pp_printf (pp
, "COUNT:" HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
314 pp_printf (pp
, " FREQ:%i |", bb
->frequency
);
315 pp_write_text_to_stream (pp
);
316 if (!(dump_flags
& TDF_SLIM
))
317 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
320 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
322 dump_flow_info (FILE *file
, int flags
)
326 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
329 dump_bb (file
, bb
, 0, flags
);
334 /* Like above, but dump to stderr. To be called from debuggers. */
335 void debug_flow_info (void);
337 debug_flow_info (void)
339 dump_flow_info (stderr
, TDF_DETAILS
);
342 /* Redirect edge E to the given basic block DEST and update underlying program
343 representation. Returns edge representing redirected branch (that may not
344 be equivalent to E in the case of duplicate edges being removed) or NULL
345 if edge is not easily redirectable for whatever reason. */
348 redirect_edge_and_branch (edge e
, basic_block dest
)
352 if (!cfg_hooks
->redirect_edge_and_branch
)
353 internal_error ("%s does not support redirect_edge_and_branch",
356 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
358 /* If RET != E, then either the redirection failed, or the edge E
359 was removed since RET already lead to the same destination. */
360 if (current_loops
!= NULL
&& ret
== e
)
361 rescan_loop_exit (e
, false, false);
366 /* Returns true if it is possible to remove the edge E by redirecting it
367 to the destination of the other edge going from its source. */
370 can_remove_branch_p (const_edge e
)
372 if (!cfg_hooks
->can_remove_branch_p
)
373 internal_error ("%s does not support can_remove_branch_p",
376 if (EDGE_COUNT (e
->src
->succs
) != 2)
379 return cfg_hooks
->can_remove_branch_p (e
);
382 /* Removes E, by redirecting it to the destination of the other edge going
383 from its source. Can_remove_branch_p must be true for E, hence this
384 operation cannot fail. */
387 remove_branch (edge e
)
390 basic_block src
= e
->src
;
393 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
395 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
396 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
398 e
= redirect_edge_and_branch (e
, other
->dest
);
399 gcc_assert (e
!= NULL
);
401 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
405 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
410 if (current_loops
!= NULL
)
411 rescan_loop_exit (e
, false, true);
413 /* This is probably not needed, but it doesn't hurt. */
414 /* FIXME: This should be called via a remove_edge hook. */
415 if (current_ir_type () == IR_GIMPLE
)
416 redirect_edge_var_map_clear (e
);
421 /* Like redirect_edge_succ but avoid possible duplicate edge. */
424 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
428 s
= find_edge (e
->src
, new_succ
);
431 s
->flags
|= e
->flags
;
432 s
->probability
+= e
->probability
;
433 if (s
->probability
> REG_BR_PROB_BASE
)
434 s
->probability
= REG_BR_PROB_BASE
;
435 s
->count
+= e
->count
;
436 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
437 redirect_edge_var_map_dup (s
, e
);
442 redirect_edge_succ (e
, new_succ
);
447 /* Redirect the edge E to basic block DEST even if it requires creating
448 of a new basic block; then it returns the newly created basic block.
449 Aborts when redirection is impossible. */
452 redirect_edge_and_branch_force (edge e
, basic_block dest
)
454 basic_block ret
, src
= e
->src
;
456 if (!cfg_hooks
->redirect_edge_and_branch_force
)
457 internal_error ("%s does not support redirect_edge_and_branch_force",
460 if (current_loops
!= NULL
)
461 rescan_loop_exit (e
, false, true);
463 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
465 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
466 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
468 if (current_loops
!= NULL
)
473 = find_common_loop (single_pred (ret
)->loop_father
,
474 single_succ (ret
)->loop_father
);
475 add_bb_to_loop (ret
, loop
);
477 else if (find_edge (src
, dest
) == e
)
478 rescan_loop_exit (e
, true, false);
484 /* Splits basic block BB after the specified instruction I (but at least after
485 the labels). If I is NULL, splits just after labels. The newly created edge
486 is returned. The new basic block is created just after the old one. */
489 split_block (basic_block bb
, void *i
)
494 if (!cfg_hooks
->split_block
)
495 internal_error ("%s does not support split_block", cfg_hooks
->name
);
497 new_bb
= cfg_hooks
->split_block (bb
, i
);
501 new_bb
->count
= bb
->count
;
502 new_bb
->frequency
= bb
->frequency
;
503 new_bb
->discriminator
= bb
->discriminator
;
505 if (dom_info_available_p (CDI_DOMINATORS
))
507 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
508 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
511 if (current_loops
!= NULL
)
513 add_bb_to_loop (new_bb
, bb
->loop_father
);
514 if (bb
->loop_father
->latch
== bb
)
515 bb
->loop_father
->latch
= new_bb
;
518 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
520 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
522 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
523 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
529 /* Splits block BB just after labels. The newly created edge is returned. */
532 split_block_after_labels (basic_block bb
)
534 return split_block (bb
, NULL
);
537 /* Moves block BB immediately after block AFTER. Returns false if the
538 movement was impossible. */
541 move_block_after (basic_block bb
, basic_block after
)
545 if (!cfg_hooks
->move_block_after
)
546 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
548 ret
= cfg_hooks
->move_block_after (bb
, after
);
553 /* Deletes the basic block BB. */
556 delete_basic_block (basic_block bb
)
558 if (!cfg_hooks
->delete_basic_block
)
559 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
561 cfg_hooks
->delete_basic_block (bb
);
563 if (current_loops
!= NULL
)
565 struct loop
*loop
= bb
->loop_father
;
567 /* If we remove the header or the latch of a loop, mark the loop for
568 removal by setting its header and latch to NULL. */
569 if (loop
->latch
== bb
570 || loop
->header
== bb
)
574 loops_state_set (LOOPS_NEED_FIXUP
);
577 remove_bb_from_loops (bb
);
580 /* Remove the edges into and out of this block. Note that there may
581 indeed be edges in, if we are removing an unreachable loop. */
582 while (EDGE_COUNT (bb
->preds
) != 0)
583 remove_edge (EDGE_PRED (bb
, 0));
584 while (EDGE_COUNT (bb
->succs
) != 0)
585 remove_edge (EDGE_SUCC (bb
, 0));
587 if (dom_info_available_p (CDI_DOMINATORS
))
588 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
589 if (dom_info_available_p (CDI_POST_DOMINATORS
))
590 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
592 /* Remove the basic block from the array. */
596 /* Splits edge E and returns the newly created basic block. */
602 gcov_type count
= e
->count
;
603 int freq
= EDGE_FREQUENCY (e
);
605 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
607 basic_block src
= e
->src
, dest
= e
->dest
;
609 if (!cfg_hooks
->split_edge
)
610 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
612 if (current_loops
!= NULL
)
613 rescan_loop_exit (e
, false, true);
615 ret
= cfg_hooks
->split_edge (e
);
617 ret
->frequency
= freq
;
618 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
619 single_succ_edge (ret
)->count
= count
;
623 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
624 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
625 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
628 if (dom_info_available_p (CDI_DOMINATORS
))
629 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
631 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
633 /* There are two cases:
635 If the immediate dominator of e->dest is not e->src, it
638 If immediate dominator of e->dest is e->src, it may become
639 ret, provided that all other predecessors of e->dest are
640 dominated by e->dest. */
642 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
643 == single_pred (ret
))
646 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
648 if (f
== single_succ_edge (ret
))
651 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
657 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
661 if (current_loops
!= NULL
)
663 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
664 add_bb_to_loop (ret
, loop
);
666 /* If we split the latch edge of loop adjust the latch block. */
667 if (loop
->latch
== src
668 && loop
->header
== dest
)
675 /* Creates a new basic block just after the basic block AFTER.
676 HEAD and END are the first and the last statement belonging
677 to the block. If both are NULL, an empty block is created. */
680 create_basic_block (void *head
, void *end
, basic_block after
)
684 if (!cfg_hooks
->create_basic_block
)
685 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
687 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
689 if (dom_info_available_p (CDI_DOMINATORS
))
690 add_to_dominance_info (CDI_DOMINATORS
, ret
);
691 if (dom_info_available_p (CDI_POST_DOMINATORS
))
692 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
697 /* Creates an empty basic block just after basic block AFTER. */
700 create_empty_bb (basic_block after
)
702 return create_basic_block (NULL
, NULL
, after
);
705 /* Checks whether we may merge blocks BB1 and BB2. */
708 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
712 if (!cfg_hooks
->can_merge_blocks_p
)
713 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
715 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
721 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
723 if (!cfg_hooks
->predict_edge
)
724 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
726 cfg_hooks
->predict_edge (e
, predictor
, probability
);
730 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
732 if (!cfg_hooks
->predict_edge
)
733 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
735 return cfg_hooks
->predicted_by_p (bb
, predictor
);
738 /* Merges basic block B into basic block A. */
741 merge_blocks (basic_block a
, basic_block b
)
746 if (!cfg_hooks
->merge_blocks
)
747 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
749 cfg_hooks
->merge_blocks (a
, b
);
751 if (current_loops
!= NULL
)
753 /* If the block we merge into is a loop header do nothing unless ... */
754 if (a
->loop_father
->header
== a
)
756 /* ... we merge two loop headers, in which case we kill
758 if (b
->loop_father
->header
== b
)
760 b
->loop_father
->header
= NULL
;
761 b
->loop_father
->latch
= NULL
;
762 loops_state_set (LOOPS_NEED_FIXUP
);
765 /* If we merge a loop header into its predecessor, update the loop
767 else if (b
->loop_father
->header
== b
)
769 remove_bb_from_loops (a
);
770 add_bb_to_loop (a
, b
->loop_father
);
771 a
->loop_father
->header
= a
;
773 remove_bb_from_loops (b
);
776 /* Normally there should only be one successor of A and that is B, but
777 partway though the merge of blocks for conditional_execution we'll
778 be merging a TEST block with THEN and ELSE successors. Free the
779 whole lot of them and hope the caller knows what they're doing. */
781 while (EDGE_COUNT (a
->succs
) != 0)
782 remove_edge (EDGE_SUCC (a
, 0));
784 /* Adjust the edges out of B for the new owner. */
785 FOR_EACH_EDGE (e
, ei
, b
->succs
)
788 if (current_loops
!= NULL
)
790 /* If b was a latch, a now is. */
791 if (e
->dest
->loop_father
->latch
== b
)
792 e
->dest
->loop_father
->latch
= a
;
793 rescan_loop_exit (e
, true, false);
797 a
->flags
|= b
->flags
;
799 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
800 b
->preds
= b
->succs
= NULL
;
802 if (dom_info_available_p (CDI_DOMINATORS
))
803 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
805 if (dom_info_available_p (CDI_DOMINATORS
))
806 delete_from_dominance_info (CDI_DOMINATORS
, b
);
807 if (dom_info_available_p (CDI_POST_DOMINATORS
))
808 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
813 /* Split BB into entry part and the rest (the rest is the newly created block).
814 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
815 part. Returns the edge connecting the entry part to the rest. */
818 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
819 void (*new_bb_cbk
) (basic_block
))
823 basic_block dummy
, jump
;
824 struct loop
*loop
, *ploop
, *cloop
;
826 if (!cfg_hooks
->make_forwarder_block
)
827 internal_error ("%s does not support make_forwarder_block",
830 fallthru
= split_block_after_labels (bb
);
831 dummy
= fallthru
->src
;
834 /* Redirect back edges we want to keep. */
835 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
839 if (redirect_edge_p (e
))
845 dummy
->frequency
-= EDGE_FREQUENCY (e
);
846 dummy
->count
-= e
->count
;
847 if (dummy
->frequency
< 0)
848 dummy
->frequency
= 0;
849 if (dummy
->count
< 0)
851 fallthru
->count
-= e
->count
;
852 if (fallthru
->count
< 0)
856 jump
= redirect_edge_and_branch_force (e
, bb
);
859 /* If we redirected the loop latch edge, the JUMP block now acts like
860 the new latch of the loop. */
861 if (current_loops
!= NULL
862 && dummy
->loop_father
!= NULL
863 && dummy
->loop_father
->header
== dummy
864 && dummy
->loop_father
->latch
== e_src
)
865 dummy
->loop_father
->latch
= jump
;
867 if (new_bb_cbk
!= NULL
)
872 if (dom_info_available_p (CDI_DOMINATORS
))
874 vec
<basic_block
> doms_to_fix
;
875 doms_to_fix
.create (2);
876 doms_to_fix
.quick_push (dummy
);
877 doms_to_fix
.quick_push (bb
);
878 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
879 doms_to_fix
.release ();
882 if (current_loops
!= NULL
)
884 /* If we do not split a loop header, then both blocks belong to the
885 same loop. In case we split loop header and do not redirect the
886 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
887 BB becomes the new header. If latch is not recorded for the loop,
888 we leave this updating on the caller (this may only happen during
890 loop
= dummy
->loop_father
;
891 if (loop
->header
== dummy
892 && loop
->latch
!= NULL
893 && find_edge (loop
->latch
, dummy
) == NULL
)
895 remove_bb_from_loops (dummy
);
899 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
901 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
903 add_bb_to_loop (dummy
, cloop
);
906 /* In case we split loop latch, update it. */
907 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
908 if (ploop
->latch
== dummy
)
912 cfg_hooks
->make_forwarder_block (fallthru
);
917 /* Try to make the edge fallthru. */
920 tidy_fallthru_edge (edge e
)
922 if (cfg_hooks
->tidy_fallthru_edge
)
923 cfg_hooks
->tidy_fallthru_edge (e
);
926 /* Fix up edges that now fall through, or rather should now fall through
927 but previously required a jump around now deleted blocks. Simplify
928 the search by only examining blocks numerically adjacent, since this
929 is how they were created.
931 ??? This routine is currently RTL specific. */
934 tidy_fallthru_edges (void)
938 if (!cfg_hooks
->tidy_fallthru_edge
)
941 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
944 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
950 /* We care about simple conditional or unconditional jumps with
953 If we had a conditional branch to the next instruction when
954 CFG was built, then there will only be one out edge for the
955 block which ended with the conditional branch (since we do
956 not create duplicate edges).
958 Furthermore, the edge will be marked as a fallthru because we
959 merge the flags for the duplicate edges. So we do not want to
960 check that the edge is not a FALLTHRU edge. */
962 if (single_succ_p (b
))
964 s
= single_succ_edge (b
);
965 if (! (s
->flags
& EDGE_COMPLEX
)
967 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
968 tidy_fallthru_edge (s
);
973 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
974 (and possibly create new basic block) to make edge non-fallthru.
975 Return newly created BB or NULL if none. */
978 force_nonfallthru (edge e
)
980 basic_block ret
, src
= e
->src
;
982 if (!cfg_hooks
->force_nonfallthru
)
983 internal_error ("%s does not support force_nonfallthru",
986 ret
= cfg_hooks
->force_nonfallthru (e
);
989 if (dom_info_available_p (CDI_DOMINATORS
))
990 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
992 if (current_loops
!= NULL
)
995 = find_common_loop (single_pred (ret
)->loop_father
,
996 single_succ (ret
)->loop_father
);
997 rescan_loop_exit (e
, false, true);
998 add_bb_to_loop (ret
, loop
);
1005 /* Returns true if we can duplicate basic block BB. */
1008 can_duplicate_block_p (const_basic_block bb
)
1010 if (!cfg_hooks
->can_duplicate_block_p
)
1011 internal_error ("%s does not support can_duplicate_block_p",
1014 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
1017 return cfg_hooks
->can_duplicate_block_p (bb
);
1020 /* Duplicates basic block BB and redirects edge E to it. Returns the
1021 new basic block. The new basic block is placed after the basic block
1025 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1029 gcov_type new_count
= e
? e
->count
: 0;
1032 if (!cfg_hooks
->duplicate_block
)
1033 internal_error ("%s does not support duplicate_block",
1036 if (bb
->count
< new_count
)
1037 new_count
= bb
->count
;
1039 gcc_checking_assert (can_duplicate_block_p (bb
));
1041 new_bb
= cfg_hooks
->duplicate_block (bb
);
1043 move_block_after (new_bb
, after
);
1045 new_bb
->flags
= bb
->flags
;
1046 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1048 /* Since we are creating edges from a new block to successors
1049 of another block (which therefore are known to be disjoint), there
1050 is no need to actually check for duplicated edges. */
1051 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1052 n
->probability
= s
->probability
;
1055 /* Take care for overflows! */
1056 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1057 s
->count
-= n
->count
;
1060 n
->count
= s
->count
;
1066 new_bb
->count
= new_count
;
1067 bb
->count
-= new_count
;
1069 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1070 bb
->frequency
-= EDGE_FREQUENCY (e
);
1072 redirect_edge_and_branch_force (e
, new_bb
);
1076 if (bb
->frequency
< 0)
1081 new_bb
->count
= bb
->count
;
1082 new_bb
->frequency
= bb
->frequency
;
1085 set_bb_original (new_bb
, bb
);
1086 set_bb_copy (bb
, new_bb
);
1088 /* Add the new block to the copy of the loop of BB, or directly to the loop
1089 of BB if the loop is not being copied. */
1090 if (current_loops
!= NULL
)
1092 struct loop
*cloop
= bb
->loop_father
;
1093 struct loop
*copy
= get_loop_copy (cloop
);
1094 /* If we copied the loop header block but not the loop
1095 we have created a loop with multiple entries. Ditch the loop,
1096 add the new block to the outer loop and arrange for a fixup. */
1098 && cloop
->header
== bb
)
1100 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1101 cloop
->header
= NULL
;
1102 cloop
->latch
= NULL
;
1103 loops_state_set (LOOPS_NEED_FIXUP
);
1107 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1108 /* If we copied the loop latch block but not the loop, adjust
1111 && cloop
->latch
== bb
)
1113 cloop
->latch
= NULL
;
1114 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1122 /* Return 1 if BB ends with a call, possibly followed by some
1123 instructions that must stay with the call, 0 otherwise. */
1126 block_ends_with_call_p (basic_block bb
)
1128 if (!cfg_hooks
->block_ends_with_call_p
)
1129 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1131 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1134 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1137 block_ends_with_condjump_p (const_basic_block bb
)
1139 if (!cfg_hooks
->block_ends_with_condjump_p
)
1140 internal_error ("%s does not support block_ends_with_condjump_p",
1143 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1146 /* Add fake edges to the function exit for any non constant and non noreturn
1147 calls, volatile inline assembly in the bitmap of blocks specified by
1148 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1151 The goal is to expose cases in which entering a basic block does not imply
1152 that all subsequent instructions must be executed. */
1155 flow_call_edges_add (sbitmap blocks
)
1157 if (!cfg_hooks
->flow_call_edges_add
)
1158 internal_error ("%s does not support flow_call_edges_add",
1161 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1164 /* This function is called immediately after edge E is added to the
1165 edge vector E->dest->preds. */
1168 execute_on_growing_pred (edge e
)
1170 if (cfg_hooks
->execute_on_growing_pred
)
1171 cfg_hooks
->execute_on_growing_pred (e
);
1174 /* This function is called immediately before edge E is removed from
1175 the edge vector E->dest->preds. */
1178 execute_on_shrinking_pred (edge e
)
1180 if (cfg_hooks
->execute_on_shrinking_pred
)
1181 cfg_hooks
->execute_on_shrinking_pred (e
);
1184 /* This is used inside loop versioning when we want to insert
1185 stmts/insns on the edges, which have a different behavior
1186 in tree's and in RTL, so we made a CFG hook. */
1188 lv_flush_pending_stmts (edge e
)
1190 if (cfg_hooks
->flush_pending_stmts
)
1191 cfg_hooks
->flush_pending_stmts (e
);
1194 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1195 a new version of the loop basic-blocks, the parameters here are
1196 exactly the same as in duplicate_loop_to_header_edge or
1197 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1198 additional work to maintain ssa information that's why there is
1199 a need to call the tree_duplicate_loop_to_header_edge rather
1200 than duplicate_loop_to_header_edge when we are in tree mode. */
1202 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1204 sbitmap wont_exit
, edge orig
,
1205 vec
<edge
> *to_remove
,
1208 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1209 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1215 /* Conditional jumps are represented differently in trees and RTL,
1216 this hook takes a basic block that is known to have a cond jump
1217 at its end and extracts the taken and not taken edges out of it
1218 and store it in E1 and E2 respectively. */
1220 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1222 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1223 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1226 /* Responsible for updating the ssa info (PHI nodes) on the
1227 new condition basic block that guards the versioned loop. */
1229 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1230 basic_block new_block
, edge e
)
1232 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1233 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1236 /* Conditions in trees and RTL are different so we need
1237 a different handling when we add the condition to the
1240 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1241 basic_block new_block
, void *cond
)
1243 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1244 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1247 /* Checks whether all N blocks in BBS array can be copied. */
1249 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1255 for (i
= 0; i
< n
; i
++)
1256 bbs
[i
]->flags
|= BB_DUPLICATED
;
1258 for (i
= 0; i
< n
; i
++)
1260 /* In case we should redirect abnormal edge during duplication, fail. */
1262 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1263 if ((e
->flags
& EDGE_ABNORMAL
)
1264 && (e
->dest
->flags
& BB_DUPLICATED
))
1270 if (!can_duplicate_block_p (bbs
[i
]))
1278 for (i
= 0; i
< n
; i
++)
1279 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1284 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1285 are placed into array NEW_BBS in the same order. Edges from basic blocks
1286 in BBS are also duplicated and copies of those that lead into BBS are
1287 redirected to appropriate newly created block. The function assigns bbs
1288 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1289 loop, so this must be set up correctly in advance)
1291 If UPDATE_DOMINANCE is true then this function updates dominators locally
1292 (LOOPS structure that contains the information about dominators is passed
1293 to enable this), otherwise it does not update the dominator information
1294 and it assumed that the caller will do this, perhaps by destroying and
1295 recreating it instead of trying to do an incremental update like this
1296 function does when update_dominance is true.
1298 BASE is the superloop to that basic block belongs; if its header or latch
1299 is copied, we do not set the new blocks as header or latch.
1301 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1302 also in the same order.
1304 Newly created basic blocks are put after the basic block AFTER in the
1305 instruction stream, and the order of the blocks in BBS array is preserved. */
1308 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1309 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1310 struct loop
*base
, basic_block after
, bool update_dominance
)
1313 basic_block bb
, new_bb
, dom_bb
;
1316 /* Duplicate bbs, update dominators, assign bbs to loops. */
1317 for (i
= 0; i
< n
; i
++)
1321 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1323 bb
->flags
|= BB_DUPLICATED
;
1324 if (bb
->loop_father
)
1326 /* Possibly set loop header. */
1327 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1328 new_bb
->loop_father
->header
= new_bb
;
1330 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1331 new_bb
->loop_father
->latch
= new_bb
;
1335 /* Set dominators. */
1336 if (update_dominance
)
1338 for (i
= 0; i
< n
; i
++)
1341 new_bb
= new_bbs
[i
];
1343 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1344 if (dom_bb
->flags
& BB_DUPLICATED
)
1346 dom_bb
= get_bb_copy (dom_bb
);
1347 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1352 /* Redirect edges. */
1353 for (j
= 0; j
< num_edges
; j
++)
1354 new_edges
[j
] = NULL
;
1355 for (i
= 0; i
< n
; i
++)
1358 new_bb
= new_bbs
[i
];
1361 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1363 for (j
= 0; j
< num_edges
; j
++)
1364 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1367 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1369 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1373 /* Clear information about duplicates. */
1374 for (i
= 0; i
< n
; i
++)
1375 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1378 /* Return true if BB contains only labels or non-executable
1381 empty_block_p (basic_block bb
)
1383 gcc_assert (cfg_hooks
->empty_block_p
);
1384 return cfg_hooks
->empty_block_p (bb
);
1387 /* Split a basic block if it ends with a conditional branch and if
1388 the other part of the block is not empty. */
1390 split_block_before_cond_jump (basic_block bb
)
1392 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1393 return cfg_hooks
->split_block_before_cond_jump (bb
);
1396 /* Work-horse for passes.c:check_profile_consistency.
1397 Do book-keeping of the CFG for the profile consistency checker.
1398 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1399 then do post-pass accounting. Store the counting in RECORD. */
1402 account_profile_record (struct profile_record
*record
, int after_pass
)
1412 if (bb
!= EXIT_BLOCK_PTR_FOR_FUNCTION (cfun
)
1413 && profile_status
!= PROFILE_ABSENT
)
1416 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1417 sum
+= e
->probability
;
1418 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1419 record
->num_mismatched_freq_out
[after_pass
]++;
1421 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1423 if (EDGE_COUNT (bb
->succs
)
1424 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1425 record
->num_mismatched_count_out
[after_pass
]++;
1427 if (bb
!= ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1428 && profile_status
!= PROFILE_ABSENT
)
1431 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1432 sum
+= EDGE_FREQUENCY (e
);
1433 if (abs (sum
- bb
->frequency
) > 100
1434 || (MAX (sum
, bb
->frequency
) > 10
1435 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1436 record
->num_mismatched_freq_in
[after_pass
]++;
1438 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1440 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1441 record
->num_mismatched_count_in
[after_pass
]++;
1443 if (bb
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1444 || bb
== EXIT_BLOCK_PTR_FOR_FUNCTION (cfun
))
1446 gcc_assert (cfg_hooks
->account_profile_record
);
1447 cfg_hooks
->account_profile_record (bb
, after_pass
, record
);