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 if (flags
& TDF_BLOCKS
)
275 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
276 if (cfg_hooks
->dump_bb
)
277 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
278 if (flags
& TDF_BLOCKS
)
279 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
283 /* Dumps basic block BB to pretty-printer PP, for use as a label of
284 a DOT graph record-node. The implementation of this hook is
285 expected to write the label to the stream that is attached to PP.
286 Field separators between instructions are pipe characters printed
287 verbatim. Instructions should be written with some characters
288 escaped, using pp_write_text_as_dot_label_to_stream(). */
291 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
293 if (!cfg_hooks
->dump_bb_for_graph
)
294 internal_error ("%s does not support dump_bb_for_graph",
296 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
299 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
301 dump_flow_info (FILE *file
, int flags
)
305 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
307 dump_bb (file
, bb
, 0, flags
);
312 /* Like above, but dump to stderr. To be called from debuggers. */
313 void debug_flow_info (void);
315 debug_flow_info (void)
317 dump_flow_info (stderr
, TDF_DETAILS
);
320 /* Redirect edge E to the given basic block DEST and update underlying program
321 representation. Returns edge representing redirected branch (that may not
322 be equivalent to E in the case of duplicate edges being removed) or NULL
323 if edge is not easily redirectable for whatever reason. */
326 redirect_edge_and_branch (edge e
, basic_block dest
)
330 if (!cfg_hooks
->redirect_edge_and_branch
)
331 internal_error ("%s does not support redirect_edge_and_branch",
334 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
336 /* If RET != E, then either the redirection failed, or the edge E
337 was removed since RET already lead to the same destination. */
338 if (current_loops
!= NULL
&& ret
== e
)
339 rescan_loop_exit (e
, false, false);
344 /* Returns true if it is possible to remove the edge E by redirecting it
345 to the destination of the other edge going from its source. */
348 can_remove_branch_p (const_edge e
)
350 if (!cfg_hooks
->can_remove_branch_p
)
351 internal_error ("%s does not support can_remove_branch_p",
354 if (EDGE_COUNT (e
->src
->succs
) != 2)
357 return cfg_hooks
->can_remove_branch_p (e
);
360 /* Removes E, by redirecting it to the destination of the other edge going
361 from its source. Can_remove_branch_p must be true for E, hence this
362 operation cannot fail. */
365 remove_branch (edge e
)
368 basic_block src
= e
->src
;
371 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
373 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
374 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
376 e
= redirect_edge_and_branch (e
, other
->dest
);
377 gcc_assert (e
!= NULL
);
379 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
383 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
388 if (current_loops
!= NULL
)
389 rescan_loop_exit (e
, false, true);
391 /* This is probably not needed, but it doesn't hurt. */
392 /* FIXME: This should be called via a remove_edge hook. */
393 if (current_ir_type () == IR_GIMPLE
)
394 redirect_edge_var_map_clear (e
);
399 /* Like redirect_edge_succ but avoid possible duplicate edge. */
402 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
406 s
= find_edge (e
->src
, new_succ
);
409 s
->flags
|= e
->flags
;
410 s
->probability
+= e
->probability
;
411 if (s
->probability
> REG_BR_PROB_BASE
)
412 s
->probability
= REG_BR_PROB_BASE
;
413 s
->count
+= e
->count
;
414 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
415 redirect_edge_var_map_dup (s
, e
);
420 redirect_edge_succ (e
, new_succ
);
425 /* Redirect the edge E to basic block DEST even if it requires creating
426 of a new basic block; then it returns the newly created basic block.
427 Aborts when redirection is impossible. */
430 redirect_edge_and_branch_force (edge e
, basic_block dest
)
432 basic_block ret
, src
= e
->src
;
434 if (!cfg_hooks
->redirect_edge_and_branch_force
)
435 internal_error ("%s does not support redirect_edge_and_branch_force",
438 if (current_loops
!= NULL
)
439 rescan_loop_exit (e
, false, true);
441 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
443 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
444 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
446 if (current_loops
!= NULL
)
451 = find_common_loop (single_pred (ret
)->loop_father
,
452 single_succ (ret
)->loop_father
);
453 add_bb_to_loop (ret
, loop
);
455 else if (find_edge (src
, dest
) == e
)
456 rescan_loop_exit (e
, true, false);
462 /* Splits basic block BB after the specified instruction I (but at least after
463 the labels). If I is NULL, splits just after labels. The newly created edge
464 is returned. The new basic block is created just after the old one. */
467 split_block (basic_block bb
, void *i
)
472 if (!cfg_hooks
->split_block
)
473 internal_error ("%s does not support split_block", cfg_hooks
->name
);
475 new_bb
= cfg_hooks
->split_block (bb
, i
);
479 new_bb
->count
= bb
->count
;
480 new_bb
->frequency
= bb
->frequency
;
481 new_bb
->discriminator
= bb
->discriminator
;
483 if (dom_info_available_p (CDI_DOMINATORS
))
485 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
486 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
489 if (current_loops
!= NULL
)
491 add_bb_to_loop (new_bb
, bb
->loop_father
);
492 if (bb
->loop_father
->latch
== bb
)
493 bb
->loop_father
->latch
= new_bb
;
496 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
498 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
500 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
501 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
507 /* Splits block BB just after labels. The newly created edge is returned. */
510 split_block_after_labels (basic_block bb
)
512 return split_block (bb
, NULL
);
515 /* Moves block BB immediately after block AFTER. Returns false if the
516 movement was impossible. */
519 move_block_after (basic_block bb
, basic_block after
)
523 if (!cfg_hooks
->move_block_after
)
524 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
526 ret
= cfg_hooks
->move_block_after (bb
, after
);
531 /* Deletes the basic block BB. */
534 delete_basic_block (basic_block bb
)
536 if (!cfg_hooks
->delete_basic_block
)
537 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
539 cfg_hooks
->delete_basic_block (bb
);
541 if (current_loops
!= NULL
)
543 struct loop
*loop
= bb
->loop_father
;
545 /* If we remove the header or the latch of a loop, mark the loop for
546 removal by setting its header and latch to NULL. */
547 if (loop
->latch
== bb
548 || loop
->header
== bb
)
552 loops_state_set (LOOPS_NEED_FIXUP
);
555 remove_bb_from_loops (bb
);
558 /* Remove the edges into and out of this block. Note that there may
559 indeed be edges in, if we are removing an unreachable loop. */
560 while (EDGE_COUNT (bb
->preds
) != 0)
561 remove_edge (EDGE_PRED (bb
, 0));
562 while (EDGE_COUNT (bb
->succs
) != 0)
563 remove_edge (EDGE_SUCC (bb
, 0));
565 if (dom_info_available_p (CDI_DOMINATORS
))
566 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
567 if (dom_info_available_p (CDI_POST_DOMINATORS
))
568 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
570 /* Remove the basic block from the array. */
574 /* Splits edge E and returns the newly created basic block. */
580 gcov_type count
= e
->count
;
581 int freq
= EDGE_FREQUENCY (e
);
583 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
585 basic_block src
= e
->src
, dest
= e
->dest
;
587 if (!cfg_hooks
->split_edge
)
588 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
590 if (current_loops
!= NULL
)
591 rescan_loop_exit (e
, false, true);
593 ret
= cfg_hooks
->split_edge (e
);
595 ret
->frequency
= freq
;
596 single_succ_edge (ret
)->probability
= REG_BR_PROB_BASE
;
597 single_succ_edge (ret
)->count
= count
;
601 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
602 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
603 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
606 if (dom_info_available_p (CDI_DOMINATORS
))
607 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
609 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
611 /* There are two cases:
613 If the immediate dominator of e->dest is not e->src, it
616 If immediate dominator of e->dest is e->src, it may become
617 ret, provided that all other predecessors of e->dest are
618 dominated by e->dest. */
620 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
621 == single_pred (ret
))
624 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
626 if (f
== single_succ_edge (ret
))
629 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
635 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
639 if (current_loops
!= NULL
)
641 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
642 add_bb_to_loop (ret
, loop
);
644 if (loop
->latch
== src
)
651 /* Creates a new basic block just after the basic block AFTER.
652 HEAD and END are the first and the last statement belonging
653 to the block. If both are NULL, an empty block is created. */
656 create_basic_block (void *head
, void *end
, basic_block after
)
660 if (!cfg_hooks
->create_basic_block
)
661 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
663 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
665 if (dom_info_available_p (CDI_DOMINATORS
))
666 add_to_dominance_info (CDI_DOMINATORS
, ret
);
667 if (dom_info_available_p (CDI_POST_DOMINATORS
))
668 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
673 /* Creates an empty basic block just after basic block AFTER. */
676 create_empty_bb (basic_block after
)
678 return create_basic_block (NULL
, NULL
, after
);
681 /* Checks whether we may merge blocks BB1 and BB2. */
684 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
688 if (!cfg_hooks
->can_merge_blocks_p
)
689 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
691 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
697 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
699 if (!cfg_hooks
->predict_edge
)
700 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
702 cfg_hooks
->predict_edge (e
, predictor
, probability
);
706 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
708 if (!cfg_hooks
->predict_edge
)
709 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
711 return cfg_hooks
->predicted_by_p (bb
, predictor
);
714 /* Merges basic block B into basic block A. */
717 merge_blocks (basic_block a
, basic_block b
)
722 if (!cfg_hooks
->merge_blocks
)
723 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
725 cfg_hooks
->merge_blocks (a
, b
);
727 /* If we merge a loop header into its predecessor, update the loop
729 if (current_loops
!= NULL
)
731 if (b
->loop_father
->header
== b
)
733 remove_bb_from_loops (a
);
734 add_bb_to_loop (a
, b
->loop_father
);
735 a
->loop_father
->header
= a
;
737 remove_bb_from_loops (b
);
740 /* Normally there should only be one successor of A and that is B, but
741 partway though the merge of blocks for conditional_execution we'll
742 be merging a TEST block with THEN and ELSE successors. Free the
743 whole lot of them and hope the caller knows what they're doing. */
745 while (EDGE_COUNT (a
->succs
) != 0)
746 remove_edge (EDGE_SUCC (a
, 0));
748 /* Adjust the edges out of B for the new owner. */
749 FOR_EACH_EDGE (e
, ei
, b
->succs
)
752 if (current_loops
!= NULL
)
753 rescan_loop_exit (e
, true, false);
756 a
->flags
|= b
->flags
;
758 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
759 b
->preds
= b
->succs
= NULL
;
761 if (dom_info_available_p (CDI_DOMINATORS
))
762 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
764 if (dom_info_available_p (CDI_DOMINATORS
))
765 delete_from_dominance_info (CDI_DOMINATORS
, b
);
766 if (dom_info_available_p (CDI_POST_DOMINATORS
))
767 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
772 /* Split BB into entry part and the rest (the rest is the newly created block).
773 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
774 part. Returns the edge connecting the entry part to the rest. */
777 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
778 void (*new_bb_cbk
) (basic_block
))
782 basic_block dummy
, jump
;
783 struct loop
*loop
, *ploop
, *cloop
;
785 if (!cfg_hooks
->make_forwarder_block
)
786 internal_error ("%s does not support make_forwarder_block",
789 fallthru
= split_block_after_labels (bb
);
790 dummy
= fallthru
->src
;
793 /* Redirect back edges we want to keep. */
794 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
798 if (redirect_edge_p (e
))
804 dummy
->frequency
-= EDGE_FREQUENCY (e
);
805 dummy
->count
-= e
->count
;
806 if (dummy
->frequency
< 0)
807 dummy
->frequency
= 0;
808 if (dummy
->count
< 0)
810 fallthru
->count
-= e
->count
;
811 if (fallthru
->count
< 0)
815 jump
= redirect_edge_and_branch_force (e
, bb
);
818 /* If we redirected the loop latch edge, the JUMP block now acts like
819 the new latch of the loop. */
820 if (current_loops
!= NULL
821 && dummy
->loop_father
!= NULL
822 && dummy
->loop_father
->header
== dummy
823 && dummy
->loop_father
->latch
== e_src
)
824 dummy
->loop_father
->latch
= jump
;
826 if (new_bb_cbk
!= NULL
)
831 if (dom_info_available_p (CDI_DOMINATORS
))
833 vec
<basic_block
> doms_to_fix
;
834 doms_to_fix
.create (2);
835 doms_to_fix
.quick_push (dummy
);
836 doms_to_fix
.quick_push (bb
);
837 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
838 doms_to_fix
.release ();
841 if (current_loops
!= NULL
)
843 /* If we do not split a loop header, then both blocks belong to the
844 same loop. In case we split loop header and do not redirect the
845 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
846 BB becomes the new header. If latch is not recorded for the loop,
847 we leave this updating on the caller (this may only happen during
849 loop
= dummy
->loop_father
;
850 if (loop
->header
== dummy
851 && loop
->latch
!= NULL
852 && find_edge (loop
->latch
, dummy
) == NULL
)
854 remove_bb_from_loops (dummy
);
858 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
860 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
862 add_bb_to_loop (dummy
, cloop
);
865 /* In case we split loop latch, update it. */
866 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
867 if (ploop
->latch
== dummy
)
871 cfg_hooks
->make_forwarder_block (fallthru
);
876 /* Try to make the edge fallthru. */
879 tidy_fallthru_edge (edge e
)
881 if (cfg_hooks
->tidy_fallthru_edge
)
882 cfg_hooks
->tidy_fallthru_edge (e
);
885 /* Fix up edges that now fall through, or rather should now fall through
886 but previously required a jump around now deleted blocks. Simplify
887 the search by only examining blocks numerically adjacent, since this
888 is how they were created.
890 ??? This routine is currently RTL specific. */
893 tidy_fallthru_edges (void)
897 if (!cfg_hooks
->tidy_fallthru_edge
)
900 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
903 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
909 /* We care about simple conditional or unconditional jumps with
912 If we had a conditional branch to the next instruction when
913 CFG was built, then there will only be one out edge for the
914 block which ended with the conditional branch (since we do
915 not create duplicate edges).
917 Furthermore, the edge will be marked as a fallthru because we
918 merge the flags for the duplicate edges. So we do not want to
919 check that the edge is not a FALLTHRU edge. */
921 if (single_succ_p (b
))
923 s
= single_succ_edge (b
);
924 if (! (s
->flags
& EDGE_COMPLEX
)
926 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
927 tidy_fallthru_edge (s
);
932 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
933 (and possibly create new basic block) to make edge non-fallthru.
934 Return newly created BB or NULL if none. */
937 force_nonfallthru (edge e
)
939 basic_block ret
, src
= e
->src
;
941 if (!cfg_hooks
->force_nonfallthru
)
942 internal_error ("%s does not support force_nonfallthru",
945 ret
= cfg_hooks
->force_nonfallthru (e
);
948 if (dom_info_available_p (CDI_DOMINATORS
))
949 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
951 if (current_loops
!= NULL
)
954 = find_common_loop (single_pred (ret
)->loop_father
,
955 single_succ (ret
)->loop_father
);
956 rescan_loop_exit (e
, false, true);
957 add_bb_to_loop (ret
, loop
);
964 /* Returns true if we can duplicate basic block BB. */
967 can_duplicate_block_p (const_basic_block bb
)
969 if (!cfg_hooks
->can_duplicate_block_p
)
970 internal_error ("%s does not support can_duplicate_block_p",
973 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
976 return cfg_hooks
->can_duplicate_block_p (bb
);
979 /* Duplicates basic block BB and redirects edge E to it. Returns the
980 new basic block. The new basic block is placed after the basic block
984 duplicate_block (basic_block bb
, edge e
, basic_block after
)
988 gcov_type new_count
= e
? e
->count
: 0;
991 if (!cfg_hooks
->duplicate_block
)
992 internal_error ("%s does not support duplicate_block",
995 if (bb
->count
< new_count
)
996 new_count
= bb
->count
;
998 gcc_checking_assert (can_duplicate_block_p (bb
));
1000 new_bb
= cfg_hooks
->duplicate_block (bb
);
1002 move_block_after (new_bb
, after
);
1004 new_bb
->flags
= bb
->flags
;
1005 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1007 /* Since we are creating edges from a new block to successors
1008 of another block (which therefore are known to be disjoint), there
1009 is no need to actually check for duplicated edges. */
1010 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1011 n
->probability
= s
->probability
;
1014 /* Take care for overflows! */
1015 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1016 s
->count
-= n
->count
;
1019 n
->count
= s
->count
;
1025 new_bb
->count
= new_count
;
1026 bb
->count
-= new_count
;
1028 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1029 bb
->frequency
-= EDGE_FREQUENCY (e
);
1031 redirect_edge_and_branch_force (e
, new_bb
);
1035 if (bb
->frequency
< 0)
1040 new_bb
->count
= bb
->count
;
1041 new_bb
->frequency
= bb
->frequency
;
1044 set_bb_original (new_bb
, bb
);
1045 set_bb_copy (bb
, new_bb
);
1047 /* Add the new block to the copy of the loop of BB, or directly to the loop
1048 of BB if the loop is not being copied. */
1049 if (current_loops
!= NULL
)
1051 struct loop
*cloop
= bb
->loop_father
;
1052 struct loop
*copy
= get_loop_copy (cloop
);
1053 /* If we copied the loop header block but not the loop
1054 we have created a loop with multiple entries. Ditch the loop,
1055 add the new block to the outer loop and arrange for a fixup. */
1057 && cloop
->header
== bb
)
1059 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1060 cloop
->header
= NULL
;
1061 cloop
->latch
= NULL
;
1062 loops_state_set (LOOPS_NEED_FIXUP
);
1066 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1067 /* If we copied the loop latch block but not the loop, adjust
1070 && cloop
->latch
== bb
)
1072 cloop
->latch
= NULL
;
1073 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1081 /* Return 1 if BB ends with a call, possibly followed by some
1082 instructions that must stay with the call, 0 otherwise. */
1085 block_ends_with_call_p (basic_block bb
)
1087 if (!cfg_hooks
->block_ends_with_call_p
)
1088 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1090 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1093 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1096 block_ends_with_condjump_p (const_basic_block bb
)
1098 if (!cfg_hooks
->block_ends_with_condjump_p
)
1099 internal_error ("%s does not support block_ends_with_condjump_p",
1102 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1105 /* Add fake edges to the function exit for any non constant and non noreturn
1106 calls, volatile inline assembly in the bitmap of blocks specified by
1107 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1110 The goal is to expose cases in which entering a basic block does not imply
1111 that all subsequent instructions must be executed. */
1114 flow_call_edges_add (sbitmap blocks
)
1116 if (!cfg_hooks
->flow_call_edges_add
)
1117 internal_error ("%s does not support flow_call_edges_add",
1120 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1123 /* This function is called immediately after edge E is added to the
1124 edge vector E->dest->preds. */
1127 execute_on_growing_pred (edge e
)
1129 if (cfg_hooks
->execute_on_growing_pred
)
1130 cfg_hooks
->execute_on_growing_pred (e
);
1133 /* This function is called immediately before edge E is removed from
1134 the edge vector E->dest->preds. */
1137 execute_on_shrinking_pred (edge e
)
1139 if (cfg_hooks
->execute_on_shrinking_pred
)
1140 cfg_hooks
->execute_on_shrinking_pred (e
);
1143 /* This is used inside loop versioning when we want to insert
1144 stmts/insns on the edges, which have a different behavior
1145 in tree's and in RTL, so we made a CFG hook. */
1147 lv_flush_pending_stmts (edge e
)
1149 if (cfg_hooks
->flush_pending_stmts
)
1150 cfg_hooks
->flush_pending_stmts (e
);
1153 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1154 a new version of the loop basic-blocks, the parameters here are
1155 exactly the same as in duplicate_loop_to_header_edge or
1156 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1157 additional work to maintain ssa information that's why there is
1158 a need to call the tree_duplicate_loop_to_header_edge rather
1159 than duplicate_loop_to_header_edge when we are in tree mode. */
1161 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1163 sbitmap wont_exit
, edge orig
,
1164 vec
<edge
> *to_remove
,
1167 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1168 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1174 /* Conditional jumps are represented differently in trees and RTL,
1175 this hook takes a basic block that is known to have a cond jump
1176 at its end and extracts the taken and not taken edges out of it
1177 and store it in E1 and E2 respectively. */
1179 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1181 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1182 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1185 /* Responsible for updating the ssa info (PHI nodes) on the
1186 new condition basic block that guards the versioned loop. */
1188 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1189 basic_block new_block
, edge e
)
1191 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1192 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1195 /* Conditions in trees and RTL are different so we need
1196 a different handling when we add the condition to the
1199 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1200 basic_block new_block
, void *cond
)
1202 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1203 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1206 /* Checks whether all N blocks in BBS array can be copied. */
1208 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1214 for (i
= 0; i
< n
; i
++)
1215 bbs
[i
]->flags
|= BB_DUPLICATED
;
1217 for (i
= 0; i
< n
; i
++)
1219 /* In case we should redirect abnormal edge during duplication, fail. */
1221 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1222 if ((e
->flags
& EDGE_ABNORMAL
)
1223 && (e
->dest
->flags
& BB_DUPLICATED
))
1229 if (!can_duplicate_block_p (bbs
[i
]))
1237 for (i
= 0; i
< n
; i
++)
1238 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1243 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1244 are placed into array NEW_BBS in the same order. Edges from basic blocks
1245 in BBS are also duplicated and copies of those of them
1246 that lead into BBS are redirected to appropriate newly created block. The
1247 function assigns bbs into loops (copy of basic block bb is assigned to
1248 bb->loop_father->copy loop, so this must be set up correctly in advance)
1249 and updates dominators locally (LOOPS structure that contains the information
1250 about dominators is passed to enable this).
1252 BASE is the superloop to that basic block belongs; if its header or latch
1253 is copied, we do not set the new blocks as header or latch.
1255 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1256 also in the same order.
1258 Newly created basic blocks are put after the basic block AFTER in the
1259 instruction stream, and the order of the blocks in BBS array is preserved. */
1262 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1263 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1264 struct loop
*base
, basic_block after
)
1267 basic_block bb
, new_bb
, dom_bb
;
1270 /* Duplicate bbs, update dominators, assign bbs to loops. */
1271 for (i
= 0; i
< n
; i
++)
1275 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1277 bb
->flags
|= BB_DUPLICATED
;
1278 if (bb
->loop_father
)
1280 /* Possibly set loop header. */
1281 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1282 new_bb
->loop_father
->header
= new_bb
;
1284 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1285 new_bb
->loop_father
->latch
= new_bb
;
1289 /* Set dominators. */
1290 for (i
= 0; i
< n
; i
++)
1293 new_bb
= new_bbs
[i
];
1295 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1296 if (dom_bb
->flags
& BB_DUPLICATED
)
1298 dom_bb
= get_bb_copy (dom_bb
);
1299 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1303 /* Redirect edges. */
1304 for (j
= 0; j
< num_edges
; j
++)
1305 new_edges
[j
] = NULL
;
1306 for (i
= 0; i
< n
; i
++)
1309 new_bb
= new_bbs
[i
];
1312 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1314 for (j
= 0; j
< num_edges
; j
++)
1315 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1318 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1320 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1324 /* Clear information about duplicates. */
1325 for (i
= 0; i
< n
; i
++)
1326 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1329 /* Return true if BB contains only labels or non-executable
1332 empty_block_p (basic_block bb
)
1334 gcc_assert (cfg_hooks
->empty_block_p
);
1335 return cfg_hooks
->empty_block_p (bb
);
1338 /* Split a basic block if it ends with a conditional branch and if
1339 the other part of the block is not empty. */
1341 split_block_before_cond_jump (basic_block bb
)
1343 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1344 return cfg_hooks
->split_block_before_cond_jump (bb
);
1347 /* Work-horse for passes.c:check_profile_consistency.
1348 Do book-keeping of the CFG for the profile consistency checker.
1349 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1350 then do post-pass accounting. Store the counting in RECORD. */
1353 account_profile_record (struct profile_record
*record
, int after_pass
)
1363 if (bb
!= EXIT_BLOCK_PTR_FOR_FUNCTION (cfun
)
1364 && profile_status
!= PROFILE_ABSENT
)
1367 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1368 sum
+= e
->probability
;
1369 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1370 record
->num_mismatched_freq_out
[after_pass
]++;
1372 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1374 if (EDGE_COUNT (bb
->succs
)
1375 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1376 record
->num_mismatched_count_out
[after_pass
]++;
1378 if (bb
!= ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1379 && profile_status
!= PROFILE_ABSENT
)
1382 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1383 sum
+= EDGE_FREQUENCY (e
);
1384 if (abs (sum
- bb
->frequency
) > 100
1385 || (MAX (sum
, bb
->frequency
) > 10
1386 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1387 record
->num_mismatched_freq_in
[after_pass
]++;
1389 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1391 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1392 record
->num_mismatched_count_in
[after_pass
]++;
1394 if (bb
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1395 || bb
== EXIT_BLOCK_PTR_FOR_FUNCTION (cfun
))
1397 gcc_assert (cfg_hooks
->account_profile_record
);
1398 cfg_hooks
->account_profile_record(bb
, after_pass
, record
);