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
, true, false);
275 if (cfg_hooks
->dump_bb
)
276 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
277 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
281 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
283 dump_flow_info (FILE *file
, int flags
)
287 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
289 dump_bb (file
, bb
, 0, flags
);
294 /* Like above, but dump to stderr. To be called from debuggers. */
295 void debug_flow_info (void);
297 debug_flow_info (void)
299 dump_flow_info (stderr
, TDF_DETAILS
);
302 /* Redirect edge E to the given basic block DEST and update underlying program
303 representation. Returns edge representing redirected branch (that may not
304 be equivalent to E in the case of duplicate edges being removed) or NULL
305 if edge is not easily redirectable for whatever reason. */
308 redirect_edge_and_branch (edge e
, basic_block dest
)
312 if (!cfg_hooks
->redirect_edge_and_branch
)
313 internal_error ("%s does not support redirect_edge_and_branch",
316 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
318 /* If RET != E, then either the redirection failed, or the edge E
319 was removed since RET already lead to the same destination. */
320 if (current_loops
!= NULL
&& ret
== e
)
321 rescan_loop_exit (e
, false, false);
326 /* Returns true if it is possible to remove the edge E by redirecting it
327 to the destination of the other edge going from its source. */
330 can_remove_branch_p (const_edge e
)
332 if (!cfg_hooks
->can_remove_branch_p
)
333 internal_error ("%s does not support can_remove_branch_p",
336 if (EDGE_COUNT (e
->src
->succs
) != 2)
339 return cfg_hooks
->can_remove_branch_p (e
);
342 /* Removes E, by redirecting it to the destination of the other edge going
343 from its source. Can_remove_branch_p must be true for E, hence this
344 operation cannot fail. */
347 remove_branch (edge e
)
350 basic_block src
= e
->src
;
353 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
355 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
356 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
358 e
= redirect_edge_and_branch (e
, other
->dest
);
359 gcc_assert (e
!= NULL
);
361 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
365 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
370 if (current_loops
!= NULL
)
371 rescan_loop_exit (e
, false, true);
373 /* This is probably not needed, but it doesn't hurt. */
374 /* FIXME: This should be called via a remove_edge hook. */
375 if (current_ir_type () == IR_GIMPLE
)
376 redirect_edge_var_map_clear (e
);
381 /* Like redirect_edge_succ but avoid possible duplicate edge. */
384 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
388 s
= find_edge (e
->src
, new_succ
);
391 s
->flags
|= e
->flags
;
392 s
->probability
+= e
->probability
;
393 if (s
->probability
> REG_BR_PROB_BASE
)
394 s
->probability
= REG_BR_PROB_BASE
;
395 s
->count
+= e
->count
;
396 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
397 redirect_edge_var_map_dup (s
, e
);
402 redirect_edge_succ (e
, new_succ
);
407 /* Redirect the edge E to basic block DEST even if it requires creating
408 of a new basic block; then it returns the newly created basic block.
409 Aborts when redirection is impossible. */
412 redirect_edge_and_branch_force (edge e
, basic_block dest
)
414 basic_block ret
, src
= e
->src
;
416 if (!cfg_hooks
->redirect_edge_and_branch_force
)
417 internal_error ("%s does not support redirect_edge_and_branch_force",
420 if (current_loops
!= NULL
)
421 rescan_loop_exit (e
, false, true);
423 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
425 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
426 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
428 if (current_loops
!= NULL
)
433 = find_common_loop (single_pred (ret
)->loop_father
,
434 single_succ (ret
)->loop_father
);
435 add_bb_to_loop (ret
, loop
);
437 else if (find_edge (src
, dest
) == e
)
438 rescan_loop_exit (e
, true, false);
444 /* Splits basic block BB after the specified instruction I (but at least after
445 the labels). If I is NULL, splits just after labels. The newly created edge
446 is returned. The new basic block is created just after the old one. */
449 split_block (basic_block bb
, void *i
)
454 if (!cfg_hooks
->split_block
)
455 internal_error ("%s does not support split_block", cfg_hooks
->name
);
457 new_bb
= cfg_hooks
->split_block (bb
, i
);
461 new_bb
->count
= bb
->count
;
462 new_bb
->frequency
= bb
->frequency
;
463 new_bb
->loop_depth
= bb
->loop_depth
;
464 new_bb
->discriminator
= bb
->discriminator
;
466 if (dom_info_available_p (CDI_DOMINATORS
))
468 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
469 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
472 if (current_loops
!= NULL
)
474 add_bb_to_loop (new_bb
, bb
->loop_father
);
475 if (bb
->loop_father
->latch
== bb
)
476 bb
->loop_father
->latch
= new_bb
;
479 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
481 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
483 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
484 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
490 /* Splits block BB just after labels. The newly created edge is returned. */
493 split_block_after_labels (basic_block bb
)
495 return split_block (bb
, NULL
);
498 /* Moves block BB immediately after block AFTER. Returns false if the
499 movement was impossible. */
502 move_block_after (basic_block bb
, basic_block after
)
506 if (!cfg_hooks
->move_block_after
)
507 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
509 ret
= cfg_hooks
->move_block_after (bb
, after
);
514 /* Deletes the basic block BB. */
517 delete_basic_block (basic_block bb
)
519 if (!cfg_hooks
->delete_basic_block
)
520 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
522 cfg_hooks
->delete_basic_block (bb
);
524 if (current_loops
!= NULL
)
526 struct loop
*loop
= bb
->loop_father
;
528 /* If we remove the header or the latch of a loop, mark the loop for
529 removal by setting its header and latch to NULL. */
530 if (loop
->latch
== bb
531 || loop
->header
== bb
)
535 loops_state_set (LOOPS_NEED_FIXUP
);
538 remove_bb_from_loops (bb
);
541 /* Remove the edges into and out of this block. Note that there may
542 indeed be edges in, if we are removing an unreachable loop. */
543 while (EDGE_COUNT (bb
->preds
) != 0)
544 remove_edge (EDGE_PRED (bb
, 0));
545 while (EDGE_COUNT (bb
->succs
) != 0)
546 remove_edge (EDGE_SUCC (bb
, 0));
548 if (dom_info_available_p (CDI_DOMINATORS
))
549 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
550 if (dom_info_available_p (CDI_POST_DOMINATORS
))
551 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
553 /* Remove the basic block from the array. */
557 /* Splits edge E and returns the newly created basic block. */
563 gcov_type count
= e
->count
;
564 int freq
= EDGE_FREQUENCY (e
);
566 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
568 basic_block src
= e
->src
, dest
= e
->dest
;
570 if (!cfg_hooks
->split_edge
)
571 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
573 if (current_loops
!= NULL
)
574 rescan_loop_exit (e
, false, true);
576 ret
= cfg_hooks
->split_edge (e
);
578 ret
->frequency
= freq
;
579 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
580 single_succ_edge (ret
)->count
= count
;
584 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
585 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
586 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
589 if (dom_info_available_p (CDI_DOMINATORS
))
590 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
592 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
594 /* There are two cases:
596 If the immediate dominator of e->dest is not e->src, it
599 If immediate dominator of e->dest is e->src, it may become
600 ret, provided that all other predecessors of e->dest are
601 dominated by e->dest. */
603 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
604 == single_pred (ret
))
607 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
609 if (f
== single_succ_edge (ret
))
612 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
618 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
622 if (current_loops
!= NULL
)
624 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
625 add_bb_to_loop (ret
, loop
);
627 if (loop
->latch
== src
)
634 /* Creates a new basic block just after the basic block AFTER.
635 HEAD and END are the first and the last statement belonging
636 to the block. If both are NULL, an empty block is created. */
639 create_basic_block (void *head
, void *end
, basic_block after
)
643 if (!cfg_hooks
->create_basic_block
)
644 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
646 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
648 if (dom_info_available_p (CDI_DOMINATORS
))
649 add_to_dominance_info (CDI_DOMINATORS
, ret
);
650 if (dom_info_available_p (CDI_POST_DOMINATORS
))
651 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
656 /* Creates an empty basic block just after basic block AFTER. */
659 create_empty_bb (basic_block after
)
661 return create_basic_block (NULL
, NULL
, after
);
664 /* Checks whether we may merge blocks BB1 and BB2. */
667 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
671 if (!cfg_hooks
->can_merge_blocks_p
)
672 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
674 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
680 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
682 if (!cfg_hooks
->predict_edge
)
683 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
685 cfg_hooks
->predict_edge (e
, predictor
, probability
);
689 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
691 if (!cfg_hooks
->predict_edge
)
692 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
694 return cfg_hooks
->predicted_by_p (bb
, predictor
);
697 /* Merges basic block B into basic block A. */
700 merge_blocks (basic_block a
, basic_block b
)
705 if (!cfg_hooks
->merge_blocks
)
706 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
708 cfg_hooks
->merge_blocks (a
, b
);
710 /* If we merge a loop header into its predecessor, update the loop
712 if (current_loops
!= NULL
)
714 if (b
->loop_father
->header
== b
)
716 remove_bb_from_loops (a
);
717 add_bb_to_loop (a
, b
->loop_father
);
718 a
->loop_father
->header
= a
;
720 remove_bb_from_loops (b
);
723 /* Normally there should only be one successor of A and that is B, but
724 partway though the merge of blocks for conditional_execution we'll
725 be merging a TEST block with THEN and ELSE successors. Free the
726 whole lot of them and hope the caller knows what they're doing. */
728 while (EDGE_COUNT (a
->succs
) != 0)
729 remove_edge (EDGE_SUCC (a
, 0));
731 /* Adjust the edges out of B for the new owner. */
732 FOR_EACH_EDGE (e
, ei
, b
->succs
)
735 if (current_loops
!= NULL
)
736 rescan_loop_exit (e
, true, false);
739 a
->flags
|= b
->flags
;
741 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
742 b
->preds
= b
->succs
= NULL
;
744 if (dom_info_available_p (CDI_DOMINATORS
))
745 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
747 if (dom_info_available_p (CDI_DOMINATORS
))
748 delete_from_dominance_info (CDI_DOMINATORS
, b
);
749 if (dom_info_available_p (CDI_POST_DOMINATORS
))
750 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
755 /* Split BB into entry part and the rest (the rest is the newly created block).
756 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
757 part. Returns the edge connecting the entry part to the rest. */
760 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
761 void (*new_bb_cbk
) (basic_block
))
765 basic_block dummy
, jump
;
766 struct loop
*loop
, *ploop
, *cloop
;
768 if (!cfg_hooks
->make_forwarder_block
)
769 internal_error ("%s does not support make_forwarder_block",
772 fallthru
= split_block_after_labels (bb
);
773 dummy
= fallthru
->src
;
776 /* Redirect back edges we want to keep. */
777 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
781 if (redirect_edge_p (e
))
787 dummy
->frequency
-= EDGE_FREQUENCY (e
);
788 dummy
->count
-= e
->count
;
789 if (dummy
->frequency
< 0)
790 dummy
->frequency
= 0;
791 if (dummy
->count
< 0)
793 fallthru
->count
-= e
->count
;
794 if (fallthru
->count
< 0)
798 jump
= redirect_edge_and_branch_force (e
, bb
);
801 /* If we redirected the loop latch edge, the JUMP block now acts like
802 the new latch of the loop. */
803 if (current_loops
!= NULL
804 && dummy
->loop_father
!= NULL
805 && dummy
->loop_father
->header
== dummy
806 && dummy
->loop_father
->latch
== e_src
)
807 dummy
->loop_father
->latch
= jump
;
809 if (new_bb_cbk
!= NULL
)
814 if (dom_info_available_p (CDI_DOMINATORS
))
816 VEC (basic_block
, heap
) *doms_to_fix
= VEC_alloc (basic_block
, heap
, 2);
817 VEC_quick_push (basic_block
, doms_to_fix
, dummy
);
818 VEC_quick_push (basic_block
, doms_to_fix
, bb
);
819 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
820 VEC_free (basic_block
, heap
, doms_to_fix
);
823 if (current_loops
!= NULL
)
825 /* If we do not split a loop header, then both blocks belong to the
826 same loop. In case we split loop header and do not redirect the
827 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
828 BB becomes the new header. If latch is not recorded for the loop,
829 we leave this updating on the caller (this may only happen during
831 loop
= dummy
->loop_father
;
832 if (loop
->header
== dummy
833 && loop
->latch
!= NULL
834 && find_edge (loop
->latch
, dummy
) == NULL
)
836 remove_bb_from_loops (dummy
);
840 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
842 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
844 add_bb_to_loop (dummy
, cloop
);
847 /* In case we split loop latch, update it. */
848 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
849 if (ploop
->latch
== dummy
)
853 cfg_hooks
->make_forwarder_block (fallthru
);
858 /* Try to make the edge fallthru. */
861 tidy_fallthru_edge (edge e
)
863 if (cfg_hooks
->tidy_fallthru_edge
)
864 cfg_hooks
->tidy_fallthru_edge (e
);
867 /* Fix up edges that now fall through, or rather should now fall through
868 but previously required a jump around now deleted blocks. Simplify
869 the search by only examining blocks numerically adjacent, since this
870 is how they were created.
872 ??? This routine is currently RTL specific. */
875 tidy_fallthru_edges (void)
879 if (!cfg_hooks
->tidy_fallthru_edge
)
882 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
885 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
891 /* We care about simple conditional or unconditional jumps with
894 If we had a conditional branch to the next instruction when
895 CFG was built, then there will only be one out edge for the
896 block which ended with the conditional branch (since we do
897 not create duplicate edges).
899 Furthermore, the edge will be marked as a fallthru because we
900 merge the flags for the duplicate edges. So we do not want to
901 check that the edge is not a FALLTHRU edge. */
903 if (single_succ_p (b
))
905 s
= single_succ_edge (b
);
906 if (! (s
->flags
& EDGE_COMPLEX
)
908 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
909 tidy_fallthru_edge (s
);
914 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
915 (and possibly create new basic block) to make edge non-fallthru.
916 Return newly created BB or NULL if none. */
919 force_nonfallthru (edge e
)
921 basic_block ret
, src
= e
->src
;
923 if (!cfg_hooks
->force_nonfallthru
)
924 internal_error ("%s does not support force_nonfallthru",
927 ret
= cfg_hooks
->force_nonfallthru (e
);
930 if (dom_info_available_p (CDI_DOMINATORS
))
931 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
933 if (current_loops
!= NULL
)
936 = find_common_loop (single_pred (ret
)->loop_father
,
937 single_succ (ret
)->loop_father
);
938 rescan_loop_exit (e
, false, true);
939 add_bb_to_loop (ret
, loop
);
946 /* Returns true if we can duplicate basic block BB. */
949 can_duplicate_block_p (const_basic_block bb
)
951 if (!cfg_hooks
->can_duplicate_block_p
)
952 internal_error ("%s does not support can_duplicate_block_p",
955 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
958 return cfg_hooks
->can_duplicate_block_p (bb
);
961 /* Duplicates basic block BB and redirects edge E to it. Returns the
962 new basic block. The new basic block is placed after the basic block
966 duplicate_block (basic_block bb
, edge e
, basic_block after
)
970 gcov_type new_count
= e
? e
->count
: 0;
973 if (!cfg_hooks
->duplicate_block
)
974 internal_error ("%s does not support duplicate_block",
977 if (bb
->count
< new_count
)
978 new_count
= bb
->count
;
980 gcc_checking_assert (can_duplicate_block_p (bb
));
982 new_bb
= cfg_hooks
->duplicate_block (bb
);
984 move_block_after (new_bb
, after
);
986 new_bb
->loop_depth
= bb
->loop_depth
;
987 new_bb
->flags
= bb
->flags
;
988 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
990 /* Since we are creating edges from a new block to successors
991 of another block (which therefore are known to be disjoint), there
992 is no need to actually check for duplicated edges. */
993 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
994 n
->probability
= s
->probability
;
997 /* Take care for overflows! */
998 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
999 s
->count
-= n
->count
;
1002 n
->count
= s
->count
;
1008 new_bb
->count
= new_count
;
1009 bb
->count
-= new_count
;
1011 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1012 bb
->frequency
-= EDGE_FREQUENCY (e
);
1014 redirect_edge_and_branch_force (e
, new_bb
);
1018 if (bb
->frequency
< 0)
1023 new_bb
->count
= bb
->count
;
1024 new_bb
->frequency
= bb
->frequency
;
1027 set_bb_original (new_bb
, bb
);
1028 set_bb_copy (bb
, new_bb
);
1030 /* Add the new block to the copy of the loop of BB, or directly to the loop
1031 of BB if the loop is not being copied. */
1032 if (current_loops
!= NULL
)
1034 struct loop
*cloop
= bb
->loop_father
;
1035 struct loop
*copy
= get_loop_copy (cloop
);
1036 /* If we copied the loop header block but not the loop
1037 we have created a loop with multiple entries. Ditch the loop,
1038 add the new block to the outer loop and arrange for a fixup. */
1040 && cloop
->header
== bb
)
1042 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1043 cloop
->header
= NULL
;
1044 cloop
->latch
= NULL
;
1045 loops_state_set (LOOPS_NEED_FIXUP
);
1049 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1050 /* If we copied the loop latch block but not the loop, adjust
1053 && cloop
->latch
== bb
)
1055 cloop
->latch
= NULL
;
1056 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1064 /* Return 1 if BB ends with a call, possibly followed by some
1065 instructions that must stay with the call, 0 otherwise. */
1068 block_ends_with_call_p (basic_block bb
)
1070 if (!cfg_hooks
->block_ends_with_call_p
)
1071 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1073 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1076 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1079 block_ends_with_condjump_p (const_basic_block bb
)
1081 if (!cfg_hooks
->block_ends_with_condjump_p
)
1082 internal_error ("%s does not support block_ends_with_condjump_p",
1085 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1088 /* Add fake edges to the function exit for any non constant and non noreturn
1089 calls, volatile inline assembly in the bitmap of blocks specified by
1090 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1093 The goal is to expose cases in which entering a basic block does not imply
1094 that all subsequent instructions must be executed. */
1097 flow_call_edges_add (sbitmap blocks
)
1099 if (!cfg_hooks
->flow_call_edges_add
)
1100 internal_error ("%s does not support flow_call_edges_add",
1103 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1106 /* This function is called immediately after edge E is added to the
1107 edge vector E->dest->preds. */
1110 execute_on_growing_pred (edge e
)
1112 if (cfg_hooks
->execute_on_growing_pred
)
1113 cfg_hooks
->execute_on_growing_pred (e
);
1116 /* This function is called immediately before edge E is removed from
1117 the edge vector E->dest->preds. */
1120 execute_on_shrinking_pred (edge e
)
1122 if (cfg_hooks
->execute_on_shrinking_pred
)
1123 cfg_hooks
->execute_on_shrinking_pred (e
);
1126 /* This is used inside loop versioning when we want to insert
1127 stmts/insns on the edges, which have a different behavior
1128 in tree's and in RTL, so we made a CFG hook. */
1130 lv_flush_pending_stmts (edge e
)
1132 if (cfg_hooks
->flush_pending_stmts
)
1133 cfg_hooks
->flush_pending_stmts (e
);
1136 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1137 a new version of the loop basic-blocks, the parameters here are
1138 exactly the same as in duplicate_loop_to_header_edge or
1139 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1140 additional work to maintain ssa information that's why there is
1141 a need to call the tree_duplicate_loop_to_header_edge rather
1142 than duplicate_loop_to_header_edge when we are in tree mode. */
1144 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1146 sbitmap wont_exit
, edge orig
,
1147 VEC (edge
, heap
) **to_remove
,
1150 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1151 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1157 /* Conditional jumps are represented differently in trees and RTL,
1158 this hook takes a basic block that is known to have a cond jump
1159 at its end and extracts the taken and not taken edges out of it
1160 and store it in E1 and E2 respectively. */
1162 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1164 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1165 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1168 /* Responsible for updating the ssa info (PHI nodes) on the
1169 new condition basic block that guards the versioned loop. */
1171 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1172 basic_block new_block
, edge e
)
1174 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1175 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1178 /* Conditions in trees and RTL are different so we need
1179 a different handling when we add the condition to the
1182 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1183 basic_block new_block
, void *cond
)
1185 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1186 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1189 /* Checks whether all N blocks in BBS array can be copied. */
1191 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1197 for (i
= 0; i
< n
; i
++)
1198 bbs
[i
]->flags
|= BB_DUPLICATED
;
1200 for (i
= 0; i
< n
; i
++)
1202 /* In case we should redirect abnormal edge during duplication, fail. */
1204 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1205 if ((e
->flags
& EDGE_ABNORMAL
)
1206 && (e
->dest
->flags
& BB_DUPLICATED
))
1212 if (!can_duplicate_block_p (bbs
[i
]))
1220 for (i
= 0; i
< n
; i
++)
1221 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1226 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1227 are placed into array NEW_BBS in the same order. Edges from basic blocks
1228 in BBS are also duplicated and copies of those of them
1229 that lead into BBS are redirected to appropriate newly created block. The
1230 function assigns bbs into loops (copy of basic block bb is assigned to
1231 bb->loop_father->copy loop, so this must be set up correctly in advance)
1232 and updates dominators locally (LOOPS structure that contains the information
1233 about dominators is passed to enable this).
1235 BASE is the superloop to that basic block belongs; if its header or latch
1236 is copied, we do not set the new blocks as header or latch.
1238 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1239 also in the same order.
1241 Newly created basic blocks are put after the basic block AFTER in the
1242 instruction stream, and the order of the blocks in BBS array is preserved. */
1245 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1246 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1247 struct loop
*base
, basic_block after
)
1250 basic_block bb
, new_bb
, dom_bb
;
1253 /* Duplicate bbs, update dominators, assign bbs to loops. */
1254 for (i
= 0; i
< n
; i
++)
1258 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1260 bb
->flags
|= BB_DUPLICATED
;
1261 /* Possibly set loop header. */
1262 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1263 new_bb
->loop_father
->header
= new_bb
;
1265 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1266 new_bb
->loop_father
->latch
= new_bb
;
1269 /* Set dominators. */
1270 for (i
= 0; i
< n
; i
++)
1273 new_bb
= new_bbs
[i
];
1275 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1276 if (dom_bb
->flags
& BB_DUPLICATED
)
1278 dom_bb
= get_bb_copy (dom_bb
);
1279 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1283 /* Redirect edges. */
1284 for (j
= 0; j
< num_edges
; j
++)
1285 new_edges
[j
] = NULL
;
1286 for (i
= 0; i
< n
; i
++)
1289 new_bb
= new_bbs
[i
];
1292 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1294 for (j
= 0; j
< num_edges
; j
++)
1295 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1298 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1300 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1304 /* Clear information about duplicates. */
1305 for (i
= 0; i
< n
; i
++)
1306 bbs
[i
]->flags
&= ~BB_DUPLICATED
;