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"
29 #include "basic-block.h"
30 #include "tree-flow.h"
32 #include "diagnostic-core.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 dump_bb_info (outf
, bb
, indent
, flags
| TDF_COMMENT
, true, true);
275 if (cfg_hooks
->dump_bb
)
276 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
279 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
281 dump_flow_info (FILE *file
, int flags
)
285 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
288 dump_bb (file
, bb
, 0, flags
);
289 check_bb_profile (bb
, file
);
295 /* Like above, but dump to stderr. To be called from debuggers. */
296 void debug_flow_info (void);
298 debug_flow_info (void)
300 dump_flow_info (stderr
, TDF_DETAILS
);
303 /* Redirect edge E to the given basic block DEST and update underlying program
304 representation. Returns edge representing redirected branch (that may not
305 be equivalent to E in the case of duplicate edges being removed) or NULL
306 if edge is not easily redirectable for whatever reason. */
309 redirect_edge_and_branch (edge e
, basic_block dest
)
313 if (!cfg_hooks
->redirect_edge_and_branch
)
314 internal_error ("%s does not support redirect_edge_and_branch",
317 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
319 /* If RET != E, then either the redirection failed, or the edge E
320 was removed since RET already lead to the same destination. */
321 if (current_loops
!= NULL
&& ret
== e
)
322 rescan_loop_exit (e
, false, false);
327 /* Returns true if it is possible to remove the edge E by redirecting it
328 to the destination of the other edge going from its source. */
331 can_remove_branch_p (const_edge e
)
333 if (!cfg_hooks
->can_remove_branch_p
)
334 internal_error ("%s does not support can_remove_branch_p",
337 if (EDGE_COUNT (e
->src
->succs
) != 2)
340 return cfg_hooks
->can_remove_branch_p (e
);
343 /* Removes E, by redirecting it to the destination of the other edge going
344 from its source. Can_remove_branch_p must be true for E, hence this
345 operation cannot fail. */
348 remove_branch (edge e
)
351 basic_block src
= e
->src
;
354 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
356 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
357 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
359 e
= redirect_edge_and_branch (e
, other
->dest
);
360 gcc_assert (e
!= NULL
);
362 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
366 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
371 if (current_loops
!= NULL
)
372 rescan_loop_exit (e
, false, true);
374 /* This is probably not needed, but it doesn't hurt. */
375 /* FIXME: This should be called via a remove_edge hook. */
376 if (current_ir_type () == IR_GIMPLE
)
377 redirect_edge_var_map_clear (e
);
382 /* Like redirect_edge_succ but avoid possible duplicate edge. */
385 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
389 s
= find_edge (e
->src
, new_succ
);
392 s
->flags
|= e
->flags
;
393 s
->probability
+= e
->probability
;
394 if (s
->probability
> REG_BR_PROB_BASE
)
395 s
->probability
= REG_BR_PROB_BASE
;
396 s
->count
+= e
->count
;
397 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
398 redirect_edge_var_map_dup (s
, e
);
403 redirect_edge_succ (e
, new_succ
);
408 /* Redirect the edge E to basic block DEST even if it requires creating
409 of a new basic block; then it returns the newly created basic block.
410 Aborts when redirection is impossible. */
413 redirect_edge_and_branch_force (edge e
, basic_block dest
)
415 basic_block ret
, src
= e
->src
;
417 if (!cfg_hooks
->redirect_edge_and_branch_force
)
418 internal_error ("%s does not support redirect_edge_and_branch_force",
421 if (current_loops
!= NULL
)
422 rescan_loop_exit (e
, false, true);
424 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
426 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
427 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
429 if (current_loops
!= NULL
)
434 = find_common_loop (single_pred (ret
)->loop_father
,
435 single_succ (ret
)->loop_father
);
436 add_bb_to_loop (ret
, loop
);
438 else if (find_edge (src
, dest
) == e
)
439 rescan_loop_exit (e
, true, false);
445 /* Splits basic block BB after the specified instruction I (but at least after
446 the labels). If I is NULL, splits just after labels. The newly created edge
447 is returned. The new basic block is created just after the old one. */
450 split_block (basic_block bb
, void *i
)
455 if (!cfg_hooks
->split_block
)
456 internal_error ("%s does not support split_block", cfg_hooks
->name
);
458 new_bb
= cfg_hooks
->split_block (bb
, i
);
462 new_bb
->count
= bb
->count
;
463 new_bb
->frequency
= bb
->frequency
;
464 new_bb
->loop_depth
= bb
->loop_depth
;
465 new_bb
->discriminator
= bb
->discriminator
;
467 if (dom_info_available_p (CDI_DOMINATORS
))
469 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
470 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
473 if (current_loops
!= NULL
)
475 add_bb_to_loop (new_bb
, bb
->loop_father
);
476 if (bb
->loop_father
->latch
== bb
)
477 bb
->loop_father
->latch
= new_bb
;
480 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
482 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
484 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
485 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
491 /* Splits block BB just after labels. The newly created edge is returned. */
494 split_block_after_labels (basic_block bb
)
496 return split_block (bb
, NULL
);
499 /* Moves block BB immediately after block AFTER. Returns false if the
500 movement was impossible. */
503 move_block_after (basic_block bb
, basic_block after
)
507 if (!cfg_hooks
->move_block_after
)
508 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
510 ret
= cfg_hooks
->move_block_after (bb
, after
);
515 /* Deletes the basic block BB. */
518 delete_basic_block (basic_block bb
)
520 if (!cfg_hooks
->delete_basic_block
)
521 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
523 cfg_hooks
->delete_basic_block (bb
);
525 if (current_loops
!= NULL
)
527 struct loop
*loop
= bb
->loop_father
;
529 /* If we remove the header or the latch of a loop, mark the loop for
530 removal by setting its header and latch to NULL. */
531 if (loop
->latch
== bb
532 || loop
->header
== bb
)
536 loops_state_set (LOOPS_NEED_FIXUP
);
539 remove_bb_from_loops (bb
);
542 /* Remove the edges into and out of this block. Note that there may
543 indeed be edges in, if we are removing an unreachable loop. */
544 while (EDGE_COUNT (bb
->preds
) != 0)
545 remove_edge (EDGE_PRED (bb
, 0));
546 while (EDGE_COUNT (bb
->succs
) != 0)
547 remove_edge (EDGE_SUCC (bb
, 0));
549 if (dom_info_available_p (CDI_DOMINATORS
))
550 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
551 if (dom_info_available_p (CDI_POST_DOMINATORS
))
552 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
554 /* Remove the basic block from the array. */
558 /* Splits edge E and returns the newly created basic block. */
564 gcov_type count
= e
->count
;
565 int freq
= EDGE_FREQUENCY (e
);
567 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
569 basic_block src
= e
->src
, dest
= e
->dest
;
571 if (!cfg_hooks
->split_edge
)
572 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
574 if (current_loops
!= NULL
)
575 rescan_loop_exit (e
, false, true);
577 ret
= cfg_hooks
->split_edge (e
);
579 ret
->frequency
= freq
;
580 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
581 single_succ_edge (ret
)->count
= count
;
585 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
586 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
587 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
590 if (dom_info_available_p (CDI_DOMINATORS
))
591 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
593 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
595 /* There are two cases:
597 If the immediate dominator of e->dest is not e->src, it
600 If immediate dominator of e->dest is e->src, it may become
601 ret, provided that all other predecessors of e->dest are
602 dominated by e->dest. */
604 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
605 == single_pred (ret
))
608 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
610 if (f
== single_succ_edge (ret
))
613 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
619 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
623 if (current_loops
!= NULL
)
625 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
626 add_bb_to_loop (ret
, loop
);
628 if (loop
->latch
== src
)
635 /* Creates a new basic block just after the basic block AFTER.
636 HEAD and END are the first and the last statement belonging
637 to the block. If both are NULL, an empty block is created. */
640 create_basic_block (void *head
, void *end
, basic_block after
)
644 if (!cfg_hooks
->create_basic_block
)
645 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
647 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
649 if (dom_info_available_p (CDI_DOMINATORS
))
650 add_to_dominance_info (CDI_DOMINATORS
, ret
);
651 if (dom_info_available_p (CDI_POST_DOMINATORS
))
652 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
657 /* Creates an empty basic block just after basic block AFTER. */
660 create_empty_bb (basic_block after
)
662 return create_basic_block (NULL
, NULL
, after
);
665 /* Checks whether we may merge blocks BB1 and BB2. */
668 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
672 if (!cfg_hooks
->can_merge_blocks_p
)
673 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
675 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
681 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
683 if (!cfg_hooks
->predict_edge
)
684 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
686 cfg_hooks
->predict_edge (e
, predictor
, probability
);
690 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
692 if (!cfg_hooks
->predict_edge
)
693 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
695 return cfg_hooks
->predicted_by_p (bb
, predictor
);
698 /* Merges basic block B into basic block A. */
701 merge_blocks (basic_block a
, basic_block b
)
706 if (!cfg_hooks
->merge_blocks
)
707 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
709 cfg_hooks
->merge_blocks (a
, b
);
711 /* If we merge a loop header into its predecessor, update the loop
713 if (current_loops
!= NULL
)
715 if (b
->loop_father
->header
== b
)
717 remove_bb_from_loops (a
);
718 add_bb_to_loop (a
, b
->loop_father
);
719 a
->loop_father
->header
= a
;
721 remove_bb_from_loops (b
);
724 /* Normally there should only be one successor of A and that is B, but
725 partway though the merge of blocks for conditional_execution we'll
726 be merging a TEST block with THEN and ELSE successors. Free the
727 whole lot of them and hope the caller knows what they're doing. */
729 while (EDGE_COUNT (a
->succs
) != 0)
730 remove_edge (EDGE_SUCC (a
, 0));
732 /* Adjust the edges out of B for the new owner. */
733 FOR_EACH_EDGE (e
, ei
, b
->succs
)
736 if (current_loops
!= NULL
)
737 rescan_loop_exit (e
, true, false);
740 a
->flags
|= b
->flags
;
742 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
743 b
->preds
= b
->succs
= NULL
;
745 if (dom_info_available_p (CDI_DOMINATORS
))
746 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
748 if (dom_info_available_p (CDI_DOMINATORS
))
749 delete_from_dominance_info (CDI_DOMINATORS
, b
);
750 if (dom_info_available_p (CDI_POST_DOMINATORS
))
751 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
756 /* Split BB into entry part and the rest (the rest is the newly created block).
757 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
758 part. Returns the edge connecting the entry part to the rest. */
761 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
762 void (*new_bb_cbk
) (basic_block
))
766 basic_block dummy
, jump
;
767 struct loop
*loop
, *ploop
, *cloop
;
769 if (!cfg_hooks
->make_forwarder_block
)
770 internal_error ("%s does not support make_forwarder_block",
773 fallthru
= split_block_after_labels (bb
);
774 dummy
= fallthru
->src
;
777 /* Redirect back edges we want to keep. */
778 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
782 if (redirect_edge_p (e
))
788 dummy
->frequency
-= EDGE_FREQUENCY (e
);
789 dummy
->count
-= e
->count
;
790 if (dummy
->frequency
< 0)
791 dummy
->frequency
= 0;
792 if (dummy
->count
< 0)
794 fallthru
->count
-= e
->count
;
795 if (fallthru
->count
< 0)
799 jump
= redirect_edge_and_branch_force (e
, bb
);
802 /* If we redirected the loop latch edge, the JUMP block now acts like
803 the new latch of the loop. */
804 if (current_loops
!= NULL
805 && dummy
->loop_father
!= NULL
806 && dummy
->loop_father
->header
== dummy
807 && dummy
->loop_father
->latch
== e_src
)
808 dummy
->loop_father
->latch
= jump
;
810 if (new_bb_cbk
!= NULL
)
815 if (dom_info_available_p (CDI_DOMINATORS
))
817 VEC (basic_block
, heap
) *doms_to_fix
= VEC_alloc (basic_block
, heap
, 2);
818 VEC_quick_push (basic_block
, doms_to_fix
, dummy
);
819 VEC_quick_push (basic_block
, doms_to_fix
, bb
);
820 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
821 VEC_free (basic_block
, heap
, doms_to_fix
);
824 if (current_loops
!= NULL
)
826 /* If we do not split a loop header, then both blocks belong to the
827 same loop. In case we split loop header and do not redirect the
828 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
829 BB becomes the new header. If latch is not recorded for the loop,
830 we leave this updating on the caller (this may only happen during
832 loop
= dummy
->loop_father
;
833 if (loop
->header
== dummy
834 && loop
->latch
!= NULL
835 && find_edge (loop
->latch
, dummy
) == NULL
)
837 remove_bb_from_loops (dummy
);
841 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
843 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
845 add_bb_to_loop (dummy
, cloop
);
848 /* In case we split loop latch, update it. */
849 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
850 if (ploop
->latch
== dummy
)
854 cfg_hooks
->make_forwarder_block (fallthru
);
859 /* Try to make the edge fallthru. */
862 tidy_fallthru_edge (edge e
)
864 if (cfg_hooks
->tidy_fallthru_edge
)
865 cfg_hooks
->tidy_fallthru_edge (e
);
868 /* Fix up edges that now fall through, or rather should now fall through
869 but previously required a jump around now deleted blocks. Simplify
870 the search by only examining blocks numerically adjacent, since this
871 is how they were created.
873 ??? This routine is currently RTL specific. */
876 tidy_fallthru_edges (void)
880 if (!cfg_hooks
->tidy_fallthru_edge
)
883 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
886 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
892 /* We care about simple conditional or unconditional jumps with
895 If we had a conditional branch to the next instruction when
896 CFG was built, then there will only be one out edge for the
897 block which ended with the conditional branch (since we do
898 not create duplicate edges).
900 Furthermore, the edge will be marked as a fallthru because we
901 merge the flags for the duplicate edges. So we do not want to
902 check that the edge is not a FALLTHRU edge. */
904 if (single_succ_p (b
))
906 s
= single_succ_edge (b
);
907 if (! (s
->flags
& EDGE_COMPLEX
)
909 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
910 tidy_fallthru_edge (s
);
915 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
916 (and possibly create new basic block) to make edge non-fallthru.
917 Return newly created BB or NULL if none. */
920 force_nonfallthru (edge e
)
922 basic_block ret
, src
= e
->src
;
924 if (!cfg_hooks
->force_nonfallthru
)
925 internal_error ("%s does not support force_nonfallthru",
928 ret
= cfg_hooks
->force_nonfallthru (e
);
931 if (dom_info_available_p (CDI_DOMINATORS
))
932 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
934 if (current_loops
!= NULL
)
937 = find_common_loop (single_pred (ret
)->loop_father
,
938 single_succ (ret
)->loop_father
);
939 rescan_loop_exit (e
, false, true);
940 add_bb_to_loop (ret
, loop
);
947 /* Returns true if we can duplicate basic block BB. */
950 can_duplicate_block_p (const_basic_block bb
)
952 if (!cfg_hooks
->can_duplicate_block_p
)
953 internal_error ("%s does not support can_duplicate_block_p",
956 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
959 return cfg_hooks
->can_duplicate_block_p (bb
);
962 /* Duplicates basic block BB and redirects edge E to it. Returns the
963 new basic block. The new basic block is placed after the basic block
967 duplicate_block (basic_block bb
, edge e
, basic_block after
)
971 gcov_type new_count
= e
? e
->count
: 0;
974 if (!cfg_hooks
->duplicate_block
)
975 internal_error ("%s does not support duplicate_block",
978 if (bb
->count
< new_count
)
979 new_count
= bb
->count
;
981 gcc_checking_assert (can_duplicate_block_p (bb
));
983 new_bb
= cfg_hooks
->duplicate_block (bb
);
985 move_block_after (new_bb
, after
);
987 new_bb
->loop_depth
= bb
->loop_depth
;
988 new_bb
->flags
= bb
->flags
;
989 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
991 /* Since we are creating edges from a new block to successors
992 of another block (which therefore are known to be disjoint), there
993 is no need to actually check for duplicated edges. */
994 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
995 n
->probability
= s
->probability
;
998 /* Take care for overflows! */
999 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1000 s
->count
-= n
->count
;
1003 n
->count
= s
->count
;
1009 new_bb
->count
= new_count
;
1010 bb
->count
-= new_count
;
1012 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1013 bb
->frequency
-= EDGE_FREQUENCY (e
);
1015 redirect_edge_and_branch_force (e
, new_bb
);
1019 if (bb
->frequency
< 0)
1024 new_bb
->count
= bb
->count
;
1025 new_bb
->frequency
= bb
->frequency
;
1028 set_bb_original (new_bb
, bb
);
1029 set_bb_copy (bb
, new_bb
);
1031 /* Add the new block to the copy of the loop of BB, or directly to the loop
1032 of BB if the loop is not being copied. */
1033 if (current_loops
!= NULL
)
1035 struct loop
*cloop
= bb
->loop_father
;
1036 struct loop
*copy
= get_loop_copy (cloop
);
1037 /* If we copied the loop header block but not the loop
1038 we have created a loop with multiple entries. Ditch the loop,
1039 add the new block to the outer loop and arrange for a fixup. */
1041 && cloop
->header
== bb
)
1043 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1044 cloop
->header
= NULL
;
1045 cloop
->latch
= NULL
;
1046 loops_state_set (LOOPS_NEED_FIXUP
);
1050 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1051 /* If we copied the loop latch block but not the loop, adjust
1054 && cloop
->latch
== bb
)
1056 cloop
->latch
= NULL
;
1057 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1065 /* Return 1 if BB ends with a call, possibly followed by some
1066 instructions that must stay with the call, 0 otherwise. */
1069 block_ends_with_call_p (basic_block bb
)
1071 if (!cfg_hooks
->block_ends_with_call_p
)
1072 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1074 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1077 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1080 block_ends_with_condjump_p (const_basic_block bb
)
1082 if (!cfg_hooks
->block_ends_with_condjump_p
)
1083 internal_error ("%s does not support block_ends_with_condjump_p",
1086 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1089 /* Add fake edges to the function exit for any non constant and non noreturn
1090 calls, volatile inline assembly in the bitmap of blocks specified by
1091 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1094 The goal is to expose cases in which entering a basic block does not imply
1095 that all subsequent instructions must be executed. */
1098 flow_call_edges_add (sbitmap blocks
)
1100 if (!cfg_hooks
->flow_call_edges_add
)
1101 internal_error ("%s does not support flow_call_edges_add",
1104 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1107 /* This function is called immediately after edge E is added to the
1108 edge vector E->dest->preds. */
1111 execute_on_growing_pred (edge e
)
1113 if (cfg_hooks
->execute_on_growing_pred
)
1114 cfg_hooks
->execute_on_growing_pred (e
);
1117 /* This function is called immediately before edge E is removed from
1118 the edge vector E->dest->preds. */
1121 execute_on_shrinking_pred (edge e
)
1123 if (cfg_hooks
->execute_on_shrinking_pred
)
1124 cfg_hooks
->execute_on_shrinking_pred (e
);
1127 /* This is used inside loop versioning when we want to insert
1128 stmts/insns on the edges, which have a different behavior
1129 in tree's and in RTL, so we made a CFG hook. */
1131 lv_flush_pending_stmts (edge e
)
1133 if (cfg_hooks
->flush_pending_stmts
)
1134 cfg_hooks
->flush_pending_stmts (e
);
1137 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1138 a new version of the loop basic-blocks, the parameters here are
1139 exactly the same as in duplicate_loop_to_header_edge or
1140 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1141 additional work to maintain ssa information that's why there is
1142 a need to call the tree_duplicate_loop_to_header_edge rather
1143 than duplicate_loop_to_header_edge when we are in tree mode. */
1145 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1147 sbitmap wont_exit
, edge orig
,
1148 VEC (edge
, heap
) **to_remove
,
1151 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1152 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1158 /* Conditional jumps are represented differently in trees and RTL,
1159 this hook takes a basic block that is known to have a cond jump
1160 at its end and extracts the taken and not taken edges out of it
1161 and store it in E1 and E2 respectively. */
1163 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1165 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1166 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1169 /* Responsible for updating the ssa info (PHI nodes) on the
1170 new condition basic block that guards the versioned loop. */
1172 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1173 basic_block new_block
, edge e
)
1175 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1176 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1179 /* Conditions in trees and RTL are different so we need
1180 a different handling when we add the condition to the
1183 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1184 basic_block new_block
, void *cond
)
1186 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1187 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1190 /* Checks whether all N blocks in BBS array can be copied. */
1192 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1198 for (i
= 0; i
< n
; i
++)
1199 bbs
[i
]->flags
|= BB_DUPLICATED
;
1201 for (i
= 0; i
< n
; i
++)
1203 /* In case we should redirect abnormal edge during duplication, fail. */
1205 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1206 if ((e
->flags
& EDGE_ABNORMAL
)
1207 && (e
->dest
->flags
& BB_DUPLICATED
))
1213 if (!can_duplicate_block_p (bbs
[i
]))
1221 for (i
= 0; i
< n
; i
++)
1222 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1227 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1228 are placed into array NEW_BBS in the same order. Edges from basic blocks
1229 in BBS are also duplicated and copies of those of them
1230 that lead into BBS are redirected to appropriate newly created block. The
1231 function assigns bbs into loops (copy of basic block bb is assigned to
1232 bb->loop_father->copy loop, so this must be set up correctly in advance)
1233 and updates dominators locally (LOOPS structure that contains the information
1234 about dominators is passed to enable this).
1236 BASE is the superloop to that basic block belongs; if its header or latch
1237 is copied, we do not set the new blocks as header or latch.
1239 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1240 also in the same order.
1242 Newly created basic blocks are put after the basic block AFTER in the
1243 instruction stream, and the order of the blocks in BBS array is preserved. */
1246 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1247 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1248 struct loop
*base
, basic_block after
)
1251 basic_block bb
, new_bb
, dom_bb
;
1254 /* Duplicate bbs, update dominators, assign bbs to loops. */
1255 for (i
= 0; i
< n
; i
++)
1259 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1261 bb
->flags
|= BB_DUPLICATED
;
1262 /* Possibly set loop header. */
1263 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1264 new_bb
->loop_father
->header
= new_bb
;
1266 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1267 new_bb
->loop_father
->latch
= new_bb
;
1270 /* Set dominators. */
1271 for (i
= 0; i
< n
; i
++)
1274 new_bb
= new_bbs
[i
];
1276 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1277 if (dom_bb
->flags
& BB_DUPLICATED
)
1279 dom_bb
= get_bb_copy (dom_bb
);
1280 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1284 /* Redirect edges. */
1285 for (j
= 0; j
< num_edges
; j
++)
1286 new_edges
[j
] = NULL
;
1287 for (i
= 0; i
< n
; i
++)
1290 new_bb
= new_bbs
[i
];
1293 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1295 for (j
= 0; j
< num_edges
; j
++)
1296 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1299 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1301 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1305 /* Clear information about duplicates. */
1306 for (i
= 0; i
< n
; i
++)
1307 bbs
[i
]->flags
&= ~BB_DUPLICATED
;