1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <s.pop@laposte.net>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "tree-flow.h"
31 #include "diagnostic-core.h"
34 /* A pointer to one of the hooks containers. */
35 static struct cfg_hooks
*cfg_hooks
;
37 /* Initialization of functions specific to the rtl IR. */
39 rtl_register_cfg_hooks (void)
41 cfg_hooks
= &rtl_cfg_hooks
;
44 /* Initialization of functions specific to the rtl IR. */
46 cfg_layout_rtl_register_cfg_hooks (void)
48 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
51 /* Initialization of functions specific to the tree IR. */
54 gimple_register_cfg_hooks (void)
56 cfg_hooks
= &gimple_cfg_hooks
;
66 set_cfg_hooks (struct cfg_hooks new_cfg_hooks
)
68 *cfg_hooks
= new_cfg_hooks
;
71 /* Returns current ir type. */
74 current_ir_type (void)
76 if (cfg_hooks
== &gimple_cfg_hooks
)
78 else if (cfg_hooks
== &rtl_cfg_hooks
)
80 else if (cfg_hooks
== &cfg_layout_rtl_cfg_hooks
)
81 return IR_RTL_CFGLAYOUT
;
86 /* Verify the CFG consistency.
88 Currently it does following: checks edge and basic block list correctness
89 and calls into IL dependent checking then. */
92 verify_flow_info (void)
94 size_t *edge_checksum
;
96 basic_block bb
, last_bb_seen
;
97 basic_block
*last_visited
;
99 timevar_push (TV_CFG_VERIFY
);
100 last_visited
= XCNEWVEC (basic_block
, last_basic_block
);
101 edge_checksum
= XCNEWVEC (size_t, last_basic_block
);
103 /* Check bb chain & numbers. */
104 last_bb_seen
= ENTRY_BLOCK_PTR
;
105 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
107 if (bb
!= EXIT_BLOCK_PTR
108 && bb
!= BASIC_BLOCK (bb
->index
))
110 error ("bb %d on wrong place", bb
->index
);
114 if (bb
->prev_bb
!= last_bb_seen
)
116 error ("prev_bb of %d should be %d, not %d",
117 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
124 /* Now check the basic blocks (boundaries etc.) */
125 FOR_EACH_BB_REVERSE (bb
)
131 if (bb
->loop_father
!= NULL
&& current_loops
== NULL
)
133 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
137 if (bb
->loop_father
== NULL
&& current_loops
!= NULL
)
139 error ("verify_flow_info: Block %i lacks loop_father", bb
->index
);
145 error ("verify_flow_info: Wrong count of block %i %i",
146 bb
->index
, (int)bb
->count
);
149 if (bb
->frequency
< 0)
151 error ("verify_flow_info: Wrong frequency of block %i %i",
152 bb
->index
, bb
->frequency
);
155 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
157 if (last_visited
[e
->dest
->index
] == bb
)
159 error ("verify_flow_info: Duplicate edge %i->%i",
160 e
->src
->index
, e
->dest
->index
);
163 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
165 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
166 e
->src
->index
, e
->dest
->index
, e
->probability
);
171 error ("verify_flow_info: Wrong count of edge %i->%i %i",
172 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
176 last_visited
[e
->dest
->index
] = bb
;
178 if (e
->flags
& EDGE_FALLTHRU
)
183 error ("verify_flow_info: Basic block %d succ edge is corrupted",
185 fprintf (stderr
, "Predecessor: ");
186 dump_edge_info (stderr
, e
, 0);
187 fprintf (stderr
, "\nSuccessor: ");
188 dump_edge_info (stderr
, e
, 1);
189 fprintf (stderr
, "\n");
193 edge_checksum
[e
->dest
->index
] += (size_t) e
;
197 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
201 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
205 error ("basic block %d pred edge is corrupted", bb
->index
);
206 fputs ("Predecessor: ", stderr
);
207 dump_edge_info (stderr
, e
, 0);
208 fputs ("\nSuccessor: ", stderr
);
209 dump_edge_info (stderr
, e
, 1);
210 fputc ('\n', stderr
);
214 if (ei
.index
!= e
->dest_idx
)
216 error ("basic block %d pred edge is corrupted", bb
->index
);
217 error ("its dest_idx should be %d, not %d",
218 ei
.index
, e
->dest_idx
);
219 fputs ("Predecessor: ", stderr
);
220 dump_edge_info (stderr
, e
, 0);
221 fputs ("\nSuccessor: ", stderr
);
222 dump_edge_info (stderr
, e
, 1);
223 fputc ('\n', stderr
);
227 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
231 /* Complete edge checksumming for ENTRY and EXIT. */
236 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
237 edge_checksum
[e
->dest
->index
] += (size_t) e
;
239 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
240 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
243 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
244 if (edge_checksum
[bb
->index
])
246 error ("basic block %i edge lists are corrupted", bb
->index
);
250 last_bb_seen
= ENTRY_BLOCK_PTR
;
254 free (edge_checksum
);
256 if (cfg_hooks
->verify_flow_info
)
257 err
|= cfg_hooks
->verify_flow_info ();
259 internal_error ("verify_flow_info failed");
260 timevar_pop (TV_CFG_VERIFY
);
263 /* Print out one basic block. This function takes care of the purely
264 graph related information. The cfg hook for the active representation
265 should dump representation-specific information. */
268 dump_bb (basic_block bb
, FILE *outf
, int indent
)
274 s_indent
= (char *) alloca ((size_t) indent
+ 1);
275 memset (s_indent
, ' ', (size_t) indent
);
276 s_indent
[indent
] = '\0';
278 fprintf (outf
, ";;%s basic block %d, loop depth %d, count ",
279 s_indent
, bb
->index
, bb
->loop_depth
);
280 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
283 fprintf (outf
, ";;%s prev block ", s_indent
);
285 fprintf (outf
, "%d, ", bb
->prev_bb
->index
);
287 fprintf (outf
, "(nil), ");
288 fprintf (outf
, "next block ");
290 fprintf (outf
, "%d", bb
->next_bb
->index
);
292 fprintf (outf
, "(nil)");
295 fprintf (outf
, ";;%s pred: ", s_indent
);
296 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
297 dump_edge_info (outf
, e
, 0);
300 fprintf (outf
, ";;%s succ: ", s_indent
);
301 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
302 dump_edge_info (outf
, e
, 1);
305 if (cfg_hooks
->dump_bb
)
306 cfg_hooks
->dump_bb (bb
, outf
, indent
, 0);
309 /* Redirect edge E to the given basic block DEST and update underlying program
310 representation. Returns edge representing redirected branch (that may not
311 be equivalent to E in the case of duplicate edges being removed) or NULL
312 if edge is not easily redirectable for whatever reason. */
315 redirect_edge_and_branch (edge e
, basic_block dest
)
319 if (!cfg_hooks
->redirect_edge_and_branch
)
320 internal_error ("%s does not support redirect_edge_and_branch",
323 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
325 /* If RET != E, then either the redirection failed, or the edge E
326 was removed since RET already lead to the same destination. */
327 if (current_loops
!= NULL
&& ret
== e
)
328 rescan_loop_exit (e
, false, false);
333 /* Returns true if it is possible to remove the edge E by redirecting it
334 to the destination of the other edge going from its source. */
337 can_remove_branch_p (const_edge e
)
339 if (!cfg_hooks
->can_remove_branch_p
)
340 internal_error ("%s does not support can_remove_branch_p",
343 if (EDGE_COUNT (e
->src
->succs
) != 2)
346 return cfg_hooks
->can_remove_branch_p (e
);
349 /* Removes E, by redirecting it to the destination of the other edge going
350 from its source. Can_remove_branch_p must be true for E, hence this
351 operation cannot fail. */
354 remove_branch (edge e
)
357 basic_block src
= e
->src
;
360 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
362 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
363 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
365 e
= redirect_edge_and_branch (e
, other
->dest
);
366 gcc_assert (e
!= NULL
);
368 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
372 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
377 if (current_loops
!= NULL
)
378 rescan_loop_exit (e
, false, true);
383 /* Redirect the edge E to basic block DEST even if it requires creating
384 of a new basic block; then it returns the newly created basic block.
385 Aborts when redirection is impossible. */
388 redirect_edge_and_branch_force (edge e
, basic_block dest
)
390 basic_block ret
, src
= e
->src
;
392 if (!cfg_hooks
->redirect_edge_and_branch_force
)
393 internal_error ("%s does not support redirect_edge_and_branch_force",
396 if (current_loops
!= NULL
)
397 rescan_loop_exit (e
, false, true);
399 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
401 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
402 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
404 if (current_loops
!= NULL
)
409 = find_common_loop (single_pred (ret
)->loop_father
,
410 single_succ (ret
)->loop_father
);
411 add_bb_to_loop (ret
, loop
);
413 else if (find_edge (src
, dest
) == e
)
414 rescan_loop_exit (e
, true, false);
420 /* Splits basic block BB after the specified instruction I (but at least after
421 the labels). If I is NULL, splits just after labels. The newly created edge
422 is returned. The new basic block is created just after the old one. */
425 split_block (basic_block bb
, void *i
)
430 if (!cfg_hooks
->split_block
)
431 internal_error ("%s does not support split_block", cfg_hooks
->name
);
433 new_bb
= cfg_hooks
->split_block (bb
, i
);
437 new_bb
->count
= bb
->count
;
438 new_bb
->frequency
= bb
->frequency
;
439 new_bb
->loop_depth
= bb
->loop_depth
;
440 new_bb
->discriminator
= bb
->discriminator
;
442 if (dom_info_available_p (CDI_DOMINATORS
))
444 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
445 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
448 if (current_loops
!= NULL
)
450 add_bb_to_loop (new_bb
, bb
->loop_father
);
451 if (bb
->loop_father
->latch
== bb
)
452 bb
->loop_father
->latch
= new_bb
;
455 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
457 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
459 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
460 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
466 /* Splits block BB just after labels. The newly created edge is returned. */
469 split_block_after_labels (basic_block bb
)
471 return split_block (bb
, NULL
);
474 /* Moves block BB immediately after block AFTER. Returns false if the
475 movement was impossible. */
478 move_block_after (basic_block bb
, basic_block after
)
482 if (!cfg_hooks
->move_block_after
)
483 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
485 ret
= cfg_hooks
->move_block_after (bb
, after
);
490 /* Deletes the basic block BB. */
493 delete_basic_block (basic_block bb
)
495 if (!cfg_hooks
->delete_basic_block
)
496 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
498 cfg_hooks
->delete_basic_block (bb
);
500 if (current_loops
!= NULL
)
502 struct loop
*loop
= bb
->loop_father
;
504 /* If we remove the header or the latch of a loop, mark the loop for
505 removal by setting its header and latch to NULL. */
506 if (loop
->latch
== bb
507 || loop
->header
== bb
)
511 loops_state_set (LOOPS_NEED_FIXUP
);
514 remove_bb_from_loops (bb
);
517 /* Remove the edges into and out of this block. Note that there may
518 indeed be edges in, if we are removing an unreachable loop. */
519 while (EDGE_COUNT (bb
->preds
) != 0)
520 remove_edge (EDGE_PRED (bb
, 0));
521 while (EDGE_COUNT (bb
->succs
) != 0)
522 remove_edge (EDGE_SUCC (bb
, 0));
524 if (dom_info_available_p (CDI_DOMINATORS
))
525 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
526 if (dom_info_available_p (CDI_POST_DOMINATORS
))
527 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
529 /* Remove the basic block from the array. */
533 /* Splits edge E and returns the newly created basic block. */
539 gcov_type count
= e
->count
;
540 int freq
= EDGE_FREQUENCY (e
);
542 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
544 basic_block src
= e
->src
, dest
= e
->dest
;
546 if (!cfg_hooks
->split_edge
)
547 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
549 if (current_loops
!= NULL
)
550 rescan_loop_exit (e
, false, true);
552 ret
= cfg_hooks
->split_edge (e
);
554 ret
->frequency
= freq
;
555 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
556 single_succ_edge (ret
)->count
= count
;
560 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
561 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
562 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
565 if (dom_info_available_p (CDI_DOMINATORS
))
566 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
568 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
570 /* There are two cases:
572 If the immediate dominator of e->dest is not e->src, it
575 If immediate dominator of e->dest is e->src, it may become
576 ret, provided that all other predecessors of e->dest are
577 dominated by e->dest. */
579 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
580 == single_pred (ret
))
583 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
585 if (f
== single_succ_edge (ret
))
588 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
594 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
598 if (current_loops
!= NULL
)
600 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
601 add_bb_to_loop (ret
, loop
);
603 if (loop
->latch
== src
)
610 /* Creates a new basic block just after the basic block AFTER.
611 HEAD and END are the first and the last statement belonging
612 to the block. If both are NULL, an empty block is created. */
615 create_basic_block (void *head
, void *end
, basic_block after
)
619 if (!cfg_hooks
->create_basic_block
)
620 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
622 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
624 if (dom_info_available_p (CDI_DOMINATORS
))
625 add_to_dominance_info (CDI_DOMINATORS
, ret
);
626 if (dom_info_available_p (CDI_POST_DOMINATORS
))
627 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
632 /* Creates an empty basic block just after basic block AFTER. */
635 create_empty_bb (basic_block after
)
637 return create_basic_block (NULL
, NULL
, after
);
640 /* Checks whether we may merge blocks BB1 and BB2. */
643 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
647 if (!cfg_hooks
->can_merge_blocks_p
)
648 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
650 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
656 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
658 if (!cfg_hooks
->predict_edge
)
659 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
661 cfg_hooks
->predict_edge (e
, predictor
, probability
);
665 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
667 if (!cfg_hooks
->predict_edge
)
668 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
670 return cfg_hooks
->predicted_by_p (bb
, predictor
);
673 /* Merges basic block B into basic block A. */
676 merge_blocks (basic_block a
, basic_block b
)
681 if (!cfg_hooks
->merge_blocks
)
682 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
684 cfg_hooks
->merge_blocks (a
, b
);
686 /* If we merge a loop header into its predecessor, update the loop
688 if (current_loops
!= NULL
)
690 if (b
->loop_father
->header
== b
)
692 remove_bb_from_loops (a
);
693 add_bb_to_loop (a
, b
->loop_father
);
694 a
->loop_father
->header
= a
;
696 remove_bb_from_loops (b
);
699 /* Normally there should only be one successor of A and that is B, but
700 partway though the merge of blocks for conditional_execution we'll
701 be merging a TEST block with THEN and ELSE successors. Free the
702 whole lot of them and hope the caller knows what they're doing. */
704 while (EDGE_COUNT (a
->succs
) != 0)
705 remove_edge (EDGE_SUCC (a
, 0));
707 /* Adjust the edges out of B for the new owner. */
708 FOR_EACH_EDGE (e
, ei
, b
->succs
)
711 if (current_loops
!= NULL
)
712 rescan_loop_exit (e
, true, false);
715 a
->flags
|= b
->flags
;
717 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
718 b
->preds
= b
->succs
= NULL
;
720 if (dom_info_available_p (CDI_DOMINATORS
))
721 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
723 if (dom_info_available_p (CDI_DOMINATORS
))
724 delete_from_dominance_info (CDI_DOMINATORS
, b
);
725 if (dom_info_available_p (CDI_POST_DOMINATORS
))
726 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
731 /* Split BB into entry part and the rest (the rest is the newly created block).
732 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
733 part. Returns the edge connecting the entry part to the rest. */
736 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
737 void (*new_bb_cbk
) (basic_block
))
741 basic_block dummy
, jump
;
742 struct loop
*loop
, *ploop
, *cloop
;
744 if (!cfg_hooks
->make_forwarder_block
)
745 internal_error ("%s does not support make_forwarder_block",
748 fallthru
= split_block_after_labels (bb
);
749 dummy
= fallthru
->src
;
752 /* Redirect back edges we want to keep. */
753 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
757 if (redirect_edge_p (e
))
763 dummy
->frequency
-= EDGE_FREQUENCY (e
);
764 dummy
->count
-= e
->count
;
765 if (dummy
->frequency
< 0)
766 dummy
->frequency
= 0;
767 if (dummy
->count
< 0)
769 fallthru
->count
-= e
->count
;
770 if (fallthru
->count
< 0)
774 jump
= redirect_edge_and_branch_force (e
, bb
);
777 /* If we redirected the loop latch edge, the JUMP block now acts like
778 the new latch of the loop. */
779 if (current_loops
!= NULL
780 && dummy
->loop_father
!= NULL
781 && dummy
->loop_father
->header
== dummy
782 && dummy
->loop_father
->latch
== e_src
)
783 dummy
->loop_father
->latch
= jump
;
785 if (new_bb_cbk
!= NULL
)
790 if (dom_info_available_p (CDI_DOMINATORS
))
792 VEC (basic_block
, heap
) *doms_to_fix
= VEC_alloc (basic_block
, heap
, 2);
793 VEC_quick_push (basic_block
, doms_to_fix
, dummy
);
794 VEC_quick_push (basic_block
, doms_to_fix
, bb
);
795 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
796 VEC_free (basic_block
, heap
, doms_to_fix
);
799 if (current_loops
!= NULL
)
801 /* If we do not split a loop header, then both blocks belong to the
802 same loop. In case we split loop header and do not redirect the
803 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
804 BB becomes the new header. If latch is not recorded for the loop,
805 we leave this updating on the caller (this may only happen during
807 loop
= dummy
->loop_father
;
808 if (loop
->header
== dummy
809 && loop
->latch
!= NULL
810 && find_edge (loop
->latch
, dummy
) == NULL
)
812 remove_bb_from_loops (dummy
);
816 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
818 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
820 add_bb_to_loop (dummy
, cloop
);
823 /* In case we split loop latch, update it. */
824 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
825 if (ploop
->latch
== dummy
)
829 cfg_hooks
->make_forwarder_block (fallthru
);
834 /* Try to make the edge fallthru. */
837 tidy_fallthru_edge (edge e
)
839 if (cfg_hooks
->tidy_fallthru_edge
)
840 cfg_hooks
->tidy_fallthru_edge (e
);
843 /* Fix up edges that now fall through, or rather should now fall through
844 but previously required a jump around now deleted blocks. Simplify
845 the search by only examining blocks numerically adjacent, since this
846 is how they were created.
848 ??? This routine is currently RTL specific. */
851 tidy_fallthru_edges (void)
855 if (!cfg_hooks
->tidy_fallthru_edge
)
858 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
861 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
867 /* We care about simple conditional or unconditional jumps with
870 If we had a conditional branch to the next instruction when
871 CFG was built, then there will only be one out edge for the
872 block which ended with the conditional branch (since we do
873 not create duplicate edges).
875 Furthermore, the edge will be marked as a fallthru because we
876 merge the flags for the duplicate edges. So we do not want to
877 check that the edge is not a FALLTHRU edge. */
879 if (single_succ_p (b
))
881 s
= single_succ_edge (b
);
882 if (! (s
->flags
& EDGE_COMPLEX
)
884 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
885 tidy_fallthru_edge (s
);
890 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
891 (and possibly create new basic block) to make edge non-fallthru.
892 Return newly created BB or NULL if none. */
895 force_nonfallthru (edge e
)
897 basic_block ret
, src
= e
->src
;
899 if (!cfg_hooks
->force_nonfallthru
)
900 internal_error ("%s does not support force_nonfallthru",
903 ret
= cfg_hooks
->force_nonfallthru (e
);
906 if (dom_info_available_p (CDI_DOMINATORS
))
907 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
909 if (current_loops
!= NULL
)
912 = find_common_loop (single_pred (ret
)->loop_father
,
913 single_succ (ret
)->loop_father
);
914 rescan_loop_exit (e
, false, true);
915 add_bb_to_loop (ret
, loop
);
922 /* Returns true if we can duplicate basic block BB. */
925 can_duplicate_block_p (const_basic_block bb
)
927 if (!cfg_hooks
->can_duplicate_block_p
)
928 internal_error ("%s does not support can_duplicate_block_p",
931 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
934 return cfg_hooks
->can_duplicate_block_p (bb
);
937 /* Duplicates basic block BB and redirects edge E to it. Returns the
938 new basic block. The new basic block is placed after the basic block
942 duplicate_block (basic_block bb
, edge e
, basic_block after
)
946 gcov_type new_count
= e
? e
->count
: 0;
949 if (!cfg_hooks
->duplicate_block
)
950 internal_error ("%s does not support duplicate_block",
953 if (bb
->count
< new_count
)
954 new_count
= bb
->count
;
956 gcc_checking_assert (can_duplicate_block_p (bb
));
958 new_bb
= cfg_hooks
->duplicate_block (bb
);
960 move_block_after (new_bb
, after
);
962 new_bb
->loop_depth
= bb
->loop_depth
;
963 new_bb
->flags
= bb
->flags
;
964 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
966 /* Since we are creating edges from a new block to successors
967 of another block (which therefore are known to be disjoint), there
968 is no need to actually check for duplicated edges. */
969 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
970 n
->probability
= s
->probability
;
973 /* Take care for overflows! */
974 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
975 s
->count
-= n
->count
;
984 new_bb
->count
= new_count
;
985 bb
->count
-= new_count
;
987 new_bb
->frequency
= EDGE_FREQUENCY (e
);
988 bb
->frequency
-= EDGE_FREQUENCY (e
);
990 redirect_edge_and_branch_force (e
, new_bb
);
994 if (bb
->frequency
< 0)
999 new_bb
->count
= bb
->count
;
1000 new_bb
->frequency
= bb
->frequency
;
1003 set_bb_original (new_bb
, bb
);
1004 set_bb_copy (bb
, new_bb
);
1006 /* Add the new block to the copy of the loop of BB, or directly to the loop
1007 of BB if the loop is not being copied. */
1008 if (current_loops
!= NULL
)
1010 struct loop
*cloop
= bb
->loop_father
;
1011 struct loop
*copy
= get_loop_copy (cloop
);
1012 /* If we copied the loop header block but not the loop
1013 we have created a loop with multiple entries. Ditch the loop,
1014 add the new block to the outer loop and arrange for a fixup. */
1016 && cloop
->header
== bb
)
1018 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1019 cloop
->header
= NULL
;
1020 cloop
->latch
= NULL
;
1021 loops_state_set (LOOPS_NEED_FIXUP
);
1025 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1026 /* If we copied the loop latch block but not the loop, adjust
1029 && cloop
->latch
== bb
)
1031 cloop
->latch
= NULL
;
1032 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1040 /* Return 1 if BB ends with a call, possibly followed by some
1041 instructions that must stay with the call, 0 otherwise. */
1044 block_ends_with_call_p (basic_block bb
)
1046 if (!cfg_hooks
->block_ends_with_call_p
)
1047 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1049 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1052 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1055 block_ends_with_condjump_p (const_basic_block bb
)
1057 if (!cfg_hooks
->block_ends_with_condjump_p
)
1058 internal_error ("%s does not support block_ends_with_condjump_p",
1061 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1064 /* Add fake edges to the function exit for any non constant and non noreturn
1065 calls, volatile inline assembly in the bitmap of blocks specified by
1066 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1069 The goal is to expose cases in which entering a basic block does not imply
1070 that all subsequent instructions must be executed. */
1073 flow_call_edges_add (sbitmap blocks
)
1075 if (!cfg_hooks
->flow_call_edges_add
)
1076 internal_error ("%s does not support flow_call_edges_add",
1079 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1082 /* This function is called immediately after edge E is added to the
1083 edge vector E->dest->preds. */
1086 execute_on_growing_pred (edge e
)
1088 if (cfg_hooks
->execute_on_growing_pred
)
1089 cfg_hooks
->execute_on_growing_pred (e
);
1092 /* This function is called immediately before edge E is removed from
1093 the edge vector E->dest->preds. */
1096 execute_on_shrinking_pred (edge e
)
1098 if (cfg_hooks
->execute_on_shrinking_pred
)
1099 cfg_hooks
->execute_on_shrinking_pred (e
);
1102 /* This is used inside loop versioning when we want to insert
1103 stmts/insns on the edges, which have a different behavior
1104 in tree's and in RTL, so we made a CFG hook. */
1106 lv_flush_pending_stmts (edge e
)
1108 if (cfg_hooks
->flush_pending_stmts
)
1109 cfg_hooks
->flush_pending_stmts (e
);
1112 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1113 a new version of the loop basic-blocks, the parameters here are
1114 exactly the same as in duplicate_loop_to_header_edge or
1115 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1116 additional work to maintain ssa information that's why there is
1117 a need to call the tree_duplicate_loop_to_header_edge rather
1118 than duplicate_loop_to_header_edge when we are in tree mode. */
1120 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1122 sbitmap wont_exit
, edge orig
,
1123 VEC (edge
, heap
) **to_remove
,
1126 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1127 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1133 /* Conditional jumps are represented differently in trees and RTL,
1134 this hook takes a basic block that is known to have a cond jump
1135 at its end and extracts the taken and not taken edges out of it
1136 and store it in E1 and E2 respectively. */
1138 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1140 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1141 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1144 /* Responsible for updating the ssa info (PHI nodes) on the
1145 new condition basic block that guards the versioned loop. */
1147 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1148 basic_block new_block
, edge e
)
1150 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1151 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1154 /* Conditions in trees and RTL are different so we need
1155 a different handling when we add the condition to the
1158 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1159 basic_block new_block
, void *cond
)
1161 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1162 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);